Newton's method

TheoremOne-step error bound for Newton's method#✓fully proved

Let \(f : \mathbb{R} \to \mathbb{R}\) be differentiable with \(f(c) = 0\), let \(x \in \mathbb{R}\), let \(m > 0\) and let \(K \ge 0\). If \(f'\) is Lipschitz with constant \(K\) on the closed interval between \(c\) and \(x\) and \(m \le |f'(x)|\), then the Newton step from \(x\) satisfies \(\left| x - f(x) / f'(x) - c \right| \le (K / m)\, |x - c|^2\).

theorem newton_step_sub_root_abs_le
    {f : ℝ → ℝ} {c x m : ℝ} {K : NNReal}
    (hf : Differentiable ℝ f) (hc : f c = 0) (hm : 0 < m)
    (hK : LipschitzOnWith K (deriv f) (uIcc c x))
    (hderiv : m ≤ |deriv f x|) :
    |x - f x / deriv f x - c| ≤ ((K : ℝ) / m) * |x - c| ^ 2

Used by 1

Used byLocal quadratic convergence of Newton's method

TheoremLocal quadratic convergence of Newton's method#✓fully proved

Let \(f : \mathbb{R} \to \mathbb{R}\) be twice continuously differentiable and let \(c\) be a simple root of \(f\): \(f(c) = 0\) and \(f'(c) \ne 0\). Then there exist \(\delta > 0\) and a real constant \(C\) with the following property. For every \(x_0 \in (c - \delta, c + \delta)\) and every real sequence \((x_n)\) that starts at \(x_0\) and satisfies \(x_{n+1} = x_n - f(x_n) / f'(x_n)\) for all \(n\), every \(x_n\) lies in \((c - \delta, c + \delta)\), \(|x_{n+1} - c| \le C\, |x_n - c|^2\) for all \(n\), and \(x_n \to c\).

Proof: Continuity keeps \(f'\) away from zero near \(c\), and \(C^2\) regularity makes \(f'\) Lipschitz on a compact interval around \(c\). The mean value theorem then bounds one Newton step by \((K / m)\, |x - c|^2\), where \(m > 0\) bounds \(|f'|\) from below and \(K\) is a Lipschitz constant of \(f'\); this replaces the Lagrange remainder in Wikipedia's "Proof of quadratic convergence for Newton's iterative method". Shrinking the neighborhood gives an invariant half-contraction and geometric convergence.

theorem newton_method_local_quadratic_convergence
    {f : ℝ → ℝ} {c : ℝ}
    (hf : ContDiff ℝ 2 f) (hc : f c = 0) (hderiv : deriv f c ≠ 0) :
    ∃ δ > 0, ∃ C : ℝ, ∀ x₀ ∈ Set.Ioo (c - δ) (c + δ),
      ∀ X : ℕ → ℝ, X 0 = x₀ →
        (∀ n, X (n + 1) = X n - f (X n) / deriv f (X n)) →
        (∀ n, X n ∈ Set.Ioo (c - δ) (c + δ)) ∧
        (∀ n, |X (n + 1) - c| ≤ C * |X n - c| ^ 2) ∧
        Filter.Tendsto X Filter.atTop (nhds c)

Sources

• R. L. Burden and J. D. Faires, Numerical Analysis, 10th ed., Theorem 2.6; stable ref https://en.wikipedia.org/wiki/Newton%27s_method.

Uses 1

Proof usesOne-step error bound for Newton's method

2 fully proved

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.