CMPSC/MATH 455: Introduction to Numerical Analysis I

Overview

This class introduces students to key topics in numerical analysis, with emphasis on the computational mathematics behind numerical methods and on proving theorems. CMPSC/MATH 451 is a related course that has a significant overlap with topics studied in CMPSC/MATH 455 and CMPSC/MATH 456. Students may obtain credit for either this class or CMPSC/MATH 451, but not both.

Topics

Floating Point Arithmetic, Approximations in Scientific Computing, Non-linear equations in one variable, Linear Systems: Direct Methods, Polynomial Interpolation, Piecewise Polynomial Interpolation, Numerical Differentiation, Numerical Integration.

Syllabus

Last updated Oct 11.

Schedule

Lecture 1, Aug 27

Course Logistics

Introduction to Scientific Computing

Lecture 2, Aug 29

Taylor's theorem

Types of error

Lecture 3, Aug 31

Analyzing algorithms

Problem conditioning

Lecture 4, Sep 5

Floating-point systems

Lecture 5, Sep 7

Rounding unit

Roundoff error accumulation

Octave tutorial

Lecture 6, Sep 10

IEEE standard

Cancellation error

More Octave examples

Lecture 7, Sep 12

Non-linear equations: Introduction

Interval bisection

Lecture 8, Sep 14

Fixed point iteration

Lecture 9, Sep 17

Order of convergence

Newton's method

Examples

Lecture 10, Sep 19

Secant method

Octave examples

Lecture 11, Sep 21

Secant method order of convergence

Lecture 12, Sep 24

HW1 discussion

Multiple roots

Lecture 13, Sep 26

Function minimization using Newton's method

Linear Systems Introduction

Lecture 14, Oct 1

Matrices Review

Vector and Matrix Norms

Lecture 15, Oct 3

Midterm 1 discussion

Lecture 16, Oct 5

Midterm 1 discussion (continued)

Special classes of matrices

Operation counts

Lecture 17, Oct 8

Forward and Backward substitution

Gaussian Elimination

Lecture 18, Oct 10

Gaussian Elimination (continued)

Examples

Lecture 19, Oct 12

GE with Pivoting

Octave Linear Systems tutorial

Lecture 20, Oct 15

Octave code for Gaussian Elimation

GE with Complete pivoting

Uniqueness of GE

Lecture 21, Oct 17

Cholesky decomposition

Example

Lecture 22, Oct 19

Sparse matrices, banded systems

Error analysis, Matrix conditioning

Lecture 23, Oct 22

Linear systems exercises

Lecture 24, Oct 24

Linear systems exercises

Lecture 25, Oct 26

Interpolation: Introduction

Monomial Basis

Lecture 26, Oct 31

Lagrange Interpolation

Newton's basis

Lecture 27, Nov 2

Divided Differences

Lecture 28, Nov 5

Review for Midterm exam 2

Lecture 29, Nov 7

Midterm exam 2 solutions

Lecture 30, Nov 9

Error in polynomial interpolation

Chebyshev interpolation

Lecture 31, Nov 12

Piecewise linear interpolation

Piecewise cubic interpolation

Lecture 32, Nov 26

Review of piecewise interpolation

Cubic spline interpolation

Lecture 33, Nov 28

Numerical Differentiation, finite difference schemes

Richardson extrapolation

Lecture 34, Nov 30

Numerical Integration, Quadrature rules

Newton-Cotes quadrature rules

Lecture 35, Dec 3

Precision of Newton-Cotes rules

Composite quadrature

Octave tutorial

Lecture 36, Dec 5

Clenshaw-Curtis quadrature

Gaussian quadrature

Lecture 37, Dec 7

Adaptive quadrature

Romberg integration

Octave examples

Lecture 38, Dec 10

Review lecture

Lecture 39, Dec 12

Review lecture

Lecture 40, Dec 14

Review lecture