Matrix computations &
Numerical linear algebra

David Gleich

Purdue University

Fall 2012

Course number CS-51500

Tuesday and Thursday, 10:30-11:45am

Location Lawson 1106

Homework 6

$\newcommand{\mat}[1]{\boldsymbol{#1}} \renewcommand{\vec}[1]{\boldsymbol{\mathrm{#1}}} \newcommand{\vecalt}[1]{\boldsymbol{#1}} \newcommand{\conj}[1]{\overline{#1}} \newcommand{\normof}[1]{\|#1\|} \newcommand{\onormof}[2]{\|#1\|_{#2}} \newcommand{\itr}[2]{#1^{(#2)}} \newcommand{\itn}[1]{^{(#1)}} \newcommand{\eps}{\varepsilon} \newcommand{\kron}{\otimes} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\trace}{trace} \DeclareMathOperator{\tvec}{vec} \newcommand{\prob}{\mathbb{P}} \newcommand{\probof}[1]{\prob\left\{ #1 \right\}} \newcommand{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand{\bmat}[1]{\begin{bmatrix} #1 \end{bmatrix}} \newcommand{\spmat}[1]{\left(\begin{smallmatrix} #1 \end{smallmatrix}\right)} \newcommand{\sbmat}[1]{\left[\begin{smallmatrix} #1 \end{smallmatrix}\right]} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\eye}{\mat{I}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mF}{\mat{F}} \newcommand{\mG}{\mat{G}} \newcommand{\mH}{\mat{H}} \newcommand{\mI}{\mat{I}} \newcommand{\mJ}{\mat{J}} \newcommand{\mK}{\mat{K}} \newcommand{\mL}{\mat{L}} \newcommand{\mM}{\mat{M}} \newcommand{\mN}{\mat{N}} \newcommand{\mO}{\mat{O}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mT}{\mat{T}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mPbar}{\bar{\mP}} \newcommand{\ones}{\vec{e}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vf}{\vec{f}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vj}{\vec{j}} \newcommand{\vk}{\vec{k}} \newcommand{\vl}{\vec{l}} \newcommand{\vm}{\vec{l}} \newcommand{\vn}{\vec{n}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\vpi}{\vecalt{\pi}}$

Homework 6

Please answer the following questions in complete sentences in a clearly prepared manuscript and submit the solution by 5pm on Tuesday, November 20th, 2012. You should submit your PDF file to Blackboard http://mycourses.purdue.edu as well as your Matlab files.

Problem 0: List your collaborators.

Please identify anyone, whether or not they are in the class, with whom you discussed your homework. This problem is worth 1 point, but on a multiplicative scale.

Problem 1: Prove or disprove, the CG edition

These are slightly longer questions.

1. CG will converge for a symmetric, negative definite matrix.

2. You can use CG to solve $\mA \vx = \vb$ when $\mA$ is full-rank, non-symmetric given a function to compute $\mA \vy$ and $\mA^T \vy$.

3. Let $\mA$ be the matrix $\mI + \ve_1 \ve_1^T$. Then CG will converge in two steps.

4. CG will always converge in at most $n$ steps in exact arithmetic.

5. You can use CG with the symmetric matrix $\bmat{0 & \mA \\ \mA^T & 0}$.

6. Let $\mA$ be singular, with all other eigenvalues positive. Consider $\mA \vx = \vb$ where $\vb$ is in the range of $\mA$. Then CG (in exact arithmetic) will converge to the solution of $\mA \vx = \vb$.

Problem 2: Orthogonality of Lanczos

Let $\lambda_1 = 0.1$ and $\lambda_n = 100$, $\rho = 0.9$, $n=30$.
Consider the $n$-by-$n$ matrix with diagonal elements

$$\lambda_i = \lambda_1 + (i-1)/(n-1) (\lambda_n - \lambda_1)\rho^{n-i}.$$

(This is called the Strako\v{s} matrix.)

1. Implement the Lanczos method starting from a a random vector $\vv_1$ and the vector $\vv_1 = \ve/\sqrt{n}$ and then plot the quantity $\log(\normof{\mV_k^T \mV_k - \mI}+10^{-20})$ for $k=1$ to $30$. Describe what you SHOULD find and what you actually find. Do your results depend on the starting vector?

2. Plot $\log(|\vv_1^T \vv_k| + 10^{-20})$ for the $k=1$ to $30$. Also plot $\log(|\vv_{k-2}^T \vv_k| + 10^{-20})$ for $k=3$ to $30$.

3. What is $\beta_{31}?$ What should it be?

4. Plot $\log(\normof{\mA \mV_k - \mV_{k+1} \mT_{k+1}} + 10^{-20})$ for $k=1$ to $60$.

Problem 3: Finding the residual

In the Lanczos derivation of CG, we showed how to efficiently compute the approximate solution $\vx_k$ by determining a recurrent for $\vx_k = \mV_k \vy_k$ where $\bar{\mT}_k \vy_k = \normof{\vb} \ve_1$. However, we did not determine how to update the residual. Determine how to adjust the Lanczos CG algorithm from the notes to compute the residual, or the norm of the residual, at each iteration with only a linear amount of extra work (that is, you CANNOT do another matrix-vector product).

Problem 4: Extra credit

Coloring with CG!