= Solution
Because $x^*$ is an interior minimizer of the differentiable function $f$, it satisfies $f'(x^*)=0$. Apply the <Taylor theorem with Lagrange remainder> to $f'$ about $x_n$. For some $y_n$ between $x_n$ and $x^*$,
$$
0=f'(x^*)
=f'(x_n)+f''(x_n)(x^*-x_n)
+\frac12f'''(y_n)(x^*-x_n)^2.
$$
The lower bound on $|f''|$ ensures that every step of the <Newton method> is defined. Divide by $f''(x_n)$ and use
$$
x_{n+1}=x_n-\frac{f'(x_n)}{f''(x_n)}
$$
to obtain the exact error relation
$$
x^*-x_{n+1}
=-\frac{f'''(y_n)}{2f''(x_n)}(x^*-x_n)^2.
$$
The assumed derivative bounds now give the <quadratic convergence bound for Newton's method>
$$
\boxed{|x^*-x_{n+1}|
\leq\frac{C_2}{2C_1}|x^*-x_n|^2}
$$
for every $n$.
Back to article page
