Самарский А.А. Гулин А.В. - Численные методы (1078412), страница 38
Текст из файла (страница 38)
Пусть х,— простой вещественньш корень уравнения (!) и пусть 1'(х) ~0 в окрестности У„(х,) =(х: ~х — х )(г). Предположим, что ('"(х) непрерывна в У„(х.) и 0(т,= )п( )7'(х)1, М,= зцр )Г(х)!, (6) кмо,мл меинял причем Мх ! лч — «„! 2м, Тогда если х,енП„(х ), то метод Ньютона (2) сходится, причем для погрешности справедлива оценка !Хд — Х,~ (У~ !Х~ — Х,~, (8) где 2 Мч ! хо — хч ! До к аз а тел ьство. Из уравнения (2) получим 1 (хч) хх„, — х„=хч — х,— р (хь) или Е (хь) хы,— х, =— р (хь) где Г(х) = (х — х )('(х) — ((х), Заметим, что Е(х.) =0 и Е'(х) = (х — х )("(х). 200 (9) (1О) (11) (12) Далее, воспользовавшись тождеством кх Р (хх) = Р (х,) + 1 Р' (!) а(! и выражением (12) для Р'(!), получим Р(ха) = 1 (! — х.))к(!) (Д к Так как функция ! — х не меняет знак на отрезке интегрирования, можно воспользоваться формулой среднего значения и записать, что ка «а — !а Р( ) = ~ (! — Л (!) ( = Р а.) ~ (! — .) (! = !"', ""! Р Ю, « к„ где $„=0«ха+ (1 — 0«)х„)В«!(1.
Обращаясь к (10), получим Р (за! (ха — х„)а хл,„— х„=- * (13) 2Р (ха) т. е. погрешность на (Й+1)-й итерации пропорциональна квадрату погрешности на к-й итерации. Докажем оценку (8) по индукции. При к=О из (13) получим Р (з.! !ха — х )* (14) 2Р («:а! По условию теоремы х,~(1,(х,), и поэтому согласно первому из ус- ловий (б) имеем )Р(х,) (= ап,)0. Кроме того, Ц,=О,х„+(! — О,)х., аза л,=ба(ха х) ! Ва — х.! ()Оа/ (ха — х.( с г, т. е. Ц,еи(l,(х ). Но тогда согласно (б) /!" (с,) ) (М,. Таким образом, приходим к оценке за« (х — х„)а ! хл — х„) = — ' "- = а! ! ха — х,(а 1 совпадающей с оценкой (8) при я=!.
Предположим, что оценка (8) выполняется при 1=1~1, и докажем, что она выполняется и прн /г=!+!. При /г=! выражение (13) принимает вид Р !Е,! !«а — х„!' хы, — х,=- — -'- (15) -! Оч) Покажем, что х„"-,~ч(l,(х ). Действительно, из (8) при й=! имеем )ха — х а!а-')х„;. ! !ха — х ) г, г.
е. хен(1,(х ). Кроме то.о, Оцх,--л.), 10,) " 1. . следовательно, ~,<=. Б,(л.) Теперь можно воспользоваться условиями (6) п оценить !)'(хо) ) «т, >О, !Г'(кеы) ) (Мо. Отсюда и нз (!5) получим ги (х) — х„)о ! х) ю — х, ! ~ 2т, Из этого неравенства н из неравенства (8), имеющего следующий вид при )е=(: ! х) — х, (з ( у™о ( хо — х, )з, получим оценку х )«- '-' "' ' ~д «!хс — х,(= — д (хо — х,(, ПИ !хо х ! ) о) оот — 1 ато т, е. оценку (8) при (е=(+1.
Из оценки (8) следует сходимость метода (2), так как для де=(0,!) правая часть неравенства (8) стремится к нулю при )е — со. Теорема 1 доказана. За ьоеча пня. !. Условие (7) означает, что начальное приближение надо брать достаточно близко к искомому корню. 2. Выпалненне равенстиа ()3) означает, что метод имеет квадратичную сходимость. 3. Поскольку х, заранее неизвестен, иногда трудно проверить условие хоомс',(х.).
Но если известно, что !Г(х)1= он,)0 в некоторой окрестности корня, то для опенки близости яачального прибли»<ения к корню можно воспользоваться нерааенстном !хо — х*! ( !1(хо) !(ть ()б) Действительно, 1(хо) =1(хо) †((х,) = (хо — х,)Р(й), откуда и следует ((б). 2. Кратные корни. Говорят, что х. является корнем кратности р, если ) (х„) = ~' (х,) =... = — У)о " (х.) = О, ()о) (х,) ~ 0 Будем предполагать сейчас, что 1'о "(х) непрерывна в окрестности корня х.
кратности р. В случае корня кратности р квадратичную сходнмость имеет метод Пьютона с параметром ,!'(хе) ' + г'(хх) =О, где т=р. Справедлива Т е о р е м а 2. Пусть х — корень кратности р уравнения (1) и в окрестности (l„(х.) =,'х: )х — х.! (г) производная ('" (х) отлична от нуля. Пусть!'о "(х) неирерьсвна в Е/,(х ) и 0 к а)л= !и( !)"'(х)), 3( .,= знр !~м'п(х)(, хюц ы,) «миг)х,) 202 причем )хс — х,.) Рн т р(р+ !) Тогда если хне=(7,(х ), то метод (17) при с=р сходится, причем для погрешности справедлива оценка ) хи — х,) д"- -т(х, — х,), где Мрм ! хи — х,) д= 1. и!рр(р+ !) Доказательство теоремы 2 мало отличается от доказательства теоремы 1 (см. (25)). Для погрешности х„,— х метода (17) с т=р получаем выражение (10), где т (х) = (х — х ))'(х) — р) (х).
Прп этом Ро"'(х„) =О, т=О, 1,..., р — 1, р. Применяя формулу Тейлора с остаточным членом в интегральной форме, получим, что Р(хс) — — — (( — х)(хх — () г" (()д( (р — !)' .! х, Далее, воспользовавшись формулой среднего значения, получим представление Г(х„) в виде )мто (е!т!) Р (хе) = ' ' (хе — х,)'"'. (р+ )И Для оценки знаменателя выражения (10) используется формула Тейлора с остаточным членом в форме Лагранжа. В результате получаем, что х — и ~'(хи)= ' '* ~!и)(й)в).
(, !)! Далее повторяются те же раг- рис. В. яонотоннни сходимость метода тельстве теоремы 1. Ньютона 3. Односторонние приближения. Если в окрестности корня х производная функции 1(х) сохраняет знак и монотонна, то приближения х„, получаемые в методе Ньютона, сходятся к х, с одной стороны. Это означает, что последовательность (х„) либо монотонно убывает, так что х <х„„,<х„для всех я, либо монотонно воз- 203 растает, так что х„(х,+,(х. для всех Й.
Монотонная сходимость метода Ньютона хорошо видна на рис. 6. Важное свойство монотонности метода Ньютона более точно сформулировано в теоремах 3, 4. В этих теоремах предполагается, что на отрезке (а, Ь1 уравнение (!) имеет единственный корень х и функция )(х) дважды непрерывно дифференцируема. Теорема 3. Пусть для всех х~(а, Ь1 либо ~'(х) )О, 1" (х) )О, (18) либо либо 1 (х) <О, 1-(х) - О, Тогда последовательность (хД, определенная согласно (2) с х,=а,монотонно возрастает и сходится к х .
Поскольку формулировки н доказательства теорем 3, 4 совершенно аналогичны, ограничимся доказательством теоремы 3. Доказательство теоремы 3. Монотонность последовательности (х ) докажем по индукции. По условию х,=Ь. Предположим, что для некоторого Ь= 0 выполняются неравенства х,<х„(Ь, (20) и докажем, что тогда (21) х.(х,„,- х,. Перепишем уравнение (2) в виде Г (хь) — г (х,) хх — хь„= 1' (х„) и воспользуемся формулой конечных приращений Лагранжа. Тогда получим (хь — х*) Г (ах) хь — хь„= Т (хх) где 5„ен (х„х,). Пусть выполнено условие (18).
Тогда 0 ~ 1 р (х ) (23) причем последнее неравенство является следствием монотонного возрастания Т'(х). Те же самые неравенства (23) выполняются и в случае условий (19). Таким образом, (хь — х,) Т (~х) С хх — х„ Т (хх) 204 Г'(х) ~0, 1" (х) ~0, (19) Тогда последовательность (х,), определенная согласно (2) с х,=-Ь, монотонно убывает и сходится к х . Т сор е м а 4. Пусть для всех хе=(а, Ь1 либо ('(х) ~0, г'(х) (О, и из (22) получим 0(хг хг<-(ч хг х, т. е. получим требуемые неравенства (2!). Таким образом, последовательность (хг) монотонно убывает и ограничена снизу числом х,. Поэтому данная последовательность имеет предел, который в силу непрерывности функции 1(х) и условия Т'(х„)~0 совпадает с корнем х, уравнения (1). Теорема 3 доказана.
Сделаем замечания отяоснтельяо скорости сходямостя метода Ньютона пря условиях теорем 3 я 4. Если начальное пряблежепяе х» выбрано достаточно близко к искомому корню, тзх что выполяяется условие (7), то согласно тео. реме 1 метод имеет квадратичную сходямость я для погрешяостя справедлива оценка (8). Есля же условие (7) не выполнено, то па начальных итерациях погрешность будет убывать более медленно. Однако в силу сходимостн последовательности (х,) найдется номер л=я», для которого очередное приближение хг, удовлет зорят неравенству М,) х„— х,) н с этого момента сходямость станет квадратичной.
4. Комплексный корень. Пусть ) (г) — функция комплексного переменного г=х+(у н г„=х„+(у„— простой нуль )(г). Будем считать, что 1(г) аналитична н некоторой окрестности г. Тогда можно рассматривать метод Ньютона гг„=гг — —, й=0, 1, ... 1(ге) (24) р (гз) Сходимость метода (24) устанавливается в теореме 5, которая обобщает иа комплексный случай теорему 1. Теорема 5. Пусть г.— простой корень уравнения Т(г)=0 и пусть )(г) аналитична в круге и,(г„) = (г: ) г — г,) ~г). Предположим, что 1п( )1'(г))=т()0, зир 1)»(г))=М„ гыуг (гм гни (гл (25) причем Мг! гг — х» ) 2гл( (26) Тогда если ггенУ,(г.), то метод (24) сходится, причем для погрешности справедлива оценка ~)гз — г„) <()з=')го — г,), (27) еде ля(гг г*) ~ 1 (28) 2/и( ИФ6 Д о к а з а т е л ь с т в о. Для погрешности получаем уравнение гоо — «", = Г (го) (29) (го) где г'( ) = ( — .)1'( ) — ('( ), Г'(2) =( — .)1" ( ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
