MATH 417 Lecture 20

« previous | Thursday, April 3, 2014 | next »

Gaussian Elimination with Partial Pivoting

Step 0. System of equations Ax=b

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

Step 1. cell [1,1] is 0. That's unfortunate, so Switch rows 1 & 2

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

Step 2. subtract 1*(top row) from (bottom row)

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

Step 3. multiply (second row) by 1/2

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

Step 4. multiply (bottom row) by -1

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

Step 5. subtract (second row) from (bottom row)

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

Step 5. multiply (bottom row) by -1

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

Step 7. Perform back substitution to get

$\begin{array}{rl}{x}_3& =3\\ x_2& =-2\\ x_1& =-1\end{array}$

At each step, we left multiply by an elementary matrix. This elementary matrix is the identity matrix with the same operation performed on it:

1. $I=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]⟶E_1=\left[\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right]$
2. $I=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]⟶E_2=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ -1& 0& 1\end{array}\right]$
3. $I=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]⟶E_3=\left[\begin{array}{ccc}1& 0& 0\\ 0& \frac{1}{2}& 0\\ 0& 0& 1\end{array}\right]$

and so on...

Observation: Each $E_k$ has two possibilities:

1. row permutations
2. lower triangular matrix

Note, if we perform row permutations $P_1\cdot P_2\dots P_n$ at the start, then we can proceed with Gaussian elimination without pivoting.

Let $\tilde{A}:=P_n\dots P_2{P}_{1}A$

Now since $E_k\dots E_3{E}_2\tilde{A}=U$, we have $A=(E_k\dots E_3{E}_2{)}^{-1}U$, so $(E_k\dots E_3{E}_2{)}^{-1}=L=E_2^{-1}{E}_3^{-1}\dots E_k^{-1}$

What is $E_i^{-1}$?

1. row-scaling: $E=\left[\begin{array}{cccc}\lambda & 0& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]⟶E^{-1}=\left[\begin{array}{ccc}\frac{1}{\lambda }& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$
2. row-addition: $E=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ \alpha & 0& 1\end{array}\right]⟶E^{-1}=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ -\alpha & 0& 1\end{array}\right]$

To multiply these inverses, take superposition of matrices

• combine nonzero entries not along diagonal
• multiply corresponding entries on diagonals

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

Therefore, given $A$, if we can run gaussian elimination without pivoting, then $A=LU$ and $L=\left[\begin{array}{cc}{\ell }_{11}& 0\\ {\ell }_{ij}& l_{nn}\end{array}\right]$; $U=\left[\begin{array}{cc}1& u_{ij}\\ 0& 1\end{array}\right]$

In practice, we can store $L$ and $U$ in the same matrix: $\left[\begin{array}{cc}{\ell }_{11}& u_{ij}\\ {\ell }_{ij}& {\ell }_{nn}\end{array}\right]$

In contrast, we can do Gaussian elimination without pivoting (i.e. leave diagonal entries ≠ 1). In this case, our LU decomposition is

$L=\left[\begin{array}{cc}1& 0\\ {\ell }_{ij}& 1\end{array}\right]$ $U=\left[\begin{array}{cc}{u}_{11}& u_{ij}\\ 0& u_{nn}\end{array}\right]$

If we have $A=A^T$, can we get $A=\tilde{L}={\tilde{L}}^T$? we should be able to (see later)

Diagonalization

$\begin{array}{rl}LU& =\left[\begin{array}{ccc}1& 0& 0\\ {\ell }_{21}& 1& 0\\ {\ell }_{31}& {\ell }_{32}& 1\end{array}\right]*\left[\begin{array}{ccc}{u}_{11}& u_{12}& u_{13}\\ 0& u_{22}& u_{23}\\ 0& 0& u_{33}\end{array}\right]\\ & =\left[\begin{array}{ccc}1& 0& 0\\ {\ell }_{21}& 1& 0\\ {\ell }_{31}& {\ell }_{32}& 1\end{array}\right]*\left[\begin{array}{ccc}{u}_{11}& 0& 0\\ 0& u_{22}& 0\\ 0& 0& u_{33}\end{array}\right]*\left[\begin{array}{ccc}1& \frac{u_{12}}{u_{11}}& \frac{u_{13}}{u_{11}}\\ 0& 1& \frac{u_{23}}{u_{22}}\\ 0& 0& 1\end{array}\right]\\ & =L\mathrm{\Delta }\tilde{U}\end{array}$

In this case, the diagonal entries of $\mathrm{\Delta }$ are the eigenvalues of the matrix.

Theorem: If there are $n$ eigenvalues, then there will be $n$ independent eigenvectors.

LDL Decomposition / Choleski Factorization

Above we saw a decomposition of the form $A=LD{L}^T$. This is called LDL decomposition.

We can alternatively write this as $L\sqrt{D}\sqrt{D}{L}^T=(L\sqrt{D})(L\sqrt{D}{)}^T=\tilde{L}{\tilde{L}}^T$

So in the example above, we have ${\ell }_{21}=\frac{u_{12}}{u_{11}}$

Special Matrices

Diagonally Dominant

Given $A=(a_{ij})$, for every row, we have $\left|a_{ii}\right|\ge \sum _{j\ne i}\left|a_{ij}\right|\ge 0$

"strictly" variant: $\left|a_{ii}\right|>\sum _{j\ne i}\left|a_{ij}\right|\ge 0$

We will consider only this "strict" case

Positive Definite

For any $\overrightarrow{x}\ne \overrightarrow{0}$, we have ${\overrightarrow{x}}^{T}A\overrightarrow{x}\ge 0$

also called non-negative definite

"strictly" variant: ${\overrightarrow{x}}^{T}A\overrightarrow{x}>0$

We will consider only this "strict" case

Theorem

Theorem. If $A$ is strictly diagonally dominant or strictly positive definite, then $A$ is non-singular.

Proof. Assume to the contrary that $A$ is singular. Then $A\overrightarrow{x}=\overrightarrow{0}$ has a non-trivial solution ($\overrightarrow{x}\ne \overrightarrow{0}$)

Case 1: $A$ is diagonally dominant. Take $\overrightarrow{x}=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right]$. Find $x_j$ such that $\left|x_j\right|=\underset{1\le i\le n}{\max }\left|x_i\right|$

Solve the system for $a_{jj}{x}_j=-\sum _{k=1;k\ne j}^n{a}_{jk}{x}_k$. Hence

$\begin{array}{rl}\left|a_{jj}\right|\left|x_j\right|& =\left|\sum _{k\ne j}{a}_{jk}{x}_k\right|\le \sum _{k\ne j}\left|a_{jk}\right|\left|x_k\right|\\ \left|a_{jj}\right|\le \sum _{k\ne j}\left|a_{kj}\right|\left|\frac{x_k}{x_j}\right|\end{array}$

Observe that $\left|\frac{x_k}{x_j}\right|\le 1$, so

$\left|a_{jj}\right|\le \sum _{k\ne j}\left|a_{kj}\right|\left|\frac{x_k}{x_j}\right|\le \sum _{k\ne j}\left|a_{jk}\right|<a_{jj}$

→CONTRADICTION

Case 2: $A$ is positive definite and $A\overrightarrow{x}=\overrightarrow{0}$ for some $\overrightarrow{x}\ne \overrightarrow{0}$.

$0<{\overrightarrow{x}}^{T}A\overrightarrow{x}={\overrightarrow{x}}^T\overrightarrow{0}=0$

If ${\lambda }_1$ is an eigenvalue of $A$, then $A\overrightarrow{x_1}={\lambda }_1{x}_1$ for some $x_1$.

${\overrightarrow{x}}_{1}A{\overrightarrow{x}}_1={\overrightarrow{x}}_1^T{\lambda }_1{\overrightarrow{x}}_1={\lambda }_1{\overrightarrow{x}}_1^T{\overrightarrow{x}}_1>0$

Hence ${\lambda }_1>0$.

...

quod erat demonstrandum

Going back to diagonal dominance. If we do Gaussian elimination, we are guaranteed that we will not need any pivoting