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]
Additional reading:
• M. J. D. Powell, On the maximum errors of polynomial approximations
defined by interpolation and by least squares criteria,
Computer J., 1967, vol. 9, pp. 404407,
[pdf file]
• The sin(x) subroutine in MATLAB
[pdf file]
Assignment #2
[ pdf file ]
... with answers [ 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 and LS solution of overdetremined systems
 SVD, PCA and LS rank approximations
 From discrete leastsquares to interpolation
Assignment #3 [pending]
 Least squares III  Gauss quadrature
• Additional reading:
On NewtonCotes quadrature,
Analysis of Numerical Methods, Issacson & Keller
• Lecture notes: On Numerical integration and EulerMacluarin formula

Numerical Solution of InitialValue Problems

Systems of ODEs. Existence, uniqueness & stability.

Euler's method. Multistep methods  stability and instability of Milne methods
 PredictorCorrector methods: the class of AdamsBashforthMoulton schemes
Assignment #4
[ pdf file ]

Consistency, stability and convergence
 Dahlquist theory. The root condition
 Convergence of multistep methods
Assignment #5
[ pdf file ]
 RungeKutta methods
 Local time stepping and error estimates
 Examples of RK4 and RKF5
 Stability and Convergence of RungeKutta methods
Assignment #6
[ pdf file ]
• Lecture notes: Numerical methods for approximate solution of ODEs
[ pdf file]

StrongStability Preserving (SSP) schemes. Methods for stiff equations
Additional reading:
• On strongstability preserving memthods: for
[linear problems] and [nonlinear problems]
Iterative Methods for Linear Systems of Equations
 Introduction and motivation. Stiff systems
 Classical methods: Jacobi, GaussSiedel, SOR, ...
• Lecture notes:
Jacobi, GaussSeidel and SOR iterations
[ pdf file]
Additional reading:
• The original work of [ D. Young Thesis (1950)]
and a Fourier look at the converegence analysis [Garabedian (1956)]
 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*
• Lecture notes: Gradient and conjugate gradient iterations
[pdf file]
Additional reading:
• "Iterative methods for linear systems" Demmel's lecture notes
[pdf file]
• Another look at (conjugate) gradient methods made easy
[pdf file]
• Recent review of Krylov spaces
[pdf file]
Numerical Optimization
 Introduction: fixed point iterations, loworder and and Newton's methods
• Iterative solution of nonlinear eqs  lecture notes by P. von Petersdorff
[pdf file]
 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

