Subsection 4.2.5 Why using the Method of Normal Equations could be bad
ΒΆfit widthHomework 4.2.5.1.
Show that ΞΊ2(AHA)=(ΞΊ2(A))2.
Hint
Solution
Use the SVD of \(A \text{.}\)
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*}
Compute B=AHA.
Compute y=AHb.
Solve BΛx=y.
βΞ΄Λxβ2βΛxβ2β€1cos(ΞΈ)ΞΊ2(A)βΞ΄bβ2βbβ2.
the sensitivity of computing Λx from BΛx=y is captured by
βΞ΄Λxβ2βΛxβ2β€ΞΊ2(A)2βΞ΄yβ2βyβ2.
If ΞΊ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.