MATH 417 Lecture 25

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

Section 8.1 and 8.2

Least Squares approximation

$f(x)\approx a_1{\varphi }_1(x)+a_2{\varphi }_2(x)+\dots +a_n{\varphi }_n(x)$

usually $n=2$ (linear) or $n=3$ (quadratic)

$⟨f,g⟩$ is given, so we wish to minimize ${\Vert f-p\Vert }^2=⟨f-p,f-p⟩$

In 8.1, $⟨f,g⟩=\sum _{i=1}^n{w}_i{f}_i{g}_i$, where $w_i>0$ is a probability weight distribution.

In 8.2, $⟨f,g⟩=\underset{a}{\overset{b}{\int }}w(x)f(x)g(x)$

Common definitions of $w(x)$:

• $w(x)=1$ (classic definition)
• $w(x)=\frac{1}{1+x^2}$ on $[-\mathrm{\infty },\mathrm{\infty }]$
• $w(x)=\sqrt{1-x^2}$ on $[-1,1]$
• $w(x)=\frac{1}{\sqrt{1-x^2}}$

Basic Concept

We compute $\mathrm{\Psi }(a_1,a_2,\dots ,a_n)=\underset{0}{\overset{1}{\int }}{|f(x)-p(x)|}^{2}w(x)\mathrm{d}x$ and find the minimum. To find this minimum, we solve for $\mathrm{\nabla }\mathrm{\Psi }=0$. This gives a system of normal equations:

$A=\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 }_2,{\varphi }_n⟩& \dots & ⟨{\varphi }_n,{\varphi }_n⟩\end{array}\right]$

This matrix is positive definite, so it has an inverse.

$b=\left[\begin{array}{c}⟨{\varphi }_1,f⟩\\ ⟨{\varphi }_2,f⟩\\ ⋮\\ ⟨{\varphi }_n,f⟩\end{array}\right]$

This system is solvable, but it's a pain to solve.

Original function $f(x)=x^3$.

Best Quadratic fit $p(x)=\frac{1}{20}-\frac{3}{5}x+\frac{3}{2}{x}^2$.

For example, find the best fit to $x^3$ by $p(x)=a_1+a_{2}x+a_3{x}^2$ on $[0,1]$

$\left[\begin{array}{ccc}1& \frac{1}{2}& \frac{1}{3}\\ \frac{1}{2}& \frac{1}{3}& \frac{1}{4}\\ \frac{1}{3}& \frac{1}{4}& \frac{1}{5}\end{array}\right]\left[\begin{array}{c}{a}_1\\ a_2\\ a_3\end{array}\right]=\left[\begin{array}{c}⟨1,x^3⟩\\ ⟨x,x^3⟩\\ ⟨x^2,x^3⟩\end{array}\right]$

Simplifying Normal Equations

What if $A$ were a diagonal matrix? That is, what if $⟨{\varphi }_i,{\varphi }_j⟩=0$ for $i\ne j$?

Then ${\varphi }_1$, ${\varphi }_2$, etc. would be an orthogonal basis for our regression space.

Continuing with our example, let $p=c_1{\varphi }_1+c_2{\varphi }_2+c_3\varphi (3)$, where ${\varphi }_1(x)=1$, ${\varphi }_2(x)=2x-1$, and ${\varphi }_3(x)=3(2x-1{)}^2-1$. $\{{\varphi }_1,{\varphi }_2,{\varphi }_3\}$ is an orthogonoal basis for our regression space.

$\left[\begin{array}{ccc}⟨1,1⟩& 0& 0\\ 0& ⟨2x-1,2x-1⟩& 0\\ 0& 0& ⟨3(2x-1{)}^2-1,3(2x-1{)}^2-1⟩\end{array}\right]\left[\begin{array}{c}{c}_1\\ c_2\\ c_3\end{array}\right]=\left[\begin{array}{c}⟨1,x^3⟩\\ ⟨2x-1,x^3⟩\\ ⟨3(2x-1{)}^2-1,x^3⟩\end{array}\right]$

This gives a much easier system to solve:

$\left[\begin{array}{ccc}1& 0& 0\\ 0& \frac{1}{3}& 0\\ 0& 0& \frac{4}{5}\end{array}\right]\left[\begin{array}{c}{c}_1\\ c_2\\ c_3\end{array}\right]=\left[\begin{array}{c}\frac{1}{4}\\ \frac{2}{5}-\frac{1}{4}\\ \frac{1}{10}\end{array}\right]$

There are two ways to find an orthogonal basis for $p$

1. Legendre polynomials
2. Gram-Schmidt

Legendre Polynomials

$L_n(x)=\frac{{\mathrm{d}}^n}{\mathrm{d}{x}^n}\left[{(1-x^2)}^n\right]$

For $n\in \{0,1,2\}$, we have:

• $L_0(x)=1$,
• $L_1(x)=x$, and
• $L_2(x)=3x^2-1$

These only work on $[-1,1]$, so we shift and scale to $[0,1]$ by substituting $y=\frac{x+1}{2}$ (or $x=2y-1$). Performing this substitution gives our $\varphi$'s above.

Gram-Schmidt

This will always give an orthonormal basis, so $⟨{\varphi }_i,{\varphi }_j⟩={\delta }_{ij}$:

def ip(f, g, a, b):
    return integrate(f*g, x, a, b)

def norm(f, a, b):
    return sqrt(ip(f, f, a, b))

def normalize(f, a, b):
    return f/norm(f, a, b)

def gram_schmidt(basis, a, b):
    on_basis = [normalize(basis[0], a, b)]
    for i in xrange(1, len(basis)):
        p = sum(ip(basis[i], e, a, b) * e for e in on_basis)
        next_e = normalize(basis[i] - p, a, b)
        on_basis.append(next_e)
    return map(simplify, on_basis)

• ${\phi }_1(x)=1$
• ${\phi }_2(x)=\sqrt{3}(2x-1)$
• ${\phi }_3(x)=\sqrt{5}(6x^2-6x+1)$

Now we have

$\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{c}{\alpha }_1\\ {\alpha }_2\\ {\alpha }_3\end{array}\right]=\left[\begin{array}{c}\frac{1}{4}\\ \frac{3\sqrt{3}}{20}\\ \frac{\sqrt{5}}{20}\end{array}\right]$

Quiz Discussion: Matrix Norms

${\Vert A\Vert }_p=\underset{{\Vert x\Vert }_p=1}{\max }{\Vert Ax\Vert }_p$

This is horrible. Bojan Popov

Find ${\Vert A\Vert }_1$, ${\Vert A\Vert }_2$, and ${\Vert A\Vert }_{\mathrm{\infty }}$ for

$A=\left[\begin{array}{ccc}1& 0& -2\\ 0& 2& 0\\ -1& 0& 3\end{array}\right]$

${\Vert A\Vert }_{\mathrm{\infty }}$ is the max row sum, so ${\Vert A\Vert }_{\mathrm{\infty }}=4$

${\Vert A\Vert }_1$ is just the max column sum, so ${\Vert A\Vert }_1=5$

${\Vert A\Vert }_2=\sqrt{\rho (A^{T}A)}$, so

1. $A^{T}A=\left[\begin{array}{ccc}2& 0& -5\\ 0& 4& 0\\ -5& 0& 13\end{array}\right]$,
2. $\rho (A^{T}A)=\underset{i}{\max }{\lambda }_i=\max \{4,\frac{15+\sqrt{221}}{2},\frac{15-\sqrt{221}}{2}\}=\frac{15+\sqrt{221}}{2}$
3. $\sqrt{\rho (A^{T}A)}=\sqrt{\frac{15+\sqrt{221}}{2}}$