Gaussian Elimination Calculator

The Gaussian Elimination Algorithm

Gaussian elimination transforms a system of equations into row echelon form through a sequence of elementary row operations, then solves by back substitution. It is the workhorse algorithm for linear systems in both hand computation and numerical software.

The three allowed row operations are:

1. Swap two rows
2. Multiply a row by a nonzero scalar
3. Add a multiple of one row to another

These operations change the form of the system but not its solution set.

Row Echelon Form

The goal is to produce an upper triangular shape in the augmented matrix $[A | \mathbf{b}]$:

The boxed entries are pivots. Each pivot must be nonzero, and every entry below a pivot must be zero. Once in this form, the solution follows by back substitution starting from the last equation.

Worked Example

Solve using Gaussian elimination:

Step 1: Eliminate below pivot in column 1:

$R_2 \leftarrow R_2 + \frac{3}{2}R_1$ and $R_3 \leftarrow R_3 + R_1$:

Step 2: Eliminate below pivot in column 2:

$R_3 \leftarrow R_3 - 4R_2$:

Step 3: Back substitution:

From row 3: $z = -1$. Row 2: $y = (1 - 1/2(-1))/(1/2) = 3$. Row 1: $x = (8 - 3 + 1)/2 = 2$.

Solution: $(x, y, z) = (2, 3, -1)$

Partial Pivoting

In practice, always use partial pivoting: before eliminating in a column, swap the current row with the row below it that has the largest absolute value in that column. This prevents division by small numbers, which amplifies rounding errors.

Computational Complexity

Gaussian elimination on an $n \times n$ system requires:

This $O(n^3)$ complexity makes it practical for systems up to thousands of equations. For very large sparse systems (millions of equations), iterative methods like conjugate gradient are preferred.

Frequently Asked Questions