Skip to main content

Unit 4.2.5 Why using the Method of Normal Equations could be bad

Homework 4.2.5.1.

Show that \(\kappa_2( A^H A ) = (\kappa_2( A ))^2 \text{.}\)

Hint

Use the SVD of \(A \text{.}\)

Solution

Let \(A = U \Sigma V^H\) be the reduced SVD of \(A \text{.}\) Then

\begin{equation*} \begin{array}{rcl} \kappa_2( A^H A ) \amp=\amp \| A^H A \|_2 \| ( A^H A )^{-1} \|_2 \\ \amp=\amp \| ( U \Sigma V^H )^H U \Sigma V^H \|_2 \| ( ( U \Sigma V^H )^H U \Sigma V^H )^{-1} \|_2 \\ \amp=\amp \| V \Sigma^2 V^H \|_2 \| V (\Sigma^{-1})^2 V^H \|_2 \\ \amp=\amp \| \Sigma^2 \|_2 \| (\Sigma^{-1})^2 \|_2 \\ \amp = \amp \frac{\sigma_0^2}{\sigma_{n-1}^2} = \left( \frac{\sigma_0}{\sigma_{n-1}} \right)^2 = \kappa_2( A )^2. \end{array} \end{equation*}

Let \(A \in \Cmxn \) have linearly independent columns. If one uses the Method of Normal Equations to solve the linear least squares problem \(\min_{x} \| b - A x \|_2 \) via the steps

  • Compute \(B = A^H A \text{.}\)

  • Compute \(y = A^H b \text{.}\)

  • Solve \(B \hat x = y \text{.}\)

the condition number of \(B \) equals the square of the condition number of \(A \text{.}\) So, while the sensitivity of the LLS problem is captured by

\begin{equation*} \frac{\| \delta\!\hat x\|_2}{\| \hat x \|_2} \leq \frac{1}{\cos( \theta )} \kappa_2( A ) \frac{\| \delta b \|_2}{\| b \|_2}. \end{equation*}

the sensitivity of computing \(\hat x \) from \(B \hat x = y \) is captured by

\begin{equation*} \frac{\| \delta\!\hat x\|_2}{\| \hat x \|_2} \leq \kappa_2( A )^2 \frac{\| \delta y \|_2}{\| y \|_2}. \end{equation*}

If \(\kappa_2( A ) \) is relatively small (meaning that \(A \) is not close to a matrix with linearly dependent columns), then this may not be a problem. But if the columns of \(A \) are nearly linearly dependent, or high accuracy is desired, alternatives to the Method of Normal Equations should be employed.

Remark 4.2.5.1.

It is important to realize that this squaring of the condition number is an artifact of the chosen algorithm rather than an inherent sensitivity to change of the problem.