Namespaces
Variants
Actions

Kantorovich process

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.


An iterative method for improving the approximation to the value of a root of a non-linear functional (operator) equation (a generalization of Newton's method cf. Newton method). For the equation $ P ( x) = 0 $, where $ P $ is a non-linear operator from one Banach space to another, the formula for calculating the root has the form

$$ x _ {n+} 1 = x _ {n} - [ P ^ { \prime } ( x _ {n} ) ] ^ {-} 1 P ( x _ {n} ) . $$

(Here $ P ^ { \prime } $ is the Fréchet derivative.) Sometimes a modified process, given by the following formula, is used:

$$ \widetilde{x} _ {n+} 1 = \ \widetilde{x} _ {n} - [ P ^ { \prime } ( x _ {0} ) ] ^ {-} 1 P ( \widetilde{x} _ {n} ) . $$

Suppose that the operator $ P $ is twice continuously differentiable and that the following conditions hold (see [2]):

1) the linear operator $ \Gamma _ {0} = [ P ^ { \prime } ( x _ {0} ) ] ^ {-} 1 $ exists;

2) $ \| \Gamma _ {0} P ( x _ {0} ) \| \leq \eta $;

3) $ \| \Gamma _ {0} P ^ { \prime\prime } ( x) \| \leq K $ when $ \| x - x _ {0} \| \leq r $;

4) $ h = K \eta \leq 1 / 2 $;

5) $ r \geq r _ {0} = ( 1 - \sqrt 1- 2h ) \eta / h $.

Then the equation $ P ( x) = 0 $ has a solution $ x ^ {*} $ such that

$$ \| x ^ {*} - x _ {0} \| \leq r _ {0} . $$

The sequences $ x _ {n} $ and $ \widetilde{x} _ {n} $ converge to this solution, with

$$ \| x ^ {*} - x _ {n} \| \leq \frac{( 2 h ) ^ {2 ^ {n} } \eta }{2 ^ {n} h } , $$

and in the case $ h < 1 / 2 $,

$$ \| x ^ {*} - \widetilde{x} _ {n} \| \leq \frac{( 1 - \sqrt 1- 2h ) ^ {n+} 1 \eta }{h} . $$

The Kantorovich process always converges to a root $ x ^ {*} $ of the equation $ P ( x) = 0 $, provided that $ P $ is sufficiently smooth, $ [ P ^ { \prime } ( x ^ {*} ) ] ^ {-} 1 $ exists and the initial approximation $ x _ {0} $ is chosen sufficiently close to $ x ^ {*} $. If $ P ^ { \prime\prime } ( x) $ exists and is continuous, then the convergence of the basic process is quadratic. The rate of convergence of the modified process is that of a decreasing geometric progression; the denominator of this progression tends to zero as $ x _ {0} \rightarrow x ^ {*} $.

The process was proposed by L.V. Kantorovich [1].

References

[1] L.V. Kantorovich, "On Newton's method for functional equations" Dokl. Akad. Nauk SSSR , 59 : 6 (1948) pp. 1237–1240 (In Russian)
[2] L.V. Kantorovich, G.P. Akilov, "Functional analysis in normed spaces" , Pergamon (1964) (Translated from Russian)
[3] M.A. Krasnosel'skii, G.M. Vainikko, P.P. Zabreiko, et al., "Approximate solution of operator equations" , Wolters-Noordhoff (1972) (Translated from Russian)
[4] L. Collatz, "Funktionalanalysis und numerische Mathematik" , Springer (1964)

Comments

The modified process is also called the Newton–Raphson method.

References

[a1] J.E. Denis jr., R. Schnable, "Numerical methods for unconstrained optimization and nonlinear equations" , Prentice-Hall (1983)
[a2] J.M. Ortega, W.C. Rheinboldt, "Iterative solution of non-linear equations in several variables" , Acad. Press (1970)
How to Cite This Entry:
Kantorovich process. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Kantorovich_process&oldid=47477
This article was adapted from an original article by I.K. Daugavet (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article