Mathematics 171 – Numerical Analysis I Discussion 3 – Iteration sequences: x_{n} = g(x_{n−1}) September 24, 1998

Goals

In this small-group discussion, we will study a general way to understand the mathematics of fixed point iteration. Looking ahead, this will give us the theoretical tools necessary to understand the behavior of Newton-Raphson iteration, other root-finding methods, and, more generally, a whole class of iterative numerical methods.

Background

As we saw in the lab last time, given a function g(x) (this might come from rearranging an equation f(x) = 0 to the form x = g(x) or from some other situation also), starting from some x_{0}, we can construct a sequence x_{n} of real numbers by applying g repeatedly: x_{1} = g(x_{0}), x_{2} = g(x_{1}), x_{3} = g(x_{2}), in general

(1)  x_{n} = g(x_{n−1})

One natural question here is: Under what conditions will such a sequence converge to a finite limit L?

Let’s assume that g : R → R is a “nice” function (e.g. differentiable with a continuous derivative for all x, or all x in some suitable interval). Note that if there is convergence, then L must be a “fixed point” of g, or in other words L must satisfy g(L) = L. The reason is that if g is differentiable then it is continuous, so from (1) above, taking limits on both sides as n → ∞:

L = lim_{n→∞} x_{n} = lim_{n→∞} g(x_{n−1}) = g( lim_{n→∞} x_{n−1}) = g(L).

Questions

A) Suppose g(x) ∈ [a, b] for all x ∈ [a, b]. Draw one or more graphs of functions satisfying this condition for [a, b] = [0, 2] to get a feeling for what this means. Must any function g satisfying this condition have a fixed point on the interval [a, b]? Why or why not? What hypotheses on g do you need for your conclusion?

Some fixed points are said to be “attracting,” because starting from x_{0} in some interval around the fixed point L, the sequences x_{n} = g(x_{n−1}) always converge to L, while some are said to be “repelling” because we either get convergence to a different fixed point or divergence. (You saw or will see examples of both types in Lab 2.)

B) Can you tell whether a fixed point of g is going to be attracting or repelling by looking at the graph y = g(x) at (or near) the fixed point? Find at least two different examples of each type and develop a conjecture based on your evidence. (Suggestion: try simple functions, like g(x) = x^{r} for various values of r, like r = 1/3, 1/2, 2, 3, etc. or g(x) = e^{−x}.) You will probably want to try consider how the iteration sequence x_{n} = g(x_{n−1}) might be constructed graphically.

There is a “Most Valuable Theorem” in 1-variable calculus which relates the total change in the values of differentiable function g over an interval [a, b] with the width of the interval: b − a, and the derivative of g:

Mean Value Theorem. If g is differentiable on (a, b) and continuous on [a, b], then there is some c ∈ (a, b) such that

g(b) − g(a) = g′(c)(b − a) .

C) Under what condition(s) would it be true that |g(x) − g(L)| < |x − L| (i.e. g(x) is closer to the fixed point L = g(L) than x is)? Suppose your condition(s) is/are true on a whole interval containing the fixed point. What will happen if you iterate x_{n} = g(x_{n−1}) starting from x_{0} in the interval?