MATH/APPM 4650
Class notes, January 30

Fixed-point iteration
If we want to find the solutions of f(x) = 0, one way to do it is to find the fixed points of g(x) = f(x) + x.

This is because if g(x) = x, then f(x) = 0 and vice versa.


Simple example: type an arbitrary number into your calculator and press "COS" over and over again.
No matter what number you start with, you'll end up with 0.7390851332.
This is the solution of cos(x) = x, which is also the solution of cos(x) - x = 0.
In this case f(x) = cos(x) - x while g(x) = cos(x).


In general the idea of fixed point iteration is: x_old is given:

1. y_old = g(x_old)
2. x_new = y_old.

Repeat.


We can draw this as a cobweb diagram.

Cobweb diagram (Maple worksheet). (Web page version).

The iteration will not always converge. It depends on the slope of the graph of g near the fixed point.


Theorem from Dynamical Systems:
If g is a function with a fixed point p, i.e., g(p) = p, then

• if |g'(p)| < 1, then the iteration converges to p if x₀ is close enough to p.
• If |g'(p)| > 1, then the iteration diverges away from p if x₀ is close enough to p.
• The case |g'(p)| = 1 is borderline: the iteration may converge or diverge.

It is very important to notice that we have no idea what happens if we start far from p.


Rough idea behind this:

x₀ ∼ p, so
x₁ = g(x₀) ∼ g(p) + g'(p) (x₀ - p).

Since g(p) = p, we know
|x₁ - p| ∼ |g'(p)| |x₀ - p|.



Suppose we want to find a solution of f(x) = cos(x) + 1/x = 0.
Set g(x) = f(x) + x = cos(x) + 1/x + x.
Check that g'(x) = -sin(x) -1/x² + 1 is less than 1 in absolute value.
Root is about x=2, and g'(2) ∼ -0.16. So we're OK.



# FIXED-POINT ITERATION
G(X) = COS(X) + 1/X + X
R = 2 # Initial guess
Tol = 0.001
MaxIter = 20
Count = 1
RelErr = 1 + Tol
WHILE( (RelErr > Tol) AND (Count <= MaxIter) ) DO
   oldR = R
   R = G(oldR)
   RelErr = ABS(oldR - R)/ABS(oldR)
   Count = Count + 1
END DO
IF (RelErr > Tol) THEN
   PRINT("Failed to reach tolerance")
ELSE
   PRINT("Reached tolerance")
END IF
PRINT(R)


If all the conditions are good (and you need to check them!), this may converge faster than the bisection method.



The book makes the point that if we are trying to solve f(x) = 0,
and we take any one-to-one function h such that h(0) = 0,
then the fixed points for g(x) = x + h( f(x) )
are exactly the same as the roots of f.


If we choose the function h correctly, we may be more likely to get |g'(p)| < 1.