14
$\begingroup$

Suppose we have a linear system and we know nothing about its conditioning and have no preliminary information about the solution. We blindly apply Gaussian elimination and obtain some solution $x$. Is it possible to determine whether this solution is trustworthy (i.e. that the system is well-conditioned) without thorough preliminary analysis of the matrix? Does the magnitude of pivots give reliable information?

And generally, what are the main guidelines for detecting ill-conditioning "on the fly"?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
13
$\begingroup$

When is a matrix ill conditioned? It depends on the accuracy of the solution you are looking for, as much as "beauty is in the eye of the beholder"...

May be your question should better rephrased as are there cheap and robust condition number estimators based on the $LU$ factorization?

Assuming you are interested in the real general (dense, non symmetric) problem in double precision arithmetic I would suggest you to use LAPACK expert solver DGESVX which provides a condition estimate in the form of its reciprocal, $\text{RCOND}\approx 1/\kappa(A)$. As a bonus you have also other goodies like equation equilibration/balancing, iterative refinement, forward and backward error bounds. By the way, pathological ill conditioning ($\kappa(A) > 1/\epsilon$) is signaled as an error by INFO>0.

Going into more detail, LAPACK estimates the condition number in the 1-norm (or $\infty$-norm if you are solving $A^T x = b$) via DGECON. The underlying algorithm is described in lawn 36: "Robust Triangular Solves for Use in Condition Estimation".

I have to confess that I'm not an expert in the area, but my philosophy is: "if it is good enough for LAPACK, it is for me".

Improve this answer
$\endgroup$
8
$\begingroup$

The solution of an ill-conditioned system of equations with a matrix of norm 1 a random right hand side of norm 1 will have with high probability a norm of the order of the condition number. Thus computing a few such solutions will tell you what is going on.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is indeed what DGECON is doing, with the added finesse of iteratively refining the search direction in order to maximize the result, and using a custom triangular solver (not the BLAS ones) in order not to have things skewed up by approximation errors. The computational cost of DGECON is therefore comparable to your simple test. +1 for remembering us of the simple meaning of matrix norms and condition number. It should be interesting to find out if DGECON is really more robust of a simple random check. $\endgroup$
    – Stefano M
    Oct 15, 2012 at 10:19
  • $\begingroup$ Taking into account that the condition number of solving $Ax=b$ coincides with the condition number of computing $Ax$ does it suffice just to multiply the scaled matrix with those random vectors instead of actual solving $Ax=b$? $\endgroup$
    – faleichik
    Oct 15, 2012 at 16:21
  • 2
    $\begingroup$ @faleichik For sure no: the trick here is to scale $A$ so that $\| A \| = 1$ and $\kappa(A) = \| A \| \cdot \| A^{-1} \| = \| A^{-1} \|$. Of course, being this linear algebra, you do not have to actually scale $A$ but only $Ax$ ... nevertheless you need to first compute $\| A \|$. Your reverse argument would require to first compute $\| A^{-1} \|$ which what we are striving to evaluate. $\endgroup$
    – Stefano M
    Oct 15, 2012 at 16:38
5
$\begingroup$

It is nearly impossible to to tell if the your system is ill conditioned from just one result. Unless you have some foresight into the behavior of your system (i.e. know what the solution SHOULD be), there's not much you can say from a single solution.

Having said this, you can gain more information if you solve more than one system with the same $A$. Suppose you have a system of the form $Ax=b$. For a specific A which you have no prior knowledge about its conditioning, you can perform the following test:

  1. Solve $Ax=b$ for a specific right hand side vector $b$.
  2. Perturb your right hand side vector by $b_{new}=b+\mathbf{\varepsilon}$ where $||\mathbf{\epsilon}||$ is very small in comparison to $||b||$.
  3. Solve $Ax_{new}=b_{new}$.
  4. If your system is well-conditioned, your new solution should be fairly close to your old solution (i.e. $||x-x_{new}||$ should be small). If you observe a dramatic change to your new solution (i.e. $||x-x_{new}||$ is large), then your system is probably ill-conditioned.

You may need to solve several linear systems with different right hand side vectors to give you a better indication of whether the system is ill-conditioned. Of course, this process is a bit expensive ($\Theta(n^3)$operations for the first solution and $\Theta(n^2)$ operations for each successive solution, assuming your direct solver saves its factors). If your matrix A is fairly small, this is not a problem. If it is large, you may not want to do this. Instead, you may be better off calculating the condition number $||A||\cdot||A^{-1}||$ in a convenient norm.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ Your $\Theta(kn^3)$ claim is extremely far from the truth. Even if $A$ is dense, $A$ can be factored once with $O(n^3)$ work and then each solve requires only $O(n^2)$ work. $\endgroup$
    – Jack Poulson
    Oct 13, 2012 at 18:53
  • $\begingroup$ @JackPoulson: You're absolutely right... I guess I completely spaced out about it. No worries:) I'll update my answer $\endgroup$
    – Paul
    Oct 13, 2012 at 19:47
  • $\begingroup$ Could one also evaluate the residual of the resulting solve? Since $$||Ax - b ||$$ scales as $$||A||\cdot||x||$$ a nearly singular $A$ might give a meaningful residual even if its solution is very bad. $\endgroup$
    – Reid.Atcheson
    Oct 13, 2012 at 20:05
  • $\begingroup$ @Reid.Atcheson: Not really. The approximate solution to an ill conditioned system can still produce a small residual. This does not really doesn't give you any indication as to how far away it is from the true solution. $\endgroup$
    – Paul
    Oct 13, 2012 at 23:02
  • 1
    $\begingroup$ May be it is more wise to explicitly state $\|\varepsilon\|$ very small with respect to $\|b\|$. Everything is relative in this area... Most readers will know, but someone could be mislead in dangerous waters. $\endgroup$
    – Stefano M
    Oct 14, 2012 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.