Kantorovich theorem

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

${\displaystyle \|F'(\mathbf {x} )-F'(\mathbf {y} )\|\leq L\;\|\mathbf {x} -\mathbf {y} \|}$

holds. The norm on the left is some operator norm that is compatible with the vector norm on the right. This inequality can be rewritten to only use the vector norm. Then for any vector ${\displaystyle \mathbf {v} \in \mathbb {R} ^{n}}$ the inequality

${\displaystyle \|F'(\mathbf {x} )(\mathbf {v} )-F'(\mathbf {y} )(\mathbf {v} )\|\leq L\;\|\mathbf {x} -\mathbf {y} \|\,\|\mathbf {v} \|}$

must hold.

Now choose any initial point ${\displaystyle \mathbf {x} _{0}\in X}$. Assume that ${\displaystyle F'(\mathbf {x} _{0})}$ is invertible and construct the Newton step ${\displaystyle \mathbf {h} _{0}=-F'(\mathbf {x} _{0})^{-1}F(\mathbf {x} _{0}).}$

The next assumption is that not only the next point ${\displaystyle \mathbf {x} _{1}=\mathbf {x} _{0}+\mathbf {h} _{0}}$ but the entire ball ${\displaystyle B(\mathbf {x} _{1},\|\mathbf {h} _{0}\|)}$ is contained inside the set ${\displaystyle X}$. Let ${\displaystyle M\leq L}$ be the Lipschitz constant for the Jacobian over this ball.

As a last preparation, construct recursively, as long as it is possible, the sequences ${\displaystyle (\mathbf {x} _{k})_{k}}$, ${\displaystyle (\mathbf {h} _{k})_{k}}$, ${\displaystyle (\alpha _{k})_{k}}$ according to

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

Now if ${\displaystyle \alpha _{0}\leq {\tfrac {1}{2}}}$ then

1. a solution ${\displaystyle \mathbf {x} ^{*}}$ of ${\displaystyle F(\mathbf {x} ^{*})=0}$ exists inside the closed ball ${\displaystyle {\bar {B}}(\mathbf {x} _{1},\|\mathbf {h} _{0}\|)}$ and
2. the Newton iteration starting in ${\displaystyle \mathbf {x} _{0}}$ converges to ${\displaystyle \mathbf {x} ^{*}}$ with at least linear order of convergence.

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

${\displaystyle p(t)=\left({\tfrac {1}{2}}L\|F'(\mathbf {x} _{0})^{-1}\|^{-1}\right)t^{2}-t+\|\mathbf {h} _{0}\|}$,

${\displaystyle t^{\ast /**}={\frac {2\|\mathbf {h} _{0}\|}{1\pm {\sqrt {1-2\alpha }}}}}$

and their ratio

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

Then

1. a solution ${\displaystyle \mathbf {x} ^{*}}$ exists inside the closed ball ${\displaystyle {\bar {B}}(\mathbf {x} _{1},\theta \|\mathbf {h} _{0}\|)\subset {\bar {B}}(\mathbf {x} _{0},t^{*})}$
2. it is unique inside the bigger ball ${\displaystyle B(\mathbf {x} _{0},t^{*\ast })}$
3. and the convergence to the solution of ${\displaystyle F}$ is dominated by the convergence of the Newton iteration of the quadratic polynomial ${\displaystyle p(t)}$ towards its smallest root ${\displaystyle t^{\ast }}$,[4] if ${\displaystyle t_{0}=0,\,t_{k+1}=t_{k}-{\tfrac {p(t_{k})}{p'(t_{k})}}}$, then

   ${\displaystyle \|\mathbf {x} _{k+p}-\mathbf {x} _{k}\|\leq t_{k+p}-t_{k}.}$

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

   ${\displaystyle \|\mathbf {x} _{n+1}-\mathbf {x} ^{*}\|\leq \theta ^{2^{n}}\|\mathbf {x} _{n+1}-\mathbf {x} _{n}\|\leq {\frac {\theta ^{2^{n}}}{2^{n}}}\|\mathbf {h} _{0}\|.}$

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]

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

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

• 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. (eds.). Numerical Analysis : Historical Developments in the 20th Century. North-Holland. pp. 241–263. ISBN 0-444-50617-9.