Fixed Point Iteration

A fixed point of a functionis a valuesuch that

Ifis a continuous function such thatconverges toas thenis a stable fixed point and

Thus, providedis sufficiently close towe can use the simple iterationto find stable fixed points.

The problem of finding the root of an equationcan 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) ofso a zero ofbecomes a fixed point of

If we chooseand start atthe fixed point iteration

converges. The fixed point ofisIf 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, forwiththe procedure diverges to infinity.

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 linesandThe different types of convergence are shown below.

Consider an iterate close tosay. Then

Thusandso ifthenis further away from thanso there is no convergence.