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

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

< Участник:Александр Двойнев(Различия между версиями)
Перейти к: навигация, поиск
(Список литературы)
(Полностью удалено содержимое страницы)
 
(3 промежуточные версии не показаны)
Строка 1: Строка 1:
-
== Введение ==
 
-
Пусть задана функция <tex>f(x)</tex> действительного переменного. Требуется найти корни уравнения
 
-
{{eqno|1}}
 
-
::<tex>f(x)=0.</tex>
 
-
 
-
Задача нахождения корней уравнения {{eqref|1}} обычно решается в 2 этапа. На первом этапе проводится отделение корней, т.е. выделение отрезков, содержащих только один корень. На втором этапе, используя начальное приближение, строится итерационный процесс, позволяющий уточнить значение отыскиваемого корня.
 
-
 
-
== Изложение метода ==
 
-
 
-
===Метод касательных (Ньютона-Рафсона)===
 
-
 
-
Пусть на отрезке <tex>[a,b]</tex> существует единственный корень уравнения {{eqref|1}}: <tex>x*</tex>
 
-
{{eqno|2}}
 
-
::<tex>f(x*)=0</tex>,
 
-
а <tex>f'(x)</tex> существует, непрерывна и отлична от нуля на <tex>[a,b]</tex>. Перепишем {{eqref|2}} следующим образом:
 
-
::<tex>f(x^k+(x*-x^k))=0</tex>
 
-
и применим к этому выражению [[формула Лагранжа|формулу Лагранжа]]:
 
-
::<tex>f(x^k)+f'(\bar{x})(x*-x^k)=0, \;\bar{x} \in [a,b].</tex>
 
-
Заменим <tex> \bar x</tex> на <tex>x^k</tex>, а <tex>x*</tex> - на <tex>x^{k+1}</tex> и получим формулу итерационного процесса:
 
-
::<tex>f(x^k)+f'(x^k)(x^{k+1}-x^k)=0.</tex>
 
-
Выразим отсюда <tex>x^{k+1}</tex>:
 
-
{{eqno|3}}
 
-
::<tex>x^{k+1}=x^k-\frac{f(x^k)}{f'(x^k)}.</tex>
 
-
 
-
Метод касательных имеет (когда сходится) квадратичную скорость сходимости: <tex>|x^{k+1}-x*|=O((x^k-x*)^2).</tex>
 
-
 
-
===Модифицированный метод касательных===
 
-
 
-
Если мы хотим избежать вычисления производной на каждом шаге, то можно взять <tex> f'(x^0)</tex> вместо <tex>f'(x),</tex> где <tex>x^0</tex> - начальное приближение:
 
-
::<tex>x^{k+1}=x^k-\frac{f(x^k)}{f'(x^0)}.</tex>
 
-
В отличие от обычного метода касательных, в модифицированном методе предоставляется меньше требований к выбору начального приближения, а так же гарантировано отсутствие деления на ноль, если <tex>f'(x^0) \ne 0.</tex>
 
-
 
-
Однако модифицированный метод имеет один существенный недостаток: линейную скорость сходимости: <tex>|x^{k+1}-x*|=O(x^k-x*).</tex>
 
-
 
-
=== Геометрическая интерпретация===
 
-
 
-
[[Изображение:kasat.jpg|thumb|200px|Метод касательных]]
 
-
Метод Ньютона-Рафсона называют также методом касательных, т.к. новое приближение <tex>x^{k+1}</tex> является абсциссой точки пересечения касательной, проведенной в точке <tex>(x^k,f(x^k))</tex> к графику функции <tex>f(x)</tex>, с осью ОХ.
 
-
 
-
== Сходимость метода ==
 
-
 
-
Заметим, что метод касательных является частным случаем [[Метод простых итераций|метода простых итераций]]
 
-
::<tex>x^{k+1}=g(x^k),\; k=0,1,\ldots,</tex>
 
-
для которого
 
-
{{eqno|4}}
 
-
::<tex>g(x)=x-\frac{f(x)}{f'(x)}.</tex>
 
-
 
-
[[Метод простых итераций]] сходится тогда и только тогда, когда
 
-
::<tex>|g'(x)|\le q < 1,</tex>
 
-
 
-
Подставим в последнее условие выражение для g(x) {{eqref|4}} и получим условие сходимости метода касательных:
 
-
::<tex>\left|\frac{f(x)f''(x)}{(f'(x))^2}\right| \le q < 1.</tex>
 
-
 
-
Сформулируем теорему о квадратичной скорости сходимости метода касательных:
 
-
 
-
'''Теорема.''' Пусть <tex>x*</tex> - простой вещественный корень уравнения <tex>f(x) = 0</tex>, а функция <tex>f(x)</tex> - дважды дифференцируема в некоторой окрестности <tex>U_r(x*)</tex>, причем первая произодная нигде не обращается в нуль.
 
-
 
-
Тогда, следуя обозначениям
 
-
::<tex>0 < m_1 = \;\inf_{x\in U_r(x*)}|f'(x)|,\;\; M_2 = \;\sup_{x\in U_r(x*)}|f''(x)|</tex>,
 
-
при выборе начального приближения <tex>x^0</tex> из той же окрестности <tex>U_r(x^*)</tex> такого, что
 
-
::<tex>\frac{M_2|x^0 - x*|}{2m_1} = q < 1</tex>,
 
-
итерационная последовательность
 
-
::<tex>x^{k+1} = x^k - \frac{f(x^k)}{f'(x^k)},\; k = 0,1,\ldots</tex>
 
-
будет сходиться к <tex>x*</tex>, причем для погрешности на k-м шаге буддет справедлива оценка:
 
-
::<tex>|x^k - x*| \le q^{2^k - 1}|x^0 - x*|.</tex>
 
-
 
-
== Числовой пример ==
 
-
 
-
[[Изображение: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|}}-->
 

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

Личные инструменты