Exercise 8

In Partial pivoting, we saw how some linear algebraic computations are sensitive to round off error made by a computer. A singular value decomposition can help us understand when this situation can occur.

For instance, consider the matrices $$A = \begin{bmatrix} 1.0001 & 1 \\ 1 & 1 \\ \end{bmatrix},\hspace{24pt} B = \begin{bmatrix} 1 & 1 \\ 1 & 1 \\ \end{bmatrix}.$$ The entries in these matrices are quite close to one another, but $A$ is invertible while $B$ is not. It seems like $A$ is almost singular. In fact, we can measure how close a matrix is to being singular by forming the condition number, $\sigma_1/\sigma_n$, the ratio of the largest to smallest singular value. If $A$ were singular, the condition number would be undefined because the singular value $\sigma_n=0$. Therefore, we will think of matrices with large condition numbers as being close to singular.

1. Define the matrix $A$ and find a singular value decomposition. What is the condition number of $A$?

2. Define the left singular vectors $\uvec_1$ and $\uvec_2$. Compare the results $A^{-1}\bvec$ when

   1. $\bvec=\uvec_1+\uvec_2$.

   2. $\bvec=2\uvec_1+\uvec_2$.

   Notice how a small change in the vector $\bvec$ leads to a small change in $A^{-1}\bvec$.

3. Now compare the results $A^{-1}\bvec$ when

   1. $\bvec=\uvec_1+\uvec_2$.

   2. $\bvec=\uvec_1+2\uvec_2$.

   Notice now how a small change in $\bvec$ leads to a large change in $A^{-1}\bvec$.

4. Previously, we saw that, if we write $\xvec$ in terms of left singular vectors $\xvec=c_1\vvec_1+c_2\vvec_2$, then we have $$\bvec=A\xvec = c_1\sigma_1\uvec_1 + c_2\sigma_2\uvec_2.$$ If we write $\bvec=d_1\uvec_1+d_2\uvec_2$, explain why $A^{-1}\bvec$ is sensitive to small changes in $d_2$.

Generally speaking, a square matrix $A$ with a large condition number will demonstrate this type of behavior so that the computation of $A^{-1}$ is likely to be affected by round off error. We call such a matrix ill-conditioned.