CMPSC/MATH 451: Numerical Computations

Overview

This class introduces students to key ideas behind numerical computation, with emphasis on the implementation of common numerical methods. CMPSC/MATH 455 is a related course that covers a subset of the topics that we will study in this class. Students may obtain credit for either this class or CMPSC/MATH 455, but not both.

Topics

Approximations in Scientific Computing, Floating Point Arithmetic, Systems of Linear Equations, Linear Least Squares, Non-linear Equations, Interpolation, Numerical Integration, Numerical Differentiation, Initial Value Problems for ODEs.

Syllabus

Last updated Sep 19.

Schedule

Lecture 1, Aug 22

• Course Logistics
• Introduction to Scientific Computing
• Error Analysis

Lecture 2, Aug 24

• Error Analysis
• Sensitivity and Conditioning
• Review

Lecture 3, Aug 26

• Floating-point systems
• IEEE-754 standard

Lecture 4, Aug 29

• Floating-point computations
• Octave tutorial

Lecture 5, Aug 31

• Octave tutorial (continued)
• Linear systems introduction
• Vector Norms

Lecture 6, Sep 2

• Matrix Norms and Condition Number
• Error Bounds
• HW 1 online

Lecture 7, Sep 7

• Transformations
• Triangular systems
• Forward and Back substitution

Lecture 8, Sep 9

• Gaussian Elimination
• HW 1 due

Lecture 9, Sep 12

• LU Factorization with Partial Pivoting
• Exercises

Lecture 10, Sep 14

• HW1 discussion
• Linear systems with Octave

Lecture 11, Sep 16

• Octave examples continued
• Gauss-Jordan elimination
• HW 2 online

Lecture 12, Sep 19

• Solving modified systems
• Special types of linear systems

Lecture 13, Sep 21

• Linear systems software
• Non-linear systems: Introduction

Lecture 14, Sep 23

• Review of floating-point arithmetic

Lecture 15, Sep 26

• Review of linear systems
• Midterm Exam 1

Lecture 16, Sep 28

• Midterm Exam solutions discussion
• Non-linear systems: conditioning

Lecture 17, Sep 30

• Convergence rate
• Intermediate value theorem
• Interval Bisection

Lecture 18, Oct 3

• Fixed-point iterations
• Newton's method

Lecture 19, Oct 5

• Newton's method convergence theorems
• Secant method

Lecture 20, Oct 7

• Inverse Quadratic Interpolation
• Linear Fractional Interpolation
• Dekker's method, Brent's method
• HW3 online

Lecture 21, Oct 10

• Non-linear equations: exercises, Halley's method
• Octave code

Lecture 22, Oct 12

• Non-linear equations, exercises
• Non-linear systems: Fixed-point, Newton method

Lecture 23, Oct 14

• Secant updating methods: Broyden method

Lecture 24, Oct 17

• Interpolation: Introduction
• Basis functions, monomial basis, Horner evaluation

Lecture 25, Oct 19

• Lagrange Interpolation
• Newton Interpolation

Lecture 26, Oct 21

• Divided differences
• Orthonormal polynomials
• Legendre polynomials

Lecture 27, Oct 24

• Chebyshev points
• Piecewise polynomial interpolation

Lecture 28, Oct 26

• Hermite cubic, cubic splines
• Octave examples for polynomial interpolation

Lecture 29, Oct 28

• Octave examples for polynomial, spline interpolation
• Review of non-linear systems

Lecture 30, Oct 31

• Review of Interpolation
• Midterm exam 2

Lecture 31, Nov 2

• Numerical Quadrature: Introduction
• Method of Undetermined Coefficients

Lecture 32, Nov 4

• Newton-Cotes Quadrature
• Clenshaw-Curtis Quadrature

Lecture 33, Nov 7

• Midterm exam 2 discussion
• Gaussian Quadrature

Lecture 34, Nov 9

• Progressive Gaussian Quadrature
• Composite Quadrature
• Adaptive Quadrature
• Octave code: Newton-Cotes rules

Lecture 35, Nov 11

• Octave code: Composite and Adaptive Quadrature
• Other Integration Problems

Lecture 36, Nov 14

• Numerical Differentiation
• Richardson Extrapolation

Lecture 37, Nov 28

• ODEs: Introduction

Lecture 38, Nov 30

• ODEs: Existence, Uniqueness

Lecture 39, Dec 2

• ODEs: Stability
• Euler's method

Lecture 40, Dec 5

• Backward Euler method
• Stiff ODEs

Lecture 41, Dec 7

• Runge-Kutta methods
• Numerical Integration: Review

Lecture 42, Dec 9

• Review for final exam