Next: Contraction Mapping Up: SOLUTION OF NONLINEAR EQUATIONS Previous: Secant Method

## Fixed Point Iteration

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.

Three Problems:

1. What functions have a fixed point?
2. How do we determine the fixed point?
3. Is the fixed point unique?
Example      has a fixed point at each ....just plot.

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

then the fixed point in is unique.

Proof:

If or , then existence of fixed point is clear. Suppose not, then it must be true that and . Define . Then is continuous on and

The Intermediate Value Theorem implies that there exist for which . Thus, is fixed point of .

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.

Fixed-Point Iteration

Pick a and generate a sequence such that If the sequence converges to and is continuous then by the theorem above:

The algorithm is depicted in Figure 18

Fixed Point Algorithm

Input: TOL,
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
Stop
Step 5: Set
Step 6: Set     Update .
Step 7: Output (Iterations exceeded. )
END

Theorem: (Fixed Point Iteration) Let and suppose . Suppose in addition that is continuous on with

if then for any in , the sequence

converges only linearly to the unique fixed point in

Proof: Fixed Point Theorem says . Since exists on apply mean value Theorem to to show that for any

since , and . Since is continuous on we have

thus

Remark: Can get higher-order convergence when

Theorem: Suppose solution of . and continuous and strictly bounded by on an open interval containing . Then such that . The sequence converges quadratically:

Fixed Point Iteration: let and suppose . Suppose in addition that exists on with

 (6)

if is any number in , then

converges to unique fixed point in .

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

By induction
 (7)

Since

and

Corollary If satisfies hypothesis of Fixed Point Iteration theorem, a bounds for the error involved in using to approximate are given by

Proof: (a) follows from (7):

For

therefore for

Since then

Since then

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 .

Figure 21a and Figure 21b illustrate the iteration history and the logarithm of the error, for a case starting with .
Finally, Figure 22a and Figure 22b 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

We can rearrange this to get which has one real root, .

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.

They also plot on the same graph as so we can see the fixed point, and finally plot the log of the error for each value of . We can see that for both and the iteration converges to a fixed point. The log error plots are straight lines with the slope showing the convergence rate (Question: Why does the log error plot flatten off for ?). In the case we can see that it converges faster than the case . For the fixed point does not converge but seems to bounce around different values in the interval . In fact for values of between and we get all sorts of interesting beheviour. For more information on this click here. But when we make less than 0.5 the iteration is able to escape from the interval and once it does this it increases rapidly with each iteration until it causes an overflow error in the computer.

(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

This shows why the iterations blow up for less than 0.5. For the range is not within the domain of (i.e. ) and so points may 'escape'. However for any value of greater than a half the range is mapped to within the domain.

Next we need to look at the derivative of

The magnitude of the derivative is only less than one for all values of if . Thus for any value of greater than two the fixed point theorem holds and we have guaranteed convergence. We know, however, that we still get convergence to a fixed point for some values of less than two. What is happening in these cases?

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 .

This is a simple quadratic equation with two solutions

For only the smaller of the two solutions lies within the interval and is the unique fixed point.

Subsections

Next: Contraction Mapping Up: SOLUTION OF NONLINEAR EQUATIONS Previous: Secant Method
Juan Restrepo 2003-04-12