Numerical Analysis I

AMSC 666, Fall 2017


Course Information

LectureRoom 4122 CSIC Bldg. #406 TuTh 2-3:15pm
Note special place: Math Bldg. Rm. 3201 on Tue 10/10
Note special place: Math Bldg. Rm. 3201 on Thu 10/12
InstructorProfessor Eitan Tadmor
Contacttel.: x5-0648   e-mail:
Office HoursBy appointment (e-mail: )
CSCAMM 4122 CSIC Bldg. #406
Teaching Assistant Kilian Cooley e-mail:
Midterm TBA
Final Sat 12/16 10:30-12:30pm 4122 CSIC Bldg. #406
NOTE: use of a calculator and your notes is allowed
Grading40% Homework; 60% Final


Course Description

  1. Approximation Theory

    1. General overview
      • On the choice of norm: least-squares vs. the uniform norm
      • Weierstrass' density theorem; Bernstein polynomials

    2. Least squares approximations I
      • Least squares: ill-conditioning of Gramm matrix
      • Orthogonal polynomials: Legendre, Chebyshev, Sturm's sequence
      • Generalized Fourier expansions; Chebyshev expansions

      Lecture notes: spectral expansions [ pdf file ]
      Lecture notes: A very short guide to Jacobi polynomials [ pdf file]
      Assignment #1: [ pdf file ] ... with answers [ pdf file]
    3. Min-Max approximations: Chebyshev interpolant; economization

    4. Error estimates in interpolation*
      • Polynomial interpolation: Runge effect, region of analyticity
      • Trigonometric interpolation: Sobolev least-squares vs uniform error bounds

      Lecture notes: Polynomial interpolation and error estimates [ pdf file ]
      Lecture notes: Jackson's theorem [ pdf file]
      Assignment #2 [ pdf file ]
      Additional lecture notes on FFT:
      • J. Colley, P. Lewis, J. Welch, The fast Fourier Transform and its applications, IEEE on Education, 1969, vol. 12 (1), [pdf file]

      • C. DeBoor, FFT as nested multiplication with a twist, SISC 1980 vol. 1(1) [pdf file]

    5. Least squares II -- the finite-dimensional case
      • QR and SVD
      • From discrete least-squares to interpolation

      Assignment #3

    6. Least squares III -- Gauss quadrature
  2. Numerical Solution of Initial-Value Problems

    1. Systems of ODEs. Existence, uniqueness & stability.

    2. Euler's method. Strong-Stability Preserving (SSP) schemes

    3. Multistep methods
      • The example of Milne method
      • Predictor-Corrector methods: the class of Adams-Bashforth-Moulton schemes

    4. Consistency, stability and convergence
      • Dahlquist theory. The root condition
      • Convergence of multi-step methods

    5. Runge-Kutta methods
      • Local time stepping and error estimates
      • Examples of RK4 and RKF5
      • Stability and Convergence of Runge-Kutta methods

    6. Methods for stiff equations
  3. Iterative Methods for Linear Systems of Equations

    1. Introduction and motivation. Stiff systems

    2. Classical methods: Jacobi, Gauss-Siedel, SOR, ...

    3. Energy functionals and gradinet methods
      • Steepest descent
      • Conjugate gradient method
      • ADI and dimensional splitting methods

    4. Non-stationary methods
      • Polynomial equations: local vs. global methods

    5. Preconditioners

    6. Multigrid mthods*; GMRES*

  4. Numerical Optimization

    1. Introduction

    2. Steepest descent and CG methods

    3. Line search methods

    4. Newton's and quasi-Newton methods

    5. Rates of converegence

    6. Gauss-Newton and related methods



    References

    GENERAL TEXTBOOKS

    K. Atkinson, An INTRODUCTION to NUMERICAL ANALYSIS, Wiley, 1987

    S. Conte & C. deBoor, ELEMENTARY NUMERICAL ANALYSIS, McGraw-Hill
    User friendly; Shows how 'it' works; Proofs, exercises and notes

    G. Dahlquist & A. Bjorck, NUMERICAL METHODS, Prentice-Hall,
    User friendly; Shows how 'it' works; Exercises

    A. Ralston & P. Rabinowitz, FIRST COURSE in NUMERICAL ANALYSIS, 2nd ed., McGraw-hill,
    Detailed; Scholarly written; Comprehensive; Proofs exercises and notes

    J. Stoer & R. Bulrisch, INTRODUCTION TO NUMERICAL ANALYSIS, 2nd ed., Springer
    detailed account on approximation, linear solvers & eigen-solvers, ODE solvers,..

    APPROXIMATION THEORY

    E. W. Cheney, INTRODUCTION TO APPROXIMATION THEORY
    Classical

    P. Davis, INTERPOLATION & APPROXIMATION, Dover
    Very readable

    T. Rivlin, AN INTRODUCTION to the APPROXIMATION of FUNCTIONS
    Classical

    R. DeVore & G. Lorentz, CONSTRUCTIVE APPROXIMATION, Springer
    A detailed account from classical theory to the modern theory; everything; Proofs exercises and notes

    NUMERICAL INTEGRATION

    F. Davis & P. Rabinowitz, NUMERICAL INTEGRATION,
    Everything...

    NUMERICAL SOLUTION Of INITIAL-VALUE PROBLEMS

    E. Hairer, S.P. Norsett and G. Wanner, SOLVING ODEs I: NONSTIFF PROBLEMS, Springer-Verlag, Berlin. 1991, (2nd ed)
    Everything - the modern version

    A. Iserles, A FIRST COURSE in the NUMERICAL ANALYSIS of DEs, Cambridge Texts

    W. Gear, NUMERICAAL INITIAL VALUE PROBLEMS in ODEs, 1971
    The classical reference on theory and applications

    Lambert, COMPUTATIONAL METHODS for ODEs, 1991
    Detailed discussion of ideas and practical implementation

    Shampine and Gordon, COMPUTER SOLUTION of ODES, 1975
    Adams methods and practial implementation of ODE "black box" solvers

    Butcher, NUMERICAL ANALYSIS of ODEs, 1987
    Comprehensive discussion on Runge-Kutta methods

    (mainly) ITERATIVE SOLUTION OF LINEAR SYSTEMS

    A. Householder, THE THEORY OF MATRICES IN NUMERICAL ANALYSIS
    The theoretical part by one of the grand masters; Outdated in some aspects

    G. H. Golub & Van Loan, MATRIX COMPUTATIONS,
    The basic modern reference

    Y. Saad, ITERATIVE METHODS for SPARSE LINEAR SYSTEMS,
    PWS Publishing, 1996. (Available on line at http://www-users.cs.umn.edu/~saad/books.html)

    R. Varga, MATRIX ITERATIVE ANALYSIS,
    Classical reference for the theory of iterations

    James Demmel, APPLIED NUMERICAL LINEAR ALGEBRA,
    SIAM, 1997

    Kelley, C. T., ITERATIVE METHODS for LINEAR and NONLINEAR EQUATIONS,
    SIAM 1995
    Eitan Tadmor