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.

When calculating the $LR$ decomposition of an invertible Matrix $A$ with the numerical Gauss algorithm there can happen to be inaccuracies caused by the computers precision.

An example is

$\begin{split} 10^{-4} x_1 + 1 x_2 = 1 \\ x_1 + x_2 = 2 \end{split}$

using precision $10^-3$. Which yields to $(x_1,x_2)=(0,1)$ for $10^{-4}$ being the first pivot or to $(x_1,x_2) = (1,1)$ when choosing the pivot to be in the second row.

That's why pivoting is important. We concluded that you should always take the maximum element in the current column as pivot.

Okay, but then I got confused. There's written that it's even better if you first kind of normalize the rows by multiplying the $i$-th row with $\left( \sum_{l=1}^n | a_{ij} | \right)^{-1}$ before deciding on the pivot. But why? And I wondered why we don't just multiply the current row so that the pivot is the largest in that column?

So for our example

$\begin{split} x_1 + 10^{4} x_2 &= 10^4 \\ x_1 + x_2 &= 2 \end{split}$

Doesn't this yield to $(x_1,x_2) = (1,1)$ as expected even when using $10^{-3}$ precision and using the first rows element as pivot?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Your question here boils down to questioning the difference between this (using the ill advised small pivot) $$ \pmatrix{10^{-4} & 1 & 1 \\ 1 & 1 & 2} \overset{R_2 \leftarrow R_2 -10^4R_1}{\longrightarrow} \pmatrix{10^{-4} & 1 & 1 \\ 0 & -10^4 & -10^4}\overset{R_1 \leftarrow 10^4R_1}{\longrightarrow} \pmatrix{1 & 10^4 & 10^4 \\ 0 & -10^4 & -10^4}$$ and this (scaling then still using the ill advised small pivot) $$ \pmatrix{10^{-4} & 1 & 1\\ 1 & 1 & 2}\overset{R_1 \leftarrow 10^4 R_1 }{\longrightarrow} \pmatrix{1 & 10^4 & 10^4 \\ 1 & 1 & 2}\overset{R_2 \leftarrow R_2 -R_1}{\longrightarrow} \pmatrix{1 & 10^4 & 10^4 \\ 0 & -10^4 & -10^4}$$

You may see that there is loss of precision in both. (There are only three digits of precision, so $2-10^4=2-10000 =-9998= -09.998\cdot 10^3 =-10.00\cdot10^{-3}= -10^4$)

The order of the operations did nothing to help the precision, as the combination of the two rows still mixed large values with small values, causing the small values to get truncated out completely in (the rounding into) the precision. Both ways produce the same results, both ways use the ill-advised pivot. Scaling a row does not change the mismatched proportions.

Now try the other pivot

$$ \pmatrix{10^{-4} & 1 & 1\\ 1 & 1 & 2}\overset{R_1 \leftarrow R_1 -10^{-4}R_2}{\longrightarrow}\pmatrix{0 & 1 & 1\\ 1 & 1 & 2}\overset{R_1 \leftrightarrow R_2}{\longrightarrow} \pmatrix{1 & 1 & 2\\ 0 & 1 & 1}$$

You can see now the difference between the two after completing the reduction $$ \pmatrix{1 & 0 & 0\\ 0 & 1 & 1}\quad\text{vs.}\quad \pmatrix{1 & 0 & 1\\ 0 & 1 & 1}$$ The first matrix completely lost the value $1$ in the top right, where the second (the one resulting from the better pivoting) did not.

It is not about the absolute size of a pivot.

share|improve this answer
    
Thank you a lot! I think my problem boiled down to the misunderstanding of three digits of precision. Some good short explanations for that? –  fritz Jan 30 '13 at 19:15
    
Not so much (short explanation). Just remember that the addition of two numbers lose precision when they differ in scale; $1.000 + 1.000\cdot 10^4 =( 0.0001 + 1.000)\cdot 10^4 $ and the smaller number ends up being treated as zero. –  adam W Jan 30 '13 at 20:01

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.