Math 128b - Numerical Analysis - Spring 2014

Announcements: I will post what material was covered in class here after each lecture.

• Lecture 1: Gaussian elimination, LU factorization, vector and matrix norms (see also Chapters 2.1 and 2.2)
• Lecture 2: Induced matrix norms, forward/backward error, condition number (see also Chapter 2.3)
• Lecture 3: Proof of a formula for the condition number, swamping, partial pivoting (see also Chapters 2.3 and 2.4)
• Lecture 4: Partial pivoting, PA = LU, introduction to SPD matrices (see also Chapters 2.4 and 2.6, and Appendix A)
• Lecture 5: Cholesky factorization, review of inner products and orthogonality (see also Chapter 2.6)
• Lecture 6: Conjugate gradient method (see also Chapter 2.6)
• Lecture 7: Pre-condtioning for conjugate gradient method and convergence of Jacobi method (see also Chapters 2.5 and 2.6)
• Lecture 8: Convergence of Gauss Seidel method; introduction to least squares (see also Chapters 2.6 and 4.1)
• Lecture 9: How to solve least squares problems with QR-factorization; using Gram-Schmidt to compute Q and R (see also Chapter 4.3)
• Lecture 10: Householder reflectors for QR factorization (see also Chapter 4.4)
• Lecture 11: GMRES (see also Chapter 4.3)
• Lecture 12: Optimization: Newton's method, steepest descent, Gauss Newton for nonlinear least squares (see also Chapters 2.7 and 13.2)
• Lecture 13: Review
• Lecture 14: Midterm
• Lecture 15: Eigenvalues and eigenvectors, Rayleigh's quotient (see also chapter 12.1 and Appendix A3)
• Lecture 16: Power iteration and its convergence, inverse power iteration, Rayleigh quotient iteration, simultaneous iteration, Schur form (see also chapters 12.1 and 12.2)
• Lecture 17: Proof of Schur form, "pure QR", equivalence of pure QR and simultaneous iteration (see also chapter 12.2)
• Lecture 18: Making QR practical, bring A into upper Hessenberg form with Householder reflectors (see also chapter 12.2)
• Lecture 19: Shifted QR with deflation. SVD: definition and computation (see also chapters 12.2 and 12.3)
• Lecture 20: SVD: definition, computation and application (see also chapters 12.3 and 12.4)
• Lecture 21: The heat equation: exact solution for Dirichlet boundary conditions, uniqueness, steady state.
• Lecture 22: Forward finite difference method for the heat equation, stability (see also chapter 8.1).
• Lecture 22: Stability, consistency, convergence; forward and backward finite difference methods (see also chapter 8.1).
• Lecture 23: Crank-Nicolson method (see also chapter 8.1).
• Lecture 24: Accuracy of the Crank-Nicolson method, the baby wave equation, characteristics, domain of dependence, CFL condition (see also chapter 8.1).
• Lecture 25: Lax-Friedrichs, Lax-Wendroff and Crank-Nicolson schemes for the baby wave equation.
• Lecture 26: Leap-frog scheme for the wave equation (see also chapter 8.2).
• Lecture 27: Stabiltiy of the leap-frog scheme for the wave equation (see also chapter 8.2); summary and review.

• Homework 1, due Tuesday 1/28 in class, before lecture starts.
• Homework 2, due Tuesday 2/4 in class, before lecture starts.
• Homework 3, due Tuesday 2/11 in class, before lecture starts.
• Homework 4, due Tuesday 2/18 in class, before lecture starts.
• Homework 5, due Tuesday 2/25 in class, before lecture starts.
• Homework 6, due Tuesday 3/11 in class, before lecture starts.
• Homework 7, due Tuesday 3/18 in class, before lecture starts.
• Homework 8, due Tuesday 4/1 in class, before lecture starts.
• Homework 9, due Tuesday 4/8 in class, before lecture starts.
• Homework 10, due Tuesday 4/15 in class, before lecture starts. Download the image here here.
• Homework 11, due Tuesday 4/22 in class, before lecture starts. Download the colormap here here.
• Homework 12, due Thursday 5/1 in class, before lecture starts.

How to hand in code: if the HW requires you to write and test code, please hand in the following as hard copies: (1) the results your code produces when you apply it to the problem asked for in the HW, e.g. a print out of Matlab's command window where you use your code; (2) print outs of the code of all functions that you call (except the Matlab routines).

Lecture: Tuesday and Thursday 3:30-5:00 pm in 2 Evans.

Discussion: Thursday 11:00-12:00 in 285 Cory.

Instructor: M. Morzfeld, office hours: Mondays 1:00-2:30 pm and Fridays 1:00-2:00 pm in 971 Evans. Email: mmo [at] math [dot] lbl [dot] gov

GSI: Christopher Wong, office hours: Mondays 4:00-5:00 pm and Thursdays 5:00-6:00 pm in 1039 Evans. Email: cawong [at] math [dot] berkeley [dot] edu

Prerequisites: Math 110 and 128a or equivalent knowledge of numerical analysis and linear algebra.

Textbook: T. Sauer, Numerical Analysis, 2nd edition, Addison-Wiley, 2012.

Software and computer lab access: We will use Matlab for coding and testing algorithms. Matlab is available in the "Calculus Microcomputer Facility" (CMF) in B3A Evans. Please check their website for availability. We have reserved access to B3A Evans on the following days:

• Mondays 3:00-4:00 pm
• Wednesdays 5:00-6:00 pm
• Thursdays 1:00-2:00 pm

Syllabus: Math 128b is a second course in numerical analysis. The course will introduce standard numerical methods for

• solving systems of equations (chapter 2);
• solving least squares problems (chapter 4);
• solving eigenvalue problems and computing singular values (chapter 12);
• numerical solution of partial differential equations (chapter 8);
• (time permitting) computing fast Fourier transforms (chapter 10) and/or solving optimization problems (chapter 13).

We will find out when, how and why the various algorithms can be expected to work. Analytically, we will focus on stability and accuracy properties. Computationally, we will write our own codes and also study and apply Matlab's routines. The lectures will follow, amplify and explain the textbook, with additional handouts when other material is required. Student participation will be encouraged during lectures.

Exams:

• Midterm: March 6th in class
• Final Exam: Group 20, Friday May 16, 7:00-10:00 pm

No books, calculators, computers or other aids will be permitted. You can bring one sheet of handwritten notes (both sides, if you want). No make-up exams will be given. If you miss the midterm, your score on the final will count in its place. If your final exam score is higher than the midterm score, the midterm score will be replaced by the final exam score.

Grading: 40% weekly homework and quizzes, 30% midterm, 30% final. The lowest two homework grades will be dropped from the computation. Four quizzes will be given during discussion sections. Each quiz counts as much as one homework assignment and the two lower scores will be dropped. Thus the final course grade will be computed from the formula 0.4 * (top n - 2 of n homework grades + top 2 quiz scores) + 0.3 * max(midterm grade, final exam grade) + 0.3 * final exam grade where each parenthesis is a number between 0 and 100.