Just to throw another bit. Just like Ted was saying. If you take the largest singular value over the smallest singular value, you get your condition number. If it turns out to be 10^16, then you're loosing all the digits of double precision accuracy, meaning that your solver is nothing more than a random number generator.
On Thu, Apr 4, 2013 at 12:21 PM, Dan Filimon <dangeorge.fili...@gmail.com>wrote: > For what it's worth, here's what I remember from my Numerical Analysis > course. > > The thing we were taught to use to figure out whether the matrix is ill > conditioned is the condition number of a matrix (k(A) = norm(A) * > norm(A^-1)). Here's a nice explanation of it [1]. > > Suppose you want to solve Ax = b. How much worse results will you get using > A if you're not really solving Ax = b but A(x + delta) = b + epsilon (x is > still a solution for Ax = b). > So, by perturbing the b vector by epsilon, how much worse is delta going to > be? There's a short proof [1, page 4] but the inequality you get is: > > norm(delta) / norm(x) <= k(A) * norm(epsilon) / norm(b) > > The rule of thumb is that if m = log10(k(A)), you lose m digits of > accuracy. So, equivalently, if m' = log2(k(A)) you lose m' bits of > accuracy. > Since floats are 32bits, you can decide that say, at most 2 bits may be > lost, therefore any k(A) > 4 is not acceptable. > > Anyway there are lots of possible norms and you need to look at ways of > actually interpreting the condition number but from what I learned this is > probably the thing you want to be looking at. > > Good luck! > > [1] http://www.math.ufl.edu/~kees/ConditionNumber.pdf > [2] http://www.rejonesconsulting.com/CS210_lect07.pdf > > > On Thu, Apr 4, 2013 at 5:26 PM, Sean Owen <sro...@gmail.com> wrote: > > > I think that's what I'm saying, yes. Small rows X shouldn't become > > large rows of A -- and similarly small changes in X shouldn't mean > > large changes in A. Not quite the same thing but both are relevant. I > > see that this is just the ratio of largest and smallest singular > > values. Is there established procedure for evaluating the > > ill-conditioned-ness of matrices -- like a principled choice of > > threshold above which you say it's ill-conditioned, based on k, etc.? > > > > On Thu, Apr 4, 2013 at 3:19 PM, Koobas <koo...@gmail.com> wrote: > > > So, the problem is that the kxk matrix is ill-conditioned, or is there > > more > > > to it? > > > > > >
