Project 3: Finding roots

Due Dates

Thursday, March 29, at 6:00 PM: Pseudocode outline for bisection method
Monday, April 2, at noon: The finished Scilab code and analysis

Your job in this project: write a set of routines for finding the root of a function, and compare them in action.

You may not use Scilab's built-in functions for finding roots -- instead, please implement two different algorithms yourself. You will need to write two functions for this project, one for each of the following methods:

bisection
Newton/Raphson

You'll need to create two different Scilab source code files this week:

root_bisect.sci
root_newton.sci

Your two functions should look like this:

 function root = root_bisect(start_range, end_range, epsilon, func)

 function root = root_newton(start_range, end_range, epsilon, func, deriv)

where

      root          is the output argument.  The function should return
                        a single floating point value, which is a 
                        root of the given 'function'

      start_range   is the start of the interval in which to search

      end_range     is the end of the interval in which to search

      epsilon       is the fractional relative error to use as a 
                        termination criterion

      func          is the name of a function to evalulate

      deriv         is the name of another routine, which is the
                        derivative of the 'func'
                        (this is needed only for Newton's method)

Use each of the 2 methods on the following problems. Note that the trigonometric functions take arguments in RADIANS, not degrees.

find a root of (x^3 - 9x^2 + 70x - 70) on the interval [-30, 70]
find a root of cos(x/5) on the interval [-10, 10]
find a root of (x^10) - 2 on the interval [0, 2]
find a root of 3*sin(x) - e^(-1/x^2) on the interval [1, 5]

Please note that the goal is to find roots which lie within the given intervals. Beware Newton's method: even if you start somewhere inside the interval, the method may pick a next guess which is somewhere outside the interval...

In each case, make a table which shows

the root found
the number of iterations required
the computational time required

Use the termination criterion

     fractional estimated error in root value (epsilon) = 10^(-6)

Nota Bene

You should include a limit on the maximum number of iterations which any method can use; try setting a limit of 1,000,000 iterations. If, after that number of iterations, the method doesn't converge within the termination criterion, cause the function to call the error routine.
Make sure that you don't divide by zero.
Your functions will also be evaluated on their performance in finding the roots of OTHER functions, not listed above. You might want to do some extra tests yourself.

Bells and Whistles

Implement the "false position" method. Compare its performance to the bisection method.
Write a "driver" function called find_root which takes 4 input arguments:
1. start_range
2. end_range
3. function
4. first derivative of function
uses each of the 2 methods (bisection and Newton's) to calculate the root, then prints out a pretty table comparing the results.
Write a "driver" function called plot_root which uses Scilab graphics to draw successive stages in the determination of a root by either the bisection or Newton's method. Your program should draw one step, then wait for the user to type y before drawing the next step.

This page maintained by Michael Richmond. Last modified March 27, 2007.