## Math 128A - Numerical Analysis

Instructor: Jon Wilkening
Office: 1051 Evans
Office Hours: Mon 10:15-11:45, Thurs 2:30-4

Lectures: MWF 8:10-9:00 AM, 105 Stanley
Prerequisites: Math 53 and 54 or equivalent
Required Text: Numerical Analysis, 9th Edition, by Burden/Faires

Matlab resources:

Ways to run matlab:

• MATLAB will be available during discussion sections in the computer lab B3A Evans
• On computers owned by the university, UC Berkeley Software Central provides MATLAB for free
• The Mathworks provide student editions of MATLAB at a discounted rate
• The free alternative Octave has some limitations (especially for graphics), but is sufficient for all excercises in the class

Syllabus: Programming for numerical calculations, round-off error, approximation and interpolation, numerical quadrature, matrix computations, and solution of ordinary differential equations.

• Error anlysis, roundoff error and computer arithmetic, algorithms and convergence (Chapter 1)
• Nonlinear equations: bisection, Newton and secaont methods (Chapter 2)
• Polynomial interpolation and approximation (Chapter 3)
• Numerical differentiation and integration (Chapter 4)
• Initial value problems for ordinary differential equations (Chapter 5)
• Matrix computations: linear systems, matrix factorizations, norms (Chapters 6, 7.1)
• Approximation theory, least squares approximation (8.1-8.3, if time permits)

Course Material: I will post handouts and assignments on bCourses. Please e-mail me if you do not have access to the bCourses page.

Piazza forum: link to 128A

 programming assignments: 10% (all scores count) homework: 5% (lowest score dropped) quizzes: 15% Sep 17, Oct 1, Oct 15, Oct 29, Nov 12, Dec 3 (in section, lowest score dropped) Midterm 1: 20% Monday, October 6 (in class) Midterm 2: 20% Friday, November 14 (in class) Final exam: 30% Monday, Dec 15, 7-10 PM (location TBA)

More Details: 11 homework assignments, 4 programming assignments, 6 quizzes. My grade cutoffs are usually around 90 A, 85 A-, 80 B+, 75 B, 70 B-, 65 C+, 60 C, 50 D. Your lowest midterm grade will be replaced by your grade on the final if you do better on the final. If you miss a midterm for any reason (illness, family emergency, didn't study, etc.), the final will count for both. Homework and programming assignments are due at the beginning of discussion section. Quizzes will be given in section. Late assignments and missed quizzes cannot be made up. Collaboration is encouraged in discussing ideas, but you are not allowed to share code or written solutions of homework. If you are caught cheating, you will receive an F in the course and be reported to the university.

Detailed syllabus (will be updated as the semester progresses)

Mon Wed Fri
8/29
1.1
Overview, example of unstable recurrence, MVT, Rolle's theorem, Extreme value theorem/algorithm
9/1 holiday 9/3
1.1
IVT, Taylor's theorem, tricks for bounding R, maximum error, meaning of R 9/5
1.1,1.2
avoiding circular reasoning, error bounds for integrals, floating-point arithmetic
9/8
1.2, 1.3
floating-point arithmetic, absolute and relative error, quadratic formula, two algorithms for evaluating polynomials 9/10
1.3, 2.1
error propagation, rate of convergence, bisection method
HW 1 due
9/12
1.3, 2.1
convergence order examples, ln(1+x)=O(x), convergence rate of bisection method
9/15
2.2
fixed point iteration, discuss HW 2.2.11, proof of fixed point theorem, error estimates 9/17
2.3
Newton's method: graphical derivation, proof of convergence, why it's so fast
HW 2 due, Quiz 1
9/19
2.3, 2.4
secant method, false position, order of convergence, quadratic convergence in fixed point iteration when g'(p)=0
9/22
2.4, 2.5
multiple roots, modified Newton, accelerating convergence, Aitken's method/proof, Steffensen's method/proof 9/24
2.6, 3.1
Horner's method, Mueller's method, polynomial interpolation
HW 3 due, PA 1 due
9/26
3.1, 3.2
polynomial interpolation, Neville's method
9/29
3.2, 3.3
recap of Neville's method, divided differences 10/1
3.3, 3.4
forward/backward differences, Hermite interpolation
HW 4 due, Quiz 2
10/3 Review
10/6 Midterm 1, (chapters 1-3) 10/8
4.1
numerical differentiation, n+1 point formula, examples 10/10
4.1-2
2nd order derivatives, Richardson extrapolation
10/13, 4.3 quadrature: trapezoidal rule, Simpson's rule, degree of accuracy, Newton-Cotes formulas 10/15, 4.4-5 composite quadrature, Romberg integration, Euler-Maclaurin formula
HW 5 due, Quiz 3
10/17, 4.5 recap/overview of quadrature, Euler-Maclaurin, Romberg integration
10/20, 4.7 Gaussian quadrature, Legendre polynomials, Gram-Schmidt procedure, proof that degree of precision = 2n-1 10/22, 4.7, 4.6 recap of Gaussian quadrature, proof that zeros are real and distinct, arbitrary intervals, adaptive quadrature
HW 6 due, PA 2 due
10/24, 4.8, 4.9 multiple integrals, improper integrals
10/27, 5.1 (guest lecture by Danny Hermes)
theory of ODE's, Lipschitz continuity, well-posed problems, examples
10/29, 5.2 (guest lecture by Ming Gu)
Euler's method, convergence proof
HW 7 due, Quiz 4
10/31, 5.2, 5.3 How to compute/bound derivatives of the unknown solution, Taylor methods, local truncation error
11/3, 5.4 Runge-Kutta methods, Butcher array/tableau, truncation error of general explicit 2-stage RK scheme 11/5, 5.6 (guest lecture by Weihua Liu)
multistep methods, derivation of Adams-Bashforth and Adams-Moulton
HW 8 due
11/7, 5.10 (guest lecture by Weihua Liu)
stability of multistep methods
11/10, 5.6, 5.10 truncation error of multistep methods, stability+consistency=convergence 11/12 Review
HW 9 due, Quiz 5
11/14 Midterm 2 (chapters 4 and 5, only sections in which homework has been assigned)
11/17, 5.9, 5.11 higher-order equations and systems, stiff equations, Prothero-Robinson example 11/19, 5.11, 5.5 linear stability analysis, adaptive stepsize control
PA 3 due
11/21, 6.1-3 Gaussian elimination, pivoting, matrix inversion
11/24, 6.5 LU factorization, forward/back-substitution, counting flops 11/26 no main lecture, yes discussion sections
HW 10 due
11/28 holiday
12/1, 6.6 positive definite matrices, Cholesky factorization, tridiagonal matrices 12/3, 3.5 cubic spline interpolation
PA 4 due, Quiz 6 (5.9, 5.11, 6.1, 6.2, 6.3, 6.5)
12/5 Review
12/8 RRR Week. (HW 11 due Monday in my office hours, or arrange with your GSI)
12/15 Final Exam, 7-10 PM, 105 Stanley