Class information for Scientific Computing -- Math 7390-2 (Fall 2006)
MWF 10:40-11:30AM, Audubon 112 (old location Lockett 113)

!!! Midterm 2: Nov 29, 2006, We !!!

Syllabus

Homeworks assigned -- Exercises

Chapter 1 -> 25 exercises on pp.42--44 (all 27 exercises except 1.1 and 1.9); due Sep 22, 2006, Fr
Chapter 2 -> 1,2,3,4,5,6,7,10,12,13,14,15,16,17,18,19; due Oct 11, 2006, We
Chapter 2 -> 21,24,25,26,27,28,31,33,34,37,38, and the two exercises on p.86 myClassNotes06.pdf; due Oct 27, 2006, Fr
Chapter 3 -> 7,8,11,13,14,20,22; due Nov 20, 2006, Mo.
Chapter 4 -> 5,7,10,19,20,22; (I am not going to collect this set, but good exercises for the final)

Computer Problems

Chapter 1 -> 1.8 and 1.15; due Sep 25, 2006, Mo
Chapter 2 -> 2.16; due Oct 11, 2006, We
Chapter 3 -> 3.12; due Dec 1, 2006, Fr.

Homework grading policy

For each lecture you miss after the due date, I will take 10 points off.
I only accept print-outs of the code and numerical examples. No software turn-ins.

Lecture notes

My class notes

Miscellaneous

Timeline for class material

(if you missed classes, monitor here what we have done)

Aug 28, 2006, Mo -- Lecture 01 -- Week 35

1.1.1 Computational problems

Aug 30, 2006, We -- Lecture 02 -- Week 35

1.1.2 General strategy
1.2.1 Sources of approximation
1.2.2 Absolute error and relative error

Sep 01, 2006, Fr -- Lecture 03 -- Week 35

1.2.4 Truncation error and rounding error
1.2.5 Forward error and backward error

Sep 04, 2006, Mo

Labor Day

Sep 06, 2006, We -- Lecture 04 -- Week 36

1.2.6 Sensitivity and conditioning

Sep 08, 2006, Fr -- Lecture 05 -- Week 36

1.2.7 Stability and accuracy
1.3.1 Floating-point numbers
1.3.2 Normalization

Sep 11, 2006, Mo -- Lecture 06 -- Week 37

1.3.4 Rounding
1.3.5 Machine precision

Sep 13, 2006, We -- Lecture 07 -- Week 37

1.3.6 Subnormals and gradual underflow
1.3.7 Exceptional values

Sep 15, 2006, Fr -- Lecture 08 -- Week 37

1.3.8 Floating-point arithmetic

Sep 18, 2006, Mo -- Lecture 09 -- Week 38

2.1 Linear systems
2.2 Existence and uniquness
2.3.1 Vector norms

Sep 20, 2006, We -- Lecture 10 -- Week 38

2.3.2 Matrix norms
2.3.3 Matrix condition number

Sep 22, 2006, Fr -- Lecture 11 -- Week 38

2.3.4 Error bounds (error analysis using cond(A))

Sep 25, 2006, Mo -- Lecture 12 -- Week 39

2.3.5 Residual
2.4 Solving linear systems
2.4.1 Problem transformations

Sep 27, 2006, We -- Week 39

No class due to illness.

Sep 29, 2006, Fr -- Lecture 13 -- Week 39

Algo 2.2 Back-substitution; saxpy, sdot
2.4.3 Elementary elimination matrices

Oct 02, 2006, Mo -- Lecture 14 -- Week 40

2.4.4 Gaussian elimination and LU factorization
2.4.5 Pivoting

Oct 04, 2006, We -- Lecture 15 -- Week 40

2.4.5 Partial pivoting
Complete pivoting

Oct 06, 2006, Fr -- Lecture 16 -- Week 40

Fall break.

Oct 09, 2006, Mo -- Lecture 17 -- Week 41

Review for midterm 1. Midterm covers everything including 2.4.5.

Oct 11, 2006, We -- Lecture 18 -- Week 41

Partial pivoting continued
2.4.6 Implementation of Gaussian elimination

Oct 13, 2006, Fr -- Midterm 1 -- Week 41

Midterm 1.

Oct 16, 2006, Mo -- Lecture 19 -- Week 42

2.4.7 Complexity of solving linear systems

Oct 18, 2006, We -- Lecture 20 -- Week 42

2.4.8 Gauss-Jordan elimination
2.4.9 Solving modified problems
Sherman-Morrison formula for rank-one change

Oct 20, 2006, Fr -- Lecture 21 -- Week 42

2.4.10 Improving accuracy
Diagonal scaling
Iterative refinement
2.5 Special types of linear systems
2.5.1 SPD systems
Cholesky factorization

Oct 23, 2006, We -- Lecture 22 -- Week 43

2.5.2 Symmetric indefinite systems
2.5.3 Banded systems

Oct 25, 2006, We -- Lecture 23 -- Week 43

3.1 Linear least squares
f(x) = ||r||_2^2 is a convex functional, therefore min exists
Polynomial fitting
3.2 Existence and uniqueness

Oct 27, 2006, Fr -- Lecture 24 -- Week 43

3.2.2 Orthogonality and orthogonal projectors
P orthogonal projector, then ||P||_2 = 1
Various projection interpreations that lead to normal equations
3.4 Sensitivity and conditioning

Oct 30, 2006, Mo -- Lecture 25 -- Week 44

3.4 Sensitivity and conditioning continued
Perturbations to right hand side
Perturbations to the matrix

Nov 01, 2006, We -- Lecture 26 -- Week 44

Example 3.5 Sensitivity and conditioning
Example 3.6 Condition squaring effect
3.4 Problem transformation
3.4.1 Normal equations
cond(A^tA) = [cond(A)]^2

Generic blurb for the course

Prerequisite: Basic concepts of numerical analysis, basic knowledge of linear algebra, and basic programming skills in C, Matlab or other computer language. Preferably Math 4065, 4066 or equivalents.

Text: Scientific Computing: An introductory survey by Michael T. Heath, McGraw Hill 2002, Lecture notes

This course serves as a foundation for analysis, design, and implementation of numerical methods. In particular, it provides an in-depth view of practical algorithms for solving large-scale linear systems of equations arising in the numerical implementation of various problems in mathematics, engineering and other applications.

The course will cover the following material:

• Linear algebra and numerical linear algebra refresher, in particular, solutions to system of linear equations.
• Matrix factorizations.
• Linear least squares.
• Ortogonalization methods.
• Eigenvalue problems.
• Basic iterative methods.
• Krylov subspace methods.
• Preconditioning techniques.
• Multilevel methods such as multigrid.

The course will focus on both the theoretical aspects and the numerical implementation of these methods. Evaluation will be based upon both theoretical and numerical projects.