\part{Numerical integration}
\chapter{Geometric methods}
\section{Riemann sum}
\[\int^{b}_{a}f(x)dx \approx \sum^{n}_{k=1} f(x_k)h\]
\[h= \frac{b-a}{n}\]
\[x_k = a+ nh\]
\section{Trapezoidal rule}
To reduce the error, one can consider the use of trapezoids along the mesh; hence the integral is estimated as a linear function over each partiton rather than as a constant function.
\[\int^{b}_{a}f(x)dx \approx \sum^{n-1}_{k=1} f(x_k)h\]
\[h= \frac{b-a}{n}\]
\[x_k = a+ nh\]
\[f_k = \frac{f(x_k)+f(x_{k+1})}{2}\]

\section{Refined trapezoidal rule}


One can remodel the trapezoidal rule as an algorithm where tolerance is specified rather than the mesh refinement. The crux of the idea is to double the refinement of the mesh until the absolute error from the previous iteration is within tolerance, however there are two standard methods for iterating the algorithm:

\begin{itemize}
\item Weighted sum of previous value and Riemann sum with 'doubly refined mesh'
\item Calculating trapezoidal rule for 'doubly refined mesh'
\end{itemize}


\[h_n= \frac{b-a}{2^{n}}\]
\[x_{n,k} = a+ kh_n\]
\[I_{0}=\frac{f(a)+f(b)}{2}(a-b)\]
\[I_{n+1}= \frac{I_n}{2} + \frac{h_{n+1}}{2} \sum_{i=1}^{2^{n+1}} f(x_{n+1,i})\]



\section{Romberg integration}
One can perform a series acceleration technique known as \emph{Richardson extrapolation} to derive higher order schemes for numerical integration. The use of this technique in numerical integration is formalized as \emph{Romberg integration}.

\section{Simpson's rule}

The theory of Romberg integration allows us to develop higher order schemes than the trapezoidal rule (0-order). \emph{Simpson's rule} is the 1-order algorithm in the Romberg integration scheme, and is otherwise observed by fitting quadratics to each partition rather than lines.

\chapter{Advanced methods}
\section{Gauss-Legendre integration}
An idea with strong link to functional analysis and the idea of orthogonal polynomials allows the realization of an extremely powerful method of numerical integration. We develop our theory within the Hilbert space $L^{2}([-1,1])$ (this just means we're going to consider integration problems on $[-1,1]$; one can do the change of variables later).

Consider a function $f$ that can be represented well by a polynomial interpolation $h$. Let $(P_n)_{n \in \mathbb{N}}$ be the Legendre polynomials. Recall that $\int^{1}_{-1}P_n (x)x^k dx = 0$

By Euclidean polynomial division, we may have $h(x)=q(x) P_n (x) +r(x)$, where

\[\int^{1}_{-1} f(x)dx \approx \int^{1}_{-1} h(x)dx \]
\[ = \int^{1}_{-1} q(x) P_n (x) +r(x)dx \]
\[ = \int^{1}_{-1} q(x) P_n (x) +r(x)dx \]
\[ = \int^{1}_{-1} r(x)dx \]

Since $r$ is a polynomial of degree less than $n$, it can be interpolated \emph{exactly} by some Lagrange interpolation.
\[ r(x) = \sum^{n}_{i=1} \ell_i (x)r(x_i) \]

\[ = \int^{1}_{-1} \sum^{n}_{i=1} \ell_i (x)r(x_i)dx \]
\[ =  \sum^{n}_{i=1} r(x_i) \int^{1}_{-1}\ell_i (x)dx \]


\[w_i = \int^{1}_{-1} \ell_i (x) dx \]

\[ =  \sum^{n}_{i=1} r(x_i) w_i dx \]

This is close, however we want to deal with the function $h$ instead of $r$; how can we pick the $x_i$ so that $r$ coincides with $h$? 
Returning to the equation $h(x_i)=q(x_i) P_n (x_i) +r(x_i)$, we can see that one way to do this is by letting $x_i$ be the zeroes of $P_n$!


\[ \int^{1}_{-1} f(x)dx \approx \sum^{n}_{i=1} f(x_i) w_i dx \]

With the change of variables, we get the following.
\[\int^{b}_{a} f(x)dx =  \approx \frac{b-a}{2} \sum^{n}_{i=0} w_i f(\frac{b-a}{2}u_i + \frac{a+b}{2})\]


\section{Monte Carlo integration}

This exotic method employs probability theory and the weak law of large numbers as the basis of its functionality. It's not particularly practical for analytic functions, however it may offer an advantage in higher dimensional integration and for highly pathological functions.
