The Kantorovich theorem is a mathematical statement on the convergence of Newton's method. It was first stated by Leonid Kantorovich in 1940.
Contents
Newton's method constructs a sequence of points that under certain conditions will converge to a solution
Assumptions
Let
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
must hold.
Now choose any initial point
The next assumption is that not only the next point
As a last preparation, construct recursively, as long as it is possible, the sequences
Statement
Now if
- a solution
x ∗ F ( x ∗ ) = 0 exists inside the closed ballB ¯ ( x 1 , ∥ h 0 ∥ ) and - the Newton iteration starting in
x 0 x ∗
A statement that is more precise but slightly more difficult to prove uses the roots
and their ratio
Then
- a solution
x ∗ B ¯ ( x 1 , θ ∥ h 0 ∥ ) ⊂ B ¯ ( x 0 , t ∗ ) - it is unique inside the bigger ball
B ( x 0 , t ∗ ∗ ) - and the convergence to the solution of
F is dominated by the convergence of the Newton iteration of the quadratic polynomialp ( t ) towards its smallest roott ∗ t 0 = 0 , t k + 1 = t k − p ( t k ) p ′ ( t k ) ∥ x k + p − x k ∥ ≤ t k + p − t k . - The quadratic convergence is obtained from the error estimate