Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2007 / A / 2 / a

Direct solution usually uses a pivoted LU decomposition $PA=LU$: solve $Lz=Pb$ by forward substitution, then $Ux=z$ by back substitution. For a symmetric positive-definite matrix, the Cholesky decomposition iswith $C$ lower triangular and positive diagonal. It exploits symmetry, requiring about $n^3/3$ arithmetic operations rather than the leading $2n^3/3$ for general elimination.

If $A$ has full column rank and its reduced QR decomposition is $A=QR$, $Q^{T}Q=I$, thenChoose the signs of $Q,R$ so that $R$ has positive diagonal. Then $R$ is precisely the upper Cholesky factor of the normal-equation matrix $A^{T}A$, or $R^T$ is its lower factor. This identifies the factors; in computation, obtaining $R$ directly by QR decomposition avoids explicitly forming the normal equations, which square the condition number.