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 $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)

$\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)

$\int _{0}^{1}1\,\mathrm {d} x=1={\frac {1}{2}}+c_{1}$ , so $c_{1}={\frac {1}{2}}$
$\int _{0}^{1}x\,\mathrm {d} x={\frac {1}{2}}={\frac {1}{2}}\,x_{0}+{\frac {1}{2}}\,x_{1}$
$\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 $x_{0},x_{1}={\frac {1}{2}}\pm {\frac {\sqrt {3}}{6}}$ .

Degree of accuracy is $2\cdot 2-1=3$ .

Note: Every Gaussian rule is symmetric

(9th ed. #13)

$\int _{0}^{2}f(x)\,\mathrm {d} x\approx 4$ by trapezoid and $\approx 2$ by simpson's rule. Find $f(1)$ .

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