Kantorovich theorem

Short description: About the convergence of Newton's method

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 {\mathbb{ℝ}}^n$ be an open subset and $F:X\subset {\mathbb{ℝ}}^n\to {\mathbb{ℝ}}^n$ a differentiable function with a Jacobian $F^{\prime }(\mathbf{𝐱})$ 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 $\mathbf{𝐱},\mathbf{𝐲}\in U$

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

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

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

must hold.

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

The next assumption is that not only the next point ${\mathbf{𝐱}}_1={\mathbf{𝐱}}_0+{\mathbf{𝐡}}_0$ but the entire ball $B({\mathbf{𝐱}}_1,\Vert {\mathbf{𝐡}}_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 $({\mathbf{𝐱}}_k{)}_k$, $({\mathbf{𝐡}}_k{)}_k$, $({\alpha }_k{)}_k$ according to

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

Statement

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

1. a solution ${\mathbf{𝐱}}^{*}$ of $F({\mathbf{𝐱}}^{*})=0$ exists inside the closed ball $\overline{B}({\mathbf{𝐱}}_1,\Vert {\mathbf{𝐡}}_0\Vert )$ and
2. the Newton iteration starting in ${\mathbf{𝐱}}_0$ converges to ${\mathbf{𝐱}}^{*}$ 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 }({\mathbf{𝐱}}_0{)}^{-1}{\Vert }^{-1})t^2-t+\Vert {\mathbf{𝐡}}_0\Vert$,

$t^{\ast /**}=\frac{2\Vert {\mathbf{𝐡}}_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 ${\mathbf{𝐱}}^{*}$ exists inside the closed ball $\overline{B}({\mathbf{𝐱}}_1,\theta \Vert {\mathbf{𝐡}}_0\Vert )\subset \overline{B}({\mathbf{𝐱}}_0,t^{*})$
2. it is unique inside the bigger ball $B({\mathbf{𝐱}}_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 {\mathbf{𝐱}}_{k+p}-{\mathbf{𝐱}}_k\Vert \le t_{k+p}-t_k.$

4. The quadratic convergence is obtained from the error estimate

   $\Vert {\mathbf{𝐱}}_{n+1}-{\mathbf{𝐱}}^{*}\Vert \le {\theta }^{2^n}\Vert {\mathbf{𝐱}}_{n+1}-{\mathbf{𝐱}}_n\Vert \le \frac{{\theta }^{2^n}}{2^n}\Vert {\mathbf{𝐡}}_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, ISBN 978-0-9715766-3-6 (preview of 3. edition and sample material including Kant.-thm.)
• Yamamoto, Tetsuro (2001). "Historical Developments in Convergence Analysis for Newton's and Newton-like Methods". in Brezinski, C.; Wuytack, L.. Numerical Analysis : Historical Developments in the 20th Century. North-Holland. pp. 241–263. ISBN 0-444-50617-9.