Уточнение корней методом половинного деления (дихотомии)

⇐ ПредыдущаяСтр 2 из 13Следующая ⇒

Рис. 1. Метод деления отрезка пополам

Самым простейшим из методов уточнения корней является метод половинного деления, или метод дихотомии, предназначенный для нахождения корней уравнений, представленных в виде f(x)=0.

Пусть непрерывная функция f(x) на концах отрезка [a, b] имеет значения разных знаков, т.е. f(a)* f(b) < = 0 (рис. 1), тогда на отрезке имеется хотя бы один корень.

Возьмем середину отрезка с=(a+b)/2. Если f(a)* f(b) < = 0, то корень явно принадлежит отрезку от a до (a+b)/2 и в противном случае от (a+b)/2 до b.

Рис. 2. Блок-схема метода половинного деления

Поэтому берем подходящий из этих отрезков, вычисляем значение функции в его середине и т.д. до тех пор, пока длина очередного отрезка не окажется меньше заданной предельной абсолютной погрешности (b-a)< e.

Так как каждое очередное вычисление середины отрезка c и значения функции f(c) сужает интервал поиска вдвое, то при исходном отрезке [a, b] и предельной погрешности e количество вычислений n определяется условием (b-a)/2ⁿ< e, или n~log₂((b-a)/e). Например, при исходном единичном интервале и точности порядка 6 знаков (e ~ 10^-6) после десятичной точки достаточно провести 20 вычислений (итераций) значений функции.

С точки зрения машинной реализации (рис. 2) этот метод наиболее прост и используется во многих стандартных программных средствах, хотя существуют и другие более эффективные по затратам времени методы.

Листинг программы в приложении

Результат работы программы

Vvedite po porjadku 3 chisla

koordinaty koncov otrezka a, b, tochost epsilon

-1 1 0.01

x= 0.0000000000E+00

Pogreshnost rezultat = 1.0000000000E+00