Mathematics 242 – Principles of Analysis Discussion 6 – Fixed Point Iteration, Revisited November 1, 2000

Background

Last time, we proved the “Most Valuable Theorem”:

Mean Value Theorem. Let f(x) be continuous on [a, b] and differentiable on (a, b). Then there exists a c ∈ (a, b) such that f′(c) = \frac{f(b)−f(a)}{b−a}.

We also saw how the MVT establishes connections between properties of f′(x) (such as the sign of the derivative), and properties of the function f(x) (such as whether f is increasing or decreasing). Today, we will see another connection dealing with properties of a function under iteration.

We will use the following ideas. Recall that we have seen (Problem Set 4) that if g is continuous and g : [a, b] → [a, b], then g has a fixed point p ∈ [a, b] – a point satisfying g(p) = p. We can attempt to find such a point by starting at some x_{0} and iterating g:

(1)  x_{1} = g(x_{0}) ; x_{2} = g(x_{1}) ; x_{3} = g(x_{2}) ; ⋮ ; x_{n+1} = g(x_{n})

Discussion Questions

A) If g is continuous and an iteration sequence x_{n}, constructed using g as in (1) above converges to some q ∈ R, must q satisfy g(q) = q? Why or why not?

B) Try the following choices for g and x_{0}. Using a calculator if necessary, determine whether it appears that the sequence x_{n} constructed as in (1) above is converging to some q ∈ R.

1) g(x) = cos(x), x_{0} = 0.

2) g(x) = \frac{x^{2}+5}{2x}, x_{0} = 1.

3) g(x) = (x^{3} + 2x^{2} − x − 2)/10, x_{0} = 1 and x_{0} = 3.

C) For each of the functions in question B, plot y = g(x) together with the line y = x. How many fixed points does each function have? Where are they, approximately, and how do they correlate with the points you found in question B?

You can visualize an iteration sequence this way: Draw the graph y = g(x) together with the line y = x. Starting from x = x_{0} (on the x-axis), draw a vertical line segment up or down to the point (x_{0}, g(x_{0})) on the graph y = g(x). Then connect that point to the point on the line y = x with the same y-coordinate. The vertical line through that point intersects the x-axis in x_{1} = g(x_{0}) (why?). Then repeat the process to get x_{2} = g(x_{1}), etc.

D) Draw diagrams using this idea to illustrate the iteration sequences from question B. Do the same for iteration sequences for g(x) = x^{3}+2x^{2}−x−2 (10 times the polynomial from B, part 3), with x_{0} = 0 and x_{0} = 3.

E) From the examples you have seen, given a function g(x) and a fixed point q of g, when does it appear that iteration starting from x_{0} close to q will yield a sequence x_{n} converging to q?

F) If we assume that g(x) is differentiable on an interval containing a fixed point q, the Mean Value Theorem can be used to prove a statement guaranteeing convergence to the fixed point. Think about the following question: Given q = g(q) and x_{0} near q, if x_{1} = g(x_{0}), then by the MVT,

|x_{1} − q| = |g(x_{0}) − g(q)| = |g′(c)||x_{0} − q|

for some c ∈ (x_{0}, q). When is it guaranteed that x_{1} is closer to q than x_{0} was? Then consider subsequent steps in the iteration.

Assignment

Group write-ups, due Monday, November 6.