Running an iteration to find a root

Some equations, such as $x^3 - 3x - 4 = 0$, can't be solved exactly with algebra you know. But we can still find the root as accurately as we like, by improving a guess over and over. That is what an iteration does.

An iteration formula looks like

$x_{n+1} = F(x_n)$

Read it as: "to get the next value, put the current value into $F$." Start with $x_1$, put it in to get $x_2$, put $x_2$ in to get $x_3$, and so on. Each output becomes the next input.

Where does $F$ come from? From rearranging the equation into the form $x = F(x)$. For example:

$x^3 - 3x - 4 = 0 \;\Rightarrow\; x^3 = 3x + 4 \;\Rightarrow\; x = \sqrt[3]{3x + 4}$

So the iteration $x_{n+1} = \sqrt[3]{3x_n + 4}$ comes from this equation.

Why does it find the root? If the values settle down to a single number $\alpha$, then for large $n$ both $x_n$ and $x_{n+1}$ are (almost exactly) $\alpha$. Putting that into the formula gives $\alpha = F(\alpha)$, which is the rearranged equation. So the number the values settle at is a root of the equation.

The diagram shows this as a "staircase". Each step goes up to the curve $y = F(x)$ (working out the next value) and across to the line $y = x$ (making that output the next input). The steps shrink as they close in on the point where the curve meets the line, and that point is the root.

1. Put $x_1$ into $F$ to get $x_2$. Write it down. Use your calculator's Ans key so you never retype a rounded number: type $x_1$, press equals, then type the formula using Ans and press equals repeatedly.
2. Write down each value to more decimal places than the final answer needs (two extra is plenty).
3. Stop when two values in a row round to the same answer at the accuracy asked for. That rounded value is the root.

Why does that rule work? Once two successive values agree to, say, 3 decimal places, the steps have become smaller than the size of that rounding, so later values are very unlikely to change the 3-decimal-place answer. (If you need to be certain, a sign-change check either side of the answer, like the one in the first lesson of this topic, proves it.)