• 1.1 Preliminary Remarks
• 1.2 Review of Taylor Series
• Appendix D:  Linear Algebra Concepts and Notation

• Setup your blog account via NSDL
• Read blog instructions and guidelines pdf.
  

• Reading & Problems:
  
• C&K 3.1 "Bisection Method"
• Answered 3.1 problems:
• Try problems:  1, 4, 9, 10, 12, 21
• Try computer problem using Matlab: 10 (Wilkinson polynomial)
• Demos:
  
• Michael Heath
  
• Ron Mak
  

• Reading & Problems:
  
• C&K 3.2 "Newton's Method"
• Answered problems: 3, 4, 7, 9, 11, 15, 22
  
• Computer problems:  4, 8, 9, 14 (Hint: Try using the Heath demo to plot/solve)
  
• Demos:
• Newton's method (Heath)
• Bonus: Multivariate Newton's method (Heath)
• Aside: Cloth animation [Baraff and Witkin 1998]
• Bonus: Newton's method fractals
  

• C&K 3.1 (Bisection): 8, 12, 23
• C&K 3.2 (Newton): 1, 2, 22 (cubeRoot), 23 (1/x)
  

• Reading & Problems:
  
• C&K 3.3 "Secant Method"
• Try answered problems
• Demos:
• Secant method (Heath)

• Project handout (PDF)  (ver. 1.0)
• Code available through the CMS submission system
• NOTE: Please do not distribute code outside of class.
  

• 1.1.6 & 1.1.8  Nested multiplication
• 3.1.22  Bisecting to machine precision
• 3.2.32  Extending Newton:  a cubically convergent root finding scheme
• 3.3.1  Secant: 4^0.75
• 3.3.9  Secant: sqrt
• 3.3.10 Secant: subtractive cancellation (aka catastrophic cancellation) 
  

• C&K 4.1 "Polynomial Interpolation"
• Interpolation demos (Heath)
• Newton interpolation demo
  
• Aside:  Clarification of "Computer Problem 1.1.3"

• Unfinished questions from previous week, e.g.,
  
• 3.3.1  Secant: 4^0.75
• 3.3.9  Secant: sqrt
• 3.3.10 Secant: subtractive cancellation (aka catastrophic cancellation)
• Lagrange Interpolation:
• 4.1.1,  4.1.3,  4.1.4,  4.1.5
  

• 4.1 Polynomial Interpolation (Wrap up)
• p.131-138 Computing divided differences
• p.144 Interpolating bivariate functions
• p.141 Inverse interpolation (root finding)
• 4.2 Errors in Polynomial Interpolation (briefly)
• p.154-5  The Runge function (see image at left), and the importance of node positioning
• Convergence demo (Heath)
  

• Time:  7:30pm
• Where:  B17 Upson
• Closed book exam
• Allowed 1 sheet of notes
• Calculators permitted (but not necessary)
• Covers material covered in lecture, HW or sessions from:
• 1.1 Prelim Remarks
• 1.2 Review of Taylor Series
  
• 3. Locating Roots
• 3.1 Bisection method
  
• 3.2 Newton's method
  
• 3.3 Secant method
• 4. Polynomial Interpolation (part)
  
• 4.1 Lagrange Interpolation material only
• Practice questions: P4.1: 1, 3, 4, 5

• 4.3 C&K
• See answered problems
  
• Finite difference estimates of derivatives
  
• Taylor series (pp. 164-66, 173)
  
• Newton interpolation (pp. 170-173)
  
• Truncation error and round-off error (pp. 165-166)
  
• Preview of Richardson Extrapolation

• C&K 4.1: Newton Interpolation:
• 4.1.7a, 4.1.8, 4.1.9
  
• C&K 4.3: Estimating Derivatives:
• 4.3.1, 4.3.6, 4.3.9a
  

• C&K 4.3:  Richardson extrapolation (pp. 166-170)
• Answered problems:  4.16, 4.20
  
• Richardson Demo (Heath)
• C&K 5.3: Romberg Algorithm (pp. 204-)
• Romberg Demo (Heath)

• Recap: Richardson extrapolation
• Examples 1
  
• Preliminary Exam
• Results
  
• Solution take-up (solution in CMS)
  
• "How are we doing?" questionnaire
• "An Early-Course Evaluation"
  

• Derivatives:
  
• C&K 4.3.3, 4.3.10
  
• Richardson:
  
• C&K 4.3.15, 4.3.19
  

• Floating Point:
• C&K 2.1 "Floating-Point Representation"
• C&K 2.2 "Loss of Precision"
• Supplemental reading:
• Goldberg, D. 1991. What every computer scientist should know about floating-point arithmetic. ACM Comput. Surv. 23, 1 (Mar. 1991), 5-48.
  
• Kahan summation algorithm
  
• BLAS (Basic Linear Algebra Subprograms) (netlib, Intel MKL)
  

• Motivating Ax=b: Newton's method for systems of nonlinear equations (pp. 96-99)
• C&K 7.1: Naive Gaussian Elimination
• See answered problems (1, 2, 3ab, 4, 5, 6, 7abc)
  
• C&K 8.1: Matrix Factorizations
• See pp. 293-302 (on LU factorization)
• See answered problems (1-8)
• PDF slides (from text;  includes a few more on LU factorization from chalkboard)
  

• 4.1.23  Divided difference table (failure)
  
• 7.1.3d  Naive Gaussian elimination (failure)
  
• 7.1.7a  Naive Gaussian elimination
  
• 8.1.1b  LU
• Floating point (time permitting):
• 2.1.6ab
• 2.1.10
• 2.1.12
  

• C&K 8.1: Matrix Factorizations
• See pp. 302-310
• LU Factorization Demo (Heath)
• LDL' Factorization
  
• Cholesky Factorization Demo (Heath)
  

• SVD
• SVD Introduction (except from book...)
  
• Lloyd N. Trefethen and David Bau, Numerical Linear Algebra, SIAM, 1997.
  
• Condition numbers as ellipses demo (Heath)

• PDF Description
• Starter Code (on CMS)

• Last week's session, and...
• 8.1 Matrix Factorizations
  
• 8.1.5
• 8.1.11
• 8.1.19
• 8.1.22
• Questions PDF
  

• C&K 12.1  "Method of Least Squares"
  
• pp. 495-504  (redundant slides)
  
• See answered problems
• Discussion of ShadowBox assignment
  

Method of Least Squares (cont'd);
QR Factorization

• Blackboard
  
• Demos:
• Condition numbers as ellipses (Heath)
• Least Squares Data Fitting (Heath)
• Gram-Schmidt Orthogonalization (Heath)
  

• C&K 12.1 "Method of Least Squares"
• Problems 1, 3, 5, 11, 13
  

QR Factorization

• Blackboard
• More advanced supplemental on
  
• Gram-Schmidt Orthogonalization (PDF)
• and GS QR factorization (PDF)
  
• Demos:
• Gram-Schmidt QR Factorization (Heath)

• Blackboard

• Main Exam
• Time:  7:30pm-9:00pm
• Where:  B17 Upson
• Conflicts-only Exam:
• Time: 6:15pm-7:45pm
• Where: 315 Upson
  
• Closed book exam
• Allowed 1 sheet of notes
• Calculators permitted (but not necessary)
• Covers material covered in lecture, HW or sessions from:
• 4.1 Newton Interpolation
• 4.3 Estimating Derivatives & Richardson Extrapolation
• 2.1 Floating-Point Representation
• 7.1 Naive Gaussian Elimination
• 8.1 Matrix Factorizations (LU, LDL', Cholesky); computation and usage
• No SVD material (defer to final)
• 12.1 Method of Least Squares
  

Mon Apr 7

Wed Apr 9

Numerical Integration

Materials:

• C&K 5.2 Trapezoid Rule
  • Composite rule
  • Recursive evaluation (equal subintervals)
• C&K 5.3 Romberg Algorithm
  • Romberg Demo (Heath)
• Newton-Cotes Quadrature Rules
  • See C&K 6.1
  • Construction from Lagrange interpolating polynomials, and also book's method of undetermined coefficients
  • Newton-Cotes Quadrature Demo (Heath)
• Adaptive Quadrature Demo (Heath)
  

"HW 8"

• PDF
• Due next Wed April 16 (in class)
  

Questions selected from:

• Modified Gram-Schmidt, and QR Factorization
  • GS QR factorization (PDF)
    
  • Demos:
  • Gram-Schmidt QR Factorization (Heath)
• C&K 5.2 Trapezoid Rule
  • Problems 1, 9
• C&K 5.3 Romberg Algorithm
  • Problems 5, 11, 14, 22
    

Mon Apr 14

Wed Apr 16

Numerical Integration of Ordinary Differential Equations (ODEs)

Materials:

• C&K 10.1 "Taylor Series Methods"
• C&K 10.2 "Runge-Kutta Methods"
• Demos (Heath):
  • Euler's Method
  • Backward Euler
  • Trapezoid Method
  • Taylor Series
  • Runge-Kutta Methods
    

"HW 9"

• C&K 10.2.7 RK3
• C&K 10.2.9
• C&K 11.2.11
• Due next Wed Apr 23 (in class)
  

Materials:

• PDF Description
• Starter Code (on CMS)
• Due Saturday May 3 (before midnight).
  

Questions selected from:

• C&K 10.1 "Taylor Series Methods"
  • Problems 5, 6, 10
• C&K 10.2 "Runge-Kutta Methods"
  • Problems 2, 3, 8

Monte Carlo Methods (& ODE wrap-up)

Materials:

• ODEs:
  • C&K 11.1 "Methods for First-Order Systems"
  • C&K 11.2 "Higher-Order Eqns & Systems"
  • Demos
• Monte Carlo Methods
  • C&K 13.2 "Estimation of Areas and Volumes by Monte Carlo Techniques"
  • Answered Problems: 13.2.1; see computer problems, too
  • Demos (Heath):
    • Monte Carlo Integration in 1-D
    • Monte Carlo Integration in 2-D
• Discuss prelim2 exam

Principal Component Analysis (PCA)

• Blackboard
• Also:
  • Global truncation error
  • Monte-Carlo integration (cont'd)
    
• Demos:
• Low-Rank Approximation (Heath)
• PCA-based morphable face models
  • [Blanz and Vetter 1999]

Other announcements:

• Course evaluations
  • Fill out the form online.
  • Suggestions welcome

Wed May 7

Final Exam

Details:

• When: 7:00pm start
• Where: Upson B17
• Logistics:
  • Closed book exam
  • Allowed 1 sheet of notes
  • Calculators permitted
• Exam is comprehensive: Covers all material from lecture, HW and sessions.
• Previous exams:
  • Spring 2007 [Final exam]