И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 18
Текст из файла (страница 18)
Положить 1 = О. 1Х. Вычислить о, = (а, + Ь,)/2. Х. Вычислить значения»р» (о,) и»р» (о;). Х1. Если ф» (о,)» О и ~р» (о;) (О, то положить р = о, и прекратить вычисления; иначе перейти к шагу ХП. ХП. Если ф (о,) ) О, то положить а»~ы = а;, Ь|+~ — — о», 1 = » + 1 и перейти к шагу 1Х; иначе положить а~+~ = о;, Ь, »~ —— Ь„1 = 1+ 1 и перейти к шагу 1Х. Теорема б. Если выполнены условия: (») — функция 7» непрерывно дифференцируема; (»») — начальное приближение х' в алгоритме б таково, что множество Х, = (х ( 1» (х) ( 1» (х»), х Г Б") ограничено, то последовательность х», х', ..., порожденная алгоритмом б, либо конечна (т.
е. после конечного числа итераций алгоритм б зациклитсявточкех» между шагами Ш и Ч или (1! и И, повторяя деление е на 2), причем 71» (х») = О, либо бесконечна и каждая ее предельная точка х' удовлетворяет условию 71» (х') = О. Алгаров»м б' Все ш»ги алгоритма 6, за исключением шага Ч, остаются без изменений. Шаг Ч алгоритма 6 следует заменить шагом Ч', т. е. если »»» ( О, то, используя алгоритм 6Б, вычислить такое число р, что и перейти к шагу Ч1; иначе положить е = е/2 и перейти к шагу 1П. Алгоритм бБ(алгоритм вычисления шагового множителя р для алгоритма 6'). 1.
Выбрать константы 1'Е (О, 1), р ) О (рекомендуется выбнр ать у Е (»/»»1») р = 1). П. Определить функцию»р»: Л»-»- Б' равенством с»( ) =),( + й') — ),(х»)— Ш. Положить р = р. 1Ч. Вычислить значение Ч~» (р). Ч. Если Ч~» (р) ( О, то положить р = 1» и прекратить вычисления, иначе положить р = ру' и перейти к шагу 1Ч. Для алгоритма 6' справедлива теорема, аналогичная теореме 6.
61 Библиографические укгмонпя. При написании параграфа использовались работы [320, 194, 2851. Многие результаты получены ранее [446, 185, 278, 536, 422, 486, 453, 198, 286, 421; 225, 390, 104, 49, 48, 376, 397, 439, 4101., 2.2. Методы типа Ньютона 3 а д а ч а 1. Найти агд ш[п 1е (х) для заданной непрерывно ваял дифференцируемой функции 7е 1 В" -ь 11'. 1.
Метод Ньщтона — Канторовича ПРедположение 1. МинимизиРУемаЯ фУнкциЯ [о дважды непРеРывно дяфференцируема с обратимой матрицей Гессе Ч„[е (х). Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение хе ~ В", положить й = О. Ос но в н о й ц и к л. П. Вычислить вектор движения й» к следующему приближению х»+' из системы уравнений — Ч'.к~е(х») й =Ч1е("). 1П. Если й' = О, то положить х' = х" и прекратить вычисления; иначе перейти к шагу 1Ч.
1Ч. Вычислить следующее приближение х»+' = х» + й". Ч. Положить й = й + 1 и перейти к шагу П. Теорема 1. Пусть выполнено предположение 1. Тогда, если бесконечная последовательность (х»),ь е, порожденная алгоритмом1, сходится к точке х', тоЧ[е (х ) = О. 2. Обобщенный метод Ньютона — Канторовича Предположение 2. (1) — функция [е дважды непрерывно дифференцируема с обратимой матрицей Гессе Ч'„„7з (х), удовлетворяющей условию у,[[у~['<(Чк„7е(х) у, у) и-уз) у~[', уз,ау, >О. (Отметим, что у таких функций существует единственная точка минимумах'). Алгоритм 2 Шаги 1 — П1 такие, как в алгоритме 1. 1Ч.
Вычислить шаговый множитель р„, удовлетвоояющий условию ~,(хл+ р»й») = ш[п~,(ха+ рй'). сье Ч. Вычислить следующее приближение х"+' = х» + р,й". Ч[. Положить й = й + 1 и перейти к шагу П. Теорема 2. Если выполнены предположения 2, то бесконечная последовательность (х')ь ь, порожденная алгоритмом 2, схо- дится к решению хь со сверхлинейной скоростью, т. е. 1хь ь' — х*((ть(хь — хч), где т„= (у,!у~~) Н( Ч~,1,(хь) — Ч'„1,(хь — В (х" — х')) 1, В Е [О, 1]. Если, кроме того, матрица вторых производных Ч' 1ь (х) функции 1ь удовлетворяет условию 1Ч„„1ь(х) — Ч„„1 (у)(((а(х — у1, а( оо, при любых х, у Е В", то бесконечная последовательность (хь)г=ь сходится к решению х* с квадратичной скоростью, т.
е. (! х~+' — х" 1( (у,/у,) н (а/у,) 1х" — х' 1'. Такой вариант обобщенного метода Ньютона — Канторовича в общем случае реализовать на цифровой ЭВМ невозможно из-за тре- бования одномерной минимизации на шаге 1Ч алгоритма 2. Приве- денный ниже вариант свободен от этого недостатка. Алгоритм 2' Н а ч-а л о. 1. Выбрать произвольное начальное приближение хь Е В" и произвольные константы е е (О, Ч,), р Е (О, 1), положить р = 1 и Ь = О. О с н о в н о й ц и к л.
П. Вычислить вектор движения Ь~ к следующему приближению хе+' Ь' = — (Ч',,1,(х")) ' Ч1,(х'). П1. Если Ь» = О, то положить х* = х и прекратить вычисле- ния; иначе перейти к шагу 1Ч. 1Ч. Положить р = р. Ч. Вычислить значение б = 1, (х" + рЬ') — 1, (х') — р (Ч1, (хь), Ь') Ч1. Если б ч ' О, то положить р„= р или вычислить рь из не- равенств Р (1 — г) (Ч1ь (х') Ь') < 1ь ( + РьЬь) — 1ь ( ) ~ Рьг (Ч1ь (х') Ь') и перейти к шагу ЧП; иначе положить р = рр и перейти к шагу Ч. ЧП.
Вычислить следующее приближение хь+~ = хь (. р,йь. ЧП!. Положить Ь = Ь + 1 и перейти к шагу П. Теорема 2'. Если выполнены предположения 2, то бесконеч- ная последовательность (х") ~ ь, порожденная алгоритмом 2', сходится к точке минимума х* со сверхлинейной скоростью, т. е. ~х"+' — х""!/( пЛн ... Лн+ь где Ь7, т( ( оо; Лн~.с( 1 при любом 1 ~ О; Л; -~ О при 1-~ оь.
83 Если, кроме того, матрица вторых производных Ч,'Д (х) Функции /о удовлетворяет условию ЦЧЩ(х) — ЧЩ(у)Ц<аЦх — УЦ, а<оо, при любых х, УЕ В", то бесконечная последовательность (хз)з=о сходится к решению х' с квадратичной скоростью, т. е. ц хз+' — х* ц < (а/у,) ц хз — х* цз. Замечание 2. Используемый в алгоритме 2 способ выбора значения шагового множителя р, /д = О, 1, ..., при выполнении условий теоремы 2' гарантирует, что, начиная с некоторой итерации, алгоритм 2' будет осуществляться с единичным шаговым множителем р„= 1, т.
е. алгоритм 2' вырождается в обычный метод Ньютона— Канторовича (алгоритм !). а. Модвфввадвв обобщеввого метода Ньютова — Невтороввча Алгоритм Я Алгоритм 3 отличается от алгоритма 2' только более простым способом вычисления вектора /д на шаге 11 из системы уравнений — (Чзз/о (х )) /д = Ч/з (х ) Теорема 8. Если выполнены предположения 2 и матрица Н = = (Ч'„,/о (х')) ' удовлетворяет условию узЦУЦ~<(НУ у)<узЦУЦ~ уз)уз>О, ЧУЕК то для бесконечной последовательности (хз)Г=о, порожденной алгоритмом 3, справедливы оценки скорости сходимости Цхе — х'11<6 дзм 6 <оо. Рз(хз) Ро(х ) ~~ (/о(хо) Ро(" )) д/ где д = 1 — 2г (1 — з) удуз (1 + уд/уг)/(угуз) Если, кроме того, начальное приближение х' в алгоритме 3 выбрано достаточно близко к точке х", то р = 1, /г = О, 1, ..., и последовательность (хз)ь д сходится к хе со сверхлинейной скоросдпью сходимости Цхз+' — хеЦ<ддЦхз — х*Ц, где дд — — (1/у,) гпах Ц Ч'„/о (х') — Ч'„,/з (х) Ц, тих, Хз (хЦ/з(х)~(/е(хо), хЕЛ').
В алгоритме 3 на каждой итерации для построения вектора двиз г жения /д используется одна и та же матрица — Ч,„/з (х'). Ниже при- водится модификация обобщенного метода Ньютона — Канторови- ча, в которой обновление матрицы производится через т (т ) 1) шагов. Такой алгоритм занимает промежуточное значение между алгоритмом 3 и обобщенным методом Ньютона — Канторовича (алгоритм 2). Алгоритм Ю' Н а ч а л о. 1. Выбрать произвольное начальное приближение хе Е В", константы г р (О, 9,), р Е (О, 1) и натуральное число т ~в !. П.
Положить) = О, р = 1. Основной цикл. П1. Положить 1 О. 1Ч. Вычислить индекс й = /т + б Ч. Вычислить вектор движения Ь» к следующему приближению х'+' из системы — Ч,'еуе ~х(т) й» = Чго (х»). Ч1. Если й' = О, то положить х" = х» и прекратить вычисления; иначе перейти к шагу ЧП. ЧП. Положить р = р. ЧП1. Вычислить значение 6=1 (х»+ рп»)-И(х») — г (Че(х») й»). 1Х.
Если 6 (О, то положить р, = р и перейти к шагу Х; иначе положить р = рр и перейти к шагу ЧП1. Х. Вычислить следующее приближение х»+' х» + р»й». Х!. Если 1( т — 1, то положить 1 = (+ 1 и перейти к шагу 1Ч; иначе перейти к шагу ХП. ХП. Положить! = 1+ 1 и перейти к шагу П1. Теорема Ю'. Если выполнены предположения 2 и (Ч,„~е(х) — Ч~е1»(У)(~и!х — У$1 а< оо, Чх, Уег)", то бесконечная последовательность (х») Г о, порожденная алгоритмом 3', сходится к решению хе со сверхлинейной скоростью ! О~+от — хе ( ( т ~~ хп — хе 1'+'.
Замечание 3. Сходимость с любого начального приближения является существенным преимуществом обобщенного метода Ньютона — Канторовича и его модификаций по сравнению с обычным методом Ньютона — Канторовича, в котором сходимость гарантируется лишь при наличии достаточно хорошего начального приближения. 4 МодвФивироааивый обобщенный метод Ньютоиа — Кавтороаича, ие требуюищй аычвеаеииа матрицы вторых ировааодиыа Алгоритм 4 Н а ч а л о. 1. Выбрать начальное приближение хе Р 1!", удовлетворяющее условиям теоремы 4, и константы зе ) О, р) О, бз р ) О, а Е (О, »/о) (рекомендуется выбираты ео Е [1О, 1О о[, ~ЕПО ', !О ),а=04;р=1). П. Положить й = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
