2.6. 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.01 & 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.01 & 1 & 1 \\ 1 & 1 & 2 \end{array} \right) \begin{array}{l} \\ R_2 - 100R_1 \end{array} & \longrightarrow & \left( \begin{array}{cc|c} 0.01 & 1 & 1 \\ 0 & -99 & -98 \end{array} \right) \begin{array}{l} \\ -\dfrac{1}{99}R_2 \end{array} \\ \\ \longrightarrow & \left( \begin{array}{cc|c} 0.01 & 1 & 1 \\ 0 & 1 & 0.9898\ldots \end{array} \right). \end{align*} \end{split}\]

So \(x_2 = 0.9898\ldots\) which is rounded to \(x_2 = 1\) and using back substitution we have \(x_1 = \dfrac{1 - 1(1)}{0.01} = 0\). However, checking our solution with the original system we see that this does not satisfy the second equation \(x_1 + x_2 = 2\). 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.01 & 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.01 & 1 & 1 \end{array} \right) \begin{array}{l} \\ R_2 - 0.001 R_1 \end{array} \\ \\ \longrightarrow & \left( \begin{array}{cc|c} 1 & 1 & 2 \\ 0 & 0.99 & 0.98 \end{array} \right) \end{align*} \end{split}\]

Solving using back substitution we have \(x_2 = \dfrac{0.98}{0.99} = 0.9898\ldots \approx 1\) as before and using back substitution we now have \(x_1 = 2 - 1(1) = 1\) 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\) coefficient matrix \(A\) and an \(m\)-element constant vector \(\vec{b}\).

Outputs: An augmented matrix in row echelon form.

1. Form the augmented matrix \(( A \mid \vec{b} )\)

2. Set pivot row \(k\) to 1

3. For each column \(j\) from 1 to \(n\):

   1. Find the pivot row:

      • Identify the row \(i\) where \(i \geq k\) with the largest absolute value in column \(j\)

      • If the largest absolute value is zero skip to next column

   2. Swap rows:

      • Swap row \(i\) with row \(k\).

   3. Eliminate elements below pivot:

      • For each row \(i\) from \(k+1\) to \(m\):

        • Subtract \(\dfrac{a_{ij}}{a_{jj}}\) times row \(j\) from row \(i\)

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}\]

Solution

\[\begin{split} \begin{align*} & \left(\begin{array}{ccc|c} 1 & -1 & 3 & 13 \\ 4 & -2 & 1 & 15\\ -3 & -1 & 4 & 8 \end{array} \right) \begin{array}{l} R_1 \leftrightarrow R_2 \end{array} & \longrightarrow & \left( \begin{array}{ccc|c} 4 & -2 & 1 & 15\\ 1 & -1 & 3 & 13 \\ -3 & -1 & 4 & 8 \end{array} \right) \begin{array}{l} \\ R_2 - \frac{1}{4}R_1 \\[1pt] R_3 + \frac{3}{4}R_1 \end{array} \\ \\ \longrightarrow & \left( \begin{array}{ccc|c} 4 & -2 & 1 & 15\\ 0 & -1/2 & 11/4 & 37/4 \\ 0 & -5/2 & 19/4 & 77/4 \end{array} \right) \begin{array}{l} \\ R_2 \leftrightarrow R_3 \\ \phantom{x} \end{array} & \longrightarrow & \left( \begin{array}{ccc|c} 4 & -2 & 1 & 15\\ 0 & -5/2 & 19/4 & 77/4 \\ 0 & -1/2 & 11/4 & 37/4 \end{array} \right) \begin{array}{l} \\ \\ R_3 - \frac{1}{5}R_2 \end{array} \\ \\ \longrightarrow & \left( \begin{array}{ccc|c} 4 & -2 & 1 & 15\\ 0 & -5/2 & 19/4 & 77/4 \\ 0 & 0 & 9/5 & 27/5 \end{array} \right) \end{align*} \end{split}\]

Solving for \(x_3\), \(x_2\) and \(x_1\) using back substitution

\[\begin{split} \begin{align*} x_3 &= \frac{5}{9}\left( \frac{27}{5} \right) = 3, \\ x_2 &= -\frac{2}{5} \left( \frac{77}{4} - \frac{19}{4}(3)\right) = -2, \\ x_1 &= \frac{1}{4}( 15 + 2(-2) - 3) = 2. \end{align*} \end{split}\]