MATH 417 Lecture 11
« previous | Tuesday, February 18, 2014 | next »
Section 4.1: Numerical Differentiation
Given some points 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_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 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 x_0 + 3h} , approximate using the values , , 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)}
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) = 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 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''} term, we need to multiply the first equation by 16 and subtract the equations. Doing so yields
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 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 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 \begin{align} \frac{-15 f(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{align}}
Section 4.3: Numerical Integration
Given an 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 0 \le x \le 1} , we want to find 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_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 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} .
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_{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{align}}
Hence we get the system
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} 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{align}}
The solution: 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 A_0 = \frac{3}{4}} , 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 A_1 = \frac{1}{4}} , 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 x_0 = \frac{1}{3}}
Hence the approximation is equal for polynomials of degree 2:
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_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 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_{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 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_{10}^{14} g(x) \,\mathrm{d}x} . The interval maps correspondingly:
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} 0 &\to 10 \\ 1 &\to 14 \\ \frac{1}{3} &\to \frac{1}{3} \cdot 4 + 10 \end{align}}
We keep the same coefficients, but multiply by the ratio of the new interval length to the old:
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_{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) = 3 f \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):
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_{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:
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}{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 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} 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} be continuous functions with 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 \ge 0} (without loss of generality) on an 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 x \in \left[ a,b \right]} . Then
If 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) = 1} ,
Proof. (omitted)
Given 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)}
, we interpolate at 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 a}
, 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{a+b}{2}}
, 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 b}
, 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 \frac{a+b}{2}}
(Find 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 p_3(x)}
).
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 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 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 p_2(x)} , and the third is "more" ... something to do with 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'} .
Now 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) \,\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 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} (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 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 p_2(x)} :
Computing the Error
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) - 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)}