1
$\begingroup$

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!

$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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)

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.