Изменения

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

Пусть нам задана монотонная функция<tex> f </tex> и какое-то значение <tex> C </tex> этой функции. Необходимо найти значение аргумента <tex>x</tex> этой функции, в которой она принимает определенное значение такое, что <tex>f(x) = C</tex>.

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

=== Способы закончить поиск ===* Первый способ заключается в том, чтобы остановиться{| class="wikitable"! Способы || Плюсы || Минусы || Оценка на число итераций|-| Окончание, когда рассматриваемый отрезок станет меньше заданного эпсилонзаданной погрешности <tex> \varepsilon </tex>. || Заданная точность найденного значения. || Алгоритм может зациклиться. Но В компьютере мы работаем с конечным числом вещественных чисел, у этого подхода которых есть свои плюсы точность. При больших значениях функции длина отрезка может никогда не уменьшиться до заданного значения. || В данном случае нам нужно рассмотреть <tex dpi=130> \genfrac{}{}{}{}{R - L}{\varepsilon} </tex> чисел <tex> \Rightarrow </tex> примерное число итераций <tex dpi=130> \log(\genfrac{}{}{}{}{R - L}{\varepsilon}) </tex>.|-| Окончание, когда значение функции на концах отрезках различается менее, чем на заданную погрешность <tex> \varepsilon </tex>. || Значение функции от найденного значения имеет заданную точность. || а) Возможна большая погрешность, если функция будет очень медленно возрастать. <br> б) Может зациклиться по той же причине, что и минусы:в первом способе. || Аналогичная с первым случаем логика, примерное число итераций <tex dpi=130> \log(\genfrac{}{}{}{}{f(R) - f(L)}{\varepsilon}) </tex>.: '''+''' Алгоритм |-| «Абсолютно точный поиск» <br> Окончание, когда границы отрезка — два соседних по представлению значения в типе данных. Утверждается, что два числа — соседние, если середина их отрезка совпадает или с левой, или с правой границей. || Максимально возможная точность найденного значения. || Возможно плохое поведение, если искомый аргумент равен нулю. || При работе с числами с плавающей точкой количество итераций зависит от плотности чисел на данном отрезке. При работе с большой точностью найдет значение аргументачислами фиксированной точности <tex>\varepsilon</tex> количество итераций аналогично первому и второму случаю равно <tex dpi=130> \log(\genfrac{}{}{}{}{R - L}{\varepsilon}) </tex>.|-| «Итеративный способ» <br> Выполнение конечного числа итераций. || У способа фиксированная погрешность. || Довольно плохая точность, если границы отрезка находятся на большом расстоянии. || Выполняется заданное количество итераций.|}

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

== Псевдокод == '''double''' findLeftBoard(C : &ndash; '''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 <font color=green> // Здесь можно использовать другое условие выхода </font> mid = (left + right) / 2 '''if''' f(mid) < C left = mid '''else''' right = mid '''return''' (left + right) / 2 . Вспомним о том == Метод секущих ==[[Файл:Secant method.png|thumb|350px|right|Метод секущих при <tex> C = 0 </tex>]] Итерационный численный метод приближённого нахождения корня уравнения. === Алгоритм ===Пусть нам задана монотонная <tex> f </tex> и значение <tex> C </tex>. Выберем две начальные точки, что вещественный числа причем <tex> f(x_{1}) < C </tex>, а <tex> f(x_{2}) > C </tex>. Проведем через них прямую, которая пересечет прямую <tex> y = C </tex> в компьютере дискретнымточке <tex> (x_{3}, C) </tex>. Будем завершать поискТеперь вместо точек <tex> x_{1} </tex> и <tex> x_{2} </tex> возьмем точки <tex> x_{3} </tex> и <tex> x_{2} </tex>, когда границы отрезка и проделаем ту же операцию и так далее, получая точки <tex> x_{n+1} </tex> и <tex> x_{n} </tex>, пока <tex> |x_{n-1} -x_{n}| > \varepsilon </tex>.Вычисляем каждое последующее значение <tex> x_{n+1} </tex> с помощью формулы: <tex dpi=130> x_{n+1} = x_{n-1} + \dfrac{(C - f(x_{n}))\cdot(x_{n} -x_{n-1})}{f(x_{n} два соседних по представлению значения в типе данных. Утверждается, что два числа ) - f(x_{n-1})} </tex> Нахождение нулей функции <tex>(C = 0)</tex>: <tex dpi=130> x_{n+1} = x_{n-1} - \dfrac{f(x_{n})\cdot(x_{n} - x_{n-1})}{f(x_{n}) -f(x_{n-1})} соседние</tex> === Псевдокод ===<code> '''double''' search (a : '''double''', если середина их отрезка совпадает или с левойb : '''double''', или с правой границей.eps : '''+double''' Алгоритм найдет число с максимально возможной точностью.): &ndash; Возможно плохое поведение <font color=green> // Где a {{---}} левая граница, если искомый аргумент равен 0.а b {{---}} правая </font> '''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</code> == Метод Ньютона ==[[Файл:Newton method.png|thumb|300px|right|Метод Ньютона]] : &ndash; Довольно плохая точность, если границы отрезка находятся на большом расстоянииИтерационный численный метод нахождения нуля заданной функции. ===Алгоритм = Выбор границы отрезка для поиска==Для начала Задана монотонная, дифференцируемая функция и начальное значение <tex> x_{0} </tex>. Построим касательную к нашей функции в заданной точке и найдем правую границуновую точку <tex> x_{1} </tex>, как пересечения касательной и оси абсцисс. Выберем произвольную положительную точку Пока не выполнено заданное условие, например <tex> f(например x_{n}) < \varepsilon </tex>, вычисляем новое значение <tex>x_{n+1} </tex>по формуле: <tex dpi=130> x_{n+1} = x_{n} - \dfrac{f(x_{n})}{f'(x_{n})} </tex> === Псевдокод ===<code> '''double''' search (x : '''double''', eps : '''double'''): '''while''' f(x) > eps x = x - f(x) / f'(x) '''return''' x</code> === Пример ===Пусть даны числа <tex> C </tex> и <tex> n </tex> {{---}} число и корень какой степень нам нужно посчитать соответственно. Будем удваивать ее до тех пор, пока значение функции Пусть <tex> x = \sqrt[n]{C}</tex>. Возведем все выражение в <tex>n</tex>-ую степень и перенесем всё в этой точке меньше заданного. Для тоголевую часть, чтобы найти левую границу выберем произвольную отрицательную точку (например тогда <tex>x^n -1C = 0 </tex>). Будем удваивать ее до тех порТо есть нужно найти нуль этого выражения, пока значение в ней будет больше заданного значениярешим это с помощью метода Ньютона. <code> '''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</code>

* Необходимо отметить, то функция должна быть строго монотонна, если мы ищем конкретный корень и он единственный. Нестрого монотонна, если нам необходимо найти самый левый (правый) аргумент. Если же функция не монотонна, то данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным. * Важным отличием от целочисленного Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x \geqslant 1</tex> нижней границей для поиска является то, что мы передвигаем границу ровно в середину отрезка (будет <tex>left = mid1</tex>), а не со смещением внутрь отрезка (верхней {{---}} <tex>left = mid + 1x</tex>).  == См. также ==* [[Целочисленный двоичный поиск]] == Источники информации == * [http://wwwen.wikipedia.org/wiki/Bisection_method Bisection method {{---}} Wikipedia]* [http://en.intuitwikipedia.ruorg/departmentwiki/algorithmsNewton%27s_method Newton's method {{---}} Wikipedia]* [http:/basicalgos/2www.youtube.com/ Интернет университет, лекция watch?v=qkLLcdgJj_o Видеолекция "сортировка и поиск"]* [http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch Binary search {{---}} Topcoder] [[Категория: Дискретная математика и алгоритмы]][[Категория: Алгоритмы поиска]]