Mathematics 371 – Numerical Analysis Comments on Discussion 2 – Fixed Point Iteration September 24, 2001

The following theorem and corollary give the alternate form of the Fixed Point Theorem that we were developing in this discussion.

Theorem. Let g(x) be differentiable on a symmetric interval J = (p − δ, p + δ), δ > 0, containing a fixed point p of g. If |g′(x)| ≤ k < 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 p.

Proof: If x_{0} ∈ J, then by the MVT

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

for some point c between x_{0} and p. Since x_{0} is in the symmetric interval J, so is the point c, and hence we have by hypothesis that |g′(c)| ≤ k < 1. Hence (1) implies that |x_{1} − p| ≤ k|x_{0} − p| < |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_{n} between x_{n−1} and p such that

|x_{n} − p| = |g(x_{n−1}) − g(p)| = |g′(c_{n})||x_{n−1} − p|.

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

|x_{n} − p| = |g′(c_{n})||x_{n−1} − p| ≤ k|x_{n−1} − p| ≤ k^{n}|x_{0} − p|.

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

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 I = (p − δ, q + δ) contained in J where |g′(x)| ≤ k < 1 for all x ∈ I. Hence, we have:

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

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