A fixed point of a function
is a value
such that
If
is a continuous function such that
converges toas
thenis a stable fixed point and
Thus, provided
is su fficiently close to
we can use the simple iterationto find stable fixed points.
The problem of finding the root of an equation
can be easily converted to a fixed point iteration by choosing, e.g.,
It is important to note that there exists an infinite number of such functionsbut the precise
form of thewe choose will prove crucial for the convergence of the fixed point iteration.
Example: Let us look at the zeros (or roots) of
so a zero of
becomes a fixed point of
If we choose
and start at
the fixed point iteration
converges. The fixed point ofis
If we write
|
|
0.0000 |
1.0000 |
2.0000 |
3.0000 |
4.0000 |
5.0000 |
|
|
1.0000 |
1.5000 |
1.3710 |
1.4297 |
1.4077 |
1.4169 |
|
|
0.4142 |
0.0858 |
0.0392 |
0.0155 |
0.0065 |
0.0027 |
However, for
with
the procedure diverges to infi nity.
|
|
1.0000 |
2.0000 |
3.0000 |
4.0000 |
5.0000 |
|
|
1 |
-0.5 |
-3.13 |
8.52 |
114.5 |
|
|
0.41 |
1.91 |
4.54 |
7.11 |
113.08 |
Clearly, we need to establish the criteria for a stable fixed point. We consider the problem graphically. The fixed point ofis at the intersection of the lines
and
The different types of convergence are shown below.
Consider an iterate close to
say. Then
Thus
and
so if
then
is further away from than
so there is no convergence.