Kantorovich process

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)