Kantorovich theorem

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

:$\backslash |F\text{'}(\backslash mathbf\; x)-F\text{'}(\backslash mathbf\; y)\backslash |\backslash le\; L\backslash ;\backslash |\backslash mathbf\; x-\backslash mathbf\; y\backslash |$

holds. The norm on the left is the operator norm. In other words, for any vector $\backslash mathbf\; v\backslash in\backslash R^n$ the inequality

:$\backslash |F\text{'}(\backslash mathbf\; x)(\backslash mathbf\; v)-F\text{'}(\backslash mathbf\; y)(\backslash mathbf\; v)\backslash |\backslash le\; L\backslash ;\backslash |\backslash mathbf\; x-\backslash mathbf\; y\backslash |\backslash ,\backslash |\backslash mathbf\; v\backslash |$

must hold.

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

The next assumption is that not only the next point $\backslash mathbf\; x\_1=\backslash mathbf\; x\_0+\backslash mathbf\; h\_0$ but the entire ball $B(\backslash mathbf\; x\_1,\backslash |\backslash mathbf\; h\_0\backslash |)$ 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 $(\backslash mathbf\; x\_k)\_k$, $(\backslash mathbf\; h\_k)\_k$, $(\backslash alpha\_k)\_k$ according to

:$\backslash begin\{alignat\}\{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{alignat}

Now if $\backslash alpha\_0\backslash le\backslash tfrac12$ then

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

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

:$$

p(t)

=\left(\tfrac12L\|F'(\mathbf x_0)^{-1}\|^{-1}\right)t^2

-t+\|\mathbf h_0\|

,

:$t^\{\backslash ast/**\}=\backslash frac\{2\backslash |\backslash mathbf\; h\_0\backslash |\}\{1\backslash pm\backslash sqrt\{1-2\backslash 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 $\backslash mathbf\; x^*$ exists inside the closed ball $\backslash bar\; B(\backslash mathbf\; x\_1,\backslash theta\backslash |\backslash mathbf\; h\_0\backslash |)\backslash subset\backslash bar\; B(\backslash mathbf\; x\_0,t^*)$
2. it is unique inside the bigger ball $B(\backslash mathbf\; x\_0,t^\{*\backslash 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^\backslash ast$,{{cite journal |first=J. M. |last=Ortega |title=The Newton-Kantorovich Theorem |journal=Amer. Math. Monthly |volume=75 |year=1968 |issue=6 |pages=658–660 |jstor=2313800 |doi=10.2307/2313800}} if $t\_0=0,\backslash ,t\_\{k+1\}=t\_k-\backslash tfrac\{p(t\_k)\}\{p\text{'}(t\_k)\}$, then
4. :$\backslash |\backslash mathbf\; x\_\{k+p\}-\backslash mathbf\; x\_k\backslash |\backslash le\; t\_\{k+p\}-t\_k.$
5. The quadratic convergence is obtained from the error estimate{{cite journal |first1=W. B. |last1=Gragg |first2=R. A. |last2=Tapia |year=1974 |title=Optimal Error Bounds for the Newton-Kantorovich Theorem |journal=SIAM Journal on Numerical Analysis |volume=11 |issue=1 |pages=10–13 |jstor=2156425 |doi=10.1137/0711002|bibcode=1974SJNA...11...10G }}
6. :$$

\|\mathbf x_{n+1}-\mathbf x^*\|

\le \theta^{2^n}\|\mathbf x_{n+1}-\mathbf x_n\|

\le\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),{{cite journal |first=A. M. |last=Ostrowski |title=La method de Newton dans les espaces de Banach |journal=C. R. Acad. Sci. Paris |volume=27 |issue=A |year=1971 |pages=1251–1253 }}{{cite book |first=A. M. |last=Ostrowski |title=Solution of Equations in Euclidean and Banach Spaces |publisher=Academic Press |location=New York |year=1973 |isbn=0-12-530260-6 }} Gragg-Tapia (1974), Potra-Ptak (1980),{{cite journal |first1=F. A. |last1=Potra |first2=V. |last2=Ptak |title=Sharp error bounds for Newton's process |journal=Numer. Math. |volume=34 |year=1980 |pages=63–72 |doi=10.1007/BF01463998 }} Miel (1981),{{cite journal |first=G. J. |last=Miel |title=An updated version of the Kantorovich theorem for Newton's method |journal=Computing |volume=27 |issue=3 |year=1981 |pages=237–244 |doi=10.1007/BF02237981 }} Potra (1984),{{cite journal |first=F. A. |last=Potra |title=On the a posteriori error estimates for Newton's method |journal=Beiträge zur Numerische Mathematik |volume=12 |year=1984 |pages=125–138 }} can be derived from the Kantorovich theorem.{{cite journal |last=Yamamoto |first=T. |year=1986 |title=A method for finding sharp error bounds for Newton's method under the Kantorovich assumptions |journal=Numerische Mathematik |volume=49 |issue=2–3 |pages=203–220 |doi=10.1007/BF01389624 }}

There is a q-analog for the Kantorovich theorem.{{cite journal |last1=Rajkovic |first1=P. M. |last2=Stankovic |first2=M. S. |last3=Marinkovic |first3=S. D. |year=2003 |title=On q-iterative methods for solving equations and systems |journal=Novi Sad J. Math |volume=33 |issue=2 |pages=127–137 }}{{cite journal |last1=Rajković |first1=P. M. |last2=Marinković |first2=S. D. |last3=Stanković |first3=M. S. |year=2005 |title=On q-Newton–Kantorovich method for solving systems of equations |journal=Applied Mathematics and Computation |volume=168 |issue=2 |pages=1432–1448 |doi=10.1016/j.amc.2004.10.035 }} For other generalizations/variations, see Ortega & Rheinboldt (1970).{{cite book |last1=Ortega |first1=J. M. |last2=Rheinboldt |first2=W. C. |year=1970 |title=Iterative Solution of Nonlinear Equations in Several Variables |publisher=SIAM |oclc=95021 }}

Oishi and Tanabe claimed that the Kantorovich theorem can be applied to obtain reliable solutions of linear programming.{{cite journal |last1=Oishi |first1=S. |last2=Tanabe |first2=K. |year=2009 |title=Numerical Inclusion of Optimum Point for Linear Programming |journal=JSIAM Letters |volume=1 |pages=5–8 |doi=10.14495/jsiaml.1.5 |doi-access=free }}

{{reflist}}

• 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}} ([http://matrixeditions.com/UnifiedApproachSamples.html preview of 3. edition and sample material including Kant.-thm.])
• {{cite book |first=Tetsuro |last=Yamamoto |chapter=Historical Developments in Convergence Analysis for Newton's and Newton-like Methods |pages=241–263 |editor-first=C. |editor-last=Brezinski |editor2-first=L. |editor2-last=Wuytack |title=Numerical Analysis : Historical Developments in the 20th Century |publisher=North-Holland |year=2001 |isbn=0-444-50617-9 }}

Category:Functional analysis

Category:Numerical analysis

Category:Theorems in mathematical analysis

Category:Optimization in vector spaces

Category:Optimization algorithms and methods