5.4. Condition Number

As described in Matrix Condition Number, the problem with a poorly conditioned matrix equation is sensitivity to perturbations of the elements of \(\bm{b}\). Viewing the solution to \(\mathbf{A}\,\bm{x} = \bm{b}\) from the perspective of the outer product of the SVD gives us an intuition into the sensitivity of \(\bm{x}\) to perturbations in \(\bm{b}\) [GOLUB13].

\[\begin{split}\begin{aligned} \bm{x} &= \mathbf{A}^{+}\,\bm{b} = \left(\mathbf{V\,\Sigma}^+\,\mathbf{U}^T\right)\, \bm{b} \\ &= \sum_{i=1}^{n} \frac{\bm{u}_i^T \bm{b}}{\sigma_i}\bm{v}_i \end{aligned}\end{split}\]

The scalar fractions \(\left(\bm{u}_i^T \bm{b}\right)/\sigma_i\) are dot products divided by singular values. Thus, the magnitude of the singular values has a significant impact on the sensitivity of the \(\mathbf{A}\,\bm{x} = \bm{b}\) problem. A small change to the values in \(\bm{b}\) will change \(\bm{x}\) significantly if \(\mathbf{A}\) has a singular value close to zero.

The condition number is defined by equation (2.22) in Matrix Condition Number as a product of matrix norms.

\[\kappa(\mathbf{A}) = \text{cond}(\mathbf{A}) = \norm{\mathbf{A}}_2\norm{\mathbf{A}^{-1}}_2\]

From 2-Norm of a Matrix, we learn that the \(\norm{\cdot}_2\) norm focuses on the ability of a matrix to stretch a vector, and is thus the largest singular value of the matrix. The singular values of a matrix’s inverse are the reciprocals of the matrix’s singular values. Refer to equation (4.4) in Properties of Eigenvalues and Eigenvectors. So the \(\norm{\cdot}_2\) condition number of a matrix is the ratio of the largest and smallest singular values.

\[\kappa(\mathbf{A}) = \frac{\sigma_{max}}{\sigma_{min}}\]

A full rank matrix will have a fairly small condition number. Singular and near-singular matrices will have condition numbers of infinity or very large (several thousand). Thus, the condition number is a metric indicating whether or not the inverse of a matrix can be accurately calculated. To avoid division by zero, linear algebra software often use the reciprocal of the condition number, which for a well-conditioned matrix is near 1, and near 0 for a poorly conditioned matrix.