Pc Gaussian Elimination

Gaussian Elimination

Gaussian elimination with back-substitution is a procedure for solving linear systems by applying a particular sequence of elementary row operations to the augmented matrix of the system. A unique augmented matrix is associated with each system of linear equations. System

2 x + 5 y = 15   3 x − 2 y = 13

Augmented matrix

2 5 3 - 2 

15  13 

Elementary row operations are of three types. 1. Interchange two rows of a matrix. 2. Multiply a row of a matrix by a nonzero constant. 3. Add a multiple of one row of a matrix to another.

A row of a matrix is a zero row if it consists entirely of zeros. A row which is not a zero row is a nonzero row. A unit column of a matrix is a column with one entry a 1 and all other entries 0. non-zero row

zero row

0 0  1  0

2 0 6 0

1 0 1 0

1 0 0 0

0 0 2 0

unit column

3 0  0  0

A matrix is in row-echelon form if and only if: 1. All zero rows occur below all nonzero rows. 2. The first nonzero entry of any nonzero row is a one. This is called the leading 1 of the row. 3. For any two nonzero rows, the leading 1 of the higher row is to the left of the leading 1 of the lower row. 3. 2. 1.

1 0 6 3  0 1 - 1 4    0 0 1 2    0 0 0 0  

A matrix is in reduced row-echelon form if and only if: 1. The matrix is in row echelon form. 2. Every column containing a leading one is a unit column. unit columns 0 0  0  0

1 3 0 0 2 0 0 1 0 5  leading 1s 0 0 0 1 2  0 0 0 0 0

Example: Tell if each matrix is in row-echelon form. not a unit column 1 2 3  A =  0 1 7   0 0 0  0 B= 0 1 C = 0 0

1 0

A is in row-echelon form. A fails to be in reduced row-echelon form because the second column contains a leading 1, but is not a unit column.

leading 1 0 B is in both row-echelon form and reduced 1  row-echelon form.

2 1 5 0 0 1 0 1 0

C fails to be in row-echelon form because the leading 1 in the second row is to the right of the leading 1 in the third row. Since C is not in row-echelon form, it cannot be in reduced row-echelon form. leading 1s

To solve a system of linear equations using Gaussian elimination with back substitution, 1. Write the augmented matrix of the system. 2. Use elementary row operations to transform the augmented matrix into row-echelon form. 3.Write the system of equations corresponding to the augmented matrix in row-echelon form 4. Use back substitution to find the solution.

Example: Use Gaussian elimination with back substitution to solve y + 3z = 3  the system 2 x + 4 y = 10  2 x + 4 y + 3 z = 16 

1R 1 2

0 2  2

1

3

4 4

0 3

1 0  2

2

0

1 4

3 3

3 10  16  5 3  16

R2 2 R1 0  2

–2R1 + R3

1 0  0

4

0

1 4

3 3

2

0

1 0

3 3

10 3  16  5 3  6 

Example continued

Example continued 1 0  0

2

0

1 3 0 3

5 3  1 R3 6  3

1 0  0

2

0

1 3 0 1

5 3  2  Row-echelon form

=5 x + 2 y  y + 3z = 3 The system associated with this augmented matrix is:  z=2 

Substitute z = 2 back into the second equation and solve for y . y + 3(2) = 3 → y = –3. Substitute y = –3 back into the first equation and solve for x . x + 2(–3) = 5 → x = –1. The unique solution is (–1, –3, 2).

Example: Use Gaussian elimination with back substitution to solve the system  x + y = 4 .  2 x + 2 y = 6

1 1 2 2 

4 6 –2R1 + R2

1 1 0 0 

4 - 2 Row-echelon form

The system corresponding to this augmented matrix is:  x + y = 4   0 = −2 Since the second equation is false, the system has no solutions.