Introduction to Numerical Methods

Time:2:30PM - 3:45PM, Tuesdays and Thursdays, Spring 2015.
Place:Engineering Hall, Room 2535
Instructor:Mridul Aanjaneya (aanjneya@cs.wisc.edu)
Office:Computer Sciences building, Room 1349
Office hours:2:00PM - 4:00PM (Wednesdays)
TA:Divy Vasal (divy@cs.wisc.edu)
Office:Computer Sciences building, Room 1302
Office hours:4:00PM - 6:00PM (Mondays)

Email policy: You are welcome to email the instructor about class-related issues. Please start your subject line with "CS412:". However, please do not always count on an immediate reply. Although most questions will be answered quickly, in the worst case you will receive a reply during (or shortly after) the instructors' next scheduled office hours. It is also recommended to post homework-related questions on the discussion forum instead of emailing the instructor so that other fellow students can benefit from it.

Office hours policy: If you need to approach the instructor or the TA outside of their office hours, please schedule an appointment ahead of time.

Announcements

Schedule

Date Topic Notes
Tue, Jan 20 Introduction. Types of Errors.

Reading: [MH02] Sections 1.1-1.2.2

Notes: Lecture 1
Thu, Jan 22 Number representations, truncation and rounding.

Reading: [JK04] Section 1.2

Notes: Lecture 2
Tue, Jan 27 Machine epsilon, Newton's method.

Reading: [JK04] Sections 2.1,2.4
            [MH02] Section 5.5.3

Notes: Lecture 3
Thu, Jan 29 Fixed point iteration.

Reading: [JK04] Section 2.1
            [MH02] Section 5.5.2

Notes: Lecture 4
Tue, Feb 03 Order of convergence, multiple roots.

Reading: [JK04] Section 2.4
            [MH02] Section 5.4

Notes: Lecture 5
Thu, Feb 05 Bisection search, Secant method.

Reading: [JK04] Sections 2.2,2.4
            [MH02] Sections 5.5.1,5.5.4

Notes: Lecture 6
Tue, Feb 10 Secant method, interpolation.

Reading: [JK04] Section 4.2
            [MH02] Section 7.1

Notes: Lecture 7
Thu, Feb 12 Polynomial interpolation, monomial basis.

Reading: [JK04] Section 4.2
            [MH02] Section 7.3.1

Notes: Lecture 8
Tue, Feb 17 Lagrange interpolation, Newton interpolation.

Reading: [JK04] Sections 4.3, 4.4
            [MH02] Sections 7.3.2, 7.3.3

Notes: Lecture 9
Thu, Feb 19 Newton interpolation, divided differences.

Reading: [JK04] Section 4.4
            [MH02] Section 7.3.3

Notes: Lecture 10
Tue, Feb 24 Accuracy of interpolation, Chebyshev points.

Reading: [JK04] Section 4.5
            [MH02] Section 7.3.5

Notes: Lecture 11
Thu, Feb 26 Piecewise polynomial interpolation.

Reading: [JK04] Section 5.3

Notes: Lecture 12
Tue, Mar 03 Cubic spline interpolation.

Reading: [JK04] Section 5.3
            [MH02] Section 7.4.2

Notes: Lecture 13
Thu, Mar 05 Cubic Hermite splines.

Reading: [MH02] Section 7.4.1

Notes: Lecture 14
Tue, Mar 10 Midterm #1
Thu, Mar 12 Vector and matrix norms.

Reading: [JK04] Section 3.1
            [MH02] Sections 2.3.1-2.3.2

Notes: Lecture 15
Tue, Mar 17 Condition number, upper triangular systems.

Reading: [JK04] Section 3.3
            [MH02] Sections 2.3.3-2.3.5

Notes: Lecture 16
Thu, Mar 19 LU decomposition.

Reading: [JK04] Section 3.5
            [MH02] Sections 2.4.3-2.4.4

Notes: Lecture 17
Tue, Mar 24 Pivoting.

Reading: [JK04] Section 3.4
            [MH02] Section 2.4.5

Notes: Lecture 18
Thu, Mar 26 Jacobi and Gauss-Seidel methods. Normal equations.

Reading: [JK04] Section 5.1
            [MH02] Sections 3.1-3.2.1

Notes: Lecture 19
Tue, Apr 07 QR factorization. Rectangle rule.

Reading: [MH02] Section 3.4.5.

Notes: Lecture 20
Thu, Apr 09 Error Analysis. Midpoint/Trapezoidal rules.

Reading: [JK04] Section 7.2

Notes: Lecture 21
Tue, Apr 14 Simpson's rule. Generalized error analysis.

Reading: [JK04] Section 7.2

Notes: Lecture 22
Thu, Apr 16 Ordinary differential equations.

Reading: [MH02] Sections 9.1-9.3.1.

Notes: Lecture 23
Thu, Apr 23 Midterm #2
Tue, Apr 28 Stability of ordinary differential equations.

Reading: [MH02] Sections 9.3.1-9.3.3.

Notes: Lecture 24
Thu, Apr 30 Final review.
Notes: Review Notes

Grading policy

Grades will be awarded based on bi-weekly homework, two 75 minute in-class midterms and a mandatory final exam.

The final grade will be the best of the following two schemes:

Scheme 1: 25%x(homework grade) + 20%x(1st midterm grade) + 20%x(2nd midterm grade) + 35%x(final exam grade)
Scheme 2: 25%x(homework grade) + 30%x(best of the 2 midterm grades) + 45%x(final exam grade)

Missing a midterm does not disqualify a student from passing the class (best of the 2 grading schemes above will still apply) but you must take the final exam in order to pass the class. Please note the following exam times on your schedules:

Midterm 1: Tuesday, March 10th, in class (2:30PM - 3:45PM)
Midterm 2: Thursday, April 23rd, in class (2:30PM - 3:45PM)
Final: Wednesday, May 13th, Noland 132 (7:45AM - 9:45AM)

Homework problems will be posted every second week on this webpage, and will be due at midnight on the Tuesday lecture two weeks later. Please use the dropbox at Learn@UW for submission. All homeworks should be typed and no late homework will be accepted. In order to accommodate special unforseen circumstances that may prevent a student from turning in homework on time, the one homework assignment with the lowest grade will not be used in determining the homework grade average.

Collaboration policy: Students are welcome to collaborate with each other on homework problems. However, they must individually turn in their solutions and also mention the names of their collaborators on their homework.

Typing resources: Students can choose their favorite platform for typing out their homework, some commonly used softwares are Microsoft Word, LaTeX, and LyX. Thanks to Alex Ames, here is a LyX guide and associated source files used to generate it.

References

[JK04]John H. Mathews and Kurtis K. Fink. Numerical Methods using MATLAB. Pearson, 4th edition, 2004.
[MH02]Michael T. Heath. Scientific Computing. McGraw Hill, 2nd edition, 2002.