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
z2
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