Math 128a - Numerical Analysis - Fall 2009

Lecture: Tuesday and Thursday 3:30-5:00, 3 LeConte

Course Home Page: http://math.berkeley.edu/~strain/128a.F09/index.html

Professor: J Strain, Office 1099 Evans, Hours Monday 2:00-4:00 and Thursday 11:00-12:00, Telephone 642-3656.

GSI Offices and Hours:

Jed Duersch, B3A Evans, Monday 10:00-12:00 and Friday 11:00-1:00

Boris Ettinger, 787 Evans, Monday 9:00-11:00 am and Wednesday 4:00-6:00 pm

Description: Programming for numerical calculations, round-off error, approximation and interpolation, numerical quadrature, and solution of ordinary differential equations. Practice on the computer.

Prerequisites: Math 53 and 54 or equivalent knowledge of calculus and linear algebra.

Required Text: A Quarteroni, R Sacco and F Saleri, Numerical Mathematics. (Texts in Applied Mathematics, vol. 37.) Springer-Verlag, New York, 2000. ISBN 978-0-387-98959-4 (Print) 978-0-387-22750-4 (Online).

Matlab programming course: Ryan Hynd will teach a companion course on Matlab programming; see his Math 98 webpage for details.

Grading: 40% weekly homework, 30% midterm, 30% final

Exams:

Midterm: Tuesday, October 20.
Final Exam: Saturday, December 19, 12:30-3:30.
No notes, books, calculators, computers or other aids will be permitted. No make-up exams will be given. If you miss the midterm, your score on the final will count in its place.
For review, you can find web pages from this course in earlier years, including exams with solutions, on Richard Borcherds' math courses archive.

Discussion sections: See schedule. You can change sections online through TeleBears. When you sign up for a section that is full, you get put on its wait list. Students on the wait list are automatically enrolled when spaces open. If you are near the top of the wait list for your preferred section, you are likely to get in. Otherwise, a good strategy is to check daily for other sections that become open or whose wait list shortens, and switch if you find one that improves your wait list position. Further enrollment issues involving TeleBears should be addressed to Barbara Peavy (peavy@math.berkeley.edu).

Homework: Homework will be due on Fridays by 5 pm, and returned in discussion sections by the following Monday. The homework problems and ideas for solving them may be discussed with other students, but solutions must be written individually. It is not acceptable to copy solutions worked out by others or found on the internet.

Special accomodations: Students requiring special accomodations for exams should contact us well in advance of the first exam so that suitable arrangements can be made.

Announcements and Handouts

Our textbook is available in electronic form via SpringerLink from university computers: http://www.springerlink.com/content/q67046/

Lower-level texts with more emphasis on programming are also available from SpringerLink: Otto and Denier, An Introduction to Programming and Numerical Methods in MATLAB and Quarteroni and Saleri, Scientific Computing with MATLAB and Octave.

Problem Set 1 (due Wednesday September 2 by 5 pm): Solve problems 2, 5, 7, 12 and 13 from Section 1.13 of Quarteroni, Sacco and Saleri. Note: In problem 12, A^T should be A^H since A is complex. In problem 13, the statement should read "is the unique minimum Frobenius norm solution to" the displayed minimization problem. Solutions are now available here

Problem Set 2 (due Wednesday September 9 by 5 pm): Solve problems 14, 15, 16 and 17 from Section 1.13 and problems 1, 2 and 5 from Section 2.6 of Quarteroni, Sacco and Saleri. Solutions are now available here

Reading for September 3: Finish reviewing Chapter 1 and read Section 2.1.

Reading for September 8: Sections 2.2 and 2.3

Reading for September 10: Section 2.4

Problem Set 3 (due Friday September 18 by 5 pm): Solve problems 9 (I0), 10 (Prove 2.37), 11 (range of F), and 12 (approximations of pi) from Section 2.6 of Quarteroni, Sacco and Saleri. Note that different versions of the text may be off by one in the numbering of the problems; hence the detailed descriptions after the numbers. The relevant page is here for convenience. Solutions are now available here

Reading for September 15: Section 2.5

Reading for September 17: Section 3.2 (Triangular systems)

Reading for September 22: Section 3.3 (Gaussian elimination)

Reading for September 24: Section 3.4.3 (QR factorization)

Problem Set 4 (due Friday September 25 by 2 pm): Solve problems 1, 2, 3, 4, 9 and 10 from Section 3.15 of Quarteroni, Sacco and Saleri.

Reading for September 29: Section 3.5 (Pivoting)

Reading for October 1: Section 3.12 (Iterative improvement)

Problem Set 5 (due Friday October 2 by 2 pm): Solve problems 12, 13, 14, and 15 from Section 3.15 of Quarteroni, Sacco and Saleri. Problem 5: write, debug and test Matlab (or other convenient language) programs for (a) applying the Householder reflection H(u) = I-2 u u^T for given unit vector u to a vector x, (b) computing the unit vector u which stably transforms a given vector x to zero below given entry j, and (c) computing the QR factorization of an invertible square matrix A. (d) Test the QR factorization on Hilbert matrices A(i,j)=1/(i+j-1) of orders n= 1:20, and tabulate the Frobenius norms of Q^T Q - I, Q Q^T - I, and A - QR. (e) Compare these residuals with the condition number of A (which is O(e^(7n/2)). (f) Sharpen your results (where possible) by iterative improvement: compute fl( Q^T A) explicitly in finite precision arithmetic (even though it should be upper triangular in exact arithmetic), refactorize as fl(Q^T A) = Q_1 R_1, and replace Q by Q Q_1.

Reading for October 6: Section 6.1 (Rootfinding) and Section 6.2 (Bisection, Regula falsi, Secant and Newton methods)

Reading for October 8: Section 6.3 (Fixed-point theory)

Problem Set 6 (due Friday October 9 by 2 pm): Solve problems 2, 3, 5, 8 and 10 from Section 6.8 of Quarteroni, Sacco and Saleri.

Problem Set 7 (due Friday October 23 by 2 pm) is here If the derivatives required by Newton's method in problem 3 are too difficult to evaluate, feel free to use any combination of bisection, secant, regula falsi and/or Steffensen's method that seems appropriate. Discuss the observed and expected rate of convergence.

As part of its mission to increase the support available to UCB undergraduates interested in mathematics, the graduate group Unbounded Representation organizes Mathspace, a weekly gathering where undergraduates can make connections with grad students in the department. Undergraduates can bring their questions, both about specific math topics and general academic or career advice, to graduate students who are there ready to help. Mathspace Meets Thursdays 5-7pm in 1015 Evans Any undergraduate interested in math is cordially invited to attend. Students are invited to bring any kind of questions (class-related, career advice, random curiosity; having no questions is ok too)

Reading for October 13: Sections 6.4 (Horner's Rule)

Sample problems for our October 20 midterm exam are here and solutions are here

Extra pre-midterm office hours: Monday October 19 in 1099 Evans.

Reading for October 15: Section 7.1.1 (Multidimensional Newton methods)

Reading for October 22: Section 7.1.3 (quasi Newton methods)

Problem Set 8 (due Friday October 30 by 2 pm): Solve problems 6 and 7 from Section 7.5 of Quarteroni, Sacco and Saleri. Use Program 57 (not 50 as in the text) for Newton's method, and repeat problem 7 with Broyden's method (Program 58) and discuss the results.

Reading for October 27: Section 7.1.4 and 7.1.5 (the Broyden method and fixed point methods)

Reading for October 29: Section 8.1 (Lagrange interpolation)

Problem Set 9 (due Friday November 6 by 2 pm): Solve problems 1, 2, 4, and 5 from Section 8.9 of Quarteroni, Sacco and Saleri.

Reading for November 3: Section 8.2 (Newton interpolation)

Reading for November 5: Section 8.3 (Piecewise Lagrange interpolation)

Problem Set 10 (due Friday November 13 by 2 pm): Solve problems 7, 12 and 13 from Section 8.9 of Quarteroni, Sacco and Saleri.

Reading for November 10: Section 8.5 (Multidimensional piecewise polynomial interpolation)

Reading for November 17: Sections 9.1 through 9.3 (Newton-Cotes integration)

Reading for November 19: Sections 9.4 and 9.6 (Extrapolation)

Problem Set 11 (due Wednesday November 25 by 5 pm): Solve problems 2, 3, 5, 6 and 7 from Section 9.11 of Quarteroni, Sacco and Saleri.

Reading for November 24: Section 10.1 (Chebyshev and Legendre polynomials)

Reading for December 1: Section 10.2 and 10.4 (Gauss-Legendre integration )

Reading for December 3: Section 10.7 (Least-squares approximation)

Problem Set 12 (due Friday December 4 by 5 pm): Solve problems 1, 5, 8 and 9 from Section 10.14 of Quarteroni, Sacco and Saleri.