Back to the on-screen lesson ·
Rewriting an equation as a map and iterating it, with the derivative at the fixed point deciding whether the errors shrink, alternate or run away.
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 rearrange an equation into an iteration map, decide from the derivative at the fixed point whether iterating it converges and how fast, and choose a different rearrangement when it does not.
You can differentiate the functions you meet here, and you know the mean value theorem: the change in a function across an interval is its derivative somewhere inside, multiplied by the width. That theorem is the whole proof of this lesson's one condition.
A fixed point of $g$ is a value $p$ with $g(p) = p$. A map contracts near $p$ when nearby points are moved closer to $p$, and the contraction factor is $|g'(p)|$. A rearrangement of an equation is any way of writing it as $x = g(x)$; there are always many, and they are not equally good.
Any equation can be written $x = g(x)$, and the obvious thing to do is iterate: $x_{k+1} = g(x_k)$. Whether that works is settled by one number. Writing the error as $e_k = x_k - p$, the mean value theorem gives $e_{k+1} = g'(\xi)e_k$ for some $\xi$ between $x_k$ and $p$, so each step multiplies the error by about $g'(p)$. Hence: $|g'(p)| < 1$ and the iteration converges, linearly, at rate $|g'(p)|$; $|g'(p)| > 1$ and it runs away from a fixed point that is perfectly real and perfectly unreachable; $g'(p) < 0$ and it converges alternately from each side, so consecutive iterates bracket the answer; $g'(p) = 0$ and the linear term vanishes, leaving a quadratic rate — which is exactly what Newton's method arranges. The rearrangement is the method. One equation offers many maps, and the choice between them is the choice between converging in ten steps, converging in ten thousand, and not converging at all.
Another way: steps
Another way: example
$x^{2} = x + 2$ has the root $2$. As $g(x) = x^{2} - 2$, $g'(2) = 4$ and the iteration diverges. Solving the same equation for the other $x$ gives $g(x) = \sqrt{x + 2}$, with $g'(2) = \tfrac14$, and it converges. The equation did not change; the map did.
It is easy to read $|g'(p)| < 1$ as a condition on the equation and conclude that some equations cannot be solved by iteration. It is a condition on the map, and a map is something you choose. The usual repair when a rearrangement diverges is to solve for a different occurrence of $x$, which typically replaces $g'(p)$ by something near its reciprocal — so a derivative of four becomes a derivative of a quarter, and the same equation becomes tractable.
$g(x) = \tfrac{x}{4} + 3$ has fixed point $4$ and $g'(x) = \tfrac14$ everywhere.
A constant contraction factor.
From an error of $16$ the errors run $4$, $1$, $\tfrac14$: each a quarter of the last.
Exactly linear here.
One step buys $\log_{10} 4 \approx 0.6$ of a decimal digit, every step, for ever.
Linear means a fixed gain per step.
$g(x) = 1 + \tfrac{2}{x}$ has fixed point $2$ and $g'(2) = -\tfrac12$.
Negative, and less than one in size.
The iterates land alternately above and below $2$, halving the error each time.
Converges, alternating.
Two consecutive iterates therefore bracket the root, which is a free error bound the positive case does not give you.
Alternation is useful, not a defect.
$g'(x) = -\dfrac{10}{x^{2}}$, and at the fixed point $x^{2} = 10$.
So $g'$ there is $-1$.
The size is exactly one, so the map neither contracts nor expands.
The iterates cycle between the starting value and $10$ divided by it, for ever, without approaching anything.
The map $g(x) = \dfrac{x}{4} + 3$ has the fixed point $4$. Starting from $x_0 = 36$, fill in the next two iterates and the error of each.
| Iterate | Error | |
|---|---|---|
| Start | 36 | 32 |
| After one step | ||
| After two steps |
An equation has been rearranged as $x = g(x)$ and iterated $8$ times from a start close to the fixed point $p$. Which condition decides whether the iterates approach $p$?
The equation $x^{2} - x - 2 = 0$ has the root $2$. Each map below has $2$ as a fixed point, and each is iterated $7$ times from near $2$. Match each to what happens.
| Runs away: the error is multiplied by about four each step | Converges from one side, the error quartered each step | Converges alternately above and below, the error halved each step | Converges with the number of correct digits doubling each step | |
|---|---|---|---|---|
| $g(x) = x^{2} - 2$ | ||||
| $g(x) = \sqrt{x + 2}$ | ||||
| $g(x) = 1 + \dfrac{2}{x}$ | ||||
| $g(x) = x - \dfrac{x^{2} - x - 2}{2x - 1}$ |
The map $g(x) = 3 + \dfrac{x^{2}}{4}$ has $g'(x) = \dfrac{2x}{4}$. On which set of $x$ is $|g'(x)| < 1$, so that the map is a contraction there?
This task has no paper form; do it on a device.
The map $g(x) = 4x - 9$ has the fixed point $3$. Starting from $4$, plot the size of the error after each of the first three steps.
Plot your answer on the grid:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
An iteration has $|g'(p)| = \dfrac{1}{2}$ near its fixed point and a starting error of $1$. About what is the error after $4$ steps? Give a fraction.
Answer:
You can run a fixed-point iteration, predict its error after several steps from the derivative, and say where the map contracts. Say in your own words why the same equation can give both a convergent and a divergent iteration.
8. Your turn: does iterating $g(x) = \tfrac{10}{x}$ find its fixed point?, step 3