\magnification=\magstep1
\centerline{Mathematics 171 -- Numerical Analysis I}
\centerline{Lab 2 -- Maple Programming, Root-finding}
\centerline{September 22, 1998}
\bigskip
\noindent
{\bf Background and Goals}
\bigskip
Last week in class we introduced the basics of the Maple programming
language and used it to code a procedure for the bisection method.
We also introduced the Newton-Raphson method and saw a Maple procedure
implementing that method.  Today, we want to continue our study, introduce
another root-finding method, and develop a Maple procedure for it
as well.
\bigskip
\noindent
{\bf Getting Started}
\bigskip
The code for the bisection method and the Newton-Raphson method that I 
distributed is in a file in my folder for this class.  You should
begin by copying it into your directory.  In a Terminal window,
enter 
\medskip
\centerline{\tt cp /home/fac/little/Classes/Numer-98/roots.map roots.map}
\medskip
\noindent
at the input prompt and press RETURN.
(This calls the copy {\tt roots.map} in your directory as well.)
We will be modifying and adding a new procedure to this file today, using
the OpenWindows Text Editor.  You can launch this program to edit a
text file in several different ways, including:
\bigskip
\item{1)} Select Programs/Text Editor from the Workspace Menu (click
right mouse button on blue workspace background).  Then use FILE/Open
to read in the file to be edited.
\item{2)} To work on an existing text file, you can also open a File Manager
window, find the icon for the file you want in the appropriate
folder (the icon should
look like a page of text), and double click the 
left mouse button to open it in the Text Editor.
\bigskip
\noindent
Text Editor operates in a fashion similar to almost all editors (like
the editor in MS Word, the message compose window in Groupwise,
or the Turbo Pascal or C++ editor, for example).  
\bigskip
\item{1)} If the border of the Text Editor
is highlighted, then typing from the keyboard inserts text into 
the file buffer at the position of the {\it insertion point\/}
which is a blinking ``I''-shaped marker.  
\item{2)} You can delete characters with the BackSpace or Del keys.
\item{3)} You can move around within the file using the arrow,
Page Up, Page Down, and other keys,
or by placing the cursor at the location you want to move to and
clicking the left mouse button.
\item{4)}  The commands for opening new text files, saving work, printing,
etc. are obtained via the FILE pull-down menu.  
A word to the wise: SAVE YOUR WORK FREQUENTLY!!
\item{5)} More drasting editing commands like Copy/Cut/Paste, Search/Replace,
Spell Check, etc. are obtained from the EDIT pull-down menu.
Copying a block of text from one place in a file to another is 
simple -- you just place the cursor at the start of the block,
hold down the left mouse button and drag it to the end of the block.
(This will highlight the block with a black background.)  Then
using the EDIT pull-down menu, select Copy.  Move the insertion
point to the place where you want the copy to go, then select 
Paste from the EDIT pull-down menu.
\bigskip
Launch a Text Editor from the Workspace Menu (this opens a new, blank
file buffer) and experiment by entering a few lines of text, changing
them, etc.  
\bigskip
\noindent
{\bf Lab Work}
\bigskip
Open your copy of the file {\tt roots.map} in a Text Editor window.  Also,
launch Maple and read {\tt roots.map} into 
your Maple session.  Note: If you launch Maple from the folder (directory) 
where the file is, you do not have to enter the full path to the 
file in the {\tt read} command.

\bigskip
\item{A)}  The equation
$$x^3 - 6x + 1 = 0$$
has root in the interval $[2,3]$.  Use both the bisection and the
Newton-Raphson procedures to approximate it to 7 decimal places (i.e.
tolerance = $.00000005 = .5 \times 10^{-7}$.)  Use the default
value for {\tt Digits} (10 decimal digits).  In a text region 
in your Maple worksheet, compare the efficiency of the two methods on 
this example.   
\item{B)}  Find all roots $x > 0$ of the equation
$$e^{x/2} - x^3/12 - 3x = 0.$$
(Recall that the exponential function in Maple is called {\tt exp(x)}.)
Use both bisection and Newton-Raphson
to approximate them to 7 decimal places (i.e.
tolerance = $.00000005 = .5 \times 10^{-7}$.)  Use the default
value for {\tt Digits} (10 decimal digits).  In a text region 
in your Maple worksheet, compare the efficiency of the two methods on 
this example. (You will need to know 
where to look for the roots -- how can Maple help you with that?)

\bigskip
\noindent
{\it Another root-finding method -- Fixed Point Iteration}.
\bigskip
Given an equation $f(x) = 0$, it is usually possible to rearrange it
algebraically in many different ways to an equation of the form
$$x = g(x)$$
For example, the equation $x^3 - 6x + 1 = 0$ from question A can
be rearranged to the forms:
\bigskip
\item{1)}  $x = (x^3+1)/6$ by isolating the $x$ term on one side,
\item{2)}  $x = {\root 3\of {6x - 1}}$ by isolating the $x^3$ term 
and taking cube roots,
\item{3)}  $x = {-1\over x^2 - 6}$ by taking the 1 to the right 
side of the equation, factoring an $x$ out of the remaining terms 
on the left, and dividing both sides by $x^2 - 6$
to isolate the single $x$ on the left.
\bigskip
\noindent
and others.  A solution $x = p$ of an equation $x = g(x)$ is an $x$-value
which is {\it taken to itself} by the function $g$.  These are called
{\it fixed points} of $g$:  $g(p) = p$.  In some cases, starting 
from $x_0$ ``suitably close to'' $p$, we can produce a sequence converging
to the fixed point by iterating the function $g$.  We construct
$$\eqalign{x_1 &= g(x_0)\cr
           x_2 &= g(x_1)\cr
           x_3 &= g(x_2)\cr
               &\vdots\cr
           x_{n+1} &= g(x_n) \cr}$$

\bigskip
\item{C)}  Starting from $x_0 = 2.5$, which (if any) of the three rearranged 
forms of the equation from A above seem to give sequences converging
to the root you found in A?  Compute at least up through $x_5$ in each case
(more if you need to to see a pattern),
using Maple to do all the calculations.  Start
by defining $g$ as a function.  For example, form 1 would be
\medskip
\centerline{\tt g := x -> (x\^{}3 + 1)/6;}
\medskip
\noindent
Then iterate, storing each computed $x_n$ in a variable so you can
use it in the computation of $x_{n+1}$ in the next step.  You can ``automate''
the procedure using a loop like this also:  First assign 
\medskip
\centerline{\tt x[0] := 2.5;}
\medskip
\centerline{\tt for i to 10 do x[i] := g(x[i-1]); od;}
\medskip
\noindent
This starts from $i = 1$ and $i$ increases in steps of $1$ until
$i = 10$ is reached.  The loop stops after $x[10]$ is computed.  It
is equivalent to assigning $i := 1$, then executing
\medskip
\centerline{\tt while i $<=$ 10 do x[i] := g(x[i-1]); i := i + 1; od;}


\bigskip
\item{D)}  Find a rearrangement of the equation from question B
for which fixed point iteration converges to the {\it largest}
positive root you found in that question, for suitable $x_0$.  (In
your final worksheet, do not include any rearrangements that did not
``work'', just one that does!)

\bigskip
\item{E)}  Using the Newton-Raphson procedure as a model, develop
a Maple procedure that takes as input a function, a starting value
x0, a tolerance, and a max number of iterations, and performs
fixed point iteration until either the tolerance is reached, or
the maximum number of iterations is exceeded.  Include it in your
copy of the roots.map file, and turn a printout of it in with your Maple
worksheet. Test it by repeating 
the computations from C and D.  
\bigskip
\noindent
{\bf Assignment}
\bigskip
Individual lab write-ups due in class Tuesday, September 29.

\bye






