Kantorovich theorem explained

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.^{[1] [2]} 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.^[3]

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.^{[1] [2]}

Assumptions

Let

X\subset\R ^{n} be an open subset and F:X \subset \R ^{n} \to\R ^{n} a differentiable function with a Jacobian F ^{\prime} ( x) 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 x, y\in U \|F'( x)-F'( y)\|\le L \| x- y\|

holds. The norm on the left is the operator norm. In other words, for any vector

v\in\R ^{n} the inequality\|F'( x)( v)-F'( y)( v)\|\le L \| x- y\|\| v\|

must hold.

Now choose any initial point

x _{0\in} X . Assume that F'( x _{0)} is invertible and construct the Newton step h _{0=-F'(x} ^{-1} ^{0 )} F( x _{0).}

The next assumption is that not only the next point

x _{1=x} _{0+h} _{0} but the entire ball B( x _{1,\|h} _{0\|)} 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

( x _{k)} _{k} , ( h _{k)} _{k} , (\alpha _{k)} _{k} according to\begin{alignat}{ 2 } h _{k&=-F'(x} ^{-1} ^{k)} F( x _{k)\\[0.4em] \alpha} _{k&=M\|F'(x} ^{-1} ^{k)} \|\| h _{k\|\\[0.4em] x} _{k+1} & = x _{k+h} _{k. \end{alignat}}

Statement

Now if

\alpha _{0\le\tfrac12} then

1. a solution

x ^{*} of F( x ^{*)=0} exists inside the closed ball \bar B( x _{1,\|h} _{0\|)} and

1. the Newton iteration starting in

x _{0} converges to x ^{*} 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 polynomialp(t) = \left(\tfrac 12 L\|F'( x ^{-1} _{0 )} \| ^{-1} \right)t ^{2} - t + \| h _{0\|} ,t ^{\ast/**} = (2 \| h _{0\|})/(1 \pm\sqrt{ 1-2 \alpha _{0}) }and their ratio \theta = (t ^{*})/(= t ^{**}) (1- \sqrt{ 1-2 \alpha _{0})/() }.Then

1. a solution

x ^{*} exists inside the closed ball \bar B( x _{1,\theta\|h} _{0\|)\subset\bar} B( x ^{*)} _{0 ,t}

1. it is unique inside the bigger ball

B( x ^{*\ast} _{0 ,t} )

1. 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} ,^[4] if t _{0=0,t} _{k+1} = t _{k-\tfrac{p(t} _{k)}{p'(t} _{k)}} , then\| x _{k+p} - x _{k\|\le} t _{k+p} - t _{k.}

1. The quadratic convergence is obtained from the error estimate^[5]

\| x _{n+1} - x ^{*\|} \le \theta ^{2 ^{n}} \| x _{n+1} - x _{n\|} \le (\theta ^{2 ^{n}})/(2 ^{n}) \| h _{0\|.}

Corollary

In 1986, Yamamoto proved that the error evaluations of the Newton method such as Doring (1969), Ostrowski (1971, 1973),^{[6] [7]} Gragg-Tapia (1974), Potra-Ptak (1980),^[8] Miel (1981),^[9] Potra (1984),^[10] can be derived from the Kantorovich theorem.^[11]

Generalizations

There is a q-analog for the Kantorovich theorem.^{[12] [13]} For other generalizations/variations, see Ortega & Rheinboldt (1970).^[14]

Applications

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

Further reading

• John H. Hubbard and Barbara Burke Hubbard: Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach, Matrix Editions, (preview of 3. edition and sample material including Kant.-thm.)
• Book: Yamamoto, Tetsuro . Historical Developments in Convergence Analysis for Newton's and Newton-like Methods . 241–263 . C. . Brezinski . L. . Wuytack . Numerical Analysis : Historical Developments in the 20th Century . North-Holland . 2001 . 0-444-50617-9 .

Notes and References

1. Book: Deuflhard, P. . Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms . Springer . Berlin . 2004 . 3-540-21099-7 . Springer Series in Computational Mathematics . 35 .
2. Book: Zeidler, E. . 1985 . Nonlinear Functional Analysis and its Applications: Part 1: Fixed-Point Theorems . New York . Springer . 0-387-96499-1 .
3. Book: John E. . Dennis . John E. Dennis . Robert B. . Schnabel . Robert B. Schnabel . The Kantorovich and Contractive Mapping Theorems . Numerical Methods for Unconstrained Optimization and Nonlinear Equations . Englewood Cliffs . Prentice-Hall . 1983 . 92–94 . 0-13-627216-9 . https://books.google.com/books?id=ksvJTtJCx9cC&pg=PA92 .
4. J. M. . Ortega . The Newton-Kantorovich Theorem . Amer. Math. Monthly . 75 . 1968 . 6 . 658–660 . 2313800 . 10.2307/2313800.
5. W. B. . Gragg . R. A. . Tapia . 1974 . Optimal Error Bounds for the Newton-Kantorovich Theorem . SIAM Journal on Numerical Analysis . 11 . 1 . 10–13 . 2156425 . 10.1137/0711002. 1974SJNA...11...10G .
6. A. M. . Ostrowski . La method de Newton dans les espaces de Banach . C. R. Acad. Sci. Paris . 27 . A . 1971 . 1251–1253 .
7. Book: Ostrowski, A. M. . Solution of Equations in Euclidean and Banach Spaces . Academic Press . New York . 1973 . 0-12-530260-6 .
8. F. A. . Potra . V. . Ptak . Sharp error bounds for Newton's process . Numer. Math. . 34 . 1980 . 63–72 . 10.1007/BF01463998 .
9. G. J. . Miel . An updated version of the Kantorovich theorem for Newton's method . Computing . 27 . 3 . 1981 . 237–244 . 10.1007/BF02237981 .
10. F. A. . Potra . On the a posteriori error estimates for Newton's method . Beiträge zur Numerische Mathematik . 12 . 1984 . 125–138 .
11. Yamamoto . T. . 1986 . A method for finding sharp error bounds for Newton's method under the Kantorovich assumptions . . 49 . 2–3 . 203–220 . 10.1007/BF01389624 .
12. Rajkovic . P. M. . Stankovic . M. S. . Marinkovic . S. D. . 2003 . On q-iterative methods for solving equations and systems . Novi Sad J. Math . 33 . 2 . 127–137 .
13. Rajković . P. M. . Marinković . S. D. . Stanković . M. S. . 2005 . On q-Newton–Kantorovich method for solving systems of equations . Applied Mathematics and Computation . 168 . 2 . 1432–1448 . 10.1016/j.amc.2004.10.035 .
14. Book: Ortega . J. M. . Rheinboldt . W. C. . 1970 . Iterative Solution of Nonlinear Equations in Several Variables . SIAM . 95021 .
15. Oishi . S. . Tanabe . K. . 2009 . Numerical Inclusion of Optimum Point for Linear Programming . JSIAM Letters . 1 . 5–8 . 10.14495/jsiaml.1.5 . free .