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,
An important way to avoid the curse of dimensionality is to use Monte Carlo integration