Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 80
Текст из файла (страница 80)
Этот вариант метода Ньютона кратко будем навывать методом (2) — (4), (10). Покажем, что метод (2) — (4), (10) сходится при любом выборе начального приближения и этим выгодно отличается от метода (2) — (4), (6). Т е ар е ма 3. Пусть сУ вЂ” замкнутое выпуклое множество из Е", 1(и) ш ш Сг(УУ) и р!В(г(<Хв(и)$, 3>(М)й)г, иш(У, 3шХю (28) где Уи — надпространство, параллельное аффинной оболочке множества ХУ, а р, М вЂ” постоянные, 0 ( )з ( М, Тогда последовательность (иь), определяемая методом (2) — (4), (10), при любом начальном приближении иззн П существует и сходится к точке и„— решению задачи (1). Если, кроме того, 1" (и) удовлетворяет условию Липшиуа (18), то найдется номер йг такой, что в (4) аь = 1 при всех й ) йг, и справедлива оиенка 2(ь жч этл 2(ь гпг ьах *(< т. Р„Ч < т.
Ч (1 — Ч У, й)йо (29) У(окаэатель сиво. Согласно теореме 4.3.4 1(и) сильно выпукла. Тогда ив теоремы 4.3.1 следует существование и единственность точки иь, удовлетворяющей условиям (3). Согласно теореме 4.2.3 тогда <Уа(и ), и— — ип) ) О или <1'(иь) + 1л(иь) (иь — иь), и — иь> ) 0 при всех и ш П. (30) Если окавалость что иь = иг, то иа (30) имеем <Х'(иь), и — иь>) О, и си УУ. В силу теоремы 4.2.3 и выпуклости 1(и) отсюда следует иа — — иа = ив— аадача (1) решена.
Поэтому можем считать, по из Фин Тогда Хь(иь) ( < Хь(иь) = О. Покажем, что тогда сУществУет хотЯ бы один номеР 1) О, для которого выполняется условие (10). С этой целью возьмем проиэвольное число а (0<се(1), и положим и = иь+ се(йь — иь). Отсюда и ич выпуклости Хь(и) следует Хь(и„) ( аУь(иь) + (1 — и)1ь(иь) = пХь(йь) ( О. Тогда иэ формулы 1(и ) — 1(иь) = Ха(и„) + (а'т2)<(Хв(иь+ Ои(йь — иь))— — Ул(иь)) (ик — иь), йь — из>, О < а ( 1, (ЗЦ с учетом условий (28) получим 1(иа) — 1(иь) < Уь(иа) + (сзз/2) (М вЂ” р) (йь — иь)г < ( пУь(йь) + (аЦ2)М(йь — иь(г, 0 < а ( 1.
(32) 336 МЕТОДЫ МИНИМИЗАЦИИ ФдНКЦИИ МНОГИХ ПЕРЕМЕННЫХ 11»Е Ь Так как йд — точка минимума сильно выпуклой функции Хд(и) на (/, то согласно теореме 4,33 (ид йд(д (~ (2/)д) [Хд(ид) — Хд(ид)) = (2/р)(Хд(йд)(. (33) Подставив ету оценку в (32), получим У(ид) — 1(ид) < — и(1д(йд) (+ а'(М/р) /Хд(йд) (, 0 ( а < 1. Воаьмем произвольное а, удовлетворяющее условиям 0 < ед = Л (1 — е) р/М < а < (1 — е) р/М < 1.
(34) Отсюда и из предыдущего неравенства будем иметь 1(ид) 1(ид+ а(ид — ид)) ~ )а(1 — а(М/)д)) (Хд(йд) ( ~ >еа~Хд(йд) ( (35) при всех а, удовлетворяющих условиям (34). Воаьмем такой номер т ) 1, для которого Л'" ( (1 — е)р/М < Л -'. Отсюда следует, что 0 < ц» = Л (1 — е) р/М < Лм ( (1 — е) р/М. (36) 1пв ~ и — и ~ = О. д (38) Далее Заметим, что согласно (37) (ид) шМ(ид) = (и: иди (Х, 1(и) < 1(ид)). Для сильно выпуклых непрерывных функций множество М(ид) выпукло, замкнуто и ограничено. Тогда последовательность (ид) имеет хотя бы одну предельную точку. Пусть и, — произвольная предельная точка (ид) и пУсть [ид ] — и .
С Учетом (38) и Условием 1(и) ш Сд((Х) из (30) при й = /ди-ьсе получим (Х'(и„), и — ид) ~ )0 для всех и ш ХХ. Согласно теореме 4.2.3 тогда е„ = ид — точка минимума 1(и) на П. Следовательно, Пш Х(ид) = Пш Х/и„) = Х(ид) =Х„т. е. (ид) — минимиеирую«»-» д е»» щая последовательность. Отсюда и из теоремы 4.34 следует 1ид)-»- ид. Пусть теперь выполнено условие (18). В силу (38) существует номер йе такой, что (Х/р)(йд — ид( (1 — е при всех /д ) йд. Иа (31) с учетом условия (18) и оценки (ЗЗ) тогда имеем 1(и„) — У(ид) < а/д(йд) + (и'/2)Х (йд — ид(~ < ( — и(Хд(йд) ) + ад(Ь/р) ~ Хд(йд) ~ (йд — и» [, Таким обрааом,а = Л удовлетворяет условиям (34) и, следовательно, при а = Л будет справедливо неравенство (35).
Это значит, при д = и» выполняется условие (10). Тогда найдется наименьший номер д = й (О < »д ( и), 1 удовлетворяющий неравенству (10). Приняв в (4) ад — — Л е, получим следующее приближение идт». Тем самым покааано, что последовательность (ид) из метода (2) — (4), (10) при любом начальном приблидкении существует. Из (10) при» = де имеем 1(и ) — 1(ид„,) ) аа~(1~(й~) ), й = О, 1, ... Учитывая, что согласно (36) ад — — Л е) Л~ > е, отсюда получим о' Х(ид) — 1(идш) ) ееа(Хд(йд) (, й = О, (37) Таким образом, Х(и„)) Х(идт ) ) Х (й = О, 1,...). Тогда существует Пш У(ид)) Х и 1дш (Х(и ) — Х(ид д)) = О.
Из (37) теперь имеем д д 1пп Хд(ид) =О, а из (33) следует д д мнтод ньютона 332 т. е х(и») — х(и„) ) ]х»(и») ]а(1 — а(е/р) ]н» вЂ” и») ) ) ае]х»(и») ] при всех а, еэ( а(1, й ) йэ. Это означает, что условие (10) выполнено при 1 = 1э = О, и, следовательно, а» = Ь = 1, и»ы = и» при каждом й ) йэ. Таким образом, начиная с номера й = йэ, метод (2) — (4), (10) превращается в метод (2) — (5) с начальным приблнэкением и, удовлетворяющим »э в которых матрица А» выбирается из условия Пш !! А, — (Ув (и,))»]] = О, (40) Взяв в (39) А»= (Хв(и»))-', а»=1, приходим к методу (8), который согласно теореме 1 имеет квадратичную скорость сходимости.
Оказывается, и методы (39), в которых матрица А» выбирается близкой к (Хл(и»)) ' в соответствии с (40), обладают высокой скоростью сходимости. Другим достоинством методов (39) является воэможность определения матриц А» из достаточно простых рекуррентных соотношений, использующих информацию с предыдущей итерации, обходясь беэ вычисления и обращения матрицы У" (и»). Примером квазиньютоновского метода является метод Давидони — Флетчера — Пауэлла, в котором матрицы А» определяются соотноше- ниями А»+ =А»+»» (»»)(»») й=О 1 ''' Ао Х' (41) .+, = ° .
где д» = Х'(и»+1) — У'(и»), г» = и»л~ — и», а величина а» находится иэ условия /„(а„) = ш!и / (а), /„(а) = У (и — аА„У' (и )). (42) и>эо Отметим, что векторы р» =А»Х'(и») удовлетворяют равенствам (8.29), так что метод (39), (41), (42) одновременно является методом сопряженных направлений. К методам (39) можно прийти, исходя из других соображений. Ь именно, если  — положительная симметричная матрица, то в К" наряду с обычным скалярным произведением <и, и> = ~Ч>„изот можно ввести в=г другое скалярное произведение <и, в>~ = <Ви, о>. Из представления У(и+ Ь) — Х(и) = <ВВ»Х(и), Ь>+ оЦЬ)) = <В (Х (и), Ь>, + о(<ВЬ, Ь>мэ> условию д = (Е/(2Р]) ~ ил + — иь ~ = (5/(2Р)) ~ и, — и, ~((1 — е)/2( 1.
Отсюда и из теоремы 2 следует оценка (29), что и требовалось. Таким образом, метод (2) — (4), (10) не намного сложнее метода (2]— (5), по скорости сходимости не уступает ему и в то нге время не столь. чувствителен к выбору начального приближения, как метод (2) — (5). При наличии эффективных методов минимизации квадратичной функции Х»(и) на множестве П метод (2) — (4], (10) можно с успехом применлть для минимиаации достаточно гладких функций. Другие теоремы о сходимости описанных выше вариантов метода Ньютона читатель может найти в (19] 5. Для задачи безусловной минимиюцивь когда в (1) (У=В, метод Ньютона является частным случаем нвнэинъюгоновсних методов и»ы = и» вЂ” и»А»Х'(и,), а») О, й= О, 1, ..., (39) 338 мвтоды миннмизлции юункции многих пвгимвнных ~гл.
з следует, что градиентом функции Х(п) в новой метрике является вектор В '1'(и). Отсюда вытекает, что й-й шаг метода (39) представляет собой шаг градиентного метода в пространстве со скалярным произведением, порожденным матрицей В = Аз ~ > О. Поэтому метод (39) часто назынаЮт методом переменной метрннп. С квазиньютоновскими метоцаьеи, методами переменной метрики читатель подробнее познакомится в (19, 48, 1И, 134, 250, 307, 314, ЗЗО, 336). $10. Метод Стеффенсена 1. Описанный выше метод Ньютона на каждой итерации требует вычисления матрицы вторых производных.
Отсюда ясно, что в тех случаях, когда вычисление матрицы Х" (и) требует значительного объема вычислений, трудоемкость каждой итерации метода Ньютона может стать чрезмерной. Поэтому возникает вопрос о возможности построения методов минимизации, которые по скорости сходимости не уступали бы методу Ньютона, но для своей реализации не требовали вычисления матрицы вторых производных. Одним из таких методов является метод Стеффенсена, представляющий собой разностный аналог метода Ньютона (9.8), в котором матрица вторых производных заменяется разностным отношением первых производных градиента по специально выбранным узловым точкам. Поначалу метод Стеффенсена разрабатывался для решения нелинейных уравнений [239), затем он был обобщен па случай операторных уравпений [301).
Применяя этот метод к решению системы уравнений Х' (и) = [У„г (и),..., Х„„(и)[ = О, получим следующий итерационный метод решения задачи минимизации Х(и)- (п1, иш У=Е". Если приближение и„((е > 0) уже известно, то следующее приближение и,ен определяется так: иьо,=и,— (У'(иы и,— [1ь1'(и,))) 'У'(и,), (с=О, 1, ..., (2) где [1,— числовой параметр, Х (и, и) = (зо(и, и)) — матрица разделенных разностей первых производных, определяемая по правилу Ум(и,о) = 17 . (от ...
от т, ит, нэтг, ... но) — У (о,, о( т, о1, нэ+т...,, и ) ид — оз идФп', (3) здесь Хо(и, и) — элемент 1-й строки у-го столбца матрицы Х'(и, и), мвтод ствФФкнсенд $ $0! а У„;(и), Х;„;(и), как и выше, обозначают первые и соответ- ственно вторые производные по переменным и', й функции Х(и) (д, /=1, ..., и); предполагается, что Х(и)юС'(Е"). Тогда из (3) следует, что 11ш)У'(и, о) — У" (и)) = О, У'(и, и) =. У" (и) ч'иеп Е™. ю-~и Это значит, что при 3д=О (/в=О, 1, ...), метод (2) превраща- ется в метод Ньютона (9.8). Как видно из (2), на каждом шаге метода Стеффенсена нуж- но решать систему линейных алгебраических уравнений Х'(им ад — рдХ'(ид) )у = — Х'(и„), у = и„д, — и,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
