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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Замечания)
 
(не показано 45 промежуточных версий 6 участников)
Строка 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]]
Строка 9: Строка 9:
 
Применим идею [[целочисленный двоичный поиск | двоичного поиска]]. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.
 
Применим идею [[целочисленный двоичный поиск | двоичного поиска]]. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.
  
== Способы закончить поиск ==
+
=== Способы закончить поиск ===
 
{| class="wikitable"
 
{| class="wikitable"
 
! Способы || Плюсы || Минусы || Оценка на число итераций
 
! Способы || Плюсы || Минусы || Оценка на число итераций
 
|-
 
|-
| Окончание, когда рассматриваемый отрезок станет меньше заданной погрешности <tex> \varepsilon </tex>. || Заданная точность найденного значения. || Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел, у которых есть точность. При больших значениях функции длина отрезка может никогда не уменьшиться до заданного значения. || В данном случае нам нужно рассмотреть <tex> (L-R)/\varepsilon </tex> чисел <tex> \Rightarrow </tex> примерное число итераций <tex> \log((L-R)/\varepsilon) </tex>.
+
| Окончание, когда рассматриваемый отрезок станет меньше заданной погрешности <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> \log((f(L)-f(R))/\varepsilon) </tex>.
+
| Окончание, когда значение функции на концах отрезках различается менее, чем на заданную погрешность <tex> \varepsilon </tex>. || Значение функции от найденного значения имеет заданную точность. || а) Возможна большая погрешность, если функция будет очень медленно возрастать. <br> б) Может зациклиться по той же причине, что и в первом способе. || Аналогичная с первым случаем логика, примерное число итераций <tex dpi=130> \log(\genfrac{}{}{}{}{f(R) - f(L)}{\varepsilon}) </tex>.
 
|-
 
|-
| «Абсолютно точный поиск» <br> Окончание, когда границы отрезка — два соседних по представлению значения в типе данных. Утверждается, что два числа — соседние, если середина их отрезка совпадает или с левой, или с правой границей. || Максимально возможная точность найденного значения. || Возможно плохое поведение, если искомый аргумент равен нулю. || При работе с числами с плавающей точкой количество итераций зависит от плотности чисел на данном отрезке. При работе с числами фиксированной точности     (= <tex>\varepsilon</tex>) количество итераций аналогично первому и второму случаю равно <tex> \log((L-R)/\varepsilon) </tex>.
+
| «Абсолютно точный поиск» <br> Окончание, когда границы отрезка — два соседних по представлению значения в типе данных. Утверждается, что два числа — соседние, если середина их отрезка совпадает или с левой, или с правой границей. || Максимально возможная точность найденного значения. || Возможно плохое поведение, если искомый аргумент равен нулю. || При работе с числами с плавающей точкой количество итераций зависит от плотности чисел на данном отрезке. При работе с числами фиксированной точности <tex>\varepsilon</tex> количество итераций аналогично первому и второму случаю равно <tex dpi=130> \log(\genfrac{}{}{}{}{R - L}{\varepsilon}) </tex>.
 
|-
 
|-
 
| «Итеративный способ» <br> Выполнение конечного числа итераций. || У способа фиксированная погрешность. || Довольно плохая точность, если границы отрезка находятся на большом расстоянии. || Выполняется заданное количество итераций.
 
| «Итеративный способ» <br> Выполнение конечного числа итераций. || У способа фиксированная погрешность. || Довольно плохая точность, если границы отрезка находятся на большом расстоянии. || Выполняется заданное количество итераций.
 
|}
 
|}
  
== Выбор границы отрезка для поиска==
+
=== Выбор границы отрезка для поиска ===
Для начала найдем правую границу. Выберем произвольную положительную точку (например <tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.
+
Для начала найдем левую границу, выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения. Для того, чтобы найти правую границу, выберем произвольную положительную точку (например <tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного.
  
 
== Псевдокод ==
 
== Псевдокод ==
<code>
+
'''double''' findLeftBoard(C : '''double'''):
  findRight('''double''' c):
+
    x = -1
 +
    '''while''' f(x) > C
 +
        x = x * 2
 +
    '''return''' x
 +
 
 +
.
 +
 
 +
  '''double''' findRightBoard(C : '''double'''):
 
     x = 1
 
     x = 1
     '''while''' f(x) < c
+
     '''while''' f(x) < C
 
         x = x * 2
 
         x = x * 2
 
     '''return''' x
 
     '''return''' x
</code>
+
.
<code>
+
 
  findLeft('''double''' c):
+
  '''double''' binSearch(C : '''double'''):
    x = -1
+
     left = findLeftBoard(C)
    '''while''' f(x) > c
+
     right = findRightBoard(C)
        x = x * 2
+
     '''while''' right - left < eps       <font color=green> // Здесь можно использовать другое условие выхода </font>
    '''return''' x
 
</code>
 
<code>
 
binSearch('''double''' c):
 
     left = '''findLeft'''(с)
 
     right = '''findRight'''(с)
 
     '''while''' left < right - eps                           <font color=green> //Здесь можно использовать другое условие выхода </font>
 
 
         mid = (left + right) / 2
 
         mid = (left + right) / 2
         '''if''' f(mid) == c                                <font color=green> //** </font>
+
         '''if''' f(mid) < C
            '''return''' mid                                <font color=green> //** </font>
 
        '''else if''' f(mid) < c
 
 
             left = mid
 
             left = mid
 
         '''else'''
 
         '''else'''
 
             right = mid
 
             right = mid
     '''return''' left
+
     '''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>
 
</code>
  
== Примеры использования ==
+
=== Пример ===
* Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x \ge 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней {{---}} <tex>x</tex>.
+
Пусть даны числа <tex> C </tex> и <tex> n </tex> {{---}} число и корень какой степень нам нужно посчитать соответственно. Пусть <tex> x = \sqrt[n]{C}</tex>. Возведем все выражение в <tex>n</tex>-ую степень и перенесем всё в левую часть, тогда <tex> x^n - C = 0 </tex>. То есть нужно найти нуль этого выражения, решим это с помощью метода Ньютона.
* Если функция нестрого монотонна, то, убрав из приведенного выше алгоритма строки, отмеченные <tex>(**)</tex>, мы получим алгоритм, который будет находить <tex>x</tex> такой, что <tex>f(x) = c</tex> и <tex>f(x - \varepsilon) < c</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>1</tex>, а верхней {{---}} <tex>x</tex>.
 +
 +
== См. также ==
 +
* [[Целочисленный двоичный поиск]]
  
== Источники информации ==  
+
== Источники информации ==
 +
* [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://www.youtube.com/watch?v=qkLLcdgJj_o Видеолекция "сортировка и поиск"]
 +
* [http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch Binary search {{---}} Topcoder]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Алгоритмы поиска]]

Текущая версия на 14:35, 17 мая 2018

Вещественный двоичный поиск (англ. 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].

См. также[править]

Источники информации[править]