Вещественный двоичный поиск

Материал из Викиконспекты
Перейти к: навигация, поиск

Вещественный двоичный поиск (англ. Bisection method)— алгоритм поиска аргумента для заданного значения монотонной вещественной функции.

Формулировка задачи[править]

Пусть нам задана монотонная функция [math] f [/math] и какое-то значение [math] C [/math] этой функции. Необходимо найти значение аргумента [math] x [/math] этой функции, такое, что [math] f(x) = C [/math].

Function.png

Решение задачи[править]

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

Способы закончить поиск[править]

Способы Плюсы Минусы Оценка на число итераций
Окончание, когда рассматриваемый отрезок станет меньше заданной погрешности [math] \varepsilon [/math]. Заданная точность найденного значения. Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел, у которых есть точность. При больших значениях функции длина отрезка может никогда не уменьшиться до заданного значения. В данном случае нам нужно рассмотреть [math] \genfrac{}{}{}{}{R - L}{\varepsilon} [/math] чисел [math] \Rightarrow [/math] примерное число итераций [math] \log(\genfrac{}{}{}{}{R - L}{\varepsilon}) [/math].
Окончание, когда значение функции на концах отрезках различается менее, чем на заданную погрешность [math] \varepsilon [/math]. Значение функции от найденного значения имеет заданную точность. а) Возможна большая погрешность, если функция будет очень медленно возрастать.
б) Может зациклиться по той же причине, что и в первом способе.
Аналогичная с первым случаем логика, примерное число итераций [math] \log(\genfrac{}{}{}{}{f(R) - f(L)}{\varepsilon}) [/math].
«Абсолютно точный поиск»
Окончание, когда границы отрезка — два соседних по представлению значения в типе данных. Утверждается, что два числа — соседние, если середина их отрезка совпадает или с левой, или с правой границей.
Максимально возможная точность найденного значения. Возможно плохое поведение, если искомый аргумент равен нулю. При работе с числами с плавающей точкой количество итераций зависит от плотности чисел на данном отрезке. При работе с числами фиксированной точности [math]\varepsilon[/math] количество итераций аналогично первому и второму случаю равно [math] \log(\genfrac{}{}{}{}{R - L}{\varepsilon}) [/math].
«Итеративный способ»
Выполнение конечного числа итераций.
У способа фиксированная погрешность. Довольно плохая точность, если границы отрезка находятся на большом расстоянии. Выполняется заданное количество итераций.

Выбор границы отрезка для поиска[править]

Для начала найдем левую границу, выберем произвольную отрицательную точку (например [math]-1[/math]). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения. Для того, чтобы найти правую границу, выберем произвольную положительную точку (например [math]1[/math]). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного.

Псевдокод[править]

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

.

Метод секущих[править]

Метод секущих при [math] C = 0 [/math]

Итерационный численный метод приближённого нахождения корня уравнения.

Алгоритм[править]

Пусть нам задана монотонная [math] f [/math] и значение [math] C [/math]. Выберем две начальные точки, причем [math] f(x_{1}) \lt C [/math], а [math] f(x_{2}) \gt C [/math]. Проведем через них прямую, которая пересечет прямую [math] y = C [/math] в точке [math] (x_{3}, C) [/math]. Теперь вместо точек [math] x_{1} [/math] и [math] x_{2} [/math] возьмем точки [math] x_{3} [/math] и [math] x_{2} [/math], и проделаем ту же операцию и так далее, получая точки [math] x_{n+1} [/math] и [math] x_{n} [/math], пока [math] |x_{n-1} - x_{n}| \gt \varepsilon [/math]. Вычисляем каждое последующее значение [math] x_{n+1} [/math] с помощью формулы:

[math] x_{n+1} = x_{n-1} + \dfrac{(C - f(x_{n}))\cdot(x_{n} - x_{n-1})}{f(x_{n}) - f(x_{n-1})} [/math]

Нахождение нулей функции [math](C = 0)[/math]:

[math] x_{n+1} = x_{n-1} - \dfrac{f(x_{n})\cdot(x_{n} - x_{n-1})}{f(x_{n}) - f(x_{n-1})} [/math]

Псевдокод[править]

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

Метод Ньютона[править]

Метод Ньютона

Итерационный численный метод нахождения нуля заданной функции.

Алгоритм[править]

Задана монотонная, дифференцируемая функция и начальное значение [math] x_{0} [/math]. Построим касательную к нашей функции в заданной точке и найдем новую точку [math] x_{1} [/math], как пересечения касательной и оси абсцисс. Пока не выполнено заданное условие, например [math] f(x_{n}) \lt \varepsilon [/math], вычисляем новое значение [math] x_{n+1} [/math] по формуле:

[math] x_{n+1} = x_{n} - \dfrac{f(x_{n})}{f'(x_{n})} [/math]

Псевдокод[править]

double search (x : double, eps : double):
    while f(x) > eps
         x = x - f(x) / f'(x)
    return x

Пример[править]

Пусть даны числа [math] C [/math] и [math] n [/math] — число и корень какой степень нам нужно посчитать соответственно. Пусть [math] x = \sqrt[n]{C}[/math]. Возведем все выражение в [math]n[/math]-ую степень и перенесем всё в левую часть, тогда [math] x^n - C = 0 [/math]. То есть нужно найти нуль этого выражения, решим это с помощью метода Ньютона.

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

Замечания[править]

  • Необходимо отметить, то функция должна быть строго монотонна, если мы ищем конкретный корень и он единственный. Нестрого монотонна, если нам необходимо найти самый левый (правый) аргумент. Если же функция не монотонна, то данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным.
  • Классической задачей на вещественный двоичный поиск является задача поиска корня [math]n[/math]-ой степени из числа [math]x[/math]: [math]\sqrt[n]{x}[/math]. При [math]x \geqslant 1[/math] нижней границей для поиска будет [math]1[/math], а верхней — [math]x[/math].

См. также[править]

Источники информации[править]