Why we need numerical methods
Some equations, like x³ − x − 1 = 0 or eˣ = 3x, have no simple formula for x. A numerical method is a set of simple steps that we repeat to get closer and closer to the answer. Each repeat is called an iteration.
Change of sign
If f(x) is continuous (no breaks or jumps) on [a, b], and f(a) and f(b) have opposite signs, then there is at least one root between a and b.
Example: f(1) = −1 and f(2) = 5, so x³ − x − 1 = 0 has a root between 1 and 2.
When the sign test fails
- Two roots close together: the sign may change twice and look like no change.
- A repeated root that just touches the axis (like y = (x − 2)²) gives no sign change at all.
- A break (asymptote) like y = 1/x changes sign at x = 0 but has no root there.
To show a root is 1.32 to 2 decimal places, check f(1.315) and f(1.325) have opposite signs.
Finding roots: bisection, Newton-Raphson and fixed-point iteration
Interval bisection
Start with [a, b] where the sign changes. Find the middle m = (a + b) ÷ 2. Keep the half that still has a sign change. Each step halves the width, so it always works, but it is slow: about 3 to 4 halvings per extra correct decimal place.
Newton-Raphson
xₙ₊₁ = xₙ − f(xₙ) ÷ f′(xₙ)
The tangent at xₙ is a straight line that hugs the curve. Where it meets the x-axis is the next guess. Near the root, the number of correct digits roughly doubles each step. It fails if f′(xₙ) = 0 (flat tangent, no crossing) or if the start is far away and the tangents jump off to another root.
Fixed-point iteration
Rearrange f(x) = 0 into x = g(x) and repeat xₙ₊₁ = g(xₙ). On a graph of y = x and y = g(x) this makes a staircase or a cobweb. It converges if |g′(x)| < 1 near the root. For x³ − x − 1 = 0, the form x = ∛(x + 1) converges, but x = x³ − 1 does not.
Writing it as an algorithm
In computing, bisection is a loop: while b − a > tolerance: m = (a + b)/2; if f(a)·f(m) < 0 then b = m else a = m. Storing each value in a list lets you see the sequence of estimates.
Numerical integration: the trapezium rule
To estimate ∫ₐᵇ f(x) dx, split [a, b] into n strips of width h = (b − a) ÷ n. Join the tops with straight lines, so each strip is a trapezium.
Area ≈ (h ÷ 2) × [y₀ + yₙ + 2(y₁ + y₂ + … + yₙ₋₁)]
The first and last heights are used once; every middle height is shared by two strips, so it is counted twice.
- If the curve bends upwards (convex, like y = x²), the straight tops sit above it: an over-estimate.
- If it bends downwards (concave, like y = √x), an under-estimate.
- Doubling n makes the error about 4 times smaller.
Other rules exist: the mid-ordinate rule uses rectangles at the middle of each strip, and Simpson's rule fits curves (parabolas) instead of straight lines.
Small steps: Euler's method for motion and growth
Often we know a rule for change (a differential equation), such as dy/dx = f(x, y), and a starting value. Euler's method walks forward in steps of size h:
xₙ₊₁ = xₙ + h, yₙ₊₁ = yₙ + h × f(xₙ, yₙ)
In physics this is the method of small steps: in each small time Δt, new velocity = old velocity + a × Δt, and new position = old position + v × Δt. A spreadsheet or a short program repeats this thousands of times to model a falling ball with air resistance or a cooling cup of tea.
Smaller steps give better answers but need more work. Errors also build up step by step, so check by halving h and seeing if the answer changes.
Errors, accuracy and choosing a method
- Absolute error = |estimate − true value|. Relative error = absolute error ÷ |true value| (often as a %).
- Rounding error comes from keeping only some digits; truncation error comes from stopping a method early or using straight lines for curves.
- A method converges if the estimates settle down to one value.
| Method | Speed | Always works? |
|---|---|---|
| Bisection | slow, steady | yes, if a sign change exists |
| Newton-Raphson | very fast near root | no: needs f′ ≠ 0 and a good start |
| Fixed-point | medium | only if |g′| < 1 |
Try it at home
On a calculator type 1 and press =. Then type ∛(Ans + 1) and keep pressing =. Watch the numbers settle at 1.3247. You have just done fixed-point iteration.
Key formulas and definitions
- Change of sign: f continuous on [a, b] and f(a)·f(b) < 0 ⇒ a root lies in (a, b)
- Bisection midpoint: m = (a + b) ÷ 2
- Newton-Raphson: xₙ₊₁ = xₙ − f(xₙ) ÷ f′(xₙ)
- Fixed-point iteration: xₙ₊₁ = g(xₙ), converges if |g′(x)| < 1 near the root
- Trapezium rule: ∫ₐᵇ y dx ≈ (h/2)[y₀ + yₙ + 2(y₁ + … + yₙ₋₁)], h = (b − a)/n
- Euler: yₙ₊₁ = yₙ + h·f(xₙ, yₙ)
- Relative error = |estimate − true| ÷ |true|
Worked examples
1. Show that x³ − x − 1 = 0 has a root between 1 and 2.
f(1) = 1 − 1 − 1 = −1 < 0. f(2) = 8 − 2 − 1 = 5 > 0. f is a polynomial, so it is continuous. The sign changes, so there is a root in (1, 2).
2. Do two steps of bisection on f(x) = x³ − x − 1 starting from [1, 2].
m = 1.5: f(1.5) = 3.375 − 1.5 − 1 = 0.875 > 0, sign change is between 1 and 1.5, new interval [1, 1.5]. m = 1.25: f(1.25) = 1.953 − 1.25 − 1 = −0.297 < 0, new interval [1.25, 1.5].
3. Use Newton-Raphson with x₀ = 2 to find x₁ and x₂ for x³ − x − 1 = 0.
f′(x) = 3x² − 1. x₁ = 2 − 5 ÷ 11 = 1.5455. f(1.5455) = 1.1458, f′(1.5455) = 6.1655, so x₂ = 1.5455 − 1.1458 ÷ 6.1655 = 1.3596. (The root is 1.3247.)
4. Use xₙ₊₁ = ∛(xₙ + 1) with x₀ = 1 to find x₁, x₂, x₃.
x₁ = ∛2 = 1.2599. x₂ = ∛2.2599 = 1.3123. x₃ = ∛2.3123 = 1.3224. The values climb in a staircase towards 1.3247.
5. Estimate ∫₀² x² dx with the trapezium rule and 4 strips. Is it an over- or under-estimate?
h = 0.5. Heights: 0, 0.25, 1, 2.25, 4. Area ≈ 0.25 × [0 + 4 + 2(0.25 + 1 + 2.25)] = 0.25 × 11 = 2.75. Exact = 8/3 = 2.667. Over-estimate, because y = x² bends upwards.
6. dy/dx = y, y(0) = 1. Use Euler with h = 0.5 to estimate y(1). Find the percentage error.
y₁ = 1 + 0.5 × 1 = 1.5 (at x = 0.5). y₂ = 1.5 + 0.5 × 1.5 = 2.25 (at x = 1). True y(1) = e ≈ 2.718. Error = 0.468, relative error ≈ 0.468 ÷ 2.718 ≈ 17%.
7. A ball is dropped (a = 9.8 m/s²). Use small steps of Δt = 0.1 s to find v and s after 0.3 s.
Each step: v_new = v + 9.8 × 0.1 = v + 0.98; s_new = s + v × 0.1 (using the old v). t = 0.1: v = 0.98, s = 0. t = 0.2: v = 1.96, s = 0.098. t = 0.3: v = 2.94, s = 0.294 m. True s = ½ × 9.8 × 0.09 = 0.441 m; smaller steps reduce the gap.
Common mistakes
- Forgetting to check that f is continuous: 1/x changes sign at 0 but has no root there.
- Using degrees instead of radians when f contains sin x or cos x.
- In the trapezium rule, counting the number of ordinates instead of strips: 4 strips need 5 heights.
- Rounding each Newton-Raphson step too early: keep full calculator values and round only at the end.