====== Quadrature ======

Quadrature is the numerical approximation of definite integrals of functions evaluated at discrete gridpoints. 

There are many, many quadrature formulae. We will start with the Trapezoid Rule and Simpson's Rule.

In both cases we will assume we have an evenly spaced set of $N+1$ gridpoints $\{x_i, i=0,\ldots,N\}$ on the interval $[a,b]$, with $x_0 = a$, $x_n = b$, and $x_i = x_0 + i h$, where $h = (b-a)/N$ is the gridspacing. We also assume we know the value of the function evaluated at the gridpoints, i.e. we have a vector of values $\{y_i = f(x_i), i=0,\ldots,N\}$.



==== Trapezoid Rule====

The Trapezoid rule approximates the definite integral of $f(x)$ over $[a,b]$ using piecewise linear 
interpolation between each pair of datapoints.
\begin{equation*}
\int_a^b f(x) \, dx = h \left( \frac{1}{2} y_0 + \sum_{i=1}^{N-1} y_i + \frac{1}{2} y_N\right) - \frac{b-a}{12} h^2 f''(c)
\end{equation*}
for some $c$ where $a<c<b$. 

For $N=5$ we would have
\begin{equation*}
\int_a^b f(x) \, dx = h \left( \frac{1}{2} y_0 + y_1 + y_2 + y_3 + y_4  + \frac{1}{2} y_5\right) + O(h^2)
\end{equation*}
Here we have collapsed the error term into $O(h^2)$.

==== Simpson's Rule====

Simpson's Rule pproximates the definite integral of $f(x)$ over $[a,b]$ using piecewise quadratic 
interpolation between triplets of  datapoints.
\begin{equation*}
\int_a^b f(x) \, dx = \frac{h}{3} \left( y_0 + 4 \sum_{i=1, i \text{odd}}^{N-1} y_i + 2\sum_{i=2, i \text{even}}^{N-2} y_i + y_N\right) - \frac{b-a}{180} \, h^4 \, f^{(iv)}(c)
\end{equation*}
for some $c$ where $a<c<b$, and where $f^{(iv)}$ is the fourth derivative of $f$. Simpson's rule requires that $N$ is even, so that the total number of gridpoints, $N+1$, is odd.

For example, for $N=6$ and $N+1=7$ gridpoints, we have 

\begin{equation*}
\int_a^b f(x) \, dx = \frac{h}{3} \left(y_0 + 4y_1 + 2y_2 + 4y_3 + 2y_4  + 4y_5 + y_6 \right) + O(h^4)
\end{equation*}


=== Further reading ===

  * [[https://en.wikipedia.org/wiki/Trapezoidal_rule|Trapezoidal rule]] (wikipedia)
  * [[http://mathworld.wolfram.com/TrapezoidalRule.html|Trapezoidal rule]] (math world)  
  * [[https://en.wikipedia.org/wiki/Simpson%27s_rule|Simpson's rule]] (wikipedia)
  * [[http://mathworld.wolfram.com/SimpsonsRule.html|Simpson's rule]] (math world)
  * [[https://en.wikipedia.org/wiki/Newton%E2%80%93Cotes_formulas|Newton-Cotes formulae]] (wikipedia)
  * [[http://mathworld.wolfram.com/Newton-CotesFormulas.html|Newton-Cotes formulae]] (math world)
  * [[http://mathworld.wolfram.com/TrapezoidalRule.html|Trapezoidal rule]] (math world)