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 April 18.

Schedule

Lecture 1, Jan 8

Course Logistics

Introduction to Scientific Computing

Lecture 2, Jan 10

Error types

Taylor series

Big-O notation for error analysis

Lecture 3, Jan 15

Conditioning of a problem

Assessing Algorithms

Floating-point systems

Lecture 4, Jan 17

Floating-point systems, properties

Roundoff error

Octave introduction

Lecture 5, Jan 22

Rounding unit

Sources of roundoff error

Decimal to binary conversion

Lecture 6, Jan 24

IEEE floating-point system

Avoiding cancellation and roundoff error

Introduction to nonlinear methods

Lecture 7, Jan 29

Interval bisection

Fixed point theorem

Fixed point iteration

Lecture 8, Jan 31

Speed of convergence

Newton iteration

Secant iteration

Lecture 9, Feb 5

Nonlinear equations Octave tutorial

Multiple roots

Function minimization

Lecture 10, Feb 7

Matrices review

Vector and matrix norms

Lecture 11, Feb 12

Midterm 1 review

Lecture 12, Feb 19

Special classes of matrices

Operation counts

Backward substitution

Lecture 13, Feb 21

Forward substitution

Gaussian Elimination

Lecture 14, Feb 26

Gaussian Elimination algorithm, operation count

Partial pivoting

Lecture 15, Feb 28

Complete pivoting

Gauss-Jordan elimination

Uniqueness of LU decomposition

Cholesky factorization

Lecture 16, Mar 12

Midterm 1 solutions, discussion

Lecture 17, Mar 14

Cholesky factorization example

Banded matrices

Error, residual, conditioning

Linear systems: Octave tutorial

Lecture 18, Mar 19

Linear systems review

Polynomial Interpolation: Introduction

Monomial basis

Lecture 19, Mar 21

Lagrange basis

Newton basis

Lecture 20, Mar 26

Divided differences

Polynomial interpolation error

Chebyshev interpolation

Lecture 21, Mar 28

Octave interlation tutorial

Piecewise polynomial interpolation introduction

Lecture 22, Apr 9

Midterm 2 solutions discussion

Hermite cubic interpolation

Cubic splines

Lecture 23, Apr 11

Finite difference formulas

Richardson Extrapolation

Lecture 24, Apr 16

Numerical Quadrature introduction

Newton-Cotes quadrature rules

Lecture 25, Apr 18

Precision of a quadrature rule

Deriving error with a quadrature formula

Clenshaw-Curtis quadrature

Composite quadrature

Lecture 26, Apr 23

Octave tutorial on numerical integration

Gaussian quadrature

Adaptive quadrature

Lecture 27, Apr 25

Final exam review