Explaining roundoff error when row reducing matrices

Question

In my linear algebra textbook (in the context of row reducing and obtaining a matrix in echelon or reduced echelon form), there is a numerical note that reads as follows: "A computer program usually selects as a pivot the entry in a column having the largest absolute value. This strategy, called partial pivoting, is used because it reduces roundoff errors in calculations."

That is all it says. It doesn't give an actual explanation of why partial pivoting reduces roundoff error. I was wondering if someone might be able to explain this or give an example.

Answer 1

Consider the following matrix: $$M = \begin{bmatrix} 0.1 & & & & & 1 \\ -1 & 0.1 \\ & -1 & 0.1 \\ && -1 & 0.1 \\ &&& -1 & 0.1 \\ &&&&-1 & 1 \end{bmatrix},$$ where all the blank spaces are also zeros.

If you start doing gaussian elimination without pivoting, the $1$ in the upper right will keep moving down the rows, getting multiplied by $10$ each time, getting very large in the process. The LU factorization becomes, $$M = \begin{bmatrix} 1 \\ -10 & 1 \\ & -10 & 1 \\ && -10 & 1 \\ &&& -10 & 1 \\ &&&& -10 & 1 \\ \end{bmatrix} \begin{bmatrix} 0.1 &&&&& 1\\ & 0.1 &&&& 10\\ && 0.1 &&& 10^2\\ &&& 0.1 && 10^3\\ &&&& 0.1 & 10^4\\ &&&&& 10^5 + 1 \end{bmatrix}$$

Now, let's say your computer has floating point accuracy $10^{-5}$, so that the last entry $10^5+1$ gets rounded to $10^5$. After making this roundoff, if we multiply the matrices together again we get, $$\begin{bmatrix} 1 \\ -10 & 1 \\ & -10 & 1 \\ && -10 & 1 \\ &&& -10 & 1 \\ &&&& -10 & 1 \\ \end{bmatrix} \begin{bmatrix} 0.1 &&&&& 1\\ & 0.1 &&&& 10\\ && 0.1 &&& 10^2\\ &&& 0.1 && 10^3\\ &&&& 0.1 & 10^4\\ &&&&& 10^5 \end{bmatrix} = \begin{bmatrix} 0.1 & & & & & 1 \\ -1 & 0.1 \\ & -1 & 0.1 \\ && -1 & 0.1 \\ &&& -1 & 0.1 \\ &&&&-1 & 0 \end{bmatrix}$$ Note the difference from the original $M$ - the lower right entry got changed from a $1$ to a $0$. Whoops!

As an exercise, try performing gaussian elimination on this matrix with pivoting (things will come out much more nicely).

---

Note: in reality, floating point precision is around $10^{-8}$ for floats and $10^{-16}$ for doubles respectively.

Answer 2

Here is an example. Assume two-digit rounding arithmetic. $$\begin{cases} 0.0001x &+y &=3 \quad (1)\\ x &+2y&=5\quad (2a)\end{cases}$$

One step Gaussian elimination gives: $$\begin{cases} 0.0001x &+y &= 3\\ &-9998y &=-29995\end{cases}$$

After rounding: $$\begin{cases} 0.0001x &+y &=3\\ &-10000y &=-30000\quad (2b)\end{cases}$$

The solution is $(0,3)$ after rounding, but the true solution is $(-1.0002,3.0001)$. The reason can be easily explained in this 2D case using geometry. You can see the equation (1) never changes when doing Gaussian elimination, while equation (2a) is changed to (2b), a horizontal line. If equation (1) is close to horizontal, the two lines become almost parallel, which causes error easily.

The idea of pivoting is then to make the first equation far away from horizontal, with diagonal element larger.

This is the example with pivoting: $$\begin{cases} x &+2y &=5\\ 0.0001x &+y &=3\end{cases}$$

This would give you a close solution.

Answer 3

I want to add another perspective to the existing excellent answers as it helped me. In a sense, I am building on the answer by @KittyL. It is clear that the following system cannot be solved using naive Gaussian elimination

\begin{align} \begin{cases} 0x &+ y &= 3\\ x &+ 2y &= 5 \end{cases}\,. \end{align}

For larger and larger values of n, the following system of equations would start looking more and more like the previous system of equations.

\begin{align} \begin{cases} 10^{-n}x &+ y &= 3\\ x &+ 2y &= 5 \end{cases}\,. \end{align}

Thus, you should expect that naive Gaussian elimination will start getting ineffective for large values of n - the exact value depends on the number of significant digits used. In other words, if we round off, that is assume $10^{-n}$ is equal to $0$, then the two systems of equations become identical.

Hope my thoughts are correct and are helpful. I would be happy to hear if there are any doubts or corrections.