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 be some set and 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

(1)

Let be a solution of (1) and let its first approximation be given by some method. Then all other approximations in the method of successive approximation are constructed by the formula

(2)

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 be a complete metric space with metric ; let the operator be defined on a closed ball with radius and centre at the point :

let for any elements and from the following relation hold:

let for the initial approximation the inequality be valid, and let for the numbers the condition be valid.

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

Further, on any subset in on which for any two points the inequality holds, (1) cannot have more than one solution.

Let be the -dimensional real vector space, and let the operator in (1) have the form , where is a square matrix of order ; let be given and let be the unknown vector in . If in this space the metric is defined by the formula

and if the entries of satisfy the condition

for all , , then the contracting-mapping principle implies that the system of algebraic equations has a unique solution in which can be obtained by the method of successive approximation starting from an arbitrary initial approximation .

If in the Euclidean metric

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

Let (1) be an integral equation in which

where the given functions , are square integrable on the sets and , respectively, and is a numerical parameter. Then the contracting-mapping principle implies that if

then the considered integral equation has a unique solution in the space 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)