\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 9},
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 9}
\input{preamble.tex}
\title{Homework}
\begin{document}
\maketitle
\section{Homework 9}\label{homework-9}
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 11th, 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}
\subsection{Problem 1: Updating solutions of linear systems of
equations}\label{problem-1-updating-solutions-of-linear-systems-of-equations}
One of the cases for updating solutions of \(\mA \vx = \vb\) that we did
not discuss in class is what happens when the linear system grows.
Suppose we \emph{add} a row and column to the system of linear equations
in such a way that the system stays non-singular. Formally, we have:
\[ \mA \vx = \vb \quad \to \quad \bmat{ \mA & \vy \\ \vz^T & \theta } \bmat{ \vx' \\ \gamma} = \bmat{ \vb \\ \beta }. \]
In this case, however, we have already computed a factorization to solve
systems with the matrix \(\mA\). Show how to use this to solve for the
new, enlarged systems.
\subsection{Problem 2: Updating factorizations of linear systems of
equations}\label{problem-2-updating-factorizations-of-linear-systems-of-equations}
In class, we showed how to solve \((\mA + \vu \vv^T) \vx = \vb\) when
given a fast factorization method to solve \(\mA \vx = \vb\). In this
problem, we will address the question of how to update the factorization
itself. Suppose that we are given a Cholesky factorization of
\(\mA = \mL \mD \mL^T\) as we saw in class. Show how to update this
factorization to produce \(\mL' \mD' \mL'^T = (\mA + \vu \vu^T)\). Your
algorithm should do no more than \(O(n^2)\) work.
\subsection{Problem 3: The Krylov subspace and eigenvalue
algorithms}\label{problem-3-the-krylov-subspace-and-eigenvalue-algorithms}
In class, we showed that the Krylov subspace:
\[ \mathbb{K}_k(\mA, \vb) = \text{span}(\vb, \mA \vb, \ldots, \mA^{k} \vb) \]
arises when solving \(\mA \vx = \vb\) via the simple Neumann series
method. Here, we note that it also arises in the power-method to
identify the largest eigenvalue of a matrix. Note that the simple
monomial basis for the Krylov subspace is:
\[ \mX_k = \bmat{ \vb & \mA \vb & \ldots & \mA^{k} \vb} \] In this case,
the power-method uses the vector \(\mX_k \ve_k\) as the estimate of the
largest eigenvalue.
\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
State an algorithm to search the Krylov subspace for the largest
eigenvalue of a symmetric matrix using the fact that the largest
eigenvalue solves the problem:
\[ \lambda_{\max} = \MAXone{}{\vx^T \mA \vx}{\normof{\vx} = 1.} \]
(Note, that you are welcome to use ideas that we discuss in subsequent
lectures, but you don't have to. Everything can be done with the
material presented through lecture 21.) Note that you may use any
routine you want on a \((k+1)\)-by-\((k+1)\) matrix.
\item
Implement your algorithm and compare the eigenvalue estimates for a
few small matrices. (Hint, a good idea here would be to show
convergence plots for the error in the largest eigenvalue compared
with iterations -- usually on a log-y-scale.)
\item
Comment on any issues that arise in your implementation.
\end{enumerate}
\subsection{\texorpdfstring{\textbf{Not required} Problem 4: Matrix
functions}{Not required Problem 4: Matrix functions}}\label{not-required-problem-4-matrix-functions}
We aren't doing this problem because I got the homework out late. Work
out an analytical formula for the largest entry of
\[ \text{exp}(\mA_n) \] where \(\mA_n\) is a \(n\)-by-\(n\) tridiagonal
matrix of with entries of 1. For instance:
\[ \mA_5 = \bmat{1 & 1 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 \\
0 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1}. \]
\end{document}