ФедотовА.А. Численные методы интегрирования .. 2015 (864364), страница 9
Текст из файла (страница 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 x1xn 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 40xyx2 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 100xyx2 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
