Вещественный двоичный поиск
Вещественный двоичный поиск (англ. Bisection method)— алгоритм поиска аргумента для заданного значения монотонной вещественной функции.
Содержание
Формулировка задачи
Пусть нам задана монотонная функция и какое-то значение этой функции. Необходимо найти значение аргумента этой функции, такое, что .
Решение задачи
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.
Способы закончить поиск
| Способы | Плюсы | Минусы | Оценка на число итераций |
|---|---|---|---|
| Окончание, когда рассматриваемый отрезок станет меньше заданной погрешности . | Заданная точность найденного значения. | Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел, у которых есть точность. При больших значениях функции длина отрезка может никогда не уменьшиться до заданного значения. | В данном случае нам нужно рассмотреть чисел примерное число итераций . |
| Окончание, когда значение функции на концах отрезках различается менее, чем на заданную погрешность . | Значение функции от найденного значения имеет заданную точность. | а) Возможна большая погрешность, если функция будет очень медленно возрастать. б) Может зациклиться по той же причине, что и в первом способе. |
Аналогичная с первым случаем логика, примерное число итераций . |
| «Абсолютно точный поиск» Окончание, когда границы отрезка — два соседних по представлению значения в типе данных. Утверждается, что два числа — соседние, если середина их отрезка совпадает или с левой, или с правой границей. |
Максимально возможная точность найденного значения. | Возможно плохое поведение, если искомый аргумент равен нулю. | При работе с числами с плавающей точкой количество итераций зависит от плотности чисел на данном отрезке. При работе с числами фиксированной точности количество итераций аналогично первому и второму случаю равно . |
| «Итеративный способ» Выполнение конечного числа итераций. |
У способа фиксированная погрешность. | Довольно плохая точность, если границы отрезка находятся на большом расстоянии. | Выполняется заданное количество итераций. |
Выбор границы отрезка для поиска
Для начала найдем левую границу, выберем произвольную отрицательную точку (например ). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения. Для того, чтобы найти правую границу, выберем произвольную положительную точку (например ). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного.
Псевдокод
double findLeftBoard(C : double):
x = -1
while f(x) > C
x = x * 2
return x
double findRightBoard(C : double):
x = 1
while f(x) < C
x = x * 2
return x
double binSearch(C : double):
left = findLeftBoard(C)
right = findRightBoard(C)
while right - left < eps // Здесь можно использовать другое условие выхода
mid = (left + right) / 2
if f(mid) < C
left = mid
else
right = mid
return (left + right) / 2
Метод секущих
Итерационный численный метод приближённого нахождения корня уравнения.
Алгоритм
Пусть нам задана монотонная и значение . Выберем две начальные точки, причем , а . Проведем через них прямую, которая пересечет прямую в точке . Теперь вместо точек и возьмем точки и , и проделаем ту же операцию и так далее, получая точки и , пока . Вычисляем каждое последующее значение с помощью формулы:
Нахождение нулей функции :
Псевдокод
double search (a : double, b : double, eps : double): // Где a — левая граница, а b — правая
while |a - b| > eps
a = b - (b - a) * f(b) / (f(b) - f(a))
b = a - (a - b) * f(a) / (f(a) - f(b))
return b
Метод Ньютона
Итерационный численный метод нахождения нуля заданной функции.
Алгоритм
Задана монотонная, дифференцируемая функция и начальное значение . Построим касательную к нашей функции в заданной точке и найдем новую точку , как пересечения касательной и оси абсцисс. Пока не выполнено заданное условие, например , вычисляем новое значение по формуле:
Псевдокод
double search (x : double, eps : double):
while f(x) > eps
x = x - f(x) / f'(x)
return x
Пример
Найдём корень -ой степени с помощью метода Ньютона. Пусть даны числа и — число и корень какой степень нам нужно посчитать соответственно. Составим функцию , тогда её пересечение с осью абсцисс и будет искомым корнем.
double nthRoot (C : double, n : double, eps : double)
while pow(x, n) - C > eps
x = x - (pow(x, n) - C) / (n * pow(x, n - 1))
return x
Замечания
- Необходимо отметить, то функция должна быть строго монотонна, если мы ищем конкретный корень и он единственный. Нестрого монотонна, если нам необходимо найти самый левый (правый) аргумент. Если же функция не монотонна, то данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным.
- Классической задачей на вещественный двоичный поиск является задача поиска корня -ой степени из числа : . При нижней границей для поиска будет , а верхней — .
