Изменения

'''Вещественный двоичный поиск''' (англ. ''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> Выполнение конечного числа итераций. || У способа фиксированная погрешность. || Довольно плохая точность, если границы отрезка находятся на большом расстоянии. || Выполняется заданное количество итераций.|}

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

== Псевдокод == '''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 <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''' Возможно плохое поведение, если искомый аргумент равен 0.* Итеративный способ. В этом способе выполнится только конечное число число итераций.eps : '''+double''' Плюсом этого способа является фиксированная погрешность.): <font color=green> // Где a {{---}} левая граница, а 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|Метод Ньютона]] Итерационный численный метод нахождения нуля заданной функции. == Выбор границы отрезка для поиска= Алгоритм ===Для начала Задана монотонная, дифференцируемая функция и начальное значение <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.intuitwikipedia.ruorg/wiki/Bisection_method Bisection method {{---}} Wikipedia]* [http:/department/algorithmsen.wikipedia.org/basicalgoswiki/2Newton%27s_method Newton's method {{---}} Wikipedia]* [http:/ Интернет университет, лекция /www.youtube.com/watch?v=qkLLcdgJj_o Видеолекция "сортировка и поиск"]* [http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch Binary search {{---}} Topcoder] [[Категория: Дискретная математика и алгоритмы]][[Категория: Алгоритмы поиска]]