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