Приближенные (итерационные) методы решения нау

Пусть интервалы изоляции корней известны. Познакомимся с несколькими итерационными методами, позволяющими найти корень на известном интервале изоляции [a, b].

Метод деления отрезка пополам (дихотомии).

Идея метода заключается в делении отрезка, на котором содержится корень, пополам, до тех пор, пока не будет достигнута заданная точность.

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

ПРИМЕР 1.2. Найдем первый корень уравнения с точностью .

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

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

 и

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

Как можно видеть, значение корня в этом случае , что является более близким к точному значению. Второй и третий корни находятся аналогично.

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

Для метода простой итерации (МПИ) уравнение (1.1) необходимо сначала преобразовать к виду . Это всегда можно сделать с помощью эквивалентных преобразований. Далее, выберем начальное приближение . Следующие итерации производятся по формуле: , т.е. , , и т.д. Если последовательность , сходится, то , то есть в пределе получаем искомое решение уравнения. Итерационный процесс следует остановить, когда  В качестве начального приближения обычно берут середину отрезка : .

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

Достаточное условие сходимости. Пусть имеет производную на отрезке , и для всех из отрезка . Тогда итерационный процесс сходится к корню уравнения, т.е. .

Доказательство. Из формулы МПИ следует, что

Применяя теорему Лагранжа о среднем, получим

.

Аналогично

, и т.д.

Следовательно,

Так как , то и, следовательно, .

Геометрическая интерпретация метода простой итерации представлена на рис. 1.4 для случаев (а), (б), (в) и (г).

Рис. 1.4. Сходящийся (а, б) и расходящийся (в, г) МПИ

Метод релаксации

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

При таком выборе функции метод простой итерации называют методом релаксации.

Получим условия на выбор константы :

Таким образом, если , то . Если же , то .

Отсюда видно, что знак постоянной совпадает со знаком производной . Часто берут в виде: , где , .

Убедимся, что такой выбор удовлетворяет условию сходимости. Пусть . Тогда и , и, следовательно, и

, т.к. . Следовательно, .

Пусть теперь . Тогда , и

, т.к. и .

Следовательно, .

ПРИМЕР 1.3. Найдем с точностью второй корень уравнения , лежащий на интервале . Для определения значения параметра необходимо найти максимальное и минимальное значения производной функции на отрезке . Для этого необходимо найти значения на концах интервала и в точках экстремума, где (если эти точки лежат на исследуемом отрезке). Далее среди этих значений выбираются максимальное и минимальное. В нашем случае

,

, при

Экстремум производной находится на заданном отрезке , находим значение производной в этой точке: . Следовательно

, , .

Таким образом, .

Выберем начальное приближение , следующие приближения вычисляются по формуле

, k=0, 1, 2,..

Условием окончания итерационного процесса является условие: или 

Результаты вычислений оформим на рабочем листе Excel в виде таблицы:

	A	B	C
1	Номер итерации
2	0	2
3	1	2,133333	0,133333
4	2	2,106983	0,026351
5	3	2,1121	0,005117
6	4	2,111101	0,000999
7	5	2,111296	0,000195

Здесь формулы для вычисления имеют вид: =B2+2/15*(B2^3-6*B2^2+3*B2+11), а для :

=ABS(B3-B2). Остальные вычисления получаются простым копированием формул.