Numerical methods
How computers find roots and areas step by step.
Pen and paper is fine · no calculator needed why?
Opens at level 54. You're level 1. You can read and practice here now.
the idea
Many equations and integrals have no tidy formula, so computers approximate them with fixed recipes.
Newton’s method moves a guess to where the tangent line meets the x-axis, usually closer to the root. Bisection halves an interval that holds a root. The trapezoid rule and Simpson’s rule estimate the area under a curve from its heights at equally spaced points.
techniques
One Newton step
- Work out f(x₀) and the slope f′(x₀).
- x₁ = x₀ − f(x₀)/f′(x₀): where the tangent line crosses the x-axis.
worked example
Apply one step of Newton’s method to f(x) = x² − 7, starting from x₀ = 3. What is x₁? Give an exact fraction.
- f(3) is 9 − 7, which is 2. f′(x) is 2x, so f′(3) is 6.
- x₁ = 3 − 2/6 = 3 − 1/3 = 8/3.
Answer: 8/3
Halve and keep the sign change
- Find the sign of f at the midpoint.
- Keep the half whose ends give opposite signs. Repeat as many times as asked.
- Answer with the midpoint of the last interval.
worked example
Start with [1, 2] for f(x) = x² − 2. Test the midpoint and keep the half where f changes sign. Do this twice. What is the midpoint of the interval you end with? Give the answer as a decimal.
- f(1) is negative. f(1.5) is 0.25, positive: keep [1, 1.5].
- f(1.25) is −0.4375, negative: keep [1.25, 1.5].
- Its midpoint is 1.375.
Answer: 1.375
Weight the heights
- Work out f at each point.
- Trapezoid rule: weights 1, 2, 2, …, 2, 1, then multiply the sum by h/2.
- Simpson’s rule, 2 strips: weights 1, 4, 1, then multiply by h/3. It is exact for polynomials up to x³.
worked example
Use the trapezoid rule with 2 strips of width 1 to estimate ∫₁³ x² dx. Give the estimate as a decimal.
- At x = 1, 2 and 3, x² is 1, 4 and 9.
- 1 + 2 × 4 + 9 = 18.
- Times h/2: 18 ÷ 2 = 9.
- The exact value is 26/3 ≈ 8.67, so the estimate is a little high.
Answer: 9
watch out for
- Getting the sign of the Newton step wrong. When f(x₀)/f′(x₀) is negative, subtracting it makes x₁ bigger than x₀.
- Giving the last point you tested instead of the midpoint of the last interval.
- Forgetting to double the inside heights, or using the trapezoid weights for Simpson’s rule.
practice
Newton’s method
worked example
Apply one step of Newton’s method to f(x) = x³ − 58, starting from x₀ = 3. What is x₁? Give an exact fraction.
Answer: 112/27
- x₁ = x₀ − f(x₀)/f′(x₀), with f′(x) = 3x².
- f(3) = 27 − 58 = −31 and f′(3) = 27.
- x₁ = 3 − (−31)/27 = 3 + 31/27 = 112/27 ≈ 4.148.
Bisection
worked example
Start with [2, 3] for f(x) = x³ − 16. Test the midpoint and keep the half where f changes sign. Do this twice. What is the midpoint of the interval you end with? Give the answer as a decimal.
Answer: 2.625
- 2.5³ = 15.625 < 16, so f(2.5) < 0: keep [2.5, 3].
- 2.75³ = 20.796875 > 16, so f(2.75) > 0: keep [2.5, 2.75].
- The midpoint of [2.5, 2.75] is 2.625.
Trapezoid rule
worked example
Use the trapezoid rule with 4 strips of width 1 to estimate ∫₂⁶ (x² − 2x) dx. Give the estimate as a decimal.
Answer: 38
- The points are x = 2, 3, 4, 5, 6, where f(x) = x² − 2x takes the values 0, 3, 8, 15, 24.
- (h/2)(f₀ + 2f₁ + 2f₂ + 2f₃ + f₄) = ½ × (0 + 2 × 3 + 2 × 8 + 2 × 15 + 24) = ½ × 76 = 38.
- The exact value is 112/3, so the estimate is 2/3 too high.
Simpson’s rule
worked example
Use Simpson’s rule with 2 strips of width 1 to estimate ∫₀² (x³ − 3x² + x − 4) dx.
Answer: -10
- The points are x = 0, 1, 2, where f(x) = x³ − 3x² + x − 4 takes the values −4, −5, −6.
- (h/3)(f₀ + 4f₁ + f₂) = ⅓ × (−4 + 4 × (−5) + (−6)) = ⅓ × (−30) = −10.
- Simpson’s rule is exact for polynomials up to degree 3, so −10 is also the exact value of the integral.