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) a_{11} ≠ 0, one eliminates x_{1} from the last (n – 1) equations by subtracting the first equation, multiplied by m_{i1} = a_{i1}/a_{11}, from the i^{th} equation (i = 2, ... , n). The last (n – 1) equations form a system in the unknowns x_{2}, x_{3}, ... , x_{n} given by
where and , (i, j = 2, 3, ... , n).
Similarly, if (again called pivot), using , one can eliminate x_{2} from the last (n – 2) equations and get a system in the unknowns x_{3}, ..., x_{n} 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 k^{th} 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 k^{th} step. To this end, one looks for a nonzero coefficient of x_{k} 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., A^{T} = A and x^{T} A_{x} > 0 for all vectors x ≠ 0, ( T denotes the transpose).
When applied to an n × n system, the Gaussian method takes n(n^{2} – 1)/3 multiplications, n(n – 1)/2 divisions and n(n^{2} – 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.
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.