= Concave Newton iteration from below
{title2=$-K e_n^2/(2m)\le e_{n+1}<0$}
Suppose $f\in C^2([a,r])$, $f(r)=0$, $f'\ge m>0$ and $-K\le f''<0$. Starting at $x_0\in[a,r)$, the <Newton root-finding iteration> remains below $r$ and increases strictly to it. To prove this, assume $x_n<r$. Strict increase of $f$ gives $f(x_n)<0$, so the Newton step is positive. <Taylor's theorem> between $x_n$ and $r$ gives, with $e_n=x_n-r$,
$$
e_{n+1}=\frac{f''(\xi_n)}{2f'(x_n)}e_n^2.
$$
Its coefficient is negative and at least $-K/(2m)$, proving both the stated error bound and $x_n<x_{n+1}<r$. <Mathematical induction> establishes the invariant. The increasing bounded iterates have a <limit> $L\le r$; continuity in $x_{n+1}-x_n=-f(x_n)/f'(x_n)$ forces $f(L)=0$, hence $L=r$. The error bound supplies local <quadratic convergence>.
Back to article page
