## Subsection4.2.5Why using the Method of Normal Equations could be bad

###### Homework4.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.

###### Remark4.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.