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

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

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

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

Версия 14:35, 5 декабря 2008

Содержание

1 Введение
2 Изложение метода
- 2.1 Геометрическая интерпретация
3 Числовой пример
4 Рекомендации программисту
- 4.1 Критерий останова
- 4.2 Ошибки округления
5 Заключение
6 Файлы
7 Ссылки
8 Список литературы

Введение

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

(1)

$f(x)=0.$

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

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

Метод секущих получается из метода касательных заменой $f'(x^k)$ разностным приближением:

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

В результате получим формулу итерационного процесса:

(1)

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

Метод секущих является двухшаговым, то есть новое приближение $x^{k+1}$ определяется двумя предыдущими итерациями $x^k$ и $x^{k-1}.$ В методе (1) необходимо задавать два начальных приближения $x^0$ и $x^1.$

Скорость сходимости метода будет линейной: $|x^{k+1}-x*|=O(k^k-x*).$

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

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

Заметим, что уравнение для секущей, проходящей через точки $M'(x^{k-1},f(x^{k-1}))$ и $M''(x^k, f(x^k))$ , будет выглядть так:

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

Положив $y=0$ и $x=x^{k+1},$ можно получить формулу (1). Это означает, что $x^{k+1}$ — это абсцисса точки пересечения нашей секущей с осью ОХ. Иначе говоря, на отрезке $[x^{k-1},x^k]$ функция $f(x)$ интерполируется многочленом первой степени и за очередное приближение $x^{k+1}$ принимается корень этого многочлена.

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

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

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

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

Заключение

Файлы

sekush.zip

Ссылки

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

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

@@ Строка 1: / Строка 1: @@
 == Введение ==
 Пусть задана функция <tex>f(x)</tex> действительного переменного. Требуется найти корни уравнения
 {{eqno|1}}
-::<tex>f(x)=0.</tex>
+:: <tex>f(x)=0.</tex>
-Задача нахождения корней уравнения {{eqref|1}} обычно решается в 2 этапа. На первом этапе проводится отделение корней, т.е. выделение отрезков, содержащих только один корень. На втором этапе, используя начальное приближение, строится итерационный процесс, позволяющий уточнить значение отыскиваемого корня.
+Задача нахождения корней уравнения {{eqref|1}} обычно решается в 2 этапа. На первом этапе проводится отделение корней, то есть выделение отрезков, содержащих только один корень. На втором этапе, используя начальное приближение, строится итерационный процесс, позволяющий уточнить значение отыскиваемого корня.
 == Изложение метода ==
-===Метод касательных (Ньютона-Рафсона)===
+Метод секущих получается из [[Метод касательных (Ньютона-Рафсона)|метода касательных]] заменой <tex>f'(x^k)</tex> разностным приближением:
+:: <tex>f'(x^k) \approx \frac{f(x^k)-f(x^{k-1})}{x^k-x^{k-1}}.</tex>
+В результате получим формулу итерационного процесса:
+{{eqno|1}}
+:: <tex>x^{k+1}=x^k-\frac{x^k-x^{k-1}}{f(x^k)-f(x^{k-1})}f(x^k), \;k=1,2,\ldots</tex>
-Пусть на отрезке <tex>[a,b]</tex> существует единственный корень уравнения {{eqref|1}}: <tex>x*</tex>
+Метод секущих является ''двухшаговым'', то есть новое приближение <tex>x^{k+1}</tex> определяется двумя предыдущими итерациями <tex>x^k</tex> и <tex>x^{k-1}.</tex> В методе {{eqref|1}} необходимо задавать ''два'' начальных приближения <tex>x^0</tex> и <tex>x^1.</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>|x^{k+1}-x*|=O(k^k-x*).</tex>
-===Модифицированный метод касательных===
+=== Геометрическая интерпретация ===
+[[Изображение:sekush.JPG|thumb|200px|Метод секущих]]
-Если мы хотим избежать вычисления производной на каждом шаге, то можно взять <tex> f'(x^0)</tex> вместо <tex>f'(x),</tex> где <tex>x^0</tex> - начальное приближение:
+Заметим, что уравнение для секущей, проходящей через точки <tex>M'(x^{k-1},f(x^{k-1}))</tex> и <tex>M''(x^k, f(x^k))</tex>, будет выглядть так:
-::<tex>x^{k+1}=x^k-\frac{f(x^k)}{f'(x^0)}.</tex>
+:: <tex>\frac{y-f(x^k)}{x-x^k}=\frac{f(x^k)-f(x^{k-1})}{x^k-x^{k-1}}.</tex>
-В отличие от обычного метода касательных, в модифицированном методе предоставляется меньше требований к выбору начального приближения, а так же гарантировано отсутствие деления на ноль, если <tex>f'(x^0) \ne 0.</tex>
+Положив <tex>y=0</tex> и <tex>x=x^{k+1},</tex> можно получить формулу {{eqref|1}}. Это означает, что <tex>x^{k+1}</tex> — это абсцисса точки пересечения нашей секущей с осью ОХ. Иначе говоря, на отрезке <tex>[x^{k-1},x^k]</tex> функция <tex>f(x)</tex> интерполируется многочленом первой степени и за очередное приближение <tex>x^{k+1}</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>f(x)= cos(x)-x+1.</tex> С помощью метода {{eqref|1}} найдем корень уравнения <tex>f(x)=0.</tex> Исходный код программы, ищущей корень уравнения методом секущих, выложен в разделе «'''Файлы'''».
-Возьмём в качестве начального приближения <tex>x^0=3</tex> и точность <tex>\eps=10^{-6}.</tex> В итоге за 5 итераций получим корень <tex>x* \approx 1.283429.</tex>
+Возьмём в качестве начальных приближений <tex>x^0=4, x^1=3</tex> и точность <tex>\eps=10^{-6}.</tex> В итоге за 8 итераций получим корень <tex>x* \approx 1.283429.</tex>
 == Рекомендации программисту ==
@@ Строка 78: / Строка 37: @@
 Как правило, берут один из следующих критериев останова:
-#<tex>f(x^k)< \eps</tex> - значение функции на данной итерации стало меньше заданого ε.
+# <tex>f(x^k)< \eps</tex> — значение функции на данной итерации стало меньше заданого ε.
-#<tex>\left|x^k-x^{k-1}\right| < \eps</tex> - изменение х<sup>k</sup> в результате итерации стало меньше заданого ε.
+# <tex>\left|x^k-x^{k-1}\right| < \eps</tex> — изменение х<sup>k</sup> в результате итерации стало меньше заданого ε.
 === Ошибки округления ===
-В методе касательных, как и в других итерационных методах решения уравнений, ошибка округления ''не накапливается''. Общая ошибка округления равна ошибке, возникшей в последней итерации, и не зависит от арифметических операций, выполнявшихся в предыдущих итерациях.
+В методе секущих, как и в других итерационных методах решения уравнений, ошибка округления ''не накапливается''. Общая ошибка округления равна ошибке, возникшей в последней итерации, и не зависит от арифметических операций, выполнявшихся в предыдущих итерациях.
 == Заключение ==
-Метод касательных сходится быстрее, чем многие другие итерационные методы. Однако, главный недостаток метода - необходимость вычисления производной. Поэтому к функциям, заданным таблично и к функциям, у которых в некоторых токах отсутствует производная, метод неприменим.
 == Файлы ==
-[[Media:Kasat.zip| kasat.zip]]
+[[Медиа:Sekush.zip | sekush.zip]]
 == Ссылки ==
 * [[Практикум ММП ВМК, 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.
-*Д. Маккракен. Численные методы и программирование на ФОРТРАНе. - М.:Мир, 1977.
-<!--{{Stub|}}-->
+<!-- {{Stub|}} -->

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

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

Версия 14:35, 5 декабря 2008

Содержание

Введение

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

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

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

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

Критерий останова

Ошибки округления

Заключение

Файлы

Ссылки

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

Просмотры

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

Навигация

Поиск

Инструменты