Partial Pivoting in Gaussian Elimination

This page is intended to be a part of the Numerical Analysis section of Math Online. Similar topics can also be found in the Linear Algebra section of the site.

Partial Pivoting in Gaussian Elimination

Recall from The Gaussian Elimination Algorithm that in the process of solution a linear system of $n$ equations in $n$ unknowns that we assumed that $a_{kk}^{(k)} \neq 0$ for each $k = 1, 2, ... n$, that is, we assumed that the entries in the main diagonal of our coefficient matrix $A$ representing our linear system were always nonzero after applying a finite number of elementary row operations. Sometimes this assumption does not hold when attempting to a solve a system of linear equations. It is also possible that $a_{kk}^{(k)}$ could be a very small number (either naturally or if $a_{kk}^{(k)}$ is meant to be $0$ by have accumulated some roundoff errors). In such case, dividing by a relatively small number has its own problems as it may cause overflow.

One way to prevent major problems from happening when using the Gaussian Elimination algorithm is through Partial Pivoting (Column Pivoting) at a step $k$ for which a problem might occur. Define the number $c$ as:

(1)
\begin{align} \quad c = \max_{k ≤ i ≤ n} \mid a_{ik}^{(k)} \mid \end{align}

In other words, at step $k$, let $c$ be equal to largest of the absolute values of the coefficients of the entries in column $k$ but on/underneath the entry $a_{kk}^{(k)}$, that is, the largest of $\mid a_{kk}^{(k)}$, $\mid a_{k+1,k}^{(k)} \mid$, …, $\mid a_{nk}^{(k)} \mid$. Therefore for some $i_0$ such that $k ≤ i_0 ≤ n$ we have that $c = \mid a_{i_0,k}^{(k)} \mid$.

We then interchange equation $E(k)$ with equation $E(i_0)$. This forces the absolute value in the position $a_{kk}^(k)$ to be the maximum among $\mid a_{kk}^{(k)} \mid$, $\mid a_{k+1,k}^{(k)} \mid$, …, $\mid a_{nk}^{(k)} \mid$.

We then continue on with the Gaussian Elimination algorithm. In doing this, we are not changing the answer to our solution since the order on working with equations lower than the step number $k$ does not add complexity and does not disturb the structure of the system.

Now recall from the Gaussian Elimination page earlier that at step $k$, the multiplier $m_{ik} = \frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}$ for $i = k+1, k+2, ..., n$. Since the absolute value of the number $a_{ik}^{(k)}$ for $i = k+1, k+2, ..., n$ is always going to be less or equal to the absolute value of the number $a_{kk}^{(k)}$ then the technique of partial pivoting in Gaussian Elimination guarantees us that:

(2)
\begin{align} \quad \mid m_{ik} \mid = \frac{\mid a_{ik}^{(k)} \mid }{\mid a_{kk}^{(k)}\mid } ≤ 1 \quad i = k+1, k+2, ..., n \end{align}

This is particularly useful because when we multiply by $m_{ik}$ during Gaussian Elimination, we will have reduced the loss of significance errors.