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

Метод половинного является самым простым и надежным способом решения нелинейного уравнения. Пусть из предварительного анализа известно, что корень уравнения находится на отрезке , т. е., так, что. Пусть функциянепрерывна на отрезкеи принимает на концах отрезка значения разных знаков, т.е..

Разделим отрезок пополам. Получим точку. Вычислим значение функции в этой точке:. Если, то– искомый корень, и задача решена. Если, то– число определённого знака:либо. Тогда либо на концах отрезка, либо на концах отрезказначения функцииимеют разные знаки. Обозначим такой отрезок. Очевидно, чтои длина отрезкав два раза меньше, чем длина отрезка. Поступим аналогично с отрезком. В результате получим либо корень, либо новый отрезоки т. д. (рис. 2).

Рис. 2

Середина -го отрезка. Очевидно, что длина отрезкабудет равна, а так как, то

. (1)

Критерий окончания. Из соотношения (1) следует, что при заданной точности приближения вычисления заканчиваются, когда будет выполнено неравенство или неравенство . Таким образом, количество итераций можно определить заранее. За приближенное значение корня берется величина.

Пример. Найдем приближенно с точностью. Эта задача эквивалентна решению уравнения, или нахождению нуля функции. В качестве начального отрезкавозьмем отрезок. На концах этого отрезка функция принимает значения с разными знаками:. Найдем числоделений отрезка, необходимых для достижения требуемой точности. Имеем:

.

Следовательно, не позднее 6-го деления найдем с требуемой точностью,. Результаты вычислений представлены в таблице 1.

Таблица 1

	0	1	2	3	4	5	6
	1,0000	1,0000	1,0000	1,1250	1,1250	1,1406	1,1406
	2,0000	1,5000	1,2500	1,2500	1,1875	1,1875	1,1562
	1,5000	1,2500	1,1250	1,1875	1,1406	1,1562	1,1484
Зн	-	-	-	-	-	-	-
Зн	+	+	+	+	+	+	+
	5,5938	0,7585	-0,2959	0,1812	-0,0691	0,0532	-0,0078
–	1,0000	0,5000	0,2500	0,1250	0,0625	0,0312	0,0156

1.4. Метод простой итерации

Пусть уравнение можно заменить эквивалентным ему уравнением

. (2)

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

. (3)

Формула (3) является расчетной формулой метода простой итерации.

Если последовательность сходится при, т. е. существует

(4)

и функция непрерывна, то, переходя к пределу в (3) и учитывая (4), получим:.

Таким образом, , следовательно,– корень уравнения (2).

Сходимость метода. Сходимость метода простой итерации устанавливает следующая теорема.

Теорема. Пусть функция определена и диффе­ренцируема на отрезке, причем все ее зна­чения. Тогда, если выполняется условиепри:

1) процесс итерации сходится независимо от начального значения;

2) предельное значение является единственным корнем уравненияна отрезке.

Доказательство. Так как и, то можно записать

.

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

Если ввести обозначение для всего интервала поиска, то предыдущее равенство может быть переписано в виде:

Аналогично . Тогда длябудет справедливо неравенство:и т. д. Продолжая эти выкладки дальше, в результате получаем, где– натуральное число. Таким образом, чтобы метод сходился, необходимо выполнение неравенства:.

Отсюда следует, что должно быть меньше единицы. В свою очередь, для всех остальных значений меньших, можно записать:. Числоопределим из соотношения. Тогда справедливо неравенство (вывод см. ниже):. Если поставить условие, что истинное значение корнядолжно отличаться от приближенного значения на величину, т.е., то приближениянадо вычислять до тех пор, пока не будет выполнено неравенство

или и тогда.

Вывод неравенства. Рассмотрим два последовательных приближения: и. Отсюда.

Используя теорему о среднем, получим:

,

тогда на основании условия можно записать:

.

С другой стороны, пусть . Очевидно, что. Отсюда, учитывая, что, получим

,

где .

Тогда или.

Используя предыдущую формулу, можно получить:

. (5)

Перейдём к пределу в равенстве (3), в силу непрерывности функции получим, то есть– корень уравнения (2). Других корней нанет, так как если, то, тогда, где. Равенство нулю будет достигнуто, если. То есть– корень единственный.

Теорема доказана.