Past exam of the probability, statistics and options I course of the University of Oxford / 2010 / P (Numerical Analysis)

Eliminate the first column with multipliers ${\ell }_{21}=2$ and ${\ell }_{31}=-1$. The new second and third rows are $(0,2,4)$ and $(0,-1,3)$. The next multiplier is ${\ell }_{32}=-1/2$, giving final row $(0,0,5)$. Recording these multipliers gives the LU decompositionFor an upper-triangular matrix with nonzero diagonal, the back substitution algorithm works from bottom to top:In the separate triangular system printed in the question, $5x_3=10$, $2x_2+4x_3=6$, and $x_1+2x_2+2x_3=3$. Hence

A QR decomposition is $A=QR$, with $Q$ orthogonal and $R$ upper triangular. Orthogonality gives $Q^{\mathsf{T}}Q=I$, and therefore $\Vert Qx{\Vert }^2=x^{\mathsf{T}}{Q}^{\mathsf{T}}Qx=x^{\mathsf{T}}x=\Vert x{\Vert }^2$, proving invariance of the Euclidean norm.

The unshifted QR algorithm starts with $A_0=A$. At step $k$, factor $A_k=Q_k{R}_k$ and set $A_{k+1}=R_k{Q}_k$. ThenThus consecutive matrices are related by orthogonal similarity, so they have the same characteristic polynomial and eigenvalues. Induction proves every iterate has the original eigenvalues. Symmetry is also preserved. When the iteration converges to diagonal form, its diagonal entries are the eigenvalues; practical implementations use shifts and deflation to improve convergence.