Course: Math 458, Numerical Methods, Fall 2022
Prerequisite: 1 from (MATH 225 or MATH 245)
Course Content: Rounding errors in digital computation; solution of linear algebraic systems; Newton's method for nonlinear systems; matrix eigenvalues; polynomial approximation; numerical integration; numerical solution of ordinary differential equations.
Last update: 18 August 2022
For enrollment information (i.e. if you are unable to enroll in this class), please contact Amy Yung, amy@usc.edu
Safety Protocols
Instructor: Steven Heilman, stevenmheilman(@-symbol)gmail.com
Office Hours: Tuesdays, 8AM-10AM, on zoom [link posted on blackboard]
Lecture Meeting Time/Location: Mondays, Wednesdays, and Fridays, 12PM-1250PM, CPA 156
TA: Chuhuan Huang, chuhuanh(@-symbol)usc.edu
TA Office Hours: Held in the Math Center, with schedule provided at that link.
Discussion Section Meeting Time/Location:
Textbook: There is no required textbook. The first course resource is a freely available book:
Numerical Computing with Matlab by Cleve Moler (the inventor of Matlab), available online at: https://www.mathworks.com/moler/chapters.html. Some other textbooks that we will follow are:
Numerical Analysis: Mathematics of Scientific Computing, Kincaid and Cheney
Numerical Mathematics and Computing, Cheney and Kincaid
Matrix Computations, Golub and van Loan
Software: Matlab is freely available as a download for USC students. You should download and install this software on your personal computer. Instructions for downloading and installing this software can be found here: https://software.usc.edu/matlab/. If you have not done so already, you should create a Mathworks account, associated to your USC email address (https://www.mathworks.com/login). Once you have installed Matlab, you should then install the NCM package (available at the bottom of this page: https://www.mathworks.com/moler/chapters.html). Once the NCM package is installed, you can access some of its features by just typing "ncmgui" in the Matlab command line.
Extra Credit Project: There will be an optional extra credit project, where students will create a computer program that plays a game (such as connect four or chess) in Matlab, and the top performers of a tournament will be awarded around 1% to 3% extra credit points for the course. The project would be due in the last week of class, and the "finals" of the tournament would occur in class during this time as well. Students can work in groups of up to three, and if a team wins some amount of extra credit, that credit will be split evenly among the participants. Also, copying any code from any online resource or from another student will result in automatic disqualification. Since I will be running the finals on a Microsoft Surface Tablet (without much memory or processing power), you are not allowed to use any functions from any extra Matlab toolboxes, other than those functions in the most basic installation of Matlab.
Here is the code for the Connect Four project. The function contained in the file that plays the game that you need to beat is called "blockplayer". The other function "randomplayer" just makes a random move among all available moves.
The final submission for your project should be a Matlab file, due Thursday, December 1 at 3PM PST, to be uploaded under the Assignments tab in blackboard. Your Matlab file should be a function that shares the same syntax as the "blockplayer" program, i.e. it should be a function whose input is (1) the current gamestate, (2) an integer 1 or -1 (denoting if you are the first or second player, respectively), and (3) the argument cnum (defining the number of tokens in a row that determines the winner). The output of your program (i.e. the output of the function) should then be the next game state after your player makes one move. The "finals" of the tournament will he held on the last day of class. Two different teams will compete in a best of ten series, alternating who goes first or second. In the case of a tie, the number of games or the size of the game board will be increased. (So make sure your program can play on different sized gameboards, as blockplayer does.) Depending on the number of submitted projects we will do either a single-elimination, double-elimination, or round-robin tournament. First place gets 6%, second place gets 5%, third place gets 4% and fourth place gets 3% extra credit points added to their final course score (shared according to the number of participants on your team). All other participants who create a program that defeats the "blockplayer" program receive 2% extra credit (shared among participants on your team, e.g. if you have two people on your team, and you don't get top four in the tournament but you beat the blockplayer program, you each receive 1% extra credit.)
Lastly, your program should take a reasonable amount of time to make a move in the game. In order to participate in the tournament, your program should not take much longer than a second or so per move. If you take e.g. longer than 10 seconds to make a move in the game, your program cannot participate in the finals of the tournament (since one game would just take too long).
Exam 1: Wednesday, September 28, 12PM-1250PM, CPA 156
Exam 2: Friday, November 4, 12PM-1250PM, CPA 156
Final Exam: Friday, December 9, 11AM-12PM Noon, CPA 156 + take home coding assessment
Other Resources: An introduction to mathematical arguments, Michael Hutchings, An Introduction to Proofs, How to Write Mathematical Arguments
Email Policy:
Exam Procedures: Students must bring their USCID cards to the midterms and to the final exam. Phones must be turned off. Cheating on an exam results in a score of zero on that exam. Exams can be regraded at most 15 days after the date of the exam. This policy extends to homeworks as well. All students are expected to be familiar with the USC Student Conduct Code. (See also here.)
Accessibility Services: If you are registered with accessibility services, I would be happy to discuss this at the beginning of the course. Any student requesting accommodations based on a disability is required to register with Accessibility Services (OSAS) each semester. A letter of verification for approved accommodations can be obtained from OSAS. Please be sure the letter is delivered to me as early in the semester as possible. OSAS is located in 301 STU and is open 8:30am-5:00pm, Monday through Friday.
https://osas.usc.edu/
213-740-0776 (phone)
213-740-6948 (TDD only)
213-740-8216 (fax)
OSASFrontDesk@usc.edu
Discrimination, sexual assault, and harassment are not tolerated by the university. You are encouraged to report any incidents to the Office of Equity and Diversity http://equity.usc.edu/ or to the Department of Public Safety http://capsnet.usc.edu/department/department-public-safety/online-forms/contact-us. This is important for the safety whole USC community. Another member of the university community - such as a friend, classmate, advisor, or faculty member - can help initiate the report, or can initiate the report on behalf of another person. The Center for Women and Men http://www.usc.edu/student-affairs/cwm/ provides 24/7 confidential support, and the sexual assault resource center webpage sarc@usc.edu describes reporting options and other resources.
Exam Resources: Some practice exams for a course similar to ours appear here. See also here here and here. See also the collection of exams here. These exams might be quite different than our exam, or cover material in a different order than our course.
Homework Policy:
Grading Policy:
Tentative Schedule: (This schedule may change slightly during the course.)
Week | Monday | Tuesday | Wednesday | Thursday | Friday |
1 | Aug 22: Matlab and NCM Toolbox | Aug 23 | Aug 24: 2.1, Floating Point Arithmetic | Aug 25: Homework 1 due | Aug 26: 2.2, Loss of Significance |
2 | Aug 29: 3.1, One Variable Nonlinear Equations | Aug 30 | Aug 31: 3.2, Newton's Method | Sep 1: Homework 2 due | Sep 2: 3.2, Newton's Method |
3 | Sep 5: No class | Sep 6 | Sep 7: 4.1, Review of Linear Algebra | Sep 8: Homework 3 due | Sep 9: 4.1, Multiplying Matrices |
4 | Sep 12: 4.2, Gaussian Elimination, Cholesky Decomposition | Sep 13 | Sep 14: 4.4, Matrix Norms, Errors | Sep 15: Homework 4 due | Sep 16: 4.8, Bounding Errors |
5 | Sep 19: 5.1, Eigenvalues, Power Method | Sep 20 | Sep 21: 5.3, QR Decomposition, Least Squares | Sep 22: Homework 5 due | Sep 23: 5.4 SVD, Pseudoinverse |
6 | Sep 26: 5.4, Dimension Reduction, Random SVD | Sep 27 | Sep 28: Exam 1 | Sep 29: No homework due | Sep 30: 6.1, Polynomial Interpolation |
7 | Oct 3: 6.1, Polynomial Interpolation | Oct 4 | Oct 5: 6.4, Spline Interpolation | Oct 6: Homework 6 due | Oct 7: 6.4, Spline Interpolation |
8 | Oct 10: 7.1, Numerical Partial Differentiation | Oct 11 | Oct 12: 7.2, Numerical Integration | Oct 13: No class | Oct 14: No class |
9 | Oct 17: 7.2, Numerical Integration | Oct 18 | Oct 19: 7.3, Gaussian Quadrature | Oct 20: Homework 7 due | Oct 21: 7.3, Gaussian Quadrature |
10 | Oct 24: 8.1, Solving ODEs | Oct 25 | Oct 26: 8.1, Solving ODEs | Oct 27: Homework 8 due | Oct 28: 8.3, Runge-Kutta Methods |
11 | Oct 31: 8.4, Multistep Methods | Nov 1 | Nov 2: 8.7, Boundary-Value Problems | Nov 3: No homework due | Nov 4: Exam 2 |
12 | Nov 7: 8.8, Shooting Methods | Nov 8 | Nov 9: 8.9, Finite Differences | Nov 10: Homework 9 due | Nov 11: No class |
13 | Nov 14: 8.10, Collocation | Nov 15 | Nov 16: 9.2 PDEs | Nov 17: Homework 10 due | Nov 18: 9.3 PDEs |
14 | Nov 21: Leeway | Nov 22 | Nov 23: No class | Nov 24: No class | Nov 25: No class |
15 | Nov 28: Leeway | Nov 29 | Nov 30: Review of course | Dec 1: Homework 11 due | Dec 2: Review of course |
Advice on succeeding in a math class:
Homework
Homework .tex files
Exam Solutions
Supplementary Notes