9.4. Condition Number

As described in Matrix Condition Number, the problem with a poorly conditioned matrix equation is sensitive 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 matrix with singular values close to zero is poorly conditioned.

The condition number is defined by equation (6.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 (8.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 an invertible test. To avoid division by zero, MATLAB uses the reciprocal of the condition number, rcond. If \(\bf{A}\) is well-conditioned, rcond(A) is near 1, and near 0 if \(\bf{A}\) is poorly conditioned.