Вещественный двоичный поиск — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 67 промежуточных версий 10 участников)
Строка 1: Строка 1:
'''Вещественный двоичный поиск''' - алгоритм поиска аргумента для заданного значения монотонной вещественной функции.
+
'''Вещественный двоичный поиск''' (англ. ''Bisection method''){{---}} алгоритм поиска аргумента для заданного значения монотонной вещественной функции.
  
 
== Формулировка задачи ==  
 
== Формулировка задачи ==  
Пусть нам задана монотонная функция. Необходимо найти значение аргумента <tex>x</tex> этой функции, в которой она принимает определенное значение <tex>C</tex>.
+
Пусть нам задана монотонная функция <tex> f </tex> и какое-то значение <tex> C </tex> этой функции. Необходимо найти значение аргумента <tex> x </tex> этой функции, такое, что <tex> f(x) = C </tex>.
  
 
[[Файл:Function.png]]
 
[[Файл:Function.png]]
  
 
== Решение задачи ==
 
== Решение задачи ==
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.
+
Применим идею [[целочисленный двоичный поиск | двоичного поиска]]. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.
  
== Способы закончить поиск ==
+
=== Способы закончить поиск ===
* Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы:
+
{| 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>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного.
: '''+''' В отличии от предыдущего, не зацикливается при больших значениях функции.
 
  
: &ndash; Возможна большая погрешность, если функция будет очень медленно возрастать
+
== Псевдокод ==
* Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка - два соседних по представлению значения в типе данных. Утверждается, что два числа - соседние, если середина их отрезка совпадает или с левой, или с правой границей.
+
'''double''' findLeftBoard(C : '''double'''):
: '''+''' Алгоритм найдет число с максимально возможной точностью.
+
    x = -1
: &ndash;  Возможно плохое поведение, если искомый аргумент равен 0.
+
    '''while''' f(x) > C
* Итеративный способ. В этом способе выполнится только конечное число число итераций.
+
        x = x * 2
: '''+''' Плюсом этого способа является фиксированная погрешность.
+
    '''return''' x
: &ndash;  Довольно плохая точность, если границы отрезка находятся на большом расстоянии.
+
 
== Выбор границы отрезка для поиска==
+
.
Для начала найдем правую границу. Выберем произвольную положительную точку (например <tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.
+
 
 +
  '''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'''):       <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>
  
== Псевдокод ==
 
<pre>
 
findLeft(c)
 
    x = -1;
 
    while f(x) > c
 
        x = x * 2;
 
    return x;
 
</pre>
 
<pre>
 
findRight(c)
 
    x = 1;
 
    while f(x) < c
 
        x = x * 2;
 
    return x;
 
</pre>
 
<pre>
 
binSearch(c)
 
    left = findLeft(с);
 
    right = findRight(с);
 
    while left < right - eps                          //Здесь можно использовать другое условие выхода
 
        mid = (left + right) / 2;
 
        if f(mid) < c
 
            left = mid;
 
        else
 
            right = mid;
 
    return l;
 
</pre>
 
== Пример использования ==
 
Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x >= 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней - <tex>x</tex>.
 
 
== Замечания ==
 
== Замечания ==
Необходимо отметить, то функция должна быть строго монотонна, иначе данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным. Важным отличием от целочисленного поиска является то, что мы передвигаем границу ровно в середину отрезка (<tex>left = mid</tex>), а не со смещением внутрь отрезка (<tex>left = mid + 1</tex>).  
+
* Необходимо отметить, то функция должна быть строго монотонна, если мы ищем конкретный корень и он единственный. Нестрого монотонна, если нам необходимо найти самый левый (правый) аргумент. Если же функция не монотонна, то данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным.
== Источники ==  
+
* Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x \geqslant 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней {{---}} <tex>x</tex>.
* [http://www.intuit.ru/department/algorithms/basicalgos/2/ Интернет университет, лекция сортировка и поиск]
+
 
 +
== См. также ==
 +
* [[Целочисленный двоичный поиск]]
 +
 
 +
== Источники информации ==
 +
* [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]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Алгоритмы поиска]]

Текущая версия на 19:22, 4 сентября 2022

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

Формулировка задачи

Пусть нам задана монотонная функция [math] f [/math] и какое-то значение [math] C [/math] этой функции. Необходимо найти значение аргумента [math] x [/math] этой функции, такое, что [math] f(x) = C [/math].

Function.png

Решение задачи

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

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

Способы Плюсы Минусы Оценка на число итераций
Окончание, когда рассматриваемый отрезок станет меньше заданной погрешности [math] \varepsilon [/math]. Заданная точность найденного значения. Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел, у которых есть точность. При больших значениях функции длина отрезка может никогда не уменьшиться до заданного значения. В данном случае нам нужно рассмотреть [math] \genfrac{}{}{}{}{R - L}{\varepsilon} [/math] чисел [math] \Rightarrow [/math] примерное число итераций [math] \log(\genfrac{}{}{}{}{R - L}{\varepsilon}) [/math].
Окончание, когда значение функции на концах отрезках различается менее, чем на заданную погрешность [math] \varepsilon [/math]. Значение функции от найденного значения имеет заданную точность. а) Возможна большая погрешность, если функция будет очень медленно возрастать.
б) Может зациклиться по той же причине, что и в первом способе.
Аналогичная с первым случаем логика, примерное число итераций [math] \log(\genfrac{}{}{}{}{f(R) - f(L)}{\varepsilon}) [/math].
«Абсолютно точный поиск»
Окончание, когда границы отрезка — два соседних по представлению значения в типе данных. Утверждается, что два числа — соседние, если середина их отрезка совпадает или с левой, или с правой границей.
Максимально возможная точность найденного значения. Возможно плохое поведение, если искомый аргумент равен нулю. При работе с числами с плавающей точкой количество итераций зависит от плотности чисел на данном отрезке. При работе с числами фиксированной точности [math]\varepsilon[/math] количество итераций аналогично первому и второму случаю равно [math] \log(\genfrac{}{}{}{}{R - L}{\varepsilon}) [/math].
«Итеративный способ»
Выполнение конечного числа итераций.
У способа фиксированная погрешность. Довольно плохая точность, если границы отрезка находятся на большом расстоянии. Выполняется заданное количество итераций.

Выбор границы отрезка для поиска

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

Псевдокод

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         // Здесь можно использовать другое условие выхода 
        mid = (left + right) / 2
        if f(mid) < C
            left = mid
        else
            right = mid
    return (left + right) / 2

.

Метод секущих

Метод секущих при [math] C = 0 [/math]

Итерационный численный метод приближённого нахождения корня уравнения.

Алгоритм

Пусть нам задана монотонная [math] f [/math] и значение [math] C [/math]. Выберем две начальные точки, причем [math] f(x_{1}) \lt C [/math], а [math] f(x_{2}) \gt C [/math]. Проведем через них прямую, которая пересечет прямую [math] y = C [/math] в точке [math] (x_{3}, C) [/math]. Теперь вместо точек [math] x_{1} [/math] и [math] x_{2} [/math] возьмем точки [math] x_{3} [/math] и [math] x_{2} [/math], и проделаем ту же операцию и так далее, получая точки [math] x_{n+1} [/math] и [math] x_{n} [/math], пока [math] |x_{n-1} - x_{n}| \gt \varepsilon [/math]. Вычисляем каждое последующее значение [math] x_{n+1} [/math] с помощью формулы:

[math] x_{n+1} = x_{n-1} + \dfrac{(C - f(x_{n}))\cdot(x_{n} - x_{n-1})}{f(x_{n}) - f(x_{n-1})} [/math]

Нахождение нулей функции [math](C = 0)[/math]:

[math] x_{n+1} = x_{n-1} - \dfrac{f(x_{n})\cdot(x_{n} - x_{n-1})}{f(x_{n}) - f(x_{n-1})} [/math]

Псевдокод

double search (a : double, b : double, eps : double):         // Где a — левая граница, а b — правая 
    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

Метод Ньютона

Метод Ньютона

Итерационный численный метод нахождения нуля заданной функции.

Алгоритм

Задана монотонная, дифференцируемая функция и начальное значение [math] x_{0} [/math]. Построим касательную к нашей функции в заданной точке и найдем новую точку [math] x_{1} [/math], как пересечения касательной и оси абсцисс. Пока не выполнено заданное условие, например [math] f(x_{n}) \lt \varepsilon [/math], вычисляем новое значение [math] x_{n+1} [/math] по формуле:

[math] x_{n+1} = x_{n} - \dfrac{f(x_{n})}{f'(x_{n})} [/math]

Псевдокод

double search (x : double, eps : double):
    while f(x) > eps
         x = x - f(x) / f'(x)
    return x

Пример

Пусть даны числа [math] C [/math] и [math] n [/math] — число и корень какой степень нам нужно посчитать соответственно. Пусть [math] x = \sqrt[n]{C}[/math]. Возведем все выражение в [math]n[/math]-ую степень и перенесем всё в левую часть, тогда [math] x^n - C = 0 [/math]. То есть нужно найти нуль этого выражения, решим это с помощью метода Ньютона.

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

Замечания

  • Необходимо отметить, то функция должна быть строго монотонна, если мы ищем конкретный корень и он единственный. Нестрого монотонна, если нам необходимо найти самый левый (правый) аргумент. Если же функция не монотонна, то данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным.
  • Классической задачей на вещественный двоичный поиск является задача поиска корня [math]n[/math]-ой степени из числа [math]x[/math]: [math]\sqrt[n]{x}[/math]. При [math]x \geqslant 1[/math] нижней границей для поиска будет [math]1[/math], а верхней — [math]x[/math].

См. также

Источники информации