Б.П. Демидович, И.А. Марон - Основы вычислительной математики (1132358), страница 60
Текст из файла (страница 60)
[1)). Л ем ма 1. Если Р(х)=~~ст(х)] (пхг), еде Д! (х) непрерывны вместе со своими чостнаыш произеодньиаи первого порядка в выпуклой области, содержащей точки х и х+Ьх, то ЦР(х+ Ьх) — Р(х) Ц( гЦЬхЦ ° ЦР' (ч)Ц, (3) еде к =х+ ОЬх, 0 < О < 1 и норма матриц понимается е смысле в-нормы. Д о к а з а т е л ь с т в о. Применяя формулу Тейлора, получим: г л Р (х+ Ьх) — Р (х) = ~Д!~ (х+ Ьх) — Д~ (х)) = ~~~'. +-У-Ьл дл» где $! —— -х+О! Ьх, 0 < 6! < 1; != 1, 2, ..., и; /=1, 2, ..., г.
Отсюда, фиксируя х и х+Ьх, будем иметь: ЦР(х+ Ьх) — Р(х) Ц = ! ! ! ) Ф 1 г и ~(шах~~!,~~), ~ ст О ~ ) Ьяа) < ! г=! Г и (шах)Ьх„) ~вал~Ч»' ~ !~ О (= а ! ! !,! !д)! (Ц! ) гЦЬхЦвах~~~~ ~ О О! ° Так как число пар (1, Я конечно, то найдется пара (р, а) такая, что вал~~!, ~ !! О ~=~~), ~ '"' "т ~ч.-вал~~> ~ '~ "' ~=ЦР'(Ц)Ц, А=! а-! А=! где $=$ее. Таким образом, ЦР(х+Ьх) — Р(х)Ц ! гЦЬхЦ ЦР'(4)Ц, что н требовалось доказать. 5 21 овщии замечании о сходимооти пгоцзссь ньютона 459 Следствие 1. Если /> (х) у(х) = †>я(х)- то Ч(х+ дх) — У(х)П вЂ” )!ДХЦ.)К(И, где Ц=х+Одх н О (8 (1. Здесь г = 1. Следствие 2.
При у(х)~С'з> имеем: Цг (х+ Дх) — г (х)Ц ~л))дхЦ )(г (ь)Ц. где Р,=х+ОДХ и 8<8<1. Лемма 2. Если 1> (х) Е Сив ~(х) = в вмлуклой области, содержащей точки Х и х+дх, го )(г (х+ Дх) — л (х) — л (х) ДхЦ к — лЦДХ)('))1 (ь)Ц, (4] где й=х+Одх и О (8 (1. Д о к а з а т е л ьс т в о.
Используя двучле иную формулу Тейлора> получаем: ((~(х+ дх) — у(х) — ~'(х) д хЦ = Щ (х+ дх) — ~, (х) — сК~, (х;)1 Ц Ф ~! ь ку ка где $с — — х+8;Дх, О < 8, (1. 460 пгивлиженное вешании систем нелинейиыя тгланений (гл. юп Так как то из неравенства (5), учитываи смысл нормы, получаем: Цг (х+ дх) — л (х) — Т (х) дхЦ ~ — Цдхй'(Цл" (ь)Ц] = 2Ц где $= $ =х+Одх и 0 < О(1. О 3*. Существование корней системы н скодимость процесса Ньютона Т е о р е и а 1.
Пусть дана нелинейная система алгебраических или трансцендентных уравнений с действительными коэффициентами д" (х) = О, (1) где вектор-функция определена и непрерывна, вместе со своими частными производными первого и второго порядков, в некоторой области св, т. е.
~(х) Е С"' (се). Положим, что х®ь' есть точка, лежащая в с» вместе со своей замкнутой Я-окрестностью: О~ (х®") = ( 1( х — х"' 1) ~ Я] ь= се, где норма понимается в смысле т-нормы *) (см. гл. Ч11, Ц Т), причем выполнены следующие условию «) То есть если А=(аП), то 11 А Ц = Ц А Цм = шах ~~~ ( аП(.
й 31 стгцвствовлннн котннй и сходимость птоцвсса ньютона 461 1) матрица Якоби йт(х) = ~ — г~ при х = хь® имеет обратГ дуг ~дкг ную Гь= Ю' '(х'ь'), где )! Гь!( ( Аь") ' 2) 3Г у(х'гп)Ц ( В ~ — ' и 3) ~~ Г ' )~«:С дх~ дхь при г, != 1, 2, ..., и и х ~ иу~(х")' 4) постоянньге А, Вь и С удовлетворяют неравенству )ге = 2пАьВьС ~ 1 (2) Тогда процесс Ньютона Х'~ г' = Хоп — (Ь' г (Хоп)т (Хпн) (3) (р = О, 1, 2, ...) при начальном приближении х'ь' сходится и предельньгб вектор х" = 1!гп хцн ц есть решение системы (1) такое, что 1)х' — х!ог(1 ~ 2Вь ~ Я. Доказательство, Введем обозначения Ь = () х"'+ и — х'"'(( = игах ~ хьш+ г! — хгю ~, Г = йр '(х'"') (р=О, 1, 2, ...). я Цх!и хгыЦ Ц (Р-1(тггп) Ьг(хгсч)Ц ~ В с Ж . ч) Иными словами, если Ф' (кь) =[аН), то Гь= !р ' (к<ь) = ~ — т~, ГА г1 -~б1' где А — алгебраические дополнения элементов агу н !!=де!(аВ) я, следо- вательно, () Т 3 = шах — ~ 1 Ар).
! 1а(г, Из формулы (3) имеем: й, = ~) Г,У(хгтп)(). Исходя из условий 1) — 4), получим оценки для величин Г и Г У(ллР>). Рассмотрим сначала случай р=1. Используя условие 2), имеем иж (х'и) ~ ОМ(х>о>). Для оценки Гт= В' '(х'и), воспользовавшись соотношением (АВ) о=В тА >, представим эту величину в виде Г,=[(Р'(х>о>) ГоЯ1(х>т>)) '=[Г Я7(хп>)) 'Г . (4) Учитывая условие 1) теоремы, имеем: ЦŠ— Го%'(х>п)Ц = ЦГо [)Р'(х>о>) — Ж(х>п))Ц (~ <ЦГоЦ Ц(1> (х>о>) Ю(хп>)Ц(АоЦ[Р (хп>) йг(х>о>)Ц Так как из условия 3) вытекает, что о ЦГ(х)Ц = - Е ~ ',*"" ~<С дх дхо то в силу следствия 2 к лемме 1 получаем: Ц [к (х'") — )г> (х о ) Ц = Цу ' (х' ') — У' (х' ') Ц < пЦх'" — х' ЦС( пВоС; поэтому Ц Е вЂ” Гонг(.к'п)Ц ~<пАоВоС=-" — '> 2 .
Следовательно (гл. У11, $10, теорема 5, следствие), существует обратная матрица [Го(У(хп>))- = (Е-(Е-Гойг(х )))->, причем, так как ЦЕЦ=ЦЕЦ„=1, то Ц[Г Яг(х'и)) тЦ « 2. 1 —— Ро 2 (3) Теперь из формулы (4) выводим: Ц Гт Ц » (Ц [ГоФ (х>т>)) т Ц Г Цо Ц ~~ 2Ао = А>. (6) Далее, из формулы (3) следует: У(х'о>+У') (х"') (х'и — х"') = О. Отсюда на основания леммы 2 будем иметь: [[~(хш) Ц = Цу'(хп') — р (х'о') — У' (х'о') (х'и — х'о') Ц < ~ — и Ц х'." — х'о' Цо Цу" (Ц) Ц < — пЯС, 462 пгивли>каннов гвшвиив снствм нвлинвйных лглвнвннй [гл. хш следовательно, "о~~Во 5 3) стшяствованнв когняй н сходимость пгоцкссл ньютона 463 где ф =хна+0(х'дв — «'в') н 0 < 8 < 1.
Поэтому, учитывая неравенство (6), получим: И Гд Г(хп') И ( И Гд И ИУ(х'и) И ( (~2А, ° ~ лВ,'С=лАвВ,'С= — (двВ, = Вд. 00200=в. Итак, для точки х'н мы имеем; (7у(х'дв) -и (х'м) =ю н, кроме того, ИГ И ~Ад, Ьд —— ((Гд~(х'дд) И(В„ где Ад=2.4в. В,= —,'Р,В,( 4. Я Отсюда получаем: рд=2лАдВ,С=2л 2Ав ° — рвВвС=р, 2лАвввС=рв~(1. (8) Следовательно, мы снова находимся в условиях теоремы с той только рааннцей, что вместо окрестности (7у (х'в') имеем окрестность (7я (х'д'), вложенную в первую. Повторяя аналогичные рассуждения,мы установим, что последовательные приближения хвю (р = 1, 2, ...) имеют смысл я таковы, что (7 (хвв),(7~(х~д>), ~ц~(Хвю), в дг причем И Г И = И %'-д (х'ю) И ( А, ИГ,У(»»И=И вЂ” И(в„, Ар — — 2Аг 1 в,- —,р,,в,, (9) р =2лА В С (р=1, 2, ...).
(19) где постоянные А н В связаны между собой рекуррентнымн соот- ношениями 464 пгивлиженное гешенив систем нелинейных хглвнвний [гл. хш Покажем, что для последовательности приближений хнп (р = О, 1, 2, ...) выполнен критерий Ноши (гл. 711, $9). Действительно, при о ) О имеем: х"'ю Е (7тг" (х'ю). Поэтому !)х'~+~ — хоп))( — ' <е, если р ) М н о ) О, что эквивалентно критерию Коши. Отсюда следует, что существует Иш хьм=хе Е(Уу(х'е1) я+а Убедимся теперь, что х" есть решение системы (1). Из соотношения (3) имеем: „Р(хоч)+ Я7(хю) (х'и+и — хю) =О. Переходя в этом равенстве к пределу при р — оо и учитывая, что при атом х а также, что Яг(хоч] непрерывна и ограничена в Уу(х'е'),будем иметь: 1пп у (х"") = О.
л +ФО Отсюда в силу непрерывности функции у(х) получим1 у ( Иш х'~') =,К (х") = О, т. е. х" есть решение системы (1). Кроме того, ~ (~', )! х'~ и — хоп )! ~ ~~'а~ Вл ( Ве+ — ' +... = 2Во ~ ~. р=е а=а Теорема доказана полностью. Замечая не 1. Если у(х) ЕС'е'(сз) и в области ы система (1) имеет простое решение Хн, т. е.
такое, что У (хн) = О, У' (хн) = )Г (х") чь О, то для каждой точки х'е', достаточно близкой к х», усаовия тео- ремы 1, очевидно, будут выполнены. БыстРОтА сходнмостн пРОцесса ньютОнА 465 % 4) Для проверки условия 2) полезно отметить, что Во дает оценку расхождения начального и первого приближений процесса Ньютона: (( Го~(х'о1)!! =!) х'и — хов () .ц; В„ и позтому зто неравенство легко может быть проверено, как только булет найдено приближение х'т'.
Заме ч а н и е 2. Аналогичные формулировки для теоремы схолимости получаются, если вместо нормы ((А )( использовать нормы (!А!)т или () А 1) о. й 4е. Быстрота сходимости процесса Ньютона Теорема 2. Если выполнены условия 1) — 4) теоремы 1 из й 3, то для последовательных приближений х'Р' (р=О, 1, 2, ...) справедливо неравенство где х" — решение системы и ро определяется формулой (2) из й 3.
Дока за тел ьс та о. Используя соотношения (9) и (10) из й 3, имеем: )ор — — 2пАрВрС=2п ° 2АР, ° 2 (хр,вр Т.С=о 1 =-р,, 2пА,ВР,С=рр Отсюда получаем о )от=ро о о )оо = р о = )оо оо )ор=)оо . Далее, 1 1 оо-1 В,= 2 рр,вр,= — 2м, в,, ПОзтомУ 1 оР-о 1 ор-о Вр= 2 )оо ' 2 )оо .. 2 )оо Во= =(2) ро " '""Во=(2) )ое Во (2) Так как () я~я+и хоч () ~~ В 466 птивлижвнноя тешвнив систем нелннвйных ттхвнвннй [гл. хш то прн у ) 1 имеем: [! х"+" — х'" [! ~ [! х'"н — х'" [[+ [! »(Р+й »0Р+о [! „! ! [! »<Р+РЪ х~ Р~т-и [! ~ ~В +В,+...+В ( ) р0 ВО [1+ )00 +'''+(2) )00 1 Отсюда, учитывая, что р и 1, получаем: [! ХШ000 «(Р) [! ( ~(-,')'рО'-'В0 [1+-,'+ ... +(-,')' '~ ~~(-,')' 'рО'-'В0 Переходя к пределу прн д — оо, окончательно находим: [!»" —.«' ')[и (-) )00 В0~~(2) )00 'ть, где )00 = 2лАОВ0~ ~ 1.
Таким образом, при )0 ( 1 сходимость процесса Ньютона — сверхбыстрая. В частности, при р = О будем иметгм [! хь — х™ [! ~ 2В ~ Я. ф 60. Единственность решения Теорема 3. При наличии условий 1) — 4) теоремы 1 из 6 3 в области [! х — х'0')! ~2В, (1) содержится единственное решение системы (1) ($3). Доказательство. Пусть, кроме решения хн системы (1) из $ 3, определяемого процессом Ньютона, имеется другое роше.
ние х"' этой системы такое, что [! х'* — х™ [! (2В . (2! Последовательные приближения хш (р=б, 1, 2, ...) процесса Ньютона содержатся в окрестности (1) и удовлетворяют условию $(х'~")+ Ю (х'Р "— х'Р') О, где Ят — (6 (хает)) Р $5) ядинстввнность рншвния Отсюда, учитывая, что У(х'*) =О, получаем: яу (х'р+д' — х**) =у(х**) — у(х'р') — %' (х** — х'р') р р и, следовательно, х" — "=Г,(у(»* ) — у (х ) — )(,(х** — И, где г =ярд. Производя оценку по норме, будем иметь: )) х" — х'р+д1)) ()) Гр Й ))у(х**) — у (х'р') — я'р (х** — х рд)((.
Согласно обозначениям $3 (см. теорему 1) )'р () (» Ар. Применяя лемму 2 из % 2, получим неравенство — — (х — ' ') () ~ — С)(х где постоянная С определена из условии 3) теоремы 1. Поэтому ))х" — хР+д>((~ — пАрС))х** — х~дч()а (р=О, 1, 2, ...). (3) 1 Полагая р=О в неравенстве (3» и используя неравенство (2), получим: )( х" — хгп (( ( — пА,С )) х'* — х'а' () ' .. 2пА,В,'С, нли, вводя числа, определяемые соотношениями )др=2пА ВрС, 1 В,+, — †, р,Вр (4) (р=О, 1, 2, ...), находим () х*"-х"')! ()д В,= 2В,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
