% -*-latex-*-
%
% CS395T Data Mining: A Mathematical Perspective
% homework1.tex
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\documentclass{hw}
\usepackage{amsmath, amssymb, bm,url}
%\usepackage{epsfig}
%%%%%%%%%%%%%\documentstyle[12pt,draft,twoside,epsf]{IEEEtran}
% Use the standard set of macros.
\input{std-mac}
% Lecture information.
\lecturenum{6}
\lecturedate{Oct 29, 2008}
\lecturer{Inderjit Dhillon}
\lecturescribe{}
\keywords{Gaussian Elimination, Partial Pivoting, Complete Pivoting}
\bibliographystyle{alpha}
%%%%%%%%%%%%%%%%\input{epsf}
\begin{document}
% Create title box.
\maketitle
\begin{enumerate}
\item
Problem 21.5, 21.6
\item Consider matrices $W_{n}(x)$
of the form:
$$W_{5}(x) =
\left( \begin{array}{rrrrc}
1 & 0 & 0 & 0 & 1 \\
-1 & 1 & 0 & 0 & 1 \\
-1 & -1 & 1 & 0 & 1 \\
-1 & -1 & -1 & 1 & 1 \\
-1 & -1 & -1 & -1 & 1+x \\
\end{array} \right), \;\;\;\;
0 \leq x \leq 2.
$$
\begin{enumerate}
\item[\underline{a}] What is the condition number (use ``rcond'' in
MATLAB) of $W_{n}(x)$ when $n = 25, 50, 100$ and $x = 0, 1, 2$?
\item[\underline{b}] What is the $LU$ decomposition of $W_{n}(x)$?
Does partial pivoting make any difference?
\item[\underline{c}] Consider single precision arithmetic in which
$fl(2^{24} + 1) = 2^{24}$. Find the smallest value of $n$ for which
Gaussian Elimination will return the solution of $W_{n}(0) y = e_{1}$,
when we asked for $W_{n}(1) y = e_{1}$? What about in IEEE double
precision arithmetic?
\item[\underline{d}] Can you tell based on the above if the MATLAB
command ``$\backslash$'' does partial or complete pivoting?
\end{enumerate}
{\sc Answers} to \underline{b} and \underline{c} should use pen and
paper only (but feel free to experiment in MATLAB).
\item Implement Gaussian Elimination with Partial Pivoting (GEPP) and with Complete Pivoting(GECP). Verify on the matrix given in the previous problem that GECP gives higher accuracy solution than GEPP.
\end{enumerate}
\end{document}