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

\subsection*{Announcement}
\begin{itemize}
\item Exam 3 is on Thursday, February 28 from noon to 12:25 pm.
 It covers material from this homework, Sections 2.8--2.11 of the textbook,
 and Sections 3.5--3.8 of the class notes.
\end{itemize}

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

\begin{enumerate}

\item[0.]  % (essential)
 Read Sections 2.8--2.11 of the textbook, omitting the last paragraph
 (on inverse iteration) beginning on page~76.

\item[] {\it Python notes.}
 The equivalent of a matrix is a {\tt numpy.ndarray}
 and of a cell array is a {\tt list}.
 The equivalent of {\tt find} is {\tt numpy.where}.

% 3.5
\item (4 points)
 Suppose $x=A^{-1}b$ and that $\Delta  x$ is the error in $x$ caused by
introducing an error $\Delta b~ {\rm in}~ b$.
\begin{enumerate}
\item Write down a relation that relates $\Delta x$ to $\Delta b$
{\em using the condition number} cond($A$).
\item  Suppose that cond($A$)=10 in the maximum norm.
Apply part (a) to
$$b=\left[\begin{array}{c}9\\20\end{array}\right], \quad
 \Delta b=\left[\begin{array}{c}-0.2\\0.1\end{array}\right], \quad
 x=\left[ \begin{array}{c}3\\5\end{array}\right]$$
 to get bounds on the maximum norm of $\Delta x$.
\item
 From this, deduce bounds on the magnitudes of {\em the elements}
$\Delta x_{1}$ and $\Delta x_{2}$ of $\Delta x$.
\item
 Further suppose that $\|A\|_\infty= 40$.
 What is $\|A^{-1}\|_\infty$?
\end{enumerate}

% 3.7
\item (9 points) Do Exercise 2.19(a, c, d) from the textbook.
 For part (a) you may use either {\tt bslashtx} or {\tt mybslash}.
 Compare the computing times of methods (a) and (c).
 Do part (d) twice.
 (The best way to view the solution is to plot it.)
 {\em Hand in}
 your code, the two timings, and the two estimates of the condition number.

% 3.8
\item (3 points) Do Exercise 2.21 from the textbook.

\item (9 points) Do Exercise 2.26(a, c, d) from the textbook.
 Incorporate the code given in the penultimate paragraph on page~76;
 do not use the code in Exercise~2.27.
 For a tolerance in part~(c) use $10^{-4}$.
 Python users---but only they---may use
 dense matrices instead of sparse matrices.
 {\em Hand in} your code for each of parts (a), (c), and (d).

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

\newpage
\subsection*{{\em DRAFT} Problems not to hand in}

However, solutions will be provided.
\begin{enumerate}
\setcounter{enumi}{\value{myenumi}}
% 3.5
\item
 Give the maximum norm of the following:
 $$\left[ \begin{array}{c}
 1 \\ -2 \\ -3 \\ 0 \end{array} \right], \qquad \qquad \qquad
 \left[ \begin{array}{rrrr}
 10 & -10 & -1 & -2 \\
 0 & 0 & 20 & 1 \\
 -5 & -12 & -2 & 1 \\
 \end{array} \right].$$
{\bf Solution:}
{\small\begin{verbatim}
\end{verbatim}}\noindent
\item
 Calculate the condition number of the following, and
classify each as either ill-conditioned or well-conditioned.
$$\left[ \begin{array}{rr}
10 & 0 \\ 0 & 10 \\ \end{array} \right], \qquad \qquad \qquad
\left[ \begin{array}{rr}
1 & 2 \\ -3 & -6 \\ \end{array} \right],$$
$$\left[ \begin{array}{rr}
1 & 1 \\ 1 & 1.0001 \\ \end{array} \right], \qquad \qquad \qquad
\left[ \begin{array}{rr}
0.0001 & 1 \\ 1 & 1 \\ \end{array} \right].$$
 {\bf Solution:}
{\small\begin{verbatim}
\end{verbatim}}\noindent

% 3.8
\item Do Exercise 2.25 from the textbook.
\\ {\bf Solution:}
{\small\begin{verbatim}
obtain solution independently and then check it
\end{verbatim}}\noindent
\end{enumerate}

\subsection*{{\em DRAFT} Learning objectives}

\begin{itemize}
\item Define the $\mathrm{l}_p$ norm of a vector for $p = 1, 2,\infty$.
\item State and reason about the basic properties of a vector norm.
 (From three properties, all others follow.)
\item Define the relative error and relative residual, as given in the class
 notes, but for a general norm.
\item
 Define the condition number of a matrix in terms of a general vector norm.
\item Supposing an error is introduced into the right-hand side vector of a
 linear system, give a bound on the relative error in the solution
 in terms of the relative error in the right-hand side.
\item Define the norm of a matrix in terms of a general vector norm.
\item Give a formula for the condition number of a matrix in terms of
 a matrix norm.
\item State a ballpark estimate of the relative error  and of the relative
 residual in Gaussian elimination with partial pivoting.
\item Define sparsity and bandwidth.
\item Program the Thomas algorithm.
\item
 Define a left stochastic matrix and state its relevance to a Markov chain.
 Define a stationary state.
 State an additional condition on the matrix
 that ensures uniqueness of the stationary state.
\item Motivate and justify the direct method for finding the stationary state.
\item Justify the direct method,
 \[ \bar{x} = (I - pGD)\backslash e,\quad x = \bar{x}/e\T \bar{x},\]
 for finding the stationary state of the PageRank Markov chain.
 State the attractive property of $pGD$ that is lacking in $z e\T$.
\item Given the matrix of transition probabilities, program the power
 method for finding a stationary state.
\end{itemize}

\end{document}