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

1. Continuous with respect to $t$
2. $\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 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} \, \vec{b}} . The cost is ${\frac {4}{3}}\,n^{3}$ to compute $A^{-1}$ plus 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-1)\,n} to multiply 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}} 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 \vec{b}}

Smarter Method

Perform gaussian elimination on 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} , keeping track of each elementary matrix operation: 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 E_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 E_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 E_3} , etc.

We will be left 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 E_k \, E_{k-1} \, \dots \, E_1 \, A = U} , 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 U} is an upper-triangular matrix. Solving once again 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 A} (i.e. finding 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( E_k \dots E_1 \right)^{-1} = L} gives a lower triangular matrix

This 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 A = L \, U} , the LU-decomposition 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 A} .

It costs 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{2}{3} \, n^3} operations to decompose an 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 n} matrix 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} .

We store 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 L\,U} inside 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 \begin{bmatrix} l_{11} & u_{12} & \dots & u_{1n} \\ l_{21} & l_{22} & & u_{2n} \\ \vdots & & \ddots & \vdots \\ l_{n1} & l_{n2} & \dots & l_{nn} \end{bmatrix}}

When 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 \vec{b}} comes along, we have 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 L \, U \, \vec{x} = \vec{b}} .

1. Solve 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 L \, \vec{y} = \vec{b}} 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 \vec{y}}
2. Solve 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 U \, \vec{x} = \vec{y}} 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 \vec{x}}

each takes approximately 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^2 - n} operations to solve, so our total cost is 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 2n^2-2n}