Numerical Analysis I
AMSC 666, Fall 2017
Course Information
Course Description

Approximation Theory
 General overview
 On the choice of norm: leastsquares vs. the uniform norm
 Weierstrass' density theorem; Bernstein polynomials
 Least squares approximations I
 Least squares: illconditioning 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]
 MinMax approximations: Chebyshev interpolant; economization
 Error estimates in interpolation*
 Polynomial interpolation: Runge effect, region of analyticity
 Trigonometric interpolation: Sobolev leastsquares 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]
 Least squares II  the finitedimensional case
 QR and SVD
 From discrete leastsquares to interpolation
Assignment #3
 Least squares III  Gauss quadrature

Numerical Solution of InitialValue Problems

Systems of ODEs. Existence, uniqueness & stability.

Euler's method. StrongStability Preserving (SSP) schemes

Multistep methods
 The example of Milne method
 PredictorCorrector methods: the class of AdamsBashforthMoulton schemes

Consistency, stability and convergence
 Dahlquist theory. The root condition
 Convergence of multistep methods
 RungeKutta methods
 Local time stepping and error estimates
 Examples of RK4 and RKF5
 Stability and Convergence of RungeKutta methods

Methods for stiff equations
Iterative Methods for Linear Systems of Equations
 Introduction and motivation. Stiff systems
 Classical methods: Jacobi, GaussSiedel, SOR, ...
 Energy functionals and gradinet methods
 Steepest descent
 Conjugate gradient method
 ADI and dimensional splitting methods
 Nonstationary methods
 Polynomial equations: local vs. global methods
 Preconditioners
 Multigrid mthods*; GMRES*
Numerical Optimization
 Introduction
 Steepest descent and CG methods
 Line search methods
 Newton's and quasiNewton methods
 Rates of converegence
 GaussNewton and related methods
References
GENERAL TEXTBOOKS
K. Atkinson, An INTRODUCTION to NUMERICAL ANALYSIS, Wiley, 1987
S. Conte & C. deBoor, ELEMENTARY NUMERICAL ANALYSIS, McGrawHill
User friendly; Shows how 'it' works; Proofs, exercises and notes
G. Dahlquist & A. Bjorck, NUMERICAL METHODS, PrenticeHall,
User friendly; Shows how 'it' works; Exercises
A. Ralston & P. Rabinowitz, FIRST COURSE in
NUMERICAL ANALYSIS, 2nd ed., McGrawhill,
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 & eigensolvers,
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 INITIALVALUE PROBLEMS
E. Hairer, S.P. Norsett and G. Wanner, SOLVING ODEs I: NONSTIFF PROBLEMS,
SpringerVerlag, 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 RungeKutta 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://wwwusers.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

