Basic idea:

  • Sample the function at many points
  • integral is approximated as weighted sum

Integration in 1D

Related: fundamental theorem of calculus trapezoidal rule: error O(h^2)

Integration in 2D

Apply the trapezoidal rule twice. The error is still the same.

Curse of Dimensionality

see curse of dimensionality How much does it cost to apply trapezoidal rule as we go up in dimension?

  • 1D:
  • 2D:
  • kD:

For many problems, is very big (think about how many parameters a function can have)

An important way to avoid the curse of dimensionality is to use Monte Carlo integration