Метод дихотомии

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Метод дихотомии как метод оптимизации)
(Перенаправление на Методы дихотомии)
 
(1 промежуточная версия не показана)
Строка 1: Строка 1:
-
== Введение ==
+
#REDIRECT [[Методы дихотомии]]
-
 
+
-
'''Метод дихотомии''' - достаточно широко используемый метод поиска, известный также как '''метод бисекции''' или '''метод половинного деления'''.
+
-
#Во-первых, это один из простых способов поиска корней функции одного аргумента.
+
-
#Во-вторых, метод дихотомии применяется для нахождения значений действительно-значной функции, определяемому по какому-либо критерию (это может быть сравнение на минимум, максимум или конкретное число).
+
-
 
+
-
== Метод дихотомии как метод поиска корней функции ==
+
-
=== Изложение метода ===
+
-
Перед применением метода дихотомии для поиска корней функции необходимо отделить корни одним из известных способов, например, графическим методом. Отделение корней необходимо в случае, если неизвестно на каком отрезке нужно искать корень.
+
-
 
+
-
Будем считать, что корень <tex>t</tex> функции <tex>f(x)=0</tex> отделён на отрезке <tex>[a,b]</tex>. Задача заключается в том, чтобы найти и уточнить этот корень методом половинного деления (дихотомии). Другими словами, требуется найти приближённое значение корня с заданной точностью <tex>\eps</tex>.
+
-
 
+
-
Пусть функция <tex>f</tex> непрерывна на отрезке <tex>[a,b]</tex>,
+
-
::<tex>f(a)\cdot f(b)<0, \; \eps=0,01</tex> и <tex>t\in[a,b]</tex> - единственный корень уравнения <tex>f(x)=0, \; a\le t\le b</tex>.
+
-
 
+
-
(Мы не рассматриваем случай, когда корней на отрезке <tex>[a,b]</tex> несколько, то есть более одного. В качестве <tex>\eps</tex> можно взять и другое достаточно малое положительное число, например, <tex>0,001</tex>.)
+
-
 
+
-
Поделим отрезок <tex>[a,b]</tex> пополам. Получим точку <tex>c= \frac {a+b}{2}, \; a<c<b</tex> и два отрезка <tex>[a,c], \; [c,b]</tex>.
+
-
*Если <tex>f(c)=0</tex>, то корень <tex>t</tex> найден (<tex>t=c</tex>).
+
-
*Если нет, то из двух полученных отрезков <tex>[a,c]</tex> и <tex>[c,b]</tex> надо выбрать один <tex>[a_1;b_1]</tex> такой, что <tex>f(a_1)\cdot f(b_1)<0</tex>, то есть
+
-
**<tex>[a_1;b_1] = [a,c]</tex>, если <tex>f(a)\cdot f(c)<0</tex> или
+
-
**<tex>[a_1;b_1] = [c,b]</tex>, если <tex>f(c)\cdot f(b)<0</tex>.
+
-
:Новый отрезок <tex>[a_1;b_1]</tex> делим пополам. Получаем середину этого отрезка <tex>c_1=\frac {a_1+b_1}{2}</tex> и так далее.
+
-
 
+
-
Для того, чтобы найти приближённое значение корня с точностью до <tex> \eps >0</tex>, необходимо остановить процесс половинного деления на таком шаге <tex>n</tex>, на котором <tex>|b_n-c_n|<\eps</tex> и вычислить <tex>x=\frac {a_n+b_n}{2}</tex>. Тогда можно взять <tex>t\approx x</tex>.
+
-
 
+
-
=== Реализация метода на С++ и числовой пример ===
+
-
Решим уравнение <tex>4-e^x-2x^2=0</tex> методом дихотомии. Графическим методом находим отрезок <tex>[0; \,1]</tex>, которому принадлежит искомый корень. Так как <tex>f(0)\cdot f(1)<0</tex>, то принимаем <tex>a=0, \; b=1</tex>.
+
-
 
+
-
Ниже приведен пример программы на [[C++|Си++]], которая решает поставленную задачу.
+
-
 
+
-
'''Программа 1. Корень уравнения'''
+
-
 
+
-
<source lang="cpp">#include <iostream>
+
-
#include <cmath>
+
-
using namespace std;
+
-
const double epsilon = 1e-2;
+
-
 
+
-
double f(double x)
+
-
{
+
-
return 4- exp(x) - 2*x^2;
+
-
}
+
-
 
+
-
int main()
+
-
{
+
-
double a, b, c;
+
-
a = 0;
+
-
b = 2;
+
-
while (b - a > epsilon){
+
-
c = (a + b) / 2;
+
-
if(f(b) * f(c) < 0)
+
-
a = c;
+
-
else
+
-
b = c;
+
-
}
+
-
cout << (a + b) / 2 << endl;
+
-
return 0;
+
-
}</source>
+
-
 
+
-
Искомый корень <tex>x \approx 0.88281</tex>. Вычисления проводились с точностью <tex>0.01</tex>.
+
-
 
+
-
Промежуточные вычисления представлены в таблице ниже.
+
-
<center>
+
-
{| class="standard"
+
-
!n
+
-
!a<sub>n</sub>
+
-
!b<sub>n</sub>
+
-
!c<sub>n</sub>
+
-
!|b<sub>n</sub>-c<sub>n</sub>
+
-
|-
+
-
!1
+
-
|0
+
-
|1
+
-
|0.5
+
-
|0.5
+
-
|-
+
-
!2
+
-
|0.5
+
-
|1
+
-
|0.75
+
-
|0.25
+
-
|-
+
-
!3
+
-
|0.75
+
-
|1
+
-
|0.875
+
-
|0.125
+
-
|-
+
-
!4
+
-
|0.875
+
-
|1
+
-
|0.9375
+
-
|0.0625
+
-
|-
+
-
!5
+
-
|0.875
+
-
|0.9375
+
-
|0.90625
+
-
|0.03125
+
-
|-
+
-
!6
+
-
|0.875
+
-
|0.90625
+
-
|0.890625
+
-
|0.015625
+
-
|-
+
-
!7
+
-
|0.875
+
-
|0.890625
+
-
|0.8828125
+
-
|0.0078125
+
-
|}
+
-
</center>
+
-
 
+
-
== Метод дихотомии как метод оптимизации ==
+
-
[[Изображение:09 01.gif|frame|Рис. 1. Поиск экстремума функции <tex>F(x)</tex> методом дихотомии]]
+
-
[[Изображение:09 02.gif|frame|Рис. 2. Схема алгоритма метода дихотомии]]
+
-
 
+
-
'''''Однопараметрическая оптимизация''''' (поиск экстремумов функций одной переменной) является самостоятельной и часто встречаемой задачей. Кроме того, к ней сводится гораздо более сложная задача - поиск экстремума функции многих переменных.
+
-
 
+
-
Рассмотрим метод дихотомии как простейший однопараметрический метод безусловной оптимизации. Данный метод является ''методом прямого поиска''. В нем при поиске экстремума целевой функции используются только вычисленные значения целевой функции.
+
-
 
+
-
Дана функция <tex>F(x)</tex>. Необходимо найти <tex>\overline{x}</tex>, доставляющий минимум (или максимум) функции <tex>F(x)</tex> на интервале <tex>[a,b]</tex> с заданной точностью <tex>\varepsilon</tex>, т.е. найти
+
-
::<tex>\overline{x} = \arg \min F(x), \; \overline{x} \in [a,b]</tex>.
+
-
 
+
-
Запишем словесный алгоритм метода.
+
-
 
+
-
#На каждом шаге процесса поиска делим отрезок <tex>[a,b]</tex> пополам, <tex>x=\frac {a+b}{2}</tex> - координата середины отрезка <tex>[a,b]</tex>.
+
-
#Вычисляем значение функции <tex>F(x)</tex> в окрестности <tex>\pm \varepsilon</tex> вычисленной точки <tex>x</tex>, т.е. <br
+
-
\> <tex>F_1=F(x-\varepsilon),\; F_2=F(x+\varepsilon)</tex>.
+
-
#Сравниваем <tex>F_1</tex> и <tex>F_2</tex> и отбрасываем одну из половинок отрезка <tex>[a,b]</tex> (рис. 1).
+
-
#*При поиске минимума:
+
-
#**Если <tex>F_1<F_2</tex>, то отбрасываем отрезок <tex>[x,b]</tex>, тогда <tex>b=x</tex>. (рис. 1.а)
+
-
#**Иначе отбрасываем отрезок <tex>[a,x]</tex>, тогда <tex>a=x</tex>. (рис. 1.б)
+
-
#*При поиске максимума:
+
-
#**Если <tex>F_1<F_2</tex>, то отбрасываем отрезок <tex>[a,x]</tex>, тогда <tex>a=x</tex>.
+
-
#**Иначе отбрасываем отрезок <tex>[x,b]</tex>, тогда <tex>b=x</tex>.
+
-
#Деление отрезка <tex>[a,b]</tex> продолжается, пока его длина не станет меньше заданной точности <tex>\varepsilon</tex>, т.е. <tex>|b-a| \le \varepsilon</tex>.
+
-
 
+
-
 
+
-
Схема алгоритма метода дихотомии представлена на рис 2.
+
-
 
+
-
На рис 2:
+
-
::<tex>c</tex>- константа,
+
-
::<tex>c =\begin{cases} \quad 1 , \quad (min \; F(x)), \\-1, \quad (max \; F(x)). \end{cases}</tex>
+
-
 
+
-
При выводе <tex>x</tex> – координата точки, в которой функция <tex>F(x)</tex> имеет минимум (или максимум), <tex>F_M</tex> – значение функции <tex>F(x)</tex> в этой точке.
+
-
 
+
-
== Список литературы ==
+
-
* ''А.А.Самарский, А.В.Гулин.''&nbsp; Численные методы. Москва «Наука», 1989.
+
-
* http://www.mgopu.ru/PVU/2.1/nummethods/Chapter1.htm
+
-
* http://www.intuit.ru/department/calculate/calcmathbase/1/4.html
+
-
 
+
-
== См. также ==
+
-
* [[Практикум ММП ВМК, 4й курс, осень 2008]]
+
-
 
+
-
[[Категория:Учебные задачи]]
+

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

  1. REDIRECT Методы дихотомии
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B4%D0%B8%D1%85%D0%BE%D1%82%D0%BE%D0%BC%D0%B8%D0%B8»
Личные инструменты