A fixed point iteration (or a fixed point method ) is a numerical method in mathematics for the approximate determination of solutions to an equation or a system of equations . The equation must first be converted into a fixed point equation, i.e. into an equation of the form
can be transformed with a function . A starting approximation is then selected and calculated. The result is put back into the function , and so on. Under appropriate conditions, the additive thus obtained approaches result a solution of and thus a solution of the original problem on and on.
General procedure
Let there be a function that maps a set in itself, as well as a starting element . The sequence in generated by the associated fixed point method is then iteratively defined by
-
for .
If there is a concept of convergence on the set , one can ask whether this sequence converges to a fixed point of , that is, to a with . The Banach fixed point theorem indicates relatively general conditions under which this is the case: Is a complete metric space, so for example, a closed subset of or a Banach space , and a contraction , then there exists in the set exactly one fixed point of and through the fixed point method generated sequence converges for arbitrary against .
Examples
Graphical representation of the one-dimensional fixed point iteration
Find the positive solution to the equation
-
.
By taking logarithms we obtain the fixed point equation
-
.
The iteration function given by , for example, maps the interval in itself and is on a contraction (see adjacent figure).
Starting from the initial value is obtained for the next iteration , , etc. In the approximation after 20 steps already the first four digits correspond to the exact solution.
The Heron method also represents a fixed point iteration. For the function has the (positive) fixed point , so that it can be used for the numerical determination of .
A sentence about existence and uniqueness
Let be a continuously differentiable fixed point iteration function with and
for all off . Then there is exactly one fixed point from
with .
proof
You bet . Then is . From the intermediate value theorem it follows that there is at least one zero with
. If there were a second zero, for example
, then there would have to be a point from the interval with
according to Rolle's theorem , which implies contradicting the assumption. So the fixed point is clear.
example
The following applies to the function :
-
.
-
.
-
for everyone .
From this it follows from the sentence above that in has
exactly one fixed point ( ).
Linear fixed point method
Construction idea
The splitting method is an important special case of fixed point iteration . A system of linear equations
with a non-singular n × n - matrix and a vector to transform into a fixed point equation, it decomposes the matrix by means of a non-singular n × n matrix in
-
.
So follows
-
,
where denotes the identity matrix .
The system of linear equations is then equivalent to the fixed point problem with
-
.
The following iteration method is obtained for a given start vector for
-
,
and the associated iteration matrix is: .
convergence
From Banach's fixed point theorem and further considerations it follows that these fixed point methods converge for every start vector if and only if the spectral radius of the iteration matrix
-
.
should be as small as possible, as this determines the speed of convergence.
Special procedures
The following known methods for solving systems of linear equations are based on the above construction idea:
Remarks
Iteration methods of the form , k = 0, 1, ... are
-
linear , d. H. x k + 1 depends linearly only on x k ,
-
stationary , d. H. M and v are independent of the step number of the iteration,
-
single stage , d. H. only the last and not further proximity vectors are used.
Nonlinear equations
The Newton method can be viewed as a fixed point iteration. In general, the convergence is ensured with the help of Banach's fixed point theorem , so the function under consideration must be a contraction , especially in the area under consideration .
literature
- Wolfgang Dahmen, Arnold Reusken: Numerics for engineers and natural scientists. 2nd Edition. Springer-Verlag, Berlin 2008, ISBN 978-3-540-76492-2 .
Individual evidence
-
↑ Suitable transformations: zeros and fixed points. In: Montanuniversität Leoben . February 23, 2005, accessed August 27, 2019 .