04 - Linear Systems and Matrix Algorithms

Linear System

Consider system $Ax=b$ in linear system form

$$\begin{array}{rl}{a}_{11}{x}_1+a_{12}{x}_2& +\cdots +a_{1n}{x}_n=b_1\\ a_{21}{x}_1+a_{22}{x}_2& +\cdots +a_{2n}{x}_n=b_2\\ & ⋮\\ a_{n1}{x}_1+a_{n2}{x}_2& +\cdots +a_{nn}{x}_n=b_n\end{array}$$

Forward Substitution

Let $A=(a_{ij})$ be a lower triangular matrix so $a_{ij}=0$ for all $1\le i<j\le n$
Let $Ax=b$ be in Linear System form

As $A$ is lower triangular then using a procedure called Forward Substitution then

$$\begin{array}{rlrl}{a}_{11}{x}_1& =b_1⟹x_1=\frac{b_1}{a_{11}}& & \Downarrow \\ a_{21}{x}_1+a_{22}{x}_2& =b_2⟹x_2=\frac{b_2-a_{21}{x}_1}{a_{22}}& & \Downarrow \\ & ⋮& & \Downarrow \\ a_{i1}{x}_1+a_{i2}{x}_2+\cdots +a_{ii}{x}_i& =b_i⟹x_i=\frac{b_i-{\sum }_{j=1}^{i-1}{a}_{ij}{x}_j}{a_{ii}}& & \Downarrow \\ & ⋮& & \Downarrow \end{array}$$

where this only works if $a_{ii}\ne 0$ for all $i$

Backward Substitution

Let $A=(a_{ij})$ be a upper triangular matrix so $a_{ij}=0$ for all $1\le j<i\le n$
Let $Ax=b$ be in Linear System form

As $A$ is upper triangular then using a procedure called Backward Substitution then

$$\begin{array}{rlrl}& ⋮& & \Uparrow \\ a_{ii}{x}_i+\cdots +a_{i,n-1}{x}_{n-1}+a_{1n}{x}_n& =b_i⟹x_i=\frac{b_i-{\sum }_{j=1+1}^n{a}_{ij}{x}_j}{a_{ii}}& & \Uparrow \\ & ⋮& & \Uparrow \\ a_{n-1,n-1}{x}_{n-1}+a_{n-1,n}{x}_n& =b_{n-1}⟹x_{n-1}=\frac{b_{n-1}-a_{n-1,n}{x}_n}{a_{n-1,n-1}}& & \Uparrow \\ a_{nn}{x}_n& =b_n⟹x_n=\frac{b_n}{a_{nn}}& & \Uparrow \end{array}$$

where this only works if $a_{ii}\ne 0$ for all $i$

Gauss Elimination (GE)

Let $A=(a_{ij})$ be a matrix

Gaussian Elimination is a systematic way to introduce zeroes into lower triangular part of $A$
by subtracting multiples of previous rows (equations)

Pseudocode

Let $A$ be a $n\times n$ matrix

For columns $j=1,2,\cdots ,n-1$
       For rows $i=j+1,j+2,\cdots ,n$

$$\begin{array}{rl}\text{row }i& \leftarrow \text{row }i-\frac{a_{ij}}{a_{jj}}\cdot \text{row }j\\ b_i& \leftarrow b_i-\frac{a_{ij}}{a_{jj}}\cdot b_j\end{array}$$

       end
end

Note that the diagonal element $a_{jj}$ used to eliminate the rows below is called the pivot

Matrix for Row Operations

Let row operation be

$$\text{row }i\leftarrow \text{row }i+\lambda \cdot \text{row }j$$

Then it can be done by pre-multiplication of a lower triangular matrix

$$\begin{array}{r}M(i,j,\lambda )=I+\left(\begin{array}{ccc}0& 0& 0\\ 0& \lambda & 0\\ 0& 0& 0\end{array}\right)\end{array}$$

where $\lambda$ is at the $(i,j)$th position in the matrix
with $\lambda$ known as the multipliers

Note that consecutive row operations use data resulting from previous transformations

Inverse of Matrix for Row Operations

If $i\ne j$ then

$$(M(i,j,\lambda ){)}^{-1}=M(i,j,-\lambda )$$

Lower Upper Decomposition of a Square Matrix

Let $A$ be a $n\times n$ matrix then

$$A=LU$$

where

$U$ is upper triangular
$L$ is unit lower triangular (ones on diagonal)

Solving Linear Systems via Lower Upper Decomposition

Let System be

$$Ax=b$$

1. Factorise $A=LU$ where $L$ is unit lower triangular and $U$ is upper triangular
2. Solve $Ly=b$ using Forward Substitution
3. Solve $Ux=y$ using Backward Substitution
4. Hence $x$ solves $Ax=b$

Pivoting Gaussian Elimination or Lower Upper Decomposition

Let $A=(a_{ij})$

If there exists pivot $a_{ii}=0$ for some $i$ then

Reorder rows (equations) to ensure $a_{ii}\ne 0$ for all $i$

Partial Pivoting

Let $A=(a_{ij})$

For creating zeros in $j$th column
Find $k$ where

$$|a_{kj}|=\max (|a_{jj}|,|a_{j+1},j|,\cdots ,|a_{n,j}|)$$

so $|a_{kj}|$ is the largest value in that column below $a_{jj}$

Then

$$\text{swap rows }j\text{ and }\text{ row }k$$

Partial Pivoting through Permutation

Swapping row $i$ and row $j$ is same as pre-multiplication by

$I$ with rows $i$ and row $j$ swapped known as $P$

Note that $P$ has same rows as $I$