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'(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'(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'(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'(x_{0}-h)+0+\left({\frac {16}{3!}}\,f'''(\xi _{1})-{\frac {64}{3!}}\,f'''(\xi _{2})\right)\,h^{3}$

Now we solve for $f'(x_{0}-h)$:

${\begin{aligned}{\frac {-15f(x_{0}-h)+16f(x_{0})-f(x_{0}+3h)}{12h}}&=f'(x_{0}-h)+{\frac {h^{3}\,\left({\frac {16}{3!}}\,f'''(\xi )-{\frac {64}{3!}}\,f'''(\xi _{2})\right)}{12h}}\\&=f'(x_{0}-h)+{\frac {h^{2}\,\left({\frac {8}{3}}\,f'''(\xi )-{\frac {32}{3}}\,f'''(\xi _{2})\right)}{12}}\end{aligned}}$

Section 4.3: Numerical Integration

Given an interval $0\leq x\leq 1$, we want to find $\int _{0}^{1}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{aligned}\int _{0}^{1}1\,\mathrm {d} x&=A_{0}+A_{1}\\\int _{0}^{1}(x-1)\,\mathrm {d} x&=A_{0}\,(x_{0}-1)+{\cancel {A_{1}\cdot 0}}\\\int _{0}^{1}(x-1)^{2}\,\mathrm {d} x&=A_{0}\,(x_{0}-1)^{2}+{\cancel {A_{1}\cdot 0^{2}}}\end{aligned}}$

Hence we get the system

${\begin{aligned}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{aligned}}$

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:

$\int _{0}^{1}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 $\int _{0}^{1}\left(x-{\frac {1}{3}}\right)^{2}\,\left(1-x\right)\,\mathrm {d} x$ is "approximated" to be 0, but is actually positive.

Shifted and Scaled Interval

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

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

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

$\int _{10}^{14}g(y)\,\mathrm {d} y\approx {\frac {4}{1}}\,\left({\frac {3}{4}}\,f\left(10+{\frac {4}{3}}\right)+{\frac {1}{4}}\,f(14)\right)=3f\left(11+{\frac {1}{3}}\right)+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):

$\int _{10}^{14}g(y)\,\mathrm {d} y\approx f(10)+3f\left(14-{\frac {4}{3}}\right)$

Composite Simpson's Rule

As done by Stirling (ca. 1730)

Simpson's rule:

$\int _{a}^{b}f(x)\,\mathrm {d} x-{\frac {b-a}{2}}\,\left(f(a)+f\left(a+{\frac {b-a}{2}}\right)+f(b)\right)$

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\geq 0$ (without loss of generality) on an interval $x\in \left[a,b\right]$. Then

$\int _{a}^{b}g(x)\,h(x)\,\mathrm {d} x=h(\xi )\,\int _{a}^{b}g(x)\,\mathrm {d} x$

If $g(x)=1$,

${\begin{aligned}\int _{a}^{b}h(x)\,\mathrm {d} x&=(b-a)\,h(\xi )\\h(\xi )&={\frac {1}{b-a}}\,\int _{a}^{b}h(x)\,\mathrm {d} x\end{aligned}}$

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\left[a,{\frac {a+b}{2}}\right]\,(x-a)+f\left[a,{\frac {a+b}{2}},b\right]\,(x-a)\,\left(x-{\frac {a+b}{2}}\right)+f\left[a,{\frac {a+b}{2}},b,{\frac {a+b}{2}}\right](x-a)\,\left(x-{\frac {a+b}{2}}\right)\,(x-b)$

The first 3 terms are the Lagrange interpolating polynomial $p_{2}(x)$, and the third is "more" ... something to do with $f'$.

Now $\int _{a}^{b}f(x)\,\mathrm {d} x=\int _{a}^{b}p_{3}(x)\,\mathrm {d} x=\int _{a}^{b}f(a)+f\left[a,{\frac {a+b}{2}}\right](x-a)+f\left[a,{\frac {a+b}{2}},b\right](x-a)\,\left(x-{\frac {a+b}{2}}\right)\,\mathrm {d} x+\int _{a}^{b}f\left[a,{\frac {a+b}{2}},b,{\frac {a+b}{2}}\right]\,(x-a)\,\left(x-{\frac {a+b}{2}}\right)\,(x-b)$

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

$\int _{a}^{b}f(x)\,\mathrm {d} x=\int _{a}^{b}p_{2}(x)\,\mathrm {d} x$

Computing the Error

$f(x)-p_{3}(x)={\frac {f^{(4)}(\xi (x))}{4!}}\,(x-a)\,\left(x-{\frac {a+b}{2}}\right)\,(x-b)\,\left(x-{\frac {a+b}{2}}\right)$

So

$\int _{a}^{b}f(x)\,\mathrm {d} x-\int _{a}^{b}p_{3}(x)=-{\frac {1}{24}}\,\int _{a}^{b}f^{(4)}(\xi (x))\,(x-a)\,(x-b)\,\left(x-{\frac {a+b}{2}}\right)^{2}$

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

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

$\int _{a}^{b}g(x)\,\mathrm {d} x=\int _{a}^{b}(x-a)\,(x-b)\,\left(x-{\frac {a+b}{2}}\right)\,\mathrm {d} x$

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

$\int _{-h}^{h}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 $\left[a,b\right]$. In other words, we take $n$ sub-intervals of $\left[a,b\right]$ that have equal length.

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

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

Simplifying the expression above gives

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

The error of this composite is given by

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

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