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.

Improve this question
$\endgroup$
4
  • 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
    Commented Mar 12, 2019 at 23:06
  • 1
    $\begingroup$ A condition number of infinity means the matrix is not invertible. $\endgroup$
    – Michael E2
    Commented Mar 12, 2019 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.'s missing motivation ♦
    Commented Mar 12, 2019 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
    Commented Mar 13, 2019 at 14:55

1 Answer 1

Reset to default
6
$\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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Does a matrix being singular necessarily mean it is ill-conditioned? $\endgroup$
    – Jaigus
    Commented Mar 13, 2019 at 1:21
  • $\begingroup$ @Jaigus, yes. ${}$ $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Mar 13, 2019 at 1:51
  • $\begingroup$ Thanks but why exactly? $\endgroup$
    – Jaigus
    Commented Mar 13, 2019 at 2:12
  • 1
    $\begingroup$ @Jaigus, before anything else, what do you know about the singular value decomposition? $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Mar 13, 2019 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
    Commented Mar 13, 2019 at 8:36

Your Answer

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

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