Jay Pantone

MSCS 6040

Spring 2019, Marquette University

The main theme of this course is foundational linear algebra considered from a numerical viewpoint. We focus on solutions of linear systems of equations, eigenvalues and eigenvectors, and transformations. The course emphasizes and illustrates proof and numerical implementation using problems arising in applications. Multivariable calculus and linear algebra are prerequisites.

•  Lectures: M, W 3:30pm - 4:45pm Cudahy 131
•  Office Hours: Monday, 9:00am - 10:00am Cudahy 307 Tuesday, 3:00pm - 4:30pm Friday, 2:30pm - 4:00pm and by appointment

Course Information

The official syllabus is here.

Announcements
• Jan 9: There will be no office hours on Tuesday, Jan 15 or Friday, Jan 18. Office hours will resume the following week.

Textbook
• Primary: Numerical Linear Algebra, by Lloyd N. Trefethen and David Bau, III
• Secondary: Applied Numerical Linear Algebra, by James W. Demmel

LaTeX Resources

I recommend using Overleaf (free) to write your assignments in LaTeX. You can use this document as a basic template by cloning it to your own account.

Tutorials

I'm happy to help troubleshoot your LaTeX in office hours!

Important Dates
 Jan 14 Classes begin Jan 21 Martin Luther King, Jr. Day, no classes Jan 22 Last day to add/drop classes or request CR/NC option March 4-8 Midterm exams March 10-17 Spring break, no classes April 12 Last day to withdraw from classes April 18-22 Easter break, no classes May 4 Last day of classes TBD Math 6040 final exam

Daily Calendar
• Topics for future dates are tentative and subject to change.
# Date Topics Homework
& Announcements
1 Mon, Jan 14 Syllabus
Start Lecture 1 (Linear Algebra Review)
There will be no office hours on Tuesday, Jan 15 or Friday, Jan 18. Office hours will resume the following week.
2 Wed, Jan 16 Continue Lecture 1 (Linear Algebra Review)
Mon, Jan 21 Martin Luther King, Jr. Day — no class
3 Wed, Jan 23 Finish Lecture 1 (Linear Algebra Review) Due Monday, January 28, by 11:59pm
Must be submitted electronically on D2L
• T-B: 1.3
• Demmel: 1.2
• Read the appendix "The Definition of Numerical Analysis" in T-B, pages 321-327
Suggested Extra Problems (not collected):
• T-B: 1.1, 1.2ab, 1.4
• Demmel: 1.4
4 Mon, Jan 28 Lecture 2 (Orthogonal Vectors and Matrices) Due Friday, February 1, by 11:59pm
Must be submitted electronically on D2L
• T-B: 2.3
Suggested Extra Problems (not collected):
• T-B: 2.1, 2.2, 2.4, 2.6
5 Wed, Jan 30 Finish Lecture 2
6 Mon, Feb 4 Lecture 3 (Norms) Due Monday, February 11, by 3:30pm
Must be submitted electronically on D2L
• T-B: 3.2, 3.5
Suggested Extra Problems (not collected):
• T-B: 3.1, 3.3
7 Wed, Feb 6 Lecture 4 (SVD, part 1)
Matlab Matrix Tutorial
Plotting Demo (created by Sarah Hamilton)
Due Wednesday, February 13, by 3:30pm
Must be submitted electronically on D2L
• T-B: 4.1, 4.3
Note: For 4.1, do not use a computer / calculator, and do not try to perform the calculations from the proof of Theorem 4.1. Instead, just think about the idea that the matrix $$A$$ turns circles into ellipses, and that when we write $$A = U \Sigma V^*$$, that means the circle -> ellipse transformation involves first a rotation/reflection ($$V^*$$), then a stretching along the axes ($$\Sigma$$), and finally a rotation/reflection back into place ($$U$$).

For 4.3, refer to the posted Matlab tutorials, and feel free to search online for other tutorials about how to plot points, lines, and vectors. You should use the "svd" function in Matlab to compute the SVD. You will submit your code to me (either a .m file or a .mlx file) on D2L and a pdf of its output.
Suggested Extra Problems (not collected):
• practice more Matlab!
8 Mon, Feb 11 Lecture 5 (SVD, part 2) Due Monday, February 18, by 3:30pm
Must be submitted electronically on D2L
• T-B: 5.3(a)-(d)
• Use this Matlab code to apply the SVD to some images to compress them. Play around with using different ranges of singular values.
• Find a photograph (an actual photograph, not a computer generated image) online that you think the SVD will compress particularly well. Find one you think it will compress particularly poorly. Explain your reasoning, then test your hypotheses and send me the results. Look at the singular values for your images and say whether you think they back up your conclusions. You can submit a pdf with your results, or a Matlab Live (.mlx) file which lets you link your code and output together in one file.
Suggested Extra Problems (not collected):
• practice more Matlab!
9 Wed, Feb 13 Lecture 6 (Projectors) No homework today! Spend a few minutes playing around in Matlab.
10 Mon, Feb 18 Finish Lecture 6 (Projectors)
Lecture 7 (QR Decomposition)
Due Monday, February 25, by 3:30pm
Must be submitted electronically on D2L
• T-B: 6.4
After doing the short(!) computation, try to put your answer in a complete sentence—something like "$$P =$$ ... is the ... that ...".
• Prove the following fact from lecture: Let $$w$$ be any vector, not necessarily with unit length. Then, $$P = \displaystyle\frac{ww^*}{w^*w}$$ is an orthogonal projector onto $$\operatorname{span}\{w\}$$.
Suggested Extra Problems (not collected):
• T-B: 6.1, 6.2, 6.3
11 Wed, Feb 20 Finish Lecture 7 (QR Decomposition)
Lecture 8 (Gram-Schmidt Orthogonalization)
Due Wednesday, February 27, by 3:30pm
Must be submitted electronically on D2L
• T-B: 7.1(a), 7.5(b)
Suggested Extra Problems (not collected):
• T-B: 7.1(b), 7.5(a)
12 Mon, Feb 25 Finish Lecture 8 (Gram-Schmidt Orthogonalization) Due Monday, March 4, by 3:30pm
Must be submitted electronically on D2L
• T-B: 8.2. Use your algorithm to compute the reduced QR decomposition of the two matrices from Exercise 6.4, and submit the code and results. (I recommend trying out a .mlx file.)
• Read Lecture 9 (in T-B) about Matlab, and try Experiments 1 and 3 on your computer. This section will help you understand how to manipulate vectors and matrices and will give you an introduction to some of the numerical stability concepts we will encounter soon. You don't have to turn in anything for this question.
Suggested Extra Problems (not collected):
• Demmel: 3.1
13 Wed, Feb 27 Lecture 11 (Least Squares Problems) Due Wednesday, March 6, by 3:30pm
Must be submitted electronically on D2L
• T-B: 11.3 (skip (c)). Note that "\" in Matlab solves systems of the form $$Ax=b$$. Use it for Steps 3 and 4 in Algorithm 11.1. You may also use the function "chol" to compute the Cholesky factorization.
Suggested Extra Problems (not collected):
• Demmel: 3.11
14 Mon, Mar 4 Lecture 12 (Conditioning and Condition Numbers) No assignment.
15 Wed, Mar 6 In-class Midterm Exam
Take-home Exam Assigned
Covers up to and including Lecture 11.
Mon, Mar 11 Spring Break — no class
Wed, Mar 13 Spring Break — no class
16 Mon, Mar 18 Finish Lecture 12
Lecture 13 (Floating Point Arithmetic)
No assignment.
17 Wed, Mar 20 Take-home Exam Due
Lecture 14 (Stability)
Lecture 15 (More on Stability)
No assignment.
18 Mon, Mar 25 Finish Lecture 15
Lecture 17 (Stability of Back Substitution)
Due Monday, April 1, by 3:30pm
Must be submitted electronically on D2L
• T-B: 15.1abcd, 15.2 (just explain the ideas, not looking for a full proof).
Suggested Extra Problems (not collected):
• Demmel: 1.12
19 Wed, Mar 27 Finish Lecture 17
Lecture 18 (Conditioning of Least Squares Problems)
No assignment.
20 Mon, Apr 1 Finish Lecture 18
Lecture 19 (Stability of Least Squares Problems)
Due Monday, April 8, by 3:30pm
Must be submitted electronically on D2L
• Use the ideas of Lecture 19 to explain why on #2 of the take-home midterm, the three least squares solutions were all so similar.
21 Wed, Apr 3 Lecture 24 (Eigenvalue Problems) Due Wednesday, April 10, by 3:30pm
Must be submitted electronically on D2L
• Prove that the geometric multiplicity of the eigenvalue $$\lambda = 2$$ is $$1$$ for the matrix $$B$$ in Example 24.1.
22 Mon, Apr 8 Finish Lecture 24
Lecture 25 (Overview of Eigenvalue Algorithms)
Due Monday, April 15, by 3:30pm
Must be submitted electronically on D2L
• T-B: 24.1
23 Wed, Apr 10 Lecture 26 (Reduction to Hessenberg or Tridiagonal Form) Due Wednesday, April 17, by 3:30pm
Must be submitted electronically on D2L
• Implement Algorithm 26.1 and have it output $$H$$, the $$Q_i$$, and the reflection vectors $$v_k$$. Apply it to the matrix
$$\displaystyle\left[\begin{array}{lllll}1&2&3&4&5\\6&7&8&9&10\\11&12&13&14&15\\16&17&18&19&20\\21&22&23&24&25\end{array}\right]$$.
Matlab notation: [1 2 3 4 5; 6 7 8 9 10; 11 12 13 14 15; 16 17 18 19 20; 21 22 23 24 25]
24 Mon, Apr 15 Lecture 27 (Rayleigh Quotient, Inverse Iteration) No assignment.
25 Wed, Apr 17 Lecture 28 (QR Algorithm without Shifts) No assignment.
Mon, Apr 22 Easter Break — no class
26 Wed, Apr 24 Finish Lecture 28
Lecture 32 (Overview of Iterative Methods)
No assignment.
27 Mon, Apr 29 Lecture 33 (The Arnoldi Iteration) No assignment.
28 Wed, May 1 Lecture 34 (How Arnoldi Locates Eigenvalues) No assignment.