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

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

Solve $|p_n-p|\le k^n\max (p_0-a,b-p_0)<\frac{1}{100}$ for $n$: $n=3$

Problem 2

Interpolate polynomial using LaGrange method given all 4^th-order divided differences (i.e. $f[\cdot ,\cdot ,\cdot ,\cdot ,\cdot ]$ 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(\frac{5}{3}+10(-1))\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{array}{rl}f(x_0-h)& =f(x_0)-h{f}^{\prime }(x_0)+\frac{h^2}{2}{f}^{″}(x_0)+O(h^3)\\ f(x_0+3h)& =f(x_0)+3h{f}^{\prime }(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}^{\prime }(x_0)+O(h^3)\end{array}$

Thus

$12h{f}^{\prime }(x_0)=f(x_0+3h)+8f(x_0)-O(h^3)$

and

$f^{\prime }(x_0)=\frac{-9f(x_0-h)+8f(x_0)+f(x_0+3h)}{12h}+O(h^2)$

Problem 4

$\underset{0}{\overset{3}{\int }}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

$\underset{2013}{\overset{2014}{\int }}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 $[2013,2014]$: $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{D}\mathrm{A}\mathrm{C}=2n-1=3$

Quiz Discussion

$\{\begin{array}{l}{y}^{\prime }=f(t,y)=y+t+\cos (\pi y)\\ y(0)=0\end{array}$

for $0\le t\le 1$

Part A: Show Well-Posedness

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

Part B: List methods

Euler's method: $w_0=0$, $w_{i+1}=w_i+hf(t_i,w_i)$

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

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(\frac{1}{2},\frac{1}{2})=1$

Numerical Linear Algebra

Practical problem: solve $A\overrightarrow{x}=\overrightarrow{b}$ many times given ${\overrightarrow{b}}_1$, ${\overrightarrow{b}}_2$, etc.

Naïve method

Compute $A^{-1}$.

When $\overrightarrow{b}$ comes along, compute $A^{-1}\overrightarrow{b}$. The cost is $\frac{4}{3}{n}^3$ to compute $A^{-1}$ plus $(2n-1)n$ to multiply $A^{-1}$ by $\overrightarrow{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 ${(E_k\dots E_1)}^{-1}=L$ gives a lower triangular matrix

This gives $A=LU$, the LU-decomposition of $A$.

It costs $\frac{2}{3}{n}^3$ operations to decompose an $n\times n$ matrix $A$.

We store $LU$ inside $A$:

$\left[\begin{array}{cccc}{l}_{11}& u_{12}& \dots & u_{1n}\\ l_{21}& l_{22}& & u_{2n}\\ ⋮& & \ddots & ⋮\\ l_{n1}& l_{n2}& \dots & l_{nn}\end{array}\right]$

When $\overrightarrow{b}$ comes along, we have $LU\overrightarrow{x}=\overrightarrow{b}$.

1. Solve $L\overrightarrow{y}=\overrightarrow{b}$ for $\overrightarrow{y}$
2. Solve $U\overrightarrow{x}=\overrightarrow{y}$ for $\overrightarrow{x}$

each takes approximately $n^2-n$ operations to solve, so our total cost is now $2n^2-2n$