Direct Methods

Overview¶

Direct methods solve linear systems $\mathbf{A}\mathbf{x} = \mathbf{b}$ for the solution $\mathbf{x}$ directly in a finite, deterministic number of steps. In contrast to iterative methods (which gradually approach the answer), a direct solver will give you the exact solution (ignoring machine roundoff error) at the end of the algorithm.

In this section, we will cover the fundamental algorithms of direct solvers:

1. Gaussian Elimination¶

The foundational algorithm of linear algebra. We systematically eliminate variables equation-by-equation until we are left with an upper triangular matrix, which is easily solved via back-substitution.

2. Diagonal Dominance and Pivoting¶

Computers represent numbers with finite precision. We will explore how “small” numbers on the diagonal can cause catastrophic roundoff error, and how pivoting (row swapping) and diagonal dominance protect our algorithms from blowing up.

3. LU Decomposition¶

The industry standard. We will prove that Gaussian Elimination can be separated into two matrices: $\mathbf{L}$ and $\mathbf{U}$. This allows us to perform the expensive elimination step once, and solve the system for any new $\mathbf{b}$ vector instantly. This is the exact algorithm used under the hood by numpy and scipy.