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 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} is symmetric, we can find 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} such that 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 \, 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 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} and equal to zero only 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{x} = \vec{0}} .

Next, 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\| \alpha \, \vec{x} \right\|_A = \sqrt{ \alpha^2 \, \vec{x}^T \, A \, \vec{x} } = \left| \alpha \right| \, \left\| \vec{x} \right\|_A}

Finally, 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\langle x,y_A \right\rangle = x^T \, A \, y \le \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\| \le \left\| \vec{x} \right\|_A \cdot \left\| \vec{y} \right\|_A}

quod erat demonstrandum

Example

Find 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 \ell_2} norm 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 = \begin{bmatrix} 4 & 0 & 5 \\ 0 & 1 & 0 \\ 5 & 0 & 7 \end{bmatrix}}

Eigenvalues are found 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 \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 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 \lambda \in \left\{ 1, \frac{11 \pm \sqrt{109}}{2} \right\}} , 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 \max_i \left| \lambda_i \right| = \frac{11 + \sqrt{109}}{2}}

Chapter 8

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 f(x)} , approximate 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 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) 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\| f - p \right\|_2^2 = \min_{q \in \Pi} \left\| f - q \right\|_2^2} , 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 \Pi = \mathrm{Span} \left\{ \phi_1, \phi_2, \ldots, \phi_n \right\}} .

Normal equations given 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 \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 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\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 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\langle f,g \right\rangle = \sum_i f_i \, g_i \, w_i}