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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Обоснование[править | править вики-текст]

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

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

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

Точность вычислений задаётся одним из двух способов:

  1. \varepsilon_{f(x)} по оси y, что ближе к условию f(x)=0 из описания алгоритма; или
  2. \varepsilon_x\!, по оси x, что может оказаться удобным в некоторых случаях.

Процедуру следует продолжать до достижения заданной точности.

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

Описание алгоритма[править | править вики-текст]

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

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

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

Противоположность знаков значений функции на концах отрезка можно определить множеством способов. Один из множества этих способов — умножение значений функции на концах отрезка и определение знака произведения путём сравнения результата умножения с нулём:

f(x_L)\cdot f(x_R)<0, \qquad ( 2.1 )

в действительных вычислениях такой способ проверки противоположности знаков при крутых функциях приводит к преждевременному переполнению.

Для устранения переполнения и уменьшения затрат времени, то есть для увеличения быстродействия, на некоторых программно-компьютерных комплексах противоположность знаков значений функции на концах отрезка нужно определять по формуле:

sign(f(x_L)) \ne sign(f(x_R)), \qquad ( 2.2 )

так как одна операция сравнения двух знаков двух чисел требует меньшего времени, чем две операции: умножение двух чисел (особенно с плавающей запятой и двойной длины) и сравнение результата с нулём. При данном сравнении, значения функции f(x) в точках x_L и x_R можно не вычислять, достаточно вычислить только знаки функции f(x) в этих точках, что требует меньшего машинного времени.

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

Найдём значение x в середине отрезка:

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

в действительных вычислениях, для уменьшения числа операций, в начале, вне цикла, вычисляют длину отрезка по формуле:

x_D=(x_R-x_L),

а в цикле вычисляют длину очередных новых отрезков по формуле: x_D=x_D/2 и новую середину по формуле:

x_M=x_L+x_D.

Вычислим значение функции f(x_M) в середине отрезка x_M:

  • Если f(x_M)=0 или, в действительных вычислениях, |f(x_M)|\leq\varepsilon_{f(x)}, где \varepsilon_{f(x)} — заданная точность по оси y, то корень найден.
  • Иначе f(x_M)\ne 0 или, в действительных вычислениях, |f(x_M)|>\varepsilon_{f(x)}, то разобьём отрезок [x_L,x_R] на два равных отрезка: [x_L,x_M] и [x_M,x_R].

Теперь найдём новый отрезок, на котором функция меняет знак:

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

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

Существует похожий метод, но с критерием останова вычислений \varepsilon_x по оси x[1], в этом методе вычисления продолжаются до тех пор, пока, после очередного деления пополам, новый отрезок больше заданной точности по оси x: (x_R-x_L)>\varepsilon_x. В этом методе отрезок на оси x может достичь заданной величины \varepsilon_x, а значения функций f(x) (особенно крутых) на оси y могут очень далеко отстоять от нуля, при пологих же функциях f(x) этот метод приводит к большому числу лишних вычислений.

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

Псевдокод[править | править вики-текст]

Пусть

  • xn — начало отрезка по х;
  • xk — конец отрезка по х;
  • xi — середина отрезка по х;
  • epsy — требуемая точность вычислений по y (заданное приближение |F(xi)| к нулю).

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

  1. Начало.
  2. Ввод xn, xk, epsy.
  3. Если F(xn) = 0, то Вывод (корень уравнения — xn).
  4. Если F(xk) = 0, то Вывод (корень уравнения — xk).
  5. dx := xk — xn.
  6. Пока |F(xi)| > epsy повторять:
  7. dx := dx / 2;
  8. xi := xn + dx;
  9. если sign(F(xn)) ≠ sign(F(xi)), то xk := xi;
  10. иначе xn := xi.
  11. конец повторять
  12. Вывод (Найден корень уравнения — xi с точностью по y — epsy).
  13. Конец.

Поиск значения корня монотонной дискретной функции[править | править вики-текст]

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

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

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

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

Псевдокод:[источник не указан 1976 дней]

леваяГраница = левГран
праваяГраница = правГран
while (праваяГраница - леваяГраница > 1) {
   длинаОтрезка = правГран - левГран
   половинаОтрезка = int(длинаОтрезка / 2) 
   середина = леваяГраница + половинаОтрезка
   if (sign(массив[леваяГраница]) ≠ sign(массив[середина]))
      праваяГраница = середина
   else
      леваяГраница = середина
}
printf середина

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

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

  • Волков Е. А. Глава 4. Методы решения нелинейных уравнений и систем. § 26. Метод деления отрезка пополам // Численные методы. — Учеб. пособие для вузов. — 2-е изд., испр.. — М.: Наука, 1987. — С. 190. — 248 с.

Ссылки[править | править вики-текст]