V Канатников и др. Дифференциальное исчисление функций многих переменных (1081393), страница 36
Текст из файла (страница 36)
Повторяя процедуру, мы получаем последовательность (х~'1 точек в окрестности Щх„я), подчиняющуюся (9.10). При этом выполняются неравенства 265 9.3. Проблема глобальной екодимости Пример 9.2. Рассмотрим систему 2(х + хг)г+ (х1 — хг)г — 8 = О, хг+ (хг,3)г каждое уравнение является алгебраицесиим 'уравнением второго порядка и иа плоскости х10хг описывает эллипс (рис. 9.1). Видно, что система имеет два решения, одно из которых легко находится: х1 — — хг = 1 (точка пг на рис.
9.1). Выбрав в качестве начального значения х1 — — — 1, хг — — 1 (точка А на о о рис. 9.1), согласно (9.9), последовательно получаем следующие значения: Рис. 9.1 т Найдено приближенное значение х. и ( — 1,1835 1,5868) для другого решения заданной системы (точка В~ на рис. 9.1). Взяв в качестве начального приближения х", = 2, хг — — 2 (точка И на рис. 9.1), получим другую итерационную последовательность, сходящуюся к решению системы х = (1 1) (точка йг): 9.3. Проблема глобальной сходимости Рассмотренные выше методы являются локальными, т.е.
оии сходятся к решению, если начальное приближение находится уже достаточно близко к этому решению. На практике. 266 9. ЧИСЛЕННЫЕ МЕТОДЫ однако, такого хорошего приближения нет и серьезной и блемой (может быть, самой важной) является поиск хоро,„ Ц1ЕГО начального приближения. В решении этой задачи могут помочь приемы, расщир„,о щие область сходамостви локального метвода, т.е. мн „„ ОЧКЕ ство тех начальных приближений из которых ерационн,„ последовательность сходится к решению. Здесь мы оста„,„ вимся на методе Ньютона и способах расширения его обло ти сходимости.
Вспомним, что для метода Ньютона итерационный пара метр ту+1 равен единице. Одна итерация метода Ньютона состоит в перемещении из текущей точки х~ в следую1цуйо х~+1, причем вектор смещения (ньютоновский шаг) ьх~+! определяется текущим значением и текущей матрицей Якобц по формуле Ьх~+1 = — (Р(х~)) Цх~). Введение итерационного параметра означает, что сохраняется направление перемещения (шага), но изменяется его величина.
Основная причина неудачного ньютоновского шага состоит в том, что он оказался слишком велик и на таком расстоянии линейное приближениг функции, построенное в точке х~, недостаточно точно. Поэтому основной стратегией здесь является уменьшение ньютоновского шага, т.е. введение в каноническую форму одношагового итерационного метода итерационного парамеп1ра туч+1 ( 1, Чтобы реализовать указанную стратегию для системы (9.1) необходимо оценивать, насколько удачным оказался очередной шаг.
В качестве критерия оценки используют величину ~(К(м )~~, вычисленную по какой-либо норме. Мы остановеисл на случае евклидовой нормы. Выбор такой оценки, по суше ству, означает, что вместо поиска нуля вехпйорной функци" Г(х) ищется минимум скалярной функции фх) = ~Щх)~~". Отметим, что — ~(У;~м))'=2~рм) ~'~ ~, ~ 1=1 1=1 267 9.3. Проблема глобальной сходимости «.(х) — координатные функции векторной функции Е'(х). г,~е ~' ~ этому у'(х) =2(Г(х)) Р'(х).
взводная скалярной функции ~р(х) в направлении ньютои0 кого шага, вычисляемого по формуле з = — (Г'(х)) .г (х), авиа Ж-- = ~р'(х) — = — — (Цх)) Е'(х)(Г'(х)) 'г(х) = дз !!з!! !!з!! 2(Р(х)) Р(х) 2Щх)!!' !!з!! !!з!! 3то значит, что в направлении ньютоновского шага функция ~р(х) убывает (такое направление в теории конечномерной оптимизации называют направлением спуска). Итак, можно использовать следующую стратегию поиска решения нелинейной системы. 1. В очередной точке х~ вычисляем ньютоновский шае 3.
= — (Г'(х )) Г(х~) и полагаем трц.1 — — 1. 2. Выбираем точку х~+' = х~+ т~+1з~. 3. Если !!Цх~+')!! < !!г(х~)!!, то оставляем точку х~+' в качестве окончательного результата текущей итерации. Иначе Уменьшаем параметр ту+1, например вдвое, и повторяем попытку (п.2) с новой величиной шага. Предложенная процедура носит название метвода лимей~ово поиска. В этой процедуре можно применять различные ПРиамы уменьшения итерационного параметра. Выбор такого "Риема играет важную роль. Если величина шагов завышена (а точнее, недостаточно уменьшена величина ньютоновского ша"а), то эффект от модификации метода Ньютона, возможно. Ие будет достигнут и полученная итерационная последователь- "Ость не будет сходиться.
Это можно наблюдать даже в од- '270 9. чис.:льнньт методы жет сходиться к точке минимума у(х), но не давать рещон„ нелинейной системы. Способов достаточно общего харак. ра., позволяющих обходить такие ловушки, по-видимому, н„,. Единственное разумное решение в данном случае — смени ч'ь начальное приближение и повторить метод решения еще раз Итак, метод Ньютона можно модифицировать с помощь, итерационного параметра таким образом, что область сход„ мости метода заметно расширится и модифицированный метр станет фактически глобально сходящимся методом"'.
Тако„" подход имеет одно явное преимущество: он дает метод, ко. торый, с одной стороны, является глобально сходящимся, а с другой стороны, обладает высокой скоростью сходимостя вблизи решения. Такие свойства метода являются следствием того, что на каждой итерации для первой попытки выбирается ньютоновский шаг. Отметим, что предложенные приемы расширения области сходимости не являются универсальными: в конкретных ситуациях они могут оказаться неэффективными и в таком случае нужно использовать другие модификации метода Ньютона. По-видимому, методов, обеспечивающих глобальную сходимость в любых ситуациях, не существует. Рассмотрим другую стратегию выбора укороченного шага. Этот вариант выбора очередного шага можно назвать методом доверительной областпи. Основная его идея заключается в том, что в текущей точке х~ строят доверительную область (х Е В": ~~я — х~~~ ~ яр~~.
В этой области функцию .г (х) заменяют ее линейным приближением тр~(х) = Р'(х ) + г'(х )(х — х ), а тогда функция ~р(х) = ~~Е(хц получает квадратичную ап проксимацию т~ч(х) = ~~трр(х)~~ . 'См.: Деннис Дж. 1'мл.~, Шнсбель Р.
(с. 186). "Область сходимости глобального метода достаточно широка, но мо'хе не охватывать все возможные варианты начального приближения. 272 Я. ЧИСЛЕННЫЕ МЕТОДЫ Параметр е нужно выбирать исходя из типичных эна ~„н, . ний координатных функций векторной Функции Р(ж), а парам .„ астр о — исходя из значений координат точки х.. Может оказа~ ь„ 'ься что координатные функции векторной функции Цю) прини мают значения разного масштаба. Например, первая коорди натная функция имеет значения порядка 10э — 104, а вторая порядка 10 4-10 э.
В этом случае в используемых оценках которые строятся с помощью нормы в К", влияние координат ных Функций будет заметно различаться. Это, скорее всего ~Ф приведет к большим ошибкам в решении по некоторым коор. динатам. Кроме того, большие различия в масштабах коорди натных функций могут быть причиной плохой обусловленнос ри ~!У] матрицы Якоби. Это приводит к трудностям при решении систем линейных алгебраических уравнений в методе Ньютона.
Точно так же на эффективность итерационного метода отрицательно влияют большие различия в значениях неизвестных н системе нелинейных уравнений (аргументов функции Р(ж) ), Избежать отмеченных проблем можно, если при постановке задачи на решение нелинейной системы проанализировать функции в левых частях уравнений и, если необходимо, изменить масштаб координат как в области определения, так и в области значений векторной функции Г(х). Пример 9.3. Некоторую иллюстрацию проблем, связанных с глобально сходящимися методами решения нелинейных систем, дает система уравнений из примера 9.2. В зависимости от выбора начального приближения итерационная последовательность метода Ньютона или его модификация с методом линейного поиска может сходиться к одному из двух решений но может и не сходиться вообще или сходиться слишком медленно. Поведение итерационных последовательностей при различных начальных приближениях отражено на рис.
9.3. Векторы, построенные в системе координат, указывают направление ньютоновского шага. На рисунке явно просматриваются три области, приводящие к разнотипным итерационным послед~- 273 Вопросы и эадзчи ельностям. Линией разграничения этих областей является ват г г Ган нербола 5х~+ 12х~хг — хг+9х~+ Зхг —— О, в точках которой яро кобиан вектоРной фУнкции Равен нУлю. Рис. 9.3 Вопросы и задачи 9.1. Определите количество корней системы нелинейных уравнений и найдите одно иэ решений системы методом Нью- тона с заданным начальным приближением: е -у+4=0, а), ' хо=4, до= — 2; х -у+3=0, х +у — бху=О, ) г+4 г 4 0 о 3 уо + у ) ~ (х~+2у~)~ — 7(ж~ — 2уг) =О, ~Зх +4у — 14=0; 9 2. Систему нелинейных уравнений из предыдущей зада- ч® Решите модифицированным методом Ньютона.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
