6.2 Метод деления пополам. (Метод бисекций)
Пусть требуется с заданной точностью найти корень уравнения
. (1)
Отрезок локализации (т. е. отрезок, содержащий только один корень ) будем считать заданным, причем . Предположим, что функция непрерывна на отрезке и на его концах принимает значения разных знаков, т. е. . В основе метода лежит следующая теорема:
Теорема (Больцано-Коши о промежуточном значении). Если функция , непрерывная на отрезке , принимает на его концах значения разных знаков, т. е. , то на отрезке есть точка, в которой функция обращается в нуль.
Рис. 3. Метод деления пополам
Пусть корень уравнения (1) отделен и находится на отрезке ( и ). Возьмем на отрезке промежуточную точку, так, чтобы она являлась серединой отрезка , т. е. . Тогда отрезок точкой разделится на два равных отрезка и . Длина каждого отрезка равна . Если , то - точный корень уравнения (1). Если же , то из двух полученных отрезков и выберем тот, на концах которого функция принимает значению противоположных знаков; обозначим его . Затем отрезок также делим пополам и проводим те же рассуждения. Получим отрезок , длина которого равна . Процесс деления отрезка пополам производим до тех пор, когда на каком-то к-ом этапе либо середина отрезка окажется корнем уравнения (случай, весьма редко встречающийся на практике), либо получится отрезок такой, что
(2)
и (число к указывает на количество проведенных делений). Числа и - корни уравнения (1) с точностью до значения . За приближенное значение корня, следует взять .
Из неравенства (2) можно оценить число итераций необходимых для достижения заданной точности (априорная)
.
Достоинства:
а) метод половинного деления прост в алгоритмизации и программировании;
б) на функцию не накладывается никаких ограничений, кроме требования непрерывности.
Недостаток: метод очень медленно сходится, т.е. необходимо использовать большое число итераций для достижения заданной точности .
6.3 Метод простых итераций
Пусть требуется с заданной точностью найти корень уравнения
. (1)
Отрезок локализации будем считать заданным, причем . Предположим, что функция непрерывна на отрезке .
Заменим уравнение (1) эквивалентным ему уравнением вида
. (2)
Это преобразование (приведение уравнения к виду, удобному для итерации) можно выполнить различными способами; некоторые из них будут указаны ниже. Функцию далее будем называть итерационной функцией.
Выберем каким-либо образом в качестве начального приближения какое-либо значение , например , (или графически или методом бисекций). Затем вычислим , и полученное число примем за первое приближение значения корня . Подставив вместо в правую часть уравнения (2), получим новое число . Продолжая этот процесс неограниченно, получим последовательность приближений к корню определяемых следующими соотношениями
;
;
; (3)
…
.
Если не удается выразить из уравнения (1), то эквивалентное уравнение и эквивалентную функцию можно построить, например, так
, .
Последовательность (3) называется методом простых итераций уточнения корней уравнения (1).
Сходиться ли последовательность (3), и, если сходиться, являются ли предельное значение корнем уравнения (2), а следовательно, и уравнения (1)? Имеет место теорема.
Теорема (достаточные условия сходимости метода простых итерации). Пусть функция в эквивалентном уравнении (2) определена и дифференцируема на отрезке . Тогда, если существует число q такое, что
(4)
на отрезке , то последовательность (3) сходится к единственному корню уравнения (2) при любом начальном приближении .
На практике итерационный процесс останавливают при выполнении условия
, .
Рис. 4. К методу простых итераций в случае
Геометрическая интерпретация метода простых итераций. Из рис. 4. видно, что , так как тангенс угла наклона касательной к графику функции меньше tg(45°) = 1. Следовательно, для произвольного начального приближения в соответствии с 1-й итерацией в (3) при определяется , которое равно значению на графике функции , а поскольку треугольник ОАВ прямоугольный и равнобедренный, то ОВ = . На следующей итерации в (3) при определяется , которое равно значению на графике функции , а поскольку треугольник OCD — равнобедренный и прямоугольный, то CD = OD = , т.е. итерационные значения , , ,…. стремятся в сторону точного корня (указано стрелкой справа налево).
На рис. 5. . Из рисунка видно, что итерационный процесс расходится (приближения корня , , ,…. стремятся от корня ).
Рис. 5. К методу простых итераций в случае |
На рис. 6. представлен случай , . Процесс итераций сходится с двух сторон, т. е. приближения корня находятся то слева, то справа от точного корня .
Рис. 6. К методу простых итераций в случае ,
Исходное уравнение всегда можно привести к виду удобному для итераций. Для этого вернемся к исходному уравнению (1) и построим эквивалентное уравнение в виде
,
где берется знак минус, если , и плюс, если .
Тогда в качестве эквивалентной функции можно принять функцию
для которой
.