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) |
Sequential approximation, method of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Sequential_approximation,_method_of&oldid=14953