Back to the on-screen lesson ·
What two hypotheses buy: a fixed point that exists, is unique, is reached from every start, and comes with a bound you can budget by and a bound you can stop by.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to state and prove the contraction mapping theorem, say which hypothesis supports which conclusion, use both error bounds for their different purposes, and recognise the theorem when the map is on vectors rather than numbers.
You have run fixed-point iterations and seen that $|g'(p)| < 1$ decides whether they converge. That test is about the fixed point, and it assumes there is one. This lesson turns it into a theorem that supplies the fixed point as well.
A map $g$ is a contraction on an interval with constant $k$ when $|g(x) - g(y)| \le k|x - y|$ there, with $k < 1$. It maps the interval into itself when $g(x)$ is in the interval whenever $x$ is. The a priori bound $k^{n}|x_0 - p|$ is known before the run; the a posteriori bound $\dfrac{k}{1-k}|x_n - x_{n-1}|$ is read off during it.
Theorem. If $g$ is continuous on $[a, b]$, maps $[a, b]$ into itself, and satisfies $|g'| \le k$ there with $k < 1$, then $g$ has exactly one fixed point $p$ in $[a, b]$, the iteration $x_{n+1} = g(x_n)$ converges to it from every start in $[a, b]$, and
$$|x_n - p| \le k^{n}|x_0 - p|, \qquad |x_n - p| \le \frac{k}{1 - k}|x_n - x_{n-1}|.$$
Three conclusions, and it is worth knowing which hypothesis buys which. Existence comes from continuity and the mapping condition alone: $g(a) \ge a$ and $g(b) \le b$, so $g(x) - x$ changes sign. Uniqueness comes from the contraction: two fixed points would be closer to each other than they are. Convergence needs both, because the contraction inequality may only be applied while the iterates remain where the derivative is bounded — which is what mapping into itself guarantees. The two error bounds answer different questions: the a priori one budgets the run in advance and is loose, the a posteriori one reads the step just taken and says whether to stop. Note that $\dfrac{k}{1-k}$ blows up as $k$ approaches one, which is the formal version of a familiar disappointment: a slow iteration takes tiny steps long before it is anywhere near the answer.
Another way: steps
Another way: picture
Draw $y = g(x)$ and $y = x$ on the square $[a, b] \times [a, b]$. Mapping into itself says the graph stays inside the square; the derivative bound says it is shallower than the diagonal everywhere. A curve that is inside the square and shallower than the diagonal has to cross it, exactly once, and the staircase of the iteration walks into the crossing whichever side it starts on.
The derivative bound is checked at the fixed point and nowhere else, and the theorem is then quoted as though it applied globally. It does not: $|g'(p)| < 1$ gives convergence from some neighbourhood of unstated size, while the theorem gives it from a specific interval you have checked. The second half of the mistake is stopping when the step is small. That is the a posteriori bound with the factor $\dfrac{k}{1-k}$ thrown away, and the factor is the whole content of the bound.
$g(x) = \cos x$ on $[0, 1]$: $g$ takes values in $[\cos 1, 1] \subset [0, 1]$.
Into itself.
$|g'| = |\sin x| \le \sin 1 \approx 0.85 < 1$ there.
A contraction, with $k = 0.85$.
So one fixed point, near $0.739$, reached from every start in $[0, 1]$, with error at most $0.85^{n}$.
All three conclusions.
$g(x) = x + \tfrac{1}{x}$ on $[1, \infty)$ maps the set into itself.
First hypothesis holds.
$|g'(x)| = |1 - 1/x^{2}| < 1$ at every point.
Pointwise, but not uniformly.
The supremum is $1$, there is no $k < 1$, and $g$ has no fixed point: the iterates run off to infinity.
The strictness was not decoration.
On $[0, 1]$, $g$ takes values between $\tfrac12$ and $\tfrac34$, which is inside $[0, 1]$.
$g'(x) = \tfrac{x}{2}$, so $|g'| \le \tfrac12$ on the interval.
Both hypotheses hold with $k = \tfrac12$: one fixed point, convergence from anywhere in $[0, 1]$, and the error at most $2^{-n}$.
Build the proof that a map of an interval into itself with $|g'| \le k < 1$ has exactly one fixed point, reached from every start.
This task has no paper form; do it on a device.
A root $r$ of $f$ is sought by the relaxed iteration $x_{n+1} = x_n - t\,f(x_n)$, and $f'(r) = 5$. For which positive $t$ does the iteration converge from a nearby start?
This task has no paper form; do it on a device.
An iteration contracts with constant $k = \dfrac{1}{3}$ and starts with $|x_0 - p| \le 5$. Give the a priori bound $k^{n}|x_0 - p|$ after each of the first three steps, as a fraction where it is not a whole number.
| Steps taken | Bound on the error | |
|---|---|---|
| After one step | 1 | |
| After two steps | 2 | |
| After three steps | 3 |
An iteration contracts with constant $k = \dfrac{1}{6}$, and the last step moved the iterate by $3$. What does the a posteriori bound give for the remaining error? Give a fraction.
Answer:
Jacobi iteration is applied to the system with matrix $\begin{pmatrix} 9 & 1 \\ 1 & 9 \end{pmatrix}$, giving $x \mapsto Mx + c$ with $M = \begin{pmatrix} 0 & -1/9 \\ -1/9 & 0 \end{pmatrix}$. What is its contraction constant in the infinity norm? Hint: it is the largest absolute row sum of $M$. Give a fraction.
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Match each hypothesis of the theorem to what is lost when it is dropped.
| The iterates can leave the region where anything was assumed | Nothing forces the errors to shrink; the iteration can be repelled | A map that never expands can still have no fixed point | The graph can jump across the diagonal without touching it | |
|---|---|---|---|---|
| $g$ maps the interval into itself | ||||
| $|g'| \le k$ on the interval | ||||
| The bound $k$ is strictly below one | ||||
| $g$ is continuous |
You can verify the hypotheses of the contraction theorem and use its two error bounds. Say in your own words why stopping when the step is small is not the same as stopping when the error is small.
8. Your turn: does $g(x) = \tfrac14(x^{2} + 2)$ contract on $[0, 1]$?, step 3