Site hosted by Angelfire.com: Build your free website today!

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(x1), f(x2)) ≤ kρ(x1,x2)

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

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

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 x1 and x2 are any two points of [a,b] which map into y1 and y2,

y1 - y2 = x1 - x2 - {f(x1)/f '(x1) - f(x2)/f '(x2)}

= (x1 - x2) f(ξ)f ''(ξ)/{f '(ξ)}2 ,

where ξ lies between x1 and x2. Hence if

|f(x)f ''(x)/{f '(x)}2| ≤ 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)}2| = |(cos x - sin x)/(cos x + sin x)|2

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

xr = Σs=1,...,narsxs + cr    (r = 1,2,...,n)

The constants ars and cr and the unknowns xr are complex numbers. This system can be written in vector form

x = Ax + c

or

(I - A)x = c

where x = [x1,..., xn] and c = [c1,..., cn] are column vectors, I is the unit matrix and A is the matrix [ars]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

ρ(x1,x2) = max{|x1r - x2r|: r = 1,..., n},

where

x1 = [x11,..., x1n], x2 = [x21,..., x2n]

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(x1), f(x2)) = max {|Σs=1,...n ars(x1s -x2s)|}

≤ max {Σs=1,...,n |ars|.|x1s - x2s|}

≤ ρ(x1, x2) max {Σs=1,...,n |ars| : r = 1, ... , n}

.

Hence, if, for every value of r,

Σs=1,...,n|ars| ≤ 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 -----