1. Gauss elimination - teacher 3 PDF

Preview

Summary

teacher 3...

Description

§1.1 and §1.2: Linear Systems and Gauss Elimination A linear system of m equations and n variables x1 , x2 , . . . , xn is a system in the form (1)

a11 x1 + a12 x2 + . . . + a1n xn

=

b1

a21 x1 + a22 x2 + . . . a2n xn

=

b2 .. .

am1 x1 + am2 x2 + · · · + amn xn

=

bm

where a11 , a12 , . . . , a1n , . . . , am1 , . . . , amn , b1 , . . . , bm are constants. Fact: Any system of linear equations has one of the following cases: (1) The system has a unique solution (2) The system has infinitely many solutions (3) The system has NO solution. If the system satisfies case (1) or case (2) then we say the system is consistent. If the system satisfies case (3) then we say the system is inconsistent. A matrix is a rectangular array of elements. A linear system can be represented by a so-called augmented matrix. For example to the following system x1 + x2 − x3

=

3x 1 − 2x 3

=

−7

2x2 + x3

=

11

correspond the following augmented matrix   1 1   3 0  0

2

−1 −2 1

−1

 .. . −1   .. . −7   .. . 11

We can change an augmented matrix by operations on the rows without changing the solutions of the system. Operations that will produce equivalent systems of linear equations: (1) Interchange two equations (2) Multiply an equations by a nonzero constant (3) Add a multiple of an equations to another equation Operations that will produce equivalent augmented matrices: (1) Interchange two rows (2) Multiply a row by a nonzero constant (3) Add a multiple of a row to another row. Definition 0.1. Two matrices are called row equivalent if one of them can be obtained from the other one by a sequence of row operations. A matrix is in row echelon form (ref) if it satisfies the following conditions: (1) If a row consists entirely of zeros then it has to be at the bottom of the matrix. (2) The first nonzero element in any row must be 1 called the leading one. 1

2

(3) In any two consecutive rows the leading one in the lower row must be to the right of the leading one in the upper row. A matrix is in reduced row echelon form (rref) if it satisfies the following conditions: (1) It is ref (2) All elements in a columns with leading one must be zeros. Example 0.2. Determine if the matrix in ref or rref   1 0 0 4 (1)  0 1 0 7   0 0 1 −1 1 0 0 (2)  0 1 0    0 0 1 0 1 −2 0 1  0 0 0 1 3   (3)   0 0 0 0 0  0 0 0 0 0   0 1 2 6 0 (4)  0 0 1 −1 0  0 0 0 0 0 Example 0.3. Determine the solution of the linear system with the augmented matrix in rref 

 1  (1)  0  0   1  (2)  0 

0

0

1

0

0

1

.. . 3 .. . 7 .. . −2 . 4 .. . 7 .. . −1 ..

0

0

1

0

0

0

1

 0   0 (3)    0 

1

−2

0

1

0

0

1

3

0

0

0

0

0

0

0

0

0

 0   0 (4)    0 

1

−2

0

1

0

0

1

3

0

0

0

0

0

0

0

0





0

    



2   1  

3  .. . 1   .. . −1    .. . 0   .. . 0  .. . 1   .. . −1    .. . 0   .. . 2

Solution: (1) It is clear that the solution x = 3, y = 7, z = −2

3

(2) Since the matrix is in rref then it cannot be reduced any more. In fact the solution is x 1 + 4x 4 x 2 + 7x 4

= =

2 1

x3 − x4

=

3.

The variables x4 is called a free variable because the fourth column has no leading one. Hence, if x4 = t then the final solution is x1

=

2 − 4t

x2

=

1 − 7t

x3

=

3+t

x4

=

t (free variable)

(3) Again the matrix is in rref and columns 1, 3 and 5 have no leading one. Hence x1 , x3 and x5 are free variables with x1 = r, x3 = s and x5 = t and the solution is x1

=

r

x2

=

1 + 2s − t

x3

=

s

x4

=

−1 − 3x5

x5

=

t

(4) The matrix is in rref and cannot be reduced anymore. Note that the last row represents the equation 0 = 2. Hence, the system has no solution. 1. Gauss-Jordan Elimination This is a method used to reduce a matrix into rref, this means that starting with any matrix A, there is a method (algorithmic) to find a matrix in rref form row equivalent to A. The algorithm was explained in class. A =⇒ hboxrref (A) Example 1.1. Solve by Gauss-Jordan Elimination



 1  Solution:  2  1



 1   0  0



 1   0  0

2

−3

1

−2

−3

4

2 1 0

x1 + 2x2 − 3x3

=

6

2x1 − x2 + 4x3

=

1

x1 − x2 + x3

=

3

   . .. −3 .. 6   6     1 2 −3 .  −1   −2R1 + R2 → R2 . . . . R → R ∼ ∼  0 −5 10 . −11  2 2 −1 4 . 1  −R1 + R3 → R3   5  . . 0 −3 4 .. −3 −1 1 .. 3    .. ... 6  6   1 2 −3 .     .. .. (3R2 + R3 → R3 ) ∼  0 1 −2 . 11/5  −1 R3 → R3 ∼ . 11/5     2 . ... −3 0 0 −2 .. 18/5  6   (Note that the last matrix is in ref and the value of x3 = −9/5. 11/5   2

. −3 .. . −2 .. . 1 .. −9/5

4

Moving forward, back substitution can be used to get x1 and x2 )    ..    1 2 0 . 3/5   1 2R3 + R2 → R2    . ∼  0 1 0 .. −7/5  (−2R2 + R1 → R1 )  0 3R3 + R1 → R1    . 0 0 1 .. −9/5 0

0

0

1

0

0

1

.. . 17/5 .. . −7/5 .. . −9/5



  . 

This implies that x1 = 17/5, x2 = −7/5 and x3 = −9/5. Substitute these values in the above system to make sure the solution is correct. Example 1.2. Solve by Gauss-Jordan Elimination x1 + 3x2 − 2x3 + 2x5 2x1 + 6x2 − 5x3 − 2x4 + 4x5 − 3x6

= 0 = −1

5x3 + 10x4 + 15x6

=

5

2x1 + 6x2 + 8x4 + 4x5 + 18x6

=

6

Solution: The rref is (check) 

 1   0    0 

3

0

4

2

0

0

1

2

0

0

0

0

0

0

1

0 0 0 0 0 0 The free variables chosen are x2 = r, x4 = s and x5 = t.

 .. . 0   .. . 0    .. . 1/3   .. . 0 The general solution is

x1 x2

= =

−3r − 4s − 2t r

x3

=

−2s

x4

=

s

x5

=

t

x6

=

1/3.

Definition 1.3. A linear system of equations is called homogeneous if the constant terms are all zeros. Remarks: (1) Note that every homogeneous system is consistent because xi = 0 for all is a solution. The solution xi = 0 for all i is called the trivial solution. (2) A homogeneous system with more unknown than equations will always have infinite number of solutions. That is NOT the case for non-homogeneous systems. Theorem 1.4. If a homogeneous linear system has n unknowns and if the reduced form of its augmented matrix has r nonzero rows then the system has n − r free variables. Example 1.5. Discuss the   1 −3 7 2   0 1 2 −4 (1)    0 0 1 6  0

0

0

0

solution of the linear system with the following ref matrices.  .. . 5   .. . 1    .. . 9   .. . 1

5



 1   0 (2)    0 

−3

7

2

1

2

−4

0

1

6

0

0

0

 1   0 (3)    0 

−3

7

2

1

2

−4

0

1

6

0

0

1

0



0

.. . .. . .. . .. . .. . .. . .. . .. .

 5   1    9  

0

 5   1    9  

0

Solution: (1) The system has NO solution because the last row produce 0 = 1 (2) The system has infinite number of solutions with x4 a free variable. (3) The last row gives x4 = 0. Use back substitution to get x3 = 9, x2 = −17, x1 = −109 Facts about ref and rref (1) Every matrix has a unique rref. (2) ref is NOT unique. (3) A column with a leading one is called pivot column....