02. Gaussian Elimination and LU factorisation

Vandermonde Matrix

Let the pairs of data points be

$$\{(x_k,f_k){\}}_{k=0}^n$$

Let $p_n(x)={\sum }_{i=0}^n{c}_i{x}^i$ then

Coefficients $c_i$ solve linear system of equations

$$\left[\begin{array}{ccccc}1& x_0& x_0^2& \cdots & x_0^n\\ 1& x_1& x_1^2& \cdots & x_1^n\\ ⋮& ⋮& \ddots & \ddots & ⋮\\ 1& x_n& x_n^2& \cdots & x_n^n\end{array}\right]\left[\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_n\end{array}\right]=\left[\begin{array}{c}{f}_0\\ f_1\\ ⋮\\ f_n\end{array}\right]$$

where the matrix is called Vandermonde and is non-singular if $\{x_i\}$ are distinct

Link to original

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

Link to original

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$

Link to original

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$

Link to original

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

Link to original

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

Link to original

Inverse of Matrix for Row Operations

If $i\ne j$ then

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

Link to original

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)

Link to original

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$

Link to original

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$

Link to original

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

Link to original

Stability of Gaussian Elimination with Partial Pivoting

Gaussian Elimination with partial pivoting cannot fail if $A$ is non-singular

Proof

Let $A$ be at the $j$-th stage so

$$A=\left[\begin{array}{cccccccc}{a}_{11}& .& a_{1,j-1}& a_{1j}& .& .& .& a_{1n}\\ 0& .& .& .& .& .& .& .\\ 0& .& a_{j-1,j-1}& a_{j-1,j}& .& .& .& a_{j-1,n}\\ 0& .& 0& a_{jj}& .& .& .& a_{jn}\\ 0& .& 0& .& .& .& .& .\\ 0& .& 0& a_{kj}& .& .& .& a_{kn}\\ 0& .& 0& .& .& .& .& .\\ 0& .& 0& a_{nj}& .& .& .& a_{nm}\end{array}\right]$$

Then

$$\det A=a_{11}{a}_{22}\cdots a_{j-1,j-1}\cdot \det \left[\begin{array}{ccccc}{a}_{jj}& .& .& .& a_{jn}\\ .& .& .& .& .\\ a_{kj}& .& .& .& a_{kn}\\ .& .& .& & .\\ a_{nj}& .& .& .& a_m\end{array}\right]$$

Hence $\det A=0$ if and only if $a_{jj}=\cdots =a_{kj}=\cdots =a_{nj}=0$

Hence pivot $a_{k,j}$ is zero so $A$ is singular
If $A$ is non-singular then all pivots are non-zero

Link to original

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$

Link to original