General course description
Instructor: Da Kuang
TA: Jialin Liu

References

• [SC] Michael Heath, Scientific Computing, 2nd edition.
• [NLA] Trefethen and Bau, Numerical Linear Algebra, 1996. [SIAM]
• [NA] (Official) Burden and Faires, Numerical Analysis, 9th or 10th edition.
• [LNE] Kelley, Iterative methods for linear and nonlinear equations, 1995. (free)


• A good summary of the official textbook in slides: [link1] [link2]
• A more practical treatment: Cleve Moler, Numerical Computing with Matlab.
• Relevant slides from [EE103]
• Matlab tutorial: [link]

Grading

• 60% Homework
• 20% Midterm
• 20% Final exam

Disclaimer

• No late homework allowed. However, there are no penalties for medical reasons or emergencies. You must submit a doctor's note or an official letter explaining the emergency.
• Attendance is not counted towards your final grade. However, if you missed a class without a valid reason, the instructor will not answer your questions that have been addressed in-class.

Programming Environments

• We will use Matlab or Octave for programming assignments.

Homework

Please note that while discussion is allowed and encouraged, individual students must write up their own answers and computer programs.
All the students must observe the conduct code.

• [10%] HW1
• [10%] HW2
• [10%] HW3
• [10%] HW4
• [10%] HW5
• [10%] HW6

Exercise Sets

• Exercise Set 1
• Exercise Set 2

Syllabus

• QR factorization, least squares
  Why is QR factorization useful?
  What's the difference between Gram-Schmidt and Householder algorithms for QR?
  What's the difference between normal equation method and QR for discrete least squares?
  How to fit a polynomial to a continuous function?
  Implementation of Gram-Schmidt, Householder, normal equation method
  
  
• Computing eigenvalues and eigenvectors
  How are eigenvalues and eigenvectors computed practically on a computer?
  Why does power method converge to the leading eigenvector?
  How to compare the speed of different algorithms?
  Implementation of power iteration, QR algorithm; Plotting the convergence
  
  
• Solving nonlinear systems of equations
  When does Newton's method converge for nonlinear systems of equations?
  Implementation of Newton's method, Broyden's method
  Comparing the convergence between Newton's method and Broyden's method
  
  
• Solving initial value problems for ODE
  What kind of ODE systems can be solved accurately? (stability)
  How to choose the step size h in Euler's method?
  How to improve the accuracy and stability of Euler's method? (Runga-Kutta; backward Euler)
  When does an explicit method for IVP have difficulty? (stiffness)
  Implementation of Euler's method, backward Euler's method; Plotting the convergence
  
  
• Solving boundary value problems for ODE
  Transforming BVP to solving linear/nonlinear systems of equations (shooting method, finite difference)
  Transforming BVP to function fitting problems (collocation, Galerkin FEM)
  Implementation of finite difference, collocation
  
  

Schedule

Date	Mon	Wed	Fri
Sep 23			Introduction / Logistics QR factorization
Sep 26 Sep 28 Sep 30	Householder transformation Reading: SC 3.5	Least squares for data fitting Algorithms for least squares Reading: SC 3.2, 3.4 HW1 out	Least squares for function fitting Orthogonal polynomials Reading: SC 7.3.4; NA 8.2
Oct 3 Oct 5 Oct 7	Eigenvalues and eigenvectors Power method Inverse iteration Reading: SC 4.5.1-2; NLA 25	Rayleigh quotient Rayleigh quotient iteration Reading: SC 4.5.3; NLA 27 HW1 due; HW2 out	Simultaneous iteration QR algorithm Reading: SC 4.5.5-6; NLA 28
Oct 10 Oct 12 Oct 14	Hessenberg and tridiagonal forms Practical QR algorithm Reading: NLA 26, 29	Nonlinear systems of equations Fixed-point iteration Reading: SC 5.6.1; LNE 4.2 HW2 due; HW3 out	Newton's method Reading: SC 5.6.2; LNE 4.3, 5.1
Oct 17 Oct 19 Oct 21	Quasi-Newton methods Reading: SC 5.6.3; LNE 7.3	Steepest descent method Reading: SC 6.5.2 HW3 due Exercise Set 1 ready	Midterm review ODE introduction
Oct 24 Oct 26 Oct 28	Stability of ODE IVP solutions Reading: SC 9.1, 9.2	Euler's method Reading: SC 9.3.1	Midterm [20%]
Oct 31 Nov 2 Nov 4	Error analysis of Euler's method Reading: SC 9.3.2	Runga-Kutta methods Reading: SC 9.3.5-6; NA 5.4 HW4 out	Backward Euler's method Reading: SC 9.3.3
Nov 7 Nov 9 Nov 11	Stiffness Reading: SC 9.3.4	(buffer) HW4 due; HW5 out	(Veterans Day holiday)
Nov 14 Nov 16 Nov 18	Boundary value problems Shooting method Reading: SC 10.1, 10.3	Finite difference method SC 10.4	Collocation method Galerkin method SC 10.5 HW5 due; HW6 out
Nov 21 Nov 23 Nov 25	(buffer)	(Cancelled)	(Thanksgiving)
Nov 28 Nov 30 Dec 2	B-splines HW6 due Exercise Set 2 ready	Galerkin FEM SC 10.6	Special topic Final review
Dec 5 Dec 7 Dec 9		Final exam [20%] 3pm-6pm

---