Fixed-point iteration

A fixed-point iteration (or a fixed point method ) is in mathematics, a numerical method for the approximate determination of solutions of an equation or a system of equations. The equation has to first in a fixed point equation, that is, in an equation of the form

Are converted with a function. Subsequently, an initial guess is selected and calculated. The result is placed back into the function, and so on. Under suitable additional assumptions, the result thus obtained a solution of and thus a solution of the original problem approaches on and on.

  • 4.1 design idea
  • 4.2 convergence
  • 4.3 Specific methods
  • 4.4 Remarks

General Procedure

Given a function that maps a lot in itself, as well as a startup item. The sequence generated by the corresponding fixed point method in is then defined iteratively by

If a notion of convergence is present on the set, one may ask whether this sequence converges to a fixed point of, that is against with. The Banach fixed point theorem indicates relatively general conditions under which this is the case: is a complete metric space, say 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 caused by the fixed point method sequence generated converges for any against.

Example

Wanted is the positive solution of the equation

By taking logarithms we obtain the fixed point equation

The iteration function given by, for example, is the interval into itself and is a contraction ( see illustration ).

Starting from the initial value is calculated for the next iteration, etc. In the approximation after 20 steps be correct, the first four digits correspond to the exact solution.

A set of existence and uniqueness

Be a continuously differentiable Fixpunktiterationsfunktion with and for all. Then there exists exactly one fixed point.

Evidence

One set. Then is. It follows from the intermediate value theorem that there is at least one zero with. If there were a second zero, about, then it would have because according to the set of role a point from the interval type with, which implies contradicts the assumption. So the fixed point is unique.

Example

For the function to apply:

  • .
  • .
  • For everyone.

It follows with the statement above that in exactly one fixed point has ().

Linear fixed point method

Design idea

An important special case of the fixed-point iteration, the splitting procedure. A linear system of equations

Transform with a non- singular n × n matrix and a vector to a fixed point equation, it decomposes the matrix by means of a non- singular matrix of n × n in

This follows

The identity matrix.

The linear system of equations is then equivalent to the fixed point task with

This gives the following iterative method for for a given starting vector

And the associated iteration matrix is:.

Convergence

From the Banach fixed point theorem and other considerations it follows that this fixed point method if and only converge for any starting vector, if the spectral radius of the iteration matrix

Should be as small as this, the convergence rate is determined.

Specific methods

In the above construction idea following known methods are based on the solution of linear systems of equations:

  • Gauss - Seidel method or also single-step method ( ESV )
  • Jacobi method or the total step method ( GSV )

Comments

Iteration of the form k = 0, 1, ... are

  • Linear, that is, xk 1 is a linear function of xk only,
  • Stationary, that is, V and M are independent of the step number of the iteration,
  • Stage, that is, only the last one and not another approximation vectors are used.

Nonlinear Equations

Newton's method can be considered as fixed-point iteration. In general, the convergence is ensured with the help of the Banach fixed point theorem, so the function must be considered especially in the region considered a contraction.

Rolle's theorem Relaxation (iterative method)
336274
de