multiplying rows to get great pivots for numerical $LR$ decomposition of invertible Matrix $A$

Question

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?

Answer 1

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.