Mathematics 171 – Numerical Analysis I Lab 2 – Maple Programming, Root-finding September 22, 1998

Background and Goals

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.

Getting Started

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

         cp /home/fac/little/Classes/Numer-98/roots.map roots.map

at the input prompt and press RETURN. (This calls the copy 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:

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.

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.

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).

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 insertion point which is a blinking “I”-shaped marker.

2) You can delete characters with the BackSpace or Del keys.

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.

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 FRE-QUENTLY!!

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.

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.

Lab Work

Open your copy of the file roots.map in a Text Editor window. Also, launch Maple and read 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 read command.

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 × 10^{−7}.) Use the default value for Digits (10 decimal digits). In a text region in your Maple worksheet, compare the efficiency of the two methods on this example.

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 exp(x).) Use both bisection and Newton-Raphson to approximate them to 7 decimal places (i.e. tolerance = .00000005 = .5 × 10^{−7}.) Use the default value for 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?)

Another root-finding method – Fixed Point Iteration.

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:

1) x = (x^{3} + 1)/6 by isolating the x term on one side, 2) x = \sqrt[3]{6x − 1} by isolating the x^{3} term and taking cube roots,

3) x = \frac{−1}{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.

and others. A solution x = p of an equation x = g(x) is an x-value which is taken to itself by the function g. These are called 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

x_{1} = g(x_{0})
x_{2} = g(x_{1})
x_{3} = g(x_{2})
⋮
x_{n+1} = g(x_{n})

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

                      g := x -> (x^3 + 1)/6;

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

                           x[0] := 2.5;
               for i to 10 do x[i] := g(x[i-1]); od;

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

       while i <= 10 do x[i] := g(x[i-1]); i := i + 1; od;

D) Find a rearrangement of the equation from question B for which fixed point iteration converges to the 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!)

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.

Assignment

Individual lab write-ups due in class Tuesday, September 29.