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\le t\le b$.

Is the IVP well-posed?

1. domain should be convex: $D=\{(t,y)\mid a\le t\le by\in ◻\}$ — 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. $|f(t,x)-f(t,y)|\le L|x-y|$.
   Theorem. $\left|\frac{\partial f}{\partial y}\right|\le C\in D$, then $f$ is Lipschitz with Lipschitz constant $C$.

Numerical Methods

$\begin{array}{rl}{y}^{\prime }(t)& =f(t,y)\\ \underset{t_i}{\overset{t_{i+1}}{\int }}{y}^{\prime }(t)\mathrm{d}t& =\underset{t_i}{\overset{t_{i+1}}{\int }}f(t,y)\mathrm{d}t\\ y(t_{i+1})-y(t_i)& =\underset{t_i}{\overset{t_{i+1}}{\int }}f(t,y)\mathrm{d}t\\ y(t_{i+1})=y(t_i)+\underset{t_i}{\overset{t_{i+1}}{\int }}f(t,y)\mathrm{d}t\end{array}$

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

Let $w_i=y(t_i)$, where $t_i=a+ih$, with $w_0=y(a)=\alpha$

Rule is of form:

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

Euler's Method

Approximate $\underset{t_i}{\overset{t_{i+1}}{\int }}f(t,y)\mathrm{d}t$ by left endpoint riemann rule: $\underset{t_i}{\overset{t_{i+1}}{\int }}f(t,y)\mathrm{d}t\approx hf(t_i,y(t_i))$.

$w_{i+1}=w_i+hf(t_i,w_i)$

Modified Euler's Method

Approximate $\underset{t_i}{\overset{t_{i+1}}{\int }}f(t,y)\mathrm{d}t$ by trapezoidal rule: $\underset{t_i}{\overset{t_{i+1}}{\int }}f(t,y)\mathrm{d}t\approx \frac{h}{2}(f(t_i,w_i)+f(t_{i+1},w_i+hf(t_i,w_i)))$.

$w_{i+1}=w_i+\frac{h}{2}(f(t_i,w_i)+f(t_{i+1},w_i+hf(t_i,w_i)))$

Midpoint Method

Approximate $\underset{t_i}{\overset{t_{i+1}}{\int }}f(t,y)\mathrm{d}t$ by midpoint rule: $\underset{t_i}{\overset{t_{i+1}}{\int }}f(t,y)\mathrm{d}t\approx hf(t_i+\frac{h}{2},w_i+\frac{h}{2}f(t_i,w_i))$.

$w_{i+1}=w_i+hf(t_i+\frac{h}{2},w_i+\frac{h}{2}f(t_i,w_i))$

Heun's Method

Too complicated for exam.

Example

$y^{\prime }(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|=|2\cos 2y|\le 2$

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

Let's use Modified Euler...

• $w_0=0$
• $w_1=0+\frac{1}{4}(f(0,0)+f(\frac{1}{2},0+\frac{1}{2}f(0,0)))=\frac{1}{4}f(\frac{1}{2},0)=\frac{\pi }{2}$
• $w_2=\frac{\pi }{2}+\frac{1}{4}(f(\frac{1}{2},\frac{\pi }{2})+f(1,\frac{pi}{2}+\frac{1}{2}f(\frac{1}{2},\frac{\pi }{2})))=2\pi$

Chapter 6

(skip linear algebra review)

$A=\left[\begin{array}{ccc}5& 0& 1\\ 4& 1& 7\\ 5& 0& 2\end{array}\right]$

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

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[i,j=a]$: 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[i,j=-a]$

$L=\left[\begin{array}{ccc}1& 0& 0\\ \frac{4}{5}& 1& 0\\ ◻& ◻& 1\end{array}\right]$

$L=\left[\begin{array}{ccc}1& 0& 0\\ \frac{4}{5}& 1& 0\\ 1& ◻& 1\end{array}\right]$

$L=\left[\begin{array}{ccc}1& 0& 0\\ \frac{4}{5}& 1& 0\\ 1& 0& 1\end{array}\right]$

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=\left[\begin{array}{ccc}4& a& 5\\ a& 1& 0\\ 5& 0& 7\end{array}\right]$

Hence

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

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

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=\left[\begin{array}{ccc}4& 0& 5\\ 0& 1& 0\\ 5& 0& 7\end{array}\right]=\left[\begin{array}{ccc}4& 0& 0\\ 0& 1& 0\\ 5& 0& \frac{3}{4}\end{array}\right]\left[\begin{array}{ccc}1& 0& \frac{5}{4}\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$

Then $L^T=\left[\begin{array}{ccc}\sqrt{4}& 0& \frac{5}{\sqrt{4}}\\ 0& \sqrt{1}& 0\\ 0& 0& \sqrt{7-5\cdot \frac{5}{\sqrt{4}}}\end{array}\right]=\left[\begin{array}{ccc}2& 0& \frac{5}{2}\\ 0& 1& 0\\ 0& 0& \frac{\sqrt{3}}{2}\end{array}\right]$

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 ${\Vert A\Vert }_p=\underset{{\Vert \overrightarrow{x}\Vert }_p=1}{\max }{\Vert A\overrightarrow{x}\Vert }_p$, but this is a pain to compute. We settle for the following theorems:

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

Theorem. ${\Vert \overrightarrow{x}\Vert }_A=\sqrt{{\overrightarrow{x}}^{T}Ax}$ is a norm if $A$ is positive definite.

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

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

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

${\Vert \overrightarrow{x}\Vert }_A=\sqrt{{\overrightarrow{x}}^{T}A\overrightarrow{x}}=\sqrt{{\overrightarrow{x}}^{T}L{L}^T\overrightarrow{x}}=\sqrt{{\left(L^T\overrightarrow{x}\right)}^T\left(L^T\overrightarrow{x}\right)}=\sqrt{{\Vert L^{T}x\Vert }_2^2}={\Vert L^{T}x\Vert }_2$

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

Next, ${\Vert \alpha \overrightarrow{x}\Vert }_A=\sqrt{{\alpha }^2{\overrightarrow{x}}^{T}A\overrightarrow{x}}=\left|\alpha \right|{\Vert \overrightarrow{x}\Vert }_A$

Finally, $⟨x,y_A⟩=x^{T}Ay\le \sqrt{{\overrightarrow{x}}^{T}A\overrightarrow{x}}\sqrt{{\overrightarrow{y}}^{T}A\overrightarrow{y}}=\Vert L^T\overrightarrow{x}\Vert \Vert L^T\overrightarrow{y}\Vert \le {\Vert \overrightarrow{x}\Vert }_A\cdot {\Vert \overrightarrow{y}\Vert }_A$

quod erat demonstrandum

Example

Find ${\ell }_2$ norm of $A=\left[\begin{array}{ccc}4& 0& 5\\ 0& 1& 0\\ 5& 0& 7\end{array}\right]$

Eigenvalues are found by

$\left|\begin{array}{ccc}4-\lambda & 0& 5\\ 0& 1-\lambda & 0\\ 5& 0& 7-\lambda \end{array}\right|=(1-\lambda )({\lambda }^2-11\lambda +3)=0$

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

Chapter 8

Given $f(x)$, approximate $p(x)=a_1{\varphi }_1(x)+a_2{\varphi }_2(x)+\dots +a_n{\varphi }_n(x)$.

To do this, we find the best least squares fit (i.e. minimize Euclidean distance) ${\Vert f-p\Vert }_2^2=\underset{q\in \mathrm{\Pi }}{\min }{\Vert f-q\Vert }_2^2$, where $\mathrm{\Pi }=\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{{\varphi }_1,{\varphi }_2,\dots ,{\varphi }_n\}$.

Normal equations given by

$\left[\begin{array}{cccc}⟨{\varphi }_1,{\varphi }_1⟩& ⟨{\varphi }_1,{\varphi }_2⟩& \dots & ⟨{\varphi }_1,{\varphi }_n⟩\\ ⟨{\varphi }_2,{\varphi }_1⟩& ⟨{\varphi }_2,{\varphi }_2⟩& \dots & ⟨{\varphi }_2,{\varphi }_n⟩\\ ⋮& ⋮& \ddots & ⋮\\ ⟨{\varphi }_n,{\varphi }_1⟩& ⟨{\varphi }_n,{\varphi }_2⟩& \dots & ⟨{\varphi }_n,{\varphi }_n⟩\end{array}\right]\left[\begin{array}{c}{a}_1\\ a_2\\ ⋮\\ a_n\end{array}\right]=\left[\begin{array}{c}⟨f,{\varphi }_1⟩\\ ⟨f,{\varphi }_2⟩\\ ⋮\\ ⟨f,{\varphi }_n⟩\end{array}\right]$

• Given continuous functions, the inner product is given by $⟨f,g⟩=\underset{a}{\overset{b}{\int }}f(x)g(x)w(x)\mathrm{d}x$
• Given point samples, the inner product is given by $⟨f,g⟩=\sum _i{f}_i{g}_i{w}_i$