Лекция: Метод Ньютона-Рафсона (метод Ньютона)

Пусть xc — начальная точка (текущая точка), x+ = xc — Dx — приближенное значение корня, тогда

или

.

На каждой итерации строится линейная (аффинная) модель функции

M(x) = g(xc) + g¢(xc) (x — xc)

и решается задача отыскания корня этой модели.

Из теоремы Ньютона-Лейбница известно

.

Используя соотношение

,

получаем аффинную аппроксимацию.

Какова погрешность метода Ньютона |x* — xk |? Будет ли она уменьшаться в результате последовательных итераций — будет ли сходиться метод Ньютона, и как быстро? Это основной вопрос любого численного метода.

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

Сходимость метода линейная, если выполняется неравенство

.

Если

, при ,

то говорят, что сходимость сверхлинейная. Если же

,

то говорят, что сходимость порядка p.

Нас интересуют сверхлинейно и квадратично сходящиеся методы.

Для большинства задач метод Ньютона сходится квадратично, если выбрано хорошее начальное приближение. Метод может вообще не сходиться, если начальное приближение выбрано плохо. Такие методы называются локально-сходящимися. Глобально-сходящимися будем называть методы, которые сходятся почти из любой начальной точки.

Напомним, что функция называется непрерывной по Липшицу с константой g на множестве X gÎLipg (x), если |g(x) — g(y)|£g|x — y|.

Лемма (Оценка близости аппроксимации g(x) + g¢(x) (x — y) к g(y))

Пусть f: D® и g¢(x)ÎLipg (D) для открытого интервала D, тогда для "x, y ÎD

.

Доказательство:

,

.

После замены переменных, получаем

,

а используя непрерывность по Липшицу функции g¢, получаем

,

где g – ограничение сверху на g¢(x), xÎD.

Теперь можно доказать фундаментальную теорему.

Теорема. Пусть g: D → R, D – открытый интервал и пусть g¢Î Lipγ(D). Предположим, что для некоторого ρ>0 |g¢(γ)|≥ρ при любом xÎD. Если уравнение g(x)=0 имеет решение x*ÎD, то существует некоторое η>0, такое, что если |x*–x0|<η, то последовательность {xk}, задаваемая формулой

,

существует и сводится к x* квадратично

Замечания:

1) |g¢|≥ρ и ρ>0 обеспечивает то, что знаменатель в методе Ньютона не обращается в ноль. Если g¢(x*)=0, то x* является кратным корнем и сходимость метода Ньютона линейная.

2) является верхней границей относительной нелинейности g(x). ρ≤|g¢(x)|≤γ. Теорема утверждает, что чем меньше эта мера относительной нелинейности, тем быстрее сходимость.