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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: == Введение == Пусть задана функция <tex>f(x)</tex> действительного переменного. Требуется найти корни уравн...)
Текущая версия (16:05, 12 февраля 2015) (править) (отменить)
м (→Числовой пример: Ссылка на формулу)
 
(4 промежуточные версии не показаны)
Строка 1: Строка 1:
== Введение ==
== Введение ==
-
Пусть задана функция <tex>f(x)</tex> действительного переменного. Требуется найти корни уравнения
+
Пусть задана функция <tex>f(x)</tex> действительного переменного. Требуется найти корни уравнения
{{eqno|1}}
{{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)</tex> разностным приближением:
-
::<tex>f'(x^k) \approx \frac{f(x^k)-f(x^{k-1})}{x^k-x^{k-1}}.</tex>
+
:: <tex>f'(x^k) \approx \frac{f(x^k)-f(x^{k-1})}{x^k-x^{k-1}}.</tex>
В результате получим формулу итерационного процесса:
В результате получим формулу итерационного процесса:
-
{{eqno|1}}
+
{{eqno|2}}
-
::<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>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>x^{k+1}</tex> определяется двумя предыдущими итерациями <tex>x^k</tex> и <tex>x^{k-1}.</tex> В методе {{eqref|1}} необходимо задавать ''два'' начальных приближения <tex>x^0</tex> и <tex>x^1.</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>
Скорость сходимости метода будет ''линейной'': <tex>|x^{k+1}-x*|=O(k^k-x*).</tex>
Скорость сходимости метода будет ''линейной'': <tex>|x^{k+1}-x*|=O(k^k-x*).</tex>
-
===Геометрическая интерпретация===
+
=== Геометрическая интерпретация ===
[[Изображение:sekush.JPG|thumb|200px|Метод секущих]]
[[Изображение:sekush.JPG|thumb|200px|Метод секущих]]
-
Заметим, что уравнение для секущей, проходящей через точки <tex>M'(x^{k-1},f(x^{k-1}))</tex> и <tex>M''(x^k,f(x^k))</tex>, будет выглядть так:
+
Заметим, что уравнение для секущей, проходящей через точки <tex>M'(x^{k-1},f(x^{k-1}))</tex> и <tex>M''(x^k, f(x^k))</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>\frac{y-f(x^k)}{x-x^k}=\frac{f(x^k)-f(x^{k-1})}{x^k-x^{k-1}}.</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>y=0</tex> и <tex>x=x^{k+1},</tex> можно получить формулу {{eqref|2}}. Это означает, что <tex>x^{k+1}</tex> — это абсцисса точки пересечения нашей секущей с осью ОХ. Иначе говоря, на отрезке <tex>[x^{k-1},x^k]</tex> функция <tex>f(x)</tex> интерполируется многочленом первой степени и за очередное приближение <tex>x^{k+1}</tex> принимается корень этого многочлена.
== Числовой пример ==
== Числовой пример ==
 +
 +
[[Изображение:kasatex.jpg|thumb|200px|График функции]]
 +
Рассмотрим функцию <tex>f(x)= cos(x)-x+1.</tex> С помощью метода {{eqref|2}} найдем корень уравнения <tex>f(x)=0.</tex> Исходный код программы, ищущей корень уравнения методом секущих, выложен в разделе «'''Файлы'''».
 +
 +
Возьмём в качестве начальных приближений <tex>x^0=4, \; x^1=3</tex> и точность <tex>\eps=10^{-6}.</tex> В итоге за 8 итераций получим корень <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> в результате итерации стало меньше заданого ε.
 +
 
 +
=== Ошибки округления ===
 +
 
 +
В методе секущих, как и в других итерационных методах решения уравнений, ошибка округления ''не накапливается''. Общая ошибка округления равна ошибке, возникшей в последней итерации, и не зависит от арифметических операций, выполнявшихся в предыдущих итерациях.
 +
 
 +
== Файлы ==
 +
 
 +
[[Медиа:Sekush.zip | sekush.zip]]
 +
 
== Ссылки ==
== Ссылки ==
* [[Практикум ММП ВМК, 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.
-
{{Stub|}}
+
[[Категория:Численные методы одномерной оптимизации]]

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

Содержание

Введение

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

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

(2)
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}, можно получить формулу (2). Это означает, что x^{k+1} — это абсцисса точки пересечения нашей секущей с осью ОХ. Иначе говоря, на отрезке [x^{k-1},x^k] функция f(x) интерполируется многочленом первой степени и за очередное приближение x^{k+1} принимается корень этого многочлена.

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

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

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

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

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

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

Как правило, берут один из следующих критериев останова:

  1. f(x^k)< \eps — значение функции на данной итерации стало меньше заданого ε.
  2. \left|x^k-x^{k-1}\right| < \eps — изменение хk в результате итерации стало меньше заданого ε.

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

В методе секущих, как и в других итерационных методах решения уравнений, ошибка округления не накапливается. Общая ошибка округления равна ошибке, возникшей в последней итерации, и не зависит от арифметических операций, выполнявшихся в предыдущих итерациях.

Файлы

sekush.zip

Ссылки

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

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%81%D0%B5%D0%BA%D1%83%D1%89%D0%B8%D1%85»
Личные инструменты