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)$:

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 \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 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 \nabla g} :

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

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} \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 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 \, \vec{x} = \vec{f}} , we have

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} \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

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} \sum_{i=1}^n f_i \\ \sum_{i=1}^n x_i \, f_i \end{bmatrix} = A^T \, \vec{f}}

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 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.