Iterative Methods

This lesson covers iterative methods for solving equations — rearranging f(x) = 0 into the form x = g(x) and using iteration — as required by the Edexcel A-Level Mathematics specification (9MA0). You need to understand convergence and divergence, and interpret staircase and cobweb diagrams.

---

Why Iterative Methods?

Many equations cannot be solved exactly using algebraic methods. For example:

• x³ + 3x - 7 = 0
• eˣ = 3x
• x = cos x

In these cases, we use numerical methods to find approximate solutions. Iterative methods generate a sequence of values x₁, x₂, x₃, ... that (hopefully) converge to the root.

---

The Fixed-Point Iteration Method

The Idea

1. Start with the equation f(x) = 0.
2. Rearrange it into the form x = g(x).
3. Choose a starting value x₀.
4. Apply the iteration formula: x_{n+1} = g(x_n) repeatedly.
5. If the sequence converges, the limit is a root of the original equation.

Why Does This Work?

If the sequence converges to a limit L, then as n → ∞: x_{n+1} → L and x_n → L

So the iteration formula x_{n+1} = g(x_n) becomes L = g(L).

This means L satisfies x = g(x), which is equivalent to f(x) = 0.

---

Worked Example

Solve x³ + 3x - 7 = 0 near x = 1.

Step 1: Rearrange to x = g(x). x³ + 3x - 7 = 0 → 3x = 7 - x³ → x = (7 - x³)/3

So g(x) = (7 - x³)/3.

Step 2: Choose x₀ = 1 and iterate.

n	x_n
0	1
1	(7 - 1)/3 = 2
2	(7 - 8)/3 = -1/3 = -0.3333
3	(7 - (-0.3333)³)/3 = (7 + 0.0370)/3 = 2.3457
4	(7 - 12.917)/3 = -1.9724

The values are oscillating and getting further apart — this rearrangement is diverging. We need a different rearrangement.

Step 3: Try another rearrangement. x³ + 3x - 7 = 0 → x³ = 7 - 3x → x = (7 - 3x)^(1/3)

So g(x) = (7 - 3x)^(1/3).

n	x_n
0	1
1	(7 - 3)^(1/3) = 4^(1/3) = 1.5874
2	(7 - 4.7622)^(1/3) = 2.2378^(1/3) = 1.3077
3	(7 - 3.9231)^(1/3) = 3.0769^(1/3) = 1.4547
4	(7 - 4.3641)^(1/3) = 2.6359^(1/3) = 1.3809
5	1.4186
6	1.3998
7	1.4093

The values are converging to approximately x ≈ 1.405.

Key Point: The same equation can have multiple rearrangements. Some converge and some diverge. The choice of rearrangement matters.

---

Convergence and Divergence

The Condition for Convergence

The iteration x_{n+1} = g(x_n) converges to a root α if:

|g'(α)| < 1

The iteration diverges if |g'(α)| > 1.

Intuition

• If |g'(x)| < 1 near the root, the function g "contracts" — each successive value gets closer to the root.
• If |g'(x)| > 1 near the root, the function g "expands" — each successive value gets further from the root.

---

Staircase and Cobweb Diagrams

These diagrams illustrate how the iteration works graphically by plotting y = g(x) and y = x.

Staircase Diagram

When the iteration converges monotonically (each value approaches from the same side), the path traces a staircase pattern:

• Start at x₀ on the x-axis.
• Go vertically to y = g(x) to get g(x₀) = x₁.
• Go horizontally to y = x (which effectively makes x₁ the new input).
• Repeat: vertical to y = g(x), horizontal to y = x.

This produces a staircase pattern approaching the intersection of y = g(x) and y = x.

A staircase occurs when 0 < g'(α) < 1.

Cobweb Diagram

When the iteration converges with values alternating above and below the root, the path traces a cobweb (spiral) pattern.

A cobweb occurs when -1 < g'(α) < 0.

Divergent Cases

• If g'(α) > 1: staircase moving away from the root (diverging).
• If g'(α) < -1: cobweb spiralling outward (diverging).

---

Starting Values

The choice of starting value x₀ can affect whether the iteration converges:

• If x₀ is too far from the root, the iteration may diverge even with a good rearrangement.
• A good starting value can be found by sketching the graphs or using the sign-change method.

---

Multiple Rearrangements

Any equation f(x) = 0 can be rearranged into x = g(x) in many different ways.

Example: x³ - 5x + 3 = 0

Possible rearrangements:

• x = (x³ + 3)/5 → g(x) = (x³ + 3)/5
• x = (5x - 3)^(1/3) → g(x) = (5x - 3)^(1/3)
• x = 3/(5 - x²) → g(x) = 3/(5 - x²)

Each rearrangement may converge to a different root or may not converge at all. Check |g'(x)| < 1 near the expected root to predict convergence.

---

Worked Example with Convergence Check

Use the iteration x_{n+1} = √(5 - 1/x_n) to find a root of x² + 1/x - 5 = 0, starting from x₀ = 2.

n	x_n
0	2
1	√(5 - 0.5) = √4.5 = 2.1213
2	√(5 - 1/2.1213) = √(5 - 0.4714) = √4.5286 = 2.1281
3	√(5 - 1/2.1281) = √4.5302 = 2.1285

The sequence is converging rapidly to x ≈ 2.128.

Convergence check: g(x) = √(5 - 1/x), so g'(x) = 1/(2√(5 - 1/x)) × 1/x²

At x ≈ 2.128: g'(2.128) ≈ 0.052. Since |0.052| < 1, the iteration converges.

---

Common Mistakes

1. Using a divergent rearrangement — If the iteration is clearly diverging (values getting further apart or oscillating wildly), try a different rearrangement.
2. Not giving enough decimal places — Questions usually specify accuracy; continue iterating until the required number of decimal places stabilises.
3. Forgetting to check convergence — The condition |g'(α)| < 1 determines whether a rearrangement will work.
4. Confusing convergence to different roots — Different rearrangements and starting values can lead to different roots.

---

Summary

• Rearrange f(x) = 0 into x = g(x) and iterate: x_{n+1} = g(x_n).
• Convergence occurs when |g'(α)| < 1 at the root.
• Staircase diagrams (0 < g'(α) < 1): monotonic convergence.
• Cobweb diagrams (-1 < g'(α) < 0): oscillating convergence.
• Different rearrangements may converge to different roots or diverge.
• The starting value x₀ should be chosen close to the expected root.

A-Level Deep Dive: Iterative Methods

Spec mapping

Edexcel 9MA0-02 specification section 13 — Numerical methods, sub-strand 13.3 covers equations approximately using simple iterative methods; be able to draw associated cobweb and staircase diagrams (refer to the official specification document for exact wording). This sits inside Year 2 Pure Mathematics and is examined on Paper 2. It builds directly on sub-strand 13.1 (locate roots of $f(x) = 0$f(x)=0 by sign change) and sub-strand 13.4 (Newton–Raphson). Iterative methods also appear synoptically with section 6 (logarithms and exponentials) when rearrangements involve $\ln$ln or $e^x$ex, with section 7 (sequences and series) through the recurrence-relation framing $x_{n+1} = g(x_n)$xn+1​=g(xn​), and with section 9 (differentiation) because the convergence test $|g'(x^*)| < 1$∣g′(x∗)∣<1 requires confident calculus. The Edexcel formula booklet does not list any iterative-method results — convergence criteria and rearrangement strategies must be memorised.

---

Worked example with full mark scheme

Question (8 marks): The equation $x^3 - 3x + 1 = 0$x3−3x+1=0 has a root $\alpha$α in the interval $(0, 1)$(0,1).

(a) Show that the equation can be rearranged into the form $x = \dfrac{x^3 + 1}{3}$x=3x3+1​. (1)

(b) Using the iterative formula $x_{n+1} = \dfrac{x_n^3 + 1}{3}$xn+1​=3xn3​+1​ with $x_0 = 0.4$x0​=0.4, find $x_1$x1​, $x_2$x2​ and $x_3$x3​, giving each value to 4 decimal places. (3)

(c) By considering $g'(x)$g′(x) where $g(x) = \dfrac{x^3 + 1}{3}$g(x)=3x3+1​, comment on whether the iteration converges to $\alpha$α. (4)

Solution with mark scheme:

(a) Starting from $x^3 - 3x + 1 = 0$x3−3x+1=0, add $3x$3x to both sides:

$x^3 + 1 = 3x \implies x = \dfrac{x^3 + 1}{3}$x3+1=3x⟹x=3x3+1​

B1 — correct rearrangement shown with at least one intermediate step. Examiners will not award the mark for simply stating the result; the algebraic move $+3x$+3x (or equivalent) must appear.

(b) Substitute repeatedly:

$x_1 = \dfrac{(0.4)^3 + 1}{3} = \dfrac{0.064 + 1}{3} = \dfrac{1.064}{3} = 0.3547 \,(4\text{ dp})$x1​=3(0.4)3+1​=30.064+1​=31.064​=0.3547(4 dp).

M1 — correct substitution into the iterative formula and at least one value reported to a sensible accuracy.

$x_2 = \dfrac{(0.3547)^3 + 1}{3} = \dfrac{0.04464 + 1}{3} = 0.3482 \,(4\text{ dp})$x2​=3(0.3547)3+1​=30.04464+1​=0.3482(4 dp).

$x_3 = \dfrac{(0.3482)^3 + 1}{3} = \dfrac{0.04221 + 1}{3} = 0.3474 \,(4\text{ dp})$x3​=3(0.3482)3+1​=30.04221+1​=0.3474(4 dp).

A1 — correct $x_1 = 0.3547$x1​=0.3547 to 4 dp.

A1 — correct $x_2$x2​ and $x_3$x3​ both to 4 dp; small rounding tolerances accepted provided the candidate's chain is internally consistent.

(c) Differentiate $g(x) = \dfrac{x^3 + 1}{3}$g(x)=3x3+1​:

$g'(x) = \dfrac{3x^2}{3} = x^2$g′(x)=33x2​=x2

M1 — correct derivative $g'(x) = x^2$g′(x)=x2.

The sequence appears to be converging toward $\alpha \approx 0.347$α≈0.347 (continuing the iteration stabilises near this value). At the root, $|g'(\alpha)| = \alpha^2 \approx (0.347)^2 \approx 0.120$∣g′(α)∣=α2≈(0.347)2≈0.120.

M1 — evaluating $|g'(x)|$∣g′(x)∣ at (or near) the root using the candidate's iterated values.

Since $|g'(\alpha)| \approx 0.120 < 1$∣g′(α)∣≈0.120<1, the iteration converges to $\alpha$α from $x_0 = 0.4$x0​=0.4.

A1 — correct numerical value of $|g'(\alpha)|$∣g′(α)∣ stated and compared with 1.

A1 — explicit conclusion linking $|g'(\alpha)| < 1$∣g′(α)∣<1 to convergence, with the magnitude (significantly less than 1) suggesting fairly rapid convergence — a "staircase" pattern toward the root because $g'$g′ is positive.

Total: 8 marks (B1 M3 A4, split as shown).

---

Specimen question modelled on the Edexcel 9MA0 Paper 2 format

Question (6 marks): The equation $2x - \cos x - 1 = 0$2x−cosx−1=0 has a single real root $\beta$β in the interval $(0.5, 1)$(0.5,1).

(a) Show that the equation can be written in the form $x = \dfrac{1 + \cos x}{2}$x=21+cosx​. (1)

(b) Use the iterative formula $x_{n+1} = \dfrac{1 + \cos x_n}{2}$xn+1​=21+cosxn​​ with $x_0 = 0.8$x0​=0.8 to find $x_1$x1​, $x_2$x2​ and $x_3$x3​, each to 4 decimal places. (Use radians.) (3)

(c) Determine whether the iteration produces a cobweb or a staircase pattern around $\beta$β, justifying your answer. (2)

Mark scheme decomposition by AO:

(a)

• B1 (AO1.1a) — adding $\cos x + 1$cosx+1 to both sides and dividing by 2, with at least one intermediate line of working visible.

(b)

• M1 (AO1.1b) — correct substitution $x_1 = (1 + \cos 0.8)/2$x1​=(1+cos0.8)/2 in radian mode.
• A1 (AO1.1b) — $x_1 \approx 0.8484$x1​≈0.8484 to 4 dp (accept any value within $\pm 0.0005$±0.0005 of the rounded chain).
• A1 (AO1.1b) — $x_2 \approx 0.8307$x2​≈0.8307 and $x_3 \approx 0.8375$x3​≈0.8375 both correct to 4 dp.

(c)

• M1 (AO2.4) — differentiating $g(x) = (1 + \cos x)/2$g(x)=(1+cosx)/2 to obtain $g'(x) = -\tfrac{1}{2}\sin x$g′(x)=−21​sinx and evaluating near $\beta \approx 0.834$β≈0.834, giving $g'(\beta) \approx -0.371$g′(β)≈−0.371.
• A1 (AO2.5) — concluding that because $g'(\beta) < 0$g′(β)<0 (with $|g'(\beta)| < 1$∣g′(β)∣<1), successive iterates alternate either side of $\beta$β, producing a cobweb pattern that converges.

Total: 6 marks split AO1 = 4, AO2 = 2. This is a classic Paper 2 specimen — procedural iteration earns AO1, while the cobweb-vs-staircase reasoning is rewarded as AO2 because it demands interpretation of the sign of $g'$g′.

---

Synoptic links

Connects to:

1. Section 13.4 — Newton–Raphson method (next lesson): Newton–Raphson is itself a fixed-point iteration with $g(x) = x - \dfrac{f(x)}{f'(x)}$g(x)=x−f′(x)f(x)​. The convergence condition $|g'(x^*)| < 1$∣g′(x∗)∣<1 is automatic at a simple root because $g'(x^*) = 0$g′(x∗)=0 — which explains why Newton–Raphson typically converges quadratically compared with the linear convergence of generic fixed-point iteration.
2. Section 13.1 — Locating roots by sign change: before iterating, candidates must establish that a root exists in some interval. The intermediate value theorem (continuous $f$f with $f(a)f(b) < 0$f(a)f(b)<0) is the standard preliminary step. Iteration without a located root is a common procedural error.
3. Section 7 — Sequences and series: the iterative formula $x_{n+1} = g(x_n)$xn+1​=g(xn​) is just a recurrence relation. Convergence to a fixed point is the same idea as a sequence converging to a limit, and the condition $L = g(L)$L=g(L) at the limit is the fixed-point equation.
4. Further Maths — Differential equations and Euler's method: Euler's method $y_{n+1} = y_n + h f(x_n, y_n)$yn+1​=yn​+hf(xn​,yn​) is structurally a fixed-point iteration in disguise, used to approximate solutions of $\dfrac{dy}{dx} = f(x, y)$dxdy​=f(x,y). The same convergence and stability questions reappear in numerical ODE solvers.
5. Computer science — Fixed-point algorithms: iterative algorithms such as PageRank (eigenvector via repeated multiplication), Newton-style optimisation, and many machine-learning training loops are fixed-point iterations. The intuition built here — "apply $g$g repeatedly and check convergence" — generalises to vast areas of computation.

---

Mark-scheme literacy

Iterative-method questions on 9MA0-02 split AO marks more evenly than algebra topics:

AO	Typical share	Earned by
AO1 (knowledge / procedure)	50–60%	Correct substitution into the iterative formula, accurate decimal values, evaluating $g'(x)$g′(x) correctly
AO2 (reasoning / interpretation)	30–40%	Justifying the rearrangement choice, comparing $
AO3 (problem-solving)	5–15%	Choosing between competing rearrangements, deciding whether to refine $x_0$x0​, recognising when an iteration diverges and selecting an alternative form