3.3. Метод дихотомии

Пусть на этапе отделения корней получены две точки A и B (A<B), между которыми находится корень уравнения (3.1), т.е. такие точки, в которых знаки значений функ­ции F(x) противоположны (см. рис.3.2): sign F(A)  sign F(B).

Метод дихотомии, называемый еще методом половинного деления, заключается в следующем:

1) определяется середина отрезка [A,B]:

;

(3.2)

2) вычисляется значение функции в этой точке - F(P) и его знак sign F(P);

3) корень уравнения (3.1) находится в той половине отрезка [A,B], на концах которой функция F(x) имеет разные знаки. Если это будет половинка [A,P], то перенесем точку B в точку P; если же половинка [P,B], то перенесем точку A в точку P. Благодаря этой операции длина отрезка [A,B], на котором находится корень уравнения, уменьшилась вдвое, т.е. можно сказать, что значение корня определено с точностью до длины полученного отрезка.

Каждое новое повторение действий 1,2,3 будет давать все более точные значения корня уравнения. Повторение этого процесса следует прекращать, когда длина отрезка [A,B] станет меньше заранее заданного значения , являющегося в данном случае ошиб­кой ограничения, т.е. неравенство

B - A <

(3.3)

является критерием окончания вычислительного процесса.

Рис.3.3. Алгоритм метода дихотомии

Если величина задана очень малая, то вблизи корня значения F(x) могут ока­заться сравнимыми с погрешностью ее вычисления, т.е. при подходе к корню вычисли­тельный процесс может попасть в так называемую "полосу шума", и дальнейшее уточне­ние корня окажется невозможным. Поэтому кроме точности надо задавать в алгоритме ширину "полосы шума" 1 и прекращать процесс при попадании в него, т.е. неравенство F(P) | < 1 является дополнительным критерием окончания вычислительного процесса. Схема алгоритма представлена на рис.3.3. Рис.3.2. Геометрическая интерпретация метода дихотомии

3.4. Метод хорд

Пусть так же, как в методе дихотомий, известны две точки A и B (A<B), для которых sign F(A)  sign F(B). В методе хорд (см. рис.3.4), в отличие от метода дихотомий, в ка­чес­тве очередного приближения P берется точка пересечения с осью абсцисс хорды, соединяющей точки (A,F(A)) и (B, F(B)).

Рис.3.4. Геометрическая интерпретация метода хорд

Уравнение прямой, проходящей через эти две точки запишем в виде: Y(x) = k x + c .

Коэффициенты k и c определяются из условий:

F(A) = k A + c ; F(B) = k B + c .

Решая эту систему из двух уравнений, получим:

; c = F(A) - k A .

Точка P пересечения этой прямой с осью ОX определяется из уравнения

kP + c = 0.

Решая его, окончательно получаем:

.

(3.4)

В методе хорд нельзя использовать в качестве критерия окончания вычислительного процесса неравенство (3.3), так как, как видно из рис.3.4, величина B – A не стремится к нулю. В данном методе, как и в рассматриваемых ниже, вычислительный процесс следует прекращать при выполнении неравенства

,

(3.5)

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

Алгоритм метода хорд, следовательно, отличается от алгоритма метода дихотомий формулой вычисления приближения P (вместо (3.2) использется (3.4) )и критерием окончания вычислительного процесса (вместо (3.3) использется (3.5) ).

Блок-схему для метода хорд предлагается разработать самостоятельно.