Iteration

Many equations in mathematics cannot be solved by straightforward algebraic manipulation. For example, the equation x³ + x − 5 = 0 has no neat formula that spits out the exact answer. Numerical methods give us systematic procedures to find approximate solutions to any desired level of accuracy, and iteration is one of the most powerful of these techniques. The word 'iterate' simply means to repeat a process, using the output of one step as the input of the next. Fixed-point iteration works by rearranging an equation f(x) = 0 into the form x = g(x), and then applying the rule xₙ₊₁ = g(xₙ) repeatedly, starting from an initial guess x₀. If the sequence x₀, x₁, x₂, … converges, it homes in on a value α where α = g(α). Such a value is called a fixed point of g, and it is simultaneously a root of the original equation f(x) = 0. Whether or not the sequence actually converges depends on how steep the graph of g is near the fixed point — specifically, the iteration converges when |g′(α)| < 1. Iteration appears throughout science and engineering: computer graphics use iterative algorithms to render images, economists iterate supply-and-demand models to find equilibrium prices, and engineers refine structural designs cycle by cycle. At A-level and IB mathematics, mastering fixed-point iteration gives you a window into this vast world of numerical computation, as well as a deeper feel for how functions behave near their roots.

Key takeaways

Rearrange the equation into x = g(x) form
Choose a starting value x₀
Apply the iteration formula repeatedly
Check for convergence using the derivative criterion
Stop when the required accuracy is reached

Rearrange the equation into x = g(x) form

Start with f(x) = 0. Rearrange algebraically so that x appears alone on one side, giving x = g(x). For example, x³ + x − 5 = 0 can be rearranged as x = 5 − x³ (giving g(x) = 5 − x³) or as x = ∛(5 − x) (giving g(x) = ∛(5 − x)). Different rearrangements lead to different iteration formulas, and not all of them will converge.

Choose a starting value x₀

Pick an initial estimate x₀ close to the root. A sign-change search helps locate the root first: evaluate f at two nearby integers and look for opposite signs. For x³ + x − 5 = 0, f(1) = −3 < 0 and f(2) = 5 > 0, so the root lies between 1 and 2. A reasonable starting value is x₀ = 1.5.

Apply the iteration formula repeatedly

Compute x₁ = g(x₀), then x₂ = g(x₁), and so on: xₙ₊₁ = g(xₙ). Record several decimal places at each step. For g(x) = ∛(5 − x) starting at x₀ = 1.5: x₁ = ∛(3.5) ≈ 1.5183, x₂ = ∛(3.4817) ≈ 1.5164, x₃ ≈ 1.5162, and the values settle towards the root α ≈ 1.5161.

Check for convergence using the derivative criterion

The iteration xₙ₊₁ = g(xₙ) converges near a fixed point α if and only if |g′(α)| < 1. If |g′(α)| > 1, the iteration diverges. For g(x) = ∛(5 − x), g′(x) = −1 / [3(5 − x)^(2/3)]. Near α ≈ 1.516, g′(α) ≈ −0.115, so |g′(α)| ≈ 0.115 < 1 — the iteration converges. A diverging iteration 'staircase' away from the root on a cobweb diagram.

Stop when the required accuracy is reached

Continue iterating until consecutive values agree to the required number of decimal places. If you need the root correct to 3 decimal places, stop when |xₙ₊₁ − xₙ| < 0.0005. You can also bracket the root by showing f changes sign in a small interval, confirming accuracy. For example, f(1.5160) < 0 and f(1.5162) > 0 proves α lies in [1.5160, 1.5162], so α = 1.516 to 3 d.p.

The Key Equation

x_{n+1} = g(x_n), \quad \text{converges if } |g'(\alpha)| < 1

x_{n+1} — Next iterate (dimensionless): The new approximation to the root, produced by applying g to the previous approximation.
x_n — Current iterate (dimensionless): The approximation to the root at step n, which becomes the input for the next application of g.
g(x) — Iteration function (dimensionless): A function obtained by rearranging f(x) = 0 so that x = g(x); it maps each iterate to the next.
\alpha — Fixed point / root (dimensionless): The value where α = g(α), which is simultaneously a root of the original equation f(x) = 0.
g'(\alpha) — Derivative of g at α (dimensionless): Controls the rate of convergence; the iteration converges when its absolute value is strictly less than 1.

Worked Example

Problem. Use the iteration xₙ₊₁ = √(2xₙ + 3) to find a root of x² − 2x − 3 = 0 correct to 3 decimal places, starting with x₀ = 2.

x \approx 3.000

Answer. x = 3.000 (to 3 decimal places)

Figure

Diagram

Origins · 1 minJoseph-Louis Lagrange and how this was discovered

Joseph-Louis Lagrange

1736–1813 · Italian-French

Lagrange made foundational contributions to the theory of equations and numerical methods. He developed rigorous error bounds for iterative approximations and studied the convergence of sequences of approximations to roots, work that underpins the modern theory of fixed-point iteration. His 'Lagrange inversion theorem' provides explicit series for the roots of equations in terms of iterative processes. Lagrange was so absorbed in mathematics from an early age that by 19 he had become a professor at the Royal Artillery School in Turin — without ever having attended a university himself.

Bisection Method — Another numerical root-finding technique: it repeatedly halves an interval known to contain a root. Comparing bisection with iteration illustrates the trade-off between guaranteed convergence and speed.
Sign-Change Root Location — Before iterating, you need to locate which interval contains a root. Sign-change arguments using the Intermediate Value Theorem provide the starting bracket that makes iteration reliable.
Derivatives and Differentiation — The convergence criterion |g′(α)| < 1 requires you to differentiate g. Understanding derivatives is therefore essential for deciding whether a given iteration formula will work.
Newton–Raphson Method — A special, very fast iteration: xₙ₊₁ = xₙ − f(xₙ)/f′(xₙ). It can be viewed as a particular choice of g(x) and typically converges much faster than basic fixed-point iteration.