Mathematics 371 – Numerical Analysis Discussion 2 – Fixed Point Iteration, Theory September 14, 2001

Background

Recall that we have introduced the idea of fixed point iteration as a method to solve equations f(x) = 0. We first rearrange the equation to the form x = g(x) using “reversible” operations so that f(x) = 0 ⇔ x = g(x), then attempt to find a point p satisfying p = g(p) by starting at some x_{0} and iterating g to construct the sequence:

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

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.

Also recall the “Most Valuable Theorem” of differential calculus:

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}.

In MATH 242, you 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 fixed point iteration for numerical root-finding.

Discussion Questions

A) If an iteration sequence x_{n} constructed using g as in (1) above converges to some q ∈ R, must q satisfy g(q) = q? What condition on g do you need to assume to say this?

B) From the examples you have seen, given a function g(x) and a fixed point p of g, when does the iteration starting from x_{0} close to p yield a sequence x_{n} converging to p? Make a conjecture (an “educated guess”) about a general statement along these lines.

C) If we assume that g(x) is differentiable on an interval containing a fixed point p, 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} − p| = |g(x_{0}) − g(p)| = |g′(c)||x_{0} − q|

for some c ∈ (x_{0}, p). When is it guaranteed that x_{1} is closer to p than x_{0} was? Then consider subsequent steps in the iteration, and prove your statement from B, or perhaps a modification of what you originally thought.

D) What can you say about the order of convergence of fixed point iteration? If x_{n} → p is a convergent iteration sequence, for what function h(n) is x_{n} = p+O(h(n))? Explain.

Assignment

Group write-up, due Wednesday, September 19.