\documentclass[11pt]{article}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{xypic}
\usepackage{nicematrix}
\usepackage{subcaption}
\usepackage{listings}
\lstset{language=Matlab}

\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\headsep}{0in}
\setlength{\headheight}{0in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{9in}

\newcommand{\todo}[1]{\textcolor{red}{[#1]}}

\input xy
\xyoption{all}

\providecommand{\SolutionSearchDirectionsPartA}{}
\providecommand{\SolutionSearchDirectionsPartB}{}
\providecommand{\SolutionSearchDirectionsPartC}{}
\providecommand{\SolutionLeastSquaresGramSchmidtPartA}{}
\providecommand{\SolutionLeastSquaresGramSchmidtPartB}{}
\providecommand{\SolutionHouseholderModified}{}
\providecommand{\SolutionQRByHandPartA}{}
\providecommand{\SolutionQRByHandPartB}{}
\providecommand{\SolutionQRMatlabPartA}{}
\providecommand{\SolutionQRMatlabPartB}{}

%Used to display the marks available in the left margin.
\newcommand{\rmp}{\reversemarginpar\marginpar}

\pagestyle{empty}

\begin{document}

\begin{center}
{\Large {\bf CS 475/675 Spring 2025: Crowdmark Assignment 4}}\\
\end{center}

\noindent
	{\bf Due July 4 at 11:59 pm Eastern.} \\
Submit ALL components of your solutions (written/analytical work, code/scripts, figures,
plots, output, etc.) to CrowdMark in PDF form in the section for each question.\\

\noindent Also separately submit a single zip file containing any and all code/scripts you
write to the Crowdmark A04 DropBox on LEARN, in runnable format (that is, .m).\\

\noindent \textbf{For full marks, be sure to show all your work!}

\begin{enumerate}%{$\bullet$}{\leftmargin 0.5cm}

\item
Let $\{p^i\}$ be a set of A-orthogonal search direction vectors, where $A$ is an SPD matrix.
We want to look for $x^{k+1}$ in {\it all} of these directions.
Thus, we write
\begin{displaymath}
x^{k+1} = x^0 + \sum_{i=0}^k \alpha_i p^i.
\end{displaymath}
We determine $\{\alpha_i\}$ by minimizing $F(x^{k+1})$, where
\begin{displaymath}
F(x) \equiv \frac{1}{2} x^TAx-b^Tx = \frac{1}{2}(x,x)_A - (b,x),
\end{displaymath}
over all search directions.

\begin{enumerate}%{$\bullet$}{\leftmargin 0.7cm}

\item
Show \rmp{[4]}that
\begin{eqnarray*}
F(x^{k+1}) = \frac{1}{2}(x^0,x^0)_A + \sum_{i=0}^k \alpha_i
(x^0,p^i)_A + \frac{1}{2} \sum_{i=0}^k \sum_{j=0}^k \alpha_i \alpha_j
(p^i,p^j)_A - (b,x^0) - \sum_{i=0}^k \alpha_i (b,p^i).
\end{eqnarray*}
\SolutionSearchDirectionsPartA

\newpage

\item
By \rmp{[2]}using the A-orthogonal property, show that
\begin{eqnarray*}
F(x^{k+1}) = \frac{1}{2}(x^0,x^0)_A + \sum_{i=0}^k \alpha_i
(x^0,p^i)_A + \frac{1}{2} \sum_{i=0}^k \alpha_i^2 (p^i,p^i)_A
- (b,x^0) - \sum_{i=0}^k \alpha_i (b,p^i).
\end{eqnarray*}
\SolutionSearchDirectionsPartB

\newpage

\item
To \rmp{[4]}minimize $F(x^{k+1})$, we set $\frac{\partial F}{\partial \alpha_j}
(x^{k+1})=0$.
Show that
\begin{eqnarray*}
\alpha_j = \frac{(r^0,p^j)}{(p^j,p^j)_A},
\end{eqnarray*}
\end{enumerate}
where $r$ is the residual.
Thus $\alpha_j$ depends only on $p^j$, not on any other search directions.
Once we have minimized in direction $p^j$, we are done with that direction.
In other words, each of the $p^j$ minimizes $F(x^{k+1})$ in a subspace and
we \textbf{never} have to look in that subspace again.
\SolutionSearchDirectionsPartC

\newpage

\item
Consider the least squares problem $Ax=b$ where
\begin{displaymath}
A = \begin{bmatrix}
 3 & -3 & -10 \\
 0 &  4 &  16 \\
 4 & -4 & -30 \\
 0 &  3 &  12
\end{bmatrix},
\hspace{1cm}
b = \begin{bmatrix}
1 \\ 1 \\ 1 \\ 1
\end{bmatrix}.
\end{displaymath}

\begin{enumerate}%{$\bullet$}{\leftmargin 0.7cm}

\item
Solve \rmp{[5]}the least squares problem using the normal equations.
Do the computation by hand, and not in Matlab.
\SolutionLeastSquaresGramSchmidtPartA

\newpage

\item
Solve \rmp{[5]}the least squares problem using (classical or modified)
Gram-Schmidt. Determine the $\hat{Q}$ and $\hat{R}$ factors.
Do the computation by hand, and not in Matlab.
\SolutionLeastSquaresGramSchmidtPartB

\end{enumerate}

\newpage

\item
Adapt \rmp{[10]}the ideas of Householder QR-factorization to derive a method to instead compute a factorization
$A=QL$, where $L$ is \textbf{lower} triangular and $Q$ is orthogonal.
Assume that $A$ is square and full-rank. Give a text description of how your algorithm works, supported by illustrations and pseudocode.
(Hint: Derive a modification of the Householder approach such that $\left ( I-2\frac{vv^T}{v^T v} \right )x$ is zero everywhere but its \textbf{last} component, rather than its first.)
\SolutionHouseholderModified

\newpage

\item
In this question, compute each of the specified QR factorizations by hand, and not in Matlab.
Show all of your work.

\begin{enumerate}

\item
Let \rmp{[5]}$A = \begin{bmatrix}
 4 & 2 \\
 -8 & -4 + 9 \sqrt{2} \\
 8 & 4 + 9 \sqrt{2}
\end{bmatrix}$ .
Compute a QR factorization for $A$, in which $Q$ is $3 \times 3$ and $R$ is $3 \times 2$.
Use Householder reflections to do the computation.
\SolutionQRByHandPartA

\newpage

\item
Let \rmp{[5]}$A = \begin{bmatrix}
 1 & 2 \\
 1 & -2 \\
 0 & 1
\end{bmatrix}$ .
Compute a QR factorization for $A$, in which $Q$ is $3 \times 3$ and $R$ is $3 \times 2$.
Use Givens rotations to do the computation.
\SolutionQRByHandPartB

\end{enumerate}

\newpage

\item
In this question, develop a Matlab function to \textbf{efficiently} compute each of the specified QR factorizations.
Include a diary which shows running each function to factorize an example matrix $A$, of size at least $3 \times 2$.

\begin{enumerate}

\item
Develop \rmp{[10]}a Matlab function, \lstinline!QRHouseholder(A)!, which uses Householder reflections to compute a QR factorization of $A$.
If $A$ is $m \times n \ (m \geq n)$, then $Q$ will be $m \times m$ and $R$ will be $m \times n$.
You may find it helpful to start with the \lstinline!QRHouseholderTemplate.m! template.
\SolutionQRMatlabPartA

\newpage

\item
Develop \rmp{[10]}a Matlab function, \lstinline!QRGivens(A)!, which uses Givens rotations to compute a QR factorization of $A$.
If $A$ is $m \times n \ (m \geq n)$, then $Q$ will be $m \times m$ and $R$ will be $m \times n$.
You may find it helpful to start with the \lstinline!QRGivensTemplate.m! template.
\SolutionQRMatlabPartB

\end{enumerate}

\noindent
Once again, submit a copy of everything to CrowdMark in PDF/image format, and separately submit your [runnable] source code to the A04 LEARN DropBox in a single ZIP file.

\end{enumerate}

\end{document}