Transcript ENGG2013 Lecture 2 - Chinese University of Hong Kong

ENGG2013
Unit 2 Linear Equations
Jan, 2011.
Linear Equation in n variables
• a1x1 + a2x2+ … + an xn = c
– a1, a2, …, an are called coefficients (real numbers).
– x1, x2,…, xn are variables (or indeterminates).
– c is a constant term (real number).
• Example
– 2x + 3y – 4z = 0.2
• Non-example
– x2+y2=1
kshum
ENGG2013
2
Geometry of a linear equation
Three variables: plane
Two variables: straight line
ax + by = c
ax + by + cz = d
kshum
ENGG2013
3
System of linear equations
• A system of linear equations (or linear system)
is a collection of one or more linear equations.
– for example:
• A solution is a list of numbers
(s1, s2, …, sn) which satisfies all equalities after
substituting xi by si, for i =1,2,…,n.
• The set of all solutions is called the solution
set.
kshum
ENGG2013
4
Nutrition problem
• Find a combination of food A, B, C and D in order to satisfy the
nutrition requirement exactly.
Food A
Food B
Food C
Food D
Requirement
Protein
9
8
3
3
5
Carbohydrate
15
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
• Let xA, xB, xC and xD be the amount of food A, B, C and D
respectively.
kshum
ENGG2013
5
Formal notation
• Given a system of m linear equations in n
variables
Double
subscripts
the solution set is defined as
kshum
ENGG2013
6
Review of set notation
• Set of Greek letters = {,,,,,,,,,,
,,,,,,,,,,,,,}
finite
• Set of prime numbers =
{2,3,5,7,11,13,17,23,29,31,37,41, …}
Countably infinite
• Sphere with radius r centered at origin
= {(x,y,z): x2+y2+z2=r2}
Uncountably infinite
kshum
ENGG2013
7
Examples of solution sets
{ (x,y): ax + by = c }
z
5
0
y
-5
1
0.5
1
0.5
0
0
-0.5
y
-0.5
-1
-1
x
x
kshum
ENGG2013
8
Consistency
• A linear system is called consistent if there is
at least one solution, in other words, if the
solution set is non-empty.
y
y
Inconsistent,
no solution
Consistent
x
x
kshum
ENGG2013
9
Classification
Linear
System
Inconsistent
Consistent
(no solution)
Tasks:
Determine whether a linear
system is consistent.
If yes, find all solutions.
kshum
Unique solution
ENGG2013
Infinitely many
solutions
10
Short-hand notation using matrix
(2 rows, 4 columns)
Usually called the augmented matrix
(4 rows, 3 columns)
kshum
ENGG2013
11
The nutrition example
kshum
ENGG2013
12
Elementary row operations
1. Interchange two rows
2. Multiply a row by a non-zero constant
3. Replace a row by the sum of itself and a
constant multiple of another row
Facts: Elementary row operations do not change the solution(s).
(There is no loss, and no gain, of information.)
kshum
ENGG2013
13
Illustration – row interchange
kshum
ENGG2013
14
Illustration – Multiply by constant
2
kshum
ENGG2013
2
15
Illustration – Row replacement
(1)  (1) – (2)
kshum
ENGG2013
(1)  (1) – (2)
16
How to solve?
• Idea: Apply the three kinds of informationlossless elementary row operations, and
transform the linear system into one which is
easier to solve.
Linear system in upper triangular
matrix form can be easily solved by
backward substitution
kshum
ENGG2013
17
Carl Friedrich Gauss
(1777~1855)
The old Deutsche 10-Mark note
kshum
ENGG2013
18
Gaussian elimination
• Step 0: Write the linear system in matrix
format
• Step 1: Try to transform the matrix into upper
triangular form
• Step 2: Solve for the variables one by one, in
backward order
kshum
ENGG2013
19
Example
1
(row
operations)
Solve
(1)
(2)
(3)
(2)  (2) – (1)
(3)  (3) + (2)/2
kshum
ENGG2013
20
Example 1 (backward sub.)
Upper triangular
Solution: x=1/3, y = –5/3, z = 7/3
(unique solution)
(3)  z = 7/3
(2)  – 2y – (7/3) = 1  y = –5/3
(1)  x+(–5/3)+(7/3) = 1  x = 1/3
kshum
ENGG2013
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
21
Example 2 (row operations)
Solve
(2)  (2) – (1)
(3)  (3) – (1)
(3)  (3) – 2  (2)
kshum
ENGG2013
22
Example 2 (backward sub.)
(1)
(2)
z can be taken as a
free variable.
Let z to be any real
number.
Solution:
x= 2– 2z,
y = –1–z,
z = any real number.
From (2), y = –1 – z
Solution set = {(2 – 2z, –1–z, z): z is any real no.}
(Infinitely many solutions)
From (1), x +(–1 – z)+3z = 1  x = 2 – 2z
kshum
ENGG2013
Note: You can let y to
be the free variable as well,
and obtain the solutions in
terms of y.
23
Example 2 (cont’d)
Solution: x= 2– 2z, y = –1–z, z = any real number
Solution set = {(2 – 2z, –1–z, z): z is any real no.}
• Verification
4
2
0
-2
z
– 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
-4
-6
-8
-5
-10
-5
0
0
5
5
kshum
10
ENGG2013
y
10
x
24
Example 3 (row operations)
Solve
(2)  (2) – (1)
(3)  (3) – (1)
(3)  (3) – 2(2)
kshum
ENGG2013
25
Example 3 (cont’d)
Contradiction, cannot be true
Answer:
the linear system is inconsistent
kshum
ENGG2013
26
Example 3 (picture)
2.5
2
1.5
z
Cross-section
1
0.5
0
No common intersection
-1
-1.2
-1.4
1
-1.6
0
-1
-2
-1.8
-3
y
-2
kshum
An infinitely long triangular tube
is formed by the three planes
-4
-5
x
ENGG2013
27
Key concepts
• Three kinds of elementary row operations
– The solution set is invariant under any elementary row
operation
• Gaussian elimination
– Transform a linear system to upper triangular form
– Backward substitution
• Three types of solutions
– No solution
– Unique solution
– Infinitely many solutions
kshum
ENGG2013
28