MATH 417 Lecture 14

« previous | Thursday, February 27, 2014 | next »

End Exam 1 content

Exam Review

Section 2.1: Bisection

(#10) $f(x)=(x+2)\,(x+1)^{2}\,x\,(x-1)^{3}\,(x-2)$

Find root in $[-1.5,2.5]=\left[-{\frac {3}{2}},{\frac {5}{2}}\right]$ using bisection:

f(-1.5) < 0
f(2.5) > 0
f(0.5) > 0
f(-0.5) < 0
f(0) = 0 ← stop

Section 2.2: Fixed Point

$f(x)=x^{3}-x-1=0$ for $x\in [1,2]$

Find $x=g(x)$ and take $p_{0}\in [a,b]$ and recursively find $p_{n+1}=g(p_{n})$ for $n=0,1,2,\ldots$

for any $x\in [a,b]$ , we need $g(x)\in [a,b]$
$(\max _{x\in [a,b]}\left|g'(x)\right|=k)<1$

$\left|p_{n}-p\right|\leq k^{n}\,\max {(b-p_{0},p_{0}-a)}$

$\left|p_{n}-p\right|\leq {\frac {k^{n}}{1-k}}\,\left|p_{1}-p_{0}\right|$

In our case, we take $x={\sqrt[{3}]{x+1}}$ :

$1<g(1)\leq g(2)=3^{\frac {1}{3}}<2$
$\left|g'(x)\right|={\frac {1}{3}}\,{\frac {1}{(x+1)^{\frac {2}{3}}}}\leq {\frac {1}{3\cdot 2^{\frac {2}{3}}}}=k$

Find the number of iterations needed to get accuracy $10^{-3}$ :

$\left|p_{n}-p\right|\leq \left({\frac {1}{3\cdot 4^{\frac {1}{3}}}}\right)^{n}\,\max(p_{0}-1,2-p_{0})$

Choose $p_{0}={\frac {3}{2}}$ , now

${\begin{aligned}\left(3\cdot 4^{\frac {1}{3}}\right)^{-n}\cdot {\frac {1}{2}}&\leq 10^{-3}\\\left(3\cdot 4^{\frac {1}{3}}\right)^{-n}&\leq 2\cdot 10^{-3}\\-n\,\ln {\left(3\cdot 4^{\frac {1}{3}}\right)}&\leq \ln {2}-3\ln {10}\\n&\geq {\frac {3\ln {10}-\ln {2}}{\ln {3}+{\frac {1}{3}}\,\ln {4}}}={\frac {9\ln {10}-3\ln {2}}{3\ln {3}+\ln {4}}}\approx 3.981909816\\\end{aligned}}$

Therefore take $n=4$

Newton's Method

$x=g(x)$ , $g(x)=x-{\frac {f(x)}{f'(x)}}$

If $f$ is concave-up, choose right endpoint: Newton's method works best when $f''>0$ and $f'>0$

In our example above, $p_{n+1}=p_{n}-{\frac {p_{n}^{3}-p_{n}-1}{3p_{n}^{2}-1}}$

Chapter 3: Interpolation

Given $x_{0},x_{1},\ldots x_{n}$ , interpolate $f(x)$ as a polynomial $p_{n}(x)$

Lagrange

f(x)=\sum _{i=1}^{n}f(x_{i})\,\prod _{j=0;j\neq i}^{n}{\frac {(x-x_{j})}{(x_{i}-x_{j})}}+\underbrace {{\frac {f^{(n+1)}(\xi )}{(n+1)!}}\,(x-x_{0})\,(x-x_{1})\dots (x-x_{n})} _{\mbox{error}}

Newton

f(x)=f(x_{0})+f[x_{0},x_{1}](x-x_{0})+\dots +f[x_{0},x_{1},\ldots ,x_{n}](x-x_{0})\dots (x-x_{n})+\underbrace {{\frac {f^{(n+1)}(\xi )}{(n+1)!}}\,(x-x_{0})\,(x-x_{1})\dots (x-x_{n})} _{\mbox{error}}

Example: (9th ed: 124 #7): Find polynomial that interpolates at 0, 1, 2, 3 at the point $x={\frac {5}{2}}$ (that is, find $p_{0,1,2,3}\left({\frac {5}{2}}\right)$ ) given:

$p_{0,1}(x)=2x+1$ (the line through $f(0)$ and $f(1)$ )
$p_{0,2}(x)=x+1$ (the line through $f(0)$ and $f(2)$ )
$p_{1,2,3}\left({\frac {5}{2}}\right)=3$ (the parabola through $f(1)$ , $f(2)$ , and $f(3)$ has value $3$ at $x={\frac {5}{2}}$

We know the lines through f(0)

x   f(x)
--------
0    1
        2
1    3       -1
        0             (a-1)/6
2    3       (a-3)/2
        a-3
3    a

Now $p_{1,2,3}(x)=3+0(x-1)+{\frac {a-3}{2}}\,(x-1)\,(x-2)$ , hence $p_{1,2,3}\left({\frac {5}{2}}\right)=3=3+{\frac {a-3}{2}}\,\left({\frac {3}{2}}\right)\,\left({\frac {1}{2}}\right)$ and $a=3$ .

Therefore, our interpolating polynomial $p_{0,1,2,3}$ is

p_{0,1,2,3}(x)=3+{\frac {1}{3}}\,\left(x-3\right)\,\left(x-2\right)\,\left(x-1\right)

and evaluated at $x={\frac {5}{2}}$ , we get $p_{0,1,2,3}\left({\frac {5}{2}}\right)={\frac {23}{8}}$

Hermite

A tomato is launched at a height of 10 ft with an initial speed of 10 ft/s. The tomato hits a person standing 50 ft away and has a final speed of -20 ft/s

 x   f(x)  f'(x)

 0    10
            10
 0    10          -51/250
            -1/5           -12/3125
 50   0           -99/250
            -20
 50   0

$H_{3}(x)=10+10x-{\frac {51}{250}}\,x^{2}-{\frac {12}{3125}}\,x^{2}\,(x-50)$

Whoa! The trajectory of an object is parabolic (disregarding friction or air resistance), and given only two points with derivatives (positions and velocities), we can reconstruct the entire trajectory exactly. The same can be done with three points, since three points uniquely defines a parabola.

Section 4.1: Differentiation

(9th ed. #22) Approximate $f'(x_{0})$ using $f(x_{0}-h)$ , $f(x_{0})$ , $f(x_{0}+h)$ , $f(x_{0}+2h)$ to accuracy $O(h^{3})$

Taylor series around $f(x_{0})$ :

${\begin{aligned}f(x_{0}-h)&=f(x_{0})-h\,f'(x_{0})+{\frac {h^{2}}{2}}\,f''(x_{0})-{\frac {h^{3}}{6}}\,f'''(x_{0})+O(h^{4})\\f(x_{0}+h)&=f(x_{0})+h\,f'(x_{0})+{\frac {h^{2}}{2}}\,f''(x_{0})+{\frac {h^{3}}{6}}\,f'''(x_{0})+O(h^{4})\\f(x_{0}+2h)&=f(x_{0})+2h\,f'(x_{0})+{\frac {(2h)^{2}}{2}}\,f''(x_{0})+{\frac {(2h)^{3}}{6}}\,f'''(x_{0})+O(h^{4})\end{aligned}}$

Multiply equations by $A$ , $B$ , and $C$ , respectively and solve for:

$A\,f(x_{0}-h)+B\,f(x_{0}+h)+C\,f(x_{0}+2h)=(A+B+C)\,f(x_{0})+h(-A+B+2C)\,f'(x_{0})$ .

We get the following system of equations

${\begin{cases}-A+B+2C&=1\\A+B+4C&=0\\-A+B+8C&=0\end{cases}}\quad \implies \quad \left\langle A,B,C\right\rangle =\left\langle -{\frac {1}{3}},1,-{\frac {1}{6}}\right\rangle$

Alternatively, we can 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_0)} via the interpolating polynomial above, but that usually involves more work.

Sections 4.3 and 4.7: Integration

(9th ed. #20)

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 \frac{1}{2} \, f(x_0) + c_1 \, f(x_1)}

Find the rule with best DAC (which will be the Gaussian rule since scaling factor is 1/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} 1 \,\mathrm{d}x = 1 = \frac{1}{2} + c_1} , 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 c_1 = \frac{1}{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} x \,\mathrm{d}x = \frac{1}{2} = \frac{1}{2} \, x_0 + \frac{1}{2} \, x_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 \int_{0}^{1} x^2 \,\mathrm{d}x = \frac{1}{3} = \frac{1}{2} \, x_0^2 + \frac{1}{2} \, x_1^2}

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 x_0, x_1 = \frac{1}{2} \pm \frac{\sqrt{3}}{6}} .

Degree of accuracy 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 2 \cdot 2 - 1 = 3} .

Note: Every Gaussian rule is symmetric

(9th ed. #13)

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}^{2} f(x) \, \mathrm{d}x \approx 4} by trapezoid 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 \approx 2} by simpson's rule. 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 f(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{cases} \frac{2}{2} \, \left( f(0) + f(2) \right) &= 4 \\ \frac{2}{6} \, \left( f(0) + 4f(1) + f(2) \right) &= 2 \end{cases} \quad \implies \quad 4 + 4f(1) = 6 \quad \implies \quad f(1) = \frac{1}{2}}