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

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

Since every $u_{jj}>0$, the diagonal matrix $D$ is invertible. SetThe division is by the diagonal entry of row $i$. Thus $\hat{U}$ is an upper triangular matrix with diagonal entries one and $A=LD\hat{U}$.

To use symmetry without assuming the conclusion, multiply by the matrix inverse of $L$ and its transpose:The matrix $M$ is symmetric because $A$ is a symmetric matrix. It is also an upper triangular matrix, since every factor on the right is an upper triangular matrix. A symmetric upper triangular matrix is diagonal. Its diagonal is exactly $D$, because $\hat{U}$ and $L^{-T}$ have diagonal entries one. Hence $M=D$, givingThis is the LDL decomposition.

Take the positive square roots of the diagonal entries:The matrix $\hat{L}$ is a lower triangular matrix with positive diagonal, andThis is a Cholesky decomposition. For a nonzero vector $x$, the vector ${\hat{L}}^{T}x$ is nonzero because ${\hat{L}}^T$ is invertible. ThereforeHere $\Vert \cdot {\Vert }_2$ is the Euclidean norm. Thus $A$ is a positive-definite matrix.

For a real square matrix, a QR factorization writes $B=QR$ with $Q$ an orthogonal matrix, $Q^{T}Q=I$, and $R$ an upper triangular matrix. If $B$ is invertible, so is $R$, andCompute $Q^{T}b$ and use back substitution; no matrix inverse needs to be formed.

Apply the Gram-Schmidt process to the columns $b_1,b_2,b_3$. The first column has Euclidean norm two, giving $q_1=(1,0,0{)}^T$ and $r_{11}=2$. For the second column,For the third column,This residual already has Euclidean norm one. Set $q_3=(0,-3/5,4/5{)}^T$ and $r_{33}=1$. ThusThe columns of $Q$ are orthonormal, and matrix multiplication verifies $QR=B$.

Using precisely this QR factorization, transform the right-hand side:Back substitution in $Rx=Q^{T}b$ givesTherefore