\documentclass[10pt,letterpaper]{article}
\usepackage{graphicx}
\usepackage[colorlinks=true]{hyperref}

\topmargin -0.5in
\textheight 9in
\oddsidemargin=-0.05in
\evensidemargin=-0.05in
\textwidth 6.5in
\pagestyle{empty}

\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand\ben{\begin{enumerate}}
\newcommand\een{\end{enumerate}}
\newcommand\vg{\vspace{2ex}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}
\newcommand{\ie}{{\it i.e.\ }}
\newcommand{\eg}{{\it e.g.\ }}
\newcommand{\eps}{\varepsilon}
\newcommand{\mbf}[1]{{\mathbf #1}}

\begin{document}
\title{Math 56 Compu \& Expt Math, Spring 2014: Homework 1}
\date{\vspace{-2ex} due 10am Thursday April 3rd}
\maketitle

{\em Meta-tasks this week:
i) Get a website if you don't already have one (see Resources);
until then you can email me an archive of your codes.
ii) You should by the 2nd homework be writing up answers using the \LaTeX\
package, which is the ubiquitous, free, professional typesetting package for
mathematicians. See X-hour and Resources page for how to install and use.

I recommend MATLAB/octave or python/SAGE for this
part of the course. (C, fortran, or java
would take much more time to code and debug.)
Certain languages I don't recommend, merely since I don't know them (lisp, java, \ldots)

Please read carefully and try to answer all questions asked!
}

\ben % ---------

\item Asymptotics.
\ben
\item Is $\frac{e^n}{10+ne^n} = O(n^{-1})$ as $n\to\infty$ ?
% This should have been ne^n - 10.   Sign too easy!
%
Prove your answer, i.e.\ if true, exhibit a $C$ and $n_0$ in the
definition of big-O.

\item For what range of $N$ is an algorithm taking $10^6 N \log N$
effort faster than one taking $N^2$ effort?
\een

\item
The following \verb|Matlab| code creates symmetric $n \times n$ matrices with 
elements that are taken from a normal distribution:
\begin{verbatim}
A = randn(n); S = A+A';       % creates n by n symmetric random matrix S
\end{verbatim}
Recall a symmetric matrix is a matrix $S$ such that $S= S^T$ where $S^T$ is the transpose of $S$. Given an arbitrary matrix $A$ we can turn it into a symmetric matrix $S$ by setting $S = A+A^T$. The eigenvalues of a symmetric matrix are always real numbers. On average, how does the maximum eigenvalue of this random symmetric matrix grow as a function of $n$, the dimension of the matrix? Determine this experimentally, giving as explicit a formula as you can.
[Hint: go to large $n$, eg $10^3$, but you don't need {\em many} datapoints at
large $n$]

You will find the \verb|eig| command useful. It will also be helpful to plot the average maximum eigenvalue vs dimension on a log-log scale.


\item Consider the series $y = \sum_{k=1}^\infty k^{-4}$.
\ben
\item Measure the convergence rate of the error $\eps_n = |\hat{y}_n-y|$ for
the $n$-term truncated approximation, by plotting $\eps_n$ vs $n$.
Choose axis types so that the graph appears linear---what is the slope?
State the type/order of convergence.
[Hint: For the exact $y$ either look it up or use the converged $\hat{y}$
after you've done d) below!]
\item How useful is a graph with linear axes here? Why?
\item Prove a big-O bound on effort (i.e.\ $n$)
in terms of desired error $\eps$. [Hint: as in lecture, but then
flip the result.]
%(assume constant effort per flop).
\item Does it matter in which order you do the sum? Give
``converged'' answers for both orderings,
and explain which one is more accurate.
\een

%\newpage


\item Write {\em your own,
documented} function that finds one approximate root of $f(x)$, a
given function  of one variable, by bisection:
given two starting arguments $a<c$
with $f(a)$ and $f(c)$ of opposite sign, set $b=(a+c)/2$ then
replace the list $a,b,c$ by either $a,(a+b)/2,b$, or by $b,(b+c)/2,c$, 
depending on what the sign of $f(b)$ tells you on which side the root lies,
then iterate until you decide when to stop.
Your inputs should be a {\em handle} to a function, the pair $a,c$,
and an error tolerance; the output the root. It should stop and report
if ever the signs don't make sense.
\ben
\item Add a {\em test script} for this function which shows it
finding the root of sine in $[3,4]$, also failing gracefully
here given the input pair $a=0$, $c=\pi$. This could be in the same text file.

%\item Edit your code, if necessary, to reuse function values where possible,
\item State the type of convergence with $n$, the number of iterations,
and give the tightest error bound you can in big-O notation.
What $n$ is needed to find a root to 15-digit accuracy?
What happens in practice if you demand 20 digits?
(These should be answered by thinking, showing working; then you can check with your code.)

\item [BONUS] State one advantage of this method over Newton's method.
\een


\item Visualizing the complex plane.
\ben
\item Compute on paper: i) $\sqrt{2i}$, ii) Im $1/(3+4i)$, iii) $e^{13\pi i/4}$,
iv) $|1-2i|$.
%\item Plot the real and imaginary parts of $e^{inx}$ for $0\le x<2\pi$ and $n=3$, on the same graph.
\item Make a short Matlab
code which makes a 3D height plot of the absolute value of
a given function $f(z)$ on the complex plane $z=x+iy$ for $x,y\in[-2,2]$.
[Hint: at some point you'll want to use {\tt [X,Y] = meshgrid(...);}
then apply your function to all complex grid values {\tt X+1i*Y} at once.]
\item Use your code to make a plot showing the poles
(non-smooth points) in the complex plane for $f(x) = 1/(1+x^2)$.
What happens to the {\em phase} in the neighborhood of each pole?
\item Use the above to predict the convergence rate $r$ of a Taylor series
for this $f$ about $x=1$ (careful), when evaluated at $x = 0.3$.
[Don't try to generate the series!]
\een


\item Give an exact formula, in terms of $\beta$ and $t$,
for the smallest positive integer $n$ that
does not belong to the floating-point system $\mbf{F}$, and compute $n$
for IEEE double-precision. Give one line of code, and its output,
which demonstrates this is indeed the case.
%[NLA Ex 13.2]


\item Let {\tt x} be any positive number (also try a really large one!).
What should the following Matlab code do mathematically, and what does
it do in practice? Explain why.

\verb& for i=1:60, x = sqrt(x); end, for i=1:60, x = x^2; end &


\een % -------------

\end{document}

