Изменения
Нет описания правки
== Псевдокод ==
'''double''' findLeftBoard(C : '''double'''):
x = -1
x = x * 2
'''return''' x
'''double''' findRightBoard(C : '''double'''):
x = 1
x = x * 2
'''return''' x
'''double''' binSearch(C : '''double'''):
left = findLeftBoard(C)
right = mid
'''return''' (left + right) / 2
== Метод секущих ==
[[Файл:Secant method.png|thumb|250px350px|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} + \genfrac{}{}{}{}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} - \genfrac{}{}{}{}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
</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 - C = 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>
== Замечания ==
* Необходимо отметить, то функция должна быть строго монотонна, если мы ищем конкретный корень и он единственный. Нестрого монотонна, если нам необходимо найти самый левый (правый) аргумент. Если же функция не монотонна, то данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным.
* [[Целочисленный двоичный поиск]]
== Источники информации ==
* [http://en.wikipedia.org/wiki/Bisection_method Bisection method {{---}} Wikipedia]
* [http://en.wikipedia.org/wiki/Newton%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]
