MATH 417 Chapter 4

« previous | Thursday, February 20, 2014 | next »

Section 4.3: Numerical Integration

Theorem. [Numerical Quadrature].

$\int _{a}^{b}f(x)\,\mathrm {d} x\quad =\quad \underbrace {\sum _{i=0}^{n}\alpha _{i}\,f(x_{i})} _{\mbox{approx.}}\quad +\quad \underbrace {{\frac {1}{(n+1)!}}\,\int _{a}^{b}f^{(n+1)}(\xi (x))\,\prod _{i=0}^{n}(x-x_{i})\,\mathrm {d} x} _{\mbox{error}}$

Where

• $x_{0},x_{1},\ldots ,x_{n}$ are points on the interval $[a,b]$
• $\alpha _{0},\alpha _{1},\ldots ,\alpha _{n}$ are constants defined by $\alpha _{i}=\int _{a}^{b}L_{i}(x)\,\mathrm {d} x$
• $\xi (x)$ is a value in $[a,b]$

Proof. Let $P_{n}(x)=\sum _{i=0}^{n}f(x_{i})\,L_{i}(x)$ be the Lagrange interpolating polynomial of $f(x)$. Since

${\begin{aligned}f(x)&=P_{n}(x)+{\frac {f^{(n+1)}(\xi (x))}{(n+1)!}}\,\prod _{i=0}^{n}(x-x_{i})\\\end{aligned}}$

is true for some $\xi (x)$ in $[a,b]$, it follows that

$\int _{a}^{b}f(x)\,\mathrm {d} x=\int _{a}^{b}P_{n}(x)\,\mathrm {d} x\ +\ \int _{a}^{b}{\frac {f^{(n+1)}(\xi (x))}{(n+1)!}}\,\prod _{i=0}^{n}(x-x_{i})\,\mathrm {d} x$

By substituting for the definition of $P_{n}(x)$, we obtain

${\begin{aligned}\int _{a}^{b}f(x)\,\mathrm {d} x&=\int _{a}^{b}\sum _{i=0}^{n}f(x_{i})\,L_{i}(x)\,\mathrm {d} x\ +\ \int _{a}^{b}{\frac {f^{(n+1)}(\xi (x))}{(n+1)!}}\,\prod _{i=0}^{n}(x-x_{i})\,\mathrm {d} x\\&=\sum _{i=0}^{n}f(x_{i})\,\int _{a}^{b}L_{i}(x)\,\mathrm {d} x\ +\ \int _{a}^{b}{\frac {f^{(n+1)}(\xi (x))}{(n+1)!}}\,\prod _{i=0}^{n}(x-x_{i})\,\mathrm {d} x\end{aligned}}$

If we let $a_{i}=\int _{a}^{b}L_{i}(x)\,\mathrm {d} x$, we arrive at the desired formula:

$\int _{a}^{b}f(x)\,\mathrm {d} x=\sum _{i=0}^{n}a_{i}\,f(x_{i})\ +\int _{a}^{b}{\frac {f^{(n+1)}(\xi (x))}{(n+1)!}}\,\prod _{i=0}^{n}(x-x_{i})\,\mathrm {d} x$

such that $\sum _{i=0}^{n}a_{i}\,f(x_{i})$ is our approximation and $\int _{a}^{b}\dots \,\mathrm {d} x$ is the error.

quod erat demonstrandum

Trapezoidal Rule

The simplest non-trivial case for the interpolating polynomial of $f(x)$ is a line between two sample points.

$P_{1}(x)={\frac {(x-x_{1})}{(x_{0}-x_{1})}}\,f(x_{0})+{\frac {(x-x_{0})}{(x_{1}-x_{0})}}\,f(x_{1})$

For simplicity, the notation $h=x_{k}-x_{k-1}$ shall be used to express the (uniform) distance between equidistant points

Theorem. [Trapezoidal Rule]. In the linear interpolating polynomial case, we let $a=x_{0}$ and $b=x_{1}$, so our formula is

$\int _{a}^{b}f(x)\,\mathrm {d} x\quad =\quad \underbrace {{\frac {h}{2}}\left(f(x_{0})+f(x_{1})\right)} _{\mbox{approx.}}\quad +\quad \underbrace {-{\frac {h^{3}}{12}}\,f''(\xi )} _{\mbox{error}}$

Proof. We can apply the quadrature formula above using our definitions for $P_{1}(x)$ and $h$. Observe that $f''(\xi (x))$ can be abstracted to a $f''(\xi )$ term by the mean value theorem for some value $\xi \in [a,b]$ because $(x-x_{0})\,(x-x_{1})$ does not change signs on $[x_{0},x_{1}]$.

${\begin{aligned}\int _{a}^{b}f(x)\,\mathrm {d} x&=\int _{x_{0}}^{x_{1}}{\frac {(x-x_{1})}{(x_{0}-x_{1})}}\,f(x_{0})+{\frac {(x-x_{0})}{(x_{1}-x_{0})}}\,f(x_{1})\,\mathrm {d} x\ +\ {\frac {1}{2}}\,\int _{x_{0}}^{x_{1}}f''(\xi (x))\,(x-x_{0})\,(x-x_{1})\,\mathrm {d} x\\&=\left.{\frac {(x-x_{1})^{2}}{2(x_{0}-x_{1})}}\,f(x_{0})+{\frac {(x-x_{0})^{2}}{2(x_{1}-x_{0})}}\,f(x_{1})\right|_{x_{0}}^{x_{1}}\ +\ f''(\xi )\,\int _{x_{0}}^{x_{1}}(x-x_{0})\,(x-x_{1})\,\mathrm {d} x\\&={\frac {(x1-x_{0})}{2}}\,\left(f(x_{0})+f(x_{1})\right)\ +\ f''(\xi )\left[{\frac {x^{3}}{3}}-{\frac {(x_{1}+x_{0})}{2}}\,x^{2}+x_{0}\,x_{1}\,x\right]_{x_{0}}^{x_{1}}\\&={\frac {h}{2}}\,\left(f(x_{0})+f(x_{1})\right)\ -\ {\frac {h^{3}}{12}}\,f''(\xi )\end{aligned}}$

quod erat demonstrandum

Simpson's Rule

If we use a quadratic interpolating polynomial instead of a linear one, we can derive Simpson's rule. The interpolating parabola defined by three points $f(x_{0})$, $f(x_{1})$, and $f(x_{2})$ is given by

$P_{2}(x)={\frac {(x-x_{1})\,(x-x_{2})}{(x_{0}-x_{1})\,(x_{0}-x_{2})}}\,f(x_{0})+{\frac {(x-x_{0})\,(x-x_{2})}{(x_{1}-x_{0})\,(x_{1}-x_{2})}}\,f(x_{1})+{\frac {(x-x_{0})\,(x-x_{1})}{(x_{2}-x_{0})\,(x_{2}-x_{1})}}\,f(x_{2})$

However, integrating this result using the quadrature method described above results in a $O(h^{4})$ error term. We can do better by using an alternative method involving the 3^rd-degree Taylor polynomial expansion of $f(x)$ centered at $x_{1}$:

${\begin{aligned}f(x)&=\sum _{k=0}^{3}{\frac {f^{(k)}(x_{1})}{k!}}\,(x-x_{1})^{k}\quad +\quad {\frac {f^{(4)}(\xi (x))}{4!}}\,(x-x_{1})^{4}\\&={\frac {f^{(0)}(x_{1})}{0!}}\,(x-x_{1})^{0}+{\frac {f^{(1)}(x_{1})}{1!}}\,(x-x_{1})^{1}+{\frac {f^{(2)}(x_{1})}{2!}}\,(x-x_{1})^{2}+{\frac {f^{(3)}(x_{1})}{3!}}\,(x-x_{1})^{3}+{\frac {f^{(4)}(\xi (x))}{4!}}\,(x-x_{1})^{4}\\&=\color {navy}{f(x_{1})+{\frac {f'(x_{1})}{1!}}\,(x-x_{1})+{\frac {f''(x_{1})}{2!}}\,(x-x_{1})^{2}+{\frac {f'''(x_{1})}{3!}}\,(x-x_{1})^{3}+{\frac {f^{(4)}(\xi (x))}{4!}}\,(x-x_{1})^{4}}\end{aligned}}$

Theorem. [Simpson's Rule]. In the quadratic interpolating polynomial case, let $a=x_{0}$ and $b=x_{2}$ with $x_{1}$ in between. If the points are equidistant at a distance $h$, then the following notation may be used. Otherwise, the integral must be calculated in terms of $x_{0}$, $x_{1}$, and $x_{2}$.

$\int _{a}^{b}f(x)\,\mathrm {d} x\quad =\quad \underbrace {{\frac {h}{3}}\left(f(x_{0})+4f(x_{1})+f(x_{2})\right)} _{\mbox{approx.}}\quad +\quad \underbrace {-{\frac {h^{5}}{90}}\,f^{(4)}(\xi )} _{\mbox{error}}$

Proof. Plugging in our definitions above yields

${\begin{aligned}\int _{x_{0}}^{x_{2}}\,\mathrm {d} x&=\int _{x_{0}}^{x_{2}}f(x_{1})+{\frac {f'(x_{1})}{1!}}\,(x-x_{1})+{\frac {f''(x_{1})}{2!}}\,(x-x_{1})^{2}+{\frac {f'''(x_{1})}{3!}}\,(x-x_{1})^{3}\,\mathrm {d} x\ +\ \int _{x_{0}}^{x_{2}}{\frac {f^{(4)}(\xi (x))}{4!}}\,(x-x_{1})^{4}\,\mathrm {d} x\\&=\left[f(x_{1})\,(x-x_{1})+{\frac {f'(x_{1})}{2}}\,(x-x_{1})^{2}+{\frac {f''(x_{1})}{6}}\,(x-x_{1})^{3}+{\frac {f'''(x_{1})}{4!}}\,(x-x_{1})^{4}\right]_{x_{0}}^{x_{2}}+{\frac {1}{24}}\,\int _{x_{0}}^{x_{2}}f^{(4)}(\xi (x))\,(x-x_{1})^{4}\,\mathrm {d} x\end{aligned}}$

Like in the proof for the trapezoidal rule, we can apply the mean value theorem to replace the $f^{(4)}(\xi (x))$ factor in the integrand with the constant $f^{(4)}(\xi _{1})$

${\begin{aligned}\int _{x_{0}}^{x_{2}}\,\mathrm {d} x&=\left[f(x_{1})\,(x-x_{1})+{\frac {f'(x_{1})}{2}}\,(x-x_{1})^{2}+{\frac {f''(x_{1})}{6}}\,(x-x_{1})^{3}+{\frac {f'''(x_{1})}{4!}}\,(x-x_{1})^{4}\right]_{x_{0}}^{x_{2}}+{\frac {f^{(4)}(\xi _{1})}{24}}\,\int _{x_{0}}^{x_{2}}(x-x_{1})^{4}\,\mathrm {d} x\\&=2h\,f(x_{1})+{\frac {h^{3}}{3}}\,f''(x_{1})+{\frac {f^{(4)}(\xi _{1})}{60}}\,h^{5}\end{aligned}}$

Replacing $f''(x_{1})$ with its approximation from Section 4.1 gives

${\begin{aligned}\int _{x_{0}}^{x_{2}}&=2h\,f(x_{1})+{\frac {h^{3}}{3}}\,\left\{{\frac {1}{h^{2}}}\,\left(f(x_{0})-2f(x_{1})+f(x_{2})\right)-{\frac {h^{2}}{12}}\,f^{(4)}(\xi _{2})\right\}+{\frac {f^{(4)}(\xi _{1})}{60}}\,h^{5}\\&={\frac {h}{3}}\left(f(x_{0})+4f(x_{1})+f(x_{2})\right)-{\frac {h^{5}}{12}}\left({\frac {1}{3}}\,f^{(4)}(\xi _{2})-{\frac {1}{5}}\,f^{(4)}(\xi _{1})\right)\end{aligned}}$

The values $\xi _{1}$ and $\xi _{2}$ can be replaced by a common value $\xi \in (x_{0},x_{2})$, giving the desired formula:

$\int _{a}^{b}f(x)\,\mathrm {d} x={\frac {h}{3}}\left(f(x_{0})+4f(x_{1})+f(x_{2})\right)\ -\ {\frac {h^{5}}{90}}\,f^{(4)}(\xi )$

quod erat demonstrandum

Degree of Accuracy

The degree of accuracy [in class, DAC], or precision, of a quadrature formula is the largest positive integer $n$ such that the formula is exact for $x^{k}$, for each $k=0,1,\ldots ,n$. Burden 197

I can't believe the book just gave this definition: it treats accuracy and precision as interchangeable terms. However, accuracy and precision are most certainly two distinct, separate topics.

The degree of accuracy may be found by finding the largest degree polynomial such that the error term is identically 0.

The error term of the trapezoidal rule has a second-derivative term, so polynomials of degree 1 are identically zero (e.g. ${\frac {\mathrm {d} }{\mathrm {d} x}}\left(x\right)=0$), but polynomials of degree 2 are constant (e.g. ${\frac {\mathrm {d} }{\mathrm {d} x}}\left(x^{2}\right)=2$). Hence the trapezoidal rule has degree of accuracy 1.

Similarly, the error term of Simpson's rule has a fourth-derivative term, so for polynomials of degree 3, ${\frac {\mathrm {d} ^{4}}{\mathrm {d} x^{4}}}\left(x^{3}\right)=0$, but ${\frac {\mathrm {d} ^{4}}{\mathrm {d} x^{4}}}\left(x^{4}\right)=24$. Therefore Simpson's rule has degree of accuracy 3.