The Algorithm for Gaussian Elimination with Partial Pivoting

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}