Computing the matrix condition number: forward stability necessary?

Question

Let's say the algorithm Alg1 to compute the condition number of a matrix uses an algorithm Alg2 for computing SVD. The algorithm Alg2 is backward stable. If I apply the algorithm Alg1 on an ill-conditioned matrix would it return the correct condition number? It does not make sense to me that it would...

I would expect the algorithm is FORWARD stable in order for this to happen. Am I right or am I missing something?

Answer 1

Standard SVD algorithms are backward stable in the sense that the estimates $\hat{\sigma}_i$ of the singular values $\sigma_1\geq\ldots\geq\sigma_n>0$ of an $n\times n$ matrix $A$ are such that $$ |\sigma_i-\hat{\sigma}_i|\leq c\epsilon \sigma_1 $$ for some "moderate" constant $c$ depending on the dimensions of the matrix and $\epsilon$ is the machine precision (in other words, there's an $\hat{A}$ such that $\|A-\hat{A}\|_2\leq c\epsilon$ with singular values $\hat{\sigma}_i$). Consequently, $$ \sigma_i-c\epsilon\sigma_1\leq\hat{\sigma}_i\leq\sigma_i+c\epsilon\sigma_1. $$

Now let's see what happens when you plug these estimates to the formula for the spectral condition number. Let's also assume that $A$ is not too ill-conditioned, for example, let $$ c\epsilon\kappa\leq K, \quad \kappa=\frac{\sigma_1}{\sigma_n}, $$ for some $K<1$. We get $$ \hat{\kappa}=\frac{\hat{\sigma}_1}{\hat{\sigma}_n} \leq\frac{(1+c\epsilon)\sigma_1}{\sigma_n-c\epsilon\sigma_1} =\frac{(1+c\epsilon)\kappa}{1-c\epsilon\kappa} \leq\frac{1+c\epsilon}{1-K}\kappa. $$ Similarly, we can get a lower bound which gives $$ \frac{1-c\epsilon}{1+K}\leq\frac{\hat{\kappa}}{\kappa}\leq\frac{1+c\epsilon}{1-K}. $$

So unless your matrix is close to being numerically singular, the computed condition number is still pretty accurate depending on how ill-conditioned the matrix is. If $\hat{\kappa}$ is close to $1/\epsilon\approx 10^{16}$, the matrix is very likely to be numerically singular and the estimate might be garbage.

Answer 2

A backward stable algorithm gives you the right answer to a perturbed problem. If your original problem is ill conditioned, then the solution is sensitive to changes in the input. In particular, the solution of your original problem and the solution of the perturbed problem can be very different. Without additional information, there is no reason to suspect that the computed condition number is a good approximation of the exact condition number.