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 -----