Метод бисекции
Простейшим методом является метод бисекции, называемый также методом деления пополам или методом дихотомии. Он состоит в следующем. Допустим, что удалось найти отрезок , на котором расположен один корень. В качестве начального приближения к корню принимаем середину этого отрезка: . Далее исследуем знаки значений функции на концах отрезков и то есть в точках . Тот из отрезков, на концах которого принимает значения разных знаков, содержит искомый корень; поэтому его принимаем в качестве нового исследуемого отрезка .
Вторую половину отрезка не рассматриваем (так как корня там нет). В качестве первого приближения к корню принимаем середину нового отрезка и т.д. После каждого приближения (итерации) отрезок, на котором расположен корень, уменьшается вдвое, то есть после k-ой итерации он сокращается в 2 k раз.
Опишем очередную -ю итерацию метода. Пусть отрезок уже найден и вычислены значения . Тогда производятся следующие действия:
1. Вычисляется .
2. Если , то в качестве отрезка локализации принимается отрезок , в противном случае – отрезок .
3. Вычисляется .
Продолжение описанного итерационного процесса дает последовательность отрезков , , содержащий искомый корень. Середина -го отрезка – точка дает приближение к корню , имеющее оценку погрешности . Это означает, что метод бисекции сходится со скоростью геометрической прогрессии, знаменатель которой . Аналогично оценивают скорости сходимости других методов.
Итерационный процесс следует продолжать до тех пор, пока значение функции после некоторой итерации с номером k+ 1 не станет по модулю не больше некоторого заданного малого числа , то есть |. После этого с погрешностью полагают: .
Замечание: Другим вариантом условия окончания итераций может служить . Это условие следует из очевидного неравенства .
Пример: Найти методом бисекции с точностью положительный корень уравнения .
Решение: Из предыдущего примера видно, что этот корень был локализован на отрезке , причем . Положим .
I итерация: Вычисляем . Так как , то за очередной отрезок локализации принимаем . Вычисляем .
II итерация: Вычисляем . Так как , то и .
Результаты следующих итераций (с четырьмя цифрами после десятичной точки) приведены в таблице
Номер итера-ции
|
|
| Знак
| Знак
|
|
|
|
| 0.0000
| 1.0000
| +
| –
| 0.5000
| 1.3513
| 1.0000
|
| 0.5000
| 1.0000
| +
| –
| 0.7500
| – 0.3670
| 0.5000
|
| 0.5000
| 0.7500
| +
| –
| 0.6250
| 0.5693
| 0.2500
|
| 0.6250
| 0.7500
| +
| –
| 0.6875
| 0.1206
| 0.1250
|
| 0.6875
| 0.7500
| +
| –
| 0.7187
| – 0.1182
| 0.0625
|
| 0.6875
| 0.7187
| +
| –
| 0.7031
| 0.0222
| 0.0312
|
| 0.7031
| 0.7187
| +
| –
| 0.7109
|
| 0.0156
|
При имеем . Следовательно, заданная точность достигнута и можно принять . Окончательно получим .
|