Численные методы. Соснин (2005) (1160462), страница 9
Текст из файла (страница 9)
Равенство превратится в уравнение:k+1f (xk ) + f 0 (xk )(xk+1 − xk ) = 0Выразим отсюда xk+1 :xk+1 = xk −f (xk ).f 0 (xk )(3.4)Проведенное преобразование называется линеаризацией уравнения (3.3).Метод Ньютона называется также методом касательных, так как новое приближение являетсяабсциссой точки пересечения касательной к графику функции f (x), проведенной в точке M (xk , f (xk )),с осью OX.Замечание. Метод Ньютона имеет (когда сходится) квадратичную скорость сходимости:xk+1 − x∗ = O (xk − x∗ )2 .Это хорошее свойство, однако метод ведь может и не сходиться.
Возвращаясь к ранее введеннымобозначениям, получим, что S(x) в методе Ньютона считается так:S(x) = x −1 РазработанИ. Ньютоном (1669).f (x),f 0 (x)3.2. ПРИМЕРЫ ЧИСЛЕННЫХ МЕТОДОВто есть τ (x) =1f 0 (x)45.Мы предположили, что метод простой итерации (т.е. и метод Ньютона) является сходящимся, если|S 0 (x)| < 1. Рассмотрим это неравенство поподробнее:S 0 (x) = 1 −(f 0 (x))2 − f (x)f 00 (x)=⇒ |S 0 (x)| < 1 ⇐⇒(f 0 (x))2 f (x)f 00 (x) < 1.⇐⇒ (f 0 (x))2 (3.5)Таким образом, метод Ньютона будет сходится, если неравенство (3.5) будет выполняться на некотором отрезке, содержащем начальное приближение x0 и нужный нам корень x∗ .
Часто такое требованиеприводит к необходимости брать x0 очень близко к x∗ , что не всегда выполнимо.Модифицированный метод НьютонаЕсли у нас есть проблемы с подсчетом производной на каждом шаге, то можно воспользоваться1модифицированным методом Ньютона, где берется τ (x) = f 0 (x0 ) , то естьxk+1 = xk −f (xk ),f 0 (x0 )k = 0, 1, .
. . ,где x0 — начальное приближение.Однако, в этом методе, как мы можем подсчитать, уже не квадратичная, а линейная скоростьсходимости:|xk+1 − x∗ | = O(xk − x∗ ).Замечание. Модифицированный метод Ньютона можно назвать методом одной касательной,так как новые приближения являются абсциссами точек, получающихся при пересечении с осью OXпрямых, параллельных касательной к графику f (x) в точке M (x0 , f (x0 )).Метод секущихКогда нет возможности считать производную, просто заменим ее в формуле (3.4) на разностноеприближение:f (xk ) − f (xk−1 )f 0 (xk ) ≈.xk − xk−1Тогда получим такую формулу:xk+1 = xk −xk − xk−1f (xk ),f (xk ) − f (xk−1 )k = 1, 2, .
. .(3.6)— здесь уже требуется задать два начальных приближения: x0 и x1 . Скорость сходимости будетлинейной.Этот метод называется методом секущих. Для пояснения названия заметим, что уравнение длясекущей, проходящей через точки M 0 (xk−1 , f (xk−1 )) и M 00 (xk , f (xk )) (точки предыдущих приближений), будет выглядеть так:y − f (xk )f (xk ) − f (xk−1 )=.x − xkxk − xk−1Положив y = 0 и x = xk+1 , можно получить формулу (3.6). Это означает, что xk+1 — это абсциссаточки пересечения нашей секущей с осью OX :46Глава 3. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙyM 00M0xk+13.3xkxk−1xСходимость метода простой итерацииКак было сказано ранее, в методе простой итерации уравнение для нового приближения xk+1 таково:xk+1 = S(xk ),k = 0, 1, .
. . ,(3.7)а x0 — заданное начальное приближение.Кроме того, введем такое обозначение для r -окрестности точки a :Ur (a) = {x : |x − a| 6 r}.Теперь мы готовы к формулировке теоремы о сходимости этого метода.Теорема 3.1. Пусть для некоторых r и a функция S(x) удовлетворяет на множестве Ur (a) условию Липшица с константой q ∈ (0; 1) :|S(x0 ) − S(x00 )| 6 q|x0 − x00 |∀ x0 , x00 ∈ Ur (a),причем |S(a) − a| 6 (1 − q)r.Тогда уравнение x = S(x) имеет на множестве Ur (a) единственное решение, а метод простойитерации (3.7) сходится к этому решению при любом начальном приближении из Ur (a), причем дляпогрешности на k-й итерации справедлива оценка:|xk − x∗ | 6 q k |x0 − x∗ |— то есть скорость сходимости линейная.Доказательство. Возьмем начальное приближение x0 из множества Ur (a).
Индукцией покажем, чтоостальные xj тоже принадлежат множеству Ur (a).Пусть xj ∈ Ur (a), докажем, что следующий член последовательности xj+1 ∈ Ur (a).|xj+1 − a| = |S(xj ) − a| = |S(xj ) − S(a) + S(a) − a| 6 |S(xj ) − S(a)| + |S(a) − a|из того, что функция S(x) Липшиц-непрерывна и условия теоремы получаем:|xj+1 − a| 6 q|xj − a| + (1 − q)r 6 qr + (1 − q)r = r.3.3.
СХОДИМОСТЬ МЕТОДА ПРОСТОЙ ИТЕРАЦИИ47Теперь покажем, что последовательность {xk } имеет предел, являющийся решением уравненияx= S(xk ), причем это решение единственно. Сначала установим сходимость, для этого оценимразность двух соседних элементов:k+1|xj+1 − xj | = |S(xj ) − S(xj−1 )| 6 q|xj − xj−1 | 6 . .
. 6 q j |x1 − x0 |.Покажем, что выполняется критерий Коши сходимости числовой последовательности: XXpp k+jk+jk+j−1 k+pkx− xk+j−1 6x−x|x−x |=6 j=1 j=16pXqk+j−110k10|x − x | = q |x − x | ·j=1pXqj−1k10< q |x − x | ·j=1∞Xq j−1 =j=1qk|x1 − x0 |.1−qПоследнее выражение не зависит от p, и его можно сделать меньше любого ε > 0, и мы можемвычислить, с какого k(ε) будет выполнена эта оценка.Таким образом, числовая последовательность {xk }∞k=0 сходится при k → ∞ к некоторому∗x ∈ Ur (a). Покажем, что этот предел является корнем уравнения x = S(x).Запишем итерационную форму нашего уравнения xk+1 = S(xk ), и перейдем к пределу при k → ∞.Левая часть xk+1 , как было уже показано, сходится к x∗ ∈ Ur (a), а правая часть S(xk ) в силуЛипшиц-непрерывности S(x) сходится к S(x∗ ). Таким образом, решение существует.Покажем единственность найденного корня.
Пусть существуют два решения: x∗ и x∗ . Рассмотриммодуль их разности:|x∗ − x∗ | = |S(x∗ ) − S(x∗ )| 6 q|x∗ − x∗ |,откуда вытекает, что x∗ = x∗ , иначе возникает противоречие, так как q < 1.В завершение докажем оценку на погрешность|xk − x∗ | = |S(xk−1 ) − S(x∗ )| 6 q|xk−1 − x∗ | 6 · · · 6 q k |x0 − x∗ |.Теперь теорема полностью доказана.Замечание 1. В теореме получена оценка∀p |xk+p − xk | 6qk|x1 − x0 |,1−qqk|S(x0 ) − x0 |.1−qПотребуем, чтобы xk отличалось от x∗ не более, чем на ε. Так както есть, переходя к пределу при p → ∞, |x∗ − xk | 6qk|S(x0 ) − x0 | 6 ε =⇒ |x∗ − xk | 6 ε,1−qто число итераций, необходимых для достижения такой точности, можно подсчитать так:(1−q)εln |S(x0 )−x0 |.k(ε) = ln qЗамечание 2.
В условиях теоремы сделано предположение, что S(x) Липшиц-непрерывна:|S(x0 ) − S(x00 )| 6 q|x0 − x00 | ∀ x0 , x00 ∈ Ur (a).Это достаточно слабое ограничение, но его сложно проверять. Тем не менее, если функция дифференцируема, а ее производная ограничена той самой константой q, то условие Липшица будет выполнено:|S(x0 ) − S(x00 )| = {применяя формулу Лагранжа} = |S 0 (ξ)| · |x0 − x00 | 6 q|x0 − x00 |— это и есть условие Липшиц-непрерывности.48Глава 3. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ3.4Метод ЭйткенаПусть метод имеет линейную скорость сходимости, то есть для погрешности выполнена следующаяоценка:|xk − x∗ | 6 q k |x0 − x∗ | =⇒ xk − x∗ ≈ aq k(3.8)— мы выразили погрешность через некоторую константу a и параметр q.Допустим, что данное соотношение выполняется точно.
Рассмотрим погрешность на трех соседнихитерациях.xk − x∗ = aq k ;k+1x− x∗ = aq k+1 ;k+2x− x∗ = aq k+2 .Из этих условий легко найти x∗ . Для этого вычтем из второго уравнения первое, а из третьеговторое, тогда получим:xk+1 − xk = aq k (q − 1);k+2x− xk+1 = aq k+1 (q − 1).Вычтем одно уравнение из другого:xk+2 − 2xk+1 + xk = aq k (q − 1)2 .Свяжем это уравнение с предыдущим следующим соотношением:a2 q 2k+2 (q − 1)2(xk+2 − xk+1 )2== aq k+2 = xk+2 − x∗ .k+1k− 2x+xaq k (q − 1)2xk+2Если бы равенство (3.8) выполнялось точно, то можно было бы получить x∗ через три последнихприближения:(xk+2 − xk+1 )2x∗ = xk+2 − k+2.x− 2xk+1 + xkТем не менее, выражение, стоящее в правой части, приближает x∗ намного лучше, чем xk+2 .
Обозначим его(xk+2 − xk+1 )2xk+2 = xk+2 − k+2,x− 2xk+1 + xkи будем считать это равенство алгоритмом построения подправленной итерационной последовательности с элементами xk .Если эту операцию (вычисление подправленных значений) проводить достаточно часто, то новаяпоследовательность из xk сходится к точному решению значительно быстрее, чем исходный метод.Построение подправленных значений последовательности называется методом Эйткена.3.5Сходимость метода НьютонаЗапишем итерационный процесс:xk+1 = xk −f (xk ).f 0 (xk )Он является модификацией метода простой итерации, тогда условием сходимости этого итерационного процесса будет неравенство|S 0 (x)| 6 q < 1,где S(x) = x −f (x)(f 0 (x))2 − f (x)f 00 (x)0.S(x)=1−, поэтомуf 0 (x)(f 0 (x))2 f (x)f 00 (x) 0 6 q < 1.|S (x)| 6 q < 1 ⇐⇒ (f 0 (x))2 3.5. СХОДИМОСТЬ МЕТОДА НЬЮТОНА49Но в силу того, что мы ищем корень уравнения f (x) = 0, существует такая окрестность, гдеS 0 (x) 6 q < 1, но в общем случае эта область будет мала, то есть нужно подбирать начальное приближение достаточно близко расположенным к корню.Теорема 3.2 (о сходимости метода Ньютона).
Пусть x∗ — простой вещественный корень уравненияf (x) = 0, а функция f (x) — дважды дифференцируема в некоторой окрестности Ur (x∗ ), причемпервая производная нигде не обращается в нуль.Тогда, следуя обозначениям0 < m1 =infx∈Ur (x∗ )|f 0 (x)|,M2 =|f 00 (x)|,supx∈Ur (x∗ )при выборе начального приближения x0 из той же окрестности Ur (x∗ ) такого, чтоM2 |x0 − x∗ |= q < 1,2m1итерационная последовательностьxk+1 = xk −f (xk ), k = 0, 1, . . .f 0 (xk )будет сходиться к x∗ , причем для погрешности на k-м шаге будет справедлива оценка:|xk − x∗ | 6 q 2k−1|x0 − x∗ |.(3.9)Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
