Основы теории оптимизации (стр. 51 )

Приведем доказательство, что функция φ(x) в окрестности корня осуществляет сжимающее отображение.

Доказательство: Пусть дана функция вещественного переменного дважды непрерывно дифференцируемая в своей области определения, производная которой нигде не обращается в нуль:

И необходимо доказать, что функция осуществляет сжимающее отображение вблизи корня уравнения f(x)=0. В силу непрерывной дифференцируемости функции f(x) и неравенства нулю её первой производной φ(x) непрерывна. Производная φ′(x) равна:

В условиях, наложенных на f(x), она также непрерывна. Пусть  — искомый корень уравнения: , следовательно в его окрестности :

Тогда согласно теореме Лагранжа:

В силу того, что в этой же дельта окрестности выполняется:

Таким образом полученная функция φ(x) в окрестности корня осуществляет сжимающее отображение.

По теореме Банаха последовательность приближений стремится к корню уравнения f(x)=0.

Рис. 1. Иллюстрация метода Ньютона

На рис. 1. представлена иллюстрация метода Ньютона (кривая изображает график функции f(x), нуль которой необходимо найти, прямая — касательную в точке очередного приближения xn). Здесь мы можем увидеть, что последующее приближение xn+1 лучше предыдущего xn.

Геометрическая интерпретация

Основная идея метода заключается в следующем: задаётся начальное приближение вблизи предположительного корня, после чего строится касательная к исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Эта точка и берётся в качестве следующего приближения. И так далее, пока не будет достигнута необходимая точность.

Пусть  — определённая на отрезке [a, b] и дифференцируемая на нём вещественнозначная функция. Тогда формула итеративного исчисления приближений может быть выведена следующим образом:

где α — угол наклона касательной в точке xn.

Следовательно искомое выражение для xn+1 имеет вид:

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

Алгоритм

Задается начальное приближение x0. Пока не выполнено условие остановки, в качестве которого можно взять или (то есть погрешность в нужных пределах), вычисляют новое приближение:

.

Пример

Иллюстрация применения метода Ньютона к функции f(x) = cosx − x3 с начальным приближением в точке x0 = 0,5.

Рис. 2. График последовательных приближений.

Рис. 3. График сходимости.

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

Рассмотрим задачу о нахождении положительных x, для которых cosx = x3. Эта задача может быть представлена как задача нахождения нуля функции f(x) = cosx − x3. Имеем выражение для производной f'(x) = − sinx − 3x2. Так как cosx ≤ 1 для всех x и x3 > 1 для x > 1, очевидно, что решение лежит между 0 и 1. Возьмём в качестве начального приближения значение x0 = 0,5, тогда:

Подчёркиванием отмечены верные значащие цифры. Видно, что их количество от шага к шагу растёт (приблизительно удваиваясь с каждым шагом): от 1 к 2, от 2 к 5, от 5 к 10, иллюстрируя квадратичную скорость сходимости.

Условия применения

Рассмотрим ряд примеров, указывающих на недостатки метода.

Контрпримеры

Если начальное приближение недостаточно близко к решению, то метод может не сойтись.

Пусть

Тогда

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

Рис.4. Иллюстрация расхождения метода Ньютона, применённого к функции с начальным приближением в точке x0=0.

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

Рассмотрим функцию:

Тогда

и всюду, кроме 0.

В окрестности корня производная меняет знак при приближении x к нулю справа или слева. В то время, как для 0<x<1.

Таким образом f(x) / f′(x) не ограничено вблизи корня, и метод будет расходиться, хотя функция всюду дифференцируема, её производная не равна нулю в корне, f бесконечно дифференцируема везде, кроме как в корне, а её производная ограничена в окрестности корня.

Рис.5. График производной функции при приближении x к нулю справа.

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

Рассмотрим пример:

Тогда и за исключением х=0, где она не определена.