Numerical Methods and Computation
Numerical methods on this paper tests whether you can choose an algorithm, predict its error order, and recognise when floating-point arithmetic or a bad pivot will break it.
Error
- Truncation error comes from the method; round-off comes from finite precision. Reducing h lowers truncation error by a power of h but can increase round-off.
- Absolute error is |x̃ − x|; relative error divides that by |x|.
Root finding
- Bisection is guaranteed when f is continuous and the endpoint signs differ; error after n steps is at most (b − a)/2ⁿ, so convergence is linear.
- Newton–Raphson: x_{n+1} = x_n − f(x_n)/f'(x_n); quadratic near a simple root, but it fails when f' ≈ 0 or the iterate jumps away.
- Secant replaces f' with a finite difference and needs two starting values.
Interpolation and quadrature
- Lagrange interpolation through n + 1 points has degree ≤ n and is unique; the error involves the (n + 1)th derivative.
- Trapezoid rule global error is O(h²); Simpson's rule requires an even number of subintervals, is O(h⁴) and is exact for cubics.
- Simpson: (h/3)[f₀ + 4f₁ + 2f₂ + … + 4f_{n−1} + f_n].
Linear systems
- Gaussian elimination with partial pivoting selects the largest available pivot in the column to control growth.
- Jacobi and Gauss–Seidel are iterative; Gauss–Seidel usually converges faster, and both need diagonal dominance or a suitable spectral radius.
Worked example
Approximate ∫₀¹ x² dx with the trapezoid rule, n = 2, h = 0.5. Nodes 0, 0.5, 1 with values 0, 0.25, 1. T = (h/2)[f₀ + 2f₁ + f₂] = 0.25[0 + 0.5 + 1] = 0.375. Exact value 1/3 ≈ 0.3333, so the error is about 0.0417. Simpson with the same nodes gives (0.5/3)[0 + 4(0.25) + 1] = 0.1667 × 2 = 0.3333 - exact, because the integrand is quadratic.
Traps that cost marks
- Applying Simpson's rule with an odd number of subintervals.
- Skipping partial pivoting and dividing by a near-zero pivot.
- Reporting more significant figures than the error justifies.
- Confusing the order of the global error with the order of the local error.
- Running Newton's method when f'(x₀) = 0.