Numerical integration: trapezoid, Simpson and Gauss

NUM · Chapter 311 min readAsked at Optiver, Citadel Securities, Akuna, Jump

Assumes Interpolation: splines, Runge and building a curve.

After this lesson you should be able to

  • Rank the standard quadrature rules by accuracy per evaluation.
  • Say when quadrature beats Monte Carlo and when it cannot.
  • Handle an integrand with a kink or an infinite range.

Option pricing is full of integrals: an expectation against a density, a variance swap against a strip of strikes, a characteristic-function inversion. In one or two dimensions quadrature is far more accurate than simulation for the same effort, and knowing which rule to use is mostly a matter of how smooth the integrand is.

RuleExact forErrorEvaluations
MidpointLinearO(h2)O(h^2)nn
TrapezoidLinearO(h2)O(h^2)n+1n+1
SimpsonCubicO(h4)O(h^4)n+1n+1, nn even
Gauss–Legendre, mm pointsDegree 2m−12m-1Spectral, for smooth integrandsmm
Table 3.1 · The rules. Simpson is exact for cubics despite being built from parabolas, which is a happy accident of the symmetric error cancelling — and it is why Simpson is the default when you want something better than trapezoid without thinking.

Why Gauss buys so much. The other rules fix the evaluation points at equal spacing and choose the weights. Gauss chooses *both*, which doubles the free parameters and therefore doubles the polynomial degree it can integrate exactly: mm points handle degree 2m−12m-1 rather than m−1m-1. For a smooth integrand the accuracy improves faster than any power of mm, so ten Gauss points can beat a thousand trapezoid ones. The catch is that the points are not where you would choose them, so if your integrand is only known at fixed places — market strikes, say — Gauss is unavailable.

Example 3.2

Integrating a smooth function, trapezoid with 100 points gives an error of 10−410^{-4}. What error would 1,000 points give, and what would Simpson give with 100?

Show the worked solutionHide the worked solution

Worked solution

  1. Formula
    trapezoid O(h2),Simpson O(h4)\text{trapezoid } O(h^2), \qquad \text{Simpson } O(h^4)
  2. Substitute
    h→h/10h \to h/10
  3. Solve
    trapezoid: 10−4×10−2=10−6\text{trapezoid: } 10^{-4} \times 10^{-2} = 10^{-6}
  4. Simpson at 100: ∼10−4×h2 better≈10−8\text{Simpson at } 100: \ \sim 10^{-4} \times h^2 \text{ better} \approx 10^{-8}
  5. Answer
    10−6 and roughly 10−810^{-6} \text{ and roughly } 10^{-8}

Sanity check. Simpson at a hundred points beats trapezoid at a thousand by two orders of magnitude, for a tenth of the function evaluations. When each evaluation is an expensive pricing call, the choice of rule is the whole performance story.

1326400.51Trapezoid, O(h²)Simpson, O(h⁴)IntervalsError
Figure 3.3 · What an extra order of accuracy is worth. Doubling the intervals divides the trapezoid error by four and Simpson’s by sixteen. The caveat is the one the next block is about: both orders assume a smooth integrand, and an option payoff has a kink at the strike that destroys them unless you split the integral there.

The rest of this lesson is in Premium

You have read the opening. 11 more sections follow, including 3 worked examples and 3 quick checks.

Start the free 7-day trialSign in

Nothing is charged for 7 days, and you can cancel before then. Or read Complexity: reading it off, and deriving it in full, free.