Numerical integration can also be done on a curve fitted to some data, and such integration is more generally useful, given the difficulty of finding many integrals.
Two simple algorithms, for integral of f(x) for x from a to b - \( \int_a^b f(x) \, dx \)
- Trapezoidal -- (b - a) * (f(a) + f(b))/2 -- \( (b-a) (f(a)+f(b))/2 \)
- Midpoint -- (b - a) * f((a+b)/2) -- \( (b-a) f((a+b)/2) \)
One can break a domain of integration into smaller segments and do either algorithm on each one. One can also use some fancier algorithm for each step, like Newton-Cotes integration (several equally-spaced points) or Gaussian integration (several variably-spaced points).
One can repeat this integration with more and more points, and reuse the previous calculations, checking on whether the result tends to converge.
One can have the help of interpolation, and the most general sort of polynomial interpolation is Lagrange interpolation:
y = sum over i of yi * product over j != i of (x - xi)/(xj - xi) -- \( \displaystyle{ y = \sum_i y_i \prod_{j \ne i} \frac{x - x_i}{x_j - x_i} } \)
But there is a way to calculate this interpolation efficiently. Create a pyramid of values starting with points 1, 2, ..., n. Create each new layer from sets of neighboring values in the previous ones: 1-2, 2-3, 3-4, ... (n-1)-n, 1-2-3, 2-3-4, ..., (n-2)-(n-1)-n, ...