\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 5},
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 5}
\input{preamble.tex}
\title{Homework}
\begin{document}
\maketitle
\section{Homework 5}\label{homework-5}
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, September 30th, 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: Show that the Jacobi method converges on a
diagonally dominant
system.}\label{problem-1-show-that-the-jacobi-method-converges-on-a-diagonally-dominant-system.}
One of the common classes of matrices are called diagonally dominant.
They have, or can be permuted to have, entries on on the diagonal such
that: \[ \sum_{j \not= i} |A_{i,j}| \le |A_{i,i}| \text{ for all } i. \]
Suppose that \(\mA \vx = \vb\) is a diagonally dominant system. Show
that the Jacobi iteration will converge to the solution when, for at
least one row \(k\), we have:
\[ \sum_{j \not= k} |A_{k,j}| < |A_{k,k}|. \]
\subsection{Problem 2: Implement Gauss-Seidel and Jacobi for a sparse
system of
equations}\label{problem-2-implement-gauss-seidel-and-jacobi-for-a-sparse-system-of-equations}
For each iteration through all \(n\) rows, you must use work
proportional to the number of non-zeros in the matrix. Stop your
iteration when the relative residual drops below \(10^{-4}\).
Show how many iterations the methods take on the Candyland linear system
of equations.
\subsection{Problem 3: Eigenvalue
Review}\label{problem-3-eigenvalue-review}
Prove or disprove!
\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
The eigenvalues of an \(n \times n\) real-valued matrix are always
real.
\item
The solution to \((\mA^T \mA + \gamma I) \vx = \vb\) is unique for any
\(\gamma > 0\).
\item
Every \(n \times n\) matrix can be written as the sum of two
non-singular matrices.
\item
An \(n \times n\) real-valued matrix has an orthogonal set of
eigenvectors.
\item
An \(n \times n\) matrix \(\mA\) and its transpose \(\mA^T\) have the
same set of eigenvalues.
\end{enumerate}
\subsection{Problem 4: The power method, and
beyond!}\label{problem-4-the-power-method-and-beyond}
We'll show that the humble power-method is really rather more
interesting than we saw in class! It's a flexible starting point that
serves as the basis for almost all of the eigenvalue algorithms.
\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
Consider the power method as a Julia code:
\begin{verbatim}
maxit = 1000
lam = 0
for i=1:maxit
x = A*x
x = x./norm(x)
lam = x'*A*x
end
\end{verbatim}
Let \(\vx\itn{i}\) be the value of \texttt{x} at the start of the
\(i\)th instance of this loop. And let \(\lambda\itn{i}\) be the value
of \texttt{lam} at the \emph{start} of the \(i\)th iteration. Suppose
that \(\vx\) and \(\lambda\) are the true eigenvector, eigenvalue pair
that we are converging too. If \(\normof{\vx - \vx\itn{i}} = \eps\),
show that: \(|\lambda - \lambda^{i}|\) is \(O(\eps^2)\) (where the
constant may depend on the matrix \(A\)).
\item
Show that if \(\vx\) is an eigenvector of \(\mA\) with eigenvalue
\(\lambda\), then \(\vx\) is an eigenvector of \(\mA^{-1}\). What is
the eigenvalue?
\end{enumerate}
\subsection{Problem 5: A matrix where Jacobi will not
converge.}\label{problem-5-a-matrix-where-jacobi-will-not-converge.}
Show that the Jacobi iteration will not converge for any choice of
\(\mM\) for the following system \[ \bmat{1 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 \\
0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 }
\vx = \bmat{1 \\ 1 \\ 1 \\ 1}. \]
\subsection{Problem 6: Find and read a
proof.}\label{problem-6-find-and-read-a-proof.}
Find and read two different proofs that Gauss-Seidel will converge for
any symmetric positive definite system \(\mA\). Give the references.
List any steps that were unclear. Which proof do you prefer and why?
\end{document}