The normal equations

Prince, E.; Boggs, P. T.

doi:10.1107/97809553602060000609

International
Tables for
Crystallography
Volume C
Mathematical, physical and chemical tables
Edited by E. Prince

pdf | chapter contents | chapter index | related articles

International Tables for Crystallography (2006). Vol. C. ch. 8.1, p. 682

Section 8.1.3.2. The normal equations

E. Prince^a and P. T. Boggs^b

^a NIST Center for Neutron Research, National Institute of Standards and Technology, Gaithersburg, MD 20899, USA, and ^bScientific Computing Division, National Institute of Standards and Technology, Gaithersburg, MD 20899, USA

8.1.3.2. The normal equations

| top | pdf |

Let us now consider the relationship of the QR procedure for solving the linear least-squares problem to the classical method based on the normal equations. The normal equations can be derived by differentiating (8.1.3.2) and equating the result to a null vector. This yields $[{\bi Z}^{T}{\bi Z}{\bf x}={\bi Z}^{T}{\bf y}^{\prime }. \eqno (8.1.3.5)]$ The algorithm is therefore to compute the cross-product matrix, $[{\bi B}={\bi Z}^{T}{\bi Z}]$ , and the right-hand side, d = Z^Ty′, and to solve the resulting system of equations, Bx = d. This is usually accomplished by computing the Cholesky decomposition of B, that is $[{\bi B}={\bi C}^{T}{\bi C}]$ , where C is upper triangular, and then solving the two triangular systems $[{\bi C}^{T}{\bf v}={\bf d}]$ and $[{\bi C}{\bf x}={\bf v}]$ . Because $[{\bi Z}={\bi Q}_{{\bi Z}}{\bi R}]$ , equation (8.1.3.5) becomes $[{\bi R}^{T}{\bi Q}_{{\bi Z}}^{T}{\bi Q}_{{\bi Z}}{\bi R}{\bf x}={\bi R}^{T}{\bi Q}_{{\bi Z}}^{T}{\bf y}^{\prime }, \eqno (8.1.3.6)]$ or $[{\bi R}^{T}{\bi R}{\bf x}={\bi R}^{T}{\bi Q}_{{\bi Z}}^{T}{\bf y}^{\prime }. \eqno (8.1.3.7)]$ It is clear that R is the Cholesky factor of $[{\bi Z}^{T}{\bi Z}]$ , although it is formed in a different way. This procedure requires of order $[(np^{2})/2]$ operations to form the product $[{\bi Z}^{T}{\bi Z}]$ and $[p^{3}/3]$ operations for the Cholesky decomposition. In some situations, the extra time to compute the QR factorization is justified because of greater stability, as will be discussed below. Most other quantities of statistical interest can be computed directly from the QR factorization.

References

International Tables for Crystallography (2006). Vol. C. ch. 8.1, p. 682