\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 3},
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 3}
\input{preamble.tex}
\title{Homework}
\begin{document}
\maketitle
\section{Homework 3}\label{homework-3}
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 16th, 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: Getting Poisson's equations to converge with
Richardson}\label{problem-1-getting-poissons-equations-to-converge-with-richardson}
In class we showed that the Richardson method for \(\mA \vx = \vb\)
\[ \vx\itn{k+1} = \vx\itn{k} + \alpha \vr\itn{k} \] will converge for
any positive semi definite matrix as long as \(\alpha < 2 / \rho(\mA)\).
We have not yet determined ways of computing \(\rho(\mA)\), however.
In the previous homework (HW2), you found that setting \(\alpha = 1\)
did not result in a method that converged for Poisson's equation with
\(n = 10\).
\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
Experimentally or theoretically, find a value of \(\alpha\) such that
using the Richardson method will converge for Poisson's equation (as
used in HW2) with \(n=10\).
\item
What happens when you try \(n=20\), does the same value of \(\alpha\)
work? If not, find a new one that does.
\item
Experimentally, find a value of \(\alpha\) that takes the fewest
iterations to produce a solution with relative residual \(10^{-5}\)
for both \(n=10\) and \(n=20\).
\item
Prove that using \(\alpha < 1/4\) will result in a method that
converges.
\end{enumerate}
\subsection{Problem 2: Norms}\label{problem-2-norms}
Let \(f(\vx)\) be any vector norm. This means that \(f(\vx)\) must be a
vector norm for \(\vx \in \RR^{1}\). Show that if \(\vx \in \RR^{1}\),
then \(f(\vx) = \alpha |x_1|\) for some value of \(\alpha\).
\subsection{Problem 3}\label{problem-3}
Consider the following function: \[ f(\mA) = \max_{i,j} |A_{i,j}|. \]
\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
Show that \(f\) is a matrix norm. (Very easy!)
\item
Show that \(f\) does not satisfy the sub-multiplicative property.
\item
Show that there exists \(\sigma > 0\) such that:
\[ g(\mA) = \sigma f(\mA) \] is a sub-multiplicative matrix-norm.
\item
\textbf{Extra tough problem for the adventurous! Not graded.} This
problem has a relatively easy proof related to something we saw in
class. But making it fully formal requires a few technicalities that
are easy to get tripped up on. Now let \(\normof{\mA}\) be an
arbitrary matrix norm. Show that there exists \(\sigma > 0\) such that
\(h(\mA) = \sigma \normof{\mA}\) is a sub-multiplicative matrix-norm.
\end{enumerate}
\subsection{Problem 4: Solving the PageRank linear system of equations
via
Richardson.}\label{problem-4-solving-the-pagerank-linear-system-of-equations-via-richardson.}
We will derive the following at some point in the class, but you have
everything you need to solve this right now. Let \(\mP\) be a matrix
that is entry-wise non-negative (\(P_{i,j} \ge 0\)) and also has columns
that sum to \(1\) (\(\sum_{i} P_{i,j} = 1\)).
Informally, the matrix \(\mP\) describes the probability of moving
around a graph, just like the matrix \(\mT\) described the probability
of moving around the game of Candyland. The interpretation of
\(P_{i,j}\) is the probability of moving from node \(j\) to node \(i\).
The PageRank linear system is:
\[ (\mI - \alpha \mP) \vx = (1-\alpha) \vv \] where \(v_i \ge 0\) and
\(\sum_i v_i = 1\). The solution \(x_{i}\) can be interpreted as the
asymptotic fraction of time a random walk spends at a node of a graph
when, at each step, it moves in the graph (according to \(\mP\)) with
probability \(\alpha\) and it \emph{jumps} according to \(\vv\) with
probability \((1-\alpha)\).
Show that we can solve the PageRank linear system using the Richardson
method.
\end{document}