3.1: Gaussian Elimination
- Last updated
- May 31, 2022
- Save as PDF
( \newcommand{\kernel}{\mathrm{null}\,}\)
The standard numerical algorithm to solve a system of linear equations is called Gaussian Elimination. We can illustrate this algorithm by example.
Consider the system of equations
−3x1+2x2−x3=−16x1−6x2+7x3=−73x1−4x2+4x3=−6
To perform Gaussian elimination, we form an Augmented Matrix by combining the matrix A with the column vector b :
(−32−1−16−67−73−44−6)
Row reduction is then performed on this matrix. Allowed operations are (1) multiply any row by a constant, (2) add multiple of one row to another row, (3) interchange the order of any rows. The goal is to convert the original matrix into an upper-triangular matrix
We start with the first row of the matrix and work our way down as follows. First we multiply the first row by 2 and add it to the second row, and add the first row to the third row:
(−32−1−10−25−90−23−7)
We then go to the second row. We multiply this row by −1 and add it to the third row:
(−32−1−10−25−900−22)
The resulting equations can be determined from the matrix and are given by
−3x1+2x2−x3=−1−2x2+5x3=−9−2x3=2
These equations can be solved by backward substitution, starting from the last equation and working backwards. We have
−2x3=2→x3=−1−2x2=−9−5x3=−4→x2=2−3x1=−1−2x2+x3=−6→x1=2
Therefore,
(x1x2x3)=(22−1)
