\documentclass{article} \begin{document} % FIRST EXAM \centerline{\bf CS/MATH 3414 FIRST EXAM (OldExam1)} \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 $-3.25$ (express your answer in hexadecimal). \begin{enumerate} \item Translate number to binary: $-(11.01)_2$ \item Put into scientific notation: $-(1.101)_2 \times 2^1$ \\ True exponent: $e = 1$ \item Figure biased exponent: \\ exponent bias for IEEE 64-bit is 3FF \\ \begin{tabular}{*{4}{c}} 0011 & 1111 & 1111 & (3FF)\\ & & 0001 & (e)\\ \hline 0100 & 0000 & 0000 & (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 & (1 && 100 0000 0000 && 1010 0000 $\cdots$ 0000 $)_2$ & \\ \hline &&& (C00A 0000 0000 0000 $)_{16}$ &&& \end{tabular}\\ (Since there are 64-bits there should be $\frac{64}{4} = 16$ hexidecimal digits total.) \end{enumerate} \pn(20) Let $$A=\pmatrix{10^{-10}&0\cr 0&10^{-10}\cr},\qquad B=\pmatrix{10^{10}&0\cr 0&10^{-10}\cr}.$$ det $A=$\urule, det $B=$\urule, $\mn A=$\urule, $\mn B=$\urule, \lfil $\mn{A^{-1}}=$\urule, $\mn{B^{-1}}=$\urule, cond $A=$\urule, cond $B=$\urule. Which matrices are ill conditioned? \urule \vskip .2in Remember for a matrix $A=\pmatrix{a & b \cr c & d\cr}$: \\ $\det{A} = ad-bc$, $A^{-1} = \pmatrix{\frac{d}{det(A)} & \frac{-b}{det(A)} \cr \frac{-c}{det A} & \frac{a}{det(A)}\cr}$, $\mn A = \hbox{max }_i \sum_{j=1}^n|A_{ij}|$ (max row sum), $||A||_1 = \hbox{max }_j \sum_{i=1}^n|A_{ij}|$ (max column sum), cond $A$ = $||A|| \times ||A^{-1}||$ \\ \vskip .1in \begin{enumerate} \item $det A = 10^{-10} \times 10^{-10} = 10^{-20}$ \item $det B = 10^{-10} \times 10^{10} = 1$ \item $||A||_\infty = 10^{-10}$ \item $||B||_\infty = 10^{10}$ \item $A^{-1} = \pmatrix{\frac{10^{-10}}{10^{-20}} & 0 \cr 0 & \frac{10^{-10}}{10^{-20}}\cr} = \pmatrix{10^{10} & 0 \cr 0 & 10^{10}\cr}$ \item $B^{-1} = \pmatrix{\frac{10^{-10}}{1} & 0 \cr 0 & \frac{10^{10}}{1}\cr} = \pmatrix{10^{-10} & 0 \cr 0 & 10^{10}\cr}$ \item $\mn{A^{-1}} = 10^{10}$ \item $\mn{B^{-1}} = 10^{10}$ \item $\hbox{cond }A = ||A|| \times ||A^{-1}|| = 10^{-10} \times 10^{10} = 10^0 = 1$ \item $\hbox{cond }B = ||B|| \times ||B^{-1}|| = 10^{10} \times 10^{10} = 10^{20} $ \item B is ill conditioned (has a high condition number). \end{enumerate} \pn(10) Let $Ax=b$, $\n{A\hat x-b}=10^{-10}$, $\n A=10^4$, $\n{A^{-1}}=10^5$, $\n b=10$. Give a sharp upper bound for $\n{\hat x-x}/\n x$. $${\n{\hat x-x}\over\n x}\le\urule.$$ \vskip .5in Note that $r = b-A\hat x$, \\ $\hbox{cond }A = \n{A} \times \n{A^{-1}} = 10^5 \times 10^4 = 10^9$\\ \begin{tabular}{*{3}{l}} $\frac{\n{\hat x-x}}{\n x}$ & $\leq$ & $\hbox{cond }A \times \frac{\n{r}}{\n{b}}$ \\ & $=$ & $10^9 \times \frac{10^{-10}}{10}$ \\ & $=$ & $10^9 \times 10^{-11}$ \\ & $=$ & $10^{-2}$ \end{tabular} (Ref: Notes - Linear Sys. of Eqns. pg. 13) \pn(20) Compute the Cholesky factorization $A=GG^t$, where $G$ is a lower triangular matrix with positive diagonal elements, of $$A= \pmatrix{4&0&-2\cr 0&1&1\cr -2&1&11\cr}.\hskip 40pt G={?}\hskip2in$$ \vskip .5in $A = \pmatrix{4&0&-2\cr 0&1&1\cr -2&1&11\cr} = \pmatrix{g_{11}&0&0\cr g_{21}&g_{22}&0\cr g_{31}&g_{32}&g_{33}\cr} \pmatrix{g_{11}&g_{21}&g_{31}\cr 0&g_{22}&g_{32}\cr 0&0&g_{33}\cr}$ \\ Formula from notes: \\ $$\displaylines {\hbox {for } k = 1,\ldots, n\cr u_{km} = a_{km} - \sum^{k-1}_{j=1}\ \ell_{kj} u_{jm}, \quad m = k,\ldots, n\cr \ell_{pk} = \left(a_{pk} - \sum^{k-1}_{j=1} \ell_{pj} u_{jk}\right)\Big/ u_{kk},\quad p = k + 1, \ldots, n\cr}$$\\ Resulting answer: \\ $A = \pmatrix{4&0&-2\cr 0&1&1\cr -2&1&11\cr} = \pmatrix{2&0&0\cr 0&1&0\cr -1&1&3\cr} \pmatrix{2&0&-1\cr 0&1&1\cr 0&0&3\cr}$ (Ref: HW\#4 Notes on Cholesky decomposition formulas or Cheney text pg 326) \pn(25) The Newton form of the polynomial matching the data $f(1)=8$, $f'(1)=12$, $f''(1)=20$, $f(0)=0$, $f'(0)=7$, $f(2)=46$ is $$\displaylines{P(x)=?}$$\vskip .1in \begin{tabular}{*{7}{c}} $x_i$ & $f[x]$ & $f[x,x]$ & $f[x,x,x]$ & & & \\ 1 & 8 & & & & & \\ & & $f[1,1]=12$ & & & & \\ 1 & 8 & & $\frac{f''(1)}{2!} = \frac{20}{2} = 10$ & & & \\ & & 12 & & $\frac{4-10}{0-1}=6$& & \\ 1 & 8 & & $\frac{8-12}{0-1} = 4$& & $\frac{3-6}{0-1} = 3$ & \\ & & $\frac{0-8}{0-1}=8$& & $\frac{1-4}{0-1} = 3$ & & $\frac{4-3}{2-1} =1$\\ 0 & 0 & & $\frac{7-8}{0-1} = 1$& & $\frac{7-3}{2-1}=4$ & \\ & & 7& & $\frac{8-1}{2-1}=7$& & \\ 0 & 0 & &$\frac{23-7}{2-0}=8$ & & & \\ & & $\frac{46-0}{2-0} = 23$& & & & \\ 2 & 46 & & & & & \\ & & & & & & \ \end{tabular} $p(x) = 8 + 12(x-1) + 10(x-1)^2 + 6(x-1)^3 + 3x(x-1)^3 + 1x^2(x-1)^3 $ \\ (Ref: Notes - Polynomial Interpolation, pg. 14) \newpage \pn(5) The piecewise linear interpolant $\ell(x)$ to $f(x)$ at $x_1< x_2<\cdots