Gaussian Elimination

Definition

Gaussian elimination is the standard algorithm for solving a system of linear equations $\mathrm{Ax}=\mathrm{b}$. It reduces the augmented matrix $[\mathrm{A}\mid \mathrm{b}]$ to upper-triangular form via row operations, followed by back substitution.

Intuition

Work column by column from left to right: use the current diagonal entry (the pivot) to zero out everything below it. After $n-1$ steps the matrix is upper-triangular and the unknowns can be read off from the bottom row upward by back substitution.

Formal Description

The three allowed elementary row operations are:

1. Interchange any two rows.
2. Multiply a row by a nonzero constant.
3. Add a multiple of one row to another.

These operations do not change the solution set. The goal is to reduce $\mathrm{A}$ to upper-triangular form $\mathrm{U}$.

Example. For the system

$$\left(\begin{array}{ccc}-3& 2& -1\\ 6& -6& 7\\ 3& -4& 4\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)=\left(\begin{array}{c}-1\\ -7\\ -6\end{array}\right),$$

form the augmented matrix and reduce:

$$\left(\begin{array}{cccc}-3& 2& -1& -1\\ 6& -6& 7& -7\\ 3& -4& 4& -6\end{array}\right)\to \left(\begin{array}{cccc}-3& 2& -1& -1\\ 0& -2& 5& -9\\ 0& -2& 3& -7\end{array}\right)\to \left(\begin{array}{cccc}-3& 2& -1& -1\\ 0& -2& 5& -9\\ 0& 0& -2& 2\end{array}\right).$$

Back substitution then gives $\mathrm{x}=(2,2,-1{)}^{\top }$.

The matrix element used to eliminate entries below it is called the pivot. Elimination fails if a pivot is zero; row interchange must be performed first. For numerical stability on large systems, partial pivoting (always swapping to bring the largest-magnitude entry to the pivot position) is used.

Applications

• Direct method for solving $\mathrm{Ax}=\mathrm{b}$ for a single right-hand side.
• Basis for LU Decomposition and Reduced Row Echelon Form.

Trade-offs

• A zero pivot requires a row interchange; without pivoting the algorithm may fail even for non-singular $\mathrm{A}$.
• Without partial pivoting, small pivots can cause catastrophic cancellation and large rounding errors.
• Costs $O(n^3)$ for an $n\times n$ system; inefficient when the same $\mathrm{A}$ must be used with many right-hand sides (use LU instead).

Links

• Systems of Linear Equations
• Reduced Row Echelon Form
• Elementary Matrices
• LU Decomposition