Gaussian_elimination_V2 - Ms

Download Report

Transcript Gaussian_elimination_V2 - Ms

Digital Lesson
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.
Copyright © by Houghton Mifflin Company, Inc. All rights reserved.
2
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
3
0 
0

0
unit column
Copyright © by Houghton Mifflin Company, Inc. All rights reserved.
3
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.
1 0 6 3 
3.
0 1 - 1 4 
2. 

0 0 1 2 


1.
0 0 0 0 
Copyright © by Houghton Mifflin Company, Inc. All rights reserved.
4
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
0
0
0
3
0
0
0
Copyright © by Houghton Mifflin Company, Inc. All rights reserved.
0
1
0
0
0
0
1
0
2
5  leading 1s
2

0
5
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
row-echelon form.
1 
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
Copyright © by Houghton Mifflin Company, Inc. All rights reserved.
6
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.
Copyright © by Houghton Mifflin Company, Inc. All rights reserved.
7
Example: Use Gaussian elimination with back substitution to solve
y  3z  3

the system 
 10
2 x  4 y
2 x  4 y  3 z  16

0
2

2
1 R
1
2
1
4
3
0
4
3
1 2 0
0 1 3

2 4 3
3
10 
16 
5
3 
16
–2R1 + R3
R2 2
R1 0

2
4
1
0
3
4
3
1
0

0
2
1
0
3
0
3
10
3 
16 
5
3 
6 
Example continued
Copyright © by Houghton Mifflin Company, Inc. All rights reserved.
8
Example continued
1
0

0
2
1
0
3
0
3
5
3 
1
R3
6 
3
1
0

0
2
1
0
3
0
1
5
3 
2  Row-echelon form
5
x  2 y

The system associated with this augmented matrix is: 
y  3z  3

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).
Copyright © by Houghton Mifflin Company, Inc. All rights reserved.
9
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.
Copyright © by Houghton Mifflin Company, Inc. All rights reserved.
10