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 a variable 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 the coefficient 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 a variable 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 the coefficient 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 a variable 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 the coefficient 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 a variable 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 the coefficient 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 4 7 −1

] [ x1

x2

] =

[ 9 8

] or, in matrix notation,

Ax = b

where,

A =

[ 2 4 7 −1

] ; x =

[ x1

x2

] ; and b =

[ 9 8

] .

Thus, sets of simultaneous linear equations can be conveniently written in matrix-vector form.

3/15

Solving

If we wanted to solve the set of equations Eq. 2, we could simply solve for, say, x2 in Eq. 2b

x2 = 7×1 − 8

and substitute into Eq. 2a: 2×1 + 4(7×1 − 8) = 9

to find 30×1 = 41

x1 = 41

30

We can find x2 by back substituting x1 into one of the equations. To automate the solution of linear systems, we would like to find a systematic procedure to accomplish the 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 9 0 1 2 −7 0 0 4 −1 0 0 0 3

  x1

x2

x3

x4

 =

 12 9 2 1

 (3)

Here the coefficient matrix is in upper-triangular form. Notice that if we start with the last equation, we can immediately solve for x4. Once we have x4, we can immediately use the second to last equation to get x3, etc. until the entire system is solved. This process is called back-substitution. We see that upper-triangular systems are especially easy to solve.

Goal: Our goal is to develop a systematic way to take a general coefficient matrix and reduce it to upper-triangular form.

5/15

A systematic procedure for reducing a general matrix to upper triangular form is known as Gaussian elimination. There are several variations, we will present the simplest. 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 not change the solution. For example replace the second equation by the sum of the first 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 is analagous 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 1 2

: 1 2 0 3 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 following matrix: 1 2 0

3 4 1 −1 −2 −3

 −→  1 2 0

3 4 1 2 · 1− 1 2 · 2− 2 2 · 0− 3

 =

1 2 0 3 4 1 1 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), in the column at or below the diagonal is on the diagonal for the first row

3 Use linear combinations of the first row using α = − ai1 a11

for each row below the

diagonal. This will make all the entries in the first column below the diagonal zero.

4 Repeat but move to the second row, second column, etc until the entire matrix is in upper-triangular form.

9/15

Example

First move largest element in column 1 to be the first row 1 2 0 3 4 1 −1 −2 −3

 −→  3 4 1

1 2 0 −1 −2 −3

 Use linear combination of row 1 and 2 with α = − 1

3 to put a zero in the second

row, first column: 3 4 1 1 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 1 0 2

3 − 1

3 −1 −2 −3

 Use linear combination of row 1 and row 3 with α = 1

3 3 4 1 0 2

3 − 1

3 −1 −2 −3

 −→  3 4 1

0 2 3

− 1 3

1 3 · 3− 1 1

3 · 4− 2 1

3 · 1− 3

 =

3 4 1 0 2

3 − 1

3 0 − 2

3 − 8

3

 Move to second row, second column. Since |a22| = |a32|, there is no need to swap rows.

Use linear combination of row 2 and row 3 to eliminate a32 using α = 13 4 1 0 2

3 − 1

3 0 − 2

3 − 8

3

 −→ 3 4 1

0 2 3 − 1

3 0 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:

A row 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 to upper-triangular form and modify the right hand side appropriately.

6 7 −5 2 0 9 2 6 0 −8 1 1 −7 −4 −10 3

  x1

x2

x3

x4

 =

 13 48 −9 −33

 (4)

12/15

LU Decomposition

Factor matrix Column 1 Pivot row 1 and row 4 

−7 −4 −10 3 0 9 2 6 0 −8 1 1 6 7 −5 2

  x1

x2

x3

x4

 =

 −33 48 −9 13

 Eliminate row 4 with row 1 using alpha= 0.857143

−7 −4 −10 3 0 9 2 6 0 −8 1 1 0 3.57143 −13.5714 4.57143

  x1

x2

x3

x4

 =

 −33 48 −9

−15.2857



13/15

Column 2

Eliminate row 3 with row 2 using alpha= 0.888889 −7 −4 −10 3 0 9 2 6 0 0 2.77778 6.33333 0 3.57143 −13.5714 4.57143

  x1

x2

x3

x4

 =

 −33 48

33.6667 −15.2857

 Eliminate row 4 with row 2 using alpha= -0.396825

−7 −4 −10 3 0 9 2 6 0 0 2.77778 6.33333 0 0 −14.3651 2.19048

  x1

x2

x3

x4

 =

 −33 48

33.6667 −34.3333

 Column 3 Pivot row 3 and row 4

−7 −4 −10 3 0 9 2 6 0 0 −14.3651 2.19048 0 0 2.77778 6.33333

  x1

x2

x3

x4

 =

 −33 48

−34.3333 33.6667

 Eliminate row 4 with row 3 using alpha= 0.19337

−7 −4 −10 3 0 9 2 6 0 0 −14.3651 2.19048 0 0 0 6.75691

  x1

x2

x3

x4

 =

 −33 48

−34.3333 27.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 =

 0 0 0 0



15/15

Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.