Kantorovich theorem

Newton's method constructs a sequence of points that under certain conditions will converge to a solution ${\displaystyle x}$ of an equation ${\displaystyle f(x)=0}$ or a vector solution of a system of equation ${\displaystyle 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 ${\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^{\mathrm{\prime }}(\mathbf{x})}$ that is locally Lipschitz continuous (for instance if ${\displaystyle F}$ is twice differentiable). That is, it is assumed that for any ${\displaystyle x\in X}$ there is an open subset ${\displaystyle U\subset X}$ such that ${\displaystyle x\in U}$ and there exists a constant ${\displaystyle L>0}$ such that for any ${\displaystyle \mathbf{x},\mathbf{y}\in U}$

${\displaystyle \Vert F^{\prime }(\mathbf{x})-F^{\prime }(\mathbf{y})\Vert \le L\Vert \mathbf{x}-\mathbf{y}\Vert }$

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

${\displaystyle \Vert F^{\prime }(\mathbf{x})(\mathbf{v})-F^{\prime }(\mathbf{y})(\mathbf{v})\Vert \le L\Vert \mathbf{x}-\mathbf{y}\Vert \Vert \mathbf{v}\Vert }$

must hold.

Now choose any initial point ${\displaystyle {\mathbf{x}}_0\in X}$. Assume that ${\displaystyle F^{\prime }({\mathbf{x}}_0)}$ is invertible and construct the Newton step ${\displaystyle {\mathbf{h}}_0=-F^{\prime }({\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,\Vert {\mathbf{h}}_0\Vert )}$ is contained inside the set ${\displaystyle X}$. Let ${\displaystyle 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 ${\displaystyle ({\mathbf{x}}_k{)}_k}$, ${\displaystyle ({\mathbf{h}}_k{)}_k}$, ${\displaystyle ({\alpha }_k{)}_k}$ according to

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