Theorem by Kantorovich

The Kantorovich theorem is a statement of applied mathematics and guarantees the convergence of Newton's method with minimal conditions. It was first published in 1940 by Leonid Vitalievich Kantorowitsch .

requirements

Let it be an open convex subset and a differentiable function whose derivative is locally Lipschitz continuous . ${\displaystyle X\subset \mathbb {R} ^{n}}$ ${\displaystyle F:\mathbb {R} ^{n}\supset X\to \mathbb {R} ^{n}}$

That is, for each of the exist Jacobi matrix F '( x ) of the partial derivatives, and there is for each limited subset of a constant L> 0 with ${\displaystyle \mathbf {x} \in X}$ ${\displaystyle U\subset X}$

${\displaystyle \|F'(\mathbf {x} )-F'(\mathbf {y} )\|\leq L\;\|\mathbf {x} -\mathbf {y} \|}$for any . ${\displaystyle \mathbf {x,y} \in U}$

The norm of the difference of the Jacobi matrices is the induced matrix norm . This resolved into the vector norm results in the condition

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

for arbitrary points and tangent vectors . ${\displaystyle x,y\in U}$ ${\displaystyle v\in \mathbb {R} ^{n}}$

A point in X is known so that the Jacobi matrix can be inverted. Let be the Newton step and the next member of the Newton iteration. ${\displaystyle \mathbf {x} _{0}\in U}$ ${\displaystyle F'(\mathbf {x} _{0})}$ ${\displaystyle h_{0}=F'(\mathbf {x} _{0})^{-1}F(\mathbf {x} _{0})}$ ${\displaystyle \mathbf {x} _{1}=\mathbf {x} _{0}-h_{0}}$

Let it denote the length of the Newton step. ${\displaystyle \|h_{0}\|=\|\mathbf {x} _{1}-\mathbf {x} _{0}\|}$

statement

If the sphere around the point with the length of the first Newton step as a radius is still completely in U and the inequality is ${\displaystyle B={\bar {K}}(\mathbf {x} _{1},\|h_{0}\|)}$ ${\displaystyle \mathbf {x} _{1}}$

${\displaystyle \alpha _{0}=M\,\|F'(\mathbf {x} _{0})^{-1}\|\,\|h_{0}\|\leq {\tfrac {1}{2}}}$

fulfilled, where M is the Lipschitz constant on B , then

1. there is a unique solution of the vector equation within the closed sphere and ${\displaystyle F(\mathbf {x} )=0}$ ${\displaystyle B={\bar {K}}(\mathbf {x} _{1},\|h_{0}\|)}$
2. the Newton iteration with the starting point converges to this solution with at least a linear convergence speed. ${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}-F'(\mathbf {x} _{k})^{-1}F(\mathbf {x} _{k})}$ ${\displaystyle \mathbf {x} _{0}}$

generalization

The normalized space can be replaced by any Banach space in the domain of definition and value; the differentiability is then defined by the Frechet derivation. ${\displaystyle (\mathbb {R} ^{n},\|\cdot \|)}$

Even in the finite-dimensional case, the norms can be selected differently in the domain of definition and the domain of values . With the special choice ${\displaystyle D}$ ${\displaystyle W}$

${\displaystyle \|x\|_{D}=\|F'(x_{0})(\,x\,)\|_{W}}$

results z. B. that

${\displaystyle \|F'(x_{0})^{-1}\|=1}$

applies. The simpler form of the convergence condition has to be weighed against the more complex form of the estimation of the Lipschitz constant.

Evidence sketch

One can show that for a convex region U with Lipschitz's constant M the first derivative always has the inequality

${\displaystyle \|F(x+h)-F(x)-F'(x)(h)\|\leq {\tfrac {1}{2}}M\,\|h\|^{2}}$

applies if x and x + h are contained in U. For and with the Newton step it follows in particular ${\displaystyle x_{0}}$ ${\displaystyle x_{1}=x_{0}+h_{0}}$ ${\displaystyle h_{0}}$

${\displaystyle \|F(x_{1})\|\leq {\tfrac {1}{2}}M\,\|h_{0}\|^{2}\leq {\tfrac {1}{2}}M\,\|F'(x_{0})^{-1}\|\,\|F(x)\|\,\|h_{0}\|={\tfrac {1}{2}}\alpha _{0}\,\|F(x)\|}$.

Because of

${\displaystyle \|F'(x_{1})-F'(x_{0})\|\leq M\|h_{0}\|\leq \alpha _{0}\,\|F'(x_{0})^{-1}\|^{-1}}$

is also invertible according to the theorem for the Neumann series and it holds ${\displaystyle F'(x_{1})}$

${\displaystyle \|F'(x_{1})^{-1}\|\leq {\tfrac {1}{1-\alpha _{0}}}\,\|F'(x_{0})^{-1}\|\leq 2\,\|F'(x_{0})^{-1}\|}$

These two estimates can be combined to form an estimate of the next Newton step : ${\displaystyle h_{1}=-F'(x_{1})^{-1}F(x_{1})}$

${\displaystyle \|h_{1}\|\leq \alpha _{0}\,\|h_{0}\|\leq {\tfrac {1}{2}}\,\|h_{0}\|}$

and the parameter controlling the convergence

${\displaystyle \alpha _{1}=M\|F'(x_{1})^{-1}\|\,\|h_{1}\|\leq 2\alpha _{0}^{2}\leq {\tfrac {1}{2}}}$.

The ball to radius is completely in B and in X contain the Lipschitz constant of the smaller ball can only be smaller than M . So all the prerequisites for the next step are in place. This is continued through induction for the entire Newton iteration. The result is a sequence of spheres contained within one another, the radius of which is at least halved in each step. The common average of all spheres is therefore exactly one point, which is also the limit value of the Newton iteration. The function values ​​of the Newton iteration are reduced in each step to a quarter of the previous function value, i.e. they form a zero sequence. The limit of the Newton iteration solves the vector equation F (x) = 0 . ${\displaystyle x_{2}=x_{1}+h_{1}}$ ${\displaystyle \|h_{1}\|}$

swell

• John H. Hubbard and Barbara Burke Hubbard (2007): Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach , Matrix Editions, reading example of the third edition (PDF; 422 kB), ISBN 9780971576636

literature

• Kantorowitsch, L. (1948): Functional Analysis and Applied Mathematics (Russian). UMN3, 6 (28), 89-185.
• Kantorowitsch, LW; Akilow, GP (1964): Functional Analysis in Normalized Spaces . Berlin .
• P. Deuflhard: Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms. , Springer, Berlin 2004, ISBN 3-540-21099-7 (Series: Springer Series in Computational Mathematics , Vol. 35)