Chapter 6: The Contraction Mapping Principle. Flashcards
Thm 6.6
THM 6.6: THE CONTRACTION MAPPING PRINCIPLE
Proof
Proof
Proof. Let 0 ≤ k < 1 be such that d(f(x), f(y)) ≤ kd(x, y) for all x, y ∈ X.
If k=0:
d(f(x), f(y)) = 0 for all x, y ∈ X, and so f(x) = f(y). Hence there exists x’ ∈ X such that f(x) = x’ for all x ∈ X. But then f(x’) = x’ and x’ is the required fixed point.
If 0 less than k less than 1:
choose x₀∈ X, and define (xₙ) recursively by iterating xₙ₊₁ = f(xₙ). We will prove that (xₙ) is a Cauchy sequence – as X is complete, the sequence will converge.
We have for all n = 0, 1, 2, . . .
d(xₙ, xₙ₊₁) ≤ kd(xₙ ₋₁ , xₙ) ≤ k² d(xₙ₋₂, xₙ₋₁) ≤ · · · ≤ kⁿ d(x₀, x₁).
Now let m bigger thn n.
Then d(xₙ, xm) ≤ d(xₙ, xₙ₊ ₁ ) + d(xₙ ₊ ₁ , xₙ ₊₂ ) + · · · + d(xₘ₋₁, xₘ)
≤
(kⁿ + kⁿ⁺¹ + · · · + kᵐ⁻¹ )d(x₀, x₁)
≤ [kⁿ + kⁿ⁺¹ + . . . ]d(x₀, x₁) = [kⁿ/ { 1 − k}] d(x₀, x₁).
Since k less than 1, [kⁿ/{ 1−k}] → 0 by the algebra of limits and 2.5(iii)(b). Hence, given ε larger than 0, there exists N such that whenever m larger thn n larger thn N,
d(xₙ, xₘ) ≤ [kⁿ/{ 1−k}] d(x₀, x₁) < ε.
Thus (xₙ) is Cauchy, and since X is complete, xₙ → x for some x ∈ X.
Let’s now see that x is a fixed point. Since the sequence (xₙ) converges to x, the subsequence (xₙ+1) also converges to x. But, as f is continuous (by 6.5),
xₙ₊ ₁ = f(xₙ) → f(x)
so x = f(x).
Now we’ll show that the fixed point is unique. Suppose that both x and x’ are fixed points. Then d(x, x₀ ) = d(f(x), f(x’ )) ≤ kd(x, x’ ). As k < 1, the only way this can happen is if d(x, x₀ ) = 0, and so x = x’ .
Thm 6.9
Differential criterion
Proof*****
Suppose f is a contraction. Fix x ∈ R, and let h bigger than 0.
We have
|f(x + h) − f(x)| ≤ k|(x + h) − x| = k|h|
and so |(f(x+h) - f(x))/h|≤ k. let h →0 and inequality becomes |f’(x)| ≤ k.
CONVERSELY
suppose |f’(x)| ≤ k for all x∈ R.
Let x bigger than y ∈ R. by the MVT there exists c between x and y st
(f(x) - f(y) )/(x-y) =f’(c).
|f’(x)| ≤ k so |(f(x) - f(y) )/(x-y)| ≤ k and hence f is a contraction.
Thm 6.11
unique point when?
Proof***
Let X be a complete metric space, and let f : X → X have the property that, for some m, the iterate f^m is a contraction of X. Then f has a unique fixed point.
Since fᵐ is a contraction and X is complete, fᵐ has a unique fixed point x.
ie fᵐ(x) = x. Apply f to this relation and we see that fᵐ⁺¹(x) = f(x)
ie fᵐ(f(x)) = f(x), so f(x) is also a fixed point of fᵐ. By uniqueness f(x) =x.
Also if f(y) = y then fᵐ(y) = y so y=x.
Solving eq of the fom f(x)=x
Ie finding fixed of points of f by picking initial value x_0 and iterating
x_(n+1) = f(xₙ)
To obtain sequence
(xₙ).
If this sequence has a limit x and f is continuous then x is a fixed point of f
Because
f(x)= f( limit as n → ∞ of xₙ) = limit as n → ∞ of f(xₙ) = limit as n → ∞ of x_(n+1) =x
We require conditions
An example where iterative method DOES NOT lead to a uniqu sol x =f(x)
By condition on functiom f:X to X
d(f(x), f(y)) IS LESS THAN d(x, y)
For all x,y distinct in X ie x ≠ y.
Ie if we apply f to a fixed point x and some other point y then f(y) is closer to x than y is.
EXAMPLE: functions cos:R to R and sin:R to R satisfy property
(d(f(x), f(y)) IS LESS THAN d(x, y)
For all x,y distinct in X ie x ≠ y.)
We use fact that |sin θ| is less than |θ| whenever θ ≠ 0.
If x ≠ y then |cosx -cosy| = |2sin( (x-y)/2) sin ((x+y)/2)| ≤ 2 |sin((x-y)/2)| Less than 2|x-y|/2 = |x-y|
Also
|sinx - siny| = |cos ((π/2)-x) - cos((π/2) -y )|
Less than
|((π/2) - x) - ( (π/2) -y)|
= |x-y|
If we iterate x_(n+1) = cos(xₙ) starting with x_0 =1 then we can find that from x_20 onwards all xₙs have value 0.739 to 3dp.
Ie seems that iteration converges to x=cosx
EXAMPLE: functions satisfy property
(d(f(x), f(y)) IS LESS THAN d(x, y)
For all x,y distinct in X ie x ≠ y.)
f:[1,∞) to [1,∞) st
f(x) = x + (1/x) for all x,y ∈ [1,∞)
Satisfy property but dont have a fixed point:
For x,y ∈ [1,∞) with x≠ y
|f(x) - f(y)| = |x + (1/x) - (y + (1/y)||
= | (x-y) + ((1/x) - (1/y)|
= |(x-y) + ((y-x)/xy)|
=|x-y||1 - (1/xy)|
Since x,y ≥ equal to 1
and x ≠ y
We have 0 less than 1 - (1/xy) less than 1
Therefore
|f(x) -f(y)| less than |x-y| if x ≠ y
A fixed point x for f would satisfy x = x +(!/x) which is impossible as 1/x is never 0.
DEF 6.3: f is a contraction if
Let f : X → X be a function on the metric space (X, d). Then f is a contraction if there exists a constant 0 ≤ k less than 1 such that
d(f(x), f(y)) ≤ kd(x, y) for all x, y ∈ X.
PROP 6.5 contractions and continuity
Let X be a metric space and let f : X → X be a contraction. Then f is continuous.
Proof: Let Let x ∈ X and let (xₙ) be a sequence that converges to x in X. Then d(xₙ, x) → 0. For all n,
d(f(xₙ), f(x)) ≤ kd(xₙ, x), where k < 1, so, by the algebra of limits and the Sandwich Rule, d(f(xₙ), f(x)) → 0, that is, f(xₙ) → f(x). Hence f is continuous.
THM 6.6: THE CONTRACTION MAPPING PRINCIPLE
Let f : X → X be a contraction of the complete metric space (X, d). Then f has a unique fixed point.
unique
contraction mapping: The proof of the theorem tells us how to find x to any degree of approximation and gives information on how quickly the sequence (f n (x₀)), converges to x.
From the proof, we have, for m > n,
d(xₘ, xₙ) ≤ [kⁿ/{ 1−k}] d(x₀, x₁). Fixing n, letting m → ∞ and applying Theorem 4.11 (or use Problem 10) we get d(xₘ, xₙ) → d(x, xₙ). Applying Proposition 3.2 to d(xₘ, xₙ) −[kⁿ/{ 1−k}] d(x₀, x₁), we get d(x, xₙ) ≤ [kⁿ/{ 1−k}]d(x₀, x₁).
THM 6.9 : DIFFERENTIAL CRITERION
Let f : R → R be differentiable. Then f is a contraction of R if and only if there exists 0 ≤ k < 1 with |f ‘ (x)| ≤ k for all x ∈ R.
for R
Versions of Theorem 6.9 hold for the intervals [a, b], [a,∞) and
(−∞, b].
For example if f : [a, b] → [a, b] is differentiable on (a, b).
Then f is a contraction on [a, b] if and only if there exists k < 1
with |f’(x)| ≤ k for all x ∈ (a, b).
THM 6.11: when can we say f has a unique fixed point
Let X be a complete metric space, and let f : X → X have the property that, for some m, the iterate f^m is a contraction of X. Then f has a unique fixed point.
Usefuleness of contraction mapping principle
The contraction mapping principle can be used to prove that many integral and differential equations have a solution.
THM 6.14: differential equation having a unique solution
Consider the differential equation
df/dx = α(f(x), x),
a ≤ x ≤ b,
f(a) = β,
where α: R×[a, b] → R is a continuous function of y and x.
Suppose that there exists L ≥ 0 such that |α(y₁, x) − α(y₂, x)| ≤ L|y₁ − y₂ |, for all y₁, y₂ ∈ R, and x ∈ [a, b].
Then the differential equation has a unique solution.
EXAMPLE of contraction with first property * kf 1
If X ⊆ R, f : X → X satisfies (∗), 0 < k < 1 and kf(x) ∈ X for all x ∈ X then kf : X → X is clearly a contraction. For example, for 0 < k < 1, the function g : R → R given by g(x) = k cos x is a contraction.
EXAMPLE of contraction with first property * kf 2
Fix k with ½ ≤ k < 1 and let f(x) = (x + 1/x ). Then g := kf defines a function g : [1,∞) → [1,∞) (see Chapter 6 Problem 1), and it is a contraction as f satisfies (∗).
EXAMPLE of contraction with first property * kf 3
Let f : R → R be given by f(x) = {⅔} cos x + {⅕} sin x.
Then |f(x) − f(y)| = |{⅔} (cos x − cos y) + {⅕} (sin x − sin y)| ≤ | {⅔} (cos x − cos y)| + | {⅕} (sin x − sin y)| ≤ {⅔} |x − y| + {⅕} |x − y| (as cos, sin satisfy (*))
= {13/15} |x − y| .
So f is a contraction with k = 13/15 .
EXAMPLE:
Show that there exist unique x, y ∈ R such that
x = (sin y )/4
y = ((sin x )/5) + 2
Define f: R²→ R²
(x,y) → ( {siny}/4 , [{sinx}/5 ] + 2)
A point (x,y)∈R² is fixed by f if and only if
x=(siny)/4 , y = (sinx)/5 +2
We check that the function f is a contraction. We need to find
k < 1 such that, for any two points (x, y) and (x’,y’) in R²,
we have
d(f(x, y), f(x’,y’)) ≤ kd((x, y),(x’,y’)). We use the fact, from prev example that |sinx-siny| ≤ |x-y| for allx,y in R
d(f(x, y), f(x’,y’))
= d ( ({siny/4}, {sinx/5} +2), ({siny’/4}, {sinx’/5} +2) )
= sqrt( ({siny/4} - {siny’/4} )² + ({sinx/5}-{sinx’/5})² )
≤ sqrt( ([{siny} - {siny’} ]/4)² + ([{sinx}-{sinx’}]/4)² )
≤ (1/4) sqrt( (y-y’)² + (x-x’)²)
= (1/4) d((x,y), (x’,y’))
f is a contraction on R³ with contraction factor k = 1/4.
As R² is complete, the Contraction Mapping Principle tells us that
f has a unique fixed point P = (x, y).
Example: consider f:R → R
or
f:[−π/2, π/2] → [−π/2, π/2]
f(x)=cosx
g(x) = f²(x) = cos(cosx)
contraction on R
f(x) =cosx so f’(x) = -sinx which fails criteria on R and [−π/2, π/2] as for any k less than 2 there exists x∈ (−π/2, π/2)
with |f’(x)| larger than k. So cos is not a contraction on R or on [−π/2, π/2].
g(x) = f²(x) = cos(cosx) so g'(x) = -sin(cosx)(-sinx) = sinx.sin(cosx) so |g'(x)| = |sinx|. |sin(cosx)| ≤ |sin(cosx)|
-1 ≤ cosx≤ 1 for all x and thus mapping x → sin(c) is monotonic increasing on [-1,1],
we have
-sin1 ≤ sin(cosx) ≤ sin1. so |sin(cosx)| ≤ sin1 = 0.8415.. less than 1
it follows that |g’(x)| ≤ sin1 less than 1. By 6.9 g is a contraction on R.
Example: Show that there is a unique solution in C[0,1] of the diff eq
df/dx = ( f(x) + x)x
0 ≤ x ≤ 1 f(0)=0
For f ∈ C[0, 1], let T(f) = g where
g(x) = ∫ over 0 to x of
(f(u) + u)u du.
Then
T(f) = f ⇔ f(x) = ∫ over 0 to x of
(f(u) + u)u du
⇔ f’(x) = (f(x) + x)x and f(0) = 0.
So f is a fixed point for T if and only if it is a solution of the differential equation. To apply the contraction mapping principle, we need to be working in a complete space, so C[0, 1] must be given the supremum metric. T is a contraction as: d ∞(T(f₁), T(f₂)) = sup_x∈[0,1] of |T(f₁)(x) -T(f₂)(x)| = sup_x∈[0,1] of | (∫ over 0 to x of (f₁(u) + u)u du.) -(∫ over 0 to x of (f₂(u) + u)u du.) | = sup_x∈[0,1] of | (∫ over 0 to x of (f₁(u) - f₂(u))u) du. |
≤ sup_x∈[0,1] of (∫ over 0 to x of |(f₁(u) - f₂(u))|u) du. = ∫ over 0 to 1 of |(f₁(u) - f₂(u))|u) du. ≤ sup_x∈[0,1] |f₁(x) - f₂(x)| . ∫ over 0 to 1 of u.du
= sup_x∈[0,1] |f₁(x) - f₂(x)| /2
=d ∞(f₁, f₂) /2
So T is a contraction on the complete metric space C([0, 1]) and
the differential equation has a unique solution
guess sol eg 0 then iterate funct f₀(x) = 0 for all x ∈ [0, 1], iterating: f₁ = T(f₀) = x/3 f₂ = T(f₁) = x/15 +x/3+... and find the series solution f(x) = x³/3 + x⁵/(3.5)+ x⁷/(3.5.7) + x⁹/(3.5.7.9) + . . . , which we can then check directly.
