Изменения

Перейти к: навигация, поиск

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

20 байт убрано, 22:41, 12 июня 2012
м
Нет описания правки
: '''+''' Алгоритм с большой точностью найдет значение аргумента
: <tex>-</tex> &ndash; Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения
* Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон.
: '''+''' В отличии от предыдущего, не зацикливается при больших значениях функции.
: <tex>-</tex> &ndash; Возможна большая погрешность, если функция будет очень медленно возрастать
* Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка - два соседних по представлению значения в типе данных. Утверждается, что два числа - соседние, если середина их отрезка совпадает или с левой, или с правой границей.
: '''+''' Алгоритм найдет число с максимально возможной точностью.
: <tex>-</tex> &ndash; Возможно плохое поведение, если искомый аргумент равен 0.
* Итеративный способ. В этом способе выполнится только конечное число число итераций.
: '''+''' Плюсом этого способа является фиксированная погрешность.
: <tex>-</tex> &ndash; Довольно плохая точность, если границы отрезка находятся на большом расстоянии.
== Выбор границы отрезка для поиска==
Для начала найдем правую границу. Выберем произвольную положительную точку (например </tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.
61
правка

Навигация