Метод половинного деления

Простейшим итерационным методом нахождения корней нелинейных уравнений является метод дихотомии (метод бисекций, половинного деления). Его алгоритм содержит следующие этапы:

1. Найти отрезок , в котором распложен корень уравнения.

2. В качестве начального приближения взять .

3. Вычислить значения функции на концах отрезков и : .

4. Выбрать отрезок, на концах которого значения функции имеют разные знаки, и использовать его в качестве нового отрезка для следующей итерации.

В результате каждой итерации отрезок, на котором расположен корень, уменьшается вдвое, после n итераций он сокращается в раз. Точность (погрешность) вычислений задается некоторым малым числом . Процесс вычислений продолжается до тех пор, пока значение функции после n-й итерации не станет меньшим по модулю этого заданного малого числа : , длина полученного отрезка становится меньше погрешности. Метод дихотомии медленно сходится к точному решению, однако он сходящийся.

Пример. Отделить действительные корни аналитически и уточнить их методом дихотомии с точностью до 0,001.

Обозначим

Найдем производную

Составим таблицу знаков

	-∞	-2			+∞
Sign f(x)	-	+	-	-	+

Существует одна перемена знака функции на промежутке [1;+∞), поэтому уравнение имеет один действительный корень. Уменьшаем промежуток, содержащий корень так, чтобы его длина была равна единице.


Sign f(x)	-	+

Следовательно, корень необходимо искать на промежутке [1;2].

Все вычисления приведены в таблице.


1,0000	2,0000	1,5000	-3,3125
1,5000	2,0000	1,7500	7,8242
1,5000	1,7500	1,6250	1,3953
1,5000	1,6250	1,5625	-1,1567
1,5625	1,6250	1,5938	0,0677
1,5625	1,5938	1,5781	-0,5571
1,5781	1,5938	1,5859	-0,2479
1,5859	1,5938	1,5898	-0,0909
1,5898	1,5938	1,5918	-0,0118
1,5918	1,5938	1,5928	0,0279
1,5918	1,5928	1,5923	0,0080
1,5918	1,5923	1,5920	-0,0019
1,5920	1,5923	1,5922	0,0031
1,5920	1,5922	1,5921	0,0006
1,5920	1,5921	1,5921	-0,0006
1,5921	1,5921	1,5921	0,0005