Изменения

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

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

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

| 1) Окончание, когда рассматриваемый отрезок станет меньше заданного эпсилон (= заданной погрешности <tex> \varepsilon </tex>). || Заданная точность найденного значения. || Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел, у которых есть точность. При больших значениях функции длина отрезка может никогда не уменьшиться до заданного значения. || В данном случае нам нужно рассмотреть <texdpi=130> (\genfrac{}{}{}{}{R - L-R)/}{\varepsilon } </tex> чисел =<tex> \Rightarrow </tex> примерное число итераций <texdpi=130> \log((\genfrac{}{}{}{}{R - L-R)/}{\varepsilon}) </tex>.

| 2) Окончание, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон (= заданную погрешность <tex> \varepsilon </tex>). || Значение функции от найденного значения имеет заданную точность. || а) Возможна большая погрешность, если функция будет очень медленно возрастать. <br> б) Алгоритм может Может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел, у которых есть точность. При быстром возрастании значений функции мы можем не найти такие границыпо той же причине, что значение на них различается менее, чем на заданное <tex> \varepsilon </tex>и в первом способе. || Аналогичная с первым случаем логика, примерное число итераций <texdpi=130> \log((\genfrac{}{}{}{}{f(LR)-f(R)L)/}{\varepsilon}) </tex>.

| 3) «Абсолютно точный поиск» <br> Окончание, когда границы отрезка — два соседних по представлению значения в типе данных. Утверждается, что два числа — соседние, если середина их отрезка совпадает или с левой, или с правой границей. || Максимально возможная точность найденного значения. || Возможно плохое поведение, если искомый аргумент равен нулю. || При работе с числами с плавающей точкой количество итераций зависит от плотности чисел на данном отрезке. При работе с числами фиксированной точности (= <tex>\varepsilon</tex>) количество итераций аналогично первому и второму случаю равно <texdpi=130> \log((\genfrac{}{}{}{}{R - L-R)/}{\varepsilon}) </tex>.

| 4) «Итеративный способ» <br> Выполнение конечного числа итераций. || У способа фиксированная погрешность. || Довольно плохая точность, если границы отрезка находятся на большом расстоянии. || Выполняется заданное количество итераций.

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

<code> '''findLeftdouble'''findLeftBoard(cC : '''double'''):

'''while''' f(x) > c C

</code><code>.  '''findRightdouble'''findRightBoard(cC : '''double'''):

'''while''' f(x) < cC

</code>.<code> '''binSearchdouble'''binSearch(c)C : left = '''findLeftdouble'''): left = findLeftBoard(сC) right = '''findRight'''findRightBoard(сC) '''while''' right - left < right - eps <font color=green> //Здесь можно использовать другое условие выхода</font>

'''if''' f(mid) == c //** '''return''' mid //** '''else if''' f(mid) < cC

'''return''' l(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'''): <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

== Примеры использования Метод Ньютона ==* Классической задачей на вещественный двоичный поиск является задача поиска корня [[Файл:Newton method.png|thumb|300px|right|Метод Ньютона]] Итерационный численный метод нахождения нуля заданной функции. === Алгоритм ===Задана монотонная, дифференцируемая функция и начальное значение <tex> x_{0} </tex>. Построим касательную к нашей функции в заданной точке и найдем новую точку <tex> x_{1} </tex>, как пересечения касательной и оси абсцисс. Пока не выполнено заданное условие, например <tex>f(x_{n}) < \varepsilon </tex>-ой степени из числа , вычисляем новое значение <tex>xx_{n+1} </tex>по формуле:  <texdpi=130>x_{n+1} = x_{n} - \sqrt[dfrac{f(x_{n]})}{f'(x_{xn})}</tex>. При  === Псевдокод ===<code> '''double''' search (x : '''double''', eps : '''double'''): '''while''' f(x) > eps x = x - f(x) / f'(x) '''return''' x</code> === Пример ===Пусть даны числа <tex>x \ge 1C </tex> нижней границей для поиска будет и <tex>1n </tex>, а верхней {{---}} число и корень какой степень нам нужно посчитать соответственно. Пусть <tex>x= \sqrt[n]{C}</tex>.* Если функция нестрого монотонна, то, убрав из приведенного выше алгоритма строки, отмеченные Возведем все выражение в <tex>(**)n</tex>-ую степень и перенесем всё в левую часть, мы получим алгоритм, который будет находить тогда <tex>x^n - C = 0 </tex> такой. То есть нужно найти нуль этого выражения, что решим это с помощью метода Ньютона. <texcode>f '''double''' nthRoot (C : '''double''', n : '''double''', eps : '''double''') '''while''' pow(x, n) - C > eps x = c<x - (pow(x, n) - C) /tex> и <tex>f(n * pow(x , n - \varepsilon1)) < c '''return''' x</texcode>.

* Необходимо отметить, то функция должна быть строго монотонна, если мы ищем конкретный корень и он единственный. Нестрого монотонна, если нам необходимо найти самый левый (правый) аргумент. Если же функция не монотонна, то данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным. * Важным отличием от [[целочисленный Классической задачей на вещественный двоичный поиск|целочисленного является задача поискакорня <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://en.wikipedia.org/wiki/Bisection_method Bisection method {{---}} Wikipedia]* [http://en.wikipedia.org/wiki/Newton%27s_method Newton's method {{---}} Wikipedia]