\documentclass[12pt]{article}
\usepackage{times}

\usepackage{fancyheadings}
\pagestyle{fancy}
\textwidth=6.5in
\oddsidemargin=0in
\setlength{\headwidth}{\textwidth} % This shouldn't be needed.  ??
\lhead{\footnotesize CS 1713, Assignment 5, Spring 1998, \today}
\rhead{\footnotesize Page \thepage~~of~~\pageref{'thatsall'}}
\lfoot{} \chead{} \cfoot{} \rfoot{}

\newcommand{\ttb}{\fontfamily{pcr}\fontseries{b}\fontshape{n}%
  \fontsize{11}{13pt}\selectfont}  %Courier bold at 11pt
\newcommand{\longst}{\rule[-3mm]{0mm}{2mm}}

\newcommand{\st}{\rule[-.8mm]{0mm}{2mm}}
\newcommand{\mywidth}{6.5in}
\newcommand{\myrightmar}{0.2in}
\newcommand{\myleftmar}{0.4in}
\newcommand{\myparsep}{2mm}
\newcommand{\mynegvertsp}{-0.35in}
\newcommand{\outerbaselinesep}{15pt}
\newcommand{\mybaselinesep}{15pt}
\newcommand{\myvspace}{-0.2in}
\textwidth \mywidth
\parindent 10mm
\parskip 3mm
\columnsep=6mm %%%10mm
\topmargin=0in
\textheight=8in
\oddsidemargin=0in
\evensidemargin=0in

\begin{document}
\sloppy

\begin{center}
%{\large\sf The University of Texas as San Antonio \\
%Division of Mathematics, Computer Science, and Statistics \\
%San Antonio, Texas  78285} \\
%
%\vspace{0.4in}

{\large\bf
   CS 1713, Introduction to Computer Science\\
    Assignment 5, Spring 1998\longst } \\
 {\large\it  Root of an Equation \longst \\
  Due February 26, 1998}
\end{center}

\vspace{-0.1in}
The objective of this programming assignment is to find
a real number $x$ satisfying $\cos(x) = x$, where
$0 \leq x \leq \pi/2$.
(Draw the graphs of the line $y = x$ and the parabola
$y = \cos(x)$ to see that they cross at a point with $x$-coordinate
between $0$ and $\pi/2$, and this is the root we want.)

You are to try out {\em two different} root-finding
methods for finding this $x$ value,
applying them to the equation $f(x) = \cos(x) - x$.
(A root is a place where $f(x) = 0$, or $\cos(x) - x = 0$,
or $\cos(x) = x$.)

\noindent {\bf 1. Newton's method.}
The first approach will use {\em Newton's
method}, which is taught in calculus courses.
(Don't worry if you haven't had calculus, because you just
need to use the formulas given below and don't need to
know calculus.)
For this method,
one also needs the derivative of $f$,
$f'(x) = -\sin(x) - 1$.  Newton's method
starts with a guess at the answer, call it $x_0$,
and produces a new, hopefully better guess $x_1$ using
the ``magic'' formula

\vspace{-0.2in}
\begin{displaymath}
 x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}
\end{displaymath}

\vspace{-0.2in}
Replace the old guess with the new one and repeat
in a loop until the old guess and the new guess are within
some small value $\epsilon$ of one another.
(You should ask if the absolute value of their difference is
less than $\epsilon$, using the function {\tt fabs}.)
In this assignment we will take $\epsilon$ to be $0.000000000001$ .
You should use the new
guess as your final answer.
Your program must use two C functions named
``{\tt f}'' and ``{\tt fprime}'' as shown below, so that
the magic formula actually uses these functions.
Finding the root must be done with a separate C
function named ``{\tt newton}'' with two input parameters, the
initial guess $x_0$, and the tolerance $\epsilon$.
Thus the header for this function should look like:

    \hspace{0.3in} {\tt void newton(double x0, double epsilon)}

\noindent Use $x_0 = 0$ for the initial guess.

\vspace{-0.2in}
{\footnotesize
\begin{verbatim}
        double f(double x)
        {
           return cos(x) - x;
        }
     
        double fprime(double x)
        {
           return -sin(x) - 1.0;
        }
\end{verbatim}
} %end of small

\noindent {\bf 2. Bisection method.}
The second approach will use the
{\em bisection method}.  Here one starts with two values
$x_1$ and $x_2$  (with $x_1 < x_2$) for which $f(x_1)$ and $f(x_2)$
have opposite signs (i.e., one is positive and
the other is negative, or $f(x_1) * f(x_2) < 0$).
If $f$ is a continuous function
(no jumps or breaks), then there must be an $x$
between $x_1$ and $x_2$ for which $f(x) = 0$.
To get closer to that value, let $x_{mid} = 
(x_1 + x_2)/2$, the midpoint.
Consider $f(x_{mid})$ and replace either $x_1$ or $x_2$
by $x_{mid}$, so that after the replacement we
still have $f(x_1)$ and $f(x_2)$ with opposite signs,
but now $x_1$ and $x_2$ are half as far apart as they
were before.
Repeat this process until the distance between $x_1$ and
$x_2$ is less than $\epsilon$, again taken to be $0.000000000001$
in this assignment.
Your final answer should be $x_{mid}$.
Again you must use a C function named ``{\tt f}''.
Finding the root must be done with a separate C
function named ``{\tt bisection}'' with three input
parameters, the initial numbers $x_1$ and $x_2$ and the
tolerance $\epsilon$.
This time the header for the function should look like:

    \hspace{0.3in} {\tt void bisection(double x1, double x2, double epsilon)}


\noindent Use the numbers $0$ and $\pi/2$
as the initial values.

\noindent{\bf Directions for both approaches.}
Your program should first read the value $0.000000000001$ for the
number $\epsilon$ used to determine how close an
approximation to the root one gets.
(If you wish, you can instead give $\epsilon$ its value using a constant
or a {\tt \#define}.)
Then print ``{\tt Tolerance value:}'' and the
value for $\epsilon$.
For each of the methods the program must {\em count} the iterations
and must terminate the loop
in case the iteration count gets larger than 50.
First you should print ``{\tt Newton's method:}''
and a short list of approximate values obtained at each iteration,
ending with a final approximation.
Next print ``{\tt Bisection method}''
and a somewhat longer list of {\em pairs} of values obtained
at each stage of
the second method, again ending with the final
approximation.
Notice that you should get (almost) the same answer by
the two methods.
All real numbers must be printed out with 15 digits to the
right of the decimal place.
Of course you must use a makefile and a separate directory
for the files for this assignment.

\noindent{\bf Outline of the source file.}

\vspace{-0.2in}
{\footnotesize
\begin{verbatim}
        /* #includes, #define for PI */
        /* function prototypes: f, fprime, newton, bisection */
        void main(void)
        {
             double epsilon;
             /* scanf for epsilon */
             printf("Newton's method\n");"
             newton(0.0, epsilon);
             printf("Bisection method\n");
             bisection(0.0, pi/2.0, epsilon);
             exit(0);
        }
        /* function definitions */
\end{verbatim}
} % end of small


\label{'thatsall'}
\end{document}