Mathematics 171 – Numerical Analysis I Discussion 3 – Iteration sequences: x_{n} = g(x_{n−1}) Summary of Results

Questions

A) Suppose g(x) ∈ [a, b] for all x ∈ [a, b]. Must g have a fixed point on the interval [a, b]? Why or why not? What hypotheses on g do you need for your conclusion?

Under the assumption that g(x) is a continuous function on [a, b] taking values in [a, b], then there must be at least one (possibly more) fixed points in [a, b]. The reason is the following. If g(a) = a, then a is itself a fixed point. Otherwise, g(a) > a since g(a) ∈ [a, b]. Similarly, either g(b) = b and b is itself a fixed point, or else g(b) < b. We need only consider the case that neither a nor b is a fixed point. Then g(x) − x is also continuous on [a, b], positive at x = a, and negative at x = b. By the Intermediate Value Theorem, g(x) − x must be zero for some x = c in [a, b]. But then g(c) = c, so c is a fixed point of g.

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.) You will probably want to try consider how the iteration sequence x_{n} = g(x_{n−1}) might be constructed graphically.

We came to the conclusion that at each example we tried, the fixed point iteration would apparently converge to the limit L provided that |g′(L)| < 1, and x_{0} was chosen “close enough” to L. Here’s another way to see this, graphically. Suppose that g′(L) > 0. If we plot the sequences x_{n}, in each case, we can see that x_{n+1} can be produced from x_{n} by

• first going vertically from (x_{n}, 0) to the point (x_{n}, g(x_{n})) = (x_{n}, x_{n+1}) on the graph y = g(x), then

• going horizontally to the point (x_{n+1}, x_{n+1}) on the graph y = x,

• going back down to (x_{n+1}, 0)

If |g′(L)| < 1, we move toward (L, L), while if |g′(L)| > 1, we move away.

C) Under what conditions would it be true that |g(x)−g(L)| < |x−L| (i.e. g(x) is closer to the fixed point than x is)? Suppose your conditions 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?

If g′ exists and satisfies |g′(t)| < 1 for all t between x and L, then this will be true by the Mean Value Theorem. To get a convergence criterion for fixed point iteration, we saw “Holy Cross Fixed Point Theorem”. Let g be a function whose derivative is continuous on an interval I containing a fixed point L of g, and assume |g′(L)| < 1. Then there exists an interval I′ ⊆ I such that fixed point iteration x_{n+1} = g(x_{n}) will converge to L if we start from any x_{0} ∈ I′.

Proof. Pick any k with |g′(L)| < k < 1. Since g′ is continuous, and |g′(L)| < 1, there is an interval I′ containing L such that |g′(x)| ≤ k for all x ∈ I′. Moreover, by passing to a smaller interval (“shaving off one side of the interval”) if necessary, we may assume that I′ is symmetric about L: I′ = (L − δ, L + δ). Pick any x_{0} ∈ I′. We claim that iteration of g starting from x_{0} must produce a sequence converging to L. At the first step x_{1} = g(x_{0}), so by the Mean Value Theorem

(1)  |x_{1} − L| = |g(x_{0}) − g(L)| = |g′(t_{1})||x_{0} − L|

for some t_{1} between x_{0} and L. But then t_{1} ∈ I′, so |g′(t)| ≤ k < 1. Hence

(2)  |x_{1} − L| ≤ k|x_{0} − L| < |x_{0} − L|

Since I′ is symmetric about L, this says x_{1} ∈ I′ also (it’s on the same side of L as x_{0} if g′(L) > 0, and on the other side if g′(L) < 0). Similarly, by induction, assume we have proved that

(3)  |x_{n} − L| ≤ k^{n}|x_{0} − L|

As in (1) and (2) above,

|x_{n} − L| = |g(x_{n−1}) − g(L)| = |g′(t_{n})||x_{n−1} − L|

for some t_{n} ∈ I. Hence since |g′(t_{n})| < k, using the induction hypothesis (3), we have

|x_{n} − L| ≤ k^{n}|x_{0} − L|

for all n ≥ 0. As n → ∞, the right-hand side goes to zero (remember k < 1), so the sequence {x_{n}} is converging to L.