I'm working on my Master's, in the field of computational fluid dynamics, where we have to solve the system $Ax = b$ a lot. As far as I can figure out, if the matrix $A$ is ill-conditioned it is possible that a small residual $r = |Ax-b|$ does not necessarily correspond with an accurate solution to the system.
Is there a "rule of thumb" as to how I can think about an ill-conditioned matrix? From what I can figure out, an ill-conditioned matrix may have large differences (close to machine precision) between some of its entries. Is this correct? And does diagonal dominance have any effects on conditioning?
$\endgroup$ 11 Answer
$\begingroup$When $\det(A)$ has a very small value ($A$ is almost singular), there's a high possibility that you have an ill-conditioned matrix. How small you ask? You need a reference against which the determinant can be measured. The reference here is called the norm of the matrix $\|A \|$.
There are several "popular" norms in the literature: $$\|A \|=\sqrt{\sum_i\sum_ja_{ij}^2} \tag{Euclidean norm}$$ $$\|A \|=\sum_i\sum_j|a_{ij}|$$ $$\|A \|=\max_{i,j}\{a_{ij}\}$$ $$\|A \|=\max_i\sum_{j=1}^{n}|a_{ij}|$$
If you're using MATLAB for example, you can define $\text{cond}(A)=\|A \| \|A^{-1} \|$(condition number). If $\text{cond}(A)$ is close to unity, then the matrix is well conditioned. And as $\text{cond}(A)\rightarrow \infty$ the matrix gets more ill-conditioned. However, for very large matrices, computing the norm is quite expensive, so in most cases, we're content with comparing the determinant with the magnitudes of the elements of the matrix.
Concerning diagonal dominance: to my knowledge, having a diagonally dominant matrix is helpful when you're solving a system using methods like Gauss elimination with scaled row pivoting. However a diagonally dominant matrix is not necessarily well-conditioned.
$\endgroup$ 8
