MATH 417 Lecture 23

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

Conjugate Gradient

Given a system

$A\overrightarrow{x}=\overrightarrow{b}$

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

$\begin{array}{rl}{x}_1& =\frac{1}{a_{11}}(b_1-a_{12}{x}_2-a_{13}{x}_3-\dots -a_{1n}{x}_n)\\ x_2& =\frac{1}{a_{22}}(b_2-a_{21}{x}_1-a_{23}{x}_3-\dots -a_{2n}{x}_n)\\ x_i& =\frac{1}{a_{ii}}(b_i-\dots )\\ x_n& =\frac{1}{a_{nn}}(b_n-a_{n1}{x}_2-a_{n2}{x}_3-\dots -a_{n,n-1}{x}_{n-1})\\ \end{array}$

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

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

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

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

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

Hence the equation for $x_i^{(k)}$ in our matrix above is $x_i^{(k)}=\frac{1}{a_{ii}}(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)})$

Quiz

Find LU decomposition for $A$:

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

Method 1

$\left[\begin{array}{cccc}1& 1& 0& 3\\ 2& 1& -1& 1\\ 3& -1& -1& 2\\ -1& 2& 3& -1\end{array}\right]\to \left[\begin{array}{cccc}1& 1& 0& 3\\ 0& -1& -1& -5\\ 0& -4& -1& -7\\ 0& 3& 3& 2\end{array}\right]$

and

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

$\left[\begin{array}{cccc}1& 1& 0& 3\\ 0& -1& -1& -5\\ 0& -4& -1& -7\\ 0& 3& 3& 2\end{array}\right]\to \left[\begin{array}{cccc}1& 1& 0& 3\\ 0& -1& -1& -5\\ 0& 0& 3& 13\\ 0& 0& 0& -13\end{array}\right]=U$

and

$L=\left[\begin{array}{cccc}1& 0& 0& 0\\ 2& 1& 0& 0\\ 3& 4& 1& 0\\ -1& -3& 0& 1\end{array}\right]$

Method 2

If we wanted $U_{ii}=1$ for $i=1\dots 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\dots n$, find $P(x)=ax+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 ${\Vert e\Vert }_2$.

Does such a minimum exist?

${\Vert e\Vert }_2^2=\sum _{i=1}^n{(a{x}_i+b_i-f_i)}^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)={\Vert e\Vert }_2^2$. Then the minimum of $g(a,b)$ occurs when $\mathrm{\nabla }g=(0,0)$:

$\mathrm{\nabla }g=(\frac{\partial g}{\partial b},\frac{\partial g}{\partial a})=2(\sum _{i=1}^n(a{x}_i+b-f_i{)}^2),\sum _{i=0}^n(a{x}_i+b-f_i)x_i)$

Break apart the components of $\mathrm{\nabla }g$:

$\{\begin{array}{l}a\sum _{i=1}^n{x}_i+bn-\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{array}$

Thus we have a system of the form:

$\left[\begin{array}{cc}\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{array}\right]\left[\begin{array}{c}a\\ b\end{array}\right]=\left[\begin{array}{c}\sum _{i=1}^n{f}_i\\ \sum _{i=1}^n{x}_i{f}_i\end{array}\right]$

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

$\left[\begin{array}{cc}\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{array}\right]=A^{T}A$

and

$\left[\begin{array}{c}\sum _{i=1}^n{f}_i\\ \sum _{i=1}^n{x}_i{f}_i\end{array}\right]=A^T\overrightarrow{f}$

Hence

$A^{T}A\overrightarrow{x}=A^T\overrightarrow{f}$

The resulting system is called the normal equations.

Now this method works for any parameterized equation.