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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: '''Метод дихотомии''' - достаточно широко используемый метод поиска, известный также как '''метод бисекц...)
(Перенаправление на Методы дихотомии)
 
(9 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
'''Метод дихотомии''' - достаточно широко используемый метод поиска, известный также как '''метод бисекции''' или '''метод половинного деления'''. Во-первых, это один из простых способов поиска корней функции одного аргумента. Во-вторых, метод дихотомии применяется для нахождения значений действительно-значной функции, определяемому по какому-либо критерию (это может быть сравнение на [[минимум]], [[максимум]] или конкретное число).
+
#REDIRECT [[Методы дихотомии]]
-
 
+
-
Перед применением метода дихотомии для поиска корней функции необходимо отделить корни одним из известных способов, например, графическим методом. Отделение корней необходимо в случае, если неизвестно на каком отрезке нужно искать корень. Будем считать, что корень <tex>t</tex> функции <tex>f(x)=0</tex> отделён на отрезке <tex>[a,b]</tex>. Задача заключается в том, чтобы найти и уточнить этот корень методом половинного деления (дихотомии). Другими словами, требуется найти приближённое значение корня с заданной точностью <tex>\eps</tex>.
+
-
 
+
-
Пусть функция <tex>f</tex> непрерывна на отрезке <tex>[a,b], \; 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>4-e^x-2x^2=0</tex> на отрезке <tex>[0;\, 2]</tex> с точностью <tex>0.01</tex> методом дихотомии. Искомый корень <tex>x \approx 0.88281</tex>.
+
-
 
+
-
Промежуточные вычисления представлены в таблице ниже.
+
-
 
+
-
n a_n b_n c_n |b_n-c_n|
+
-
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
+
-
 
+
-
 
+
-
'''''Однопараметрическая оптимизация''''' (поиск экстремумов функций одной переменной) является самостоятельной и часто встречаемой задачей. Кроме того, к ней сводится гораздо более сложная задача - поиск экстремума функции многих переменных.
+
-
 
+
-
Рассмотрим метод дихотомии как простейший однопараметрический метод безусловной оптимизации. Данный метод является методом прямого поиска. В нем при поиске экстремума целевой функции используются только вычисленные значения целевой функции.
+
-
 
+
-
Дана функция <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>.
+
-
 
+
-
Запишем словесный алгоритм метода.
+
-
 
+
-
1) На каждом шаге процесса поиска делим отрезок <tex>[a,b]</tex> пополам, <tex>x=\frac {a+b}{2}</tex> - координата середины отрезка <tex>[a,b]</tex>.
+
-
 
+
-
2) Вычисляем значение функции <tex>F(x)</tex> в окрестности <tex>\pm \varepsilon</tex> вычисленной точки <tex>x</tex>, т.е.
+
-
 
+
-
 
+
-
<tex>F_1=F(x-\varepsilon), \\ F_2=F(x+\varepsilon).</tex>
+
-
 
+
-
3) Сравниваем <tex>F_1</tex> и <tex>F_2</tex> и отбрасываем одну из половинок отрезка <tex>[a,b]</tex> (рис. 9.1).
+
-
 
+
-
При поиске минимума:
+
-
 
+
-
Если <tex>F_1<F_2</tex>, то отбрасываем отрезок <tex>[x,b]</tex>, тогда <tex>b=x</tex>. (рис. 9.1.а)
+
-
 
+
-
Иначе отбрасываем отрезок <tex>[a,x]</tex>, тогда <tex>a=x</tex>. (рис. 9.1.б)
+
-
 
+
-
При поиске максимума:
+
-
 
+
-
Если <tex>F_1<F_2</tex>, то отбрасываем отрезок <tex>[a,x]</tex>, тогда <tex>a=x</tex>.
+
-
 
+
-
Иначе отбрасываем отрезок <tex>[x,b]</tex>, тогда <tex>b=x</tex>.
+
-
 
+
-
4) Деление отрезка <tex>[a,b]</tex> продолжается, пока его длина не станет меньше заданной точности <tex>\varepsilon</tex>, т.е. <tex>|b-a| \le \varepsilon</tex>.
+
-
 
+
-
 
+
-
 
+
-
Рис. 9.1. Поиск экстремума функции <tex>F(x)</tex> методом дихотомии
+
-
 
+
-
Схема алгоритма метода дихотомии представлена на рис 9.2.
+
-
 
+
-
На рис 9.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> в этой точке.
+
-
 
+
-
 
+
-
 
+
-
Рис. 9.2. Схема алгоритма метода дихотомии
+
-
 
+
-
 
+
-
Метод хорд
+
-
 
+
-
'''Метод хорд''' (способ пропорциональных частей) — численный метод уточнения корня трансцендентного уравнения.
+
-
Метод основан на замене функции <tex>f(x)</tex> на каждом шаге поиска хордой, пересечение которой с осью <tex>Х</tex> дает приближение корня.
+
-
 
+
-
При этом в процессе поиска семейство хорд может строиться:
+
-
 
+
-
а) при фиксированном левом конце хорд, т.е. <tex>z=a</tex>, тогда начальная точка <tex>x_0=b</tex> (рис. 4.10а);
+
-
 
+
-
б) при фиксированном правом конце хорд, т.е. <tex>z=b</tex>, тогда начальная точка <tex>x_0=a</tex> (рис. 4.10б);
+
-
 
+
-
 
+
-
 
+
-
Рис. 4.10.
+
-
 
+
-
В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:
+
-
 
+
-
для случая а):
+
-
 
+
-
<tex>x_{n+1}=x_n - \frac{f(x_n)}{f(x_n)-f(a)} (x_n - a);</tex> (4.11)
+
-
 
+
-
для случая б):
+
-
<tex>x_{n+1}=x_n - \frac{f(x_n)}{f(x_n)-f(b)} (x_n - b);</tex> (4.12)
+
-
 
+
-
Процесс поиска продолжается до тех пор, пока не выполнится условие
+
-
<tex>|x_{n+1}–x_n| \le \varepsilon </tex> или <tex>| h| \le \varepsilon </tex>. (4.13)
+
-
 
+
-
Метод обеспечивает быструю сходимость, если <tex>f(z)\cdot f''(z) > 0</tex>, т.е. хорды фиксируются в том конце интервала <tex>[a,b]</tex>, где знаки функции <tex>f(z)</tex> и ее кривизны <tex>f"(z)</tex> совпадают.
+
-
 
+
-
Схема алгоритма уточнения корня методом хорд представлена на рис. 4.11.
+
-
 
+
-
 
+
-
 
+
-
Схема алгоритма уточнения корня методом хорд
+
-
 
+
-
Рис. 4.11. Схема алгоритма уточнения корня методом хорд
+
-
 
+
-
 
+
-
 
+
-
Этот метод позволяет исключать в точности половину интервала на каждой итерации.
+
-
Приведем описание поисковой процедуры, ориентированной на нахождение точки минимума функции <tex>f(x)</tex> в интервале <tex>(a,b)</tex>.
+
-
 
+
-
1. Шаг1. Положить <tex>x_m=(a+b)/2</tex> и <tex>L=b-a</tex>.
+
-
Вычислить значение <tex>f(x_m)</tex>.
+
-
2. Шаг2. Положить <tex>x_1=a+L/4</tex> и <tex>x_2=b-L/4</tex>.
+
-
Можно заметить,что точки <tex>x_1,\; x_m,\; x_2</tex> делят интервал <tex>(a,b)</tex> на четыре равные части.
+
-
Вычислить значения <tex>f(x_1)</tex> и <tex>f(x_2)</tex>.
+
-
3. Шаг3. Сравнить <tex>f(x_1)</tex> и <tex>f(x_2)</tex>.
+
-
* если <tex>f(x_1)\le f(x_m)</tex>, исключить интервал <tex>(x_m,b)<tex>, положив <tex>b=x_m</tex>.
+
-
Средней точкой нового интервала поиска становится точка <tex>x_1</tex>.
+
-
Следовательно, необходимо положить <tex>x_m=x_1</tex>. Перейти к шагу 5.
+
-
* если <tex>f(x_1)\me f(x_m)</tex>, то перейти к шагу 4.
+
-
4. Шаг4. Сравнить <tex>f(x_2)</tex> и <tex>f(x_m)</tex>.
+
-
* если <tex>f(x_2)&le f(x_m)</tex>, исключить интервал <tex>(a,x_m)</tex>, положив <tex>a=x_m</tex>.
+
-
Т.к. средней точкой нового интервала становится точка <tex>x_2</tex>, положить <tex>x_m=x_2</tex>.
+
-
Перейти к шагу 5.
+
-
* если <tex>f(x_2)>=(x_m)</tex>, исключить интервалы <tex>(a,x_1)</tex> и <tex>(x_2,b)</tex>.
+
-
Положить <tex>a=x_1</tex> и <tex>b=x_2</tex>. (Заметим, что <tex>x_m</tex> продолжает оставаться средней точкой нового интервала)
+
-
Перейти к шагу 5.
+
-
5. Шаг5. Вычислить <tex>L=b-a</tex>.
+
-
Если величина <tex>|L|</tex> мала, закончить поиск, в противном случае вернуться к шагу 2.
+

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

  1. REDIRECT Методы дихотомии
Источник — «http://www.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»