MATH 417 Lecture 26

« previous | Thursday, April 24, 2014 | next »

End Exam 2 content

Pre-Exam Discussion

• 6 problems total for possible score of over 100 (but 100 is perfect)
• 1-2 problems from first exam's sections

Chapter 5

Initial Value Problem (IVP): ${\frac {\mathrm {d} y}{\mathrm {d} t}}=f(t,y)$, and $y(a)=\alpha$ for $a\leq t\leq b$.

Is the IVP well-posed?

1. domain should be convex: $D=\left\{(t,y)~\mid ~a\leq t\leq b\quad y\in \Box \right\}$ — you should be able to draw straight line that never leaves the set between any two points $(t,y)$.
2. $f$ is continuous in $D$
3. $f$ is Lipschitz with respect to $y\in D$, i.e. $\left|f(t,x)-f(t,y)\right|\leq L\,\left|x-y\right|$.
   Theorem. $\left|{\frac {\partial f}{\partial y}}\right|\leq C\in D$, then $f$ is Lipschitz with Lipschitz constant $C$.

Numerical Methods

${\begin{aligned}y'(t)&=f(t,y)\\\int _{t_{i}}^{t_{i+1}}y'(t)\,\mathrm {d} t&=\int _{t_{i}}^{t_{i+1}}f(t,y)\,\mathrm {d} t\\y(t_{i+1})-y(t_{i})&=\int _{t_{i}}^{t_{i+1}}f(t,y)\,\mathrm {d} t\\y(t_{i+1})=y(t_{i})+\int _{t_{i}}^{t_{i+1}}f(t,y)\,\mathrm {d} t\end{aligned}}$

Over interval $\left[a,b\right]$ with $n$ sample points, we define $h:={\frac {b-a}{n}}$

Let $w_{i}=y(t_{i})$, where $t_{i}=a+i\,h$, with $w_{0}=y(a)=\alpha$

Rule is of form:

$w_{i+1}=w_{i}+{\mbox{numerical integration method}}$

Euler's Method

Approximate $\int _{t_{i}}^{t_{i+1}}f(t,y)\,\mathrm {d} t$ by left endpoint riemann rule: $\int _{t_{i}}^{t_{i+1}}f(t,y)\,\mathrm {d} t\approx h\,f(t_{i},y(t_{i}))$.

$w_{i+1}=w_{i}+h\,f(t_{i},w_{i})$

Modified Euler's Method

Approximate $\int _{t_{i}}^{t_{i+1}}f(t,y)\,\mathrm {d} t$ by trapezoidal rule: $\int _{t_{i}}^{t_{i+1}}f(t,y)\,\mathrm {d} t\approx {\frac {h}{2}}\,\left(f(t_{i},w_{i})+f(t_{i+1},w_{i}+h\,f(t_{i},w_{i}))\right)$.

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

Midpoint Method

Approximate $\int _{t_{i}}^{t_{i+1}}f(t,y)\,\mathrm {d} t$ by midpoint rule: $\int _{t_{i}}^{t_{i+1}}f(t,y)\,\mathrm {d} t\approx h\,f(t_{i}+{\frac {h}{2}},w_{i}+{\frac {h}{2}}\,f(t_{i},w_{i}))$.

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

Heun's Method

Too complicated for exam.

Example

$y'(t)=\sin {2y}+4\pi \,t$, and $y(0)=0$

This is well-posed:

• domain of RHS is entire real plane
• $\left|{\frac {\partial f}{\partial y}}\right|=\left|2\cos {2y}\right|\leq 2$

$h={\frac {1}{2}}$

Let's use Modified Euler...

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

Chapter 6

(skip linear algebra review)

$A={\begin{bmatrix}5&0&1\\4&1&7\\5&0&2\end{bmatrix}}$

We wish to find $L$ and $U$ such that $A=L\,U$:

Standard Gaussian elimination sets the pivot elements equal to 1, and this requires a little extra modification to find $L$. If we stick with just elementay operation #3 (adding a multiple of one row to another), then computation of $L$ is easy:

Elementary matrix 3 is given by $E_{ij}=I\left[i,j=a\right]$: this will add $a$ times row $j$ to row $i$. The $i,j$-th entry of the identity matrix is $a$. Computing the inverse is incredibly straightforward:

$E_{ij}^{-1}=I\left[i,j=-a\right]$

$L={\begin{bmatrix}1&0&0\\{\frac {4}{5}}&1&0\\\Box &\Box &1\end{bmatrix}}$

$L={\begin{bmatrix}1&0&0\\{\frac {4}{5}}&1&0\\1&\Box &1\end{bmatrix}}$

$L={\begin{bmatrix}1&0&0\\{\frac {4}{5}}&1&0\\1&0&1\end{bmatrix}}$

Positive Definite Matrices

Theorem. A matrix $A$ is positive definite if and only if the determinants of all the minors of $A$ are positive:

$A={\begin{bmatrix}4&a&5\\a&1&0\\5&0&7\end{bmatrix}}$

Hence

• $\left|4\right|=4>0$
• ${\begin{vmatrix}4&a\\a&1\end{vmatrix}}=4-a^{2}>0$
• $\left|A\right|=3-7a^{2}>0$

From these constraints, we get $a\in \left(-{\sqrt {\frac {3}{7}}},{\sqrt {\frac {3}{7}}}\right)$

Cholesky [sp?] Factorization

Given symmetric matrix $A$, find $L$ such that $A=L\,L^{T}$.

To get this, perform LU decomposition, but replace diagonal pivot elements of $L$ with ${\sqrt {\ell _{ii}}}$ (and multiply the corresponding column by ${\frac {1}{\sqrt {\ell _{ii}}}}$).

Let $A={\begin{bmatrix}4&0&5\\0&1&0\\5&0&7\end{bmatrix}}={\begin{bmatrix}4&0&0\\0&1&0\\5&0&{\frac {3}{4}}\end{bmatrix}}\,{\begin{bmatrix}1&0&{\frac {5}{4}}\\0&1&0\\0&0&1\end{bmatrix}}$

Then $L^{T}={\begin{bmatrix}{\sqrt {4}}&0&{\frac {5}{\sqrt {4}}}\\0&{\sqrt {1}}&0\\0&0&{\sqrt {7-5\cdot {\frac {5}{\sqrt {4}}}}}\end{bmatrix}}={\begin{bmatrix}2&0&{\frac {5}{2}}\\0&1&0\\0&0&{\frac {\sqrt {3}}{2}}\end{bmatrix}}$

This is often called the square root of a matrix, since the closest we can get to an abstract "square" of any matrix (of any size) is $A\,A^{T}$.

Matrix Norms

All norms discussed here are called "native"

Defined as $\left\|A\right\|_{p}=\max _{\left\|{\vec {x}}\right\|_{p}=1}\left\|A\,{\vec {x}}\right\|_{p}$, but this is a pain to compute. We settle for the following theorems:

1. $\left\|A\right\|_{\infty }={\mbox{max row sum}}=\max _{i}\sum _{j=1}^{n}\left|a_{ij}\right|$
2. $\left\|A\right\|_{1}=\left\|A^{T}\right\|_{\infty }={\mbox{max column sum}}=\max _{j}\sum _{i=1}^{n}\left|a_{ij}\right|$
3. $\left\|A\right\|_{2}={\sqrt {\rho (A^{T}\,A)}}$, where $\rho (A)=\max _{i}\left|\lambda _{i}\right|$ is the largest magnitude eigenvalue.

Theorem. $\left\|{\vec {x}}\right\|_{A}={\sqrt {{\vec {x}}^{T}\,A\,x}}$ is a norm if $A$ is positive definite.

Proof. By definition, $\left\|\cdot \right\|$ is a norm if and only if it satisfies the following:

1. $\left\|x\right\|\geq 0$, and $\left\|x\right\|=0$ if and only if $x=0$.
2. $\left\|\alpha \,x\right\|=\left|\alpha \right|\,\left\|x\right\|$ for all constants $\alpha$
3. $\left\|x+y\right\|\leq \left\|x\right\|+\left\|y\right\|$, which holds iif and only if the Cauchy-Schwartz inequality ($\left\langle x,y\right\rangle \leq {\sqrt {\left\langle x,x\right\rangle }}\cdot {\sqrt {\left\langle y,y\right\rangle }}$).

Since $A$ is symmetric, we can find $L$ such that $A=L\,L^{T}$. thus

$\left\|{\vec {x}}\right\|_{A}={\sqrt {{\vec {x}}^{T}\,A\,{\vec {x}}}}={\sqrt {{\vec {x}}^{T}\,L\,L^{T}\,{\vec {x}}}}={\sqrt {\left(L^{T}\,{\vec {x}}\right)^{T}\,\left(L^{T}\,{\vec {x}}\right)}}={\sqrt {\left\|L^{T}\,x\right\|_{2}^{2}}}=\left\|L^{T}\,x\right\|_{2}$

We know this norm is always greater than $0$ and equal to zero only when ${\vec {x}}={\vec {0}}$.

Next, $\left\|\alpha \,{\vec {x}}\right\|_{A}={\sqrt {\alpha ^{2}\,{\vec {x}}^{T}\,A\,{\vec {x}}}}=\left|\alpha \right|\,\left\|{\vec {x}}\right\|_{A}$

Finally, $\left\langle x,y_{A}\right\rangle =x^{T}\,A\,y\leq {\sqrt {{\vec {x}}^{T}\,A\,{\vec {x}}}}\,{\sqrt {{\vec {y}}^{T}\,A{\vec {y}}}}=\left\|L^{T}\,{\vec {x}}\right\|\,\left\|L^{T}\,{\vec {y}}\right\|\leq \left\|{\vec {x}}\right\|_{A}\cdot \left\|{\vec {y}}\right\|_{A}$

quod erat demonstrandum

Example

Find $\ell _{2}$ norm of $A={\begin{bmatrix}4&0&5\\0&1&0\\5&0&7\end{bmatrix}}$

Eigenvalues are found by

${\begin{vmatrix}4-\lambda &0&5\\0&1-\lambda &0\\5&0&7-\lambda \end{vmatrix}}=(1-\lambda )\,(\lambda ^{2}-11\lambda +3)=0$

So $\lambda \in \left\{1,{\frac {11\pm {\sqrt {109}}}{2}}\right\}$, and $\max _{i}\left|\lambda _{i}\right|={\frac {11+{\sqrt {109}}}{2}}$

Chapter 8

Given $f(x)$, approximate $p(x)=a_{1}\,\phi _{1}(x)+a_{2}\,\phi _{2}(x)+\dots +a_{n}\,\phi _{n}(x)$.

To do this, we find the best least squares fit (i.e. minimize Euclidean distance) $\left\|f-p\right\|_{2}^{2}=\min _{q\in \Pi }\left\|f-q\right\|_{2}^{2}$, where $\Pi =\mathrm {Span} \left\{\phi _{1},\phi _{2},\ldots ,\phi _{n}\right\}$.

Normal equations given by

${\begin{bmatrix}\left\langle \phi _{1},\phi _{1}\right\rangle &\left\langle \phi _{1},\phi _{2}\right\rangle &\dots &\left\langle \phi _{1},\phi _{n}\right\rangle \\\left\langle \phi _{2},\phi _{1}\right\rangle &\left\langle \phi _{2},\phi _{2}\right\rangle &\dots &\left\langle \phi _{2},\phi _{n}\right\rangle \\\vdots &\vdots &\ddots &\vdots \\\left\langle \phi _{n},\phi _{1}\right\rangle &\left\langle \phi _{n},\phi _{2}\right\rangle &\dots &\left\langle \phi _{n},\phi _{n}\right\rangle \end{bmatrix}}\,{\begin{bmatrix}a_{1}\\a_{2}\\\vdots \\a_{n}\end{bmatrix}}={\begin{bmatrix}\left\langle f,\phi _{1}\right\rangle \\\left\langle f,\phi _{2}\right\rangle \\\vdots \\\left\langle f,\phi _{n}\right\rangle \end{bmatrix}}$

• Given continuous functions, the inner product is given by $\left\langle f,g\right\rangle =\int _{a}^{b}f(x)\,g(x)\,w(x)\,\mathrm {d} x$
• Given point samples, the inner product is given by $\left\langle f,g\right\rangle =\sum _{i}f_{i}\,g_{i}\,w_{i}$