Applications of the Contraction Mapping Theorem

The treatment of the material here is taken from "Metric Spaces" by E. T. Copson. If (X, ρ) is a complete metric space and f : X -> X satisfies

ρ(f(x₁), f(x₂)) ≤ kρ(x₁,x₂)

where 0 < k < 1, there is a unique point α in X such that α = f(α). f is said to be a contraction mapping if it satisfies this condition.

A proof of this theorem is found at the page Metric Spaces, Contraction Maps and Fixed Point Iteration at www.mathreference.com.

1. Numerical solution of equations

There are iterative processes for finding the real roots of an algebraic equation which can be justified by the theory of contraction mappings; one of the most famous is the Newton-Raphson iteration

x_n+1 = x_n - f(x_n)/f '(x_n)

for solving the equation f(x) = 0.

Consider the mapping

y = x - f(x)/f '(x)

where f(x)/f '(x) is continuous on a closed interval [a,b] and differentiable on the open interval (a,b). If x₁ and x₂ are any two points of [a,b] which map into y₁ and y₂,

y₁ - y₂ = x₁ - x₂ - {f(x₁)/f '(x₁) - f(x₂)/f '(x₂)}

= (x₁ - x₂) f(ξ)f ''(ξ)/{f '(ξ)}² ,

where ξ lies between x₁ and x₂. Hence if

|f(x)f ''(x)/{f '(x)}²| ≤ k < 1

the mapping is a contraction mapping of [a,b] onto a closed interval of the real line. The mapping then has a unique fixed point α and the Newton-Raphson sequence converges to α.

Example: Calculation of π. Consider the function f(x) = sin x - cos x. We have

f(x) = cos x - sin x

f '(x) = - sin x - cos x

f ''(x) = - cos x + sin x

Hence

|f(x)f ''(x)/{f '(x)}²| = |(cos x - sin x)/(cos x + sin x)|²

which becomes arbitrarily small as x -> π/4. Thus Newton-Raphson iteration can be used to compute the value of π/4.

2. Systems of linear equations

Consider a system of linear equations in n unknowns, written as

x_r = Σ_s=1,...,na_rsx_s + c_r    (r = 1,2,...,n)

The constants a_rs and c_r and the unknowns x_r are complex numbers. This system can be written in vector form

x = Ax + c

or

(I - A)x = c

where x = [x₁,..., x_n] and c = [c₁,..., c_n] are column vectors, I is the unit matrix and A is the matrix [a_rs]_1≤r,s≤n. The system has a unique solution if and only if I - A is nonsingular.

The set of all column vectors can be turned into a complete metric space by taking

ρ(x¹,x²) = max{|x¹_r - x²_r|: r = 1,..., n},

where

x¹ = [x¹₁,..., x¹_n], x² = [x²₁,..., x²_n]

We wish to show that, under certain conditions, the mapping

y =f(x), where f(x) = Ax + c

from this metric space to itself has a fixed point. We have

ρ(f(x¹), f(x²)) = max {|Σ_s=1,...n a_rs(x¹_s -x²_s)|}

≤ max {Σ_s=1,...,n |a_rs|.|x¹_s - x²_s|}

≤ ρ(x¹, x²) max {Σ_s=1,...,n |a_rs| : r = 1, ... , n}

Hence, if, for every value of r,

Σ_s=1,...,n|a_rs| ≤ k < 1,

the mapping is a contraction mapping.

Remark. Computation by the fixed point method is useful in the case where A is a sparse matrix of large order, since in this case the computation of (I - A)^-1 is difficult while multiplication of a column vector by A can be done rather fast.

3. Ordinary differential equations

The existence and uniqueness of solution of a system of ordinary differential equations can be established using the contraction mapping theorem. This is done at http://qwerty-2009.tripod.com/ode1.html.

----- SITE MAP -----