COL 726 : Numerical analysis and scientific computing

Course Coordinator

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

Teaching Assistants

Aniket Mishra, Dhairya Gupta, Ramneet Singh

Announcements

Audit policy: Pass on B- grade or better.

Class Timings

Slot M: Monday, Thursday, 3:30-5:00pm. Venue: LH 527

Homeworks



Homework 1 (due on Jan 23, 2024)
Homework 2 (due on Feb 21, 2024)
Homework 3 (due on , April 12 2024)

Lecture Topics

Lecture 1 (1.1.24) : Introduction, Errors in computation, Floating Point Representation ([H] Chapter 1)
Lecture 2 (4.1.24): Machine Precision, Cancellation errors, Norms of vectors, Condition number ([H] Chapter 1,2.3.1, [TB] Chapters 3,12)
Lecture 3 (8.1.24): Condition number and examples, Backward Stability ([TB] Chapters12, 14)
Lectrue 4 (11.1.24): Norm of a matrix, invariance of 2-norm under unitary transformation. ([TB} Chapter 3)
Lecture 5 (15.1.2024): Linear Algebra review (change of basis), Singular value decomposition and implications ([TB] Chapters 3, 4)
Lecture 6 (18.1.2024): Completion of the proof of the SVD theorem, low-rank approximation by SVD. ([TB] Chapter 5)
Lecture 7 (25.1.2024): Applictions of SVD, Quiz I
Lecture 8 (29.01.2024): Least Squares, Normal Equations, Least Squares from QR facrtorization ([TB] Chapters 7,11)
Lecture 8 (01.02.2024): Conditioning of Least Squares, Gram Schmidt Orthonormalization ([H] Chapter 3.2, 3.3, [TB] Chapter 8)
Lecture 9 (05.02.2024): Modified Gram Schmidt and stability ([TB] Chapter 8, 19)
Lecture 10 (08.02.2024): Householder Transformation, QR Factorization using Householder ([TB] Chapter 10)
Lecture 11 (12.02.2024): Gaussian Elimination, LU Factorization, Partial Pivoting ([TB] Chapter 20, 21)
Lecture 12 (15.02.2024): Cholesky Decomposition ([TB] Chapter 22)
Lecture 13 (09.03.2024): Eigenvalues and some applications ([TB] Chapter 25)
Lecture 14 (11.03.2024): Schur Factorization, Power Iteration ([TB] Chapter 24, 27)
Lecture 15 (14.03.2024): Inverse Iteration, Rayleight Quotioent, Inverse Iteration with Shifts ([TB] Chapter 27)
Lecture 16 (18.03.2024): Krylov Spaces, Arnoldi Iteration ([TB} Chapter 33, 34)
Lecture 17 (21.03.2024): Arnoldi Iteration, Quiz II ([TB] Chapter 33, 34)
Lecture 18 (04.04.2024): Arnoldi Iteration and Eigenvalue computation ([TB] Chapter 33, 34)
Lecture 19 (06.04.2024): Non-linear Equations; bisection method, fixed point iteration convergence ([H] Chapter 5)
Lecture 20 (08.04.2024): Non-linear Equations: Newton's method, Secant method, convergence ([H] Chapter 5)
Lecture 21 (11.04.2024): Non-linear Equations: Newtons' method in Higher Dimensions, Broyden's method, Optimization and convex functions ([H] Chapter 6)
Lecture 22 (15.04.2024): Convex functions in higher dimensions and their properties ([H] Chapter 6)
Lecture 23 (18.04.2024): Unconstrained Optimization: Gradient Descent, Newton's method ([H] Chapter 6)

Pre-requisites

First course in linear algebra, calculus and programming.
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.

Programming Language

Codes in the assignments can be done in MATLAB or Python (numpy). Some online tutorials/references for numpy:
1. https://cs231n.github.io/python-numpy-tutorial/ - quick crash course on Jupyter Notebooks, Colab, Python, Numpy, Scipy and Matplotlib.
2. https://numpy.org/devdocs/user/absolute_beginners.html - more detailed introduction
3. https://assets.datacamp.com/blog_assets/Numpy_Python_Cheat_Sheet.pdf : numpy cheatsheet
4. https://youtu.be/pJoYVxgI840?si=FqzRkSBcJYGtNAmb - basic youtube tutorial

Grading

30% : Homework, Quizzes and Programming Assignments
30% : Minor exam
40% : Major exam