V Канатников и др. Дифференциальное исчисление функций многих переменных (1081393), страница 35

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 35)

Это позволяет обойтись без использования частных „роизводных, которые нужны в методе Ньютона (они входят в матрицу Якоби Г'(х1~) ). Но при этом матрицы В1ч+1 в методе црОйдена можно рассматривать как некоторую аппроксимаци~о матриц Якоби Р(ж1~), и с этой точки зрения метод удобно интерпретировать как одношаговый. При выполнении определенных условий метод Бройдена является локально сходящимся, но скорость его сходимости, как правило, ниже, чем скорость сходимости метода Ньютона. Нелинейные методы. Одношаговые методы, описываемые канонической формой (9.2), на каждой итерации приводят к решению системы линейных алгебраических уравнений, что связано с обращением матриц Вщ+1.

Такие методы называют линейными. Для решения нелинейных систем используют также нелинейные методы, в которых очередное приближение ищется как решение нелинейной системы, более простой по сравнению с исходной. В нелинейном мепъоде Якоби для получения очередного "Риближения х1~+' решают и независимых нелинейных уравнений. Каждая координата х~~+ вектора х1~+' представляет собой решение уравнения М М %+1 М Ф Ях1,...,х~ 1,х,х~+1,...,х„) =О, й=~,п. 4ля Решения такого уравнения можно применить один из итеРационных методов решения нелинейных уравнений ~1ц, прием для разных уравнений можно применять разные методы.

9.1. Итерационные методы решения Подготовительный этап. Приступая к решению некото„- нелинейной системы, следует провести ее предварительное рой едование. Это исследование необходимо не только для выиссл а наиболее удобного и зффективного метода ее решения. бора может оказать помощь в определении начального прин,кения, хотя такая цель на практике не всегда достижима, ля задания начального приближения могут понадобиться „ислеиные методы (см, 9.3).

Кроме того, анализ уравнений системы позволяет выбрать более удобный порядок уравн ий и системе, провести нормировку уравнений, а также согласоать масштабы неизвестных. Все зто существенно влияет на, ффективность применяемых численных методов решения нелинейной системы. Пример 9.1. Пусть задана нелинейная система х, — х2 — — О, 2 х~ ~— х1 — — О.

(9.5) При ее решении методом Якоби полезно изменить порядок уравнений в системе: х~ — х~ — -О, 2 х~ — х2 — — О. 2 (й,б) Гогда итерационная последовательность по методу Якоби опре- деляется явными формулами х, + = (х~~)2, (~Г~)2 (9 ~) " процесс вычислений можно построить без внутренних итераций, Рассматриваемая система проста и легко решается анали- ти "чески исключением неизвестных: х2 — — х2, х", — х1 — — О. Она, 9.

ЧИСЛЕННЫЕ МЕТОДЫ т т имеет два решения х. = (О О) и х . =(1 1) . Запишем си, ч с'ге му (9.7) в виде х +' = Ях ), где Ях) = (х~ ~х1) . Так как '~'( ) =, О ~, ~'(О,О) = О О, ~'(1,1) = спеюпральная норма матрицы Якоби отображения 5(х) в точ ках х. и х„„равна ~~5'(О,ОЦ =О и )~У(1,1)~~ =2 соответственн„ Поэтому отображение 8(х) является сжимающим в некоторой окрестности точки х„а итерационная последовательность и тода Якоби сходится к этой точке, если начальное приближение достаточно близко к ней. Напротив, в точке х..

достаточн0е условие локальной сходимости итерационного метода наруща. ется. Можно показать, что итерационная последовательность метода Якоби не будет сходиться к точке х. незавигимо от того, насколько близким к х„, взято начальное приближение. т Например, если х0 = (д д), О < д < 1, то, как нетрудно увидеть, х~ = (д2 д~ ) — ~ х. при У -~ оо. Итак, для вычисления решения х „системы (9.5) итерационная последовательность метода Якоби, построенная согласно формулам (9.7), не годится.

В этом случае можно воспользоваться методом Ньютона, так как матрица Якоби функция т ,Р(х1,х2) = (х~2 — х1 х1~ — ж~), соответствующей системе (9.6), в окрестности решения х„невырождена: дел Р' (1, 1) = -3 ф. О. 9.2. Метод Ньютона Метод Ньютона очень эффективен для уточнения решения так как он обладает высокой скоростью сходимости вблиз" решения. Чтобы это обосновать, докажем следующие две леммы. 259 Я.2. Метод Ньютона де~има 9.2.

Пусть ~Я~ — некоторая кольцевая норма в иейном пространстве квадратных матриц М„(Е) порядка яиие ~сли ~~А~~ < а < 1, то матрица Е+ А невырождена, причем ~~~(~+А)-1 ~~ < (1 — д)-1. 4 Рассмотрим последовательность матриц Х = Е А+Ая ...+( ц'А', )~=1, 1, ~окажем, что эта последовательность сходится по норме. к „екоторой матрице Х и при этом (Е+ А)Х = Х(Е+ А) = Е. выберем произвольные натуральные числа й и р.

Тогда й+р й 1с+р Х~+„— Х~ = ~(-1) А — ~~1 1-1)'"А = ~ 1-1) А т=О т=О тЫс+1 Поэтому, учитывая, что норма кольцевая ~т.е. ~~АВ~~ < )~А~~ ~~В~~ для любых матриц А и В), получаем ( — 1)'"А < Е1™~1< Р~+р — Х~1! = тес+1 т= 1+1 1 р /с+1 < Е ))АГ~ К с-=с" —,', < — ', тес+1 т=1с+1 Для произвольного числа е > О выберем ЙО так, чтобы д~'+' < <:е(1 — д). Тогда для любых чисел й > ЙО и р й+1 ~,+1 ~~Хц р Х~~~ < < < е 1-д 1-д !ИЕ+ А)Х вЂ” (Е+ А)ХД = фЕ+ А)(Х вЂ” Ху,)~~ < < ~~ Е+ А ~~ '))))Х вЂ” Ху, ~~ -+ О т е последовательность (Х1,) фундаментальна в конечномер- иом линейном пространстве М„(Ж).

Согласно критерию Лоши, эта последовательность сходится к некоторой матрице Х. Отметим, что 260 9. ЧИСЛЕННЫЕ МЕТОДЫ при й -+ оо, т.е. последовательность (Е+ А) Х~ сходится (Е+А)Х. Но (Е+А)Х~=Х~+А — А +...+( — 1)~А~+' =Е+(-1)~А~+' -~ р так как ~[А"+'~~ <- ~~А~~~~' ( д"+1-+ 0 при )с -+ оо. Поэтом, (Е+ А)Х = Е, и матрицы Е+ А и Х невырождены, причем (Е+ А) ' = Х ~Ш].

При этом ~~(Е+ А) '~~ = ))~Х~~ < ~~Х вЂ” Х~~~+ ~~ХЦ = ~')-Ц" А" т=О < Р— ха!) + ~., Р 11 < = ~~Х вЂ” ХД+ < пх — х~))+ ~ д < ))х — х~~)+ —, 1 п~=О 1 — д ))(Е+ А) 1)) <— Лемма 9.3. Пусть функция Г непрерывно дифференциррма в некоторой окрегтностпи 13(х.,г) = (х Е $Г: ~~х — х.~~ < г) точки х., а ее матрица Якоби удовлетворяет в этой окрестности условию Линшица ))к'(х') — к(х~))) < у)(и — з )) (9.8) относительно нормы матриц, согласованной с евклидовой нормой в Ж".

Тогда для любых точек х,хо б 1цх„,г) верю неравенство ))к(х) — Р'(х ) — Р'(х )(и — х~))) < у))х — и~!) 'На самом деле верно более сильное неравенство (~Р(х) — Р(х ) — Р (х )(х — х )~~ ~~ — ~~х — х ~~ . Р Докаэательство этого утверждения см.: Деннис Дж. ~мл.), Шнабела (с. 98). откуда с учетом ~~~Х вЂ” ХД -~0 при й — ~ оо получаем неравенство 26! 9.2. Метод Ньютона рассмотрим функцию цх) = г(х) — Р(хо) — Р'(хо)(х — хо), прерывно дифференцируемую в Цх„г).

Отрезок, соединя,~~ий точки хо, х Е 0(х.,г), целиком лежит в 1Г(х.,г), так как дл я произвольной точки ~ = х~+ д(х — хо), 0 < д < 1, согласно „вравенству треугольника, имеем ~ф — х,Й = Ц(1 — д)(х — х,)+ д(х — х,)Ц < < (1 д) Цхо х.Ц+д~~х х.И~ < (1 д)г+дг —, Следовательно, согласно лемме 9.1, ЦР'(х) — г'(х ) — г'(х~)(х — х )Ц = ЦЬ(х) — Б(х )Ц < < ЦЬ (~)Ц Цх — х Ц = ЦГ (~) — Г (х )Ц Цх — х Ц, где точка ~ = хо+ д(х — хо), О < д < 1, принадлежит окрестно- сти 10(х„г). Используем условие Липшица (9.8): Ц~(х) ц ") К'( о)( )Ц <~Цф х Ц Ц РЦ Так как Цф — х~Ц = Цд(х — х ) Ц = д Цх — х Ц < Цх — х Ц, окончательно получаем Ц р ( х ) ~~ ( х о ) ~ ( о ) ( х х о ) ! ~ < ~ Ц х х о $ $ Теорема 9.2.

Пусть функция Р' непрерывно дифференциРуема в некоторой окрестности (3(х„,г) = (х Е И": ~~х-х.Й < г) точки х., причем Е(х.) = О, а матрица Якоби Р(х) функции ~(х) в 13(х.,г) удовлетворяет условию Липшица (9.8) относительно нормы матриц, индуцированной нормой в И". Пусть, "Роме того, матрица Якоби Р(х ) в точке х. невырождеиа и,З вЂ” некоторое число, удовлетворяющее условию /3 > ~ Ц(Р(х )) Ц. Тогда существует такое число е > О, что для 263 Я.З. Метод Ньютона довательно, 11(Р'(х)) $1 < $$(Е+А) '11 1]р'( .Г'$$ <2д. Выберем произвольную точку х б 0(х,е) и построим точ„у х1 согласно соотношению (9.9) при Л =О.

Тогда )-'--.-с~'с-')) '~с")~~= с~'с ')) 'с-~с ')-гс"и.-"))~~< $]х'- .11= < !/скс '))-'сгс*,) — кс ") — кс*")с .— "))// < < Ц с~с"))-'/Ц/ гс..) — ~с-') — ~с-') с.. -") // и, согласно лемме 9.3, 11Ж1 — х $1 < 11(ру(хО)) 1!71]х — хО]$ < 2д71]ХΠ— х !$ Тем самым доказано соотношение (9.10) для У = О. Так как 1]ХΠ— х 11 < (28у) ', заключаем, что О 112<11 О 1]х)~ — х,]1 < 1]х~ 1 — х,]1 < ... < 1]ХΠ— х,]1. Следовательно, согласно (9.10), 1]х +' — х,]1 <2у,д]]х — х„]1 < < (2'у,д 1]х — х,]1) ]]х — х.]1 = д 1]х — х, 11, Следовательно, точка х' остается в окрестности Щх„е). Итак, исходя из произвольной точки хО б 1)(х„я), мы в соответствии с равенством (9.9) находим следующее приближение х, которое принадлежит У(х.,е) и удовлетворяет неравенству 1 (9.10).

Характеристики

Список файлов книги