Newton's Method - Analysis

Analysis

Suppose that the function ƒ has a zero at α, i.e., ƒ(α) = 0.

If f is continuously differentiable and its derivative is nonzero at α, then there exists a neighborhood of α such that for all starting values x₀ in that neighborhood, the sequence {x_n} will converge to α.

If the function is continuously differentiable and its derivative is not 0 at α and it has a second derivative at α then the convergence is quadratic or faster. If the second derivative is not 0 at α then the convergence is merely quadratic. If the third derivative exists and is bounded in a neighborhood of α, then:

where

If the derivative is 0 at α, then the convergence is usually only linear. Specifically, if ƒ is twice continuously differentiable, ƒ '(α) = 0 and ƒ ''(α) ≠ 0, then there exists a neighborhood of α such that for all starting values x₀ in that neighborhood, the sequence of iterates converges linearly, with rate log₁₀ 2 (Süli & Mayers, Exercise 1.6). Alternatively if ƒ '(α) = 0 and ƒ '(x) ≠ 0 for x ≠ 0, x in a neighborhood U of α, α being a zero of multiplicity r, and if ƒ ∈ Cr(U) then there exists a neighborhood of α such that for all starting values x₀ in that neighborhood, the sequence of iterates converges linearly.

However, even linear convergence is not guaranteed in pathological situations.

In practice these results are local, and the neighborhood of convergence is not known in advance. But there are also some results on global convergence: for instance, given a right neighborhood U₊ of α, if f is twice differentiable in U₊ and if, in U₊, then, for each x₀ in U₊ the sequence x_k is monotonically decreasing to α.