ALAFF Answers and Solutions to Homeworks

Processing math: 100%

Skip to main content

$\usepackage{array} \setlength{\oddsidemargin}{-0.0in} \setlength{\evensidemargin}{-0.0in} \setlength{\textheight}{8.75in} \setlength{\textwidth}{6.5in} \setlength{\topmargin}{-0.25in} \newcommand{\R}{\mathbb R} \newcommand{\Rm}{\mathbb R^m} \newcommand{\Rn}{\mathbb R^n} \newcommand{\Rnxn}{\mathbb R^{n \times n}} \newcommand{\Rmxn}{\mathbb R^{m \times n}} \newcommand{\Rmxm}{\mathbb R^{m \times m}} \newcommand{\Rmxk}{\mathbb R^{m \times k}} \newcommand{\Rkxn}{\mathbb R^{k \times n}} \newcommand{\C}{\mathbb C} \newcommand{\Cm}{\mathbb C^m} \newcommand{\Cmxm}{\mathbb C^{m \times m}} \newcommand{\Cnxn}{\mathbb C^{n \times n}} \newcommand{\Cmxn}{\mathbb C^{m \times n}} \newcommand{\Ckxk}{\mathbb C^{k \times k}} \newcommand{\Cn}{\mathbb C^n} \newcommand{\Ck}{\mathbb C^k} \newcommand{\Null}{{\cal N}} \newcommand{\Col}{{\cal C}} \newcommand{\Rowspace}{{\cal R}} \newcommand{\Span}{{\rm {Span}}} \newcommand{\rank}{{\rm rank}} \newcommand{\triu}{{\rm triu}} \newcommand{\tril}{{\rm tril}} \newcommand{\sign}{{\rm sign}} \newcommand{\FlaTwoByTwo}[4]{ \left( \begin{array}{c | c} #1 \amp #2 \\ \hline #3 \amp #4 \end{array} \right) } \newcommand{\FlaTwoByTwoSingleLine}[4]{ \left( \begin{array}{c c} #1 \amp #2 \\ #3 \amp #4 \end{array} \right) } \newcommand{\FlaTwoByTwoSingleLineNoPar}[4]{ \begin{array}{c c} #1 \amp #2 \\ #3 \amp #4 \end{array} } \newcommand{\FlaOneByTwo}[2]{ \left( \begin{array}{c | c} #1 \amp #2 \end{array} \right) } \newcommand{\FlaOneByTwoSingleLine}[2]{ \left( \begin{array}{c c} #1 \amp #2 \end{array} \right) } \newcommand{\FlaTwoByOne}[2]{ \left( \begin{array}{c} #1 \\ \hline #2 \end{array} \right) } \newcommand{\FlaTwoByOneSingleLine}[2]{ \left( \begin{array}{c} #1 \\ #2 \end{array} \right) } \newcommand{\FlaThreeByOneB}[3]{ \left( \begin{array}{c} #1 \\ \hline #2 \\ #3 \end{array} \right) } \newcommand{\FlaThreeByOneT}[3]{ \left( \begin{array}{c} #1 \\ #2 \\ \hline #3 \end{array} \right) } \newcommand{\FlaOneByThreeR}[3]{ \left( \begin{array}{c | c c} #1 \amp #2 \amp #3 \end{array} \right) } \newcommand{\FlaOneByThreeL}[3]{ \left( \begin{array}{c c | c} #1 \amp #2 \amp #3 \end{array} \right) } \newcommand{\FlaThreeByThreeBR}[9]{ \left( \begin{array}{c | c c} #1 \amp #2 \amp #3 \\ \hline #4 \amp #5 \amp #6 \\ #7 \amp #8 \amp #9 \end{array} \right) } \newcommand{\FlaThreeByThreeTL}[9]{ \left( \begin{array}{c c | c} #1 \amp #2 \amp #3 \\ #4 \amp #5 \amp #6 \\ \hline #7 \amp #8 \amp #9 \end{array} \right) } \newcommand{\diag}[1]{{\rm diag}( #1 )} \newcommand{\URt}{{\sc HQR}} \newcommand{\FlaAlgorithm}{ \begin{array}{|l|} \hline \routinename \\ \hline \partitionings \\ ~~~ \begin{array}{l} \partitionsizes \end{array} \\ {\bf \color{blue} {while}~} \guard \\ ~~~ \begin{array}{l} \repartitionings \end{array} \\ ~~~ \color{red} { \begin{array}{l} \hline \color{black} {\update} \\ \hline \end{array}} \\ ~~~ \begin{array}{l} \moveboundaries \end{array} \\ {\bf \color{blue} {endwhile}} \\ \hline \end{array} } \newcommand{\FlaAlgorithmWithInit}{ \begin{array}{|l|} \hline \routinename \\ \hline \initialize \\ \partitionings \\ ~~~ \begin{array}{l} \partitionsizes \end{array} \\ {\bf \color{blue} {while}~} \guard \\ ~~~ \begin{array}{l} \repartitionings \end{array} \\ ~~~ \color{red} { \begin{array}{l} \hline \color{black} {\update} \\ \hline \end{array}} \\ ~~~ \begin{array}{l} \moveboundaries \end{array} \\ {\bf \color{blue} {endwhile}} \\ \hline \end{array} } \newcommand{\FlaBlkAlgorithm}{ \begin{array}{|l|} \hline \routinename \\ \hline \partitionings \\ ~~~ \begin{array}{l} \partitionsizes \end{array} \\ {\bf \color{blue} {while}~} \guard \\ ~~~ {\bf choose~block~size~} \blocksize \\ ~~~ \begin{array}{l} \repartitionings \end{array} \\ ~~~ ~~~ \repartitionsizes \\ ~~~ \color{red} { \begin{array}{l} \hline \color{black} {\update} \\ \hline \end{array}} \\ ~~~ \begin{array}{l} \moveboundaries \end{array} \\ {\bf \color{blue} {endwhile}} \\ \hline \end{array} } \newcommand{\complexone}{ \begin{array}{|c|}\hline \!\pm\! \\ \hline \end{array}~ } \newcommand{\HQR}{{\rm HQR}} \newcommand{\QR}{{\rm QR}} \newcommand{\st}{{\rm \ s.t. }} \newcommand{\QRQ}{{\rm {\normalsize \bf Q}{\rm \tiny R}}} \newcommand{\QRR}{{\rm {\rm \tiny Q}{\bf \normalsize R}}} \newcommand{\deltaalpha}{\delta\!\alpha} \newcommand{\deltax}{\delta\!x} \newcommand{\deltay}{\delta\!y} \newcommand{\deltaz}{\delta\!z} \newcommand{\deltaw}{\delta\!w} \newcommand{\DeltaA}{\delta\!\!A} \newcommand{\meps}{\epsilon_{\rm mach}} \newcommand{\fl}[1]{{\rm fl( #1 )}} \newcommand{\becomes}{:=} \newcommand{\defrowvector}[2]{ \left(#1_0, #1_1, \ldots, #1_{#2-1}\right) } \newcommand{\tr}[1]{{#1}^T} \newcommand{\LUpiv}[1]{{\rm LU}(#1)} \newcommand{\maxi}{{\rm maxi}} \newcommand{\Chol}[1]{{\rm Chol}( #1 )} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

Solutions E Answers and Solutions to Homeworks

Part I Orthogonality

Week 1 Norms

Section 1.1 Opening Remarks

Subsection 1.1.1 Why norms?

Homework 1.1.1.1.

Homework 1.1.1.2.

Homework 1.1.1.3.

Homework 1.1.1.4.

Homework 1.1.1.5.

Section 1.2 Vector Norms

Subsection 1.2.1 Absolute value

Homework 1.2.1.1.

Homework 1.2.1.2.

Hint Answer Solution

Homework 1.2.1.3.

Hint Answer Solution 1 Solution 2 Solution 3

Homework 1.2.1.4.

Answer Solution

Homework 1.2.1.5.

Homework 1.2.1.6.

Answer Solution

Subsection 1.2.2 What is a vector norm?

Homework 1.2.2.1.

Hint Answer Solution

Subsection 1.2.3 The vector 2-norm (Euclidean length)

Homework 1.2.3.2.

Homework 1.2.3.3.

Answer Solution

Subsection 1.2.4 The vector $p$ -norms

Homework 1.2.4.1.

Homework 1.2.4.2.

Subsection 1.2.5 Unit ball

Homework 1.2.5.1.

Subsection 1.2.6 Equivalence of vector norms

Homework 1.2.6.1.

Homework 1.2.6.2.

Homework 1.2.6.3.

Hint Solution 1

$\| x \|_1 \leq C_{1,2} \| x \|_2$ Solution 2

$\| x \|_1 \leq C_{1,\infty} \| x \|_\infty$ Solution 3

$\| x \|_2 \leq C_{2,1} \| x \|_1 \text{:}$ Solution 4

$\| x \|_2 \leq C_{2,\infty} \| x \|_\infty$ Solution 5

$\| x \|_\infty \leq C_{\infty,1} \| x \|_1 \text{:}$ Solution 6

$\| x \|_\infty \leq C_{\infty,2} \| x \|_2$ Solution 7 Table of constants

Section 1.3 Matrix Norms

Subsection 1.3.2 What is a matrix norm?

Homework 1.3.2.1.

Hint Answer Solution

Subsection 1.3.3 The Frobenius norm

Homework 1.3.3.1.

Homework 1.3.3.2.

Homework 1.3.3.3.

Homework 1.3.3.4.

Homework 1.3.3.5.

Answer Solution

Subsection 1.3.4 Induced matrix norms

Homework 1.3.4.1.

Answer Solution

Subsection 1.3.5 The matrix 2-norm

Homework 1.3.5.1.

Homework 1.3.5.2.

Hint Answer Solution

Homework 1.3.5.3.

Hint Answer Solution

Homework 1.3.5.4.

Homework 1.3.5.5.

Subsection 1.3.6 Computing the matrix 1-norm and $\infty$ -norm

Homework 1.3.6.1.

Hint Answer Solution

Homework 1.3.6.2.

Hint Answer Solution

Subsection 1.3.7 Equivalence of matrix norms

Homework 1.3.7.1.

Homework 1.3.7.2.

Homework 1.3.7.3.

Subsection 1.3.8 Submultiplicative norms

Homework 1.3.8.1.

Answer Solution

Homework 1.3.8.2.

Homework 1.3.8.3.

Homework 1.3.8.4.

Homework 1.3.8.5.

Answer Solution

Homework 1.3.8.6.

Answer Solution

Section 1.4 Condition Number of a Matrix

Subsection 1.4.1 Conditioning of a linear system

Homework 1.4.1.1.

Answer Solution

Homework 1.4.1.2.

Answer Solution

Subsection 1.4.2 Loss of digits of accuracy

Homework 1.4.2.1.

Section 1.6 Wrap Up

Subsection 1.6.1 Additional homework

Homework 1.6.1.8.

Week 2 The Singular Value Decomposition

Section 2.1 Opening Remarks

Subsection 2.1.1 Low rank approximation

Homework 2.1.1.1.

Homework 2.1.1.2.

Section 2.2 Orthogonal Vectors and Matrices

Subsection 2.2.1 Orthogonal vectors

Homework 2.2.1.1.

Answer Solution

Homework 2.2.1.2.

Answer Solution

Subsection 2.2.2 Component in the direction of a vector

Homework 2.2.2.1.

Answer Solution

Homework 2.2.2.2.

Answer Solution

Homework 2.2.2.3.

Answer Solution

Subsection 2.2.3 Orthonormal vectors and matrices

Homework 2.2.3.1.

Answer Solution

Homework 2.2.3.2.

Answer Solution

Homework 2.2.3.3.

Answer Solution

Subsection 2.2.4 Unitary matrices

Homework 2.2.4.1.

Answer Solution

Homework 2.2.4.2.

Answer Solution

Homework 2.2.4.3.

Answer Solution

Homework 2.2.4.4.

Answer Solution

Homework 2.2.4.5.

Answer Solution

Homework 2.2.4.6.

Homework 2.2.4.7.

Homework 2.2.4.8.

Homework 2.2.4.9.

Homework 2.2.4.10.

Subsection 2.2.5 Examples of unitary matrices

Subsubsection 2.2.5.1 Rotations

Homework 2.2.5.1.

Homework 2.2.5.2.

Subsubsection 2.2.5.2 Reflections

Homework 2.2.5.3.

Homework 2.2.5.4.

Homework 2.2.5.5.

Homework 2.2.5.6.

Subsection 2.2.6 Change of orthonormal basis

Homework 2.2.6.1.

Subsection 2.2.7 Why we love unitary matrices

Homework 2.2.7.1.

Section 2.3 The Singular Value Decomposition

Subsection 2.3.1 The Singular Value Decomposition Theorem

Homework 2.3.1.1.

Homework 2.3.1.2.

Answer Solution

Homework 2.3.1.3.

Homework 2.3.1.4.

Answer Solution

Homework 2.3.1.5.

Subsection 2.3.4 The Reduced Singular Value Decomposition

Homework 2.3.4.1.

Subsection 2.3.5 SVD of nonsingular matrices

Homework 2.3.5.1.

Answer Solution

Homework 2.3.5.2.

Answer Solution

Homework 2.3.5.3.

Answer Solution

Homework 2.3.5.4.

Answer Solution

Homework 2.3.5.5.

Answer Solution

Subsection 2.3.6 Best rank-k approximation

Homework 2.3.6.1.

Homework 2.3.6.2.

Section 2.5 Wrap Up

Subsection 2.5.1 Additional homework

Homework 2.5.1.1.

Homework 2.5.1.2.

Homework 2.5.1.3.

Homework 2.5.1.4.

Week 3 The QR Decomposition

Section 3.1 Opening Remarks

Subsection 3.1.1 Choosing the right basis

Homework 3.1.1.1.

Homework 3.1.1.2.

Section 3.2 Gram-Schmidt Orthogonalization

Subsection 3.2.2 Gram-Schmidt and the QR factorization

Ponder This 3.2.2.1.

Subsection 3.2.3 Classical Gram-Schmidt algorithm

Homework 3.2.3.1.

Subsection 3.2.4 Modified Gram-Schmidt (MGS)

Homework 3.2.4.1.

Ponder This 3.2.4.2.

Homework 3.2.4.3.

Subsection 3.2.5 In practice, MGS is more accurate

Homework 3.2.5.1.

Subsection 3.2.6 Cost of Gram-Schmidt algorithms

Homework 3.2.6.1.

Homework 3.2.6.2.

Homework 3.2.6.3.

Section 3.3 Householder QR Factorization

Subsection 3.3.1 Using unitary matrices

Homework 3.3.1.1.

Subsection 3.3.2 Householder transformation

Homework 3.3.2.1.

Subsection 3.3.3 Practical computation of the Householder vector

Subsubsection 3.3.3.3 A routine for computing the Householder vector

Homework 3.3.3.1.

Subsection 3.3.4 Householder QR factorization algorithm

Homework 3.3.4.1.

Homework 3.3.4.2.

Homework 3.3.4.3.

Subsection 3.3.5 Forming $Q$

Homework 3.3.5.1.

Answer Solution

Homework 3.3.5.2.

Homework 3.3.5.3.

Subsection 3.3.6 Applying $Q^H$

Homework 3.3.6.1.

Subsection 3.3.7 Orthogonality of resulting $Q$

Homework 3.3.7.1.

Section 3.5 Wrap Up

Subsection 3.5.1 Additional homework

Homework 3.5.1.1.

Week 4 Linear Least Squares

Section 4.2 Solution via the Method of Normal Equations

Subsection 4.2.1 The four fundamental spaces of a matrix

Homework 4.2.1.1.

Homework 4.2.1.2.

Homework 4.2.1.3.

Homework 4.2.1.4.

Hint Answer Solution

Subsection 4.2.2 The Method of Normal Equations

Homework 4.2.2.1.

Homework 4.2.2.2.

Hint Answer Solution

Subsection 4.2.4 Conditioning of the linear least squares problem

Homework 4.2.4.1.

Subsection 4.2.5 Why using the Method of Normal Equations could be bad

Homework 4.2.5.1.

Section 4.3 Solution via the SVD

Subsection 4.3.1 The SVD and the four fundamental spaces

Homework 4.3.1.1.

Homework 4.3.1.3.

Answer Solution

Homework 4.3.1.4.

Answer Solution

Subsection 4.3.3 Case 2: General case

Homework 4.3.3.1.

Section 4.4 Solution via the QR factorization

Subsection 4.4.1 $A$ has linearly independent columns

Homework 4.4.1.1.

Part II Solving Linear Systems

Week 5 The LU and Cholesky Factorizations

Section 5.1 Opening Remarks

Subsection 5.1.1 Of Gaussian elimination and LU factorization

Homework 5.1.1.1.

Homework 5.1.1.2.

Section 5.2 From Gaussian elimination to LU factorization

Subsection 5.2.1 Gaussian elimination

Homework 5.2.1.1.

Answer Solution

Homework 5.2.1.2.

Answer Solution

Homework 5.2.1.3.

Answer Solution

Subsection 5.2.2 LU factorization: The right-looking algorithm

Homework 5.2.2.1.

Answer Solution

Homework 5.2.2.2.

Answer Solution

Homework 5.2.2.3.

Subsection 5.2.3 Existence of the LU factorization

Homework 5.2.3.1.

Homework 5.2.3.2.

Homework 5.2.3.4.

Subsection 5.2.4 Gaussian elimination via Gauss transforms

Homework 5.2.4.1.

Homework 5.2.4.2.

Homework 5.2.4.3.

Ponder This 5.2.4.4.

Section 5.3 LU factorization with (row) pivoting

Subsection 5.3.1 Gaussian elimination with row exchanges

Homework 5.3.1.1.

Homework 5.3.1.2.

Subsection 5.3.2 Permutation matrices

Homework 5.3.2.1.

Homework 5.3.2.2.

Homework 5.3.2.3.

Homework 5.3.2.4.

Answer Solution

Subsection 5.3.3 LU factorization with partial pivoting

Homework 5.3.3.1.

Subsection 5.3.5 Solving with a triangular matrix

Subsubsection 5.3.5.1 Algorithmic Variant 1

Homework 5.3.5.1.

Subsubsection 5.3.5.2 Algorithmic Variant 2

Homework 5.3.5.2.

Homework 5.3.5.3.

Section 5.4 Cholesky factorization

Subsection 5.4.1 Hermitian Positive Definite matrices

Homework 5.4.1.1.

Answer Solution

Homework 5.4.1.2.

Hint Answer Solution

Homework 5.4.1.3.

Answer Solution

Subsection 5.4.3 Cholesky factorization algorithm (right-looking variant)

Homework 5.4.3.1.

Answer Solution

Homework 5.4.3.2.

Section 5.5 Enrichments

Subsection 5.5.1 Other LU factorization algorithms

Subsubsection 5.5.1.1 Variant 1: Bordered algorithm

Homework 5.5.1.1.

Subsubsection 5.5.1.2 Variant 2: Up-looking algorithm

Homework 5.5.1.2.

Subsubsection 5.5.1.3 Variant 3: Left-looking algorithm

Homework 5.5.1.3.

Subsubsection 5.5.1.4 Variant 4: Crout variant

Homework 5.5.1.4.

Subsubsection 5.5.1.5 Variant 5: Classical Gaussian elimination

Homework 5.5.1.5.

Week 6 Numerical Stability

Section 6.1 Opening Remarks

Subsection 6.1.1 Whose problem is it anyway?

Ponder This 6.1.1.1.

Homework 6.1.1.2.

Section 6.2 Floating Point Arithmetic

Subsection 6.2.2 Error in storing a real number as a floating point number

Homework 6.2.2.1.

Subsection 6.2.4 Stability of a numerical algorithm

Homework 6.2.4.1.

Answer Solution

Subsection 6.2.6 Absolute value of vectors and matrices

Homework 6.2.6.1.

Answer Solution

Homework 6.2.6.2.

Section 6.3 Error Analysis for Basic Linear Algebra Algorithms

Subsection 6.3.1 Initial insights

Homework 6.3.1.1.

Answer Solution

Subsection 6.3.2 Backward error analysis of dot product: general case

Homework 6.3.2.2.

Subsection 6.3.3 Dot product: error results

Homework 6.3.3.1.

Homework 6.3.3.2.

Subsection 6.3.4 Matrix-vector multiplication

Ponder This 6.3.4.1.

Subsection 6.3.5 Matrix-matrix multiplication

Homework 6.3.5.2.

Section 6.4 Error Analysis for Solving Linear Systems

Subsection 6.4.1 Numerical stability of triangular solve

Homework 6.4.1.1.

Homework 6.4.1.2.

Homework 6.4.1.3.

Homework 6.4.1.4.

Subsection 6.4.3 Numerical stability of linear solve via LU factorization

Homework 6.4.3.1.

Subsection 6.4.5 Is LU with Partial Pivoting Stable?

Homework 6.4.5.1.

Homework 6.4.5.2.

Week 7 Solving Sparse Linear Systems

Section 7.1 Opening Remarks

Subsection 7.1.1 Where do sparse linear systems come from?

Homework 7.1.1.1.

Section 7.2 Direct Solution

Subsection 7.2.1 Banded matrices

Homework 7.2.1.1.

Homework 7.2.1.2.

Homework 7.2.1.3.

Homework 7.2.1.4.

Homework 7.2.1.5.

Subsection 7.2.2 Nested dissection

Homework 7.2.2.1.

Section 7.3 Iterative Solution

Subsection 7.3.2 Gauss-Seidel iteration

Homework 7.3.2.1.

Homework 7.3.2.2.

Homework 7.3.2.3.

Homework 7.3.2.4.

Subsection 7.3.3 Convergence of splitting methods

Homework 7.3.3.1.

Homework 7.3.3.2.

Homework 7.3.3.5.

Week 8 Descent Methods

Section 8.2 Search directions

Subsection 8.2.1 Basics of descent methods

Homework 8.2.1.1.

Subsection 8.2.2 Toward practical descent methods

Homework 8.2.2.1.

Homework 8.2.2.2.

Subsection 8.2.3 Relation to Splitting Methods

Homework 8.2.3.1.

Subsection 8.2.5 Preconditioning

Homework 8.2.5.1.

Hint Solution 1 Solution 2 Constructive solution

Section 8.3 The Conjugate Gradient Method

Subsection 8.3.1 A-conjugate directions

Homework 8.3.1.1.

Homework 8.3.1.2.

Answer Solution

Homework 8.3.1.3.

Answer Solution

Subsection 8.3.5 Practical Conjugate Gradient Method algorithm

Homework 8.3.5.1.

Homework 8.3.5.2.

Subsection 8.3.6 Final touches for the Conjugate Gradient Method

Subsubsection 8.3.6.2 Preconditioning

Homework 8.3.6.1.

Part III The Algebraic Eigenvalue Problem

Week 9 Eigenvalues and Eigenvectors

Section 9.1 Opening Remarks

Subsection 9.1.1 Relating diagonalization to eigenvalues and eigenvectors

Homework 9.1.1.1.

Section 9.2 Basics

Subsection 9.2.1 Singular matrices and the eigenvalue problem

Homework 9.2.1.1.

Answer Solution

Homework 9.2.1.2.

Answer Solution

Homework 9.2.1.3.

Answer Solution

Homework 9.2.1.4.

Answer Solution

Homework 9.2.1.5.

Homework 9.2.1.6.

Homework 9.2.1.7.

Answer Solution

Subsection 9.2.2 The characteristic polynomial

Homework 9.2.2.1.

Subsection 9.2.3 More properties of eigenvalues and vectors

Homework 9.2.3.1.

Homework 9.2.3.2.

Homework 9.2.3.3.

Homework 9.2.3.4.

Subsection 9.2.4 The Schur and Spectral Decompositions

Homework 9.2.4.1.

Answer Solution

Homework 9.2.4.2.

Homework 9.2.4.3.

Homework 9.2.4.4.

Subsection 9.2.5 Diagonalizing a matrix

Homework 9.2.5.1.

Homework 9.2.5.2.

Answer Solution

Subsection 9.2.6 Jordan Canonical Form

Homework 9.2.6.1.

Homework 9.2.6.2.

Section 9.3 The Power Method and related approaches

Subsection 9.3.1 The Power Method

Subsubsection 9.3.1.4 The Rayleigh quotient

Homework 9.3.1.1.

Answer Solution

Subsection 9.3.2 The Power Method: Convergence

Homework 9.3.2.1.

Subsection 9.3.3 The Inverse Power Method

Homework 9.3.3.1.

Answer Solution

Subsection 9.3.4 The Rayleigh Quotient Iteration

Homework 9.3.4.1.

Answer Solution

Homework 9.3.4.2.

Week 10 Practical Solution of the Hermitian Eigenvalue Problem

Section 10.1 Opening Remarks

Subsection 10.1.1 Subspace iteration with a Hermitian matrix

Homework 10.1.1.1.

Homework 10.1.1.2.

Homework 10.1.1.3.

Homework 10.1.1.4.

Section 10.2 From Power Method to a simple QR algorithm

Subsection 10.2.1 A simple QR algorithm

Homework 10.2.1.1.

Homework 10.2.1.2.

Homework 10.2.1.3.

Homework 10.2.1.4.

Homework 10.2.1.5.

Subsection 10.2.2 A simple shifted QR algorithm

Homework 10.2.2.1.

Homework 10.2.2.2.

Homework 10.2.2.3.

Homework 10.2.2.4.

Subsection 10.2.3 Deflating the problem

Homework 10.2.3.1.

Homework 10.2.3.2.

Section 10.3 A Practical Hermitian QR Algorithm

Subsection 10.3.1 Reduction to tridiagonal form

Homework 10.3.1.1.

Homework 10.3.1.3.

Subsection 10.3.2 Givens' rotations

Homework 10.3.2.1.

Subsection 10.3.4 The implicit Q theorem

Homework 10.3.4.1.

Subsection 10.3.5 The Francis implicit QR Step

Homework 10.3.5.1.

Week 11 Computing the SVD

Section 11.1 Opening Remarks

Subsection 11.1.1 Linking the Singular Value Decomposition to the Spectral Decomposition

Homework 11.1.1.1.

Homework 11.1.1.2.

Section 11.2 Practical Computation of the Singular Value Decomposition

Subsection 11.2.1 Computing the SVD from the Spectral Decomposition

Homework 11.2.1.1.

Homework 11.2.1.2.

Homework 11.2.1.3.

Homework 11.2.1.4.

Subsection 11.2.2 A strategy for computing the SVD

Homework 11.2.2.1.

Subsection 11.2.3 Reduction to bidiagonal form

Homework 11.2.3.1.

Section 11.3 Jacobi's Method

Subsection 11.3.1 Jacobi rotation

Ponder This 11.3.1.1.

Homework 11.3.1.2.

Subsection 11.3.2 Jacobi's method for computing the Spectral Decomposition

Homework 11.3.2.1.

Homework 11.3.2.2.

Week 12 Attaining High Performance

Section 12.1 Opening Remarks

Subsection 12.1.1 Simple Implementation of matrix-matrix multiplication

Homework 12.1.1.2.

Answer Solution

Homework 12.1.1.3.

Homework 12.1.1.4.

Section 12.2 Linear Algebra Building Blocks

Subsection 12.2.2 Opportunities for optimization

Homework 12.2.2.1.

Homework 12.2.2.2.

Homework 12.2.2.3.

Homework 12.2.2.4.

Section 12.3 Casting Computation in Terms of Matrix-Matrix Multiplication

Subsection 12.3.2 Blocked LU factorization

Homework 12.3.2.1.

Homework 12.3.2.2.

Homework 12.3.2.3.