Метод дихотомии
Пусть на этапе отделения корней получены две точки 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) |
является критерием окончания вычислительного процесса.
Если величина задана очень малая, то вблизи корня значения F(x) могут оказаться сравнимыми с погрешностью ее вычисления, т.е. при подходе к корню вычислительный процесс может попасть в так называемую "полосу шума", и дальнейшее уточнение корня окажется невозможным. Поэтому кроме точности надо задавать в алгоритме ширину "полосы шума" 1 и прекращать процесс при попадании в него, т.е. неравенство F(P) | < 1 является дополнительным критерием окончания вычислительного процесса.
Рис.3.2. Геометрическая интерпретация метода дихотомии
Дата добавления: 2015-01-15; просмотров: 1200;