Участник:Александр Двойнев/песочница

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

(Различия между версиями)

Перейти к: навигация, поиск

Версия 13:24, 4 декабря 2008

Содержание

1 Введение
2 Изложение метода
3 Сходимость метода
4 Числовой пример
5 Рекомендации программисту
6 Заключение
7 Ссылки
8 Список литературы

Введение

Пусть задана функция $f(x)$ действительного переменного. Требуется найти корни уравнения

(1)

$f(x)=0.$

Задача нахождения корней уравнения (1) обычно решается в 2 этапа. На первом этапе проводится отделение корней, т.е. выделение отрезков, содержащих только один корень. На втором этапе, используя начальное приближение, строится итерационный процесс, позволяющий уточнить значение отыскиваемого корня.

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

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

Пусть на отрезке $[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$

Заключение

Ссылки

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

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

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%90%D0%BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80_%D0%94%D0%B2%D0%BE%D0%B9%D0%BD%D0%B5%D0%B2/%D0%BF%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»

@@ Строка 68: / Строка 68: @@
 == Числовой пример ==
-Рассмотрим функцию <tex>f(x)=
+Рассмотрим функцию <tex>f(x)= cos(x)-x+1</tex>
 == Рекомендации программисту ==