Partial pivoting

2.5. Partial pivoting#

In most practical applications of row reduction to solve a linear system we use computers to perform the calculations. Computers use floating point numbers to compute arithmetic operations which are not exact and can be prone to rounding errors. Consider the following linear system of equations

\[\begin{split} \begin{pmatrix}0.0001 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix}1 \\ 2 \end{pmatrix}. \end{split}\]

Using Gaussian elimination to solve this system

\[\begin{split} \begin{align*} & \left( \begin{array}{cc|c} 0.0001 & 1 & 1 \\ 1 & 1 & 2 \end{array} \right) \begin{array}{l} \\ R_2 - 1000R_1 \end{array} & \longrightarrow & \left( \begin{array}{cc|c} 0.0001 & 1 & 1 \\ 0 & -9999 & -9998 \end{array} \right) \begin{array}{l} \\ -\frac{1}{9999}R_2 \end{array} \\ \\ \longrightarrow & \left( \begin{array}{cc|c} 0.0001 & 1 & 1 \\ 0 & 1 & 0.9998\dot{9} \end{array} \right). \end{align*} \end{split}\]

So \(x_2 = 0.9998\dot{9}\). If we were to round this to four decimal places then \(x_2 = 1.0000\) and using back substitution we have \(x_1 = (1 - 1) / 0.0001 = 0\). However, checking our solution with the original system we see that this does not satisfy the second equation \(x_1 + x_2 = 2\). The problem is that our first pivot element of 0.0001 was small compared with the value beneath it which produced large values when adding multiples of the pivot row to the other rows.

To overcome this we can perform a row swap so that the pivot element is larger than the value below

\[\begin{split} \begin{align*} & \left(\begin{array}{cc|c} 0.0001 & 1 & 1 \\ 1 & 1 & 2 \end{array} \right) \begin{array}{l} R_1 \leftrightarrow R_2 \\ \phantom{x} \end{array}& \longrightarrow & \left( \begin{array}{cc|c} 1 & 1 & 2 \\ 0.0001 & 1 & 1 \end{array} \right) \begin{array}{l} \\ R_2 - 0.0001 R_1 \end{array} \\ \\ \longrightarrow & \left( \begin{array}{cc|c} 1 & 1 & 2 \\ 0 & 0.9999 & 0.9998 \end{array} \right) \end{align*} \end{split}\]

Solving using back substitution we have \(x_2 = 0.9998 / 0.9999 = 0.9998\dot{9}\) which rounded to four decimal places is \(x_2 = 1.0000\) as before. However, this time using back substitution we now have \(x_1 = 2 - 1.0000 = 1.0000\) which is consistent with the original system. This process is called partial pivoting and it’s where we perform a row swap to ensure that the pivot element has a larger absolute value from the elements in the column beneath the pivot.

Algorithm 2.2 (Gaussian elimination with partial pivoting)

Inputs: An \(m \times n\) matrix \(A\)

Outputs: The matrix \(A\) in row echelon form

Start with the pivot element as the element in the first row and column of \(A\).
For each column of \(A\)
- Perform a row swap with the row beneath the pivot row that has the largest absolute value element in the pivot column which is greater than the absolute value fo the pivot element.
- If the pivot element is zero move to the next column.
- For each row beneath the pivot row
  - Subtract the pivot row multiplied by the value in the pivot column of the row divided by the pivot element from the current row.
Return \(A\)

Example 2.4

Solve the system of linear equations using Gaussian elimination with partial pivoting.

\[\begin{split} \begin{align*} x_1 - x_2 + 3x_3 &= 13, \\ 4x_1 - 2x_2 + x_3 &= 15, \\ -3x_1 - x_2 + 4x_3 &= 8. \end{align*} \end{split}\]