\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\else % if luatex or xelatex
\ifxetex
\usepackage{mathspec}
\makeatletter % undo the wrong changes made by mathspec
\let\RequirePackage\original@RequirePackage
\let\usepackage\RequirePackage
\makeatother
\else
\usepackage{fontspec}
\fi
\defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\usepackage{hyperref}
\hypersetup{unicode=true,
pdftitle={Homework 10},
pdfborder={0 0 0},
breaklinks=true}
\urlstyle{same} % don't use monospace font for urls
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi
\title{Homework 10}
\input{preamble.tex}
\title{Homework}
\begin{document}
\maketitle
\section{Homework 10}\label{homework-10}
Please answer the following questions in complete sentences in a clearly
prepared manuscript and submit the solution by the due date on
Blackboard (around Sunday, November 18th, 2018.)
Remember that this is a graduate class. There may be elements of the
problem statements that require you to fill in appropriate assumptions.
You are also responsible for determining what evidence to include. An
answer alone is rarely sufficient, but neither is an overly verbose
description required. Use your judgement to focus your discussion on the
most interesting pieces. The answer to ``should I include `something' in
my solution?'' will almost always be: Yes, if you think it helps support
your answer.
\subsection{Problem 0: Homework
checklist}\label{problem-0-homework-checklist}
\begin{itemize}
\item
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.
\item
Make sure you have included your source-code and prepared your
solution according to the most recent Piazza note on homework
submissions.
\end{itemize}
\begin{center}\rule{0.5\linewidth}{\linethickness}\end{center}
\subsection{Problem 1: Experimenting with Lanczos-based
methods.}\label{problem-1-experimenting-with-lanczos-based-methods.}
\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
Implement a Lanczos-based MINRES code that explictly builds
\(\mV_k, \mT_k\) and then finds the minimum residual vector within the
Krylov subspace.
\item
Compare the first 25 residuals from the Lanczos-based CG code we wrote
in class that explictly builds \(\mV_k, \mT_k\), with the a standard
implementation of CG from:
\url{http://www.cs.purdue.edu/homes/dgleich/cs515-2018/homeworks/cg.jl}
for the linear system
\begin{verbatim}
n = 100
on = ones(Int64,n)
A = spdiagm((-2*on[1:end-1],4*on,-2*on[1:end-1]),(-1,0,1))
b = ones(n)
\end{verbatim}
as well as the MINRES code you developed above.
\item
Using the \texttt{cg.jl} function, look at how many iterations are
required for CG to converge to a tolerance of \(10^{-8}\) for the
matrix in the last part. Determine how this scales with \(n\).
\end{enumerate}
\subsection{Problem 2: Orthogonality of
Lanczos}\label{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\\
\[ d_i = \lambda_1 + (i-1)/(n-1) (\lambda_n - \lambda_1)\rho^{n-i}. \]
(This is called the Strako\v{s} matrix.)
\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
Use 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?
\item
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\).
\item
What is \(\beta_{31}?\) What should it be?
\item
Plot \(\log(\normof{\mA \mV_k - \mV_{k+1} \mT_{k+1}} + 10^{-20})\) for
\(k=1\) to \(60\).
\end{enumerate}
\subsection{Problem 3: Krylov methods}\label{problem-3-krylov-methods}
Let \(\mA = \mI + \ve \ve^T\) be a square matrix (where \(\ve\) is the
column vector of all 1s of appropriate dimensions). Suppose we use
MINRES to solve the system \(\mA \vx = \vb\). In exact arithmetic, how
many steps will MINRES take to converge to the exact solution? Be sure
to explain
\textit{how you determine what the answer is. Note, your result
should be self contained and not utilize the theory discussed in class -- this
is good practice for the final; if you do use a theorem to justify your answer,
you may lose a few points.}
\subsection{Problem 4: Solving non-symmetric
systems.}\label{problem-4-solving-non-symmetric-systems.}
Note that there are few ways to turn a non-symmetric linear system into
a symmetric linear system. The first is to use the normal equations
\(\mA^T \mA \vx = \mA^T \vb\). The second is to use a set of augmented
equations:
\[ \bmat{ \mI & \mA \\ \mA^T & 0} \bmat{\vr \\ \vx} = \bmat{ \vb \\ 0 }. \]
\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
Show that the solution of the augmented system of equations exists for
any square, full-rank non-symmetric matrix \(\mA\).
\item
Use CG and MINRES to solve the Candyland linear system from the
beginning of class using these approaches. How many matrix-vector
products do they take compared with your Neumann series-based solver
to converge to a 2-norm relative residual of \(10^{-8}\).
\end{enumerate}
\end{document}