A fixed point iteration is an iterative method for approximating a fixed point 
of a map 
. Starting from an initial value 
, it forms the sequence
 |
(1)
|
for 
,
1, 2, 
.
The method is also called the method of successive approximations and, in several
settings, Picard iteration. If the sequence
converges to 
and 
is continuous at 
, then taking the limit in the iteration
gives 
.
Convergence is not automatic and can depend strongly on both the map
and the initial value.
Suppose 
is a complete metric space and 
is a contraction. If there is a constant 
with 
such that
 |
(2)
|
for all 
,
the Banach fixed point theorem states
that 
has a unique fixed point 
and that the fixed point iteration converges to 
for every 
(Banach 1922). It also gives the a priori error bound
 |
(3)
|
For 
,
an a posteriori error bound is
 |
(4)
|
For a differentiable real function or complex function, a fixed point
is locally attracting when 
and repelling when 
. When 
, convergence is generally linear with asymptotic
error ratio 
.
The problem of finding a root of 
can be converted to fixed point form 
, but different choices of 
can have different convergence behavior (Schröder 1870).
Newton's method, for example, is the fixed point
iteration with 
.
Fixed point iteration can be computed in the Wolfram Language using FixedPoint[g,
x0]. The intermediate iterates are returned by FixedPointList[g,
x0]. For example, iterating 
from 
converges to the Dottie number.
