\documentclass[]{article}
\textwidth 6.4in
\textheight 8.7in
\oddsidemargin -0.3in
\evensidemargin -0.3in
\usepackage{latexsym}
\usepackage{multicol}
%\usepackage{epsfig}
\usepackage{latexsym}
 \usepackage{epsfrag}
\usepackage{multicol}
\usepackage{fancybox}

\topmargin -.25in

\input{zmacros}
\def\be{\begin{enumerate}}
\def\ee{\end{enumerate}}
%\newcommand{\vthin}{\vskip 5pt}


\pagestyle{empty}
\begin{document}
\hfill\vbox{\hbox{MA/CSC 580, \ Homework \#1}
\hbox{\bf Due Wednesday,  September12, 2018}}
\vskip .2in
\baselineskip 14pt

\vthin

{\bf Please Read the Homework Guidelines Carefully.}

\be
\vthin


%\item Use a separate page to complete the class questionnaire. You can also  e-mail me your answers.

\vthin
\item
Let $x=0.d_1 d_2 \cdots d_n d_{n+1}\cdots \beta^b$, $d_1\neq 0$, $0\le d_i
\le \beta-1$.
We can use the chopping method to express $x$ as a floating number
\eqmno
fl_c(x) = 0.d_1 d_2 \cdots d_n\beta^b
\enmno
Find upper bounds of the absolute and relative errors of $fl_c(x)$
approximating $x$. Compare the results with the results obtained from
the rounding-off approach. 

\vthin
\item Let $F$ be a computer number system of 64 bits. Find the following
\be
\item The largest and smallest number.
\item The smallest normalized positive number.
\item The smallest positive number.
\item Give examples of {\em underflow} and {\em overflow}.
\item The machine precision.
\item Find upper bounds of the absolute and
relative errors of $fl_c(x)$ approximating $x$ using the rounding approach.
\ee
Note that the specifics may differ slightly with different computers and
compilers.




\vthin
\item Assume we use a computer to evaluate the
following expressions
\eqmno
(a) \;\; p = xyz, \qquad (b)\;\; s = x + y+ z,
\enmno
where $x$, $y$, and $z$ are real numbers. Find upper bounds of absolute
and relative errors. Assume all the numbers involved are in the range of the
computer number system. Analyze the error bounds. 

({\bf HINT:} You can set $x_1=fl(x)$, $y_1=fl(y)$, $z_1=fl(z)$, $p_1=fl(x_1
y_1)$, $p_c = fl(p_1 z_1)$ is the computed product of $x$, $y$, and $z$.
({\bf Note:} Pay attention to the upper bounds and
absolute values, \eg, $\delta_5 \le 5 \epsilon$ is wrong, it should be
$|\delta_5 | \le 5 \epsilon$.)

\vthin
\vthin
\item Design an algorithm (in pseudo-code form) to evaluate the following
\be
\item $\log (1+x)/x$ in the interval $[-0.5, \; 0.5]$.
\item $ b - \sqrt{b^2 - \delta}$, where $b$ and $\delta$ are two
parameters with $b^2-\delta\ge 0$.
\item $\grad \phi(x)/|\grad \phi(x)|$ where $\phi(x,y)$ is a scalar function of $x$ and $y$.
\ee
You need to consider all possible scenarios.


\item Which of the following two formulas in computing $\pi$ is better?
\eqmno
&& \pi = 4 \lp 1 - \fr{1}{3} + \fr{1}{5} - \fr{1}{7} + \fr{1}{9} + \cdots
\rp \\ \eqsp
&& \pi = 6 \lp 0.5 + \fr{0.5^3}{2\cdot 3} + \fr{3 (0.5)^5}{2 \cdot 4 \cdot 5}
+ \fr{3 \cdot 5 (0.5)^7}{2 \cdot 4 \cdot 6\cdot 7} + \cdots \rp.
\enmno
How many terms should be chosen such that the error is less than $10^{-6}$?
You can write a short Matlab code to compare. Consider both accuracy and
speed.
\vthin
\vthin
\item We can use the following three formulas to approximate the first
derivative of a function $f(x)$ at $x_0$.
\eqmno
f'(x_0) &\approx& \fr{f(x_0+h)-f(x_0)}{h}\\
f'(x_0) &\approx& \fr{f(x_0+h)-f(x_0-h)}{2h} \\
f'(x_0) &\approx& \fr{f(x_0)-f(x_0-h)}{h} 
\enmno 
When we use
computers to find an approximation of a derivative (used in finite
difference (FD) method,
optimization, and many areas, we need to balance the errors from
the algorithm (truncation error) and round-off errors (from
computers). 
\be 
\item Which formula is the most accurate in theory?
{\em Hint:} Find the absolute error using the Taylor expansion at
$x=x_0$: $f(x_0\pm h)=f(x_0)\pm  f'(x_0) h +  f''(x_0)h^2/2 \pm f'''(x_0)
h^3/6 + O(h^4)$.

\item Write a program to compute the derivative with
\bi
\item $f(x)=x^2$, $x_0=1.8$. 
 \item $f(x)=e^x \sin x$, $x_0=0.55$.
\ei 
\emph{\textbf{Plot}} the errors versus $h$ using $\log$-$\log$
plot with labels and legends if necessary. In the plot, $h$ should
range from $0.1$ to the order of machine constant ($10^{-16}$)
with $h$ being cut by half each time (\ie, $h=0.1$, $h=0.1/2$,
$h=0.1/2^2$, $h=0.1/2^3$, $\cdots$, until $h\le 10^{-16}$.)

\emph{\textbf{Hint:}} You need to find the true derivative (analytic)
values in order to compute and plot the errors.
\vthin

\emph{\textbf{Tabulate}} the absolute and relative errors
corresponding to $h=0.1$, $0.1/2$, $0.1/4$, $0.1/8$, and $0.1/16$
(that is, difference choices of $h$ compared with that used in the
plots). The ratio (should be around $2$ or $4$) is defined as the
quotient of two consecutive errors. \emph{\textbf{Analyze and explain}}
your plots
and tables. What is the best $h$ for each case with and without
round-off errors? 
\ee

\bc
\begin{tabular}{||c||c|c||c|c||c|c||} \hline \hline
$1/h$ & error (a)  & ratio & error (b)& ratio & error (c)& ratio \\ \hline
$10$ & & -- & & --& & --\\ \hline
$20$ & & & & & & \\ \hline
$40$ & & & & & & \\ \hline
$80$ & & & & & & \\ \hline
$160$ & & & & & &\\ \hline
\end{tabular}
\ec

The ratio is defined as, for example 
\eqmno
 ratio = \fr{ |\mbox{error for $n=10$}| }{ |\mbox{error for $n=20$}|}.
\enmno

\vthin

\item {\bf Mini-project:} Find the relation between relative errors and significant digits. 
\ee

\ignore{ 
{\bf Note:} Please submit any \emph{\textbf{ computer code(s)}} through \
http://courses.ncsu.edu/ma580/   \
or   \\
http://courses.ncsu.edu/csc580/ \ depending on the course that you
registeredi to save paper. But you need to attach your 
\emph{\textbf{plots, tables, 
arranged outputs, analysis}} along with your homework.  }

\end{document}
