Редактирование: Вещественный двоичный поиск

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 2: Строка 2:
  
 
== Формулировка задачи ==  
 
== Формулировка задачи ==  
Пусть нам задана монотонная функция <tex> f </tex> и какое-то значение <tex> C </tex> этой функции. Необходимо найти значение аргумента <tex> x </tex> этой функции, такое, что <tex> f(x) = C </tex>.
+
Пусть нам задана монотонная функция. Необходимо найти значение аргумента <tex>x</tex> этой функции, в которой она принимает определенное значение <tex>C</tex> = ''valOfFunc''.
  
 
[[Файл:Function.png]]
 
[[Файл:Function.png]]
Строка 17: Строка 17:
 
| Окончание, когда значение функции на концах отрезках различается менее, чем на заданную погрешность <tex> \varepsilon </tex>. || Значение функции от найденного значения имеет заданную точность. || а) Возможна большая погрешность, если функция будет очень медленно возрастать. <br> б) Может зациклиться по той же причине, что и в первом способе. || Аналогичная с первым случаем логика, примерное число итераций <tex dpi=130> \log(\genfrac{}{}{}{}{f(R) - f(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>\varepsilon</tex>) количество итераций аналогично первому и второму случаю равно <tex dpi=130> \log(\genfrac{}{}{}{}{R - L}{\varepsilon}) </tex>.
 
|-
 
|-
 
| «Итеративный способ» <br> Выполнение конечного числа итераций. || У способа фиксированная погрешность. || Довольно плохая точность, если границы отрезка находятся на большом расстоянии. || Выполняется заданное количество итераций.
 
| «Итеративный способ» <br> Выполнение конечного числа итераций. || У способа фиксированная погрешность. || Довольно плохая точность, если границы отрезка находятся на большом расстоянии. || Выполняется заданное количество итераций.
Строка 26: Строка 26:
  
 
== Псевдокод ==
 
== Псевдокод ==
  '''double''' findLeftBoard(C : '''double'''):  
+
<code>
 +
  '''double''' findLeftBoard(valueOfFunc : '''double'''):  
 
     x = -1
 
     x = -1
     '''while''' f(x) > C
+
     '''while''' f(x) > valueOfFunc
 
         x = x * 2
 
         x = x * 2
 
     '''return''' x  
 
     '''return''' x  
 
+
</code>
.
+
<code>
 
+
  '''double''' findRightBoard(valueOfFunc : '''double'''):
  '''double''' findRightBoard(C : '''double'''):
 
 
     x = 1
 
     x = 1
     '''while''' f(x) < C
+
     '''while''' f(x) < valueOfFunc
 
         x = x * 2
 
         x = x * 2
 
     '''return''' x
 
     '''return''' x
.
+
</code>
 
+
<code>
  '''double''' binSearch(C : '''double'''):
+
  '''double''' binSearch(valueOfFunc : '''double'''):
     left = findLeftBoard(C)
+
     left = findLeftBoard(valueOfFunc)
     right = findRightBoard(C)
+
     right = findRightBoard(valueOfFunc)
 
     '''while''' right - left < eps        <font color=green> // Здесь можно использовать другое условие выхода </font>
 
     '''while''' right - left < eps        <font color=green> // Здесь можно использовать другое условие выхода </font>
 
         mid = (left + right) / 2
 
         mid = (left + right) / 2
         '''if''' f(mid) < C
+
         '''if''' f(mid) < valueOfFunc
 
             left = mid
 
             left = mid
 
         '''else'''
 
         '''else'''
 
             right = mid
 
             right = mid
 
     '''return''' (left + right) / 2
 
     '''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>
 
</code>
  
Строка 110: Строка 57:
 
* Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x \geqslant 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней {{---}} <tex>x</tex>.
 
* Классической задачей на вещественный двоичный поиск является задача поиска корня <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/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]
+
* [http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch Binary search - Topcoder]
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Алгоритмы поиска]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: