MATH 417 Lecture 11

« previous | Tuesday, February 18, 2014 | next »

Section 4.1: Numerical Differentiation

Given some points $x_0-h$, $x_0$, and $x_0+3h$, approximate $f^{\prime }(x_0-h)$ using the values $f(x_0-h)$, $f(x_0)$, and $f(x_0+3h)$ within $O(h^2)$ accuracy.

Taylor Method:

$f(x_0)=f(x_0-h+h)=f(x_0-h)+h{f}^{\prime }(x_0-h)+\frac{h^2}{2}{f}^{″}(x_0-h)+\frac{h^3}{3!}{f}^{‴}({\xi }_1)$

$f(x_0+3h)=f(x_0-h+4h)=f(x_0-h)+4h{f}^{\prime }(x_0-h)+\frac{16h^2}{2}{f}^{″}(x_0-h)+\frac{64h^3}{3!}{f}^{‴}({\xi }_2)$

To cancel the $f^{″}$ term, we need to multiply the first equation by 16 and subtract the equations. Doing so yields

$16f(x_0)-f(x_0+3h)=15f(x_0-h)+(16h-4h)f^{\prime }(x_0-h)+0+(\frac{16}{3!}{f}^{‴}({\xi }_1)-\frac{64}{3!}{f}^{‴}({\xi }_2))h^3$

Now we solve for $f^{\prime }(x_0-h)$:

$\begin{array}{rl}\frac{-15f(x_0-h)+16f(x_0)-f(x_0+3h)}{12h}& =f^{\prime }(x_0-h)+\frac{h^3(\frac{16}{3!}{f}^{‴}(\xi )-\frac{64}{3!}{f}^{‴}({\xi }_2))}{12h}\\ & =f^{\prime }(x_0-h)+\frac{h^2(\frac{8}{3}{f}^{‴}(\xi )-\frac{32}{3}{f}^{‴}({\xi }_2))}{12}\end{array}$

Section 4.3: Numerical Integration

Given an interval $0\le x\le 1$, we want to find $\underset{0}{\overset{1}{\int }}f(x)\mathrm{d}x\approx A_{0}f(x_0)+A_{1}f(1)$.

To do this, we must find a rule with the least degree of accuracy (DAC) such that the approximation is equivalent for polynomials of degree $n$.

$\begin{array}{rl}\underset{0}{\overset{1}{\int }}1\mathrm{d}x& =A_0+A_1\\ \underset{0}{\overset{1}{\int }}(x-1)\mathrm{d}x& =A_0(x_0-1)+\cancel{A_1\cdot 0}\\ \underset{0}{\overset{1}{\int }}(x-1{)}^2\mathrm{d}x& =A_0(x_0-1{)}^2+\cancel{A_1\cdot 0^2}\end{array}$

Hence we get the system

$\begin{array}{rl}{A}_0+A_1& =1\\ (x_0-1)A_0& =-\frac{1}{2}\\ (x_0-1)A_0(x_0-1)& =\frac{1}{3}\end{array}$

The solution: $A_0=\frac{3}{4}$, $A_1=\frac{1}{4}$, and $x_0=\frac{1}{3}$

Hence the approximation is equal for polynomials of degree 2:

$\underset{0}{\overset{1}{\int }}f(x)\mathrm{d}x=\frac{3}{4}f\left(\frac{1}{3}\right)+\frac{1}{4}f(1)$.

This approximation does not work for polynomials of degree 3 because $\underset{0}{\overset{1}{\int }}{(x-\frac{1}{3})}^2(1-x)\mathrm{d}x$ is "approximated" to be 0, but is actually positive.

Shifted and Scaled Interval

Using the previous approximation, we want to approximate $\underset{10}{\overset{14}{\int }}g(x)\mathrm{d}x$. The interval maps correspondingly:

$\begin{array}{rl}0& \to 10\\ 1& \to 14\\ \frac{1}{3}& \to \frac{1}{3}\cdot 4+10\end{array}$

We keep the same coefficients, but multiply by the ratio of the new interval length to the old:

$\underset{10}{\overset{14}{\int }}g(y)\mathrm{d}y\approx \frac{4}{1}(\frac{3}{4}f(10+\frac{4}{3})+\frac{1}{4}f(14))=3f(11+\frac{1}{3})+f(14)$

We keep the same degree of accuracy (i.e. 2) because shifting and scaling is just a linear change of variables.

We can find an alternate rule if we keep the other endpoint (i.e. 10):

$\underset{10}{\overset{14}{\int }}g(y)\mathrm{d}y\approx f(10)+3f(14-\frac{4}{3})$

Composite Simpson's Rule

As done by Stirling (ca. 1730)

Simpson's rule:

$\underset{a}{\overset{b}{\int }}f(x)\mathrm{d}x-\frac{b-a}{2}(f(a)+f(a+\frac{b-a}{2})+f(b))$

This rule is exact for polynomials of of up to degree 3, hence DAG = 3

We are going to need the following theorem:

Theorem. [Intermediate Value Theorem]. let $g$ and $h$ be continuous functions with $g\ge 0$ (without loss of generality) on an interval $x\in [a,b]$. Then

$\underset{a}{\overset{b}{\int }}g(x)h(x)\mathrm{d}x=h(\xi )\underset{a}{\overset{b}{\int }}g(x)\mathrm{d}x$

If $g(x)=1$,

$\begin{array}{rl}\underset{a}{\overset{b}{\int }}h(x)\mathrm{d}x& =(b-a)h(\xi )\\ h(\xi )& =\frac{1}{b-a}\underset{a}{\overset{b}{\int }}h(x)\mathrm{d}x\end{array}$

Proof. (omitted)

quod erat demonstrandum

Given $f(x)$, we interpolate at $a$, $\frac{a+b}{2}$, $b$, and $\frac{a+b}{2}$ (Find $p_3(x)$).

$p_3(x)=f(a)+f[a,\frac{a+b}{2}](x-a)+f[a,\frac{a+b}{2},b](x-a)(x-\frac{a+b}{2})+f[a,\frac{a+b}{2},b,\frac{a+b}{2}](x-a)(x-\frac{a+b}{2})(x-b)$

The first 3 terms are the Lagrange interpolating polynomial $p_2(x)$, and the third is "more" ... something to do with $f^{\prime }$.

Now $\underset{a}{\overset{b}{\int }}f(x)\mathrm{d}x=\underset{a}{\overset{b}{\int }}{p}_3(x)\mathrm{d}x=\underset{a}{\overset{b}{\int }}f(a)+f[a,\frac{a+b}{2}](x-a)+f[a,\frac{a+b}{2},b](x-a)(x-\frac{a+b}{2})\mathrm{d}x+\underset{a}{\overset{b}{\int }}f[a,\frac{a+b}{2},b,\frac{a+b}{2}](x-a)(x-\frac{a+b}{2})(x-b)$

Now $\underset{a}{\overset{b}{\int }}(x-a)(x-\frac{a+b}{2})(x-b)\mathrm{d}x=0$, so we're left with the integral of the interpolating polynomial $p_2(x)$:

$\underset{a}{\overset{b}{\int }}f(x)\mathrm{d}x=\underset{a}{\overset{b}{\int }}{p}_2(x)\mathrm{d}x$

Computing the Error

$f(x)-p_3(x)=\frac{f^{(4)}(\xi (x))}{4!}(x-a)(x-\frac{a+b}{2})(x-b)(x-\frac{a+b}{2})$

So

$\underset{a}{\overset{b}{\int }}f(x)\mathrm{d}x-\underset{a}{\overset{b}{\int }}{p}_3(x)=-\frac{1}{24}\underset{a}{\overset{b}{\int }}{f}^{(4)}(\xi (x))(x-a)(x-b){(x-\frac{a+b}{2})}^2$

Let $h(x)=f^{(4)}(\xi (x))$, and $g(x)=(x-a)(x-b)(x-\frac{a+b}{2})$

Then $\underset{a}{\overset{b}{\int }}h(x)g(x)\mathrm{d}x=h(\zeta )\underset{a}{\overset{b}{\int }}g(x)\mathrm{d}x$ by the intermediate value theorem.

$\underset{a}{\overset{b}{\int }}g(x)\mathrm{d}x=\underset{a}{\overset{b}{\int }}(x-a)(x-b)(x-\frac{a+b}{2})\mathrm{d}x$

Let $y=x-\frac{a+b}{2}$ and $h=\frac{b-a}{2}$, then

$\underset{-h}{\overset{h}{\int }}{y}^2(y+h)(y-h)\mathrm{d}y=\frac{4h^5}{15}$

Therefore, the error is $-\frac{f^{(4)}(\xi (\zeta ))}{24}\frac{4h^5}{15}=-\frac{f^{(4)}({\xi }_1)}{90}{h}^5$

Composite Rule

Suppose we apply Simpson's rule $n$ times (hence we need $2n$ points) over a large interval $[a,b]$. In other words, we take $n$ sub-intervals of $[a,b]$ that have equal length.

$\underset{a}{\overset{b}{\int }}f(x)\mathrm{d}x=\sum _{k=0}^{n-1}\underset{x_{2k}}{\overset{x_{2k+2}}{\int }}f(x)\mathrm{d}x\approx \sum _{k=0}^{n-1}h(f(x_{2k})+4f(x_{2k+1})+f(x_{2k+2}))$

Where $h=\frac{b-a}{2h}$.

Simplifying the expression above gives

$\underset{a}{\overset{b}{\int }}f(x)\mathrm{d}x=\frac{b-a}{2n}(f(a)+f(b)+4\sum _{k=0}^{n-1}f(x_{2k+1})+\sum _{k=1}^{n-1}f(x_{2k}))$

The error of this composite is given by

$\sum _{k=1}^n(-\frac{f^{(4)}({\xi }_k)}{90}{\left(\frac{b-a}{2n}\right)}^5)=-\frac{h^4(b-a)}{180}\cdot \underset{f^{(4)}(\zeta )}{\underbrace{\frac{1}{n}\sum _{k=1}^n{f}^{(4)}({\xi }_k)}}$

Hence $error\in O(h^4)$