Решение нелинейных уравнений.

Итерационные методы вычисления изолированного корня уравнения .

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

В итерационных методах функция , , должна удовлетворять следующим стандартным условиям:

1) ;

2) функция непрерывна на .

Корень определяется как предел некоторой последовательности : .

1.2.1 Метод половинного деления (метод дихотомии).

В методе половинного деления функция , , должна удовлетворять только стандартным условиям, приведенным выше.

Идея метода состоит в построении последовательности вложенных отрезков , на концах которых удовлетворяются условия , Найдем середину отрезка и вычислим . Если , то - корень уравнения (1), если , то из двух половин отрезка выбирается та, на концах которой функция имеет противоположные знаки, так как корень находится внутри именно этой половины. Обозначим новые границы отрезка через . Затем для нового отрезка выполняем аналогичную процедуру и так далее.

Деление пополам продолжается до тех пор, пока не выполнится условие

.

Тогда значение приближенно определяет корень с точностью :

, (10)

( – любая точка интервала и расстояние от нее не превосходит половины его длины, что видно из последнего неравенства при ).

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

1.2.2 Метод Ньютона или метод касательных

Пусть функция , , помимо стандартных условий удовлетворяет дополнительным условиям:

1) Существование производных 1-го и 2-го порядков;

2) ;

3) производные 1-го и 2-го порядков знакопостоянны на отрезке .

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

Геометрический смысл метода Ньютона состоит в следующем: приближения к корню строятся по абсциссам точек пересечения касательных к графику данной функции, проводимых в точках, соответствующих предыдущим приближениям (рис.4).

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

Рис. 4.

Следовательно, уравнение касательной, которая проходит через точку будет

. (11)

Отсюда, положив в (11) , находим точку пересечения касательной с осью абсцисс, которую обозначим через :

.

Через точку снова проводим касательную и, продолжая этот процесс, приходим к формуле Ньютона

(12)

Значения , вычисленные по формуле (12), образуют последовательность, которая стремится к значению корня уравнения (1).

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

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

то этому условию и должно удовлетворять выбранное значение .

Формулу Ньютона можно получить и аналитическим путем.

Оценка погрешности метода ,

где

На практике часто применяют упрощенное правило окончания итерационного процесса

, (19)

где – заданная точность.

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

Таким образом, метод Ньютона – квадратично сходящийся процесс. При “хорошем” начальном приближении он позволяет получить корень с большой точностью и сравнительно небольшим количеством вычислений.