\documentstyle[12pt]{article}
\begin{document}
\begin{center}
%{\bf NOTE:} office hours instructor: MC6065 x4597 Tues. 2-3PM, Thurs. 1-2PM.\\
%~~~~~~~~~~office hours TA ???\\

{\large\bf C\&O 367 \\ 
Assignment 1 
}
\end{center}
\begin{flushleft}
{\large  Due on Tuesday, Sept. 21, 1993.   Instructor H. Wolkowicz
}
\end{flushleft}

\begin{enumerate}
\item
Pretend you have a computer with base $10$ and precision $4$ that
truncates after each arithmetic operation; for example, the sum of
$24.57 + 128.3 = 152.87$ becomes $152.8$. What are the results when 
$128.3, 24.47, 3.163,$ and $0.4825$ are added in
ascending order and descending order in this machine? How
do these compare with the correct ("infinite-precision") result?
What does this show you about adding sequences of numbers
on the computer?

\item
Now consider the quadratic equation
$$x^2 -100x +1 =0.$$
Use the formula for the solution of a quadratic equation to find the roots
of this equation. (Assume again that you have the same computer as above,
but with precision 5.)
How many correct digits do you get? Why? Can you improve the accuracy by
changing the algorithm? (Recall that the product of the
two roots of a quadratic
equals the ratio of the last and first coefficient, i.e. $x_1x_2=c/a,$
where here $a,c$ both equal $1$.)

\item
Consider the following program. (You may run it using e.g. matlab.)
\[
\begin{array}{rcl}
h & = & 1/2\\
x & = & 2/3-h\\
y & = & 3/5-h\\
e & = & (x+x+x)-h\\
f & = & (y+y+y+y+y)-h\\
q & = & f/e
\end{array}
\]
Explain the value of $q$ on the computer and on a calculator.

\item
Write a MATLAB program to implement Newton's method for root finding.
Apply it to the function
\[
f(x)=(x-1)^2 (x-4)
\]
starting at the points:
\begin{enumerate}
\item
$x=3.95$
\item
$x=0.95$
\end{enumerate}
Compare your results with those you obtain using the MATLAB optimization
toolkit. 

\item
Prove that Newton's method converges linearly to a multiple root, i.e. a
root where $f(x^*)=f^{\prime}(x^*)=0.$ (Assume that you obtain an
infinite sequence of iterations for Newton's method.)

\item
Classify the convergence of the following sequences:
\begin{enumerate}
\item
\[
x_n=e^{(-n^2)}
\]
\item
\[
1~,~0~,~1/2~,~0~,~1/4~,~0~,~1/8
\]
\item
\[
x_n=\frac{1}{n}a^n, ~~(0<a<1)
\]
\item
\[
x_n=a^{\log n} ~~(0<a<1)
\]
\item
\[
x_n=a^{n \log n} ~~(0<a<1)
\]
\end{enumerate}

\item
Write, debug, and test a program for solving one nonlinear equation in
one unknown. It should be safeguarded using Newton's method or the
secant method combined with bisection or backtracking. Run your program
on:
\begin{enumerate}
\item
\[
f(x)=\sin x - \cos 2x, ~x_0=1
\]
\item
\[
f(x)=x^3-7x^2+11x-5, ~x_0=1
\]
\item
\[
f(x)=\sin x - \cos x, ~x_0=1
\]
\end{enumerate}
Check your results by using the matlab optimization toolkit.
Then use the program to find the point $c>0$ from which Newton's method
for $\arctan x =0$ will cycle.

\item
Prove the following:
Let $f \in C^1(D)$ for an open interval $D$, and let $z \in D$. If 
$f^{prime}(z)
\neq 0$, then for any $s$ with $f^{\prime}(z) \cdot s < 0$, there is a
constant $t>0$ for which $f(z+\lambda s) < f(z)$, for every $\lambda
\in (0,t)$.

\item
Prove the following:
Let $f \in C^2(D)$ for an open interval $D$, and let $x^* \in D$ for
which $f(x^*)=0$ and $f^{\prime}(x^*)>0$. Then there is some open
subinterval $D^{\prime} \subset D$ for which $x^* \in D^{\prime}$ and
$f(x)>f(x^*)$ for any other $x \in D^{\prime}$.


\end{enumerate}
\end{document}