Trapezoidal rule

When the grid spacing is non-uniform, one can use the formula

$${\displaystyle \int _{a}^{b}f(x)\,dx\approx \sum _{k=1}^{N}{\frac {f(x_{k-1})+f(x_{k})}{2}}\Delta x_{k},}$$

wherein ${\displaystyle \Delta x_{k}=x_{k}-x_{k-1}.}$

For a domain discretized into ${\displaystyle N}$ equally spaced panels, considerable simplification may occur. Let

$${\displaystyle \Delta x_{k}=\Delta x={\frac {b-a}{N}}}$$

the approximation to the integral becomes

$${\displaystyle {\begin{aligned}\int _{a}^{b}f(x)\,dx&\approx {\frac {\Delta x}{2}}\sum _{k=1}^{N}\left(f(x_{k-1})+f(x_{k})\right)\\[1ex]&={\frac {\Delta x}{2}}{\Biggl (}f(x_{0})+2f(x_{1})+2f(x_{2})+2f(x_{3})+\dotsb +2f(x_{N-1})+f(x_{N}){\Biggr )}\\[1ex]&=\Delta x\left({\frac {f(x_{N})+f(x_{0})}{2}}+\sum _{k=1}^{N-1}f(x_{k})\right).\end{aligned}}}$$

First suppose that ${\displaystyle h={\frac {b-a}{N}}}$ and ${\displaystyle a_{k}=a+(k-1)h}$. Let

$${\displaystyle g_{k}(t)={\frac {1}{2}}t[f(a_{k})+f(a_{k}+t)]-\int _{a_{k}}^{a_{k}+t}f(x)\,dx}$$

be the function such that ${\displaystyle |g_{k}(h)|}$ is the error of the trapezoidal rule on one of the intervals, ${\displaystyle [a_{k},a_{k}+h]}$. Then

$${\displaystyle {dg_{k} \over dt}={1 \over 2}[f(a_{k})+f(a_{k}+t)]+{1 \over 2}t\cdot f'(a_{k}+t)-f(a_{k}+t),}$$

and

$${\displaystyle {d^{2}g_{k} \over dt^{2}}={1 \over 2}t\cdot f''(a_{k}+t).}$$

Now suppose that ${\displaystyle \left|f''(x)\right|\leq \left|f''(\xi )\right|,}$ which holds if ${\displaystyle f}$ is sufficiently smooth. It then follows that

$${\displaystyle \left|f''(a_{k}+t)\right|\leq f''(\xi )}$$

which is equivalent to ${\displaystyle -f''(\xi )\leq f''(a_{k}+t)\leq f''(\xi )}$, or ${\displaystyle -{\frac {f''(\xi )t}{2}}\leq g_{k}''(t)\leq {\frac {f''(\xi )t}{2}}.}$

Since ${\displaystyle g_{k}'(0)=0}$ and ${\displaystyle g_{k}(0)=0}$,

$${\displaystyle \int _{0}^{t}g_{k}''(x)dx=g_{k}'(t)}$$

and

$${\displaystyle \int _{0}^{t}g_{k}'(x)dx=g_{k}(t).}$$

Using these results, we find

$${\displaystyle -{\frac {f''(\xi )t^{2}}{4}}\leq g_{k}'(t)\leq {\frac {f''(\xi )t^{2}}{4}}}$$

and

$${\displaystyle -{\frac {f''(\xi )t^{3}}{12}}\leq g_{k}(t)\leq {\frac {f''(\xi )t^{3}}{12}}}$$

Letting ${\displaystyle t=h}$ we find

$${\displaystyle -{\frac {f''(\xi )h^{3}}{12}}\leq g_{k}(h)\leq {\frac {f''(\xi )h^{3}}{12}}.}$$

Summing all of the local error terms we find

$${\displaystyle \sum _{k=1}^{N}g_{k}(h)={\frac {b-a}{N}}\left[{f(a)+f(b) \over 2}+\sum _{k=1}^{N-1}f\left(a+k{\frac {b-a}{N}}\right)\right]-\int _{a}^{b}f(x)dx.}$$

But we also have

$${\displaystyle -\sum _{k=1}^{N}{\frac {f''(\xi )h^{3}}{12}}\leq \sum _{k=1}^{N}g_{k}(h)\leq \sum _{k=1}^{N}{\frac {f''(\xi )h^{3}}{12}}}$$

and

$${\displaystyle \sum _{k=1}^{N}{\frac {f''(\xi )h^{3}}{12}}={\frac {f''(\xi )h^{3}N}{12}},}$$

so that

$${\displaystyle -{\frac {f''(\xi )h^{3}N}{12}}\leq {\frac {b-a}{N}}\left[{f(a)+f(b) \over 2}+\sum _{k=1}^{N-1}f\left(a+k{\frac {b-a}{N}}\right)\right]-\int _{a}^{b}f(x)dx\leq {\frac {f''(\xi )h^{3}N}{12}}.}$$

Therefore the total error is bounded by

$${\displaystyle {\text{error}}=\int _{a}^{b}f(x)\,dx-{\frac {b-a}{N}}\left[{f(a)+f(b) \over 2}+\sum _{k=1}^{N-1}f\left(a+k{\frac {b-a}{N}}\right)\right]={\frac {f''(\xi )h^{3}N}{12}}={\frac {f''(\xi )(b-a)^{3}}{12N^{2}}}.}$$

The trapezoidal rule converges rapidly for periodic functions. This is an easy consequence of the Euler-Maclaurin summation formula, which says that if ${\displaystyle f}$ is ${\displaystyle p}$ times continuously differentiable with period ${\displaystyle T}$

$${\displaystyle \sum _{k=0}^{N-1}f(kh)h=\int _{0}^{T}f(x)\,dx+\sum _{k=1}^{\lfloor p/2\rfloor }{\frac {B_{2k}}{(2k)!}}(f^{(2k-1)}(T)-f^{(2k-1)}(0))-(-1)^{p}h^{p}\int _{0}^{T}{\tilde {B}}_{p}(x/T)f^{(p)}(x)\,dx}$$

where ${\displaystyle h:=T/N}$ and ${\displaystyle {\tilde {B}}_{p}}$ is the periodic extension of the ${\displaystyle p}$th Bernoulli polynomial.[8] Due to the periodicity, the derivatives at the endpoint cancel and we see that the error is ${\displaystyle O(h^{p})}$.

A similar effect is available for peak-like functions, such as Gaussian, Exponentially modified Gaussian and other functions with derivatives at integration limits that can be neglected.[9] The evaluation of the full integral of a Gaussian function by trapezoidal rule with 1% accuracy can be made using just 4 points.[10] Simpson's rule requires 1.8 times more points to achieve the same accuracy.[10][11]

Although some effort has been made to extend the Euler-Maclaurin summation formula to higher dimensions,[12] the most straightforward proof of the rapid convergence of the trapezoidal rule in higher dimensions is to reduce the problem to that of convergence of Fourier series. This line of reasoning shows that if ${\displaystyle f}$ is periodic on a ${\displaystyle n}$-dimensional space with ${\displaystyle p}$ continuous derivatives, the speed of convergence is ${\displaystyle O(h^{p/d})}$. For very large dimension, the shows that Monte-Carlo integration is most likely a better choice, but for 2 and 3 dimensions, equispaced sampling is efficient. This is exploited in computational solid state physics where equispaced sampling over primitive cells in the reciprocal lattice is known as Monkhorst-Pack integration.[13]

For functions that are not in C², the error bound given above is not applicable. Still, error bounds for such rough functions can be derived, which typically show a slower convergence with the number of function evaluations ${\displaystyle N}$ than the ${\displaystyle O(N^{-2})}$ behaviour given above. Interestingly, in this case the trapezoidal rule often has sharper bounds than Simpson's rule for the same number of function evaluations.[14]