|
|
| (2 промежуточные версии не показаны) |
| Строка 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|}}-->
| |
