1626435587-51311eae4652e8ad616b5bdef025cbb3 (844239), страница 10
Текст из файла (страница 10)
3 ( ); стрелками обозначены вычисления функции (). Покажем, что предел последовательности { }существует и равен искомому корню * : (* ) = * . Чтобы убедиться в этом, заметим, что функция () реализует, уменьшая длину произвольного отрезка [, ] → [(), ()]минимум в 1/ раз в силу ограниченности производной |′ | ≤ . Приэтом корень * по определению отображается функцией () сам в себя. Следовательно, выбирая = 0 и = * , имеем | − * | → 0 при → ∞, т. е. → * , ч.
т. д.Оценим количество итераций, необходимых для получения приближённого значения корня с требуемой точностью . Будем полагатьфункцию () гладкой, а начальное приближение 0 достаточно точным, так что (0 ) ≈ (* )+′ (* ) (0 −* ). Учитывая, что (* ) = * ,получаем (1 − * ) ≈ (0 − * ) · ′ (* ), т. е. абсолютная погрешностьопределения искомого корня умножается на каждой итерации на величину |′ | ≤ < 1, откуда получаем оценку для числа итераций:сжимающее отоб-ражение≈log(0 /).− log |′ |(7)Сравнение (5) и (7) показывает, что метод простых итераций сходится быстрее метода деления отрезка пополам при условии |′ (* )| < 12 .Особенно быстрой будет сходимость при ′ (* ) = 0. Очевидно, чтопроведённое выше рассмотрение и оценка количества итераций (7) впоследнем случае будут неприменимы: при малых |′ (* )| в разложении (0 ) ≈ (* ) + ′ (* ) (0 − * ) в ряд Тейлора следует удерживатьчлены более высоких порядков.Заметим, что сформулированное вначале ограничение |′ | ≤ < 1является достаточным, но не необходимым условием сходимости итерационного процесса.
Для сходимости итераций достаточно, чтобы отображение уменьшало длину произвольного отрезка, один из концовкоторого совпадает с искомым корнем * , при этом производная ′46Y(а)y=0=xY(б)x)ϕ(x0x1x2 x*0 xnX(в)Yx*xn+1X(г)y=f(x)Yyϕ-1ϕ-1ϕ(x)=y=yx0x0x1x2 x*0 x* x3Xx2x1x0XРис. 3. (а) Метод простых итераций, (б) секторы сходимости, (в) итерациидля обратной функции, (г) использование корректирующего множителяможет принимать сколь угодно большие значения или даже вовсе несуществовать. Итерационный процесс будет сходиться при любом начальном приближении 0 , если график функции () лежит междупрямыми 1 = * + ( − * ) и 2 = * − ( − * ), где 0 < < 1 —некоторая постоянная (рис. 3 ( )).
На рисунке видно, что итерация+1 = ( ) из любой точки ( , ( )) внутри заштрихованных секторов улучшит приближение к корню: |+1 − * | < | − * |.Очевидно, многие функции не удовлетворяют даже более слабомуусловию, сформулированному в предыдущем абзаце. Покажем две модификации итерационного процесса, позволяющие расширить областьего применения.Первая возможность связана с переходом от функции к обратной функции −1 . В случае, если |′ ()| ≥ > 1, можно перейти кобратным функциям в уравнении () = , в результате получим ите-б47рационный процесс +1 = −1 ( ), который будет сходиться в силусоотношения (−1 )′ = 1/′ . Геометрический смысл итераций для обратной функции показан на рис.
3 ( ), стрелками обозначены вычисления функции −1 (). Производная ′ > 1, поэтому итерационныйпроцесс +1 = ( ) будет расходящимся. Для сходимости необходимо, по сути, двигаться в обратную сторону (ср. направление стрелок нарис. 3 ( ) и ( )), что и достигается переходом к вычислению обратнойфункции −1 ( ) вместо ( ). Итерационный процесс для обратныхфункций целесообразно использовать в случае, когда обратная функция −1 может быть относительно легко вычислена, а |′ (* )| ≫ 1.Другая модификация метода итераций может быть получена введением корректирующего множителя. Вместо уравнения = + () ≡() будем решать уравнение = − (), множество решений которого, очевидно, совпадает с множеством корней уравнения () = 0при условии ̸= 0.
Пусть функция () непрерывно дифференцируема, так что | ′ ()| < ∞. Производная ˜′ () = 1 − ′ () может бытьсделана сколь угодно малой в точке = * соответствующим выбором, что обеспечит сходимость итерационного процессавав+1 = − ( )(8)для любой гладкой функции (). Знак нужно выбирать равнымзнаку производной, а значение — по возможности ближе к обратномузначению производной 1/ ′ (* ). Геометрический смысл итерационногопроцесса (8) показан на рис. 3 ( ).Выход из цикла итераций можно осуществлять, проверяя условиемалости изменения на последней итерации: | − −1 | < , где —требуемая точность. Однако данная оценка может быть слишком грубой, особенно в случае |′ (* )| ≈ 1.
Для получения более точного критерия завершения итерационного процесса рассмотрим последовательность { }, сходящуюся к корню * , полагая 0 достаточно близким к* . Обозначая := * − , из +1 = − ( ) получаем(︀)︀+1 ≈ 1 − ′ (* ) ≡ ,(9)гт. е. итерации сходятся приблизительно как сумма геометрической прогрессии со знаменателем = ( − −1 )/(−1 − −2 ). Итерационныйпроцесс может быть остановлен, когда погрешность текущего приближения к корню не превосходит требуемой точности вычислений .Поскольку − −1 = −1 − ≈ / − , приходим к условию⃒⃒⃒ − −1 ⃒( − −1 )2⃒⃒=| | ≈ ⃒< .(10)1/ − 1 ⃒ |2−1 − − −2 |48Оценка для в левой части неравенства (10) может быть использована для повышения точности расчётов (сокращения числа итераций,необходимых для получения заданной точности).3.3. Метод НьютонаГеометрический смысл рассмотренного выше метода итераций состоит в приближении к искомому корню * по прямым с постояннымнаклоном (рис.
3 ( )). Скорость сходимости можно существенно повысить, положив () = 1/ ′ () с тем, чтобы наклон был равен производной функции () (рис. 4 ( )). При этом мы получим итерационныйпроцесс ( )+1 = − ′, = 0, 1, 2, . . . ,(11) ( )гаметод НьютонаНьютона — Рафсонаточноелинеаризованнойизвестный как, или. В выражении (11) полезно увидеть такжерешениезадачи () = 0 — это позволит нам впоследствии обобщить данный методна матричные и операторные уравнения.(б)0x*x2x1x0y=f(x)Yf(x)(а)y=YX0x*x3x2x1x0XРис.
4. (а) метод Ньютона, (б) метод секущихИсследуем скорость сходимости процесса (11) к корню * . Для этого предположим, как и раньше, что нам задано достаточно хорошееприближение , так что ( ) ≈ ′ (* ) ( − * ) + 12 ′′ (* ) ( − * )2 ,а ′ ( ) ≈ ′ (* ) + ′′ (* ) ( − * ). Вычитая * из обеих частей (11),имеем:+1 ≈ + ′ (* ) (− ) + 12 ′′ (* ) (− )21 ′′ (* ) 2≈− .
′ (* ) − ′′ (* )2 ′ (* ) 49(12)Сравнивая (12) с (9), легко заметить, что метод Ньютона обладает более высокимпо сравнению с методом итераций.Так, если в методе итераций погрешность убывала приблизительно вгеометрической прогрессии (+1 ≈ 1 ), то в методе Ньютона погрешность на каждом следующем шаге оказывается квадратично малапо сравнению с погрешностью на предыдущем шаге, +1 = 2 .Заметим, что выражение (12) допускает возможность расходящегося процесса |+1 | > | | при достаточно больших | |, тогда как придостаточно малых | | процесс монотонно сходится.
Другими словами,в методе Ньютона может существовать:в случае, если начальное приближение 0 лежит в области < 0 < ,так что * ∈ (, ), процесс (11) сходится к корню * , в противном случае итерации расходятся (либо сходятся к другому корню, отличномуот * и лежащему вне отрезка [, ]).порядком сходимостиобласть притяжения к корню3.4. Метод секущихРассмотренный в п.
3.3 метод Ньютона обладает вторым порядком сходимости, однако для его реализации необходимо вычисление накаждом шаге значения функции ( ) и её первой производной ′ ( ).Зачастую, однако, производная функции () неизвестна (например, () измеряется в эксперименте или является результатом численногорешения некоторой сложной задачи).
Кроме того, даже если имеетсявыражение, позволяющее вычислить ′ ( ), такое вычисление требуетдополнительного времени на каждом шаге, что может сделать болеевыгодным использование других методов.Например, вместо ′ () при вычислении корректирующего множителя = 1/ ′ () в (8) можно использовать оценки значения производной, полученные с использованием асимптотических разложений ()или вычисленные с помощью разделённой разности (см. п.
5.2) по результатам двух последних вычислений ():+1 = − ( ) − −1, ( ) − (−1 ) = 1, 2, . . .(13)двухшаговымИтерационный процесс (13) является: для нахожденияследующего приближения +1 необходимо знать два предыдущих.Исследуем скорость сходимости процесса (13). Полагая и −1достаточно близкими к корню * и заменяя () ≈ ′ (* ) ( − * ) ++ 12 ′′ (* )( − * )2 , имеем:+1 ≈ − 1 − ,1 − · ( + −1 )50 ≡ * − , ≡ ′′ (* ).2 ′ (* )Удерживая члены не выше второго порядка по и −1 , получаем:+1 ≈ − −1 .(14)Аналогично (9) и (12), попробуем найти степенной закон убывания погрешности на каждой итерации.
Подставляя |+1 | = | | в (14),получаем два условия на показатели и : = 1, 2 − − 1 = 0.Для сходимостиитерационного процесса необходимо > 0, откуда√ = 21 (1 + 5) ≈ 1,618.Порядок процесса получился дробным — метод секущих (13) сходится быстрее (по числу шагов) метода простых итераций, но медленнееметода Ньютона. Заметим, однако, что в методе Ньютона на каждомшаге необходимо вычислять значение функции ( ) и её первой производной ′ ( ). Полагая, что для вычисления и ′ требуется приблизительно одинаковое количество арифметических операций, получим,что на каждые два вычисления функции приходится один шаг методаНьютона, дающий (приблизительно) удвоение числа значащих цифрпосле запятой для корня, |+1 | ∝ | |2 . Для сравнения, двукратноевычисление значения функции позволяет сделать два шага методом2секущих, что даёт улучшение точности |+2 | ∝ | | .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
