3.3.1.3. Уточнение корней
Рассмотрим несколько численных методов уточнения корней, применяемых для решения как алгебраических, так и трансцендентных уравнений. Эти методы относятся к разряду итерационных.
Итерационный процесс состоит в последовательном шаг за шагом уточнении начального приближения x0 искомого корня. Каждый шаг такого метода называется итерацией.
В
результате реализации итерационного
метода получают последовательность
приближенных значений корня
Если эти значения с увеличением n
приближаются к истинному значению
корня x*,
то говорят, что итерационный процесс
сходится.
3.3.1.3.1. Метод половинного деления (дихотомии, бисекции)
Пусть дано уравнение
(3.17)
где функция непрерывна и монотонна на отрезке и имеет на концах отрезка разные знаки:
(3.18)
Т
ребуется
найти корень
уравнения (3.17)
с
точностью до
График функции
представлен на рис. 3.5.
Р
ассмотрим
суть и этапы реализации метода
половинного деления.
1) Отрезок делим пополам и определяем середину отрезка:
(3.19)
2)
Вычисляем значение функции в точке
Если
,
то
является корнем уравнения. Если
то поиск корня продолжается на одном
из двух полученных отрезков –
или
.
Следует
выбрать тот отрезок, на концах которого
функция
принимает значения противоположных
знаков. В данном случае (см. рис. 3.5)
выбираем отрезок
,
так как для него выполняется условие:
Для того чтобы сохранить в дальнейших
расчетах единое обозначение
текущего отрезка, на котором ведется
поиск корня на данном шаге вычислений,
необходимо параметру b
присвоить новое значение
:
b
=
.
С точки зрения геометрической
интерпретации
(см. рис. 3.5) это означает, что правая
граница исходного отрезка точка b
переносится в точку
а оставшаяся за пределами точки
часть графика дальше не рассматривается.
3)
Новый отрезок
снова делим пополам:
(3.20)
4)
Вычисляем
и проводим анализ двух вновь полученных
отрезков –
и
.
Выбираем
тот из них, для которого выполняется
условие противоположности знаков
функции в граничных точках.
5)
Процесс деления пополам текущего
отрезка продолжаем до тех пор, пока
очередной отрезок
не будет удовлетворять условию:
(3.21)
где ε – требуемая точность расчета.
За
приближенное значение корня x*
принимаем
значение середины последнего отрезка
,
т. е.
x*
=
.
(3.22)
П
ри
этом погрешность вычисления корня не
будет превышать
,
где n
– количество произведенных делений
отрезков (количество итераций).
Алгоритм метода половинного деления, представлен на рис. 3.6.
В блоке 2 (рис. 3.6) задается начальное значение счетчика n количества итераций (делений отрезка пополам). Блоки 6 – 8 реализуют выбор того из двух отрезков, на котором следует продолжать поиск корня и соответственно корректировку границы (b – при выборе левого отрезка, a – правого).
Метод половинного деления – один из самых простых и надежных. Сходимость метода обеспечена для любых непрерывных функций, в том числе и для недифференцируемых.
Метод устойчив к ошибкам округления. Однако скорость сходимости его меньше, чем у методов, которые будут рассмотрены ниже.