MATH 417 Lecture 26

From Notes
Jump to navigation Jump to search

« 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): 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{\mathrm{d}y}{\mathrm{d}t} = f(t,y)} , 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 y(a) = \alpha} 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 \le t \le b} .

Is the IVP well-posed?

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


Numerical Methods

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

Over interval 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[ a,b \right]} 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 n} sample points, we define 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 h := \frac{b-a}{n}}

Let 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_i = y(t_i)} , 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 t_i = a + i \, h} , 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 w_0 = y(a) = \alpha}

Rule is of form:

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_{i+1} = w_i + \mbox{numerical integration method}}

Euler's Method

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 \int_{t_i}^{t_{i+1}} f(t,y) \,\mathrm{d}t} by left endpoint riemann rule: 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_{t_i}^{t_{i+1}} f(t,y) \,\mathrm{d}t \approx h \, f(t_i,y(t_i))} .

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_{i+1} = w_i + h \, f(t_i, w_i)}

Modified Euler's Method

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 \int_{t_i}^{t_{i+1}} f(t,y) \,\mathrm{d}t} by trapezoidal rule: 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_{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)} .

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_{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 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_{t_i}^{t_{i+1}} f(t,y) \,\mathrm{d}t} by midpoint rule: 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_{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))} .

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

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 y'(t) = \sin{2y} + 4\pi\,t} , 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 y(0) = 0}

This is well-posed:

  • domain of RHS is entire real plane
  • 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| \frac{\partial f}{\partial y} \right| = \left| 2\cos{2y} \right| \le 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 h = \frac{1}{2}}

Let's use Modified Euler...

  • 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}
  • 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_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}}
  • 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{\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)

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} 5 & 0 & 1 \\ 4 & 1 & 7 \\ 5 & 0 & 2 \end{bmatrix}}

We wish to 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} 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 U} 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 \, U} :

Standard Gaussian elimination sets the pivot elements equal to 1, and this requires a little extra modification to 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} . If we stick with just elementay operation #3 (adding a multiple of one row to another), then computation 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 L} is easy:

Elementary matrix 3 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 E_{ij} = I\left[ i,j = a \right]} : this will add 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} times row 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 j} to row 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 i} . The 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 i,j} -th entry of the identity matrix 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 a} . Computing the inverse is incredibly straightforward:

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_{ij}^{-1} = I \left[ i,j = -a \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 L = \begin{bmatrix} 1 & 0 & 0 \\ \frac{4}{5} & 1 & 0 \\ \Box & \Box & 1 \end{bmatrix}}

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

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


Positive Definite Matrices

Theorem. A 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} is positive definite if and only if the determinants of all the minors 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} are positive:

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 & a & 5 \\ a & 1 & 0 \\ 5 & 0 & 7 \end{bmatrix}}

Hence

  • 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| 4 \right| = 4 > 0}
  • 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 & a \\ a & 1 \end{vmatrix} = 4-a^2 > 0}
  • 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| A \right| = 3-7a^2 > 0}

From these constraints, we get 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 \in \left( -\sqrt{ \frac{3}{7} }, \sqrt{ \frac{3}{7} }\right)}


Cholesky [sp?] Factorization

Given symmetric 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} , 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} .

To get this, perform LU decomposition, but replace diagonal pivot elements 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 L} 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 \sqrt{\ell_{ii}}} (and multiply the corresponding column 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 \frac{1}{\sqrt{\ell_{ii}}}} ).

Let 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} = \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 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^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 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 \, A^T} .


Matrix Norms

All norms discussed here are called "native"

Defined as 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\| 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. 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\| A \right\|_\infty = \mbox{max row sum} = \max_i \sum_{j=1}^n \left| a_{ij} \right|}
  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 \left\| A \right\|_1 = \left\| A^T \right\|_\infty = \mbox{max column sum} = \max_j \sum_{i=1}^n \left| a_{ij} \right|}
  3. 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\| A \right\|_2 = \sqrt{ \rho(A^T \, A) }} , 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 \rho(A) = \max_i \left| \lambda_i \right|} is the largest magnitude eigenvalue.

Theorem. 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\| \vec{x} \right\|_A = \sqrt{\vec{x}^T \, A \, x}} is a norm if 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 positive definite.

Proof. By definition, 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\| \cdot \right\|} is a norm if and only if it satisfies the following:

  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 \left\| x \right\| \ge 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 \left\| x \right\| = 0} if and only if 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} .
  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 \left\| \alpha \, x \right\| = \left| \alpha \right| \, \left\| x \right\|} for all constants 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 \alpha}
  3. 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\| x + y \right\| \le \left\| x \right\| + \left\| y \right\|} , which holds iif and only if the Cauchy-Schwartz inequality (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 \right\rangle \le \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

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\| \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}
Retrieved from "https://notes.komputerwiz.net/w/index.php?title=MATH_417_Lecture_26&oldid=7691"