Systems of Linear Equations

Systems of Linear Equations
The system of linear equations
ai,0 x0 + · · · + ai,n-1 xn-1 = bi, for i = 0, . . . ,n - 1,
with coefficients ai,j and components bi belonging to a field can be solved for xi. The solution is unique if the determinant of the matrix of coefficients A = ( ai,j ) is nonzero. In matrix notation the system is written simply as A x = B.

The techniques for solving the linear system A x = B are customarily divided into two classes: direct methods and iterative methods. The methods belonging the class of direct methods include Gaussian elimination, Choleski decomposition of positive definite symmetric matrices, Crout's LU decomposition, Doolittle's LU decomposition, and special methods for lower or upper triangular matrices and for tridiagonal matrices. The methods belonging to the class of iterative methods include Jacobi's method, Gauss-Seidel's method and the method of successive overrelaxation.

Direct Methods
The direct methods are usually preferrable for small matrices. If a single linear system
A x = B is to be solved where det A ≠ 0, then unless the system is a triangular system or a tridiagonal system, Gaussian Elimination (with partial pivoting) is adequate with the proviso that the system of equations is equilibrated. If the right-hand side B can vary, then it is preferable to chose one of the LU decomposition methods, either Crout's, Doolittle's, or Choleski's. Note that the linear system A x = B is mathematically equivalent to the linear system ( ATA ) x = AT B, where ATA is positive definite symmetric (if A is nonsingular).

Iterative Methods
The iterative methods are generally preferred for large sparse matrices in which the diagonal elements are all non-zero. In general Gauss-Seidel's method is preferable to Jacobi's method, but there are examples in which Gauss-Seidel's method fails to converge while Jacobi's method converges and vice-versa. Successive Overrelaxation is preferable to Gauss-Seidel provided that the relaxation parameter is well-chosen.

Table of Routines for Solving a
System of Linear Equations