Kantorovich theorem

Template:Short description The Kantorovich theorem, or Newton–Kantorovich theorem, is a mathematical statement on the semi-local convergence of Newton's method. It was first stated by Leonid Kantorovich in 1948. It is similar to the form of the Banach fixed-point theorem, although it states existence and uniqueness of a zero rather than a fixed point.

Newton's method constructs a sequence of points that under certain conditions will converge to a solution $x$ of an equation $f(x)=0$ or a vector solution of a system of equation $F(x)=0$. The Kantorovich theorem gives conditions on the initial point of this sequence. If those conditions are satisfied then a solution exists close to the initial point and the sequence converges to that point.

Assumptions

Let $X\subset {ℝ}^n$ be an open subset and $F:X\subset {ℝ}^n\to {ℝ}^n$ a differentiable function with a Jacobian $F^{\prime }(𝐱)$ that is locally Lipschitz continuous (for instance if $F$ is twice differentiable). That is, it is assumed that for any $x\in X$ there is an open subset $U\subset X$ such that $x\in U$ and there exists a constant $L>0$ such that for any $𝐱,𝐲\in U$

$\Vert F^{\prime }(𝐱)-F^{\prime }(𝐲)\Vert \le L\Vert 𝐱-𝐲\Vert$

holds. The norm on the left is the operator norm. In other words, for any vector $𝐯\in {ℝ}^n$ the inequality

$\Vert F^{\prime }(𝐱)(𝐯)-F^{\prime }(𝐲)(𝐯)\Vert \le L\Vert 𝐱-𝐲\Vert \Vert 𝐯\Vert$

must hold.

Now choose any initial point ${𝐱}_0\in X$. Assume that $F^{\prime }({𝐱}_0)$ is invertible and construct the Newton step ${𝐡}_0=-F^{\prime }({𝐱}_0{)}^{-1}F({𝐱}_0).$

The next assumption is that not only the next point ${𝐱}_1={𝐱}_0+{𝐡}_0$ but the entire ball $B({𝐱}_1,\Vert {𝐡}_0\Vert )$ is contained inside the set $X$. Let $M$ be the Lipschitz constant for the Jacobian over this ball (assuming it exists).

As a last preparation, construct recursively, as long as it is possible, the sequences $({𝐱}_k{)}_k$, $({𝐡}_k{)}_k$, $({\alpha }_k{)}_k$ according to

$\begin{array}{cc}{𝐡}_k& =-F^{\prime }({𝐱}_k{)}^{-1}F({𝐱}_k)\\ {\alpha }_k& =M\Vert F^{\prime }({𝐱}_k{)}^{-1}\Vert \Vert {𝐡}_k\Vert \\ {𝐱}_{k+1}& ={𝐱}_k+{𝐡}_k.\end{array}$

Statement

Now if ${\alpha }_0\le \frac{1}{2}$ then

1. a solution ${𝐱}^{*}$ of $F({𝐱}^{*})=0$ exists inside the closed ball $\overline{B}({𝐱}_1,\Vert {𝐡}_0\Vert )$ and
2. the Newton iteration starting in ${𝐱}_0$ converges to ${𝐱}^{*}$ with at least linear order of convergence.

A statement that is more precise but slightly more difficult to prove uses the roots $t^{\ast }\le t^{**}$ of the quadratic polynomial

$p(t)=(\frac{1}{2}L\Vert F^{\prime }({𝐱}_0{)}^{-1}{\Vert }^{-1})t^2-t+\Vert {𝐡}_0\Vert$,

$t^{\ast /**}=\frac{2\Vert {𝐡}_0\Vert }{1\pm \sqrt{1-2{\alpha }_0}}$

and their ratio

$\theta =\frac{t^{*}}{t^{**}}=\frac{1-\sqrt{1-2{\alpha }_0}}{1+\sqrt{1-2{\alpha }_0}}.$

Then

1. a solution ${𝐱}^{*}$ exists inside the closed ball $\overline{B}({𝐱}_1,\theta \Vert {𝐡}_0\Vert )\subset \overline{B}({𝐱}_0,t^{*})$
2. it is unique inside the bigger ball $B({𝐱}_0,t^{*\ast })$
3. and the convergence to the solution of $F$ is dominated by the convergence of the Newton iteration of the quadratic polynomial $p(t)$ towards its smallest root $t^{\ast }$, if $t_0=0,t_{k+1}=t_k-\frac{p(t_k)}{p^{\prime }(t_k)}$, then

   $\Vert {𝐱}_{k+p}-{𝐱}_k\Vert \le t_{k+p}-t_k.$

4. The quadratic convergence is obtained from the error estimate

   $\Vert {𝐱}_{n+1}-{𝐱}^{*}\Vert \le {\theta }^{2^n}\Vert {𝐱}_{n+1}-{𝐱}_n\Vert \le \frac{{\theta }^{2^n}}{2^n}\Vert {𝐡}_0\Vert .$

Corollary

In 1986, Yamamoto proved that the error evaluations of the Newton method such as Doring (1969), Ostrowski (1971, 1973), Gragg-Tapia (1974), Potra-Ptak (1980), Miel (1981), Potra (1984), can be derived from the Kantorovich theorem.

Generalizations

There is a q-analog for the Kantorovich theorem. For other generalizations/variations, see Ortega & Rheinboldt (1970).

Applications

Oishi and Tanabe claimed that the Kantorovich theorem can be applied to obtain reliable solutions of linear programming.

Further reading

• John H. Hubbard and Barbara Burke Hubbard: Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach, Matrix Editions, Template:ISBN (preview of 3. edition and sample material including Kant.-thm.)
• Template:Cite book