Sequential approximation, method of

method of successive approximation, method of repeated substitution, method of simple iteration

One of the general methods for the approximate solution of equations. In many cases the good convergence properties of the approximations constructed by this method allow one to apply it to practical computations.

Let $ E $ be some set and $ A $ an operator (not necessarily linear) on this set mapping it into itself. Suppose one has to find a fixed point of this mapping, i.e. a solution of the equation

$$ \tag{1 } x = A ( x) ,\ \ x \in E . $$

Let $ x ^ {*} $ be a solution of (1) and let its first approximation $ x _ {0} \in E $ be given by some method. Then all other approximations in the method of successive approximation are constructed by the formula

$$ \tag{2 } x _ {n+ 1} = A x _ {n} ,\ \ n = 0 , 1 ,\dots . $$

This process is called a simple one-step iteration.

To study the convergence properties of the sequence (2) and to prove the existence of a solution to (1), the contracting-mapping principle formulated below is widely used (cf. also Contracting-mapping principle).

Let $ E $ be a complete metric space with metric $ \rho $; let the operator $ A $ be defined on a closed ball $ S $ with radius $ \delta $ and centre at the point $ x _ {0} $:

$$ S = \{ {x \in E } : {\rho ( x , x _ {0} ) \leq \delta } \} ; $$

let for any elements $ x $ and $ y $ from $ S $ the following relation hold:

$$ \rho ( A x , A y ) \leq \alpha \rho ( x , y ) ,\ \ 0 < \alpha = \textrm{ const } < 1 ; $$

let for the initial approximation $ x _ {0} $ the inequality $ \rho ( A x _ {0} , x _ {0} ) \leq m $ be valid, and let for the numbers $ \alpha , \delta , m $ the condition $ m / ( 1 - \alpha ) \leq \delta $ be valid.

Then: 1) the successive approximations $ x _ {n} $ calculated by the rule (2) can be found for any $ n $ and they all belong to $ S $; 2) the sequence $ x _ {n} $ converges to some point $ x _ {*} \in S $; 3) the limit element $ x _ {*} $ is a solution of (1); and 4) for the approximation $ x _ {n} $ the following estimate of the distance to the solution $ x _ {*} $ holds:

$$ \rho ( x _ {n} , x _ {*} ) \leq \frac{m}{1 - \alpha } \alpha ^ {n} . $$

Further, on any subset in $ E $ on which for any two points $ x , y $ the inequality $ \rho ( A x , A y ) < \rho ( x , y ) $ holds, (1) cannot have more than one solution.

Let $ E = \mathbf R ^ {n} $ be the $ n $-dimensional real vector space, and let the operator $ A $ in (1) have the form $ A x = B x + b $, where $ B = \| a _ {ik} \| $ is a square matrix of order $ n $; let $ b = ( b _ {1} \dots b _ {n} ) $ be given and let $ x = ( x _ {1} \dots x _ {n} ) $ be the unknown vector in $ \mathbf R ^ {n} $. If in this space the metric is defined by the formula

$$ \rho ( x , y ) = \max _ { i } | x _ {i} - y _ {i} | $$

and if the entries of $ B $ satisfy the condition

$$ \sum _ { k= 1 }^ { n } | a _ {ik} | < 1 $$

for all $ i $, $ i = 1 \dots n $, then the contracting-mapping principle implies that the system of algebraic equations $ x = A x $ has a unique solution in $ \mathbf R ^ {n} $ which can be obtained by the method of successive approximation starting from an arbitrary initial approximation $ x _ {0} \in \mathbf R ^ {n} $.

If in $ \mathbf R ^ {n} $ the Euclidean metric

$$ \rho ( x , y ) = \sqrt {\sum _ { i= 1} ^ { n } ( x _ {i} - y _ {i} ) ^ {2} } $$

is given, then one obtains another condition of convergence for the successive approximations:

$$ \sum _ { i= 1} ^ { n } \sum _ { k= 1} ^ { n } a _ {ik} ^ {2} < 1 . $$

Let (1) be an integral equation in which

$$ A x ( t) = f ( t) + \lambda \int\limits _ { a } ^ { b } K ( t , s ) x ( s) d s , $$

where the given functions $ f $, $ K $ are square integrable on the sets $ [ a , b ] $ and $ [ a , b ] \times [ a , b ] $, respectively, and $ \lambda $ is a numerical parameter. Then the contracting-mapping principle implies that if

$$ | \lambda | < \left ( \int\limits _ { a } ^ { b } \int\limits _ { a } ^ { b } K ^ {2} ( s , t ) dt ds \right ) ^ {-} 1/2 , $$

then the considered integral equation has a unique solution in the space $ L _ {2} ( [ a , b ] ) $ which can be constructed by the method of successive approximation.

References

[1]	D.K. Faddeev, V.N. Faddeeva, "Computational methods of linear algebra" , Freeman (1963) (Translated from Russian)
[2]	V.I. Krylov, V.V. Bobkov, P.I. Monastyrnyi, "Numerical methods" , 1–2 , Moscow (1976–1977) (In Russian)
[3]	L. Collatz, "Funktionalanalysis und numerische Mathematik" , Springer (1964)

Comments

The contracting-mapping principle is of special interest for non-linear equations; see, e.g., [a1], [a2].

References

[a1]	E.A. Coddington, N. Levinson, "Theory of ordinary differential equations" , McGraw-Hill (1955)
[a2]	J. Cronin, "Fixed points and topological degree in nonlinear analysis" , Amer. Math. Soc. (1964)