.. _condSVD:
.. _condition-number:

Condition Number
================

.. index:: rcond

As described in :ref:`conditionNum`, the problem with a poorly
conditioned matrix equation is sensitivity to perturbations of the
elements of :math:`\bm{b}`. Viewing the solution to
:math:`\mathbf{A}\,\bm{x} = \bm{b}` from the perspective of the outer
product of the SVD gives us an intuition into the sensitivity of
:math:`\bm{x}` to perturbations in :math:`\bm{b}` [GOLUB13]_.

.. math::

   \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}

The scalar fractions :math:`\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
:math:`\mathbf{A}\,\bm{x} = \bm{b}` problem. 
A small change to the values in :math:`\bm{b}` will change :math:`\bm{x}` 
significantly if :math:`\mathbf{A}` has a singular value close to zero.

The condition number is defined by equation :eq:`eq-conNum` in
:ref:`conditionNum` as a product of matrix norms.

.. math::

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

From :ref:`mat2norm`, we learn that the :math:`\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 :eq:`eq-eigInv` in :ref:`eigProperties`. So the
:math:`\norm{\cdot}_2` condition number of a matrix is the ratio of the
largest and smallest singular values.

.. math:: \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.

.. index:: condition number
.. index:: invertible test