Math 6610 • Analysis of Numerical Methods I

{Sensitivity of Solution of Linear System}
Suppose that \(A\) is a real non-singular \(n\times n\) matrix. Consider the family of
linear systems \(Ax(\epsilon)=b+\epsilon c\), where \(b\) and \(c\) are given nonzero
vectors in \(\R^n\), and \(\epsilon\) is a real parameter. Let \(x=x(0)\) be the solution
for \(\epsilon=0\). Let \(\lVert\cdot\rVert_2\) denote the Euclidean vector norm.

\textbf{a)} Show that
\[
  \frac{\lVert x(\epsilon)-x\rVert_2}{\lVert x\rVert_2}
  \le
  \lVert A\rVert_2\lVert A^{-1}\rVert_2
  \frac{\lVert\epsilon c\rVert_2}{\lVert b\rVert_2}.
\]
The expression \(\lVert A\rVert_2\lVert A^{-1}\rVert_2\) is the condition number of
\(A\). Interpret the above inequality and explain its significance?

\textbf{b)} What is the Singular Value Decomposition (SVD) of \(A\)? Express the
condition number above in terms of \(A\)'s singular values.

\textbf{c)} When the condition number is very large, the matrix is called
ill-conditioned. Sometimes people say that an ill-conditioned matrix is
`nearly-singular'. Make this precise by expressing the (relative) distance between
\(A\) and the nearest singular matrix to \(A\) in terms of the condition number of \(A\).