Past exam of the numerical analysis course of the University of Oxford / 2017 / 2 / a / Solution

Gaussian elimination uses elementary row operations to remove entries below successive pivot elements, reducing a linear system to one with an upper triangular matrix. Back substitution then solves that system. It also computes a reusable matrix factorization, so additional right-hand sides can be handled by forward substitution and back substitution without repeating the elimination.

For elimination without row exchanges, let $A^{(1)}=A$. At step $k$, provided the pivot element $a_{kk}^{(k)}$ is nonzero, form the elimination multipliersand perform ${\text{row}}_i\leftarrow {\text{row}}_i-m_{ik}{\text{row}}_k$, applying the same operation to the right-hand side. More explicitly the resulting entries satisfy $a_{ij}^{(k+1)}=a_{ij}^{(k)}-m_{ik}{a}_{kj}^{(k)}$ for $i>k$, $j\ge k$.

Let $E_k=I-{\sum }_{i>k}{m}_{ik}{e}_i{e}_k^T$, where $e_i$ are the standard basis vectors. ThenThe matrix $L$ is a unit lower triangular matrix storing the elimination multipliers, while $U$ is an upper triangular matrix:Solving $Ax=b$ becomes $Ly=b$ followed by $Ux=y$. If a required pivot element vanishes, an unpermuted LU decomposition can fail even for an invertible matrix. Row exchanges, typically selected by partial pivoting, instead produce $PA=LU$ with a permutation matrix $P$; then solve $Ly=Pb$, $Ux=y$.