MATH 417 Lecture 19

« previous | Tuesday, April 1, 2014 | next »

Exam Discussion

Perfect score is 102

Problem 1

$x=g(x)=(x+1)^{\frac {1}{3}}$

$p_{0}={\frac {3}{2}}$ and set $p_{n+1}=g(p_{n})=(p_{n}+1)^{\frac {1}{3}}$

If $1\leq x\leq 2$ , then show $1\leq x\leq 2$ . In this case $1<{\sqrt[{3}]{2}}=g(1)\leq g(x)\leq g(2)={\sqrt[{3}]{3}}<2$
$\left|g'(x)\right|={\frac {1}{3}}\,{\frac {1}{(x+1)^{\frac {2}{3}}}}\leq {\frac {1}{3\cdot 4^{\frac {1}{3}}}}=k<1$

Solve $\left|p_{n}-p\right|\leq k^{n}\,\max {\left(p_{0}-a,b-p_{0}\right)}<{\frac {1}{100}}$ for $n$ : $n=3$

Problem 2

Interpolate polynomial using LaGrange method given all 4^th-order divided differences (i.e. $f\left[\cdot ,\cdot ,\cdot ,\cdot ,\cdot \right]$ are 10

 x  p(x)

-2   2
         -1
 0   0       1/3
          0       5/3
 1   0        7        10
         14        ?
 2  14        ?
          ?
 ?   ?

Hence $p(x)=2-(x+2)+{\frac {1}{3}}\,(x+2)\,x+{\frac {5}{3}}\,(x+2)\,x\,(x-1)+10\,(x+2)\,x\,(x-1)\,(x-2)$

$x^{3}\,\left({\frac {5}{3}}+10(-1)\right)\to -{\frac {25}{3}}$

Problem 3

Find Hermite polynomial

x  p(x)

0   2
         0
0   2        -1/4
       -1/2          5/4
2   1         9/4
         4
2   1

$H_{3}(x)=2+0\cdot x-{\frac {1}{4}}\,x^{2}+{\frac {5}{4}}\,x^{2}\,(x-2)$

Problem 4

Taylor Series expansion given $x_{0}-h$ , $x_{0}$ , and $x_{0}+3h$ .

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

Thus

$12h\,f'(x_{0})=f(x_{0}+3h)+8f(x_{0})-O(h^{3})$

and

$f'(x_{0})={\frac {-9f(x_{0}-h)+8f(x_{0})+f(x_{0}+3h)}{12h}}+O(h^{2})$

Problem 4

$\int _{0}^{3}f(x)\,\mathrm {d} x=c_{0}\,f(0)+c_{1}\,f(x_{1})$

$c_{0}={\frac {3}{4}}$ , $c_{1}={\frac {9}{4}}$ , and $x_{1}=2$

Problem 5

$\int _{2013}^{2014}f(x)\,\mathrm {d} x\approx c_{0}\,f(x_{0})+c_{1}\,f(x_{1})$

On $[-1,1]$ , we have $c_{0}=c_{1}=1$ and $x_{0}=-x_{1}=-{\frac {\sqrt {3}}{3}}$ .

Scale to new range $[0,1]$ : $c_{0}=c_{1}={\frac {1}{2}}$ , $x_{0}={\frac {1}{2}}-{\frac {\sqrt {3}}{3}}\cdot {\frac {1}{2}}$ , and $x_{1}={\frac {1}{2}}+{\frac {\sqrt {3}}{3}}\cdot {\frac {1}{2}}$

Now shift to range $\left[2013,2014\right]$ : $c_{0}=c_{1}={\frac {1}{2}}$ , $x_{0}={\frac {1}{2}}-{\frac {\sqrt {3}}{3}}\cdot {\frac {1}{2}}+2013$ , and $x_{1}={\frac {1}{2}}+{\frac {\sqrt {3}}{3}}\cdot {\frac {1}{2}}+2013$

this has $\mathrm {DAC} =2n-1=3$

Quiz Discussion

${\begin{cases}y'=f(t,y)=y+t+\cos {(\pi \,y)}\\y(0)=0\end{cases}}$

for $0\leq t\leq 1$

Part A: Show Well-Posedness

Continuous with respect to $t$
$\left|{\frac {\partial f}{\partial x}}\right|=\left|1-\pi \,\sin {(\pi \,y)}\right|\leq \pi +1<5$

Part B: List methods

Euler's method: $w_{0}=0$ , $w_{i+1}=w_{i}+h\,f(t_{i},w_{i})$

Modified Euler's method: $w_{0}=0$ , $w_{i+1}=w_{i}+{\frac {h}{2}}\,\left(f(t_{i},w_{i})+f(t_{i+1},w_{i}+h\,f(t_{i},w_{i})\right)$

Part C: Euler Approximation

$w_{0}=0$
$w_{1}={\frac {1}{2}}\,f(0,0)={\frac {1}{2}}$
$w_{2}={\frac {1}{2}}+{\frac {1}{2}}\,f\left({\frac {1}{2}},{\frac {1}{2}}\right)=1$

Numerical Linear Algebra

Practical problem: solve $A\,{\vec {x}}={\vec {b}}$ many times given ${\vec {b}}_{1}$ , ${\vec {b}}_{2}$ , etc.

Naïve method

Compute $A^{-1}$ .

When ${\vec {b}}$ comes along, compute $A^{-1}\,{\vec {b}}$ . The cost is ${\frac {4}{3}}\,n^{3}$ to compute $A^{-1}$ plus $(2n-1)\,n$ to multiply $A^{-1}$ by ${\vec {b}}$

Smarter Method

Perform gaussian elimination on $A$ , keeping track of each elementary matrix operation: $E_{1}$ , $E_{2}$ , $E_{3}$ , etc.

We will be left with $E_{k}\,E_{k-1}\,\dots \,E_{1}\,A=U$ , where $U$ is an upper-triangular matrix. Solving once again for $A$ (i.e. finding $\left(E_{k}\dots E_{1}\right)^{-1}=L$ gives a lower triangular matrix