Math191

Scientific Computation I

Class meets Tuesdays, Thursdays, 2:00 PM to 3:15 PM in Phillips 301

Office hours: M-Th, 11:00 AM to 12:00 PM, (Phillips 307), e-mail appointment

[Motivation] [Objectives] [Syllabus] [Grading] [Texts] [Assignments] [Computing] [Projects] [Midterm] [Final]

Motivation

Analytical mathematics furnishes powerful tools for describing natural phenomena. Finding closed form solutions is however often impeded by complex geometry, complicated physical models or even known to be unattainable from theory. In such situations numerical methods provide the tool that allows solutions to practical problems to be found. Most numerical methods start from an analytical background, typically linear algebra and differential equation theory. But the development is then guided by the need to effectively find accurate solutions and the limitations imposed by computer architecture. The resulting discipline has come to be known as Scientific Computation and has assumed a significant role in all branches of science.

Course Objectives

The objective of this course is to introduce the basic ideas and algorithms that find wide applicability within computational models at an advanced undergraduate, beginning graduate student level. The subject matter within the course is that typical for a numerical methods class, but we will also discuss applications to more properly give the flavor of scientific computation.

Syllabus

·         Floating point arithmetic

·         Approximation of single-variate functions: interpolation, least squares, min-max

·         Numerical differentiation and integration

·         Linear systems

·         Non-linear equations and systems

·         Eigenproblems

·         Differential equations

·         Integral equations

Grading Policy

Grading shall be determined based on homework (HW, 48 points), supplementary reading (SR, 8 points), midterm examination (ME, 20 points) and final examination (FE, 24 points). The number of points accumulated during classwork is mapped to a graduate grade as shown in the following table.

 

H+

93-100 points

Clear Excellence

H

86-92 points

 

H-

80-85 points

 

P+

75-79 points

Entirely Satisfactory

P

70-74

 

P-

65-69

 

L+

60-64

Low Passing

L

55-59

 

L-

50-54

 

F

0-49

 

Course Texts

One of the tenets of graduate study is the ability to critically examine multiple sources in order to verify theories and to enhance understanding. It is expected and required that the student supplement the course text with reading from other sources.

Basic text: A First Course in Numerical Analysis, Anthony Ralston & Philip Rabinowitz

Lecture notes

Lecture
Date

Topic

Notes

Lecture
Date

Topic

Notes

1, 8/30

Floating point arithmetic

.pdf

16,  10/25

ODE: Runge-Kutta, multistep comparison. Stiff equations. ODE systems.

.pdf

2, 9/1

Error analysis, approximation criteria, types

.pdf

17, 10/27

ODE: Deferred corrections.

 

3,9/6

Approximation theorems, Lagrange interpolating polynomial

.pdf

18, 11/1

Least squares approximation. Orthogonal polynomial approximation. Fast Fourier transformation

.pdf

4, 9/8

Newton interpolating polynomial

.pdf

.m

19, 11/3

Midterm exam

 

5, 9/13

Difference calculus

.pdf

.nb

20, 11/8

Min-max approximation

.pdf

6, 9/15

Hermite interpolation, splines

.pdf

21, 11/10

Scalar nonlinear equations, simple iteration, secant, Newton, parabolas

.pdf

7, 9/20

Spline algorithms

.pdf

22, 11/15

Discussion of HW7 hint

.nb

8, 9/22

Numerical differentiation

.pdf

23, 11/17

Zeros of polynomials

.pdf

9, 9/29

Newton-Cotes integration

.pdf

24, 11/22

Held during extended L20-23

 

10, 10/4

Newton-Cotes integration error, orthogonal polynomials, Gauss integration.

.pdf

25, 11/29

Not held

 

11, 10/6

Richardson extrapolation, Romberg integration.

.pdf

26, 12/1

Linear systems. Matrix formulation of Gauss elimination. LU factorizations. Crout, Doolittle factorizations. BLAS, LAPACK. Nonlinear systems.

.pdf

12, 10/7

Romberg implementation. Recursive integration. (Reschedule of 9/27 class)

.pdf

romberg.f90

27, 12/6

Real-world examples

 

13, 10/11

ODE – Review of analytical solutions. Taylor series method. Undetermined coefficients.

.pdf

28, 12/8

Final review

 

14, 10/13

ODE – Multistep methods, implicit, explicit, predictor-corrector. Single step methods – Runge-Kutta

.pdf

 

 

 

15, 10/18

ODE - Multistep, Runge-Kutta truncation error, stability.

 

 

 

 

General bibliography

The following texts serve as general background material. Students are encouraged to actively read from these texts material related to the current lecture. Homework and final examination questions from this material should be expected.

Assignments

Homework assignments

During the course, 12 homework assignments shall be given. Each assignment shall contain 4 questions worth 0.5 point each and 2 problems which will involve computer work: coding, running parameter sets, analysis of results. Homework assignments are given every Friday and due one week thereafter. No assignments shall be given prior to the midterm and the final examinations.

Date issued

Date due

Topic

Homework

Solution

9/1

9/8

Floating point arithmetic, basic tools

.pdf

.pdf

.m

.c

9/9

9/16

Global interpolating polynomial

.pdf

.pdf

.m

.nb & .html

9/16

9/23

Hermite, spline interpolation

.pdf

.pdf

.m

.nb & .html

9/23

9/30

Numerical differentiation

.pdf

.pdf

.m

.nb & .html

10/5

10/14

Numerical integration (counts as 2 HW’s)

.pdf

.pdf

3.m gl.m

6.m

.nb & .html

10/25

11/1

Review questions

.pdf

.pdf

11/10

11/29

Ordinary differential equations (counts as 2 HW’s)

.pdf

Q1 Hint: RK4.nb

 

11/29

12/8

Linear and nonlinear systems of equations

.pdf

 

 

12/8

12/15

Review questions – Final exam preparation

(counts as 2 HW’s)

.pdf

 

 

 

 

 

 

 

.pdf = Portable Document File, .html = Web page, .nb = Mathematica notebook .m = Matlab m file .f90=Fortran 90 source file

Supplementary reading assignments

Two reading assignments shall be given, each graded with 4 points. The purpose of the reading assignments is to introduce students to the tasks involved in research work. Points are awarded to this end as follows:

·         1 point for reading the assigned text (I'll ask a quick question);

·         1 point for background research, i.e. placing the assigned text in the context of previous work for instance by reading the references from the assigned text;

·         1 point for forward research, i.e. investigating the ramifications of the assigned text using tools such as the Science Citation Index ;

·         1 point for working through some of the results from the assigned text,

Students can freely choose when they want to carry out their reading assignment, but beware the temptation of putting things off until the last week of the semester. A rack with suitable papers is available in my office starting Sep. 8. A short report on each reading assignment must be prepared and turned in before the end of the semester.

A very good option is to choose from among the list developed by Nick Trefethen:

Trefethen's list of 13 classic papers in applied mathematics

  • R. Courant, "Variational methods for the solution of problems of equilibrium and vibrations," Bull. Amer. Math. Soc., 49 (1943), pp. 1–23.
  • R. Fletcher and M.J.D. Powell, "A rapidly convergent descent method for minimization," Comput. J., 6 (1963/1964), pp. 163–168.
  • G. Wanner, E. Hairer, and S.P. Nørsett, "Order stars and stability theorems," BIT, 18 (1978), no. 4, pp. 475–489.
  • N. Karmarkar, "A new polynomial-time algorithm for linear programming," Combinatorica, 4 (1984), no. 4, pp. 373–395.

Another list from Trefethen’s group:

LINEAR ALGEBRA - SYSTEMS OF EQUATIONS AND LEAST-SQUARES
  Frankel (1950)                        optimal omega for SOR iteration
  Hestenes & Stiefel (1952)              the conjugate gradient iteration
  Young (1954)                           theory of classical iterative methods
  Householder (1958)                     QR decomposition
  Wilkinson (1961)                       error analysis for systems of eqs.
  Golub (1965)                           least-squares problems
  Strassen (1969)                        Gaussian elimination is not optimal
  George (1973)                          nested dissection
  Gill, Golub, Murray & Saunders (1974)  updating matrix factorizations
  Concus, Golub & O'Leary (1976)         preconditioned conjugate gradients
  Meijerink & van der Vorst (1977)       incomplete LU preconditioning
  Skeel (1980)                           iterative refinement and stability
  Saad & Schultz (1986)                  GMRES for nonsymmetric systems
  
LINEAR ALGEBRA - EIGENVALUES AND SVD
  Jacobi (1846)                         Jacobi's method for matrix eigenvalues
  Henrici (1958)                         convergence of the Jacobi method
  Rutishauser (1958)                     the LR algorithm
  Kublanovskaya (1961)                   the QR algorithm
  Francis (1961)                         the QR algorithm
  Golub & Kahan (1965)                   computation of the SVD
  Moler & Stewart (1973)                 QZ algorithm for gen'd eigenvalues
  Cuppen (1981)                          divide and conquer for eigenvalues
  
OPTIMIZATION
  Dantzig (1951)                         simplex method for linear programming
  Davidon (1959)                         variable metric methods
  Fletcher & Powell (1963)               DFP quasi-Newton update formula
  Broyden/Fletcher/Goldfarb/Shanno (`70) BFGS quasi-Newton update formula
  Karmarkar (1984)                       interior pt methods for linear prog.
 
INTEGRATION
  Golub & Welsch (1969)                        Gauss quadrature rules
  de Boor (1971)                         adaptive quadrature algorithms
  
APPROXIMATION
  Remes (1934)                           Remes algorithm for Chebyshev approx.
  Schoenberg (1946)                      splines
  Powell (1967)                          near-optimality of Chebyshev interp.
  Reinsch (1967)                         smoothing with splines
  Cox (1972)                             calculation with B-splines
  de Boor (1972)                         calculation with B-splines
 
OTHER
  Aitken (1932)                          Aitken extrapolation
  Cooley & Tukey (1965)                  the fast Fourier transform
  Greengard & Rokhlin (1987)             fast multipole methods
 
ODEs
  Curtiss & Hirschfelder (1952)          stiffness and BD formulas
  Dahlquist (1956)                       stability and convergence
  Dahlquist (1963)                       A-stability
  Butcher (1965)                         Runge-Kutta methods
  Gear (1969)                            stiff ODEs
  Wanner, Hairer & Norsett (1978)        order stars and stability theorems
  
ELLIPTIC PDEs
  Peaceman & Rachford (1955)             ADI
  Douglas (1955)                         ADI
  Strang (1971 or 1973)                  finite elements and approx. theory
  Buzbee, Golub & Nielsen (1970)         fast Poisson via cyclic reduction
  Hockney (1965)                         fast Poisson via FFT
  Fedorenko (1961)                       multigrid methods
  Brandt (1977)                          multigrid methods
 
PARABOLIC AND HYPERBOLIC PDEs
  Courant, Friedrichs & Lewy (1928)      the CFL condition
  Crank & Nicolson (1947)                finite differences for parabolic PDE
  O'Brien, Hyman & Kaplan (1951)         Von Neumann stability analysis
  Lax & Richtmyer (1956)                 general stability theory
  Lax & Wendroff (1960,1962,1964)        methods for solving conservation laws
  Kreiss (1962)                          more general stability theory
  Orszag (1971)                          spectral methods
  Kreiss and Oliger (1972)               spectral methods
  Gustafsson, Kreiss & Sundstrom (1972)  stability of boundary conditions
  Chorin (1973)                          vortex methods for CFD
  Engquist & Majda (1977)                absorbing boundary conditions

 

 

Computational work

It is essential that students acquire a basic familiarity with the process of developing and using scientific software. The homework assignments shall contain gradually more difficult problems that are intended to be solved using programs written by the students using Matlab, Mathematica, C or Fortran.

Scientific Computing Club

In order to aid proficiency in computer techniques attendance at the extracurricular Scientific Computing Club is encouraged. Especially active students will be awarded bonus points towards their MATH 191 grade (up to maximum of 8 points). Scheduling will be announced on Sep. 8. 

Midterm examination preparation

The midterm examination will be held Thursday, November 3 from 2:00 PM to 3:15 PM in Phillips 301.

Questions similar to those students can expect on the midterm examination are presented in HW06.

Midterm solution

Final examination preparation

The final examination will be held Saturday, December 17 from 4:00 PM to 7:00 PM in Phillips 301.

Questions similar to those students can expect on the final examination are presented in HW10.

Final solution