def: Fixed Point is the value such that .
Fixed Point problems and root-finding problems are equivalent: let . Hence, if a function has a fixed point then has a root.
Example has 2 fixed points in ....plot, again.
Theorem (Existence and Uniqueness): If and then has a fixed point in .
Suppose, in addition, that exists on and that a
positive constant exists with
If or , then existence of fixed point is clear.
Suppose not, then it must be true that and .
Define . Then is continuous on and
Suppose, in addition .
holds and that and are both fixed points in with .
By the Mean Value Theorem a number exists between and such that
This contradiction comes from and the fixed point is unique.
Pick a and generate a sequence
If the sequence converges to
and is continuous then by the theorem above:
Fixed Point Algorithm
Output: or message of failure
Step 1: Set
Step 2: While do Steps 3 - 6
Step 3: Set % Compute
Step 4: if TOL then
output ; % found not
Step 5: Set
Step 6: Set Update .
Step 7: Output (Iterations exceeded. )
Theorem: (Fixed Point Iteration) Let and suppose
. Suppose in addition that
is continuous on with
Proof: Fixed Point Theorem says
exists on apply mean value Theorem to to show that for any
Remark: Can get higher-order convergence when
Theorem: Suppose solution of . and
continuous and strictly bounded by on an open interval containing .
. The sequence
Fixed Point Iteration: let
Suppose in addition that exists on with
Proof: From fixed point theorem, a unique fixed point exists in . Since maps into itself, the sequence is defined and .
Using (6) and the Mean Value Theorem
Corollary If satisfies hypothesis of Fixed Point Iteration theorem, a bounds for the error involved in using to approximate are given by
Remark: Rate depends on . The smaller , the faster it converges.
Example: Consider for . This function is illustrated in Figure 19. Get matlab code used in the example.
First we wish to ensure that the function maps into itself.
Next we look at the derivative of
This fulfills the requirements for a unique fixed point to exist in . It also ensures that if we start with any non-negative value we will converge to the fixed point. The table below shows the first ten iterations for three different values of . Figure 20a and Figure 20b illustrate the iteration history and the logarithm of the error, for a case starting with .
The iterations for the three different starting points all appear to converge on . The log error plots are straight lines and they all have the same slope, indicating the same rate of convergence.
We can also prove analytically that is the fixed point of
. A fixed point of satisfies
Example: Consider the function for . We will start with the initial value and consider what happens for various values of . -Figure show the iterations for , respectively.
(b) . (c) . (d) .">Get matlab code used in the example.
Now lets see whether we can understand what is happening.
First let us look at the range of the function
Next we need to look at the derivative of
If the magnitude of the derivative will be less than one for . As long as the fixed point lies within this interval the theorem tell us that there will be a region around the fixed point where iterations will converge to the fixed point. This is the case as long as . As it turns out, we may still start at any point within and we will eventually arrive at the fixed point although convergence takes longer and longer the closer is to the critical point.
For values of the fixed point still exists but it becomes unstable (i.e. If you start close to the fixed point and iterate you will move away from it rather than towards it).
If we plot and the line on the same graph we can see that there is only one fixed point within the interval for all values of . In fact we can calculate the value of the fixed point analytically by solving .