4
$\begingroup$

I want to better understand ill-conditioning for matrices. Say we're given any matrix $A$, where some elements are $10^6$ in magnitude and some are $10^{-7}$ in magnitude. Does this guarantee that this matrix has a condition number greater than 100? Greater than 1000? Even though we haven't specified which elements of $A$ contain those values?

1 Answers 1

7

I addressed a very similar question on scicomp.SE, but I suppose it's good to have an answer here. The point is that neither the size of the entries nor the size of the determinant is a guarantee that your matrix is well- or ill-conditioned. For that, one would need to look at the matrix's singular values, to use a common criterion. In particular, the 2-norm condition number of a matrix is the largest singular value divided by the tiniest singular value; if the smallest singular value is zero, the matrix is singular, and if the smallest singular value is very tiny relative to the largest singular value, you have ill-conditioning.

For instance, matrices of the form

$$\begin{pmatrix}10^{12}&10^{-12}&\cdots&10^{-12}\\10^{-12}&10^{12}&\ddots&\vdots\\\vdots&\ddots&\ddots&10^{-12}\\10^{-12}&\cdots&10^{-12}&10^{12}\end{pmatrix}$$

($10^{12}$ on the diagonal, and $10^{-12}$ off-diagonal) are well conditioned (the ratio of the largest to the smallest singular value is very nearly equal to $1$), while the family of upper triangular matrices

$$\begin{pmatrix}1&2&\cdots&2\\&1&\ddots&\vdots\\&&\ddots&2\\&&&1\end{pmatrix}$$

studied by Alexander Ostrowski and Jim Wilkinson have a condition number equal to $\cot^2\dfrac{\pi}{4n}$, where $n$ is the size of the matrix.

  • 0
    Interesting. +1. Yet it is not obvious that the columns of the triangular matrix are "nearly linearly dependent". Is that any heuristic argument to explain why the matrix is ill-conditioned?2013-05-29
  • 0
    Nothing immediate comes to mind. I only convinced myself of the ill-conditioning by building linear systems based on these matrices, and observing the loss of accuracy as the dimension was increased.2013-05-29
  • 1
    So there is no way to "casually" look at a matrix and tell that it's the ill-conditioned type? An assignment of mine asks: "Why is the condition number of this matrix so high?" That matrix has a column much bigger than the others, but that doesn't seem to be a valid sign of ill-conditionality per your answer.2015-02-03
  • 0
    @Heisenberg, "no way to "casually" look at a matrix" - nope. You should probably post that matrix you're dealing with, perhaps in a separate question.2015-05-01