Kantorovich theorem

The set of Kantorovich is a statement of applied mathematics and guarantees the convergence of Newton's method under minimal conditions. He was released by Leonid Kantorovich 1940 Vitalyevich first time.

Requirements

It had an open convex subset and a differentiable function whose derivative is locally Lipschitz continuous.

That for each exists, the Jacobian matrix F '(x) of the partial derivatives and there is for every bounded subset is a constant L > 0 such that

The norm of the difference of the Jacobian matrices, the induced matrix norm. This resolves to the vector norm yields the condition

For arbitrary points and tangent vectors.

X, a point is known, so that the Jacobian is inverted. Be the Newton step and the next link in the Newton iteration.

Denote the length of the Newton step.

Statement

Is the ball to the point with the length of the first radius of Newton step as yet fully in U, and the inequality

Is satisfied, where M is the Lipschitz constant for B, then

Generalization

The normalized space can be replaced by any Banach space in definition and range of values, the differentiability is then defined by the Frechet derivative.

Even in the finite case, one can choose the norms in the definition range and value range varies. With the special choice

Results, for example, that

Applies. The simpler form of the convergence condition is, however, counterbalance against the more complex form of assessment on the Lipschitz constants.

Sketch of proof

It can be shown that for a convex region U with Lipschitz constant M of first derivative always the inequality

Holds if x and x h are contained in U. For and with the Newton step follows in particular

Because of

Is according to the rate for Neumann series is also invertible and it holds

These two estimates can be combined to form an estimate of the next Newton step:

And the convergence controlling parameter

The ball around with radius is complete in B, and thus included in X, the Lipschitz constant of the smaller ball can only be smaller than M. all the conditions for the next step so it made ​​. This will be continued to the whole Newton iteration by induction. The result is a series of interlocking contained spheres whose radius is halved in each step at least. The combined average of all balls is exactly one point, which is also threshold the Newton iteration. The function values ​​of the Newton iteration are reduced in each step to a quarter of the previous function value, ie, form a null sequence. The limit of the Newton iteration thus solves the vector equation F (x ) = 0

Swell

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