COL 726 : Numerical analysis and scientific computing


Instructor

Amit Kumar
Office : Room # 417, Bharti Building
Email : amitk@cse.iitd.ac.in
Phone : (ext) 1286.

Teaching Assistants

Indu Joshi, Moin Ul Islam Asmi, Anushka Goyal

Announcements

Classroom shifted to LH 408.

Class Timings

Slot J

Homeworks



1. Homework 1 (due Jan 19, 2018)
2. Homework 2 (due Feb 2, 2018)
3. Homework 3 (due March 12, 2018)
4. Homework 4 (due April 1, 2018)
5. Homework 5 (due April 16, 2018)
6. Homework 6 (due May 4, 2018)


Lecture Topics

Lecture 1: Introduction, floating point representation, machine precision. ([H] Chapter 1).
Lecture 2: Condition number, floating point operations ( [H] Chapter 1, [TB] Chapter 12)
Lecture 3: Stability, review of linear algebra ([H] Chapter 1, [TB] Chapter 14, Chapter 15, Chapter 1)
Lecture 4: Review of linear algebra
Lecture 5: Linear transformations, norms of matrices ([TB] Chapter 3)
Lecture 6: Singular value decomposition, properties of matrices using SVD ([TB] Chapter 4, Chapter 5)
Lecture 7: Proof of SVD Theorem, low rank approximation. (TB Chapter 4, Chapter 5)
Lecture 8: Applications of SVD. Condition Number of a matrix. (TB Chapter 5, Chapter 12)
Lecture 9: Latent Semantic Indexing
Lecture 10: QR factorization, QR using Gram Schmidt. ([TB] Chapter 7,8)
Lecture 11: Householder transformation, QR factorization via Householder. ([TB] Chapter 10)
Lecture 12: Stability of QR factorization. Least Squares Problem. ([TB] Chapter 16, Chapter 11)
Lecture 13: Conditioning of Least Squares Problem and solution using QR factorization. ([TB] Chapter 18, 19)
Lecture 14: Guassian Elimination and LU factorization ([TB] Chapter 20)
Lecture 15: LUP factorization and stability of Gaussian Elimination ([TB] Chapter 21, 22)
Lecture 16: Positive semidefinite matrices and Cholesky factorization ([TB} Chapter 23)
Lecture 17: Eigenvalues: existence, diagonalizability, applications to ODE ([TB] Chapter 24, [H] Example 9.7)
Lecture 18: Schur factorization, eigenvalues of symmetric matrices, Reduction to Hessenberg form ([TB] Chapter 25, 26)
Lecture 19: Power iteration, convergence, Rayleigh quotient ([TB] Chapter 27)
Lecture 20: Pagerank Algorithm
Lecture 21: Inverse iteration, Rayleigh iteration and cubic convergence ([TB] Chapter 27)
Lecture 22: Simultaneous iteration and convergence, conditioning of eigenvalue problems ([H] Chapter 4.3, 4.5.5)
Lecture 23: Convex functions and unconstrained optimization ([H] Chapter 6.2, [BV] Chapter 3)
Lecture 24: More on convexity, Gradient Descent ([H] Chapter 6.3, [BV] Chapter 9.3)
Lecture 25: Smoothness, strong convexity, analysis of gradient descent for smooth and strongly convex functions ([BV] Chapter 9.3)
Lecture 26: Preconditioning in gradient descent, Newton's method and various ways to derive Newton's method, affine invariance([BV] Chapter 9.5)
Lecture 27: Optimization with equality and inequality constraints, duality, KKT conditions ([BV] Chapter 5.1, 5.5)
Lecture 28: Examples of KKT conditions ([BV] Chapter 5.5)
Lecture 29: Newton's method with equality constraints, some basic ideas of barrier methods for inequality constraints ([BV] Chapter 10.2.1)
Lecture 30: IVP for Ordinary Differential Equations, concept of stable solutions, accuracy (Heath Chapter 9.1, 9.2)
Lecture 31: Euler's method, Implicit Euler's method, trapezoid method, solving an equation using fixed point iteration (Heath Chapter 9.3, 5.5.2)
Lecture 32: More on solving systems of equations using Newton's method and its variants (Heath Chapter 5.5.3, 5.5.4)
Lecture 33: Taylor series methods, problems with Taylor series methods, accuracy of Taylor's method (Heath Chapter 9.3.5)
Lecture 34: Runge Kutta method, derivation of 2nd order and 3rd order methods (Heath Chapter 9.3.6)
Lecture 35: Multi-step methods, derivation of multi-step methods using interpolation (Heath Chapter 9.3.8)

Pre-requisites

First course in linear algebra, calculus and programming.
Warning : the course will make heavy use of linear algebra, so if you are not comfortable with fundamentals of linear algebra, you should not take this course.
You will be expected to write programs in MATLAB.

Books

There is no required textbook for this course. But most of the topics covered can be found in one of these books.

1. [CK] Numerical Mathematics and Computing, by Ward Cheney and David Kincaid.
2. [H] Scientific Computing : an introductory survey, by Michael T. Heath.
3. [TB] Numerical Linear Algebra, by Llyod N. Trefethen and David Bau.
4. [BV] Convex Optimization , by Boyd and Vanderberghe.

Grading

25% : Homework and Programming Assignments
20% : Each minor exam
35% : Major exam