### 2 Partial pivoting

Partial pivoting is a refinement of the Gaussian elimination procedure which helps to prevent the growth of rounding error.

#### 2.1 An example to motivate the idea

Consider the example

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{cc}\hfill 1{0}^{-4}\hfill & \hfill 1\hfill \\ \hfill -1\hfill & \hfill 2\hfill \end{array}\right]\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right].$

First of all let us work out the exact answer to this problem

$\begin{array}{rcll}\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \end{array}\right]& =& {\left[\begin{array}{cc}\hfill 1{0}^{-4}\hfill & \hfill 1\hfill \\ \hfill -1\hfill & \hfill 2\hfill \end{array}\right]}^{-1}\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right]& \text{}\\ & =& \frac{1}{2×1{0}^{-4}+1}\left[\begin{array}{cc}\hfill 2\hfill & \hfill -1\hfill \\ \hfill 1\hfill & \hfill 1{0}^{-4}\hfill \end{array}\right]\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right]& \text{}\\ & =& \frac{1}{2×1{0}^{-4}+1}\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1+1{0}^{-4}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 0.999800...\hfill \\ \hfill 0.999900...\hfill \end{array}\right].\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}& \text{}\end{array}$

Now we compare this exact result with the output from Gaussian elimination. Let us suppose, for sake of argument, that all numbers are rounded to 3 significant figures. Eliminating the one non-zero element below the diagonal, and remembering that we are only dealing with 3 significant figures, we obtain

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{cc}\hfill 1{0}^{-4}\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 1{0}^{4}\hfill \end{array}\right]\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1{0}^{4}\hfill \end{array}\right].$

The bottom equation gives ${x}_{2}=1$ , and the top equation therefore gives ${x}_{1}=0$ . Something has gone seriously wrong, for this value for ${x}_{1}$ is nowhere near the true value 0.9998…found without rounding.The problem has been caused by using a small number ( $1{0}^{-4}$ ) to eliminate a number much larger in magnitude ( $-1$ ) below it.

The general idea with partial pivoting is to try to avoid using a small number to eliminate much larger numbers.

Suppose we swap the rows

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{cc}\hfill -1\hfill & \hfill 2\hfill \\ \hfill 1{0}^{-4}\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right]$

and proceed as normal, still using just 3 significant figures. This time eliminating the non-zero below the diagonal gives

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{cc}\hfill -1\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right]$

which leads to ${x}_{2}=1$ and ${x}_{1}=1$ , which is an excellent approximation to the exact values, given that we are only using 3 significant figures.

#### 2.2 Partial pivoting in general

At each step the aim in Gaussian elimination is to use an element on the diagonal to eliminate all the non-zeros below. In partial pivoting we look at all of these elements (the diagonal and the ones below) and swap the rows (if necessary) so that the element on the diagonal is not very much smaller than the other elements.

##### Key Point 3

Partial Pivoting

This involves scanning a column from the diagonal down. If the diagonal entry is very much smaller than any of the others we swap rows. Then we proceed with Gaussian elimination in the usual way.

In practice on a computer we swap rows to ensure that the diagonal entry is always the largest possible (in magnitude). For calculations we can carry out by hand it is usually only necessary to worry about partial pivoting if a zero crops up in a place which stops Gaussian elimination working. Consider this example

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{cccc}\hfill 1\hfill & \hfill -3\hfill & \hfill 2\hfill & \hfill 1\hfill \\ \hfill 2\hfill & \hfill -6\hfill & \hfill 1\hfill & \hfill 4\hfill \\ \hfill -1\hfill & \hfill 2\hfill & \hfill 3\hfill & \hfill 4\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \\ \hfill {x}_{3}\hfill \\ \hfill {x}_{4}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill -4\hfill \\ \hfill 1\hfill \\ \hfill 12\hfill \\ \hfill 0\hfill \end{array}\right].$

The first step is to use the 1 in the top left corner to eliminate all the non-zeros below it in the augmented matrix

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill -3\hfill & \hfill 2\hfill & \hfill 1\hfill & \hfill -4\hfill \\ \hfill 2\hfill & \hfill -6\hfill & \hfill 1\hfill & \hfill 4\hfill & \hfill 1\hfill \\ \hfill -1\hfill & \hfill 2\hfill & \hfill 3\hfill & \hfill 4\hfill & \hfill 12\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill \end{array}\right]\begin{array}{c}\hfill \\ R2-2×R1\hfill \\ R3+R1\hfill \\ \hfill \\ \hfill \end{array}⇒\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill -3\hfill & \hfill 2\hfill & \hfill 1\hfill & \hfill -4\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -3\hfill & \hfill 2\hfill & \hfill 9\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 5\hfill & \hfill 5\hfill & \hfill 8\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill \end{array}\right].$

What we would like to do now is to use the boxed element to eliminate all the non-zeros below it. But clearly this is impossible. We need to apply partial pivoting. We look down the column starting at the diagonal entry and see that the two possible candidates for the swap are both equal to $-1$ . Either will do so let us swap the second and fourth rows to give

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill -3\hfill & \hfill 2\hfill & \hfill 1\hfill & \hfill -4\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 5\hfill & \hfill 5\hfill & \hfill 8\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -3\hfill & \hfill 2\hfill & \hfill 9\hfill \end{array}\right].$

That was the partial pivoting step. Now we proceed with Gaussian elimination

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill -3\hfill & \hfill 2\hfill & \hfill 1\hfill & \hfill -4\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 5\hfill & \hfill 5\hfill & \hfill 8\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -3\hfill & \hfill 2\hfill & \hfill 9\hfill \end{array}\right]\begin{array}{c}\hfill \\ \hfill \\ R3-R2\hfill \\ \hfill \end{array}⇒\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill -3\hfill & \hfill 2\hfill & \hfill 1\hfill & \hfill -4\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 4\hfill & \hfill 4\hfill & \hfill 8\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -3\hfill & \hfill 2\hfill & \hfill 9\hfill \end{array}\right].$

The arithmetic is simpler if we cancel a factor of 4 out of the third row to give

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill -3\hfill & \hfill 2\hfill & \hfill 1\hfill & \hfill -4\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -3\hfill & \hfill 2\hfill & \hfill 9\hfill \end{array}\right].$

And the elimination phase is completed by removing the $-3$ from the final row as follows

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill -3\hfill & \hfill 2\hfill & \hfill 1\hfill & \hfill -4\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -3\hfill & \hfill 2\hfill & \hfill 9\hfill \end{array}\right]\begin{array}{c}\hfill \\ \hfill \\ \hfill \\ R4+3×R3\hfill \end{array}⇒\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill -3\hfill & \hfill 2\hfill & \hfill 1\hfill & \hfill -4\hfill \\ \hfill 0\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 5\hfill & \hfill 15\hfill \end{array}\right].$

This system is upper triangular so back substitution can be used now to work out that ${x}_{4}=3$ , ${x}_{3}=-1$ , ${x}_{2}=2$ and ${x}_{1}=1$ .

The Task below is a case in which partial pivoting is required.

[For a large system which can be solved by Gauss elimination see Engineering Example 1 on page 62].

Transform the matrix

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 1\hfill & \hfill -2\hfill & \hfill 4\hfill \\ \hfill -3\hfill & \hfill 6\hfill & \hfill -11\hfill \\ \hfill 4\hfill & \hfill 3\hfill & \hfill 5\hfill \end{array}\right]$

into upper triangular form using Gaussian elimination (with partial pivoting when necessary).

The row operations required to eliminate the non-zeros below the diagonal in the first column are

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 1\hfill & \hfill -2\hfill & \hfill 4\hfill \\ \hfill -3\hfill & \hfill 6\hfill & \hfill -11\hfill \\ \hfill 4\hfill & \hfill 3\hfill & \hfill 5\hfill \end{array}\right]\begin{array}{c}\hfill \\ R2+3×R1\hfill \\ R3-4×R1\hfill \end{array}⇒\left[\begin{array}{ccc}\hfill 1\hfill & \hfill -2\hfill & \hfill 4\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 11\hfill & \hfill -11\hfill \end{array}\right]$

which puts a zero on the diagonal. We are forced to use partial pivoting and swapping the second and third rows gives

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 1\hfill & \hfill -2\hfill & \hfill 4\hfill \\ \hfill 0\hfill & \hfill 11\hfill & \hfill -11\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right]$

which is in the required upper triangular form.

##### Key Point 4

When To Use Partial Pivoting

1. When carrying out Gaussian elimination on a computer, we would usually always swap rows so that the element on the diagonal is as large (in magnitude) as possible. This helps stop the growth of rounding error.
2. When doing hand calculations (not involving rounding) there are two reasons we might pivot
1. If the element on the diagonal is zero, we have to swap rows so as to put a non-zero on the diagonal.
2. Sometimes we might swap rows so that there is a “nicer" non-zero number on the diagonal than there would be without pivoting. For example, if the number on the diagonal can be arranged to be a 1 then no awkward fractions will be introduced when we carry out row operations related to Gaussian elimination.
##### Exercises
1. Solve the following system by back substitution $\begin{array}{rcll}{x}_{1}+2{x}_{2}-{x}_{3}& =& 3& \text{}\\ 5{x}_{2}+6{x}_{3}& =& -2& \text{}\\ 7{x}_{3}& =& -14\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}& \text{}\end{array}$
1. Show that the exact solution of the system of equations

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{cc}\hfill 1{0}^{-5}\hfill & \hfill 1\hfill \\ \hfill -2\hfill & \hfill 4\hfill \end{array}\right]\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 2\hfill \\ \hfill 10\hfill \end{array}\right]$  is  $\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill -0.99998\hfill \\ \hfill 2.00001\hfill \end{array}\right]$ .

2. Working to 3 significant figures, and using Gaussian elimination without pivoting, find an approximation to $\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \end{array}\right]$ . Show that the rounding error causes the approximation to ${x}_{1}$ to be a very poor one.
3. Working to 3 significant figures, and using Gaussian elimination with pivoting, find an approximation to $\left[\begin{array}{c}\hfill {x}_{1}\hfill \\ \hfill {x}_{2}\hfill \end{array}\right]$ . Show that the approximation this time is a good one.
2. Carry out row operations (with partial pivoting if necessary) to reduce these matrices to upper triangular form.
1. $\left[\begin{array}{ccc}\hfill 1\hfill & \hfill -2\hfill & \hfill 4\hfill \\ \hfill -4\hfill & \hfill -3\hfill & \hfill -3\hfill \\ \hfill -1\hfill & \hfill 13\hfill & \hfill 1\hfill \end{array}\right]$ ,
2. $\left[\begin{array}{ccc}\hfill 0\hfill & \hfill -1\hfill & \hfill 2\hfill \\ \hfill 1\hfill & \hfill -4\hfill & \hfill 2\hfill \\ \hfill -2\hfill & \hfill 5\hfill & \hfill -4\hfill \end{array}\right]$ ,
3. $\left[\begin{array}{ccc}\hfill -3\hfill & \hfill 10\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill -3\hfill & \hfill 2\hfill \\ \hfill -2\hfill & \hfill 10\hfill & \hfill -4\hfill \end{array}\right]$ .

(Hint: before tackling (c) you might like to consider point 2(b) in Key Point 4.)

1. From the last equation we see that ${x}_{3}=-2$ . Using this information in the second equation gives us ${x}_{2}=2$ . Finally, the first equation implies that ${x}_{1}=-3$ .
1. The formula ${\left[\begin{array}{cc}\hfill a& \hfill b\\ \hfill c& \hfill d\end{array}\right]}^{-1}=\frac{1}{ad-bc}\left[\begin{array}{cc}\hfill d& \hfill -b\\ \hfill -c& \hfill a\end{array}\right]$ can be used to show that

$\phantom{\rule{2em}{0ex}}{x}_{1}=-\frac{50000}{50001}=-0.99998\phantom{\rule{2em}{0ex}}\text{and}\phantom{\rule{2em}{0ex}}{x}_{2}=\frac{200005}{100002}=2.00001$ as required.

2. Carrying out the elimination without pivoting, and rounding to 3 significant figures we find that ${x}_{2}=2.00$ and that, therefore, ${x}_{1}=0$ . This is a very poor approximation to ${x}_{1}$ .
3. To apply partial pivoting we swap the two rows and then eliminate the bottom left element. Consequently we find that, after rounding the system of equations to 3 significant figures, ${x}_{2}=2.00$ and ${x}_{1}=-1.00$ . These give excellent agreement with the exact answers.
1. The row operations required to eliminate the non-zeros below the diagonal in the first column are as follows

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 1& \hfill -2& \hfill 4\\ \hfill -4& \hfill -3& \hfill -3\\ \hfill -1& \hfill 13& \hfill 1\\ \hfill \end{array}\right]\begin{array}{c}\hfill \\ R2+4×R1\hfill \\ R3+1×R1\hfill \end{array}⇒\left[\begin{array}{ccc}\hfill 1& \hfill -2& \hfill 4\\ \hfill 0& \hfill -11& \hfill 13\\ \hfill 0& \hfill 11& \hfill 5\\ \hfill \end{array}\right]$

Next we use the element in the middle of the matrix to eliminate the value underneath it. This gives

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 1& \hfill -2& \hfill 4\\ \hfill 0& \hfill -11& \hfill 13\\ \hfill 0& \hfill 0& \hfill 18\\ \hfill \end{array}\right]\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}$ which is of the required upper triangular form.

2. We must swap the rows to put a non-zero in the top left position (this is the partial pivoting step). Swapping the first and second rows gives the matrix

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 1& \hfill -4& \hfill 2\\ \hfill 0& \hfill -1& \hfill 2\\ \hfill -2& \hfill 5& \hfill -4\end{array}\right].$

We carry out one row operation to eliminate the non-zero in the bottom left entry as follows

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 1& \hfill -4& \hfill 2\\ \hfill 0& \hfill -1& \hfill 2\\ \hfill -2& \hfill 5& \hfill -4\\ \hfill \end{array}\right]\begin{array}{c}\hfill \\ \hfill \\ R3+2×R1\hfill \end{array}⇒\left[\begin{array}{ccc}\hfill 1& \hfill -4& \hfill 2\\ \hfill 0& \hfill -1& \hfill 2\\ \hfill 0& \hfill -3& \hfill 0\\ \hfill \end{array}\right]$

Next we use the middle element to eliminate the non-zero value underneath it. This gives

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 1& \hfill -4& \hfill 2\\ \hfill 0& \hfill -1& \hfill 2\\ \hfill 0& \hfill 0& \hfill -6\\ \hfill \end{array}\right]\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}$ which is of the required upper triangular form.

3. If we swap the first and second rows of the matrix then we do not have to deal with fractions. Having done this the row operations required to eliminate the non-zeros below the diagonal in the first column are as follows

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 1& \hfill -3& \hfill 2\\ \hfill -3& \hfill 10& \hfill 1\\ \hfill -2& \hfill 10& \hfill -4\\ \hfill \end{array}\right]\begin{array}{c}\hfill \\ R2+3×R1\hfill \\ R3+2×R1\hfill \end{array}⇒\left[\begin{array}{ccc}\hfill 1& \hfill -3& \hfill 2\\ \hfill 0& \hfill 1& \hfill 7\\ \hfill 0& \hfill 4& \hfill 0\\ \hfill \end{array}\right]$

Next we use the element in the middle of the matrix to eliminate the non-zero value underneath it. This gives

$\phantom{\rule{2em}{0ex}}\left[\begin{array}{ccc}\hfill 1& \hfill -3& \hfill 2\\ \hfill 0& \hfill 1& \hfill 7\\ \hfill 0& \hfill 0& \hfill -28\\ \hfill \end{array}\right]\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}$ which is of the required upper triangular form.