Review of Gauss Elimination
Daniel C. Simkins, Jr.
University of South Florida
September 22, 2020
1/15
Matrices and Linear Equations
There is a very close relationship between matrices and systems of linear equations. .
2x − 9 = −4y (1a)
7x − y = 8. (1b)
By convention, we respect the following rules:
1 write all pure numbers on the right-hand side (RHS), and all terms with avariable on the left-hand side (LHS)
4y + 2x = 9
7x − y = 8.
2 write the terms on the LHS in the same order according to the unknowns
2x + 4y = 9
7x − y = 8.
3 label the unknowns as elements of a vector, i.e. xi .
2×1 + 4×2 = 9 (2a)
7×1 − x2 = 8. (2b)
Then, the only thing that distinguishes one equation from another is the value of thecoefficient of each variable and the number on the right.
2/15
Matrices and Linear Equations
There is a very close relationship between matrices and systems of linear equations. .
2x − 9 = −4y (1a)
7x − y = 8. (1b)
By convention, we respect the following rules:
1 write all pure numbers on the right-hand side (RHS), and all terms with avariable on the left-hand side (LHS)
4y + 2x = 9
7x − y = 8.
2 write the terms on the LHS in the same order according to the unknowns
2x + 4y = 9
7x − y = 8.
3 label the unknowns as elements of a vector, i.e. xi .
2×1 + 4×2 = 9 (2a)
7×1 − x2 = 8. (2b)
Then, the only thing that distinguishes one equation from another is the value of thecoefficient of each variable and the number on the right.
2/15
Matrices and Linear Equations
There is a very close relationship between matrices and systems of linear equations. .
2x − 9 = −4y (1a)
7x − y = 8. (1b)
By convention, we respect the following rules:
1 write all pure numbers on the right-hand side (RHS), and all terms with avariable on the left-hand side (LHS)
4y + 2x = 9
7x − y = 8.
2 write the terms on the LHS in the same order according to the unknowns
2x + 4y = 9
7x − y = 8.
3 label the unknowns as elements of a vector, i.e. xi .
2×1 + 4×2 = 9 (2a)
7×1 − x2 = 8. (2b)
Then, the only thing that distinguishes one equation from another is the value of thecoefficient of each variable and the number on the right.
2/15
Matrices and Linear Equations
There is a very close relationship between matrices and systems of linear equations. .
2x − 9 = −4y (1a)
7x − y = 8. (1b)
By convention, we respect the following rules:
1 write all pure numbers on the right-hand side (RHS), and all terms with avariable on the left-hand side (LHS)
4y + 2x = 9
7x − y = 8.
2 write the terms on the LHS in the same order according to the unknowns
2x + 4y = 9
7x − y = 8.
3 label the unknowns as elements of a vector, i.e. xi .
2×1 + 4×2 = 9 (2a)
7×1 − x2 = 8. (2b)
Then, the only thing that distinguishes one equation from another is the value of thecoefficient of each variable and the number on the right.
2/15
Matrix Form
Following this convention allows us to write this as a matrix equation[2 47 −1
] [x1
x2
]=
[98
]or, in matrix notation,
Ax = b
where,
A =
[2 47 −1
]; x =
[x1
x2
]; and b =
[98
].
Thus, sets of simultaneous linear equations can be conveniently written inmatrix-vector form.
3/15
Solving
If we wanted to solve the set of equations Eq. 2, we could simply solve for, say, x2 inEq. 2b
x2 = 7×1 − 8
and substitute into Eq. 2a:2×1 + 4(7×1 − 8) = 9
to find30x1 = 41
x1 =41
30
We can find x2 by back substituting x1 into one of the equations. To automate thesolution of linear systems, we would like to find a systematic procedure to accomplishthe same result.
4/15
Let’s consider a very special set of equations:
2×1 + 3×2 − 4×3 + 9×4 = 12
x2 + 2×3 − 7×4 = 9
4×3 − x4 = 2
3×4 = 1
or, in matrix form, 2 3 −4 90 1 2 −70 0 4 −10 0 0 3
x1
x2
x3
x4
=
12921
(3)
Here the coefficient matrix is in upper-triangular form. Notice that if we start with thelast equation, we can immediately solve for x4. Once we have x4, we can immediatelyuse the second to last equation to get x3, etc. until the entire system is solved. Thisprocess is called back-substitution. We see that upper-triangular systems are especiallyeasy to solve.
Goal: Our goal is to develop a systematic way to take a general coefficient matrix andreduce it to upper-triangular form.
5/15
A systematic procedure for reducing a general matrix to upper triangular form isknown as Gaussian elimination. There are several variations, we will present thesimplest. The basis for Gauss elimination is the repetitive use of basic operations,based on the following observations:
re-writing the order of the equations does not change their solution
2×1 + 4×2 = 9
7×1 − x2 = 8.
is the same as
7×1 − x2 = 8
2×1 + 4×2 = 9.
multiplying an entire equation by a scalar does not change the solution
2 (2×1 + 4×2) = 2 (9)
7×1 − x2 = 8.
6/15
we can replace any equation by the sum of itself with another equation does notchange the solution. For example replace the second equation by the sum of thefirst and second:
2×1 + 4×2 = 9
9×1 − 3×2 = 17.
7/15
Row operations
1 Swap two rows. This operation merely interchanges two rows in the matrix and isanalagous to re-ordering the linear equations.Example: 1 2 0
3 4 1−1 −2 −3
−→ 3 4 1
1 2 0−1 −2 −3
2 Row scaling. Here, a single row is multiplied by a scalar, rather than the entire
matrix. Example, scale row 3 by 12
: 1 2 03 4 1−1 −2 −3
−→ 1 2 0
3 4 1− 1
2−1 − 3
2
3 Linear combination of two rows. Here we take the scalar multiple of one row and
add it to another row, replacing the last row. In equations,
a′jk = α aik + ajk ; k = 1, …, n
for rows i and j .Example: for α = 2, take the linear combination of rows 1 and 3 in the followingmatrix: 1 2 0
3 4 1−1 −2 −3
−→ 1 2 0
3 4 12 · 1− 1 2 · 2− 2 2 · 0− 3
=
1 2 03 4 11 2 −3
8/15
Gauss Procedure
The procedure to reduce a general matrix to upper-triangular form is simple:
1 Start with first row and column
2 swap rows so that the row containing the largest element (in absolute value), inthe column at or below the diagonal is on the diagonal for the first row
3 Use linear combinations of the first row using α = − ai1a11
for each row below the
diagonal. This will make all the entries in the first column below the diagonalzero.
4 Repeat but move to the second row, second column, etc until the entire matrix isin upper-triangular form.
9/15
Example
First move largest element in column 1 to be the first row 1 2 03 4 1−1 −2 −3
−→ 3 4 1
1 2 0−1 −2 −3
Use linear combination of row 1 and 2 with α = − 1
3to put a zero in the second
row, first column: 3 4 11 2 0−1 −2 −3
−→ 3 4 1− 1
3· 3 + 1 − 1
3· 4 + 2 − 1
3· 1 + 0
−1 −2 −3
=
3 4 10 2
3− 1
3−1 −2 −3
Use linear combination of row 1 and row 3 with α = 1
3 3 4 10 2
3− 1
3−1 −2 −3
−→ 3 4 1
0 23
− 13
13· 3− 1 1
3· 4− 2 1
3· 1− 3
=
3 4 10 2
3− 1
30 − 2
3− 8
3
Move to second row, second column. Since |a22| = |a32|, there is no need to swaprows.
Use linear combination of row 2 and row 3 to eliminate a32 using α = 13 4 10 2
3− 1
30 − 2
3− 8
3
−→3 4 1
0 23− 1
30 0 −3
which is now reduced to upper-triangular form.
10/15
So, we see that a sequence of row operations changes the matrix A into the matrix U:
Arow operations−−−−−−−−−−−→ U
Important!
It is crucial to note that what ever we do to the LHS, must also be done to the RHS,i.e. swapping rows and linear combinations.
11/15
Solution Example
Using the Gauss elimination procedure given in class, reduce the following matrix toupper-triangular form and modify the right hand side appropriately.
6 7 −5 20 9 2 60 −8 1 1−7 −4 −10 3
x1
x2
x3
x4
=
1348−9−33
(4)
12/15
LU Decomposition
Factor matrixColumn 1Pivot row 1 and row 4
−7 −4 −10 30 9 2 60 −8 1 16 7 −5 2
x1
x2
x3
x4
=
−3348−913
Eliminate row 4 with row 1 using alpha= 0.857143
−7 −4 −10 30 9 2 60 −8 1 10 3.57143 −13.5714 4.57143
x1
x2
x3
x4
=
−3348−9
−15.2857
13/15
Column 2
Eliminate row 3 with row 2 using alpha= 0.888889−7 −4 −10 30 9 2 60 0 2.77778 6.333330 3.57143 −13.5714 4.57143
x1
x2
x3
x4
=
−3348
33.6667−15.2857
Eliminate row 4 with row 2 using alpha= -0.396825
−7 −4 −10 30 9 2 60 0 2.77778 6.333330 0 −14.3651 2.19048
x1
x2
x3
x4
=
−3348
33.6667−34.3333
Column 3Pivot row 3 and row 4
−7 −4 −10 30 9 2 60 0 −14.3651 2.190480 0 2.77778 6.33333
x1
x2
x3
x4
=
−3348
−34.333333.6667
Eliminate row 4 with row 3 using alpha= 0.19337
−7 −4 −10 30 9 2 60 0 −14.3651 2.190480 0 0 6.75691
x1
x2
x3
x4
=
−3348
−34.333327.0276
14/15
Back solve
Solve for x4: x4 = 27.0276−(0)6.75691
= 4
Solve for x3: x3 = −34.3333−4(2.19048)−14.3651
= 3
Solve for x2: x2 = 48−(2∗3+4∗6)9
= 2
Solve for x1: x1 = −33−(−4∗2−10∗3+3∗4)−7
= 1
Check solution
R = Ax− b =
0000
15/15
