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

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

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

Формулировка задачи

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

Function.png

Решение задачи

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

Способы закончить поиск

  • Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы:
+ Алгоритм с большой точностью найдет значение аргумента
– Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения
  • Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон.
+ В отличии от предыдущего, не зацикливается при больших значениях функции.
– Возможна большая погрешность, если функция будет очень медленно возрастать
  • Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка — два соседних по представлению значения в типе данных. Утверждается, что два числа — соседние, если середина их отрезка совпадает или с левой, или с правой границей.
+ Алгоритм найдет число с максимально возможной точностью.
– Возможно плохое поведение, если искомый аргумент равен 0.
  • Итеративный способ. В этом способе выполнится только конечное число число итераций.
+ Плюсом этого способа является фиксированная погрешность.
– Довольно плохая точность, если границы отрезка находятся на большом расстоянии.

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

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

Псевдокод

findLeft(c) 
    x = -1;
    while f(x) > c 
        x = x * 2;
    return x; 
findRight(c)
    x = 1;
    while f(x) < c
        x = x * 2;
    return x;
binSearch(c)
    left = findLeft(с);
    right = findRight(с);
    while left < right - eps                           //Здесь можно использовать другое условие выхода
        mid = (left + right) / 2;
        if f(mid) == c                                 //**
            return mid;                                //**
        else if f(mid) < c
            left = mid;
        else
            right = mid;
    return l;

Примеры использования

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

Замечания

  • Необходимо отметить, то функция должна быть строго монотонна, если мы ищем конкретный корень и он единственный. Нестрого монотонна, если нам необходимо найти самый левый (правый) аргумент. Если же функция не монотонна, то данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным.
  • Важным отличием от целочисленного поиска является то, что мы передвигаем границу ровно в середину отрезка ([math]left = mid[/math]), а не со смещением внутрь отрезка ([math]left = mid + 1[/math]).

Источники