MATH 417 Lecture 19

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

Exam Discussion

Perfect score is 102

Problem 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 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. Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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$, 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} , 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 x_0 + 3h} .

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{align} 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{align}}

Thus

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

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}^{3} f(x) \,\mathrm{d}x = c_0 \, f(0) + c_1 \, f(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 c_0 = \frac{3}{4}} , 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{9}{4}} , and $x_{1}=2$

Problem 5

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_{2013}^{2014} f(x) \,\mathrm{d}x \approx c_0 \, f(x_0) + c_1 \, f(x_1)}

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 [-1, 1]} , 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 c_0 = c_1 = 1} 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 x_0 = -x_1 = -\frac{\sqrt{3}}{3}} .

Scale to new range 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 [0,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 c_0 = 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 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 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[ 2013,2014 \right]} : 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_0 = 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 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

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} 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 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 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: 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 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$
• Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle w_{1}={\frac {1}{2}}\,f(0,0)={\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 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 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}_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 \vec{b}_2} , etc.

Naïve method

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

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, 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 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{4}{3} \, n^3} to 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}} 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 $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 ${\vec {b}}$ comes along, we have $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}