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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{(4)}(\xi(x))} factor in the integrand with the constant Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{(4)}(\xi_1)}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}

Replacing Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f''(x_1)} with its approximation from Section 4.1 gives

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}

The values Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \xi_1} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \xi_2} can be replaced by a common value Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \xi \in (x_0, x_2)} , giving the desired formula:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} such that the formula is exact for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^k} , for each Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{\mathrm{d}}{\mathrm{d}x} \left( x \right) = 0} ), but polynomials of degree 2 are constant (e.g. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{\mathrm{d}^4}{\mathrm{d}x^4} \left( x^3 \right) = 0} , but Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{\mathrm{d}^4}{\mathrm{d}x^4} \left( x^4 \right) = 24} . Therefore Simpson's rule has degree of accuracy 3.