ФедотовА.А. Численные методы интегрирования .. 2015 (А.А. Федотов, П.В. Храпов - Численные методы интегрирования, решения дифференциальных уравнений и задач оптимизации), страница 9

Если N = 1, то получится частный случай метода сопряженных градиентов — метод наискорейшего спуска.Опишем алгоритм метода сопряженных градиентов.Шаг 0. Задать параметр точности   0, выбрать x 0  R n , найтиgrad F ( x 0 ).Шаг 1. Положить k  0, p0  grad F ( x 0 ).Шаг 2. Решить задачу одномерной минимизацииF ( x k   p k )  min,   0, т. е. найти    k .Шаг 3. Положить x k 1  x k  k p k и вычислить grad F ( x k 1 ).Проверить условие достижения точности grad F ( x k 1 )  .

Еслионо выполняется, то положить x 0  x k 1 , grad F ( x 0 )  grad F ( x k 1 )и закончить поиск, иначе — перейти к шагу 4.Шаг 4. Проверить условие k + 1 = n. Если оно выполняется, тоположить x 0  x k 1 , grad F ( x 0 )  grad F ( x k 1 ) и перейти к шагу 1(рестарт), иначе — перейти к шагу 5.Шаг 5. Вычислить коэффициент k grad F ( x k 1 )grad F ( x k )22и найтиновое направление поиска p k 1  grad F ( x k 1 )  k p k . Положитьk = k + 1 и перейти к шагу 2.Примечание. Вблизи точки минимума дважды дифференцируемаяфункция с положительно определенной матрицей Гессе F ( x  ), как прави70ло, достаточно хорошо аппроксимируется квадратичной функцией.

Поэтомуможно надеяться на хороший результат применения этого метода для такихфункций.Пример. Методом сопряженных градиентов найти точку минимума функции F ( x )  4 x12  3x22  4 x1 x2  x1 из начальной точкиx 0  (0, 0).Итерация 1.Шаг 0. Положим   0,01; x 0  (0, 0), найдем grad F ( x 0 )  (1, 0).Шаг 1. Положим k  0, p0  grad F ( x 0 )  (1,0).Шаг 2. Решим задачу одномерной минимизации F ( x 0   p 0 )  min.

Получим 0  1 / 8 (для нахождения 0 можно было воспользоваться формулой  k   ( Ax k  b, p k ) ( Ap k , p k ).Шаг 3. Найдем x1  x 0   0 p0  (1 / 8,0) и grad F ( x1 )  (0,1 / 2). Точность не достигнута, перейдем к шагу 4.Шаг 4. Проверим условие k + 1 = n, если оно не выполняется,перейдем к шагу 5.Шаг 5. Найдем коэффициент  0  1 / 4 и новое направлениеспуска p1  grad F ( x1 )  0 p0  (1 / 4, 1 / 2).Итерация 2.Шаг 2. Решим задачу одномерной минимизации F ( x1   p1 )  min. Получим 1  1 / 4.Шаг 3. Найдем x 2  x1  1 p1  (3 / 16, 1 / 8) и grad F ( x 2 )  (0,0) — задача решена точно.5.2.4.

Метод проекции градиентаПусть требуется найти min F ( x1 , x2 , ..., xn ) при условиях1 ( x1 , x2 , ..., xn )  0; 2 ( x1 , x2 , ..., xn )  0;................................ m ( x1 , x2 , ..., xn )  0,или  ( x )  0.Условный минимум целевой функции находится на поверхности ограничений ( x )  0, поэтому алгоритм метода проекции градиента состоит из двух основных этапов.71Этап 1. Возврат на поверхность ограничений из текущей точки поиска x k , если эта точка вышла за допустимые пределынарушения ограничений  (рис. 5.8):  ( x k )  .Рис. 5.8.

Метод проекции градиентаТакое движение происходит из точки x k по нормали к поверхности ограничений (см. рис. 5.8) из точки x 0 в точку x1. Приращениезависит от величины отклонения и определяется по формуле x k 1  Tk (  k Tk ) 1  ( x k ),где  k — матрица размеров (m  n), строками которой являютсяградиенты функций-ограничений  j ( x ), вычисленные в точке x k : 1 ...

1  x1xn  k   .....................  ,  m  m ...xn  x1где ( x k ) — вектор-функция ограничений в точке x k .Таким образом, на этапе 1x k 1  x k   x k 1.72После попадания в малую окрестность поверхности ограничений выполняется второй этап алгоритма.Этап 2.

Перемещение в сторону условного экстремума вдольлинеаризованной поверхности ограничений, т. е. вдоль многомерной плоскости, касательной к поверхности ограничений в точкеx k . Направление поиска минимума определяется по направлениюпроекции антиградиента целевой функции на эту плоскость:s k  H k grad F ( x k ).Здесь H k  I   Tk (  k Tk ) 1  k — проектирующая матрица, где I —единичная матрица порядка n.

Тогдаx k 1  x k  hk s k  x k  hk H k grad F ( x k ),где hk — величина шага.Если поверхность ограничений не линейна, то перемещениевдоль гиперповерхности может привести к нарушению условий ( x k )  . Тогда повторяется этап 1 и т. д.5.3. Задание к лабораторной работеНайти минимум функции методом наискорейшего спуска(табл. 5.1).Таблица 5.1Варианты функций к лабораторной работе «Методы оптимизации»№вариантаf ( x, y )1x  y 3  3 xy22 x 3  3 y 3  4 xy3x 2  xy  y 2  3 x  6 y42 x 2  3 xy  4 y 2  2 x  3 y54 x 2  3 xy  2 y 2  3 x  2 y6xy 2 (1  x  y ), ( x  0, y  0)7x 2 y (1  x  y ), ( x  0, y  0)8xy 320 50 , ( x  0, y  0)xy73Окончание табл.

5.1№вариантаf ( x, y )93x 2  x 3  3 y 2  4 y103x 2  y 3  3 y 2  4 x1250 20 , ( x  0, y  0)xy22x  y  2 ln x  18 ln y , ( x  0, y  0)13x 3  3 xy 2  15 x  12 y112  y2 )14(2 x 2  y 2 )e  ( x15(5 x 2  2 y 2 )e  ( x2  y2 )164 x 2  xy  y 2  4 x  6 y173 x 2 y  y 3  12 x  15 y19100 40xyx2  x2 y  2 y3  5 y2202 x 3  xy 2  5 x 2  y 221x 2  xy  4 x 2  4 x  6 y182xy 2340 100xyx2  y2  z2  4 x  6 y  2z24x2  y2  z2  2 x  6 y  4z25x2  y2  z2  2x  8 y  4z26x2  y2  z2  2 x  6 y  4z22 74xy 2xy 2  y2 )27( x 2  2 y 2 )e  ( x28(2 x 2  5 y 2 )e  ( x2  y2 )292 x 2  3 xy  4 y 2  2 x  3 y304 x 2  3 xy  2 y 2  3 x  2 yЛитератураАмосов А.А., Дубинский Ю.А., Копченова Н.В.

Вычислительные методы. М.: Изд-во МЭИ, 2008. 672 с.Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы.М.: Лаборатория базовых знаний, 2002. 632 с.Бахвалов Н.С., Лапин А.В., Чижонков Е.В. Численные методы в задачах и упражнениях. М.: Высшая школа, 2000. 190 с.Вержбицкий В.М. Основы численных методов. М.: Высшая школа,2005.

840 с.Костомаров Д.П., Фаворский А.П. Вводные лекции по численнымметодам. М.: Университетская книга; Логос, 2006. 184 с.Лесин В.В., Лисовец Ю.П. Основы методов оптимизации.М.: МАИ, 1995.Самарский А.А. Введение в численные методы. СПб.: Лань, 2005.288 с.Самарский А.А., Вабищевич П.Н., Самарская Е.А. Задачи и упражнения по численным методам. М.: Эдиториал УРСС, 2003. 208 с.  75ОглавлениеПредисловие .....................................................................................31. ЧИСЛЕННЫЕ МЕТОДЫ ВЫЧИСЛЕНИЯ ОПРЕДЕЛЕННОГО ИНТЕГРАЛА ................................................................... 41.1. Квадратурные формулы .......................................................

41.1.1. Формула средних прямоугольников ............................. 51.1.2. Формула трапеций ........................................................... 71.1.3. Формула Симпсона .......................................................... 81.1.4. Составные квадратурные формулы ............................... 91.1.5. Квадратурные формулы Гаусса .................................... 111.2. Правило Рунге практической оценки погрешности .......... 151.3. Задание к лабораторной работе ...........................................

182. ПРИБЛИЖЕННОЕ ВЫЧИСЛЕНИЕ ДВОЙНОГО ИНТЕГРАЛА .............................................................................................2.1. Численные методы вычисления двойного интеграла .......2.1.1. Метод ячеек ......................................................................2.1.2. Последовательное интегрирование с использованием формулы трапеций .................................................2.1.3.

Последовательное интегрирование с использованием квадратурных формул Гаусса ...............................2.2. Задание к лабораторной работе ...........................................3. ЗАДАЧА КОШИ ДЛЯ ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ ......................................................3.1. Численные методы решения задачи Коши.........................3.1.1.

Явный метод Эйлера........................................................3.1.2. Методы Рунге — Кутты ..................................................3.1.3. Многошаговые методы Адамса ....................................3.1.4. Правило Рунге практической оценки погрешности ....3.2. Интегрирование систем обыкновенных дифференциальных уравнений первого порядка ...............................3.3. Задание к лабораторной работе ...........................................7621212127293134343540414345474. КРАЕВАЯ ЗАДАЧА ДЛЯ ЛИНЕЙНОГО ОБЫКНОВЕННОГО ДИФФЕРЕНЦИАЛЬНОГО УРАВНЕНИЯВТОРОГО ПОРЯДКА ..................................................................4.1.