Gram method for computing least squares approximate solution.Algorithm 12.1 in the textbook uses the QR factorization to computethe least squares approximate solution xˆ = A†b, where the m × nmatrix A has linearly independent columns. It has a complexity of2mn2 flops. In this exercise we consider an alternative method:First, form the Gram matrix G = AT A and the vector h = AT b; andthen compute xˆ = G?1h (using algorithm 11.2 in the textbook). Whatis the complexity of this method? Compare it to algorithm 12.1.Remark. You might find that the Gram algorithm appears to be a bitfaster than the QR method, but the factor is not large enough tohave any practical significance. The idea is useful in situationswhere G is partially available and can be computed more efficientlythan by multiplying A and its transpose.
