A method of successive eliminations of unknowns for solving a system of linear equations. Consider the system
and let . Gaussian elimination operates as follows. If the element (called pivot) a11 ≠ 0, one eliminates x1 from the last (n – 1) equations by subtracting the first equation, multiplied by mi1 = ai1/a11, from the ith equation (i = 2, ... , n). The last (n – 1) equations form a system in the unknowns x2, x3, ... , xn given by
where and , (i, j = 2, 3, ... , n).
Similarly, if (again called pivot), using , one can eliminate x2 from the last (n – 2) equations and get a system in the unknowns x3, ..., xn The coefficients of this system are given by and , (i, j = 3, ..., n).
If all the pivots , , , … are nonzero, then the procedure continues. In the kth step, the last (n – k) equations become:
where and , (i, j = k + 1, ..., n) with .
Gaussian elimination is performed in (n – 1) steps. Collecting the first equation from each step one obtains the following upper triangular system:
If , there is a unique solution given as:
Otherwise, if , then there is no solution if , while there are infinitely many solutions if .
If for some k, the pivot , then the elimination procedure cannot be continued unless an alternate pivot is chosen for the kth step. To this end, one looks for a nonzero coefficient of xk in equations k, k + 1, ..., n, and if it is found in equation j > k, one interchanges equations j and k. This process is called pivoting .
The Gaussian elimination method can be carried out without pivoting if (i) matrix A is diagonally dominant, i.e., (i = 1, 2, ..., n), or (ii) if A is symmetric and positive definite, i.e., AT = A and xT Ax > 0 for all vectors x ≠ 0, ( T denotes the transpose).
When applied to an n × n system, the Gaussian method takes n(n2 – 1)/3 multiplications, n(n – 1)/2 divisions and n(n2 – 1)/3 additions or subtractions.
Dahlquist, G and Björk, A. (1974) Numerical Methods, Prentice-Hall, N.J.
Golub, G. H. and Loan, C. F. van, (1983) Matrix Computations, North Oxford Acad.