\documentclass{article}
\begin{document}

\centerline{\bf CS/MATH 3414 FIRST EXAM (Exam1)}
\bigskip\rightline{Name \leaders\hrule\hskip 2.5in}
\medskip\hrule\noindent
Show your answers on these pages. Either show your work on these pages
or on attached sheets.\smallskip\hrule\medskip


\begin{enumerate}
\def\urule{\hbox{\leaders\hrule\hskip 40pt}}\def\pn#1{\filbreak
\item{#1}}\def\n#1{\left\|#1\right\|}\def\mn#1{\left\|#1\right\|_\infty}
\def\lfil{\hfil\penalty0}
\pn(10) Give the IEEE standard 64-bit floating point representation
of $33.5$ (express your answer in hexadecimal).


\begin{enumerate}
\item 
Translate number to binary: $(100001.1)_2$
\item 
Put into scientific notation: $(1.000011)_2 \times 2^5$ \\
True exponent: $e = 5$
\item
Figure biased exponent: \\
exponent bias for IEEE 64-bit is 3FF \\
\begin{tabular}{*{4}{c}}
0011 & 1111 & 1111 & (3FF)\\
     &      & 0101 & (e)\\
\hline
0100 & 0000 & 0100 & (E)
\end{tabular}

\item
(Leave first 1 off significand.) \\
\begin{tabular}{*{7}{c}}
\# bits: & 1 && 11 && 52 &\\
\hline
\vrule& sign bit &\vrule& biased exponent &\vrule& significand &\vrule\\
\hline
& (0 && 100 0000 0100 && 0000 1100 $\cdots$ 0000 $)_2$ & \\
\hline
&&& (4040 C000 0000 0000$)_{16}$ &&&
\end{tabular}\\             
\end{enumerate}

\pn(10) Let $x=(x_1,\ldots,x_n)$ be an arbitrary real $n$-vector.  
Find the smallest constant $C$ such that $||x||_1 \leq C\mn{x}$ always holds.\\
$C = n$ because $\sum_{i=1}^n |x_i| \le n \max_i|x_i|$

\pn(20) Let $$A=\pmatrix{10^{10}&1\cr 0&10^{-10}\cr}
.$$ det $A=1$, 
$\mn A=1+10^{10}$, $\mn{A^{-1}}=10^{10}$, cond $A=10^{10}+10^{20}$.
\vskip .2in

\pn(20) Compute the $LDL^t$ factorization of $A$, where $L$ is a unit lower 
triangular matrix and $D$ is a diagonal matrix. \\
$A = \pmatrix{4&0&-2\cr 0&1&1\cr -2&1&11\cr}, L = ?, D = ? $
\vskip .1in
First compute the LU Decomposition: \\
% Commented out stuff is wrong - need to fix
$A = \pmatrix{4&0&-2\cr 0&1&1\cr -2&1&11\cr} \rightarrow 
     \pmatrix{4&0&-2\cr 0&1&1\cr  0&4&10\cr} \rightarrow
     \pmatrix{4&0&-2\cr 0&1&1\cr  0&0&9\cr } = U$ \\
$A = LU = \pmatrix{1&0&0\cr 0&1&0\cr -.5&1&1\cr} \pmatrix{4&0&-2\cr 0&1&1\cr 0&0&9\cr}$ \\
Then, $U = DL^t$ \\
$\pmatrix{4&0&-2\cr 0&1&1\cr  0&0&9\cr } = 
	\pmatrix{4&0&0\cr 0&1&0\cr 0&0&9\cr}\pmatrix{1&0&-.5\cr 0&1&1\cr 0&0&1\cr}$ \\

\pn(10) Let $A = QR$ where $A \in E^{n\times n}$ is invertible, $Q \in 
E^{n\times n}$ has the property that $Q^TQ = I$, and $R \in E^{n \times n}$ 
is upper triangular.  Given $Q$ and $R$, explain how one would solve a linear 
system $Ax = b$ for $x$.
\vskip .1in
\begin{tabular}{*{3}{l}}
$A$ & = & $QR$ \\
$QRx$ & = & $b$ \\
$Q^TQRx$ & = & $Q^Tb$ \\
$IRx$ & = & $Rx$ = $Q^Tb$
\end{tabular}

Note that $Q^Tb$ requires only the transpose of the given matrix $Q$.  So
first compute $Q^Tb = \hat b$, then solve the upper traingular system
$Rx=\hat b$ by back substitution. 

\pn(20) The Newton form of the polynomial matching the data  \\
$f(1)=9, f'(1) = 10, f''(1) = 40, f(0) = 7, f'(0) = 0, f(2) = 71$ is:
\vskip .1in

\begin{tabular}{*{7}{c}}
$x_i$ & $f[x]$ & $f[x,x]$ & $f[x,x,x]$ & $f[x,x,x,x]$ & $f[x,x,x,x,x]$ & \\
1& 9&  &  &  &  & \\
 &  &10&  &  &  & \\
1& 9&  &20&  &  & \\
 &  &10&  &12&  & \\
1& 9&  &8 &  & 6& \\
 &  & 2&  & 6&  &2\\
0& 7&  &2 &  & 8& \\
 &  & 0&  &14&  & \\
0& 7&  &16&  &  & \\
 &  &32&  &  &  & \\
2&71&  &  &  &  & \\
 &  &  &  &  &  & 
\end{tabular}

$P(x) = 9 + 10(x-1) + 20(x-1)^2 + 12(x-1)^3 + 6(x-1)^3x + 2(x-1)^3x^2$

\pn(10) Let $f(x)$ be a polynomial of degree 7, $x_0 < x_1 < x_2 
< \cdots < x_6 < x_7, p_6(x)$ the unique polynomial of degree $\leq 6$
interpolating $f(x)$ at $x_0, x_1, \ldots, x_6, $ and $q_6(x)$ the unique
polynomial of degree $leq 6$ interpolating $f(x)$ at $x_1,x_2,\ldots,x_7$.
Explain why: \\
$f(x) = p_7(x) \equiv \frac{(x_0-x)q_6(x)-(x_7-x)p_6(x)}{x_0-x_7}$ \\
identically in $x$. (This is Aitken's interpolation formula.)

Evaluate $p_7(x)$ at each of $x_0$, $x_1$, $\ldots$, $x_7$, and observe
that $p_7(x_i)=f(x_i)$ for $i=0$, 1, \dots, 7.  Therefore $p_7(x)$ is a
polynomial of degree $\le7$ that interpolates $f(x)$ at eight distinct
points.  $f(x)$ is also a polynomial of degree $\le7$ that interpolates
$f(x)$ at eight distinct points. Since the interpolating polynomial
is unique, $p_7(x)=f(x)$.


\end{enumerate}
\end{document}