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

\subsection*{Announcements}
\begin{itemize}
\item
\begin{tabbing}
mmmmmmmmmmmmm\=mmmmmmmmmmmmmmmmm\=mmmmmmmmmmmmmmmmm \kill
Office hours:\> Instructor \>  Teaching Assistant \\
Monday \> \> 4:00--5:00 \\
Tuesday \> 2:30--3:00 \> 4:00--5:00\\
Wednesday \> 2:30--3:00 \> 4:00--6:00
\end{tabbing}
\item Exam 2 is Thursday, February 14th from noon to 12:25 pm.
 It covers material from this homework, Sections 1.7--2.7 of the textbook,
 and Sections 2.0--3.1.1, 3.2--3.4 of the class notes.
 You can use only pens, pencils, and erasers;
 in particular, no written material nor electronic devices are permitted.
\end{itemize}

\subsection*{Due Thursday, February 7 at noon.}

\paragraph{Hand in hard copies}
 Type or neatly print your solutions.
 For Problem 1 include a printout of code.
 For Problem 4 include a printout of code and of results.

\begin{enumerate}

\item[0.] (essential)
 \begin{enumerate}
 \item Read course policy on cheating and acknowledge that you understand it.
 \item State whether you are using Matlab, Octave, Julia, or Python.
 \end{enumerate}
 Read Sections 1.7--2.7 of the textbook.

%%% 2.3
\item (6 points) Do the first part of Exercise~1.7 from the textbook,
 using the textbook's indexing of the Fibonacci sequence.
 For full credit, obtain your answer by using the 3-term recurrence
 to generate the sequence and checking the correctness
 of the addition at each step by using the following principle:
 \begin{quote}
 If $x$ and $y$ are machine numbers, $\frac12\le x/y\le 2$,
 floating-point subtraction $x\hat{-}y$ is exact.
 \end{quote}

\item (3 points) Do Exercise~1.34 from the textbook.
 In addition to your explanation, include the (first 5 digits of the)
 numerical result.

%%% 3.4
\item (6 points) Do Exercise~2.10 from the textbook with ``triangular''
 replaced by ``upper triangular''.
 Also, do not rewrite {\tt bslashtx}; merely, state what minimal changes
 are needed, e.g., ``replace \ldots\ in function \ldots\ by \ldots''.

\newpage
\item (10 points) Do Exercise~2.14 from the textbook, except
\begin{enumerate}
\item do it for {\tt mylu} and {\tt mybslash} given below,
\item test your modified {\tt mylu} on the matrix \\
{\tt A = [0 4 2 4; 0 0 6 -4; 4 8 4 0; -2 -4 1 0]}.
\item test your modified {\tt mybslash} on the system
 with the above coefficient matrix and the right-hand side vector
 {\tt b = [14; 0; 0; 6]}.
\end{enumerate}
 Note that
 \begin{itemize}
 \item[(i)] The unreduced matrix excludes the first {\tt k-1} rows.
 \item[(ii)] If $Q$ is the matrix represented by {\tt q},
 $LU = PAQ\T$ and $A^{-1} = Q\T U^{-1} L^{-1} P$.
 \item[(iii)] Multiplication of a vector {\tt v} by $Q\T$ can be effected by
 {\tt v(q) = v}.
\end{itemize}
 There are several ways to get the largest element of a matrix and its indices.
 Repeated use of {\tt max} is one way.
{\small\begin{verbatim}
function [L, U, p] = mylu(a)  % mylu.m
   [n, n] = size(a);
   p = (1:n)';
   for k = 1:n-1
      [r, m] = max(abs(a(k:n,k)));
      m += k-1;
      a([k m],:) = a([m k],:);
      p([k m]) = p([m k]);
      i = k+1:n;
      a(i,k) = a(i,k)/a(k,k);
      j = k+1:n;
      a(i,j) = a(i,j) - a(i,k)*a(k,j);
   end
   L = tril(a, -1) + eye(n, n);
   U = triu(a);
\end{verbatim}}\noindent
{\small\begin{verbatim}
function x = mybslash(A, b)  % mybslash.m
   % solves A*x = b
   [n, n] = size(A);
   [L, U, p] = mylu(A);
   y = forward(L, b(p));
   x = backsubs(U, y);
function y = forward(L, b)
   % solves L*y = b where L is unit lower triangular
   [n, n] = size(L);
   for k = 1:n-1
      i = k+1:n;
      b(i) = b(i) - L(i, k)*b(k);
   end
   y = b;
function x = backsubs(U, y)
   % solves U*x = y where U is upper triangular
   [n, n] = size(U);
   x = y;
   for i = n:-1:1
      j = i+1:n;
      x(i) = (y(i) - U(i, j)*x(j))/U(i, i);
   end
\end{verbatim}}\noindent

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

\newpage

\subsection*{Problems not to hand in}

However, solutions will be provided.
\begin{enumerate}
\setcounter{enumi}{\value{myenumi}}
%%% 2.1
\item Is 35.375 exactly representable
 as a double precision floating-point number? Justify your answer.
\item
 In double precision (53 binary digits), what is the successor
 of 2 (the machine number just after 2)?
 the predecessor of 2?
\item
On a computer with binary floating point numbers do all machine
numbers (other than infinity or NaN) have terminating representations
in base ten? Explain why your answer is true.

%%% 2.2
\item
 Let $x$, $y$ be real numbers and let $\fl$ denote rounding to the nearest
 machine number for a binary floating-point system of unlimited exponent range.
 For each of following indicate whether or not it is always true:
 \begin{enumerate}
 \item $\fl(\fl(x)) = \fl(x)$,
 \item $ x \leq y ~\Rightarrow~ \fl(x) \leq \fl(y)$,
 \item $ \fl(2x) = 2\fl(x)$.
 \end{enumerate}
 For any that is not always true give a counterexample.
%%% 2.3
\item If four machine numbers $a$, $b$, $c$, $d$ satisfy
 $a+b=c \times d$ (exact arithmetic), does it always follow
 that $a \hat{+} b=c \hat{\times} d$ (rounded arithmetic)
 assuming no underflow or overflow? Explain.
%%% 2.4
\item
 Consider the expression $\sqrt{y} - \sqrt{x}$ where $x, y \geq 0$.
 \begin{enumerate}
 \item For which
 values of $x$ and $y$ might there be a large relative error in the answer due
 to roundoff error in the calculation?
 \item Give an alternative expression that avoids the problem.
 \end{enumerate}
\item
 Consider the evaluation of $(1/(1 + x)) - 1$ in floating-point arithmetic
 where $x$ is a {\em positive} (machine) number.
 \begin{enumerate}
 \item For which values of $x$ might the computed result have a relative
  error much bigger than the unit roundoff error?
  (Answer yes or no to each of the possibilities presented below.)
  \begin{enumerate}
  \item $x \ll 1$ ($x$ very small)?
  \item $x \approx 1$?
  \item $x \gg 1$ ($x$ very large)?
  \end{enumerate}
 \item What is the best way to prevent this?
 \end{enumerate}
%%% 3.1
\item
 Let $x = u$, $x = v$,
 $x = w$ each be a solution of $A x = b$
 where $A$ is a square matrix.
 What condition(s), if any, must be satisfied for
 $x = \alpha u + \beta v + \gamma w$
 to be a solution of $A x = b$
 where $\alpha$, $\beta$, and $\gamma$ are scalars?
 Simplify your answer.
%%% 3.4

\item Do Exercise~2.11 from the textbook.

\item Suppose that we have a system $A x=b$ where
 $b=[8~~1~~0]\T$ and suppose the {\tt mylu}
 algorithm given in the class notes yields values
 $$ \left[ \begin{array}{ccc}
  1 &  0 & 0 \\
  -1/2 & 1 & 0 \\
  1/4 & 1/2 & 1 \\
  \end{array}\right],
 \left[ \begin{array}{ccc}
  4 & -1 & 2 \\
  0 & 1/4 & 1/2 \\
  0 & 0 & -3/2 \\
  \end{array}\right],
  ~\left[ \begin{array}{c} 3 \\ 1 \\ 2 \end{array}\right].$$
 Use this to determine the reduced upper triangular system $Ux=c$ where
 $U = L^{-1}PA$, $c = L^{-1}Pb$, and $P$ is the matrix represented by $p$.
\item For the system $Ax=b$ where
 $$ A = \left[\begin{array}{rrr}
  2 & 1 & -1 \\
  4 & 0 & -1 \\
  -8 & 2 & 2 \\ \end{array} \right], \qquad b =
  \left[\begin{array}{r} 6 \\ 6 \\ -8 \\ \end{array} \right].$$
 show the calculation of {\tt mybslash} step by step.
\end{enumerate}

\subsection*{Learning objectives}

For floating-point computation
\begin{itemize}
\item Determine
 whether a number is exactly representable as a floating-point number.
\item Round a number to the nearest machine number.
\item Determine the result of a floating-point operations;
 know when a floating-point operation is exact.
\item Design an algorithm to minimize roundoff error effects associated
 with cancellation.
\end{itemize}
For linear systems of equations
\begin{itemize}
\item Define matrix concepts (matrix operations, determinant, inverse,
 permutation matrix, triangular matrix) and reason about them.
\item Define elementary linear algebra concepts
 (linear independence, rank, null space, elementary row operations)
 and reason about them.
\item Program Gaussian elimination with (or without) partial pivoting
 so that it returns an LU factorization of a permutation of the original
 square matrix.  The permutation should be returned as a vector.
\item Invert a permutation matrix.
\item Program a backsolve (the solution of a linear system,
 given an LU factorization of a permutation of the coefficient matrix).
\item Know when an LU factorization fails. When a backsolve fails.
\item Reason about the LU factorization and backsolve algorithms.
 Make minor modifications to them.
\end{itemize}

\end{document}