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

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

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

Коликова Катя (Обсуждение | вклад)
(Новая: == Введение == '''Метод дихотомии''' - достаточно широко используемый метод поиска, известный также как '''...)
К следующему изменению →

Версия 18:33, 23 ноября 2008

Содержание

1 Введение
2 Метод дихотомии как метод поиска корней функции
- 2.1 Изложение метода
- 2.2 Реализация метода на С++ и числовой пример
3 Метод дихотомии как метод оптимизации
4 Список литературы
5 См. также

Введение

Метод дихотомии - достаточно широко используемый метод поиска, известный также как метод бисекции или метод половинного деления.

Во-первых, это один из простых способов поиска корней функции одного аргумента.
Во-вторых, метод дихотомии применяется для нахождения значений действительно-значной функции, определяемому по какому-либо критерию (это может быть сравнение на минимум, максимум или конкретное число).

Метод дихотомии как метод поиска корней функции

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

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

Будем считать, что корень $t$ функции $f(x)=0$ отделён на отрезке $[a,b]$ . Задача заключается в том, чтобы найти и уточнить этот корень методом половинного деления (дихотомии). Другими словами, требуется найти приближённое значение корня с заданной точностью $\eps$ .

Пусть функция $f$ непрерывна на отрезке $[a,b]$ ,

$f(a)\cdot f(b)<0, \; \eps=0,01$ и $t\in[a,b]$ - единственный корень уравнения $f(x)=0, \; a\le t\le b$ .

(Мы не рассматриваем случай, когда корней на отрезке $[a,b]$ несколько, то есть более одного. В качестве $\eps$ можно взять и другое достаточно малое положительное число, например, $0,001$ .)

Поделим отрезок $[a,b]$ пополам. Получим точку $c= \frac {a+b}{2}, \; a<c<b$ и два отрезка $[a,c], \; [c,b]$ .

Если $f(c)=0$ , то корень $t$ найден ( $t=c$ ).
Если нет, то из двух полученных отрезков и надо выбрать один такой, что , то есть
- $[a_1;b_1] = [a,c]$ , если $f(a)\cdot f(c)<0$ или
- $[a_1;b_1] = [c,b]$ , если $f(c)\cdot f(b)<0$ .

Новый отрезок $[a_1;b_1]$ делим пополам. Получаем середину этого отрезка $c_1=\frac {a_1+b_1}{2}$ и так далее.

Для того, чтобы найти приближённое значение корня с точностью до $\eps >0$ , необходимо остановить процесс половинного деления на таком шаге $n$ , на котором $|b_n-c_n|<\eps$ и вычислить $x=\frac {a_n+b_n}{2}$ . Тогда можно взять $t\approx x$ .

Реализация метода на С++ и числовой пример

Решим уравнение $4-e^x-2x^2=0$ методом дихотомии. Графическим методом находим отрезок $[0; \,1]$ , которому принадлежит искомый корень. Так как $f(0)\cdot f(1)<0$ , то принимаем $a=0, \; b=1$ .

Ниже приведен пример программы на Си++, которая решает поставленную задачу.

Программа 1. Корень уравнения

#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;
}

Искомый корень $x \approx 0.88281$ . Вычисления проводились с точностью $0.01$ .

Промежуточные вычисления представлены в таблице ниже.

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

Метод дихотомии как метод оптимизации

Рис. 1. Поиск экстремума функции методом дихотомии

Рис. 1. Поиск экстремума функции $F(x)$ методом дихотомии

Рис. 2. Схема алгоритма метода дихотомии

Однопараметрическая оптимизация (поиск экстремумов функций одной переменной) является самостоятельной и часто встречаемой задачей. Кроме того, к ней сводится гораздо более сложная задача - поиск экстремума функции многих переменных.

Рассмотрим метод дихотомии как простейший однопараметрический метод безусловной оптимизации. Данный метод является методом прямого поиска. В нем при поиске экстремума целевой функции используются только вычисленные значения целевой функции.

Дана функция $F(x)$ . Необходимо найти $\overline{x}$ , доставляющий минимум (или максимум) функции $F(x)$ на интервале $[a,b]$ с заданной точностью $\varepsilon$ , т.е. найти

$\overline{x} = \arg \min F(x), \; \overline{x} \in [a,b]$ .

Запишем словесный алгоритм метода.

На каждом шаге процесса поиска делим отрезок $[a,b]$ пополам, $x=\frac {a+b}{2}$ - координата середины отрезка $[a,b]$ .
Вычисляем значение функции $F(x)$ в окрестности $\pm \varepsilon$ вычисленной точки $x$ , т.е.
$F_1=F(x-\varepsilon),\; F_2=F(x+\varepsilon)$ .
Сравниваем и и отбрасываем одну из половинок отрезка (рис. 1).
- При поиске минимума:
  - Если $F_1<F_2$ , то отбрасываем отрезок $[x,b]$ , тогда $b=x$ . (рис. 1.а)
  - Иначе отбрасываем отрезок $[a,x]$ , тогда $a=x$ . (рис. 1.б)
- При поиске максимума:
  - Если $F_1<F_2$ , то отбрасываем отрезок $[a,x]$ , тогда $a=x$ .
  - Иначе отбрасываем отрезок $[x,b]$ , тогда $b=x$ .
Деление отрезка $[a,b]$ продолжается, пока его длина не станет меньше заданной точности $\varepsilon$ , т.е. $|b-a| \le \varepsilon$ .