# When is a matrix ill-conditioned?

167 views (last 30 days)
Eric Schols on 3 Feb 2016
Edited: John D'Errico on 3 Feb 2016
For what value of cond(A) becomes the matrix A ill-conditioned? Is it 1e16? I had that value in my head, but can't find any site/post/etc. that confirms it.

John D'Errico on 3 Feb 2016
Edited: John D'Errico on 3 Feb 2016
That is a rough number. A matrix does not suddenly become ill-conditioned, falling off the edge of the world. Ill-conditioning is an entire spectrum, going from good to bad to worse.
The condition number tells you how much solving a linear system will magnify any noise in your data. Think of it as a measure of amplification, a gain.
So if your condition number is 1e8, then when you solve a linear system, that solution will magnify noise by roughly a factor of 1e8. This might not be a problem if your data is in double precision, and your noise level is down in the least significant bits of the data. But if your data comes from real world experiments, then your noise might be on the order of say 1%. If you then magnify that noise by a factor of 1e8, then your noise will dominate the solution, even though the matrix problem is still solvable with no warnings issued.
So one should understand that the condition number of a matrix is a relative thing in terms of how bad it is. A solve will not issue warning messages until the condition number goes above some specified threshold. The result will not turn to NaNs until things get really bad. But even for some larger condition numbers, we can still get garbage out if the noise is sufficiently large.
At the other end of the scale, a condition number can never fall below 1. For example, an orthogonal matrix would have a condition number of 1. It will not amplify any noise in your data.
So a condition number that is small is good. The bigger it is, your troubles will get worse as that condition number increases. A condition number of 1e16 is big enough that you can expect garbage for results almost always (at least when working in double precision.)
Edit: I decided an example might be nice. First, I'll create a matrix A that has a variable condition number, that I can control.
Afun = @(delta) [1 1- delta;1 1 + delta];
The above matrix has a condition number that for small delta, has a condition number of approximately 2/delta. For my example, I'll choose a delta of 1e-8.
A = Afun(1.e-8)
A =
1 0.99999999
1 1.00000001
cond(A)
ans =
199999999.137258
Now, lets create a problem where we know the answer. Here, the solution to A*x=b will be [1;3], so I'll choose a vector b from that vector as x.
b = A*[1;3]
b =
3.99999997
4.00000003
Can we recover the vector [1;3] using backslash?
A\b
ans =
0.999999994448885
3.00000000555112
NO! In fact, the result is corrupted by noise. The solve used floating point operations in double precision, in the end, the moderately large condition number amplified any errors in the least significant bits by roughly 2e8.
So now lets try adding in some noise that is a bit larger. Still on the order of 1e-7, but here you can see that it is now completely corrupting the result.
A\(b + randn(size(b))*1.e-7)
ans =
4.94229551969727
-0.942295486579804