Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 79
Текст из файла (страница 79)
..., Го „). Сравнение формул (8) и (9) показывает, что метод (8) решения задачи (1) в случае ХХ=Е~ представляет собой известный метод Ньютона для решения уравнения Х' (и) = О, определяющего стационарные точки функции Х(и). Отсюда происходит название метода (2) — (4) и в общем случае. 2) В качестве ад в (4) можно принять сад=Лад,где (о — минимальный среди 1> 0 номер, для которых выполняется неравенство (19) Х(и,) — Х(и, + Л'(й„ вЂ” и„))~ ЕЛ'Уд(й,)1, (10) где Л, е — параметры метода, 0 < Л; з < 1. 3) Возможен выбор сод в (4) из условий [19] 0(ад~~1, 1д(ад) = ш(п Хд(а), Хд(а) =У(ид+ а(ид — ид)). озала (11) Заметим, что метод (2) — (4) с выбором длины шага сод по правилам (10), (11) аналогичен соответствующим вариантам метода условного градиента.
Для определения й„использовалась линейная часть приращения, а в методе Ньютона — квадратичная часть (2). Если Х,(и) из (2) сильно выпукла, а ХХ = Е" или ХХ задается линейными ограничениями типа равенств или неравенств, то для определения й, из (3) могут быть использованы методы из 3 7, 8. Следует заметить, что задача (3) в общем случае может оказаться весьма сложной и сравнимой по объему требуемой для своего решения вычислительной работы с исходной задачей (1).
Метод Ньютона для решения задачи (1) обычно применяют в тех случаях, когда вычисление производных Х'(и), У" (и) не представляет особых трудностей и вспомогательная задача (3) решается достаточно просто. Достоинством метода Ньютона является высокая скорость сходимости. Поэтому хотя трудоемкость каждой итерации этого метода, вообще говоря, выше, чем в методах первого порядка, но общий объем вычислительной работы, необходимой для решения задачи (1)' с требуемой точностью, при применении метода Ньютона может оказаться меньше, чем при применении других более простых методов.
2. Сначала исследуем сходимость метода Ньютона '(2) — (4) с выбором шага сод из условия (5) при условии ХХ=Е" или, проще говоря, метода (8). Теорема 1. Пусть функа1ия Х(и) сильно выпукла на Е, У(и) он С'(Е") и, кроме тово, ПХ" (и) — Х" (н)1 < Ыи — и1, и, с оиЕ, Х,=сопза> О. (12) Пусть начальное приближение и, выбрано таким, что Х |Х'(ио)! ~ <2)д~д, (13) 333 методы минимизАции ФункциЙ мнОГих пеРеменных ~гл, ь где [1) 0 — постоянная иг теоремы 4.3.4, а у — некоторая константа, 0(у<1. Тогда последователысость (и1), определяемая условиями (8), еу1цествует, сходится к точке и минимума Х(и) на Е", причем справедлива оценка ]и„— и ](2[1Л 1дгь, й= О, 1, ... (14) Доказательство.
Существование и единственность точки и„установлена в теореме 4.3.1. Согласно теореме 4.3.4 <Х" (и)е е>) [1]$]1, иеЕ", $жЕ". (15) Отсюда следует, что система уравнений Х" (и)3= 0 имеет единственное решение 5 =0 и, следовательно, матрица Х" (и) невы- рожденная при всех и ж Е". Это значит, что система (7) при каждом й = О, 1, ...
имеет, и притом единственное, решение, т. е. последовательность (и„) однозначно определяется условиями (8). Кроме того, полагая в (15) $ =(Х" (и))-'г, получим [1](Х" (и)) 'г[1 ( <г, (Х (и)) 'г) ( [г[[(Х" (и)) 'г! или ](Х" (и))-'г! < ]г][А ' при всех г ж Е'. Это значит, что [[(Х" (и)) '[! (~ [1 ', и1БЕ". (16) Введем числовую последовательность а, = [Х'(и„)! и покажем, что ад(2[11Ь 1дг", й = О, 1, ...
(17) При й=О неравенство (17) следует из условия (13). Пусть (17) справедливо при некотором й>0. Из условия (8) и формулы (2.3.5) имеем 1 Х'(идт,) = Х'(иь) + ~ Х" (ид+ 1(идт, — ид)) (и1+,— ид) д1= в 1 = ) [Х" (ид) — Х" (ид + ! (ад+1 — иь))] дг (Х" (иь))-1Х' (ид). о Отсюда и нз (8), (12), (16) с помощью предположения индукции получим вы, ( (Х !2) ! иат1 — иь ! [1 — 'а1( (ЬЯ2[11)) а,', ( < (Ж/(2[1')) (2[1'/Х)' (Ф")' = (2[11/Ь) у"+1 Неравенства (17) доказаны.
Тогда из теоремы 4.3.3 с учетом равенства Х'(и„) = 0 имеем р]иь — и ]1~(<Х'(иь) — Х'(и„), ид— — и.„)(]Х'(ид)]]ид — и ! или ]иь — и ](аьр 1. Отсюда и из неравенства (17) следует оценка (14). Теорема 1 доказана. Как видно из оценки (14) и как показывает практика, метод Ньютона (8) сходится очень быстро. Однако у него есть ззз 9 з) МЕТОД НЬЮТОНА один существенный недостаток: для его сходимости начальная точка и, должна выбираться достаточно близкой к искомой точке ие. Это требование в теореме 1 выражено условием (13), означающим, что (по — ие) ..ае)с-с((2)с(Ь)д. Приведем пример, показывающий, что при отсутствии хорошего начального приближения метод (8) может расходиться.
Пример 1. Пусть — — и + — ~1+ — )и )и)(6 1 в 1! Зтз 4бз 2~ б) и 3 — +2( ! — — 6, У(и) = (и))6, лаась р ) Π— постоянная ив теоремы 4.3,4. Доказательство. В силу теоремы 4.3.1 функция 1(и) огрзкичеиа снизу и достигает своей вижяей грани кз У в единственной точке и . Из теоремы 4.3.4 следует (У"(и)$, згЪ р)4)г, ига П, 3 вибо, (21) где би — подпростравство, параллельное зффиккой оболочке множества ьс. Так как Уз (и) = У" (из), то из предыдущего керавеиства и теоремы 4.3.4 вытекает сильная выпуклость функции гь(и) ка множестве У при всех й = О, 1, ...
Снова обращаясь к теореме 4.3.1, заключаем, что условия (6) где ижЕс, а 6 — сколь угодно малое фиксированное положительное число, 0< 6(1. Нетрудно видеть, что в'(и)жС'(Е') и, кроме того, Хд (и)~ 1 при всех ижЕс, так что в'(и) сильно вы- пукланаЕ'. Далее, ясно,что Уз = О, ие = О. В качестве начального приближения возьмем ив=6. Из (8) получим последовательность пь = ( — 1)' 2 (й = 1, 2, ...), которая расходится, хотя начальное приближение и, отличается от ие = О на малое число 6. Метод (8) часто применяют на завершающем этапе поиска минимума, когда с помощью более грубых, менее трудоемких методов уже найдена некоторая точка, достаточно близкая к точке минимума. 3. Исследуем сходимость метода (2) — (5) без предположеяия, что тс р'г Т е о~р е м а 2.
Пусть 0 — вьспуклсв замкнутое множество ив Е", функция г(и) сильно выпукла и принадлежит классу Сз(У) и )Ув(и) — св(с)) (б)и — с), и, еж У, Ь=солзс. (13) Тогда последовательность (иь) однозначно оирвдвлявтся условиями (6) при любом выборе начального приближения иг. Пели д = (Ьсс(29)) сис — ое) ( 1, (19) тс последовательность (аП, опредсляемая услсви ми (6), сходится к точке и — решению задачи (1), причем справедлива оценка ) иа — и„ ) < "с ~ у ~ (й д~ (1 — д~ ) , й = О, 1, ...; (20) 334 мктоды мнннмнзлцнн еэункцнн многих пкгкмннных егл.
э однозначно определяют точку ив+о Таким обрааом, существование последовательности (ив) из (6) доказано. Применив теорему 4.2.3 к функции Хв(и) на У, получим (Хд(ид~ьв), и — иде.в) > О, иенУ, й= О, 1, ... (22) Может случиться, что ив+е — — ив. Тогда из (23) имеем <Х'(ив), и — ив> ) 0 при всех и ш У. Согласно теореме 4.2.3 в этом случае ид — — ив — задача (1) решена, Поэтому можем считать, что ив ~ идте при всех й = О, 1, ... Положим в (23) и = иь Получим <Х'(ив) + Х" (ив) (идте — ив), ив — Ш+е> ) О.
Отсюда и иа (21) имеем 1в(ив+е — ив) < <Х" (ив) (идте — ив), ив„.е — ив> ~( « Х'(ив), ив — идте>, й = О, 1,... (24) Оценим правую часть (24) сверху. Для атого в (22) ааменим й на й — 1. Получим (Х„в(ид), и — ид))0, и ем У. Полагая здесь и = иввь имеем е'Хд (ид), ид — и,„)<0, й=1, 2..., Отсюда, из формулы (2.3.5) и условия (18) следует <Х'(и,), и, — и,+ > ((Х'(и,) — Х, (и,), и, — и,„) = = <Х' (ид) — Х'(ид ) — Хв (и в) (и — ид ), ид — ид+ ) = 1 ее~*(~- -"(" —" )) — '(" 3 "(" — "-)" "+Хе е Х < 2 )ид — ид )з)ид — ид„е), й=1, 2, ...
Подставив полученную оценку в (24), получим (ив+е — ив) < (ХХ(21в)) (ив — ив е)в, й = 1, 2, Докажем оценку )и,„— ид)<(2иеХ)д, й=0,1, ... (25) (26) При й = 0 эта оценка следует из условия (19). Сделаем индуктивное предав положение: пусть (и — и (< (29Я) о при некотором й ) 1. Отсюда и из (25) имеем ) и +т — ид)< (йу(29)) (2)вИ) (д ) = (2)в/Ь) д . ОЦенка (26) доказана.
Из (26) следует в — в Р-1 '(и — и„(< ~ )и + — и )( ~г — о (~ '~в 2)в зев ев=д ев=д < ~) — ч~ < — чз (1 — ч~ Х (27) Так как Хд(и)— = Х'(ид)+Хв(ид)(и — ид), то неравенство (22) перепишется в виде <Х(ив) + Х" (ив) (ив+е — ив), и — ивы>) О, и ш У, й =О, 1,... (23) МЕТОД НЬЮТОНА для всех р, й, р ) й ) О. Так как 0 < ч < 1, то правая часть (27) стремится к нулю при й- о . Это значит, что последовательность (иь) фундаментальна и сходится к некоторой точке и„.
В силу эамкнутостн множества ХУ точка и ~ (У. Переходя к пределу при р -ь оо, ив (27) получим оценку (20). Остается убедиться в том, что и„ вЂ” точка минимума 1(и) на (У. Так как 1(и) зи Сг(ХУ), то при й -ь оо иэ (23) имеем <У'(из), и — и„> )ж 0 при всех и зн (У. Учитывал выпуклость 1(и), отсюда и иа теоремы 4.2.3 эаключаем, что и — решение задачи (1). Теорема 2 доказана.
Иэ (20) при й=О имеем (и — иг(((2(г(Л) ч(1 — ч) г. Это неравенство означает, что метод (6) при УУ ~ Е", так же как и метод (8), который получен иэ (6) при (У=Е, сходится, вообще говоря, лишь при выборе достаточно хорошего начального приближения. 4. Перейдем к рассмотрению метода (2) — (4) с выбором шага сса —— = йго, где й — минимальный номер, для которого выполняется неравенство (10).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
