The Algorithm for Gaussian Elimination with Partial Pivoting

We will now present the algorithm for Gaussian elimination with using the partial pivoting technique assuming that a unique solution to the system $Ax = b$ exists.

For input, obtain an $n \times n$ matrix $A$ and an $n \times 1$ column matrix $b$. Check to see if the matrices $A$ and $b$ are of the appropriate size. Let $\tilde{A} = (A | b)$ be the $n \times n +1$ matrix obtained by attaching the column $b$ to the right side of $A$.

For each $k = 1, 2, ..., n$:

Step 1: Find the row index $P_k ≥ k$ for which $\mid a_{p_k, k} \mid = \max_{k≤i≤n} \mid a_{i, k} \mid$. This finds the index of the largest (when absolute valued) entry in each row.

Step 2: If $a_{p_k, k} = 0$, then stop. An entire column consists of zeros which implies that the matrix $A$ is singular and has no solution. If $a_{p_k, k} \neq 0$, then interchange row $k$ and row $p_k$. This brings the largest (when absolute valued) entry to the main diagonal each time.

Step 3: For $i = k+1, k+2, ..., n$, let $a_{i,k} = a_{i, k} \div a_{k, k}$, and for $j = k+1, k+2, ..., n+1$, let $a_{i, j} = a_{i, j} - a_{i, k} a_{k, j}$.

Step 4: For $i = n, n-1, ..., 1$, we have that the solution is given by

(1)

\begin{align} \quad x_i = \frac{\left ( a_{i, n+1} - \sum_{j=i+1}^{n} a_{i, j}x_j \right )}{a_{ii}} \end{align}