= Cubic convergence of Newton optimization for an even quartic
{c}
{title2=$f(x)=x^2/2+x^4/4$}
For the <strictly convex> <polynomial> $f(x)=x^2/2+x^4/4$, applying <Newton root-finding iteration> to $f'(x)=x+x^3$ gives
$$
x_{k+1}=x_k-\frac{x_k+x_k^3}{1+3x_k^2}=\frac{2x_k^3}{1+3x_k^2}.
$$
The unique <minimum> is at zero. For any sufficiently small nonzero initial point, the errors satisfy $|x_{k+1}|/|x_k|^3\to2$, so the order is cubic, not merely quadratic. This provides a simple counterexample to treating the usual <quadratic convergence> theorem as an upper bound on possible orders. In general, the quadratic coefficient for <Newton root-finding iteration>[Newton optimization] near a nondegenerate <stationary point> is $f^{(3)}(x_*)/(2f''(x_*))$; when it vanishes, a higher order is possible.
Back to article page
