MATH 417 Lecture 23

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

Conjugate Gradient

Given a system

$A\,{\vec {x}}={\vec {b}}$

The solution to ${\vec {x}}$ is given by

${\begin{aligned}x_{1}&={\frac {1}{a_{11}}}\,\left(b_{1}-a_{12}\,x_{2}-a_{13}\,x_{3}-\dots -a_{1n}\,x_{n}\right)\\x_{2}&={\frac {1}{a_{22}}}\,\left(b_{2}-a_{21}\,x_{1}-a_{23}\,x_{3}-\dots -a_{2n}\,x_{n}\right)\\x_{i}&={\frac {1}{a_{ii}}}\,\left(b_{i}-\dots \right)\\x_{n}&={\frac {1}{a_{nn}}}\,\left(b_{n}-a_{n1}\,x_{2}-a_{n2}\,x_{3}-\dots -a_{n,n-1}\,x_{n-1}\right)\\\end{aligned}}$

Given ${\vec {x}}^{(0)}$ (for sequence ${\vec {x}}^{(k)}$), find ${\vec {x}}^{(1)}$ using ${\vec {x}}^{(0)}$ in the RHS.

We have $A\,{\vec {x}}={\vec {b}}$, we have $A=D+({\mbox{rest}})$.

We want $D\,{\vec {x}}={\mbox{RHS}}$, where ${\vec {x}}=D^{-1}\,({\mbox{rest}})$.

Therefore ${\vec {x}}^{(k)}=T\,{\vec {x}}^{(k-1)}+C$

If $\rho (T)<1$, then $\lim _{k\to \infty }{\vec {x}}^{(k)}={\vec {x}}$.

Hence the equation for $x_{i}^{(k)}$ in our matrix above is $x_{i}^{(k)}={\frac {1}{a_{ii}}}\,\left(b_{i}-a_{i1}\,x_{1}^{(k)}-a_{i2}\,x_{2}^{(k)}-\dots -a_{i,i-1}\,x^{(k)}-a_{i,i+1}\,x_{i+1}^{(k-1)}-\dots -a_{in}\,x_{n}^{(k-1)}\right)$

Quiz

Find LU decomposition for $A$:

$A={\begin{bmatrix}1&1&0&3\\2&1&-1&1\\3&-1&-1&2\\-1&2&3&-1\end{bmatrix}}$

Method 1

${\begin{bmatrix}1&1&0&3\\2&1&-1&1\\3&-1&-1&2\\-1&2&3&-1\end{bmatrix}}\to {\begin{bmatrix}1&1&0&3\\0&-1&-1&-5\\0&-4&-1&-7\\0&3&3&2\end{bmatrix}}$

and

$L={\begin{bmatrix}1&0&0&0\\2&1&0&0\\3&&1&0\\-1&&&1\end{bmatrix}}$

${\begin{bmatrix}1&1&0&3\\0&-1&-1&-5\\0&-4&-1&-7\\0&3&3&2\end{bmatrix}}\to {\begin{bmatrix}1&1&0&3\\0&-1&-1&-5\\0&0&3&13\\0&0&0&-13\end{bmatrix}}=U$

and

$L={\begin{bmatrix}1&0&0&0\\2&1&0&0\\3&4&1&0\\-1&-3&0&1\end{bmatrix}}$

Method 2

If we wanted $U_{ii}=1$ for $i=1\ldots 4$, we multiply row 2 by $-1$, row 3 by ${\frac {1}{3}}$, and row 4 by $-{\frac {1}{13}}$ along the way. (this is where I made my mistake)

Traces back to Gauss

Objects orbit in an ellipse. An ellipse has two parameters. Suppose we have a bunch of measurements that are points close to an elliptical trajectory. We want to find an ellipse that best fits the data we have.

Given $(x_{i},f_{i})$ for $i=1\ldots n$, find $P(x)=a\,x+b$ such that $P(x_{i})=f_{i}$

Let's look at the error: $e_{i}=p(x_{i})-f_{i}$. We want to minimize $\left\|e\right\|_{2}$.

Does such a minimum exist?

$\left\|e\right\|_{2}^{2}=\sum _{i=1}^{n}\left(a\,x_{i}+b_{i}-f_{i}\right)^{2}$ is a sum of all nonnegative terms. The minimum possible value of each term is 0, so if this is the case, the line is a perfect fit.

Let $g(b,a)=\left\|e\right\|_{2}^{2}$. Then the minimum of $g(a,b)$ occurs when $\nabla g=(0,0)$:

$\nabla g=\left({\frac {\partial g}{\partial b}},{\frac {\partial g}{\partial a}}\right)=2\,\left(\sum _{i=1}^{n}\left(a\,x_{i}+b-f_{i})^{2}\right),\,\sum _{i=0}^{n}\left(a\,x_{i}+b-f_{i}\right)\,x_{i}\right)$

Break apart the components of $\nabla g$:

${\begin{cases}a\,\sum _{i=1}^{n}x_{i}+b\,n-\sum _{i=1}^{n}f_{i}=0\\a\,\sum _{i=1}^{n}{x_{i}}^{2}+b\,\sum _{i=1}^{n}x_{i}-\sum _{i=1}^{n}x_{i}\,f_{i}=0\end{cases}}$

Thus we have a system of the form:

${\begin{bmatrix}\sum _{i=1}^{n}1&\sum _{i=1}^{n}x_{i}\\\sum _{i=1}^{n}x_{i}&\sum _{i=1}^{n}{x_{i}}^{2}\end{bmatrix}}\,{\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}\sum _{i=1}^{n}f_{i}\\\sum _{i=1}^{n}x_{i}\,f_{i}\end{bmatrix}}$

The matrix of sums is symmetric and positive definite. Observe that for the overdefined system $A\,{\vec {x}}={\vec {f}}$, we have

${\begin{bmatrix}\sum _{i=1}^{n}1&\sum _{i=1}^{n}x_{i}\\\sum _{i=1}^{n}x_{i}&\sum _{i=1}^{n}{x_{i}}^{2}\end{bmatrix}}=A^{T}\,A$

and

${\begin{bmatrix}\sum _{i=1}^{n}f_{i}\\\sum _{i=1}^{n}x_{i}\,f_{i}\end{bmatrix}}=A^{T}\,{\vec {f}}$

Hence

$A^{T}\,A\,{\vec {x}}=A^{T}\,{\vec {f}}$

The resulting system is called the normal equations.

Now this method works for any parameterized equation.