DS2810
Lecture 3
Solving Linear systems
Gaussian Elimination
By. Professor Wu
In-class Extra credit Policy Change
- The previous policy is that you just need to submit something that showed you came to class and
worked on the questions you would get the credit.
- This resulted in several students cheating and didn’t bother to attempt the last class exercise (this
defeats the spirit of the extra credit)
- New policy:
- All class work would have to be submitted to get the credit.
- You would have to submit a separate image for each exercise
- We will extend the submission time to 11:00pm to give you extra time.
- Please submit only in the following formats: .py, .pdf, .jpg, .png (canvas cannot read .HEIC
or other formats)
-
- For class 1, we will still accept partial work.
- For class 2, you will have till the end of today to re-submit all the work (if you didn’t submit everything)
- Going forward, you would have to submit everything.
Homework policy
- Original Policy: No need to show work
- Change my mind:
- I really want you to get a lot of latex practice
- It makes it impossible to give partial credits.
- It is just too easy to copy someone else’s latex code.
- If you work out the homework yourself,
- it should look sufficiently different from other people’s work
- But if you only have the solution, everybody’s work will look the same.
Also show everybody where the class video lectures are at
Extra Office Hours
The TA and I really want everyone to learn a lot and do well in this class.
- We talked and the TAs volunteered to give you guys extra office hours.
Tuesday (TA=Neel) : 10:30 - 11:30am
Tuesday (TA=Ashley): 5:00 - 6:00pm
Friday (TA=Alex) : 12:00 - 1:00pm
Friday (TA=Bindra): 1:00-2:00pm
Here is a problem you may have seen in the SAT
A concert charges $20 for adult tickets and $10 for student tickets. If the concert sold
100 tickets and made $2000, how many of each type of tickets were sold?
Take out a piece of paper and try to solve this problem.
Here is a problem you may have seen in the SAT
A concert charges $20 for adult tickets and $10 for student tickets. If the concert sold
100 tickets and made $2000, how many of each type of tickets were sold?
The problem gives us 2 pieces of information.
- Let “a” be the number of adult tickets sold
- Let “s” be the number of student tickets sold
Then, we know that
1. adult + student is 100 tickets or a + s = 100
2. 20a + 10s = 2000
With 2 equations and 2 unknowns, you should be able to find a and s.
The standard way we learn to solve this is through substitution
This approach is useful with a only a few
variables to solve, but what if we have a
bigger problem?
It would take a long time to solve this.
What’s is the alternative?
Gaussian Elimination.
Let’s look at a simple example
Notation Simplification
Notice that when we use the Gaussian Elimination so far, we
have to copy x1, x2 over and over again. This is really not
necessary. Instead, we can simplify the copying by representing
the linear system with matrix notation.
Let’s now solve a linear system of 4 equations
Once we obtain a 1 in the We can now ignore the 1st row
leftmost term, it's easy to zero and column and repeat the
out all other 1st terms. process in the smaller
sub-matrix.
Let’s now solve a linear system of 4 equations
This is called the row echelon
form, and the problem is
basically solved
Let’s Try it yourself
Step 1. Write it into augmented matrix form
Step 2. Scale one of the equation’s 1st term to be one
Step 3. Zero out all first terms in the matrix
Step 4. You now have a smaller matrix, repeat steps 1 to 3
Make sure you can get this solution
It takes a lot of practice to get it, try again
Step 1. Write it into augmented matrix form
Step 2. Scale one of the equation’s 1st term to be one
Step 3. Zero out all first terms in the matrix
Step 4. You now have a smaller matrix, repeat steps 1 to 3
Once you have a solution, plug x back in and see of all the
statements are still True
Don’t worry if you got it wrong, it takes a lot of practice
If you didn’t get the right solution, go back home and try again.
It is important for you to write out all the steps you took to reach
the solution. (This allows you to go back and review your logic
flaw if you made a mistake)
Solving them in python
How do you get the RREF with sympy
To automatically obtain the RREF matrix.
Download sympy from sympy.org.
>>> from sympy import *
>>> M = Matrix([ [1,0,3,7],
Remember that the solution was
... [2,1,0,2],
... [2,4,1,4] ])
>>> print(M_rref[0])
Matrix([ [1, 0, 0, 1],
[0, 1, 0, 0],
[0, 0, 1, 2] ])
Last Exercise
1. Find the x vector that satisfy these equation by hand
a. Find the REF
b. Find the RREF (this should give u the same solution)
2. Once you solve it, use python to get the answer
( You should have the same answer if done correctly)
3. Download sympy and obtain the RREF
4. Remember to submit your result
(Make sure to include your name)
You are welcome to ask a friend or TA for help if you are confused.
