section 1.1-1.2
Download
Report
Transcript section 1.1-1.2
Chapter 1 Systems of Linear Equations and Matrices
•Introduction to System of Linear Equations
• Gaussian Elimination
• Matrices and Matrix Operations
• Inverses; Rules of Matrix Arithmetic
• Elementary Matrices and a Method for Finding
A1
• Further Results on Systems of Equations and Invertibility
• Diagonal, Triangular, and Symmetric Matrices
1.1 Introduction to systems of linear equations
•Any straight line in xy-plane can be represented algebraically by an equation of
the form:
a1 x a2 y b
•General form: Define a linear equation in the n variables x1 , x2 ,..., xn :
a1 x1 a2 x2 ... an xn b
where a1, a2, …, an and b are real constants.
The variables in a linear equation are sometimes called unknowns.
Linear Equations
Examples:
•
Some linear equations:
3x 5 y 6 0,109 z 123x 100 y 98, x1 2 x2 4 x3 5x4 9
•
Some NON linear equations:
2 x 6 y 0, 9 xz 3x 2 y, e x y 9, 3ln y x 4 z 8, cos x tan y 6
Observe that
•A linear equation does not involve any products or roots of variables
•All variables occur only to the first power and do not appear as arguments for
trigonometric, logarithmic, or exponential functions.
Solutions of Linear Equations
•A solution of a linear equation is a sequence of n numbers s1, s2, …, sn
such that the equation is satisfied.
•The set of all solutions of the equation is called its solution set or general
solution of the equation.
Example:
(a) Find the solution of 3x+4y = 5
Solution: We can assign arbitrary values to any one of the variables and solve
for the other variable. In particular, we have
x t, y
3t 5
4
where t is an arbitrary value, called a parameter.
Example (b): Find the solution of x1 3x2 8 x3 16
Solution: We can assign arbitrary values to any two variables and solve for
the third variable. In particular,
x1 3s 8t 16, x2 s, x3 t
where s, t are parameters
Linear Systems
A finite set of linear equations in the variables x1, x2, …, xn is called a
system of linear equations or a linear system.
A sequence of numbers s1, s2, …, sn is called a solution of the system if
every equation is satisfied.
A system has no solution is said to be inconsistent.
If there is at least one solution of the system, it is called consistent.
Every system of linear equations has either no solutions, exactly one
solution, or infinitely many solutions.
A general system of two linear equations:
a1 x b1 y c1 (a1 , b1 not both zero)
a2 x b2 y c2 (a2 , b2 not both zero)
Two line may be parallel – no solution
Two line may be intersect at only one point – one solution
Two line may coincide – infinitely many solutions
An arbitrary system of m linear equations in n unknown can be written as
a11 x1 a12 x2 ... a1n xn b1
a21 x1 a22 x2 ... a2 n xn b2
...
am1 x1 am 2 x2 ... amn xn bm
Where x1, x2, …, xn are unknowns and the subscripted a’s and b’s denote
Constants.
Note that
aij is in the ith equation and multiplies unknown x j
Augmented Matrix
A system of m linear equations in n unknowns can be written as a rectangular array
of numbers:
a11 x1 a12 x2 ... a1n xn b1
a21 x1 a22 x2 ... a2 n xn b2
...
am1 x1 am 2 x2 ... amn xn bm
a11
a
21
...
am1
a12
...
a1n
a22
...
am 2
... a2 n
... ...
... amn
This is called the augmented matrix for the system.
Example:
2 x1 3 x2 x3 5
6 x1 11x2 4 x3 0
5 x1 9 x2 2 xn 1
2 3 1 5
6 11 4 0
5 9
2 1
b1
b2
...
bm
Elementary Row Operations
Since the rows of an augmented matrix correspond to the equations,
we can apply the following three types of operations to solve systems of
linear equations.
•Multiply an equation through by an nonzero constant
• Interchange two equation
• Add a multiple of one equation to another
These operations are called elementary row operations.
We will go to details in the next session.
1.2 Gaussian Elimination
A matrix which has the following properties is in reduced row echelon Form.
•If a row does not consist entirely of zeros, then the first nonzero number in
the row is a 1. We call this a leader 1.
•If there are any rows that consist entirely of zeros, then they are grouped
together at the bottom of the matrix.
•In any two successive rows that do not consist entirely of zeros, the leader
1 in the lower row occurs farther to the right than the leader 1 in the higher
row.
•Each column that contains a leader 1 has zeros everywhere else.
A matrix that has the first three properties is said to be in row echelon form.
Note: A matrix in reduced row-echelon form is of necessity in row echelon
form, but not conversely
Row-Echelon and Reduced Row-Echelon Forms
Example: Determine which of the following matrices are in row-echelon form, reduced
Row-echelon form, both, or neither.
1
0
0
1
0
0
0 0 1 8
1 0,0 1
0 1 0 0
0 0 2 0
1 0 3 , 0
0 1 3 0
2 1
0,0
0 0
1 5
1 0
0 0
0 0
3 0
2 1
4 1 5 4 2
7 , 0 1 6 1
1 0 0 0 0
Solution: in row-echelon form:
1 0 0 1 8 2 1 0 0 2 1 5 4 2
, 0 1 6 1
0
1
0
,
0
1
0
,
0
1
0
3
0 0 1 0 0 0 0 0 1 3 0 0 0 0
in reduced row-echelon form:
1 0 0 1 0 0 2
0
1
0
,
0
1
0
3
0 0 1 0 0 1 3
Example: Determine which of the following matrices are in row-echelon form, reduced
Row-echelon form, both, or neither.
1
0
0
1
0
0
0 0 1 8
1 0,0 1
0 1 0 0
0 0 2 0
1 0 3 , 0
0 1 3 0
2 1
0,0
0 0
1 5
1 0
0 0
0 0
3 0
2 1
4 1 5 4 2
7 , 0 1 6 1
1 0 0 0 0
Solution: in both: 1 0 0 1 0 0 2
0
1
0
,
0
1
0
3
0 0 1 0 0 1 3
In neither: 1 0 0 0 1 5 4
0
3
0
,
0
1
0
7
0 2 1 0 0 0 1
More on Row-Echelon and Reduced Row-Echelon Form
All matrices of the following types are in row-echelon form (any
real numbers substituted for the *’s. ) :
1
0
0
0
*
1
0
0
*
*
1
0
* 1
* 0
,
* 0
1 0
*
1
0
0
*
*
1
0
* 1
* 0
,
* 0
0 0
*
1
0
0
*
*
0
0
0
*
0
*
, 0
0
0
0
0
1
0
0
0
0
*
0
0
0
0
*
1
0
0
0
*
*
1
0
0
*
*
*
1
0
*
*
*
*
0
*
*
*
*
0
*
*
*
*
1
*
*
*
*
*
All matrices of the following types are in reduced row-echelon form (any
real numbers substituted for the *’s. ) :
1
0
0
0
0
1
0
0
0
0
1
0
0 1
0 0
,
0 0
1 0
0
1
0
0
0
0
1
0
* 1
* 0
,
* 0
0 0
0
1
0
0
*
*
0
0
0
*
0
*
, 0
0
0
0
0
1
0
0
0
0
*
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
*
*
*
*
0
*
*
*
*
0
0
0
0
0
1
*
*
*
*
*
Solutions of Linear Equations
Example: Suppose that the augmented matrix for a system of linear equations
has been reduced by row operations to the given reduced row-echelon form.
Solve the system.
1
(a) 0
0
1
0
(c )
0
0
0 0 6
1 0 3 ,
0 1 8
3 0 0 2 8
0 1 0 3 5
,
0 0 1 4 7
0 0 0 0 0
1 0 0 5 6
(b) 0 1 0 1 3
0 0 1 7 9
1 0 0 0
( d ) 0 1 4 0
0 0 0 1
Solution (a): The corresponding system of equations is
6
x1
x2
3
x3 8
By inspection, x1 6, x2 3, x3 8
Example: Suppose that the augmented matrix for a system of linear equations
has been reduced by row operations to the given reduced row-echelon form.Solve
the system.
1 0 0 5 6
(b) 0 1 0 1 3
0 0 1 7 9
Solution (b): The corresponding system of equation is
+ 5x4 6
x1
Leading variables
x4 3
x2
x3
free variables
7 x4 9
Solving for the leading variables in terms of the free variable gives
x1 6 5x4
x2 3 x4
x3 9 7 x4
Thus, the general solution is
x1 6 5t , x2 3 t , x3 9 7t , x4 t
Example: Suppose that the augmented matrix for a system of linear equations
has been reduced by row operations to the given reduced row-echelon form.Solve
the system.
1
0
(c )
0
0
3 0 0 2 8
0 1 0 3 5
0 0 1 4 7
0 0 0 0 0
Solution (c): The corresponding system of equation is
+ 2x5 8
x1 +3x2
+3x5 5
x3
x4 4 x5 7
Solving for the leading variables in terms of the free variable gives
x1 8 3x2 2x5
x3 5 3x5
x4 7 4 x5
Thus, the general solution is
x1 8 3s 2t , x2 s, x3 5 3t , x4 7 4t , x5 t
Example: Suppose that the augmented matrix for a system of linear equations
has been reduced by row operations to the given reduced row-echelon form.Solve
the system.
1 0 0 0
(d ) 0 1 4 0
0 0 0 1
Solution (d): The corresponding system of equation is
x1
0
x2 4 x3 0
0 1
Since 0=1 cannot be satisfied, there is no solution to the system
Elimination Method
Elimination procedure to reduce a matrix to reduced row-echelon form.
0 0 2 0 7 12
2 4 10 6 12 28
2 4 5 6 5 1
Step 1. Locate the leftmost column that does not consist entirely of zeros.
0 0 2 0 7 12
2 4 10 6 12 28
2 4 5 6 5 1
Step 2. Interchange the top row with another row, if necessary, to bring a nonzero
entry to the top of the column found in step 1.
R1
R2
2 4 10 6 12 28
0 0 2 0 7 12
2 4 5 6 5 1
Step 3. If the entry that is now at the top of the column found in step 1 is a, multiply
The first row by 1/a in order to introduce a leading 1.
1
R1
2
1 2 5 3 6 14
0 0 2 0 7 12
2 4 5 6 5 1
Step 4. Add suitable multiples of the top row to the rows below so that all entries
Below the leading 1 become zeros.
R3 (2 R1 )
14
1 2 5 3 6
0 0 2 0 7
12
0 0 5 0 17 29
Step 5. Cover the top row in the matrix and begin again with Step 1 applied to the
Submatrix that remains. Continue in this way until the entire matrix is in row-echelon
form.
1
R2
2
6
14
1 2 5 3
0 0 1 0 7 / 2 6
0 0 5 0 17 29
6
14
1 2 5 3
0
0
1
0
7
/
2
6
0 0 0 0 1/ 2
1
R3 5R1
2R3
6
14
1 2 5 3
0 0 1 0 7 / 2 6
0 0 0 0
1
2
Step 6. Beginning with the last nonzero row and working upward, add suitable
multiples of each row to the rows above to introduce zeros above the leading 1’s
6
14
1 2 5 3
0 0 1 0 7 / 2 6
0 0 0 0
1
2
R1 5R2
R2
7
R3
2
1 2 5 3 6 14
0 0 1 0 0 1
0 0 0 0 1 2
R1 6 R3
1 2 5 3 0 2
0 0 1 0 0 1
0 0 0 0 1 2
1 2 0 3 0 7
0 0 1 0 0 1
0 0 0 0 1 2
•Step1~Step5: the above procedure produces a row-echelon form and
is called Gaussian elimination
•Step1~Step6: the above procedure produces a reduced row-echelon
form and is called Gaussian-Jordan elimination
Every matrix has a unique reduced row-echelon form but a row-echelon
form of a given matrix is not unique
x y 2z 9
Example: Solve by Gauss-Jordan elimination
2 x 4 y 3z 1
3x 6 y 5 z 0
1 1 2 9
Solution: The augmented matrix for the system is 2 4 3 1
3 6 5 0
1 1 2 9
2 4 3 1 R2 2R1
3 6 5 0
9
1 1 2
7
17
0 1
2
2
0 3 11 27
9
1 1 2
0 2 7 17
3 6 5 0
1 1 2
R3 3R2
0 1 7
2
1
0 0
2
R3 3R1
9
17
2
3
2
9
1 1 2
0 2 7 17
0 3 11 27
2R3
1 1 2
0 1 7
2
0 0 1
9
17
2
3
1
R2
2
1 1 2
0 1 7
2
0 0 1
R1 R2
9
7
17 R2 R3
2
2
3
1 1 2 9 R 2 R
3
0 1 0 2 1
0 0 1 3
1 1 0 3
0 1 0 2
0 0 1 3
1 0 0 1
0 1 0 2
0 0 1 3
1
x
The corresponding system of equations is
The solution is x=1, y=2, z=3.
y
2
z 3
Homogeneous Linear Systems
A system of linear equations is said to be homogeneous if the constant
terms are all zero; that is, the system has the form:
a11 x1 a12 x2 ... a1n xn 0
a21 x1 a22 x2 ... a2 n xn 0
...
am1 x1 am 2 x2 ... amn xn 0
Every homogeneous system of linear equation is consistent, since all
such system have x1 = 0, x2 = 0, …, xn = 0 as a solution. This solution
is called the trivial solution. If there are another solutions, they are
called nontrivial solutions.
There are only two possibilities for its solutions:
• There is only the trivial solution
• There are infinitely many solutions in addition to the trivial solution
Example: Solve the homogeneous system of linear equations by GaussJordan elimination
2 x1 +2 x2 x3
+ x5 0
x1 x2 2 x3 -3x 4 x5 0
x1 x2 2 x3
x5 0
x3 x4 x5 0
Solution: The augmented matrix is
The augmented matrix is
2 2 1 0 1
1 1 2 3 1
1 1 2 0 1
0 0 1 1 1
1
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
The corresponding system of equations is
+ x5 0
x1 +x2
x3
x5 0
x4
Solve for the leading variables yields
x1 x2 x5
x3 x5
x4 0
The general solution is
x1 s t , x2 s, x3 t , x4 0, x5 t
Note: the trivial solution is obtained when s = t = 0
0
Theorem 1.2.1
A homogeneous system of linear equations with more unknowns
than equations has infinitely many solutions.
Remark
•This theorem applies only to homogeneous system!
• A nonhomogeneous system with more unknowns than equations need
not be consistent; however, if the system is consistent, it will have infinitely
many solutions.