\documentclass[11pt,onecolumn]{article}
\usepackage{amssymb, amsmath, amsthm,graphicx, paralist,algpseudocode,algorithm,cancel,url,color}
\usepackage{sectsty}
\usepackage{fancyvrb}
\usepackage{mathrsfs}
\usepackage{multirow}
\usepackage{hhline}
\usepackage{booktabs}
\usepackage[table]{xcolor}
\usepackage{tikz}
% \usepackage[framed,numbered,autolinebreaks,useliterate]{mcode}
\usepackage{listings}
\usepackage{enumitem}

\newcommand{\bvec}[1]{\mathbf{#1}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Rn}{\R^{n\times n}}
\newcommand{\Rmn}{\R^{m\times n}}
\newcommand{\Cn}{\C^{n\times n}}
\newcommand{\Cmn}{\C^{m\times n}}
\newcommand{\cO}{\mathcal{O}}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\trace}{trace}
\DeclareMathOperator{\diag}{diag}
\sectionfont{\Large\sc}
\subsectionfont{\sc}
\usepackage[margin=1 in]{geometry}
\begin{document}
\noindent
\textsc{\Large CS 6210: Homework 2}\\
Instructor: Anil Damle\\
Due: September 20, 2018\\

\subsection*{Policies}
You may discuss the homework problems freely with other students, but please
refrain from looking at their code or writeups (or sharing your own).
Ultimately, you must implement your own code and write up your own solution to
be turned in. Your solution, including supporting plots and requested output from your code
must be typeset and submitted via the CMS as a single pdf file. Additionally, please
submit any code written for the assignment via the CMS as well. This can be done
by either including it in your solution as an appendix, or uploading it as a zip
file.\\
\hrule
\vspace{1cm}
\noindent

\subsection*{Question 1:}
For the following four problems state whether you think it is plausible/reasonable to try and construct stable or backwards stable algorithms. Think carefully about what the input/output space of such algorithms is and based on your characterization of the problem justify your choice.
\begin{enumerate}
\item Computing the inner product $x^*y$ given vectors $x,y\in\C^n.$
\item Computing the outer product $xy^*$ given vectors $x,y\in\C^n.$
\item Computing Cholesky factorization ($A=LL^*,$ with $L$ lower triangular) of a given Hermitian positive definite matrix $A\in\Cn.$
\item Computing the SVD of a given matrix $A\in\Cn.$
\end{enumerate}

\subsection*{Question 2:}
For any square non-singular matrix $A,$ prove that $1/\kappa_2(A)$ is the relative distance to the nearest singular matrix to $A$ in the two-norm. In other words, prove that
\[
\frac{1}{\kappa(A)} = \min_{\text{rank}(X)<n}\frac{\|A-X\|_2}{\|A\|_2}.
\]


\subsection*{Question 3:}
Assume we solve a problem $f$ with a stable algorithm $\tilde{f}$, prove that the relative accuracy is bounded by $\cO(\kappa(x)\mu)$ where $\mu$ is machine precision and $\kappa(x)$ is the relative condition number of $f$ at $x.$

\subsection*{Question 4:}
Implement LU factorizations with no, partial, and complete pivoting for $A\in\Rn$. Then, address the following:
\begin{itemize}
\item Demonstrate that your implementations can accurately solve most well-conditioned square non-singular linear systems $Ax=b$ given $A$ and $b,$ and scales as $\mathcal{O}(n^3).$ Clearly outline how you test this and include your results.
\item Construct test cases where without the use of pivoting your algorithm will result in large errors in the solution\textemdash demonstrate this does indeed happen.  
\item Construct a test case where partial pivoting fails to yield a good solution but complete pivoting does\textemdash demonstrate this does indeed happen. Such examples exist, but are typically considered pathological and ``rare'' enough that simply using LU with partial pivoting (despite its poor worst case theoretical performance) is fine in practice.
\item Consider computing the LU factorization (all three ways) of the so-called Hilbert matrix of size $n$ (defined as $H_{ij}=1/(i+j-1)$ and a symmetric positive definite matrix). For moderate $n$ what do you observe about $\|LU-H\|_2$ (adding permutation matrices as applicable)? What about the accuracy of a solution to $Hx=b$? Explain your observations.
\end{itemize}
\end{document}