3
$\begingroup$

in the equation of A*q=b, A is a NxN matrix in which the numbers can be up to 10^56 and the minimum is 1. the condition number of the matrix can be as large as 3.16e+064.

The SVD, QR and LUP have been used to deal with the matrix.

however, when computing using matlab, there are still warnings such as 'Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.164458e-065. '

why?

$\endgroup$

3 Answers 3

12
$\begingroup$

Simply put, the range of the values in your matrix span many, many orders of magnitude.

In double-precision arithmetic, we can only add numbers together that are within about 16 orders of magnitude of each other, otherwise the smaller number is "too small" and gets lost in the noise.

Many algorithms such as QR and SVD will run happily along with a matrix such as yours, but the results might be inaccurate. Let's just use a simple example to see what might happen.

Let $A = \begin{pmatrix} 5\times 10^{60} & 14 \\ 5\times 10^{60} & 140\end{pmatrix}$.

Obviously this matrix is non-singular. But what happens when we compute the inverse? Recall that the inverse would be:

$$A^{-1} = \frac{1}{\left(5\times 10^{60}\right)\cdot 140-14\cdot\left(5\times 10^{60}\right)}\begin{pmatrix} 140 & -14 \\ -5\times 10^{60} & 5\times 10^{60}\end{pmatrix}.$$

The denominator in the factor is very large, about $6.3\times 10^{62}$. Now, when you multiply that through, you get

$$A^{-1} = \begin{pmatrix} \frac{140}{6.3\times 10^{62}} & -\frac{14}{6.3\times 10^{62}} \\ -\frac{5\times 10^{60}}{6.3\times 10^{62}} & \frac{5\times 10^{60}}{6.3\times 10^{62}}\end{pmatrix}.$$

The numbers in the bottom row are equal to about $0.00794$. The numbers in the top row are practically zero.

So when you compute $A^{-1}A$, what you get is an issue of finite storage. The (1,1) element of $A^{-1}$ is tiny, and the (1,1) element of $A$ is huge. The computer can't store them both when it tries to compute them, so it rounds the tiny one down to zero.

So when you (naively) multiply $A^{-1}A$ on the computer, you end up getting:

$$A^{-1}A = \begin{pmatrix} 0 & 0 \\ 0 & 1\end{pmatrix}.$$

Now, if you actually punch these into MATLAB, you'll get the right answer. But that's because MATLAB has many built-in utilities for handling these scenarios. However, these utilities do not universally work on every algorithm, and the larger your matrix and the more complicated the algorithm, the less likely we are to be able to take shortcuts to avoid precision issues.

MATLAB checks this by computing the reciprocal of the condition number, aka RCOND. Usually, if RCOND is very small, you have a badly scaled matrix, and you should not trust your results, because some quirky hacks went into trying to deal with those scaling issues, and because those hacks were used, the quality of your results is not to be guaranteed.

$\endgroup$
2
  • $\begingroup$ Thanks for your detailed answer. $\endgroup$
    – wwsui
    May 14, 2014 at 8:15
  • $\begingroup$ Now, is there better solutions for such problem if I don't use those decomposition method? $\endgroup$
    – wwsui
    May 14, 2014 at 8:29
0
$\begingroup$

Results become inaccurate because the computation is highly instable: there are many products of very big or very small numbers (according to the fact that you treat numbers like 1.56), and you end up with 'not a number' (NaN). this because matlab uses finite arithmetics (to make it simple, a finite number of digits) and not exact arithmetic.

a solution is to use scaling or a matrix preconditioner.

$\endgroup$
3
  • $\begingroup$ There are 1e20, 1e21, ...,1e63 in the same column. So, when I had the scaling applied, extremely little numbers came into been. Whether this can be solved using a matrix preconditioner? $\endgroup$
    – wwsui
    May 14, 2014 at 11:32
  • $\begingroup$ you should look for the properties of your matrix, for example if it is symmetric, hermitian or stuff like that, and choose accordingly a preconditioner (there are a lot for specific cases). the effect of the preconditioner is to lower the condition number of the matrix before you apply a linear solver, a conjugated gradient or any other. $\endgroup$
    – Marco
    May 14, 2014 at 11:51
  • $\begingroup$ I am sorry but the login system is not avaliable to me for days. I have bean studying the preconditioner for the ill-conditioned matrix. I will continue having a try and thanks a lot. $\endgroup$
    – wwsui
    May 20, 2014 at 13:41
0
$\begingroup$

This link could be very useful for you: http://www.mathworks.com/moler/chapters.html

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .