Метод бисекции или метод деления отрезка пополам — простейший численный метод для решения нелинейных уравнений вида f(x)=0. Предполагается только непрерывность функции f(x). Поиск основывается на теореме о промежуточных значениях.
Обоснование Алгоритм основан на следующем следствии из теоремы Больцано — Коши:
Таким образом, если мы ищем ноль, то на концах отрезка функция должна быть противоположных знаков. Разделим отрезок пополам и возьмём ту из половинок, на концах которой функция по-прежнему принимает значения противоположных знаков. Если значение функции в серединной точке оказалось искомым нулём, то процесс завершается.
Точность вычислений задаётся одним из двух способов: по оси , что ближе к условию из описания алгоритма; или , по оси , что может оказаться удобным в некоторых случаях. Процедуру следует продолжать до достижения заданной точности.
Для поиска произвольного значения достаточно вычесть из значения функции искомое значение и искать ноль получившейся функции.
Описание алгоритма Задача заключается в нахождении корней нелинейного уравнения
Для начала итераций необходимо знать отрезок значений , на концах которого функция принимает значения противоположных знаков.
Противоположность знаков значений функции на концах отрезка можно определить множеством способов. Один из множества этих способов — умножение значений функции на концах отрезка и определение знака произведения путём сравнения результата умножения с нулём:
в действительных вычислениях такой способ проверки противоположности знаков при крутых функциях приводит к преждевременному переполнению.
Для устранения переполнения и уменьшения затрат времени, то есть для увеличения быстродействия, на некоторых программно-компьютерных комплексах противоположность знаков значений функции на концах отрезка нужно определять по формуле:
так как одна операция сравнения двух знаков двух чисел требует меньшего времени, чем две операции: умножение двух чисел (особенно с плавающей запятой и двойной длины) и сравнение результата с нулём. При данном сравнении, значения функции в точках и можно не вычислять, достаточно вычислить только знаки функции в этих точках, что требует меньшего машинного времени.
Из непрерывности функции и условия (2.2) следует, что на отрезке существует хотя бы один корень уравнения (в случае не монотонной функции функция может иметь несколько корней на отрезке, тогда метод приводит к нахождению одного из них).
Найдём значение в середине отрезка:
в действительных вычислениях, для уменьшения числа операций, в начале, вне цикла, вычисляют длину отрезка по формуле:
а в цикле вычисляют длину очередных новых отрезков по формуле: и новую середину по формуле:
Вычислим значение функции в середине отрезка : Если или, в действительных вычислениях, , где — заданная точность по оси , то корень найден. Иначе или, в действительных вычислениях, , то разобьём отрезок на два равных отрезка: и .
Теперь найдём новый отрезок, на котором функция меняет знак: Если значения функции на концах отрезка имеют противоположные знаки на левом отрезке, или , то, соответственно, корень находится внутри левого отрезка . Тогда возьмём левый отрезок присвоением , и повторим описанную процедуру до достижения требуемой точности по оси . Иначе значения функции на концах отрезка имеют противоположные знаки на правом отрезке, или , то, соответственно, корень находится внутри правого отрезка . Тогда возьмём правый отрезок присвоением , и повторим описанную процедуру до достижения требуемой точности по оси .
За количество итераций деление пополам осуществляется раз, поэтому длина конечного отрезка в раз меньше длины исходного отрезка.
Существует похожий метод, но с критерием останова вычислений по оси Ю. Губарь, Курс "Введение в математическое моделирование" Лекция 4: Численные методы решения нелинейных уравнений: Метод половинного деления // Интуит.ру, 15.03.2007, в этом методе вычисления продолжаются до тех пор, пока, после очередного деления пополам, новый отрезок больше заданной точности по оси : . В этом методе отрезок на оси может достичь заданной величины , а значения функций (особенно крутых) на оси могут очень далеко отстоять от нуля, при пологих же функциях этот метод приводит к большому числу лишних вычислений.
В дискретных функциях и — это номера элементов массива, которые не могут быть дробными, и, в случае второго критерия останова вычислений, разность не может быть меньше .
Псевдокод ;Пусть 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 алгоритм будет выглядеть следующим образом:
# Метод биссекции 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)}")
Поиск значения корня монотонной дискретной функции
Поиск наиболее приближённого к корню значения в монотонной дискретной функции, заданной таблично и записанной в массиве, заключается в разбиении массива пополам (на две части), выборе из двух новых частей той части, в которой значения элементов массива меняют знак путём сравнения знаков срединного элемента массива со знаком граничного значения и повторении алгоритма для половины в которой значения элементов массива меняют знак.
Пусть переменные леваяГраница и праваяГраница содержат, соответственно, левую левГран и правую правГран границы массива, в которой находится приближение к корню. Исследование начинается с разбиения массива пополам (на две части) путём нахождения номера среднего элемента массива середина.
Если знаки значений массива массив[леваяГраница] и массив[середина] противоположны, то приближение к корню ищут в левой половине массива, то есть значением праваяГраница становится середина и на следующей итерации исследуется только левая половина массива. Если знаки значений массив[леваяГраница] и массив[середина] одинаковы, то осуществляется переход к поиску приближения к корню в правой половине массива, то есть значением переменной леваяГраница становится середина и на следующей итерации исследуется только правая половина массива. Т.о., в результате каждой проверки область поиска сужается вдвое.
Например, если длина массива равна 1023, то после первого сравнения область сужается до 511 элементов, а после второго — до 255. Т.о. для поиска приближения к корню в массиве из 1023 элементов достаточно 10 проходов (итераций).
Псевдокод: леваяГраница = левГран праваяГраница = правГран while (праваяГраница - леваяГраница > 1) { длинаОтрезка = правГран - левГран половинаОтрезка = int(длинаОтрезка / 2) середина = леваяГраница + половинаОтрезка if (sign(массив[леваяГраница]) ≠ sign(массив[середина])) праваяГраница = середина else леваяГраница = середина } printf середина
См. также Линейный поиск Двоичный поиск Метод дихотомии Метод золотого сечения Троичный поиск Метод Ньютона
Примечания
Литература
Ссылки
Метод бисекции на сервере применения Mathcad. Метод бисекции Mathcad, Maple, Matlab, Mathematica Использование метода бисекции в программировании свободно распространяемая программа для вычисления изоэлектрической точки.
Категория:Численные методы решения уравнений