Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
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? –  user1551 May 29 '13 at 12:16
    
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. –  J. M. May 29 '13 at 13:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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