NM2, NM3 - Iteration and when methods fail

Iteration feeds an answer back into a formula to obtain the next answer. NM2 uses this simple loop to approximate roots; NM3 explains why a sensible-looking loop, or a change-of-sign search, can sometimes fail. You will learn to show the numerical evidence and decide what it really establishes.

Rearranging and using an iteration

Can the same equation give one calculator loop that settles down and another that runs into trouble? Yes: rearranging an equation preserves its roots, but it can completely change the behaviour of the loop. We will find out why.

You already know

A recurrence relationship uses one term to calculate the next. To locate a root by change of sign, evaluate a continuous function at two endpoints and find opposite signs. Keep full calculator precision between steps.

Start with $x^3-x-4=0$ . Rearranging gives $x^3=x+4$ , then $x=\sqrt[3]{x+4}$ . If a number solves the equation, this last operation returns the same number. We use it to turn an initial estimate into successive estimates.

Iteration and fixed point

An iteration $x_{r+1}=\mathrm{g}(x_r)$ repeatedly applies the same function, starting from $x_0$ . A fixed point $\alpha$ satisfies $\alpha=\mathrm{g}(\alpha)$ . For an equivalent rearrangement of the original equation, such a fixed point is a root of that equation.

There is no universal iterative formula on the formulae sheet: learn how to rearrange the equation, and use the specific formula supplied or obtained. The index advances on the left; the right uses the previous term. An ANS key is useful because it retains digits you do not write down.

Worked example 1: a cube-root iteration

Question. Rearrange $x^3-x-4=0$ into an iterative formula. Starting with $x_0=2$ , find the root correct to $3$ significant figures.

Plan. Isolate $x^3$ , take the cube root, then iterate until successive values settle at the requested accuracy.

\begin{aligned} x^3&=x+4 &&\text{rearrange}\\ x&=\sqrt[3]{x+4} &&\text{take cube roots}\\ x_{r+1}&=\sqrt[3]{x_r+4} &&\text{use the previous estimate}\\ x_1&=\sqrt[3]{2+4}=1.817120593\ldots &&\text{first substitution}\\ x_2&=\sqrt[3]{x_1+4}=1.798467893\ldots &&\text{retain calculator digits}\\ x_3&=1.796543562\ldots &&\text{repeat}\\ x_4&=1.796344801\ldots &&\text{repeat}\\ x_5&=1.796324269\ldots &&\text{values settling} \end{aligned}

Why take a cube root? It leaves a single $x$ on the left and a simple function of the previous value on the right. Algebra alone does not guarantee convergence; the iterates provide evidence that this rearrangement is useful here.

Answer. The root is $1.80$ correct to $3$ significant figures.

Check. For $\mathrm{f}(x)=x^3-x-4$ , $\mathrm{f}(1.795)<0<\mathrm{f}(1.805)$ . This brackets the root between the rounding boundaries for $1.80$ .

The next example changes only the constant. Keep exactly the same method and check the rounding again.

Worked example 2: another constant, the same loop

Question. Starting with $x_0=2$ , use a suitable iteration to solve $x^3-x-5=0$ , correct to $3$ significant figures.

Plan. Replace the constant in the cube-root rearrangement and calculate enough terms to support the answer.

\begin{aligned} x^3-x-5=0&\Longrightarrow x^3=x+5 &&\text{isolate the cubic term}\\ x_{r+1}&=\sqrt[3]{x_r+5} &&\text{equivalent fixed-point form}\\ x_1&=1.912931183\ldots &&\text{put }x_0=2\\ x_2&=1.904966800\ldots &&\text{repeat using ANS}\\ x_3&=1.904234949\ldots &&\text{repeat}\\ x_4&=1.904167670\ldots &&\text{repeat}\\ x_5&=1.904161485\ldots &&\text{values settling} \end{aligned}

Why retain the unrounded terms? Feeding back $1.90$ instead of the stored term changes the iteration. Round the final answer, not the calculation loop.

Answer. The root is $1.90$ correct to $3$ significant figures.

Check. For $\mathrm{f}(x)=x^3-x-5$ , $\mathrm{f}(1.895)<0<\mathrm{f}(1.905)$ , so the rounding is justified even though the root lies close to $1.905$ .

Two consecutive values rounding alike are useful evidence in a convergent sequence, but not a proof that every iteration works. Later terms, a graph and a sign bracket can expose a misleading early pattern.

Watch out

Wrong: $x_{r+1}=\sqrt[3]{x_{r+1}+5}$ . This asks you to find the new term before you can calculate it. Right: $x_{r+1}=\sqrt[3]{x_r+5}$ , using the term already known.

Now change the constant once more and show the actual terms, rather than only a calculator root.

Convergence, divergence and cycles

An iteration succeeds when its terms approach the required root; being an equivalent rearrangement is only the starting point.

The graph of $y=\mathrm{g}(x)$ meets $y=x$ at a fixed point. To follow an iteration on the graph, move vertically from the line to the curve, then horizontally back to the line. Repeat. The picture shows whether the steps shrink towards the crossing or grow away from it.

[DIAGRAM: asset_name: Shrinking and growing iteration steps; asset_slug: nm2-iteration-steps; caption: A gentle graph draws the iteration towards a fixed point, while a steep graph can push it away; description: Two graphs compare y equals 0.5x plus 1 and y equals 1.5x minus 1 with the line y equals x. Both cross at (2, 2). Starting from 2.2, staircase steps shrink towards 2 in the first graph and grow away from 2 in the second]
A gentle graph draws the iteration towards a fixed point, while a steep graph can push it away

For the left-hand graph, $x_{r+1}=0.5x_r+1$ and $x_0=2.2$ give $2.1$ , $2.05$ , $2.025$ , $2.0125$ . The error relative to $2$ halves each time. For the right-hand graph, $x_{r+1}=1.5x_r-1$ gives $2.3$ , $2.45$ , $2.675$ , $3.0125$ . Its error is multiplied by $1.5$ . The same fixed point can attract one loop and repel another.

Convergence and failure to converge

A sequence converges to $\alpha$ when its terms approach $\alpha$ . It fails to converge to $\alpha$ if, for example, its terms move away from $\alpha$ , keep repeating a cycle of distinct values, or become undefined.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Algebra

Enumeration (counting and probability)

Coordinate geometry

Pythagoras' theorem and trigonometry

Calculus

Exponentials and logarithms

Numerical methods

NM2, NM3 - Iteration and when methods fail

Rearranging and using an iteration

Convergence, divergence and cycles

Continue this lesson.

Learn faster with Nova