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

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

Версия от 16:57, 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,c]$ и $[c,b]$ надо выбрать один $[a_1;b_1]$ такой, что $f(a_1)\cdot f(b_1)<0$ , то есть $[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

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

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

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

Дана функция $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)$ .
Сравниваем и и отбрасываем одну из половинок отрезка (рис. 9.1).
- При поиске минимума:\\Если $F_1<F_2$ , то отбрасываем отрезок $[x,b]$ , тогда $b=x$ . (рис. 9.1.а)\\Иначе отбрасываем отрезок $[a,x]$ , тогда $a=x$ . (рис. 9.1.б)
- При поиске максимума:

Если $F_1<F_2$ , то отбрасываем отрезок $[a,x]$ , тогда $a=x$ .

Иначе отбрасываем отрезок $[x,b]$ , тогда $b=x$ .

Деление отрезка $[a,b]$ продолжается, пока его длина не станет меньше заданной точности $\varepsilon$ , т.е. $|b-a| \le \varepsilon$ .

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

Схема алгоритма метода дихотомии представлена на рис 9.2.

На рис 9.2: $c$ - константа,

$c = \begin{cases} \quad 1 , \quad (min \; F(x)), \\ -1, \quad (max \; F(x)). \end{cases}$

При выводе $x$ – координата точки, в которой функция $F(x)$ имеет минимум (или максимум), $F_M$ – значение функции $F(x)$ в этой точке.

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

Метод хорд

Метод хорд (способ пропорциональных частей) — численный метод уточнения корня трансцендентного уравнения. Метод основан на замене функции $f(x)$ на каждом шаге поиска хордой, пересечение которой с осью $Х$ дает приближение корня.

При этом в процессе поиска семейство хорд может строиться:

а) при фиксированном левом конце хорд, т.е. $z=a$ , тогда начальная точка $x_0=b$ (рис. 4.10а);

б) при фиксированном правом конце хорд, т.е. $z=b$ , тогда начальная точка $x_0=a$ (рис. 4.10б);

Рис. 4.10.

В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:

для случая а):

$x_{n+1}=x_n - \frac{f(x_n)}{f(x_n)-f(a)} (x_n - a);$ (4.11)

для случая б): $x_{n+1}=x_n - \frac{f(x_n)}{f(x_n)-f(b)} (x_n - b);$ (4.12)

Процесс поиска продолжается до тех пор, пока не выполнится условие $|x_{n+1}–x_n| \le \varepsilon$ или $| h| \le \varepsilon$ . (4.13)

Метод обеспечивает быструю сходимость, если $f(z)\cdot f''(z) > 0$ , т.е. хорды фиксируются в том конце интервала $[a,b]$ , где знаки функции $f(z)$ и ее кривизны $f$ совпадают.

Схема алгоритма уточнения корня методом хорд представлена на рис. 4.11.

Схема алгоритма уточнения корня методом хорд

Рис. 4.11. Схема алгоритма уточнения корня методом хорд

Этот метод позволяет исключать в точности половину интервала на каждой итерации. Приведем описание поисковой процедуры, ориентированной на нахождение точки минимума функции $f(x)$ в интервале $(a,b)$ .

  1. Шаг1. Положить  и .
     Вычислить значение .
  2. Шаг2. Положить  и .
     Можно заметить,что точки  делят интервал  на четыре равные части.
     Вычислить значения  и .
  3. Шаг3. Сравнить  и .
         * если , исключить интервал .
           Средней точкой нового интервала поиска становится точка .
           Следовательно, необходимо положить . Перейти к шагу 5.
         * если , то перейти к шагу 4. 
  4. Шаг4. Сравнить  и .
         * если , исключить интервал , положив .
           Т.к. средней точкой нового интервала становится точка , положить .
           Перейти к шагу 5.
         * если , исключить интервалы  и .
           Положить  и . (Заметим, что  продолжает оставаться средней точкой нового интервала)
           Перейти к шагу 5. 
  5. Шаг5. Вычислить .
     Если величина  мала, закончить поиск, в противном случае вернуться к шагу 2.