Solving Linear systems of Equations-Gauss elimination method

Solving Linear systems of Equations-Gauss elimination method

1. Linear systems and
Solution of Linear
Systems using
Matrices
The Gauss-Elimination
Method
Dr. Hina M. Dutt
[email protected]

2. Linear Equation in nvariables
•a
1x
1+a
2x
2+… +a
nx
n=c
–a
1, a
2, …, a
nare called coefficients(real numbers).
–x
1, x
2,…, x
nare variables(or indeterminates).
–cis a constant term (real number).
•Example
–2x+ 3y–4z= 0.2
•Non-example
–x
2
+y
2
=1

3. Geometry of a linear equation
Two variables: straight line
ax + by = c
Three variables: plane
ax + by +cz = d

4. System of linear equations
•Asystem of linear equations (or linear system)
is a collection of one or more linear equations.
–for example:
•A solutionis a list of numbers
(s
1, s
2, …, s
n) which satisfies all equalities after
substituting x
iby s
i, for i=1,2,…,n.
•The set of all solutions is called the solution
set.

5. Nutrition problem
•Find a combination of food A, B, C and D in order to satisfy the
nutrition requirement exactly.
•Let x
A, x
B, x
Cand x
Dbe the amount of food A, B, C and D
respectively.
Food A Food B Food C Food DRequirement
Protein 9 8 3 3 5
Carbohydrate15 11 1 4 5
Vitamin A 0.02 0.003 0.01 0.006 0.01
Vitamin C 0.01 0.01 0.005 0.05 0.01

6. Formal notation
•Given a system of mlinear equations in n
variables
the solution set is defined as
Double
subscripts

7. Consistency
•A linear system is called consistentif there is
at least one solution, in other words, if the
solution set is non-empty.
x
y
Inconsistent,
no solution
x
y
Consistent

8. Classification
Linear
System
Inconsistent
(no solution)
Consistent
Unique solution
Infinitely many
solutions
Tasks:
Determine whether a linear
system is consistent.
If yes, find all solutions.

9. Types of Solutions
Consistent System
One solution
Consistent System
Infinite solutions
Inconsistent System
No solution

10. 10

11. 11

12. Using Matrices to Solve Systems of Equations
Augmented Matrix –a matrix that is used to solve a system of equations.
Augmented matrix2 1 5
4 6 2


 1 1 1 0
3 2 4 9
1 1 1 0





 Augmented matrix

13. Using Matrices to Solve Systems of Equations
Given the augmented matrix, write the system of equations.5 1 9
2 8 7


 3 6 2 8
2 0 5 13
1 3 7 12



 

System of Equations



 System of Equations



 





14. The nutrition example

15. Using Matrices to Solve Systems of Equations
The use of Elementary Row Operations is required when
solving a system of equations using matrices.
Elementary Row Operations
I. Interchange two rows.
II. Multiply one row by a nonzero number.
III. Add a multiple of one row to a different row.

16. Using Matrices to Solve Systems of Equations
Row Equivalent Matrices
Two matrices are row equivalent if one
matrix can be transformed into the other
matrix by a sequence of elementary row
operations.
Fact about Row Equivalent Matrices
If the augmented matrices of two linear
systems are row equivalent, then the two
systems have the same solutions set.

17. Using Matrices to Solve Systems of Equations
The solution to the system of equations is complete when the augmented
matrix is in Row Echelon Form.
Row Echelon Form1 3 7 2
0 1 5 3
0 0 1 6





A matrixis in row echelon form(ref) when it satisfies the following
conditions.
1.The first non-zero element in each row, called the leading entry, is 1.
2. Each leading entry is in a column to the right of the leading entry in
the previous row.
3. Rows with all zero elements, if any, are below rows having a non-zero
element.1 4 5
0 1 8


 1 4 7 5
0 1 7 11
0 0 0 0






18. 18
Row Echelon forms
Using Matrices to Solve Systems of Equations

19. Using Matrices to Solve Systems of Equations
Reduced Row Echelon Form1 0 0 9
0 1 0 3
0 0 1 7





1. The matrix is in row echelon form (i.e., it satisfies the three
conditions listed for row echelon form.
2. The leading entry in each row is the only non-zero entry in its
column.1 0 4
0 1 6


 1 0 0 4
0 1 0 12
0 0 0 0





A matrixis in reduced row echelon form(rref) when it satisfies the
following conditions.

20. 20
Using Matrices to Solve Systems of Equations
Reduced Row Echelon Form

21. Gaussian elimination (ref)
•Step 1: Write the linear system in
augmented matrix form.
•Step 2: Transform the matrix into
row echelon form.
•Step 3: Solve for the variables
one by one, in backwardorder.
Carl Friedrich Gauss

22. Example 1 (row operations)
Solve:

23. Example 1 (row operations)
Solution:

24. Example 1 (backward sub.)
Upper triangular
(3)z = 7/3
(2) –2y –(7/3) = 1 y = –5/3
(1) x+(–5/3)+(7/3) = 1 x = 1/3
Verify:
x+y+z = 1/3 –5/3 + 7/3 = 3/3 = 1
x–y = (1/3)–(–5/3) = 6/3 = 2
y+2z = (–5/3)+2(7/3) = 9/3 = 3
Solution: x=1/3, y = –5/3, z = 7/3
(unique solution)

25. Example 2 (row operations)
Solve:

26. Example 2 (row operations)
Solution:

27. Example 2 (backward sub.)
zcan be taken as a
free variable.
Let zto be any real
number.
(1)
(2)
From (2), y = –1 –z
From (1), x +(–1 –z)+3z = 1 x = 2 –2z
Solution:
x= 2–2z,
y = –1–z,
z = any real number.
Solution set = {(2 –2z, –1–z, z): z is any real no.}
(Infinitely many solutions)
Note: You can let y to
be the free variable as well,
and obtain the solutions in
terms of y.

28. Example 2 (cont’d)
•Verification
–x+y+3z
=(2 –2z) + (–1 –z) + 3z
= 1
–x+2y+4z
=(2 –2z) + 2(–1 –z) + 3z
= 0
–x+3y+5z
=(2 –2z) + 3(–1 –z) + 5z
= –1
Solution: x= 2–2z, y = –1–z, z = any real number
Solution set = {(2 –2z, –1–z, z): z is any real no.} -5
0
5
10
-5
0
5
10
-10
-8
-6
-4
-2
0
2
4
x
y
z

29. Example 3 (row operations)
Solution:

30. Example 3 (row operations)
Solution:

31. Example 3 (cont’d)
Contradiction, cannot be true
Answer:
the linear system is inconsistent

32. Example 3 (picture)
Cross-section-5
-4
-3
-2
-1
0
1
-2
-1.8
-1.6
-1.4
-1.2
-1
0
0.5
1
1.5
2
2.5
x
y
z
No common intersection
An infinitely long triangular tube
is formed by the three planes

33. Practice Questions
33

34. Practice Questions
•Introductory Linear Algebra (9thEdition) by B. Kolman
–Exercise 2.2
•Q.1--Q.17
•Linear Algebra with Applications (8th Edition) by Gareth Williams
–Exercise 1.1
•Q.1--Q.9
•Advanced Engineering Mathematics (9th Edition) by Erwin Kreyszig
–Exercise 7.3
•Q.1--Q.16
34