Lectures: Mon, Wed between 12:30-13:45 at CAS Z25

Instructor: Emre Mengi Office: SCI 114 E-mail: emengi@ku.edu.tr Phone: (212)338-1658 Office Hours: Thr 13:15-15:15

Course Description: This course concerns the numerical solution of linear systems, linear least squares problems (best approximate solution for an inconsistent linear system), eigenvalue and singular value problems. We will introduce numerical algorithms for the solution of these problems on a computer, and analyze their efficieny and accuracy in the presence of rounding errors. There will be a fine balance between theoretical and computational issues. The Krylov-subspace based iterative algorithms will be covered as well as the direct algorithms.(See the course syllabus for issues such as grading and the formats of the exams.)Announcements: The final will be held on January 19th, Wednesday between 12:00-15:00 at ENG Z15. It includes all topics covered throughout the semester with emphasis on topics covered after the midterm specifically backward error analysis, linear systems and their numerical solution, eigenvalues and their numerical solution. Solutions to homework 3 and homework 4 are available now. Homework 5 (due on Jan 24th, Tue by 5pm; the deadline is tight this time) is also available now. There are nineteen questions. But you are expected to return the solutions to only any six of them. I highly recommend to go over all of the questions. This should help you a great deal for the final. The m-files that you may need for this homework are provided below. random_growth_factor.m plot_growth_factor.m plot_condition_number.m growth_factor.m Homework 4 (due on Dec 27th, Mon by 5pm) is available. You may need the following Matlab routines for this homework. forwardsubstitute.m backsubstitute.m

 

Textbooks:
Both of the textbooks will be available at the reserve desk in the library.

• Numerical Linear Algebra, Lloyd N. Trefethen and David Bau
• Fundamentals of Matrix Computations (2nd Edition), David S. Watkins

Supplementary Books:

• Numerical Computing with Matlab, Cleve Moler (Available at http://www.mathworks.com/moler/index_ncm.html)
• Numerical Computing with IEEE floating point arithmetic, Michael L. Overton (see the brief notes below under the resources extracted from this book. If you think you will be frequently involved in IEEE arithmetic, this book is relatively cheap when bought from the SIAM website.)
• Matrix Computations 3rd Edition, Gene H. Golub and Charles F. Van Loan (available at the reserve desk in the library)

Resources:

• Slides and lecture notes
  • Lecture 1 – IEEE Double Precision Arithmetic and Operation Count
  • Lecture 2 – Orthogonality and Norms
  • Lectures 3-4 – Singular Value Decomposition
  • Lectures 5-6 – Applications of Singular Value Decomposition
  • Lectures 7-8 – Projectors
  • Lecture 9 – QR Factorization and Classical Gram-Schmidt
  • Lectures 10-11 – Modified Gram-Schmidt and Householder Reflectors
  • Lectures 11 – QR Factorization by Householder Reflectors
  • Lecture 12 (part I) – Householder Reflectors and Least Squares Problem
  • Lecture 12 (part II) – Numerical Solution of the Least Squares Problem
  • Lecture 13 – Condition Number
  • Lecture 14 – Conditioning of the Least Squares Problem
  • Lecture 15 – Backward Error Analysis, Part I
  • Lecture 16 – Backward Error Analysis, Part II
  • Lecture 17 – Linear Systems, Forward and Back Substitutions
  • Lecture 18 – LU Factorization without Pivoting
  • Lecture 19 – LU Factorization with Partial Pivoting
  • Lecture 20 – Backward Error Analysis of LU Factorization with Partial Pivoting
  • Lecture 21 – Eigenvalues, Basic Definitions and Motivation
  • Lecture 22 – Similarity Transformations
  • Lecture 23 – Reduction into Hessenberg Form and Power Iteration
  • Lecture 24 – Inverse, Rayleigh Iterations and the QR Algorithm
  • Lecture 25 – QR Algorithm with Shifts, Simultaneous and Subspace Iterations
  • Lecture 26 – Derivation of the QR Algorithm and the Implicit QR Algorithm
• A brief note on backward error analysis
• An introductory Matlab manual
• Brief notes on IEEE floating-point arithmetic by Michael L. Overton (Ignore the title IEEE floating point numbers “in Java”. Everything here, except the last two subsections on page 11, applies to Matlab.)
• Matlab Clones (These are free softwares -almost- compatible with Matlab. If you have a personal computer, you can install one of these and do the computational hws in these platforms instead of Matlab.)

Homeworks:
All hws are due by 4pm on the indicated dates below unless otherwise indicated.

• Homework 1 (due on October 22nd, Friday) – Solutions
  • Additional files for hw1: harvest_gray.jpg, accuracy.m, accuracy2.m, accuracy3.m
• Homework 2  (due on November 24th) – Solutions
  • Additional files for hw2: constructq.m, backsubstitute.m, modifiedGS.m
• Homework 3 (due on December 8th, Wednesday by 5pm) – Solutions
• Homework 4 (due on December 27th, Monday by 5pm) – Solutions
  • Additional files: forwardsubstitute.m, backsubstitute.m
• Homework 5 (due on January 25th, Tuesday by 5pm; the deadline is tight)
  • Additional files:random_growth_factor.m, plot_growth_factor.m, plot_condition_number.m, growth_factor.m

Midterm:
Midterm was held on December 1st.
Midterm – Solutions

Final:
Final will be held on January 19th, Wednesday between 12:00-15:00 at ENG Z15.

Exams and Solutions:

• Midterm 1
• Final

Important Enrollment Dates and Holidays:
(Holidays are underlined.)

• September 27th, First day of classes
• September 29th-October 1st, Add-drops
• October 28th-29th, Foundation of Republic of Turkey
• November 15th-19th, Kurban Bayramı
• January 7th, Last day of classes
• January 10th-23rd, Finals