A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

GAUSSIAN ELIMINATION

DOI: 10.1615/AtoZ.g.gaussian_elimination

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.

REFERENCES

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.

Number of views: 6150 Article added: 2 February 2011 Article last modified: 14 February 2011 © Copyright 2010-2017 Back to top