- Метод бисекции
-
Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей.Не следует путать с Двоичный поиск.Не следует путать с Дихотомия.Метод бисекции или метод деления отрезка пополам — простейший численный метод для решения нелинейных уравнений вида f(x)=0. Предполагается только непрерывность функции f(x). Поиск основывается на теореме о промежуточных значениях.
Содержание
Обоснование
Алгоритм основан на следующем следствии из теоремы Больцано — Коши:
Пусть непрерывная функция , тогда, если
, то
.
Таким образом, если мы ищем ноль, то на концах отрезка функция должна быть противоположных знаков. Разделим отрезок пополам и возьмём ту из половинок, на концах которой функция по-прежнему принимает значения противоположных знаков. Если значение функции в серединной точке оказалось искомым нулём, то процесс завершается.
Точность вычислений задаётся одним из двух способов:по оси
, что ближе к условию
из описания алгоритма; или
, по оси
, что может оказаться удобным в некоторых случаях.
Процедуру следует продолжать до достижения заданной точности.
Для поиска произвольного значения достаточно вычесть из значения функции искомое значение и искать ноль получившейся функции.
Описание алгоритма
Задача заключается в нахождении корней нелинейного уравнения
Для начала итераций необходимо знать отрезок
значений
, на концах которого функция принимает значения противоположных знаков.
Противоположность знаков значений функции на концах отрезка можно определить множеством способов. Один из множества этих способов — умножение значений функции на концах отрезка и определение знака произведения путём сравнения результата умножения с нулём:
в действительных вычислениях такой способ проверки противоположности знаков при крутых функциях приводит к преждевременному переполнению.
Для устранения переполнения и уменьшения затрат времени, т.е. для увеличения быстродействия, на некоторых программно-компьютерных комплексах противоположность знаков значений функции на концах отрезка нужно определять по формуле:
так как одна операция сравнения двух знаков двух чисел требует меньшего времени, чем две операции: умножение двух чисел (особенно с плавающей запятой и двойной длины) и сравнение результата с нулём. При данном сравнении, значения функции
в точках
и
можно не вычислять, достаточно вычислить только знаки функции
в этих точках, что требует меньшего машинного времени.
Из непрерывности функции
и условия (2.2) следует, что на отрезке
существует хотя бы один корень уравнения (в случае не монотонной функции
функция имеет несколько корней и метод приводит к нахождению одного из них).
Найдём значение
в середине отрезка:
в действительных вычислениях, для уменьшения числа операций, в начале, вне цикла, вычисляют длину отрезка по формуле:
а в цикле вычисляют длину очередных новых отрезков по формуле:
и новую середину по формуле:
Вычислим значение функции
в середине отрезка
:
- Если
или, в действительных вычислениях,
, где
— заданная точность по оси
, то корень найден.
- Иначе
или, в действительных вычислениях,
, то разобьём отрезок
на два равных отрезка:
и
.
Теперь найдём новый отрезок, на котором функция меняет знак:
- Если значения функции на концах отрезка имеют противоположные знаки на левом отрезке,
или
, то, соответственно, корень находится внутри левого отрезка
. Тогда возьмём левый отрезок присвоением
, и повторим описанную процедуру до достижения требуемой точности
по оси
.
- Иначе значения функции на концах отрезка имеют противоположные знаки на правом отрезке,
или
, то, соответственно, корень находится внутри правого отрезка
. Тогда возьмём правый отрезок присвоением
, и повторим описанную процедуру до достижения требуемой точности
по оси
.
За количество итераций
деление пополам осуществляется
раз, поэтому длина конечного отрезка в
раз меньше длины исходного отрезка.
Существует похожий метод, но с критерием останова вычислений
по оси
[1], в этом методе вычисления продолжаются до тех пор, пока, после очередного деления пополам, новый отрезок больше заданной точности по оси
:
. В этом методе отрезок на оси
может достичь заданной величины
, а значения функций
(особенно крутых) на оси
могут очень далеко отстоять от нуля, при пологих же функциях
этот метод приводит к большому числу лишних вычислений.
В дискретных функциях
и
- это номера элементов массива, которые не могут быть дробными, и, в случае второго критерия останова вычислений, разность
не может быть меньше
.
Псевдокод
Пусть
- xn – начало отрезка по х;
- xk – конец отрезка по х;
- xi – середина отрезка по х;
- epsy – требуемая точность вычислений по y (заданное приближение |F(xi)| к нулю).
Тогда алгоритм метода бисекции можно записать в псевдокоде следующим образом:
- Начало.
- Ввод xn, xk, epsy.
- Если F(xn) = 0, то Вывод (корень уравнения – xn).
- Если F(xk) = 0, то Вывод (корень уравнения – xk).
- Пока |F(xi)| > epsy повторять:
- dx := (xk - xn) / 2;
- xi := xn + dx;
- если sign(F(xn)) ≠ sign(F(xi)), то xk := xi;
- иначе xn := xi.
- конец повторять
- Вывод (Найден корень уравнения – xi с точностью по y - epsy).
- Конец.
Поиск значения корня монотонной дискретной функции
Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей.Поиск наиболее приближённого к корню значения в монотонной дискретной функции, заданной таблично и записанной в массиве, заключается в разбиении массива пополам (на две части), выборе из двух новых частей той части, в которой значения элементов массива меняют знак путем сравнения знаков срединного элемента массива со знаком граничного значения и повторении алгоритма для половины в которой значения элементов массива меняют знак.
Пусть переменные леваяГраница и праваяГраница содержат, соответственно, левую левГран и правую правГран границы массива, в которой находится приближение к корню. Исследование начинается с разбиения массива пополам (на две части) путём нахождения номера среднего элемента массива середина.
Если знаки значений массива массив[леваяГраница] и массив[середина] противоположны, то приближение к корню ищут в левой половине массива, то есть значением праваяГраница становится середина и на следующей итерации исследуется только левая половина массива. Если знаки значений массив[леваяГраница] и массив[середина] одинаковы, то осуществляется переход к поиску приближения к корню в правой половине массива, то есть значением переменной леваяГраница становится середина и на следующей итерации исследуется только правая половина массива. Т.о., в результате каждой проверки область поиска сужается вдвое.
Например, если длина массива равна 1023, то после первого сравнения область сужается до 511 элементов, а после второго — до 255. Т.о. для поиска приближения к корню в массиве из 1023 элементов достаточно 10 проходов (итераций).
леваяГраница = левГран праваяГраница = правГран длинаОтрезка = правГран - левГран while (праваяГраница - леваяГраница > 1) { половинаОтрезка = int(длинаОтрезка / 2) середина = леваяГраница + половинаОтрезка if (sign(массив[леваяГраница]) ≠ sign(массив[середина])) праваяГраница = середина else леваяГраница = середина } printf середина
См. также
Примечания
Литература
- Волков Е. А. Глава 4. Методы решения нелинейных уравнений и систем. § 26. Метод деления отрезка пополам // Численные методы. — Учеб. пособие для вузов. — 2-е изд., испр.. — М.: Наука, 1987. — С. 190. — 248 с.
Ссылки
- Метод бисекции на сервере применения Mathcad.
- Метод бисекции Mathcad, Maple, Matlab, Mathematica
- Использование метода бисекции в программировании свободно распространяемая программа для вычисления изоэлектрической точки.
Категории:- Численные методы
- Вычислительная математика
Wikimedia Foundation. 2010.