# P r o j e c t s

N o t e s

## Condition Number

For an nonsingular square matrix A, its condition number is
\begin{align} \text{Cond}(A)= \left|| A \right\| \left|| A^{-1} \right\| = \left( \max_{x \ne 0} \frac{ \left|| Ax \right\| }{ \left|| x \right\| } \right) \left( \min_{x \ne 0} \frac{\left|| Ax \right\|}{\left|| x \right\|} \right)^{-1}. \end{align}
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 A is a scaling matrix which stretches evenly to all the axes. When A stretches espacially more to some axes, the condition number is larger. By convention, text{Cond}(A)=infty if A is singular.

• Euclidean condition number is
\begin{align}  \left|| A \right\|_2 \left|| A^{-1} \right\|_2 = \sqrt{\frac{\lambda_{max}(A^tA)}{\lambda_{min}(A^tA)}} \end{align}
where lambda_max(X) and lamba_min(X) are the maximum and minimum eigenvalues of X. If A is symmetric, then A^tAx=A(lambda x)=lambda^2 x where x and lambda are the eigenvector and eigenvalue of A, so
\begin{align}  \left|| A \right\|_2 \left|| A^{-1} \right\|_2 = \sqrt{\frac{\lambda_{max}(A^tA)}{\lambda_{min}(A^tA)}} = \left| \frac{\lambda_{max}(A)}{\lambda_{min}(A)} \right| \end{align}
• The large the condition number is, the large the amount of distortion of the unit sphere is.

• text{Cond}(A) geq 1 and text{Cond}(I) = 1.
• text{Cond}(gamma A) = text{Cond}(A) where gamma in mathbb{R}.
• text{Cond}(D)=frac{max |d_i|}{min |d_i|} where D is a diagonal matrix and d_i is the i-th element of D.
• The condition number of A tells us about how close to singularity A is. On the other hand, det A is not a good measure. When A is singular, det A=0, but it does not mean that A is close to singularity. For example, det alpha I_n=alpha^n for alpha in mathbb{R}. For |alpha|<1, however, the determinant is close to zero although I_n is perfectly well-conditioned.
• When estimating the condition number, the hardest part would be calculating ||A^{-1}||. Suppose that Az=y and A is nonsingular. Then ||z||=||A^{-1}y||leq ||A^{-1}||||y||, so frac{||z||}{||y||} leq ||A^{-1}||. If a good y is selected which makes frac{||z||}{||y||} large enough, it can approximate to ||A^{-1}||. First of all, it can be found by random. Second, it can be solved by A^ty=c where c is a vector whose elements are 1 or -1 so that c makes y as large as possible. Finally, it can be | frac{\lambda_{max}(A)}{\lambda_{min}(A)} |  in case of estimating Euclidean condition number.

︎Reference

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

emoy.net