Участник:Александр Двойнев/Метод касательных. Метод секущих

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

< Участник:Александр Двойнев(Различия между версиями)
Перейти к: навигация, поиск
(→Введение)
 
(3 промежуточные версии не показаны)
Строка 1: Строка 1:
== Введение ==
== Введение ==
-
Пусть на отрезке <tex>[a,b]</tex> задана функция <tex>f(x)</tex>. Требуется найти корни уравнения
+
 
 +
Пусть задана функция <tex>f(x)</tex> действительного переменного. Требуется найти корни уравнения
{{eqno|1}}
{{eqno|1}}
::<tex>f(x)=0.</tex>
::<tex>f(x)=0.</tex>
Строка 7: Строка 8:
== Изложение метода ==
== Изложение метода ==
 +
 +
===Метод касательных (Ньютона-Рафсона)===
 +
 +
Пусть на отрезке <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>
 +
 +
=== Метод секущих ===
 +
 +
== Анализ метода и ошибок ==
== Анализ метода и ошибок ==
== Числовой пример ==
== Числовой пример ==
Строка 14: Строка 45:
* [[Практикум ММП ВМК, 4й курс, осень 2008|Практикум ММП ВМК, 4й курс, осень 2008]]
* [[Практикум ММП ВМК, 4й курс, осень 2008|Практикум ММП ВМК, 4й курс, осень 2008]]
== Список литературы ==
== Список литературы ==
-
*[http://mmphome.1gb.ru/index.php?pid=show&id=79 Численные методы. Конспект лекций]
+
*[http://mmphome.1gb.ru/index.php?pid=show&id=79 Н.В.Соснин. Численные методы. Конспект лекций (сост. Д.В.Ховратович, Е.А.Попов)]
*Самаский А.А., Гулин А.В. Численные Методы. Учеб. пособие для вузов. - М.:Наука, 1989.
*Самаский А.А., Гулин А.В. Численные Методы. Учеб. пособие для вузов. - М.:Наука, 1989.

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

Содержание

Введение

Пусть задана функция 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*).

Метод секущих

Анализ метода и ошибок

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

Рекомендации программисту

Заключение

Ссылки

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

Источник — «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%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._%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%81%D0%B5%D0%BA%D1%83%D1%89%D0%B8%D1%85»