Numerical iteration for equation roots · Higher
Introduit| English | Sens |
|---|---|
| iteration/ˌɪtəˈreɪʃn/ | itération |
$\sqrt{2}$ on a clay tablet
- The Babylonian tablet YBC 7289, from about 1800 BC, gives $\sqrt{2}$ as 1.414213 — correct to 6 decimal places. It was probably found by repeating a rule that improves a guess each time.
- That repeating process is iteration 迭代.
The idea
- Rearrange the equation into the form $x = g(x)$, then use $x_{n+1} = g(x_n)$.
- Start with a guess $x_0$; each new value is fed back in.
An example
- $x^2 - x - 2 = 0$ rearranges to $x^2 = x + 2$, so $x = \sqrt{x + 2}$.
- Iterate $x_{n+1} = \sqrt{x_n + 2}$ from $x_0 = 1$.
Which is a rearrangement of $x^3 + 4x - 1 = 0$?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
$4x = 1 - x^3$.
Worked example: iterating
- $x_1$ $= \sqrt{3} \approx 1.73205$; $x_2$ $= \sqrt{3.73205} \approx 1.93185$; $x_3$ $\approx 1.98289$.
- Limit: the values approach 2. Check in the original: $4 - 2 - 2 = 0$ ✓.
- Note: this rearrangement finds only the positive root; the equation also has $x = -1$.
Numerical iteration for equation roots
Rearrange an equation as x=g(x), choose x₀ and use x_(n+1)=g(x_n)
Compare the model with the worked case and explain one change.
Use $x_{n+1} = \sqrt{x_n + 6}$ with $x_0 = 2$. Find $x_1$ to 4 decimal places.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
$\sqrt{8}$.
The iteration $x_{n+1} = \sqrt{x_n + 6}$ converges. To what value?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
$x = \sqrt{x + 6}$ gives $x^2 - x - 6 = 0$, positive root 3.
Locating a root first
- A sign change shows a root: if $f(1) < 0$ and $f(2) > 0$, a root lies between 1 and 2 (for a smooth curve).
- For $f(x) = x^3 - 2x - 5$: $f(2) = -1$, $f(3) = 16$, so a root is between 2 and 3.
$f(x) = x^3 - 3x - 1$. Between which whole numbers is there a root?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
$f(1) = -3$, $f(2) = 1$.
When iteration fails
- A different rearrangement, $x_{n+1} = x_n^2 - 2$ from 3, gives 7, 47, … — it diverges.
- If values run away, try another rearrangement.
Every rearrangement $x = g(x)$ of an equation converges to a root.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Some diverge.
Do not round between steps. Keep the full calculator value (use the ANS key). Rounding each $x_n$ to 2 d.p. can change later digits of the answer.
What is the best practice when iterating on a calculator?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Avoid early rounding.
Rearrange $f(x) = 0$ into $x = g(x)$ and iterate $x_{n+1} = g(x_n)$ from a starting value, keeping full accuracy. A sign change locates a root. Not every rearrangement converges, and one may miss some roots.
Show that $x^3 + x = 7$ has a root between 1 and 2, then use $x_{n+1} = \sqrt[3]{7 - x_n}$ from $x_0 = 2$ for three steps.
Locate then iterate.