Condition Number

For a nonsingular square matrix AA, its condition number is Cond(A)=AA1=(maxx0Axx)(minx0Axx)1\begin{aligned} Cond(A) = \left\| A \right\| \left\| A^{-1} \right\| = \left( \max_{x \not = 0} \frac{\left\| Ax \right\|}{\left\| x \right\|} \right) \left( \min_{x \not = 0} \frac{\left\| Ax \right\|}{\left\| x \right\|} \right)^{-1} \end{aligned}

The condition number of a matrix denotes the ratio of the maximum relative stretching to the maximum relative shrinking to any nonzero vectors. In other words, it measures the amount of distortion of the unit sphere. Therefore, the condition number is not large when AA is a scaling matrix which stretches evenly to all the axes. When AA stretches espacially more to some axes, the condition number is larger. By convention, Cond(A)=Cond(A) = \infty if AA is singular.

  • Euclidean condition number is
A2A12=λmax(AtA)λmin(AtA)\begin{aligned} \left\| A \right\|_2 \left\| A^{-1} \right\|_2 = \sqrt{\frac{\lambda_{\max}(A^t A)}{\lambda_{\min}(A^t A)}} \end{aligned}

where λmax(X)\lambda_{\max}(X) and λmin(X)\lambda_{\min}(X) are the maximum and minimum eigenvalues of XX. If AA symmetric, then AtAx=A(λx)=λ2xA^t Ax = A(\lambda x) = \lambda^2 x where xx and λ\lambda are the eigenvector and eigenvalue of AA, so A2A12=λmax(AtA)λmin(AtA)=λmax(A)λmin(A)\begin{aligned} \left\| A \right\|_2 \left\| A^{-1} \right\|_2 = \sqrt{\frac{\lambda_{\max}(A^t A)}{\lambda_{\min}(A^t A)}} = \left\vert \frac{\lambda_{\max}(A)}{\lambda_{\min}(A)} \right\vert \end{aligned}

The large the condition number is, the large the amount of distortion of the unit sphere is.

PNorms

  • Cond(A)1Cond(A) \ge 1 and Cond(I)=1Cond(I) = 1.
  • Cond(γA)=Cond(A)Cond(\gamma A) = Cond(A) where γR\gamma \in \mathbb{R}.
  • Cond(D)=maxdimindiCond(D) = \frac{\max{\vert d_i \vert}}{\min{\vert d_i \vert}} where DD is a diagonal matrix and did_i is the ii-th element of DD.
  • The condition number AA tells us about how close to singularity AA is. On the other hand, detA\det A is not a good measure. When AA is singular, detA=0\det A = 0, but it does not mean that AA is close to singularity. For example, detαIn=αn\det \alpha I_n = \alpha^n for αR\alpha \in \mathbb{R}. For α<1\vert \alpha \vert < 1, however, the determinant is close to zero although InI_n is perfectly well-conditioned.
  • When estimating the condition number, the hardest part would be calculating A1\left\| A^{-1} \right\|. Suppose that Az=yAz = y and AA is nonsingular. Then z=A1yA1y\left\| z \right\| = \left\| A^{-1} y \right\| \le \left\| A^{-1} \right\| \left\| y \right\|, so zyA1\frac{\left\| z \right\|}{\left\| y \right\|} \le \left\| A^{-1} \right\|. If a good yy is selected which makes zy\frac{\left\| z \right\|}{\left\| y \right\|} large enough, it can approximate to A1\left\| A^{-1} \right\|. First of all, it can be found by random. Second, it can be solved by Aty=cA^t y = c where cc is a vector whose elements are 11 or 1-1 so that cc makes yy as large as possible. Finally, it can be λmax(A)λmin(A)\left\vert \frac{\lambda_{\max}(A)}{\lambda_{\min}(A)} \right\vert in case of estimating Euclidean condition number.

Reference

[1] Michael T. Heath, Scientific Computing: An Introductory Survey. 2nd Edition, McGraw-Hill Higher Education.


© 2022. All rights reserved.