\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,amssymb}
\usepackage[pdftex]{graphicx}
\usepackage[pdftex,colorlinks=true,plainpages=false]{hyperref}
\newcommand{\T}{^\mathsf{T}}
\newcommand{\rmd}{\mathrm{d}}
\begin{document}
\begin{center}
{\Large COMPUTER SCIENCE 314}\\
{\Large Numerical Methods} \\
{\large SPRING 2013} \\
 ASSIGNMENT \# 6 (25 points) \\
{\small March 28}
\end{center}

\subsection*{Announcements}
\begin{itemize}
\item To make up for the cancelled lecture of March 7th, Lecture~23 will
 be given Tuesday, April 2 from 5:00--6:00 pm in LWSN B155
 and again Wednesday, April 3 from 5:00--6:00 pm in LWSN B134.
\item Exam 6 is Thursday, April 18 from noon to 12:25 pm.
 It covers material from this homework, Sections 5.1--5.5
 of the textbook, and Sections 6.1--6.3 of the class notes.
 You can use only pens, pencils, and erasers;
 in particular, no written material nor electronic devices is permitted.
\end{itemize}

\subsection*{Due Thursday, April 11 at noon.}

\begin{enumerate}

\item[0.]
 Read Sections 5.1--5.5 of the textbook.

% Sec 6.1

\item (10 points) Do Exercises 5.12 from the textbook.
 For convenience here are the data:
{\small\begin{verbatim}
x = [1.02 0.95 0.87 0.77 0.67 0.56 0.44 0.30 0.16 0.01]';
y = [0.39 0.32 0.27 0.22 0.18 0.15 0.13 0.12 0.13 0.15]';
\end{verbatim}}\noindent
Getting just the right x and y ranges for the given {\tt contour} data
requires more than one try.
Part~(b) has a typographical error; it should say $[-0.005, 0.005]$.
There is no need to change the x and y ranges for the perturbed orbit.
The function {\tt unifrnd} is convenient.
{\em Hand in} your code, your printout of the two sets of coefficients,
 and a single plot containing both orbits.
 Use {\tt axis equal} for your plot.

% Sec 6.2

\item (4 points) Do Exercise 5.5 from the textbook.

% Sec 6.3

\item (5 points)
Suppose $P$ and $Q$ are two locations on land near the sea with
elevations measured to be 200 meters and 300 meters above sea level,
respectively.  Also suppose that the difference in elevation between
$P$ and $Q$ is measured to be 120 meters.  Assume that each of the three
measurements contains a random error that is normally distributed and
that these errors are independent and of equal standard deviation.
\begin{itemize}
\item[(a)]Express the elevations of $P$ and $Q$ as the solution
of an overdetermined system of linear equations.
\item[(b)]Determine the normal equations for your answer to part (a).
\item[(c)]How should your answer to part (a) be modified
 if the error in measuring the difference in elevation between $P$ and $Q$
 has a standard deviation which is 40\% of the other two standard deviations?
\end{itemize}

\item (6 points)
 Let $x_\ast$ minimize $\|b - A x\|_2$ where $A$ is a matrix having more rows
 than columns, and let $A = QR$ be a full QR factorization.
 \begin{enumerate}
 \item Prove that $x_\ast$ also minimizes $\|Q\T b - R x\|_2$.
 (Note that $\|v\|_2 = (v\T v)^{1/2}$.)
 \item What is the least squares solution of the overdetermined system
 $R x\approx Q\T b$?
 To answer this, you may find it convenient
 to introduce additional symbols for parts of matrices/vectors.
 \end{enumerate}

\newcounter{myenumi}\setcounter{myenumi}{\value{enumi}}
\end{enumerate}

\subsection*{Problems not to hand in}

However, solutions will be provided.
\begin{enumerate}
\setcounter{enumi}{\value{myenumi}}

% Sec 6.1

\item
 Assume the following data
 \[\begin{array}{|c|c|c|c|} \hline
 x & 0 & 1 & 3 \\ \hline
 y & 2 & 2 & 8 \\ \hline
 \end{array} \]
 are the result of $y$ being a linear polynomial in $x$
 except for independent normally distributed
 random errors of equal standard deviation.
 Set up an overdetermined system of linear equations whose least
 squares solution gives the maximum-likelihood
 estimate of the linear polynomial.

% Sec 6.3

\item True or false?  A linear least-squares problem $Ax \approx b$
 always has a unique solution $x$ that minimizes the RMS of
 the residual vector $r=b-Ax$ when normal equations is used.
 Justify your answer.

\item
 Consider the tabulated data
\begin{center}
\begin{tabular}{r|r|r}
$k$ & $x_k$ & $y_k$ \\ \hline
1 & 0 & 1 \\
2 & 1 & 2 \\
3 & 3 & $-2$
\end{tabular}
\end{center}
Determine coefficients $a$ and $b$ such that
$$\sum_{k=1}^3 (y_k - (a x_k + b))^2$$
is minimum.

\end{enumerate}

\subsection*{Learning objectives}

\begin{itemize}
\item Explain the assumptions behind least-squares approximation.
\item Determine a Householder reflection
 that reflects a given vector to a given direction.
\item Form the normal equations.
\item Give the condition
 for uniqueness of the solution of a linear least-squares problem.
\item Define a full QR factorization.
\item Given a full QR factorization, obtain a reduced QR factorization.
\item Explain how to solve a least squares problem from a QR factorization.
\item Explain in general terms how Householder reflections can be used
 to compute a QR factorization.
\end{itemize}

\end{document}