Mathematics 242 – Principles of Analysis Comments on Discussion 6 – Fixed Point Iteration November 7, 2000

The following theorem and corollary give a general pattern including the behavior you saw in the examples on this discussion.

Theorem. Let g(x) be differentiable on a symmetric interval I = (q − a, q + a), a > 0, containing a fixed point q of g. If |g′(x)| ≤ b < 1 for all points in I, then the iteration sequence x_{n} = g(x_{n−1}) constructed starting from any point x_{0} ∈ I will converge to q.

Proof: As in part F of the discussion, if x_{0} ∈ I, then by the MVT

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

for some point c between x_{0} and q. Since x_{0} is in the symmetric interval I, so is the point c, and hence we have by hypothesis that |g′(c)| ≤ b < 1. Hence (1) implies that |x_{1} − q| ≤ b|x_{0} − q| < |x_{0} − q|. That is: x_{1} is closer to q than x_{0} is. By the same argument using the MVT we have that for all n ≥ 1 there exists some c between x_{n−1} and q such that

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

Arguing by mathematical induction, if we assume that x_{n−1} ∈ I, then c ∈ I as well, so |g′(c)| ≤ b < 1, and

|x_{n} − q| = |g′(c)||x_{n−1} − q| ≤ b|x_{n−1} − q| ≤ b^{n}|x_{0} − q|.

Since b < 1, lim_{n→∞} b^{n} = 0, so lim_{n→∞} |x_{n} − q| = 0, and hence lim_{n→∞} x_{n} = q. //

The hypotheses in this theorem can also be replaced by the following. If we know that the derivative function g′(x) is continuous on some interval I containing q and |g′(q)| < 1, then by standard properties of continuous functions, there will exist a symmetric interval J = (q − a, q + a) contained in I where |g′(x)| ≤ b < 1 for all x ∈ J. Hence, we have:

Corollary. Assume g(x) is differentiable on an interval I containing a fixed point q and the derivative function g′(x) is continuous on that interval. If |g′(q)| < 1, then there exists an interval J ⊆ I such that the iteration sequence x_{n} = g(x_{n−1}) will converge to q for any choice of x_{0} ∈ J.

This form is sometimes more convenient since we only need to check the size of the derivative of g at the fixed point.