Next: , Up: Large Linear Systems   [Index]


38.6.1 Normal Equations Approach

The normal equations approach to the large linear least squares problem described above is popular due to its speed and simplicity. Since the normal equations solution to the problem is given by only the p-by-p matrix X^T X and p-by-1 vector X^T y need to be stored. Using the partition scheme described above, these are given by Since the matrix X^T X is symmetric, only half of it needs to be calculated. Once all of the blocks (X_i,y_i) have been accumulated into the final X^T X and X^T y, the system can be solved with a Cholesky factorization of the X^T X matrix. The normal equations approach is the fastest method for solving the large least squares problem, and is accurate for well-conditioned matricies X. However, for ill-conditioned matrices, as is often the case for large systems, this method suffers from numerical instabilities (see Trefethen and Bau, 1997). The number of operations for this method is O(np^2 + p^3/3).