Ответы на вопросы по высшей математике (Вариант 3)

17. Задачи оптимизации. Методы спуска Методы оптимизации – методы поиска экстремума функции при наличии ограничений или без ограничений очень широко используются на практике. Это, прежде всего, оптимальное проектирование (выбор наилучших номинальных технологических режимов, элементов конструкций, структуры технологических цепочек, условий экономической деятельности, повышение доходностии т. д.), оптимальное управление построением нематематических моделей объектов управления (минимизации невязок различной структуры модели и реального объекта) и многие другие аспекты решения экономических и социальных проблем (например, управление запасами, трудовыми ресурсами, транспортными потоками и т. д.). Суть метода состоит в том, что, задав начальное приближение, выбирается направление движения по одной из покоординатных осей, причем, на последующих шагах идет циклический перебор направлений по координатным осям. Наиболее распространенным является метод покоординатного спуска с дроблением шага.

18. Оптимизация на основе генетических алгоритмов

Генети́ческий алгори́тм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе. Задача формализуется таким образом, чтобы её решение могло быть закодировано в виде вектора («генотипа») генов, где каждый ген может быть битом, числом или неким другим объектом. В классических реализациях генетического алгоритма (ГА) предполагается, что генотип имеет фиксированную длину. Однако существуют вариации ГА, свободные от этого ограничения.Некоторым, обычно случайным, образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием «функции приспособленности», в результате чего с каждым генотипом ассоциируется определённое значение («приспособленность»), которое определяет насколько хорошо фенотип, им описываемый, решает поставленную задачу.При выборе «функции приспособленности» (или fitness function в англоязычной литературе) важно следить, чтобы её «рельеф» был «гладким».Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» — crossover и «мутация» — mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение.Этот набор действий повторяется итеративно, так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:нахождение глобального, либо субоптимального решения;исчерпание числа поколений, отпущенных на эволюцию;исчерпание времени, отпущенного на эволюцию.Генетические алгоритмы служат, главным образом, для поиска решений в многомерных пространствах поиска. Таким образом, можно выделить следующие этапы генетического алгоритма: Задать целевую функцию (приспособленности) для особей популяции Создать начальную популяцию (Начало цикла) Размножение (скрещивание) Мутирование Вычислить значение целевой функции для всех особей Формирование нового поколения (селекция) Если выполняются условия остановки, то (конец цикла), иначе (начало цикла).

19. Полуаналитические методы решения дифференциальных уравнений. Метод Пикара и метод последовательного дифференцирования для решения задачи Коши

Самый распространенный способ исследования многих физических, механических, экологических, экономических, социальных и других явлений заключается в применении математической модели изучаемого явления. Часто используемый математический аппарат при описании таких моделей – обыкновенные дифференциальные уравнения (ОДУ) и системы ОДУ (СОДУ). Такими уравнениями можно описывать траектории движения небесных тел, модели нелинейной автоколебательной цепи. Ряд задач, описываемых уравнениями в частных производных, также сводятся к решению ОДУ. Например, задачи нахождения собственных колебаний мембраны, определение спектра собственных значений энергии частицы и другие. Различают три основных типа задач для ОДУ: задача Коши, краевая задача и задача об устойчивости решения. Данный метод решает задачу Коши. Для простоты записи ограничимся одним дифференциальным уравнением. Алгоритм легко обобщается на случай системы дифференциальных уравнений путем формальной замены и(х) и f(x,u) на соответствующие векторы. Метод Пикара является приближенным методом, обобщающим метод последовательных приближений.

20. Численные методы решения дифференциальных уравнения в форме задачи Коши. Явные и неявные схемы. Методы Рунге-Кутты для одного дифференциального уравнения и для системы ОДУ

Постановка задачи В области D ={a≤x≤b, |yi −yi 0|≤bi}∈Rn+1 определена функция f ≡f(x,y1,…,yn), (x,y)∈D. Необходимо найти решение dy dx = f(x,y) (1) удовлетворяющее начальному условию y(x0) = y0. (2) Используя метод последовательных приближений Пикара, можно получить точное решение y(x) задачи Коши (1),(2) как предел последовательности y0(x),y1(x),…,yk(x),…, (3) где yk(x) = y0(x)+Zx x0 f(x,yk−1(x))dx, k = 1,2…. (4) Для сходимости этой последовательности необходимо выполнение условий: f(x,y) непрерывна в D ; f(x,y) удовлетворяет условию Липшица по аргументу y kf(x, ˆ y)−f(x, ¯ y)k≤Lkˆ y−¯ yk (5) для всех x∈[a,b] и всех компонент векторов ˆ y и ¯ y . При этих предположениях yk(x) равномерно сходится к точному решению задачи Коши, поэтому для достаточно больших k отклонение ky(x)−yk(x)k не превышает заданной величины. Таким образом, в качестве искомого решения можно взять yk(x) . Практическая реализация этого метода затруднена по причине того, что для сложной функции f(x,y) интеграл не берется в квадратурах и решение нельзя получить в аналитическом виде. Константа Липшица L играет важную роль в численных методах. Обсуждаемые ниже численнные методы известны как дискретные, т.е. такие методы, посредством которых вычисляется последовательность приближений yi ≈ y(xi) на множестве точек xi+1 = xi + hi, i = 0,1,…,N −1; xN = b, hi > 0− шаг сетки. В большинстве рассматриваемых методов будем считать hi = h, h = const > 0, i = 1,2,…. Для облегчения изложения будем в дальнейшем рассматривать методы для скалярного случая (1) n = 1 и отдельно оговаривать их распространение на случай систем. Ме́тоды Ру́нге — Ку́тты (в литературе встречаются названия: ме́тоды Ру́нге — Ку́тта или же ме́тоды Ру́нге — Кутта́) — большой класс численных методов решения задачи Коши для обыкновенных дифференциальных уравнений и их систем. Первые методы данного класса были предложены около 1900 года немецкими математиками К. Рунге и М. В. Куттой.К классу методов Рунге — Кутты относятся явный метод Эйлера и модифицированный метод Эйлера с пересчётом, которые представляют собой соответственно методы первого и второго порядка точности. Существуют стандартные явные методы третьего порядка точности, не получившие широкого распространения. Наиболее часто используется и реализован в различных математических пакетах (Maple, MathCAD, Maxima) классический метод Рунге — Кутты, имеющий четвёртый порядок точности. При выполнении расчётов с повышенной точностью всё чаще применяются методы пятого и шестого порядков точности[1][2]. Построение схем более высокого порядка сопряжено с большими вычислительными трудностями[3].Методы седьмого порядка должны иметь по меньшей мере девять стадий, а методы восьмого порядка — не менее 11 стадий. Для методов девятого и более высоких порядков (не имеющих, впрочем, большой практической значимости) неизвестно, сколько стадий необходимо для достижения соответствующего порядка точности.

21. Многошаговые схемы. Прогноз и коррекция. Метод Адамса-Башфорта

Для того чтобы начать расчет методом прогноза и коррекции, необходимо знать значения функции в двух первых узлах сетки — x0 и x1 — и . Обычно значение в узле x1 определяется каким-либо одношаговым методом (методом Рунге-Кутты или Гюна). На каждом шаге построения решения методом прогноза и коррекции требуется вычислить всего одно значение функции, а одно берется из предыдущего узла сетки. Поэтому он весьма экономичен по затратам времени вычислений при достаточной точности. Погрешность описываемого метода пропорциональна h3 (d ~ h3). Аналогичные схемы прогноза-коррекции могут быть получены сочетанием явных (прогноз) и неявных (коррекция) формул Адамса для различных k. Так, например, широко применяется четырехшаговый метод прогноза-коррекции, в котором в качестве прогноза используется 4-х шаговая формула Адамса-Башфорта, а для коррекции — 4-х шаговая формула Адамса-Моултона. Погрешность такого метода пропорциональна ~ h5. Ме́тод А́дамса — конечноразностный многошаговый метод численного интегрирования обыкновенных дифференциальных уравнений первого порядка. В отличие от метода Рунге-Кутты использует для вычисления очередного значения искомого решения не одно, а несколько значений, которые уже вычислены в предыдущих точках.

22. Методы решения жестких ОДУ. Методы Гира

Жёсткой системой обыкновенных дифференциальных уравнений (ОДУ) называется (нестрого говоря) такая система ОДУ, численное решение которой явными методами (например, методами Рунге — Кутты или Адамса) является неудовлетворительным из-за резкого увеличения числа вычислений (при малом шаге интегрирования) или из-за резкого возрастания погрешности (так называемого, взрыва погрешности) при недостаточно малом шаге. Для жёстких систем характерно то, что для них неявные методы дают лучший результат, обычно несравненно более хороший, чем явные методы[1]. Метод Гира относится к классу так называемых многозначных методов. Также его часто называют методом Нордсика или метод на основе формул дифференцирования назад (ФДН-метод) в представлении Нордсика [5, 6]. Как и многошаговые, многозначный метод основан на получении нового значения функции с использованием аппроксимирующего полинома. Однако в отличие от них многозначный метод использует разложение решения в ряд Тейлора в некоторой точке интегрирования. Таким образом, коэффициентами полинома становятся приближения к производным от решения в точке tn-1. Теперь цель интегрирования заключается в том, чтобы получить те же коэффициенты ряда Тейлора, но уже в следующей точке tn. Однако итерационные формулы, полученные непосредственно из такого представления полинома, оказались нестабильными. Для решения этой проблемы Нордсик предложил ввести p коэффициентов, что при их правильном подборе позволяет добиться стабильности. Важными особенностями многозначного метода Гира является его возможность на каждом шаге контроля ошибки интегрирования и соответственно изменять порядок метода и шаг интегрирования по времени.

23. Методы решения краевых задач. Метод стрельбы и метод конечных разностей

Краевая задача (граничная задача) — задача о нахождении решения заданного дифференциального уравнения (системы дифференциальных уравнений), удовлетворяющего краевым (граничным) условиям в концах интервала или на границе области. Краевые задачи для гиперболических и параболических уравнений часто называют начально-краевыми или смешанными, потому что в них задаются не только граничные, но и начальные условия. По смыслу значение функции z (0) определяет тангенс угла наклона функции y (x) при x = 0. Если в качестве начального значения функции z (x) задать произвольное значение z (0) =  , и решить задачу (2.7) – (2.9) численно, одним из методов, описанных в главе 1, то в координате x = l будет вычислено некоторое значение y (l) = yn. Очевидно, что при случайном выборе z (0) =  величина y (l) = yn ≠ b, что противоречит начальному условию (2.6) исходной задачи. При изменении параметра  для граничного условия z (0) =  1 решение задачи (2.7) дает отличное от предыдущего значение исходной функции на правой границе, y (l) = yn,1. Исходя из этого, используется следующий алгоритм расчета. Вычисляются значения y (l) при z (0) =  и z (0) =  1. Проводится анализ, как при изменении величины, изменилась величина yn: стала ли она «ближе» к величине b, или «дальше». По результатам анализа определяется новая величина параметра и повторяется расчет. Многократным заданием величины добиваемся совпадения вычисленной величины yn с величиной b с заданной точностью расчета. Такой метод расчета называется методом «стрельбы». Название пошло из баллистики артиллерийский снарядов, когда путем выстрелов с «недолетом» и «перелетом» третьим выстрелом цель (в нашем случае это величина функции y (l) = yn) поражается. Наиболее распространенным и универсальным численным методом решения дифференциальных уравнений является метод конечных разностей. Основное содержание метода заключается в следующем. Область непрерывного изменения аргумента (например, отрезок) заменяется дискретным множеством точек, называемых узлами. Эти узлы составляют разностную сетку. Искомая функция непрерывного аргумента приближенно заменяется функцией дискретного аргумента на заданной сетке. Эта функция называется сеточной. Исходное дифференциальное уравнение заменяется разностным уравнением относительно сеточной функции. При этом для входящих в уравнение производных используются соответствующие конечно-разностные соотношения. Такая замена дифференциального уравнения разностным называется его аппроксимацией на сетке (или разностной аппроксимацией). Решение дифференциального уравнения сводится к отысканию значений сеточной функции в узлах сетки.

24. Численно аналитические методы решения краевых задач. Метод коллокаций

Суть метода коллокаций заключается в следующем. Приближенное решение ищется в конечномерном линейном пространстве функций. Неизвестные коэффициенты его разложения по базису пространства определяются из уравнений коллокаций и краевых условий. Уравнения коллокаций — требования того, чтобы приближенное решение удовлетворяло дифференциальным уравнениям задачи в конечном множестве точек области постановки задачи (точках коллокаций). Краевые условия получаются из соответствующих условий исходной постановки задачи, записанных в нескольких точках на границе области. В методе коллокаций записывается ровно столько уравнений, сколько имеется неизвестных. В методе коллокаций и наименьших квадратов (КНК) число уравнений превосходит число неизвестных, то есть система, из которой ищутся неизвестные коэффициенты, является переопределенной. Для ее решения используется метод наименьших квадратов.

25. Метод конечных разностей для решения дифференциальных уравнений в частных производных. Синтез сетки решения

Метод конечных разностей — численный метод решения дифференциальных уравнений, основанный на замене производных разностными схемами. Является сеточным методом. Для решения эллиптической задачи методом конечных разностей на расчётной области строится сетка, затем выбирается разностная схема и для каждого узла сетки записывается разностное уравнение (аналог исходного уравнения, но с использованием разностной схемы), затем производится учёт краевых условий (для краевых условий второго и третьего рода так же строится некоторая разностная схема). Получается система линейных алгебраических уравнений, решая которую в ответе получают приближенные значения решения в узлах. Главной проблемой метода является построение правильной разностной схемы, которая будет сходиться к решению. Построение схемы выполняется исходя из свойств исходного дифференциального оператора. Решение задач методом конечных разностей, когда процесс изменяется во времени, представляет собой итерационный процесс — на каждой итерации мы находим решение на новом временном слое. Для решения таких задач используются явные, неявные схемы и предиктор-корректор (пара из специально подобранных явной и неявной схемы). Явные схемы и схемы предиктор-корректор просто пересчитывают значение, используя информацию с предыдущих временных слоёв, использование неявной схемы приводит к решению уравнения (или системы уравнений).Для параболических и гиперболических уравнений часто прибегают к смешиванию методов — производные по времени аппроксимируют с помощью разностной схемы, а оператор по пространству аппроксимируется с помощью конечноэлементной постановки[1].

26. Методы анализа сигналов и графических изображений. Морфологические алгоритмы. Клеточные автоматы

Морфологические методы успешно применяются для анализа и содержательной интерпретации изображений реальных сцен, полученных при неконтролируемых условиях регистрации, таких как условия освещения, его спектральный состав, характеристики аппаратуры, регистрирующей изображения, оптические свойства сцены и др. Подобная задача анализа и интерпретации изображений возникает при создании систем машинного зрения, систем обзора земли из космоса, устройств видеоконтроля, в связи с необходимостью автоматического выделения и распознавания объектов на изображениях, полученных при неопределенных условиях освещения, при решении задач ориентации и привязки к местности летательных аппаратов при различных погодных условиях и т. д. Методами морфологического анализа можно успешно решать задачи автоматического узнавания, классификации идентификации объектов по их изображениям, выделения отличий в сценах по их изображениям и др. Кле́точный автома́т — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Включает регулярную решётку ячеек, каждая из которых может находиться в одном из конечного множества состояний, таких как 1 и 0. Решетка может быть любой размерности. Для каждой ячейки определено множество ячеек, называемых окрестностью. К примеру, окрестность может быть определена как все ячейки на расстоянии не более 2 от текущей (окрестность фон Неймана ранга 2). Для работы клеточного автомата требуется задание начального состояния всех ячеек и правил перехода ячеек из одного состояния в другое. На каждой итерации, используя правила перехода и состояния соседних ячеек, определяется новое состояние каждой ячейки. Обычно правила перехода одинаковы для всех ячеек и применяются сразу ко всей решётке. Основное направление исследования клеточных автоматов — алгоритмическая разрешимость тех или иных задач. Также рассматриваются вопросы построения начальных состояний, при которых клеточный автомат будет решать заданную задачу.

Список использованных источников

Бейтмен Г., Эрдейи Э. Высшие трансцендентные функции. Том 2. − М: Наука, 1966. Бесекерский В.А., Дедус Ф.Ф., Ройтберг М.А. Сжатие информации и идентификация на основе ортогональных разложений // Труды Ленинградского ИАП, 1977. Гальченко А.А., Дедус Ф.Ф. Идентификация экспоненциальных сигналов методом взвешенных моментов. Автометрия. № 4, 1983. Дедус Ф.Ф. Автоматизация аналитического представления и обработки результатов экспериментальных исследований. //Материалы I Международной школы по автоматизации научных исследований. − Пущино, 1985, с.96-112. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. − М: Наука, 1968. Корн Г., Корн Т. Справочник по математике, М. Наука, 1984. Никольский С.М. Курс математического анализа. Т.2. − М.: Наука, 1975. Паплаускас А.Б. Тригонометрические ряды от Эйлера до Лебега. − М., 1966. Сеге Г. Ортогональные многочлены. Физматгиз,1962. Чебышев П.Л. Вопросы о наименьших величинах, связанные с приближенным представлением функций. Полн. собр. соч.. Т. 2.− М.-Л., 1947, с. 151-235.