Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 53
Текст из файла (страница 53)
ТеоРема 10.1, замечание 1, а также РезУльтат пРимеРа 10.2 указывают на то, что скорость сходимости резко падает при увеличении величины Ос. Действительно, известно, что градиентный метод сходится очень медленно, если поверхности уровня минимизируемой функции сильно вытянуты в некоторых направлениях. В двумерном случае рельеф соответствующей поверхности и = /(х~, хт) напоминает рельеф местности с оврагом (рис.
10.7). Поэтому такие функции принято называть овражнили. Вдоль направлений, характеризующих "дно оврага", овражная функция меняется незначительно, а в других направлениях, характеризующих "склон оврага", происходит резкое изменение функции. 276 Рис. 10. 7 Если начальная точка я<о' попадает на "склон оврага", то направление градиентного спуска оказывается почти перпендикулярным "дну оврага" и очередное приближение х< <> попадает на противоположный "склон оврага". Следующий шаг в направлении ко "дну оврага" возвращает приближение я<2> на первоначальный "склон оврага". В результате вместо того чтобы двигаться вдоль "дна оврага" в направлении к точке минимума, траектория спуска совершает зигзагообразные скачки поперек "оврага", почти не приближаясь к цели (рис. 10.7).
Для ускорения сходимости градиентного метода при минимизации овражных функций разработан ряд специальных "овражных" методов. Дадим представление об одном из простейших приемов. Из двух близких начальных точек Фс' и я<'< совершают градиентный спуск на "дно оврага".
Через найденные точки я<о' и я«< проводят прямую, вдоль которой совершают большой "овражный" швг (рис. 10.8). Из найденной таким образом точки х< ~> снова делают один шаг градиентного спуска в точку з<~>. Затем совершают второй "овражный" шаг вдоль прямой, проходящей через точки я< <' и в<2>, и т. д. В результате движение вдоль "дна оврага" к точке минимума существенно ускоряется.
Рис. 10.8 Более подробную информацию о проблеме "оврагов" и "овражных" методах можно найти„например, в ~9], [18~. 277 3. Другие подходы к определению шага спуска. Как нетрудно понять, на каждой итерации было бы желательно выбирать направление спуска у'">, близкое к тому направлению, перемещение вдоль которого приводит из точки я'"' в точку я. К сожалению, антиградиент у'"' = — у'"' является, как правило, неудачным направлением спуска. Особенно ярко это проявляется для овражных функций.
Поэтому возникает сомнение в целесообразности тщательного поиска решения задачи одномерной минимизации (10.23) и появляется желание сделать в направлении р~ "~ лишь такой шаг, который бы обеспечил "существенное убывание" функции у. Более того, на практике иногда довольствуются определением значения а„> О, которое просто обеспечивает уменьшение значения целевой функции. В одном из простейших алгоритмов (типа дробления шага) такого выбора шага а„фиксируют начальное значение а > 0 и значение параметра у, 0 < у < 1. За а„принимают а„= а у'", где ~'„— первый из номеров ~ = О, 1, 2, ..., для которого выполнено условие убывания (10.28) Х(я( и) — а7йу( й) ) — У(хч и) ) < О.
Однако при таком выборе а„нет гарантии, что последовательность я~ "~ будет сходиться к точке минимума даже для простой квадратичной функции (10.24). Условие (10.28) является слишком слабым: последовательность я< ">, незначительно уменьшая значения функции у, может "останавливаться", не доходя до точки а Такое поведение последовательности я("~ можно предотвратить, если заменить условие (10.28) условием "существенного убывания" функции ~ на каждой итерации: ~(я(пъ ауау(™)) Дя(™ъ) ~ (фаув~у(м )2 (10.29) Пример 10.3. Продемонстрируем применение градиентного метода с дроблением шага к задаче минимизации квадратичной функции У(Ч вг) = я~ + + 2х~т — 4х~ — 4тт из примера 10.1. Для выбора значения шага будем использовать условие (10.29). Воспользуемся следующими краткими обозначениями: а; = ау', в~" "= я~ "> — а;у~ ">. Заметим, что у~ "~=' (2г'"~ — 4, 4г'"' — 4)т.
Здесь р (О <,О < 1) — дополнительный параметр. Заметим, что для рассматриваемого метода у~ "> = -у~ "~ = -у'(я~ ">) и поэтому неравенство (10.29) в точности совпадает с неравенством (10.15), используемым в методах спуска при дроблении шага. Выберем начальное приближение в~о> = (О, 0)т, начальное значение шага ао = 1, значения параметров у = 1/2,,У = 3/4. Вычислим значения у( ~о)) = 0 у(о) = (-4 -4)т. Х и т е р а ц и я. Вычисляем Ы о*о) = а~о) — аоу~о) = (4 4)т /(я~о о) ) = = 16. Так как значение функции не уменьшилось, то следует уменьшить шаг: а~ = оо/2 = 0.5 Вычисляем а~о ~> = в~о~ — а~у~® = (2, 2)т /(з'о~>) = — 4. Поскольку /(з~ о ~ ' ) — / (з~ о ~ ) = -4 ) -фа~ ~ у~ ® ~ 2 = -12, условие (10.29) не выполняется и следует снова уменьшить шаг: а2 = о~/2 = 0.25.
Вычисляем а(о,П вЂ” з(О) о2~(о> — (1 1)т У(з(о,2) ) — 5 Имеем /(з'~2') — /(з"®) = — 5 > -фа2~у'о~ ~т = -6, т. е. условие (10;29) не выпслняетси. Уменьшаем шаг: аз = а2/2 = 0.125. Вычисляем а(о 3) — а40) азу(о) = (0.5, 0.5)т /(~40,3)) = -3.25. Так как /(з~о з>) — /(а~о~) = -325 ( -1Уаз~у'о> ]з = — 3, то условие (10.29) выполнено. Положим в~~1 = (0.5, 0.5)т; напомним, что /(з~м) = -3.25. Вычислим у~ ~> = ( — 3, -2)т и положим ао = 1. Далее вычисления следует продолжить до выполнения какого-либо принятого критерия окончания итераций.
4. Влияние погрешности вычислений. Один из существенных недостатков градиентного метода связан с его чувствительностью к погрешностям вычислений. Особенно сильно этот недостаток сказывается в малой окрестности' точки минимума, где антиградиент, задающий направление поиска, мал по модулю. Поэтому эффективность градиентного метода на завершающей стадии поиска существенно ниже, чем на начальной стадии, $10.4.
Меюд Ньютона 1. Простейший вариант метода Ньютона и жиод Ньиттона с дроблением шага. Пусть в некоторой окрестности точки минимума х функция / является сильно выпуклой и дважды непрерывно дифференцируемой. Далее, пусть в'"' — хорошее приближение к ж Тогда в малой окрестности точки х~ "~ функция /достаточно точно аппроксимируется квадратичной функцией Г„(в) = /(а< "') + (у' "', а — а< "1 ) + 1 + — (С< "' (в — и' "'), и — х< "'), являющейся суммой первых трех членов ее разложения по формуле Тейлора (ср.
с формулой (10.9)). Здесь у< "~ = /'(Ы ">), С'"> = /"(а< ">). Можно ожидать, что точка к("), в которой достигается минимум функции Р„, будет значительно лучшим приближением к к, чем к(т. учитывая, что Р'„(к) = у'") + О")(к — к(п)), замечаем, что точка я(") может быть определена из необходимого условия экстремума: у( и) + Ц[ и) (к( и) к( и) ) — 0 Таким образом, чтобы попасть из точки к(") в точку к(п), нужно переместиться вдоль вектора р' "),= к("' — *("', который определяет- ся из системы линейных алгебраических уравнений (10.30) Д(п) р( и) — у(п) Вектор р(") принято называть ньютоновским направление.и, а метод спуска К(а+1) — К(п) + () р( и) (10.31) с таким выбором р("' — методом Ньютона.
Отметим, что ньютоновское направление является направлением спуска. В самом деле, в силу равенства (10.30) для р("' верна формула р(") = — [С(п)])у'"'. Матрица [б(п)~ ' положительно определена (это следует из положительной определенности матрицы 6(") ). Поэтому Д'(К(п) ) р(п) ) — ([Д(п))-1у(п) у(П)) ~ 0 мума к функиия ~ является сильно выпуклой и трижды непрерывно дифференцируемой. То(да найдется такая малая 6-окрестность точки к, что при произвольном выборе начально(о приблихения к(о) из этой окрестности последовательность к(п), вычисляемая с помощью мето- 280 Таким образом, условие (10.14) выполняется и р'") действительно задает направление спуска.
Разлйчные варианты метода (10.31), (10.30) связаны с различными способами выбора шагов ап. Заметим, что при выборе ап = 1 рассматриваемый метод в точности совпадает с методом Ньютона решения систем нелинейных уравнений, примененным к решению системы T(к) = О. Отсюда — и название метода, Простым следствием теоремы 7.3 о сходимости метода Ньютона решения систем нелинейных уравнений является следующая теорема. Т е о р е м а 10.2. Лусть в некоторой окрестности 1(' точки мини- да (10.30), (10.31) при а„= 1, не выходит эа пределы б-окрестности точки х и сходится к ней квадратично.
3 а м е ч а н и е. Квадратичная скорость сходимости .метода позво- ляет использовать простой практический критерий окончания: ~ х( п+1) х( и) ~ < е (10.32) Теорема 10.2 указывает на то, что метод Ньютона сходится очень быстро, и практика вычислений это подтверждает. Однако существенным недостатком рассмотренного варианта метода является необходимость выбора достаточно хорошего начального приближения, которое на начальной стадии поиска точки минимума, как правило, отсутствует. Поэтому метод Ньютона с выбором а„= 1 чаще применяют на завершающем этапе поиска х, когда с помощью других методов уже найдено достаточно точное приближение к точке минимума.
Указанного недостатка в значительной степени лишен вариант метода Ньютона, в котором в качестве шага спуска выбирается ап = а„= ~'и сходится к х с квадратичной скоростью. Более тоьо, найдется номер по такой, что для всех и 1 по выполняется равенство ап = 1. 3 а м е ч а н и е. Используют и другие способы выбора а„. Например, иногда а„выбирают из условия ~рп(ап) = ш1п у„(а), где О~ ач1 ,о (а) — ~(х(п) + ар< т ) Квадратичная скорость сходимости метода Ньютона, а также возможность использования матрицы Гессе для контроля за соблюдением достаточных условий экстремума делают этот метод чрезвычайно привлекательным при решении задачи безусловной минимизации.
281 = 7'", где ~п — первый среди номеров ~ Э О, для которых выполняется неравенство ~(х< "> + улр' "') — ~(х' "> ) ~,о7(у~ п~ р< "'). Здесь 0 < 7 < 1, О < 4 < 1/2 — параметры метода. Метод Ньютона с таким выбором а„для широкого класса функций сходится при любом выборе начального приближения х<о' Е П и этим выгодно отличается от метода с выбором а„= 1. Т е о р е м а 10.3. Пусть трижды непрерывно дифференцируемая в Ян функция ~ и иеет точку .иинимума х и ее иатрица Гессе Г(х)положительно определена. Тоьда при любом начально и приближении х~® последовательность Ып', вычисляе иая методом Ньютона с выбором Пример 104. Применим метод Ньютона (10.30), (10.31) с [г„= 1 для поиска точки минимума функции у(х[, хг) = х1 + 10(хг — вш х1)2 с точностью в = 10 5.
Будем использовать критерий окончания итераций (10.32) и вести вычисления на 6-разрядной десятичной ЗВМ. Отметим, что минимальное н равное нулю значение функция у достигает в точке х = (О, 0)т. Имеем У["' = Г( ',"', = (2х[ "' + 20(в1п х< н1 — х[ п1 ) . сов х( н< 20(х< ~1 — вгп х[ ™ ))т д н[ — у"( < и) )— 2+ 20(сов 2х[ "1 + х<"' вшх< "1) 1 2 1 -20сов х[ "1 1 — 20сов х< "1 1 20 Возьмем за начальное приближение в<11 = (1, 1)т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
