Метод бисекции

Не следует путать с Двоичный поиск.

Не следует путать с Дихотомия.

Метод бисекции или метод деления отрезка пополам — простейший численный метод для решения нелинейных уравнений вида f(x)=0. Предполагается только непрерывность функции f(x). Поиск основывается на теореме о промежуточных значениях.

Обоснование

Алгоритм основывается на следующем следствии теоремы Больцано — Коши:

Пусть функция $f(x)\in\mathrm{C}([a,\;b])\!$, тогда если $f(a)>0, f(b)\!<0$, то $\exist c\in[a,\;b]:\;f(c)=0$.

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

Если задана точность вычисления $\varepsilon \!$, то процедуру следует продолжать до тех пор, пока длина отрезка не станет меньше $\varepsilon$.

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

Описание алгоритма

Задача заключается в нахождении корней нелинейного уравнения

$f(x)=0. \qquad ( 1 )$

Для начала итераций необходимо знать интервал [x_L,x_R] значений x, на концах которого функция принимает значения разных знаков:

$f(x_L)f(x_R)<0. \qquad ( 2 )$

Из непрерывности функции f и условия (2) следует, что на интервале [x_L,x_R] существует хотя бы один корень уравнения (в случае наличия нескольких корней метод приводит к нахождению одного из них)

Выберем точку внутри интервала

$x_M=(x_R+x_L)/2. \qquad ( 3 )$

Если $f(x_M)=0$, то корень найден. Если $f(x_M)\ne 0$ разобьём интервал [x_L,x_R] на два: [x_L,x_M] и [x_M,x_R]. Теперь найдём новый интервал, в котором функция меняет знак. Пусть $\! f(x_L)f(x_M)<0$ и соответственно корень находится внутри интервала [x_L,x_M]. Тогда обозначим x_R=x_M и повторим описанную процедуру до достижения требуемой точности. За количество итераций N первоначальный отрезок делится в 2^N раз.

Поиск значения монотонной функции

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

Пускай переменные $L_b\,\!$ и $U_b\,\!$ содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются со среднего элемента отрезка. Если искомое значение меньше среднего элемента, осуществляется переход к поиску в верхней половине отрезка, где все элементы меньше только что проверенного, то есть значением $U_b\,\!$ становится $\left( M - 1 \right)\,\!$ и на следующей итерации исследуется только половина массива. Т.о., в результате каждой проверки область поиска сужается вдвое.

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

l = леваяГраница - 1
r = праваяГраница + 1
while (r - l > 1) {
  середина = (l+r) / 2
  if (массив[середина] < значение)
     l = середина
  else
     r = середина
 } 
 if (массив[r] ≠ значение)
   return -1 // элемент не найден
 else
   return r

^{[источник не указан 1004 дня]}

Программный код

• x_n – начало отрезка по х;
• x_k – конец отрезка по х;
• x_i – середина отрезка по х;
• eps – требуемая точность вычислений.

Таким образом, весь алгоритм можно записать следующим образом (в псевдокоде):

1. Начало.
2. Ввод x_n, x_k, eps.
3. Если F(x_n) = 0, то Вывод (корень уравнения – x_n).
4. Если F(x_k) = 0, то Вывод (корень уравнения – x_k).
5. Пока (F(x_i) <> 0) и |x_k-x_n| > eps повторять:
6. xi := (x_k+x_n)/2;
7. если (F(x_n)*F(x_i) < 0), то x_k := x_i;
8. если (F(x_i)*F(x_k) < 0), то x_n := x_i.
9. Вывод (Найден корень уравнения – x_i точности ε).
10. Конец.

Пример реализации алгоритма на языке Matlab^{[источник не указан 476 дней]}

 clear;
 
 %Интервал
 x_L=1;
 x_R=2;
 length=x_R-x_L;
 %Начальная ошибка
 err=length;
 
 %Итерационный цикл
 while err>1e-3
     %Деление отрезка пополам
     x_M=(x_L+x_R)/2;
     %Нахождение нового интервала
     if tan(x_L)*tan(x_M)<0
         x_R=x_M;
     else
         if tan(x_M)*tan(x_R)<0
             x_L=x_M;
         else
             x_M
             break;
         end
     end
     %Пересчёт ошибки
     err=(x_R-x_L)/length;
 end
 %Вывод результата
 x_M
 err

Результат выполнения вполне ожидаемый

 x_M =
 
     1.5713
 
 
 err =
 
   9.7656e-004

См. также

• Линейный поиск
• Двоичный поиск
• Метод дихотомии
• Метод золотого сечения
• Троичный поиск
• Метод Ньютона

Ссылки

• Метод бисекции на сервере применения Mathcad.
• Метод бисекции Mathcad, Maple, Matlab, Mathematica
• Использование метода бисекции в программировании свободно распространяемая программа для вычисления изоэлектрической точки.