Partial pivoting

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.001 & 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.001 & 1 & 1 \\ 1 & 1 & 2 \end{array} \right) \begin{array}{l} \\ R_2 - 1000R_1 \end{array} & \longrightarrow & \left( \begin{array}{cc|c} 0.001 & 1 & 1 \\ 0 & -999 & -998 \end{array} \right) \begin{array}{l} \\ -\dfrac{1}{999}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.998998\ldots\) which we can round to \(x_2 = 1\) and using back substitution we have \(x_1 = \dfrac{1 - 1(1)}{0.001} = 0\). However, lets check our solution to see if we are correct

\[\begin{split} \begin{align*} 0.01(0) + 1(1) &= 1, \\ 1(0) + 1(1) &= 1 \neq 2. \end{align*} \end{split}\]

So the solution of \(x_1 = 0\) and \(x_2 = 1\) does not satisfy the original system and is clearly wrong. Lets solve the system again but perform a row swap on the two rows before eliminating the value beneath the pivot.

\[\begin{split} \begin{align*} & \left(\begin{array}{cc|c} 0.001 & 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.001 & 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.999 & 0.998 \end{array} \right) \end{align*} \end{split}\]

Solving using back substitution we have \(x_2 = \dfrac{0.998}{0.999} = 0.998998\ldots \approx 1\) as before and using back substitution we now have \(x_1 = 2 - 1(1) = 1\). Lets check this solution to see if it is correct

\[ \begin{align*} 0.001(1) + 1(1) &= 1.001 \approx 1, \end{align*} \]

which is consistent with the original system when rounding is applied. 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.

Form the augmented matrix \(( A \mid \vec{b} )\)
Set pivot row \(k\) to 1
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}\]