Quadratic convergence of Newton's method

Remarks

Taylor's theorem with the Lagrange remainder at $x_k$ gives $0 = f(r) = f(x_k) + f'(x_k)(r - x_k) + \tfrac12 f''(\xi_k)(r - x_k)^2$ for some $\xi_k$ between $x_k$ and $r$. Dividing by $f'(x_k)$ and using the definition of $x_{k+1}$ gives $x_{k+1} - r = \frac{f''(\xi_k)}{2 f'(x_k)} (x_k - r)^2$, so $\abs{x_{k+1} - r} \le M \abs{x_k - r}^2 \le M\delta \abs{x_k - r}$; this keeps the iterates in $J$ and makes them converge, and the limit follows from $\xi_k, x_k \to r$. Since $f'(r) \ne 0$ and $f'$ and $f''$ are continuous, $M$ stays bounded as $\delta \to 0$, so a small $\delta$ gives $M\delta < 1$. Example: for $f(x) = x^2 - 2$ from $x_0 = 1$, the errors are about $4.1 \times 10^{-1}$, $8.6 \times 10^{-2}$, $2.5 \times 10^{-3}$, $2.1 \times 10^{-6}$, $1.6 \times 10^{-12}$; each error is about $0.35$ times the square of the previous one, and $f''(r)/(2f'(r)) = 1/(2\sqrt{2}) \approx 0.35$. The hypothesis $f'(r) \ne 0$ is needed: for $f(x) = x^2$ the iteration is $x_{k+1} = x_k/2$, which converges only linearly. Differentiability at $r$ is needed as well: for $f(x) = x^{1/3}$ the iteration is $x_{k+1} = -2x_k$, which diverges from every $x_0 \ne 0$.

Going deeper

For a student

This is the basic local convergence theorem for Newton's method: order $2$ in the sense of rate of convergence, with asymptotic constant $f''(r)/(2f'(r))$. The same proof works for systems $F(x) = 0$ in $\R^n$ with an invertible Jacobian at the zero, where it is a special case of the Newton–Kantorovich theory. At a zero of multiplicity $m \ge 2$ the convergence becomes linear with ratio $(m - 1)/m$, and the modified step $x_{k+1} = x_k - m f(x_k)/f'(x_k)$ restores quadratic convergence. Global convergence is not guaranteed, which is why practical solvers combine Newton steps with bisection or line searches.