imported>Eoan Ermine: /* Псевдокод */

2025-05-18T18:11:37Z

Псевдокод

Новая страница

{{distinguish|Двоичный поиск}}
{{distinguish|Дихотомия}}
[[Image:Bisection method.svg|250px|thumb|Несколько шагов метода деления пополам применяются к начальному диапазону [a1;b1]. Большая красная точка — это корень функции.]]
'''Метод бисекции''' или '''метод деления [[отрезок|отрезка]] пополам''' — простейший [[численные методы|численный метод]] для решения [[нелинейные уравнения|нелинейных уравнений]] вида ''f''(''x'')=0. Предполагается только непрерывность функции ''f''(''x''). Поиск основывается на [[теорема о промежуточных значениях|теореме о промежуточных значениях]].

== Обоснование ==
Алгоритм основан на следующем следствии из [[Теорема Больцано — Коши|теоремы Больцано — Коши]]:

{{теорема|1=Пусть [[непрерывная функция]] <math>f(x)\in\mathrm{C}([a,\;b])</math>, тогда, если <math>sign(f(a)) \ne sign(f(b))</math>, то <math>\exist c\in[a,\;b]:\;f(c)=0</math>.}}

Таким образом, если мы ищем ноль, то на концах отрезка функция должна быть противоположных знаков. Разделим отрезок пополам и возьмём ту из половинок, на концах которой функция по-прежнему принимает значения противоположных знаков. Если значение функции в серединной точке оказалось искомым нулём, то процесс завершается.

Точность вычислений задаётся одним из двух способов:
# <math>\varepsilon_{f(x)}</math> по оси <math>y</math>, что ближе к условию <math>f(x)=0</math> из описания алгоритма; или
# <math>\varepsilon_x</math>, по оси <math>x</math>, что может оказаться удобным в некоторых случаях.
Процедуру следует продолжать до достижения заданной точности.

Для поиска произвольного значения достаточно вычесть из значения функции искомое значение и искать ноль получившейся функции.

== Описание алгоритма ==
Задача заключается в нахождении корней [[нелинейные уравнения|нелинейного уравнения]]
<center><math>f(x)=0. \qquad ( 1 )</math></center>
Для начала итераций необходимо знать отрезок <math>[x_L,x_R]</math> значений <math>x</math>, на концах которого функция принимает значения противоположных знаков.

Противоположность знаков значений функции на концах отрезка можно определить множеством способов. Один из множества этих способов — умножение значений функции на концах отрезка и определение знака произведения путём сравнения результата умножения с нулём:
<center><math>f(x_L)\cdot f(x_R)<0, \qquad ( 2.1 )</math></center>
в действительных вычислениях такой способ проверки противоположности знаков при крутых функциях приводит к преждевременному [[Арифметическое переполнение|переполнению]].

Для устранения переполнения и уменьшения затрат времени, то есть для увеличения быстродействия, на некоторых программно-компьютерных комплексах противоположность знаков значений функции на концах отрезка нужно определять по формуле:
<center><math>sign(f(x_L)) \ne sign(f(x_R)), \qquad ( 2.2 )</math></center>
так как одна операция сравнения двух знаков двух чисел требует меньшего времени, чем две операции: умножение двух чисел (особенно с плавающей запятой и двойной длины) и сравнение результата с нулём. При данном сравнении, значения функции <math>f(x)</math> в точках <math>x_L</math> и <math>x_R</math> можно не вычислять, достаточно вычислить только знаки функции <math>f(x)</math> в этих точках, что требует меньшего машинного времени.

Из непрерывности функции <math>f(x)</math> и условия (2.2) следует, что на отрезке <math>[x_L,x_R]</math> существует хотя бы один корень уравнения (в случае не [[Монотонная функция|монотонной функции]] <math>f(x)</math> функция может иметь несколько корней на отрезке, тогда метод приводит к нахождению одного из них).

Найдём значение <math>x</math> в середине отрезка:
<center><math>x_M=(x_L+x_R)/2, \qquad ( 3 )</math></center>
в действительных вычислениях, для уменьшения числа операций, в начале, вне цикла, вычисляют длину отрезка по формуле:
: <math>x_D=(x_R-x_L),</math>
а в цикле вычисляют длину очередных новых отрезков по формуле: <math>x_D=x_D/2</math> и новую середину по формуле:
: <math>x_M=x_L+x_D.</math>
Вычислим значение функции <math>f(x_M)</math> в середине отрезка <math>x_M</math>:
* Если <math>f(x_M)=0</math> или, в действительных вычислениях, <math>|f(x_M)|\leq\varepsilon_{f(x)}</math>, где <math>\varepsilon_{f(x)}</math> — заданная точность по оси <math>y</math>, то корень найден.
* Иначе <math>f(x_M)\ne 0</math> или, в действительных вычислениях, <math>|f(x_M)|>\varepsilon_{f(x)}</math>, то разобьём отрезок <math>[x_L,x_R]</math> на два равных отрезка: <math>[x_L,x_M]</math> и <math>[x_M,x_R]</math>.

Теперь найдём новый отрезок, на котором функция меняет знак:
* Если значения функции на концах отрезка имеют противоположные знаки на левом отрезке, <math>f(x_L)\cdot f(x_M)<0</math> или <math>sign(f(x_L)) \ne sign(f(x_M))</math>, то, соответственно, корень находится внутри левого отрезка <math>[x_L,x_M]</math>. Тогда возьмём левый отрезок присвоением <math>x_R=x_M</math>, и повторим описанную процедуру до достижения требуемой точности <math>\varepsilon_{f(x)}</math> по оси <math>y</math>.
* Иначе значения функции на концах отрезка имеют противоположные знаки на правом отрезке, <math>f(x_M)\cdot f(x_R)<0</math> или <math>sign(f(x_M)) \ne sign(f(x_R))</math>, то, соответственно, корень находится внутри правого отрезка <math>[x_M,x_R]</math>. Тогда возьмём правый отрезок присвоением <math>x_L=x_M</math>, и повторим описанную процедуру до достижения требуемой точности <math>\varepsilon_{f(x)}</math> по оси <math>y</math>.

За количество итераций <math>N</math> деление пополам осуществляется <math>N</math> раз, поэтому длина конечного отрезка в <math>2^N</math> раз меньше длины исходного отрезка.

Существует похожий метод, но с критерием останова вычислений <math>\varepsilon_x</math> по оси <math>x</math><ref>Ю. Губарь, [http://www.intuit.ru/studies/courses/2260/156/lecture/2284?page=2#sect2 Курс "Введение в математическое моделирование" Лекция 4: Численные методы решения нелинейных уравнений]: Метод половинного деления // [[Интуит.ру]], 15.03.2007</ref>, в этом методе вычисления продолжаются до тех пор, пока, после очередного деления пополам, новый отрезок больше заданной точности по оси <math>x</math>: <math>(x_R-x_L)>\varepsilon_x</math>. В этом методе отрезок на оси <math>x</math> может достичь заданной величины <math>\varepsilon_x</math>, а значения функций <math>f(x)</math> (особенно крутых) на оси <math>y</math> могут очень далеко отстоять от нуля, при пологих же функциях <math>f(x)</math> этот метод приводит к большому числу лишних вычислений.

В дискретных функциях <math>x_L, x_M</math> и <math>x_R</math> — это номера элементов массива, которые не могут быть дробными, и, в случае второго критерия останова вычислений, разность <math>(x_R-x_L)</math> не может быть меньше <math>\varepsilon_x=1</math>.

== Псевдокод ==
<nowiki>;</nowiki>Пусть
* xn — начало отрезка по х;
* xk — конец отрезка по х;
* xi — середина отрезка по х;
* epsy — требуемая точность вычислений по y (заданное приближение интервала [xn; xk] : xk — xn к нулю).

Тогда алгоритм метода бисекции можно записать в [[Псевдокод (язык описания алгоритмов)|псевдокоде]] следующим образом:

# Начало.
# Ввод xn, xk, epsy.
# Если F(xn) = 0, то Вывод (корень уравнения — xn).
# Если F(xk) = 0, то Вывод (корень уравнения — xk).
# Пока xk — xn > epsy повторять:
# dx := (xk — xn)/2;
# xi := xn + dx;
# если sign(F(xn)) ≠ sign(F(xi)), то xk := xi;
# иначе xn := xi.
# конец повторять
# Вывод (Найден корень уравнения — xi с точностью по y — epsy).
# Конец.

На языке программирования [[Python]] алгоритм будет выглядеть следующим образом:

<pre>
# Метод биссекции
def F(dx):
return dx**2 - 6*dx + 8
xn = 0
xk = 10
epsy = 0.01
print (xn, xk, epsy)
if F(xn) == 0:
print (f"xn")
exit()
if F(xk) == 0:
print (f"xk")
exit()
while xk - xn > epsy:
dx = (xk - xn)/2;
xi = xn + dx;
if (F(xn)<0 and F(xi)>0)or (F(xn)>0 and F(xi)<0):
xk = xi
else:
xn = xi
print (f"Найден корень уравнения — xi: {xi}")
print (f"Найден c точностью по y — epsy: {F(xi)}")
</pre>

== Поиск значения корня монотонной дискретной функции ==
{{переработать раздел|дата=2012-05-03}}
Поиск наиболее приближённого к корню значения в монотонной дискретной функции, заданной таблично и записанной в массиве, заключается в разбиении массива пополам (на две части), выборе из двух новых частей той части, в которой значения элементов массива меняют знак путём сравнения знаков срединного элемента массива со знаком граничного значения и повторении алгоритма для половины в которой значения элементов массива меняют знак.

Пусть [[Переменная (программирование)|переменные]] ''леваяГраница'' и ''праваяГраница'' содержат, соответственно, левую ''левГран'' и правую ''правГран'' границы массива, в которой находится приближение к корню. Исследование начинается с разбиения массива пополам (на две части) путём нахождения номера среднего элемента массива ''середина''.

Если знаки значений массива ''массив[леваяГраница]'' и ''массив[середина]'' противоположны, то приближение к корню ищут в левой половине массива, то есть значением ''праваяГраница'' становится ''середина'' и на следующей итерации исследуется только левая половина массива.
Если знаки значений ''массив[леваяГраница]'' и ''массив[середина]'' одинаковы, то осуществляется переход к поиску приближения к корню в правой половине массива, то есть значением переменной ''леваяГраница'' становится ''середина'' и на следующей итерации исследуется только правая половина массива.
Т.о., в результате каждой проверки область поиска сужается вдвое.

Например, если длина массива равна 1023, то после первого сравнения область сужается до 511 элементов, а после второго — до 255. Т.о. для поиска приближения к корню в массиве из 1023 элементов достаточно 10 проходов (итераций).

[[Псевдокод (язык описания алгоритмов)|Псевдокод]]:
<source lang="C">
леваяГраница = левГран
праваяГраница = правГран
while (праваяГраница - леваяГраница > 1) {
длинаОтрезка = правГран - левГран
половинаОтрезка = int(длинаОтрезка / 2)
середина = леваяГраница + половинаОтрезка
if (sign(массив[леваяГраница]) ≠ sign(массив[середина]))
праваяГраница = середина
else
леваяГраница = середина
}
printf середина
</source>

== См. также ==
* [[Линейный поиск]]
* [[Двоичный поиск]]
* [[Метод дихотомии]]
* [[Метод золотого сечения]]
* [[Троичный поиск]]
* [[Метод Ньютона]]

== Примечания ==
{{примечания}}

== Литература ==
* {{книга |автор=Волков Е. А. |заглавие=Численные методы |издание=Учеб. пособие для вузов. — 2-е изд., испр. |место={{М.}} |издательство=Наука |год=1987 |страниц=248 |часть=Глава 4. Методы решения нелинейных уравнений и систем. § 26. Метод деления отрезка пополам |страницы=190}}
* {{Citation | last1=Burden | first1=Richard L. | last2=Faires | first2=J. Douglas | title=Numerical Analysis | publisher=PWS Publishers | edition=3rd | isbn=0-87150-857-5 | year=1985 | chapter=2.1 The Bisection Algorithm | url-access=registration | url=https://archive.org/details/numericalanalys00burd }}

== Ссылки ==
{{Викиучебник|Программные реализации метода бисекции|Программные реализации метода бисекции}}

*[http://twt.mpei.ac.ru/mas/worksheets/Bisection.mcd Метод бисекции] на сервере применения Mathcad.
* [http://numericalmethods.eng.usf.edu/topics/bisection_method.html Метод бисекции] Mathcad, Maple, Matlab, Mathematica
* [https://web.archive.org/web/20130429005222/http://isoelectric.ovh.org/ Использование метода бисекции в программировании] свободно распространяемая программа для вычисления [[изоэлектрическая точка|изоэлектрической точки]].

[[Категория:Численные методы решения уравнений]]

Метод бисекции - История изменений

imported>Eoan Ermine: /* Псевдокод */