Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 54
Текст из файла (страница 54)
1 итерация. Вычислим о1 ГО 286928~ о1 — Г 10 5065 10 8060 ~3.17058 ~ ' (-10.8060 20 Таким образом, при н = 0 система (10.30) принимает следующий вид: 10 5065р< о1 10 8060 р< о1 — 0 286928 — 10.8060р[о1 + 20рг[о' = — 3.17058. Решая ее, получаем р[о1 = О.428445, р'о' = О.390018. Далее в соответствии с формулой (10.31) полагаем х'11 = х[о' + р<о' = 0.571555, х<11 = х'о1 + + р'о' = 0.609982. Так как ~ х' " — х<о' ~ ~ 0.6 > е, то вычисления следует продолжить далее. Результаты следующих итераций приведены в табл. 10.1. Т а б л и ц а 10.1 .[а) ~х[н< х[о-1) ~ г х[ п[ 1 282 1.00000000 0.57155400 0.15541900 0.00824200 0.00000082 0.00000000 1.00000000 0.60997200 0.19094400 0.00939200 0.00000101 0.00000922 6 101 6 101 2 101 1 ° 10 г 2.10 в При и = 5 критерий окончания выполняется и вычисления следует прекра- тить.
Итак, к)(( (0.00000, 0.00000)т. 2. Понятие о квазинъютоновских методах. Высокая скорость сходимости метода Ньютона связана с тем, что в нем используется матрица Гессе, содержащая информацию о кривизнах функции ~ В результате минимизируемую функцию удается достаточно точно аппроксимировать последовательностью квадратичных функций Ги. В методах, которые называют квазиньютоновски.ии1, также фактически используется квадратичная аппроксимация функции ~ но в отличие от метода Ньютона в них не применяется вычисление вторых производных.
Информация о кривизнах функции )". здесь накапливается постепенно и является результатом наблюдений за изменением градиента ~( и) Направление спуска в квазиньютоновских методах определяется как решение системы уравнений и( и) р( и) — гг( и) в которой В(и) — текущее приближение к матрице Гессе. Начальное приближение В(о' обычно полагают равным единичной матрице.
В таком случае у(о) = -у(о) и первая итерация совпадает с одним шагом градиентного метода. После того, как найдено приближение к(и"), вычисляют матрицу В' и" = В'и) + ЬВ(и), где ЬВ(и) — некоторая поправочная матрица. Во всех правилах пересчета неизменным является выполнение кваэиньютоновского условия В( и+1) (К( и+1) К( и) ) — ~( и+1) ~( и) Известно, что при определенных условиях квази ньютоновские методы сходятся сверхлинейно. Для квадратичных же функций они дают точное значение точки минимума после конечного числа итераций, которое не превышает2 т. Первый из квазиньютоновских методов был предложен в 1959 г.
Дзвидоном. С тех пор эти методы непрерывно совершенствовались и к настоящему времени стали одними из наиболее популярных и широко 1 Первоначально эти методы называли методами переменной метрики. ~ Естественно, что это верно только при отсутствии вычислительной погрешности. применяемых на практике. Весьма интересное и содержательное обсуж- дение квазнньютоновских методов содержится в книгах [24], [32], [91]. 3 а м е ч а н и е. В некоторых вариантах квазиньютоновских методов направление спуска вычисляется по формуле р = — Н< у <ю то) «<) где В< "< — матрица, аппроксимирующая матрицу, обратную матрице Гессе.
3. Метод Ньютона и квазиньютоновские методы при наличии помех. Вычислительные ошибки (помехи) оказывают существенное влияние на поведение метода Ньютона. Природа этих ошибок может быть различной (вычисление у< ">, решение системы уравнений С< "' р < "' = = -у< "> и др.).
В результате вместо ньютоновского направления р< "> получается направление р<,"". Пусть ~р<"' — р<,"' ~ < а. Как известно, метод Ньютона сходится, вообще говоря, лишь в некоторой окрестности Г точки минимума. В случае, когда радиус этой окрестности меньше е, очередное приближение х<""' = х<"' + а„р<,"< скорее всего окажется вне окрестности У и метод не будет сходиться. Таким образом, метод Ньютона сохраняет свои преимущества лишь при высокой точности вычислений, Квазиньютоновские методы оказываются весьма чувствительны к ошибкам в вычислении градиента. Причина здесь состоит в том, что в основе этих методов лежит идея восстановления матрицы Гессе по результатам вычисления градиента ~ (х) в точках х< "<.
Как и в методе Ньютона, здесь необходимо очень аккуратное вычисление градиента. $10.5. Метод сопряженных градиентов ' Метод Ньютона и квазиньютоновские методы, обсуждавшиеся в предыдущем параграфе, весьма эффективны как средство решения задач безусловной минимизации. Однако они предъявляЮт довольно высокие требования к объему используемой памяти ЭВМ. Это связано с тем, что выбор направления поиска р''"' требует решения систем линейных уравнений, а также с возникающей необходимостью хранения матриц типа В<"', Н< ">. Поэтому при больших т использование этих методов может оказаться невозможным.
В существенной степени от этого недостатка избавлены методы сопряженных направлений. 1. Понятие о методах сопряженных направлений Рассмотрим задачу минимизации квадратичной функции Г(х) = — (Ах, х) -(Ь, х) 2 (10.33) 284 х<п+)) — х<п) + апр<п) (п= 0 1 2 " т 1) в котором направления р<®, р<'), ..., р<'"') взаимно сопряжены, а шаги (у(п) р<п) ) (Ар< п) р(п) ) получаются как решение задач одномерной минимизации; (ои((гп) = ш(п уп((г), уп(е) = Г(х'п' + (гр<п)) а10 Т е о р е и а 10.4 Метод сопряженных направлений позволяет найти пгочку лгинилгу ив квадратичной функции (10.33) не более челг за т игагов. Методы сопряженных направлений отличаются один от другого способом построения сопряженных направлений. Наиболее известным среди них является иетод сопряженных градиентов.
2. Метод сопряженных градиентов. В этом методе направления р< п) строят по правилу р(о) у(о) р(и) — у(п) + Д <р(и-)) п) 1 (10.34) где (Ар(п-)) в(п)) Вп-) = (А < п-) ) р< п- ) ) (10.35) Так как р<о) = -у'о), то первый шаг этого метода совпадает с шагом метода наискорейшего спуска. Можно показать (мы этого делать не будем), что направления (10.34) действительно являются сопряжен- 285 с симметричной положительно определенной матрицей А.
Напомним, что для ее решения требуется один шаг метода Ньютона и не более чем т шагов квазиньютоновского метода. Методы сопряженных направлений также позволяют найти точку минимума функции (10.33) не более чем за т шагов, Добиться этого удается благодаря специальному выбору направлений поиска. Будем говорить, что ненулевые векторы р' о), р' ", ..., р' " ) ) являк)тся вэаи.ино сопряженнылги (относительно матрицы А) „если (Ар< п), р< () ) = 0 для всех и 1 г. Под лгетодолг сопряженных направлений для минимизации квадра— тичной функции (10.33) будем понимать метод ными относительно матрицы А. Более того, градиенты у' "> (и = О, 1, ..., т — 1) оказываются взаимно ортогональными.
Пример 10.5. Применим метод сопряженных градиентов для минимизации квадратичной функции /(х>, х2) = х1 + 2х~ — 4х> — 4хт из примера 10.1. 1 Запишем /в виде — (Ая х) — (Ь, ф, где Возьмем начальное приближение х< о) = (О, О)т. 1-й ш а г метода совпадает с первым шагом метода наискорейшего спуска. Позтому (см. пример 10.1) у'о) = (-4, -4)т, р'о) = -у(о> х<>) = (4/3, 4/З)т.
2-й ш а г. Вычислим у'>' = Ах<>) — Ь = (-4/3, 4/3)т, (Ау<о> у<») 8 (-4/3) + 16 (4/3) 1 (Ау(о) у(о) ) 8.4 + 16.4 9 у'>) = -у(>) + Фоу(о) — (4/3 1/3)т + (1/9)(4 4)т = (16/9 -8/9)т (у<>>, у'>') (-4/3) (16/9)+(4/3) (-8/9) 3 й> (Ау< >), у' >' ) (32/9) (16/9)+(-32/9) (-8/9) 8 ' х(г) = х<>) + (т>у(>) — (4/3 4/3)т + (3/8)(16/9 8/9)т — (2 1) Так как у<2> = Ах<~) — Ь = О, то х = х<2' = (2, 1)т и решение оказалось найденным за два шага. (у< и> у< >)) у( и-) > ) Ф ->— (10.36) или к виду ]у(и) ~ 2 <'-~ = >-ПГТГ>г (10.37) Преимущество формул (10.36), (10.37) в том, что они не содержат явным образом матрицу А.
286 3. Метод сопряж~>ных градиентов для минимизации неквадратичных функций. Для того чтобы указанный метод можно было применить для минимизации произвольной гладкой функции / формулу (10.35) для вычисления коэффициента Д, 1 преобразуют к виду Минимизацию функции ~ методом сопряженных градиентов производят в соответствии с формулами я~"'~~ = з'"> + а„р~"', и>0, у„(а„) = ппп ср~(а), уа(а) = ~(а1 "> + ар< ">). а>0 (10.38) (10.39) (10.40) Коэффициенты,0„~ вычисляют по одной из формул (10.36), (10.37).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
