Kantorovich theorem


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. 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.
Newton's method constructs a sequence of points that under certain conditions will converge to a solution of an equation or a vector solution of a system of equation. 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 be an open subset and a differentiable function with a Jacobian that is locally Lipschitz continuous. That is, it is assumed that for any there is an open subset such that and there exists a constant such that for any
holds. The norm on the left is the operator norm. In other words, for any vector the inequality
must hold.
Now choose any initial point. Assume that is invertible and construct the Newton step
The next assumption is that not only the next point but the entire ball is contained inside the set. Let be the Lipschitz constant for the Jacobian over this ball.
As a last preparation, construct recursively, as long as it is possible, the sequences,, according to

Statement

Now if then
  1. a solution of exists inside the closed ball and
  2. the Newton iteration starting in converges to with at least linear order of convergence.
A statement that is more precise but slightly more difficult to prove uses the roots of the quadratic polynomial
and their ratio
Then
  1. a solution exists inside the closed ball
  2. it is unique inside the bigger ball
  3. and the convergence to the solution of is dominated by the convergence of the Newton iteration of the quadratic polynomial towards its smallest root, if, then
  4. :
  5. The quadratic convergence is obtained from the error estimate
  6. :

Corollary

In 1986, Yamamoto proved that the error evaluations of the Newton method such as Doring, Ostrowski, Gragg-Tapia, Potra-Ptak, Miel, Potra, can be derived from the Kantorovich theorem.

Generalizations

There is a q-analog for the Kantorovich theorem. For other generalizations/variations, see Ortega & Rheinboldt.

Applications

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