1

The condition number of a nonsingular matrix $A$ is defined as $$ \kappa(A) = \mbox{cond}(A) = \Vert A \Vert \Vert A^{-1} \Vert \tag{1} $$ and its value is dependent on the choice of the norm in (1).

However, as all $p$-norms are equivalent in a finite-dimensional space, if a matrix $A$ is ill-conditioned in any $p$-norm, it will continue to be ill-conditioned in other $p$-norms also, where $p = 1, 2, \ldots..$ In fact, I also saw some results giving equivalence of $\Vert \cdot \Vert_1$ and $\Vert \cdot \Vert_\infty$ with some bounds.

My query is on numerical linear algebra, where I saw some results giving an estimate for $$ {1 \over \kappa(A)} $$ rather than $\kappa(A)$.

As we use ill-conditioned matrices (like Hilbert's matrix) for test matrices, $\kappa(A)$ will be quite large. Is my reasoning correct that numerical estimates are given for ${1 \over \kappa(A)}$ rather than $\kappa(A)$ as ${1 \over \kappa(A)}$ (reciprocals) will be closer to zero for an ill-conditioned matrix $A$, while $\kappa(A)$ can get quite large. This helps the accuracy of the numerical estimate.

I checked the available commands in MATLAB and I find that MATLAB uses "rcond(A)" for the reciprocal of condition number of a matrix $A$ using $1$-norm. As MATLAB does not give the paper used for finding this estimate, I like to know why specially $1$-norm is used in this estimate, as the default value of "cond(A)" in MATLAB uses the spectral norm or the $2$-norm. [In MATLAB, if the value of "rcond(A)" is closer to zero, it indicates that $A$ is very close to a singular matrix, while if the value of "rcond(A)" is closer to one, it indicates that $A$ is well-conditioned.]

Your comments are welcome!

Dr. Sundar
  • 2,677

2 Answers2

0

William W. Hager (1984) developed an algorithm for 1-norm condition number estimator, and his algorithm essentially gives an estimate for $\Vert A^{-1} \Vert_1$ from which $\kappa_1(A)$ can be directly computed. This is a direct method for finding $\kappa_1(A)$ and it does not proceed like finding the reciprocal of $\kappa_1(A)$.

References:

  1. Hager WW (1984) Condition estimates. SIAM J Sci Stat Comput 5(2):311–316

  2. Hager WW (1998) Applied numerical linear algebra. Prentice Hall, New Jersey

Dr. Sundar
  • 2,677
0

If $y$ is any non-zero vector in $\mathbb{R}^n$, then

$$ A z = y $$ yields $$ z = A^{-1} \ y $$ which shows that $$ \Vert z \Vert = \Vert A^{-1} \ y \Vert \leq \Vert A^{-1} \Vert \Vert y \Vert $$

Thus, $$ \Vert A^{-1} \Vert \geq {\Vert z \Vert \over \Vert y \Vert}, \ \ \mbox{where} \ \ y \neq 0. \tag{1} $$

For an ill-conditioned matrix $A$, which is usually taken as a test matrix for estimating $\kappa(A)$, $\Vert A^{-1} \Vert$ will be very large.

If we choose a $y$ such that $$ {\Vert z \Vert \over \Vert y \Vert} \tag{2} $$ is large, than we may get a reasonably good estimate for $$ \Vert A^{-1} \Vert $$ (using the bound given in (1)).

This is the basic idea for the condition number estimatator given in the classical paper:

"An Estimate for the Condition Number of a Matrix" (1979)

A. K. Cline, C. B. Moler, G. W. Stewart and J. H. Wilkinson

(SIAM Journal on Numerical Analysis)

To avoid overflow, the LINPACK condition number estimator computes an estimate for the reciprocal of $\kappa(A)$, namely $$ RCOND = {\Vert y \Vert \over \Vert A \Vert \Vert z \Vert} $$

Cline's paper in SIAM J. Numerical Analysis (1979)

Dr. Sundar
  • 2,677