Direct Methods for Linear Systems

Direct methods solve a linear system Ax = b in a finite number of arithmetic steps, typically by factoring the matrix and then solving triangular systems by substitution.

Definition

A direct method is an algorithm that computes the exact solution of a linear system — up to rounding error — in a predetermined finite number of operations, as opposed to an iterative method that produces a sequence of approximations.

Scope

This topic covers Gaussian elimination, its expression as an LU factorization, the role of pivoting in controlling error growth, forward and back substitution for triangular systems, and the operation counts that make direct solvers practical for dense and banded matrices.

Core questions

• How does Gaussian elimination reduce a system to triangular form, and why is this equivalent to an LU factorization?
• Why is pivoting necessary, and how do partial and complete pivoting control the growth of rounding error?
• What is the computational cost of a direct solve, and how does exploiting structure (symmetry, bandedness, sparsity) reduce it?
• Under what conditions is Gaussian elimination with partial pivoting backward stable in practice?

Key theories

LU factorization with partial pivoting

Gaussian elimination with row interchanges factors a matrix as PA = LU with L unit lower-triangular and U upper-triangular; partial pivoting bounds the multipliers and makes the method reliable for almost all matrices encountered in practice.

Growth factor and backward stability

The backward error of Gaussian elimination is governed by the growth factor of entries during elimination; although exponential growth is possible in contrived cases, partial pivoting keeps growth small enough that the method is backward stable for virtually all real problems.

Mechanisms

Gaussian elimination proceeds column by column: at each step a pivot is selected (partial pivoting chooses the largest-magnitude candidate in the current column), multiples of the pivot row are subtracted from the rows below to introduce zeros, and the multipliers are stored to form L. The resulting upper-triangular U is solved by back substitution and the right-hand side is processed by forward substitution. For an n-by-n dense matrix the factorization costs about two-thirds n-cubed operations, while each triangular solve costs order n-squared.

Clinical relevance

Direct solvers are the default workhorse whenever a moderately sized dense or banded system must be solved to full accuracy — in finite-element assembly, circuit simulation, control, and as the inner solve inside larger numerical schemes — and a single factorization can be reused to solve many right-hand sides cheaply.

History

Elimination methods trace to Gauss and earlier, but their behaviour in finite-precision arithmetic was clarified by Wilkinson's backward error analysis in the 1960s, which showed that partial pivoting tames error growth and explained the empirical reliability of the method that had long been observed on early computers.

Key figures

• Carl Friedrich Gauss
• James H. Wilkinson
• Nicholas J. Higham

Seminal works

• trefethen1997
• golub2013
• higham2002

Frequently asked questions

When should a direct method be preferred over an iterative one?

Direct methods are preferred when the matrix is dense or moderately sized, when many right-hand sides share one matrix (so a single factorization is reused), or when a guaranteed finite, full-accuracy solution is required. Very large sparse systems usually favour iterative methods.

Does pivoting always guarantee a small error?

Partial pivoting guarantees backward stability in practice for almost all matrices, but it does not overcome ill-conditioning: if the matrix itself is nearly singular, even a backward-stable solve can return a solution with large forward error.