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 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_0-h)} , 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_0)} , 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 f(x_0 + 3h)} within 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 O(h^2)} accuracy.

Taylor Method:

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_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

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 - \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 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 h(x) = f^{(4)}(\xi(x))} , 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 g(x) = (x-a) \, (x-b) \, \left( x - \frac{a+b}{2} \right)}

Then 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} h(x) \, g(x) \,\mathrm{d}x = h(\zeta) \, \int_{a}^{b} g(x) \,\mathrm{d}x} by the intermediate value theorem.

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} g(x) \,\mathrm{d}x = \int_{a}^{b} (x-a) \, (x-b) \, \left( x-\frac{a+b}{2} \right) \,\mathrm{d}x}

Let 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 y = x - \frac{a+b}{2}} 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 h = \frac{b-a}{2}} , then

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_{-h}^{h} y^2 \, (y+h) \, (y-h) \,\mathrm{d}y = \frac{4h^5}{15}}

Therefore, the error is 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{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 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} times (hence we need 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 2n} points) over a large interval 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 \left[ a,b \right]} . In other words, we take 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} sub-intervals of 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 \left[ a,b \right]} that have equal length.

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 = \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 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 h = \frac{b-a}{2h}} .

Simplifying the expression above 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 \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

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 \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 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 error \in O(h^4)}