Метод касательных (Ньютона-Рафсона)

Пусть на отрезке $[a,b]$ существует единственный корень уравнения (1): $x*$

(2)

$f(x*)=0$ ,

а $f'(x)$ существует, непрерывна и отлична от нуля на $[a,b]$ . Перепишем (2) следующим образом:

$f(x^k+(x*-x^k))=0$

и применим к этому выражению формулу Лагранжа:

$f(x^k)+f'(\bar{x})(x*-x^k)=0, \;\bar{x} \in [a,b].$

Заменим $\bar x$ на $x^k$ , а $x*$ - на $x^{k+1}$ и получим формулу итерационного процесса:

$f(x^k)+f'(x^k)(x^{k+1}-x^k)=0.$

Выразим отсюда $x^{k+1}$ :

(3)

$x^{k+1}=x^k-\frac{f(x^k)}{f'(x^k)}.$

Метод касательных имеет (когда сходится) квадратичную скорость сходимости: $|x^{k+1}-x*|=O((x^k-x*)^2).$

Модифицированный метод касательных

Если мы хотим избежать вычисления производной на каждом шаге, то можно взять $f'(x^0)$ вместо $f'(x),$ где $x^0$ - начальное приближение:

$x^{k+1}=x^k-\frac{f(x^k)}{f'(x^0)}.$

В отличие от обычного метода касательных, в модифицированном методе предоставляется меньше требований к выбору начального приближения, а так же гарантировано отсутствие деления на ноль, если $f'(x^0) \ne 0.$

Однако модифицированный метод имеет один существенный недостаток: линейную скорость сходимости: $|x^{k+1}-x*|=O(x^k-x*).$

Геометрическая интерпретация

Метод касательных

Метод Ньютона-Рафсона называют также методом касательных, т.к. новое приближение $x^{k+1}$ является абсциссой точки пересечения касательной, проведенной в точке $(x^k,f(x^k))$ к графику функции $f(x)$ , с осью ОХ.

Сходимость метода

Заметим, что метод касательных является частным случаем метода простых итераций

$x^{k+1}=g(x^k),\; k=0,1,\ldots,$

для которого

(4)

$g(x)=x-\frac{f(x)}{f'(x)}.$

Метод простых итераций сходится тогда и только тогда, когда

$|g'(x)|\le q < 1,$

Подставим в последнее условие выражение для g(x) (4) и получим условие сходимости метода касательных:

$\left|\frac{f(x)f''(x)}{(f'(x))^2}\right| \le q < 1.$

Сформулируем теорему о квадратичной скорости сходимости метода касательных:

Теорема. Пусть $x*$ - простой вещественный корень уравнения $f(x) = 0$ , а функция $f(x)$ - дважды дифференцируема в некоторой окрестности $U_r(x*)$ , причем первая произодная нигде не обращается в нуль.

Тогда, следуя обозначениям

$0 < m_1 = \;\inf_{x\in U_r(x*)}|f'(x)|,\;\; M_2 = \;\sup_{x\in U_r(x*)}|f''(x)|$ ,

при выборе начального приближения $x^0$ из той же окрестности $U_r(x^*)$ такого, что

$\frac{M_2|x^0 - x*|}{2m_1} = q < 1$ ,

итерационная последовательность

$x^{k+1} = x^k - \frac{f(x^k)}{f'(x^k)},\; k = 0,1,\ldots$

будет сходиться к $x*$ , причем для погрешности на k-м шаге буддет справедлива оценка:

$|x^k - x*| \le q^{2^k - 1}|x^0 - x*|.$

Числовой пример

График функции

Рассмотрим функцию $f(x)= cos(x)-x+1.$ С помощью метода (3) найдем корень уравнения $f(x)=0.$ Исходный код программы, ищущей корень уравнения методом касательных, выложен в разделе "Файлы".

Возьмём в качестве начального приближения $x^0=3$ и точность $\eps=10^{-6}.$ В итоге за 5 итераций получим корень $x* \approx 1.283429.$

Заключение

Метод касательных сходится быстрее, чем многие другие итерационные методы. Однако, главный недостаток метода - необходимость вычисления производной. Поэтому к функциям, заданным таблично и к функциям, у которых в некоторых точках отсутствует производная, метод неприменим.

Файлы

kasat.zip

Ссылки

Список литературы

Н.В.Соснин. Численные методы. Конспект лекций (сост. Д.В.Ховратович, Е.А.Попов)
Самаский А.А., Гулин А.В. Численные Методы. Учеб. пособие для вузов. - М.:Наука, 1989.
Д. Маккракен. Численные методы и программирование на ФОРТРАНе. - М.:Мир, 1977.

Это незавершённая статья. Вы поможете проекту, исправив и дополнив её.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BA%D0%B0%D1%81%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%28%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0-%D0%A0%D0%B0%D1%84%D1%81%D0%BE%D0%BD%D0%B0%29»

Категория: Незавершённые статьи

@@ Строка 67: / Строка 67: @@
 == Числовой пример ==
+[[Изображение:kasatex.jpg|thumb|200px|График функции]]
+Рассмотрим функцию <tex>f(x)= cos(x)-x+1.</tex> С помощью метода {{eqref|3}} найдем корень уравнения <tex>f(x)=0.</tex> Исходный код программы, ищущей корень уравнения методом касательных, выложен в разделе "'''Файлы'''".
+Возьмём в качестве начального приближения <tex>x^0=3</tex> и точность <tex>\eps=10^{-6}.</tex> В итоге за 5 итераций получим корень <tex>x* \approx 1.283429.</tex>
 == Рекомендации программисту ==
+=== Критерий останова ===
+Как правило, берут один из следующих критериев останова:
+#<tex>f(x^k)< \eps</tex> - значение функции на данной итерации стало меньше заданого ε.
+#<tex>\left|x^k-x^{k-1}\right| < \eps</tex> - изменение х<sup>k</sup> в результате итерации стало меньше заданого ε.
+=== Ошибки округления ===
+В методе касательных, как и в других итерационных методах решения уравнений, ошибка округления ''не накапливается''. Общая ошибка округления равна ошибке, возникшей в последней итерации, и не зависит от арифметических операций, выполнявшихся в предыдущих итерациях.
 == Заключение ==
+Метод касательных сходится быстрее, чем многие другие итерационные методы. Однако, главный недостаток метода - необходимость вычисления производной. Поэтому к функциям, заданным таблично и к функциям, у которых в некоторых точках отсутствует производная, метод неприменим.
+== Файлы ==
+[[Media:Kasat.zip| kasat.zip]]
 == Ссылки ==
 * [[Практикум ММП ВМК, 4й курс, осень 2008|Практикум ММП ВМК, 4й курс, осень 2008]]
+* [[Метод секущих]]
 == Список литературы ==
 *[http://mmphome.1gb.ru/index.php?pid=show&id=79 Н.В.Соснин.  Численные методы. Конспект лекций (сост. Д.В.Ховратович, Е.А.Попов)]
 *Самаский А.А., Гулин А.В. Численные Методы. Учеб. пособие для вузов. - М.:Наука, 1989.
+*Д. Маккракен. Численные методы и программирование на ФОРТРАНе. - М.:Мир, 1977.
 {{Stub|}}

Метод касательных (Ньютона-Рафсона)

Материал из MachineLearning.

Текущая версия

Содержание

Введение

Изложение метода