% This is a LaTex file.
% Homework for the course "Scientific Computing",
% Spring semester, 1996, Jonathan Goodman.
% A latex format for making homework assignments.
\documentstyle[12pt]{article}
% The page format, somewhat wider and taller page than in art12.sty.
\topmargin -0.1in \headsep 0in \textheight 8.9in \footskip 0.6in
\oddsidemargin 0in \evensidemargin 0in \textwidth 6.5in
\begin{document}
% Definitions of commonly used symbols.
% The title and header.
\noindent
{\scriptsize Scientific Computing, Spring 1996} \hfill
\begin{center}
\large
Assignment 2.
\normalsize
\end{center}
\noindent
Given February 5, due January 12.
\vspace{.3in}
% The questions!
\noindent
{\bf Objectives:} To explore an ill conditioned matrix.
\vspace{.5cm}
For this assignment you will need software that estimates the condition
number of a matrix. This can be matlab, or a standard scientific
subroutine package (e.g. NAG) or software from netlib. If you don't
have access to such software, you will have to skip part (1).
If you don't find a routine that estimates condition number but you
can find one that computes the singular values or the singular value
decomposition, the condition number is
$\sigma_{\mbox{\scriptsize max}}/\sigma_{\mbox{\scriptsize max}}$. If
you can't compute singular values but you can compute eigenvalues of
symmetric matrices, compute the eigenvalues of $A^*A$,
$\lambda_1 \geq \cdots \geq \lambda_n$. The condition number of $A$ is
$\sqrt{\lambda_1/\lambda_n}$.
For a fixed $n$, define $A$ to be the $n \times n$ matrix with all
entries zero except the $a_{ii} = 1$ and $a_{1,i+1} = 2$ for all
$i$. That is, $A$ has $1$ on the diagonal and $2$ just above the
diagonal and all the rest zero. The determinant of this matrix is $1$
and its norm is about $3$ (depending on exactly which norm is used).
\begin{description}
\item[(1)]
Find the (estimated) condition number of $A$ as a function of $n$ for
$n=2,3,\ldots$ until the condition number becomes (in the computer) infinite.
\item[(2)]
Let $x \in R^n$ be the vector with $n$ components whose components are
given by $x_j = 1$ if $j$ is even and $x_j = 1/3$ if $j$ is odd. The
value $1/3$ is not stored exactly in the computer in floating point.
Compute $b=Ax$ by simple matrix multiplication. Now compute $y$ by
solving the equations $Ay=b$ where $b$ has just been computed. Write
a program to do this in FORTRAN, C, or C++ using back back substitution
on an upper triangular matrix that is bidiagonal (see Kahaner,
Moler, and Nash). Compute $\left\| x-y \right\|$ for some norm and
plot this as a function of $n$ so long as possible. Compute
$\left|Ay-b\right|$
for the $y$ you have and check its dependence on $n$. Comment on the
contrast between this and the dependence of $\left\| x-y \right\|$ on $n$.
\item[(3)]
Is the error $\left\| x-y \right\|$ of the order predicted by the size of
roundoff error and the condition number of $A$?
\end{description}
\end{document}