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

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

Содержание

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

Введение

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

Задать начальный интервал $[X_{left}..X_{right}]$ ;
Убедиться, что на концах функция имеет разный знак;
Повторять
- выбрать внутри интервала точку $X$ ;
- сравнить знак функции в точке со знаком функции в одном из концов;
  - если совпадает, то переместить этот конец интервала в точку $X$ ,
  - иначе переместить в точку $X$ другой конец интервала;

пока не будет достигнута нужная точность.

Варианты метода дихотомии различаются выбором точки деления. Рассмотрим варианты дихотомии: метод половинного деления и метод хорд.

Метод половинного деления

Метод половинного деления известен также как метод бисекции. В данном методе интервал делится ровно пополам.

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

Метод половинного деления:

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

Метод половинного деления как метод поиска корней функции

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

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

Будем считать, что корень $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$ .

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

На рис 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)$ в этой точке.

Метод хорд

Недостаток деления отрезка строго пополам проистекает от того, что он использует лишь знак функции, игноририруя отклонение (абсолютную величину). Но очевидно, что чем меньше (по абсолютной величине) значение функции, тем ближе мы находимся к корню. Метод хорд предлагает делить отрезок в точке, отстоящей от краев отрезка пропорционально абсолютному значению функции на краях. (Название "метод хорд" происходит от того, что точка деления является пересечением отрезка $[(X_{left},\; F(X_{left})), \; (X_{right},\; F(X_{right}))]$ - хорды - с осью абцисс.)

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

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

Рис. 3. Метод хорд

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

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

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

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

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

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

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

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

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

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

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

Комбинация метода хорд и метода половинного деления

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

Если применять аналогичное уточнение к интервалу, полученному методом хорд, то эффект будет значительно слабее. Это ещё раз иллюстрирует тот факт, что метод хорд очень хорошо работает в условиях малого интервала (близости обеих границ интервала к корню), но неспособен сам создать себе эти условия (приблизить обе границы к корню).

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

Поэтому лучше использовать в качестве точки деления что-то среднее: если метод половинного деления предлагает использовать $X_{halfdiv}$ , а метод хорд - $X_{chord}$ , то возьмем $X_{halfdiv}*K+X_{chord}*(1-K)$ . Коэффициент $K \in [0..1]$ .

Чему должен быть равен коэффициент $K$ ? Его следует не задавать, а вычислять по ходу работы: если при очередной операции интервал уменьшился более чем в два раза (это то, что гарантирует метод половинного деления), то значит, нужно больше доверять методу хорд (уменьшить $K$ ), и наоборот.

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

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

См. также

Практикум ММП ВМК, 4й курс, осень 2008

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B4%D0%B8%D1%85%D0%BE%D1%82%D0%BE%D0%BC%D0%B8%D0%B8»

Категория: Учебные задачи

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

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

Содержание

Введение

Метод половинного деления

Метод половинного деления как метод поиска корней функции

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

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

Метод половинного деления как метод оптимизации

Метод хорд

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

Комбинация метода хорд и метода половинного деления

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

См. также

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты