Transcript Fixed Points and The Fixed Point Algorithm

Fixed Points
and
The Fixed Point Algorithm
Fixed Points
y
y=x
A fixed point for a function f(x) is a value x0 in
the domain of the function such that f(x0) =
x0. We say the function f(x) fixes the value x0.
y  2 x
Geometry
x
Geometrically the fixed point occurs where
the graph of y=f(x) crosses the graph of y=x.
A function may have none, one or many
fixed points.
Algebra
In terms of algebra the fixed point(s) is(are)
the solutions to the equation f(x)=x.
In the example to the right we see the fixed
point for the function f(x) is 2. If you compute
f(2) you get 2 (i.e. f(2)=2).
2

2 x  x

2
2  x  x2
2  x  x2
0  x2  x  2
0  ( x  2)(x  1)
Complicated Fixed Points
Finding the fixed point for some
functions results in a very complicated or
impossible equation to solve that would
find and exact value for the fixed point.
For example if we consider the function
f(x)=cos(x) it is apparent from the graph
that (or you could prove using the
Intermediate Value Theorem) this
functions has a fixed point.
2
1.5
1
0.5
1
2
3
4
5
6
-0.5
-1
It has been proven there is no algebraic combination of number to express the
solution to the equation cos(x)=x. This is why we need to rely on Numerical
Method to estimate solutions.
The Fixed Point Algorithm
The Fixed Point Algorithm (FPA) is an algorithm that generates a recursively
defined sequence that will find the fixed point for a function under the correct
conditions. One of the big advantages of the algorithm is that it is no very difficult
to implement.
The Fixed Point Algorithm (FPA) use a value x0 (ideally chosen close to the fixed
point you want to find) and a function f(x) and generates a recursively defined
sequence given by:
x0 for n=0
and
xn+1=f(xn) for n>0.
The FPA will be able to estimate a fixed point if and only if the sequence xn
converges.
There are several conditions that will that would imply convergence.
•f(x) is increasing and bounded
•f(x) satisfies a Lipshitz condition
•f(x) is decreasing and contractive
•others