2
$\begingroup$

I'm using the Eigensystem function, and I'm trying figure out whether or not it is singular or ill-conditioned. I'm using the function as so:

Eigensystem[A]
LUDecomposition[A]

And it returns a list of eigenvalues and eigenvectors, and the condition number last. How high or low does the condition number have to be for us to deem the corresponding matrix ill-conditioned?

On one matrix, the condition number is $\infty$, I'm sure this is ill-conditioned, but the other numbers are something like 14.555555, and 120.4, etc.

$\endgroup$
  • 2
    $\begingroup$ For solving $Ax=b$, if the relative error in the input $b$ is $e$ and the matrix condition number is $K$, then in the worst case, the relative error in the output $x$ is at most $K\,e$. For the LU decomposition, the norms used is the infinity norm. For double-precision numbers with an error of machine epsilon, a condition number of $K=10^8$ means you expect to lose up to half of the sixteens digits of precision, which is often not that bad. If your input is experimental data with much larger errors of measurement, you cannot tolerate such large condition numbers. It's relative. $\endgroup$ – Michael E2 Mar 12 at 23:06
  • 1
    $\begingroup$ A condition number of infinity means the matrix is not invertible. $\endgroup$ – Michael E2 Mar 12 at 23:06
  • 2
    $\begingroup$ The usual rule of thumb in these cases is that you can lose up to $\log_b \kappa(\mathbf A)$ base-$b$ digits when inverting or using your matrix $\mathbf A$ to solve linear equations. Whether it is a "big" or "small" loss is application-dependent, of course. (See this as well.) $\endgroup$ – J. M. will be back soon Mar 12 at 23:09
  • 1
    $\begingroup$ Conditioning is not necessarily the same between the operations of doing an lu decomposition (for linear solving) vs extracting an eigensystem. $\endgroup$ – Daniel Lichtblau Mar 13 at 14:55
5
$\begingroup$

When LUDecomposition or LinearSolve do not complain about badly conditioned matrix, you may deem the matrix as well-conditioned.

If A is dense, these functions complain only if the estimator for the condition number (the last entry in the list returned by LUDecomposition or LinearSolve[A]["ConditionNumber"]) is larger than 10^10. So a condition number of order 10^2 is no problem at all.

$\endgroup$
  • $\begingroup$ Does a matrix being singular necessarily mean it is ill-conditioned? $\endgroup$ – Jaigus Mar 13 at 1:21
  • $\begingroup$ @Jaigus, yes. ${}$ $\endgroup$ – J. M. will be back soon Mar 13 at 1:51
  • $\begingroup$ Thanks but why exactly? $\endgroup$ – Jaigus Mar 13 at 2:12
  • 1
    $\begingroup$ @Jaigus, before anything else, what do you know about the singular value decomposition? $\endgroup$ – J. M. will be back soon Mar 13 at 2:19
  • 2
    $\begingroup$ @Jaigus For a self-adjoint matrix $A$, the condition number is easy to explain: It is the quotient of the largest absolute eigenvalue (which coincides with the operator norm) and the smallest absolute eigenvalue. If $A$ is not invertible, it has a nontrivial kernel (you can see this by combining dimension theorem and self-adjointness) and thus an "eigenvalue" 0; so if $A$ is not the 0-matrix, it has condition number $\|A\|/0 = \infty$. One can generalize by means of singular value decomposition. More general, the condition number is $\|A\| \| A^{-1}\|$ if $A$ is invertible and $\infty$ else. $\endgroup$ – Henrik Schumacher Mar 13 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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