Пусть найдены такие точки t0 и t1, что , то есть на отрезке [t0,t1] лежит не менее одного корня уравнения .
Найдем середину отрезка и вычислим . Из двух половин отрезка выберем ту, для которой . Эту половину делим пополам и выбираем ту половину, на концах которой функция имеет разные знаки.
Если требуется найти корень с точностью e, то продолжаем деление пополам до тех пор, пока длина отрезка не станет меньше 2e. Тогда середина последнего отрезка даст значение корня с требуемой точностью.
Дихотомия проста и очень надежна: к простому корню она сходится для любых непрерывных функций , в том числе недифференцируемых. Дихотомия устойчива к ошибкам округления, скорость сходимости невелика: за одну итерацию точность увеличивается примерно вдвое, то есть уточнение трех цифр требует 10 итераций (210~1000). Но точность результата гарантируется.
Недостатки метода:
Для начала вычислений надо найти отрезок, на котором функция меняет знак;
Если в этом отрезке несколько корней, то неизвестно, к какому из них сойдется процесс;
|
|
На системы уравнений дихотомия не обобщается.
Пример. Решить уравнение с точностью до e = 0.1.
Построим график функции :
Из графика следует, что уравнение имеет единственный корень вблизи t=2. Поэтому выберем отрезок [1.5,2], на концах которого функция меняет знак.
f(t0)<0, f(t1)>0, t0=1.5, t1=2, t2=(1.5+2)/2=1.75
f(t2)=f(1.75)=-0.308<0;
f(t2)<0, f(t1)>0, t2=1.75, t1=2, длина отрезка 0.25, t3=(1.75+2)/2=1.88
f(t3)=f(1.88)=0.019>0;
f(t3)>0, f(t2)<0, t3=1.88, t2=1.75, длина отрезка 0.13, t4=(1.88+1.75)/2=1.82
0.13<2e = 0.2, поэтому с требуемой точностью корень уравнения 1.82.
(С точностью до 4-х знаков после точки корень равен 1.8731).