# Numerical Analysis I

## AMSC 666, Fall 2009

### Course Information

 Lecture Room 4122 CSIC Bldg. #406 TuTh 2-3:15pm Note special place: Math Bldg. Rm. 0304 on Tue 9/22 Note special place: Math Bldg. Rm. 0304 on Tue 9/24 Instructor Professor Eitan Tadmor Contact tel.: x5-0648   Email: Eitan Tadmor Office Hours By appointment ( Eitan Tadmor ) CSCAMM 4122 CSIC Bldg. #406 Teaching Assistant Amanda Galante Eitan Tadmor Midterm Tue 10/6 2-3:15pm 4122 CSIC Bldg. #406 NOTE: you may use a calculator but no other additional material is allowed Final Thu 12/17 10:30-12:30pm 4122 CSIC Bldg. #406 (open material} Grading 25% Homework, 25% Mid-Term, 50% Final

### Course Description

1. #### Ten steps of 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. A general overview
• Gramm mass matrix
• Ill-conditioning of monomials in L2

3. Least Squares Approximations II. (Generalized) Fourier expansions
• Bessel, Parseval, ...
• Orthogonal polynomials: Legendre, Chebyshev, Sturm's sequence
##### Assignment #1: [ pdf file ] ... with answers [ pdf file]
4. Least Squares Approximations III. Discrete expansions
• Examples of discrete least squares.
• From discrete least-squares to interpolation

5. Interpolation I. Lagrange and Newton interpolants
• Divided differences
• Equi-distant points
• Synthetic calculus
• Forward backward and centered formulae
##### Assignment #2 [ pdf file ]
6. Interpolation II. Error estimates.
• Runge effect
• region of analyticity
##### Lecture notes: Interpolation Error [ pdf file ]
7. Interplolation III. Trigonometric interpolation
• FFT
• truncation + aliasing
• error estimates
• elliptic solvers
• fast summations ( - discrete convolution)
##### 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]

##### Assignment #3 [ pdf file ] ... with answers [ pdf file]
8. Min-Max approximations
• The alternation theorem
• Chebyshev interpolant and its distance from the min-max polynomial
• Economization
• 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. 404-407, [pdf file]

The sin(x) subroutine in MATLAB [pdf file]

9. Modern aspects of approximation
• Error Estimates - Jackson, Bernstein and Chebyshev
• smoothness and regularity spaces
##### MID-TERM [ pdf file ] ... and its answers: [ pdf file ]
10. Approximation with derivatives and rational approximations
• Hermite interpolation
• piecewise interpolation: Splines
2. #### Numerical Differentiation and Numerical Integration

1. Numerical differentiation
• Polynomial and spline interpolants - Error estimates
• Equidistant points: synthetic calculus; Richardson extrapolation
• Spline and trigonometric interpolation
3. ##### Lecture notes: A Very Short Guide to Jacobi Polynomials [ pdf file]
4. Numerical integration with equidistant points
• Newton-Cotes formulae
• Composite Simpson's rule

3. #### Solution of Linear System of Equations - Iterative Methods

1. Introduction
2. Fixed point iterations
3. ##### Lecture notes: Matrices -- norms, eigenvalues and powers [ pdf file]
4. The basic algorithms:
• Jacobi, Gauss-Seidel and SOR methods
5. ##### Lecture notes: Jacobi, Gauss-Seidel and SOR iterations [ pdf file]
• On the Fourier approach to the SOR: [Garabedian (1956)] [LeVeque & Trefethen (1988)]
• The original work of [ D. Young Thesis (1950)]
##### Assignment #7 [ pdf file ]
6. Non-stationary methods
7. Steepest descent; Conjugate gradient method
8. ADI and dimensional splitting methods
9. Multigrid
10. Preconditioners
4. #### Eigen-solvers

1. Introduction
2. Similarity transformations, Rayleigh quotations
3. Power and inverse power method
4. Householder transformations
5. Hessenberg form and the QR method
##### Assignment #9 [ pdf file ]
7. Singular Value decomposition
8. Preconditioners
9. The divide and conquer method

### 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

E. Isaacson & H. Keller, ANALYSIS of NUMERICAL METHODS, Wiley
The 'First'; Proofs; out-dated in certain aspects; Encrypted message in Preface

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,..

B. Wendroff, THEORETICAL NUMERICAL ANALYSIS, Academic Press, 1966
Only the 'Proofs'; elegant presentation

APPROXIMATION THEORY

E. W. Cheney, INTRODUCTION TO APPROXIMATION THEORY
Classical

P. Davis, INTERPOLATION & APPROXIMATION, Dover

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

(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

J. H. Wilkinson HANDBOOK for AUTOMATIC COMPUTATIONS, 1971
Modern theory started there with the grand master...

D. Young, ITERATIVE SOLUTION OF LARGE linear SYSTEMS, Academic Press, 1971
Excellent detailed account

(mainly) EIGEN-SOLVERS

B. Parllett, THE SYMMETRIC EIGENVALUE PROBLEM
Recommended

J. H. Wilkinson The ALGEBRAIC EIGENVALUE PROBLEM, 1965
The classical reference