Сегодня речь пойдет о численном методе поиска корня уравнения. Для этого мы будем использовать итеративный метод, который основан на делении отрезка на две части, которые в дальнейшем подвергаются анализу.
Пусть дана функция f(x), которая непрерывна на произвольном отрезке исследования [a,b]. При этом функция должна принимать на концах отрезка [a,b] значения разных знаков (см. теорему Больцано — Коши). Тогда, на отрезке [a,b] находится по меньшей мере один корень.
В первом же пункте мы оговорим важную деталь, а именно количество корней на отрезке исследования [a,b]. Мы должны самостоятельно выделить произвольный отрезок на котором находится один корень и значение функции на краях отрезка различного знака. В таких случаях произносят сокровенную фразу: "Графически отделим корни уравнения", а именно попытаемся построить примерный график функции и выбрать необходимые нам интервалы.
Все наши исследования будут основываться на теореме Больцано — Коши, которая утверждает, что если функция f(x) непрерывна на отрезке [a,b] и на концах отрезков функция принимает значения разных знаков (f(a)<0<f(b) или f(b)<0<f(b)), то существует по крайней мере одна точка, в которой функция обращается в ноль.
Примечание: Теорема Больцано — Коши утверждает, что функция, непрерывная на отрезке, принимает все промежуточные значения.
Необходимые знания
Для дальнейшего диалога нам потребуется вспомнить основные моменты из геометрии, а именно:
- Длина отрезка [a,b] — L = (b - a)
- Середина отрезка [a,b] — M = (a + b)/2
Возьмем отрезок разбиения [a,b], такой, что f(a)<0<f(b) (или f(b)<0<f(a)). До тех пор пока длина отрезка [a,b]>2eps будем выполнять циклично следующие операции:
#include <iostream> using namespace std; double f(double x){ return x*x+2*x-3; } int main(){ double a = 0, b = 4, c = 0, eps = 0.01; while( (b-a)>2*eps ){ c = (a+b)/2; if (f(c)==0) break; if (f(a)*f(c)<0) b = c; else a = c; } cout << "x=" << c; return 0; }
var a,b,c,eps:real; function f(x:real):real; begin f := x*x+2*x-3; end; begin a := 0; b := 4; while ((b-a)>2*eps) do begin c := (a+b)/2; if (f(c)=0) then break; if (f(a)*f(c)<0) then b := c else a := c; end; writeln('x=',c); end.
Исходный код: bisection_method.nb
Зачастую, при описании этого алгоритма, жертвуют проверкой F(c)=0, а эта небольшая оплошность может привести к некорректной работе алгоритма. Если в нашем примере убрать проверку на F(c)=0, то на отрезке [0,4] значение корня уравнения f(x)=x^2+2x-3 будет стремиться к двум. (трассировка некорректного алгоритма.pdf)
В случае выполнения условий, описанных ранее, справедлива следующая оценка:
(xn - приближение к корню x с заданной eps, а n - число шагов метода).
Число шагов метода можно получить из формулы |xn-x|<=eps, а так как (b-a)/2^(n+1)<=eps, то получаем неравенство:
© EduNow.su — материалы подлежат полному/частичному копированию при указании прямой ссылки на источник. (Сегодня 22.04.18)