Due November 17, 2006
NOTE1: YOU MUST USE THE VARIABLE NAMES SPECIFIED IN THE ASSIGNMENT, failure to
do so will result in deduction of points.
For each part of the assignment
:· Make a test plan for the problem.
· Write a refined algorithm based
on the summary algorithm below
· Translate the algorithm to C code.
· Test the C Code
· Submit the test plan for each function and for the main program. and your tested C Code (including main program and all functions in a single file polyroot.c)
PART 1: (14 points)
Write a function to evaluate a polynomial of order N where N>0.
Consider
a polynomial of the form result = ANXN + AN-1-XN-1+
AN-2-XN-2 + ... +A1X + A0. When you
evaluate the polynomial you calculate the value of result given a value of X.
Think of the polynomial in the following form to simplify the evaluation of the
polynomial (... (((ANX +AN-1)X+AN-2)X
+ AN-3 ... ))+A0. You must evaluate the polynomial in this
for using Horner’s algorithm, which is summarized below, you may not use
the pow function in your function..The prototype of the function should be
double PolyEval(double Coefs[ ], double X, int polynomialOrder);
Note that the Coefficients are being stored in a 1-dimensional array and that
array is being passed into the function. Element 0 of the array contains the
coefficient of the constant term, element 1 the coefficient of the term in X,
element 2 the coefficient of the term in X2, and so on. Your
function should work for polynomials of arbitrary order > 0. The order of
the polynomial being evaluated is also passed into the function as the value of
polynomialOrder, the size of the array of
coefficients passed into the function must be at least polynomialOrder+1. Use
Horner’s algorithm (outlined below) to evaluate the polynomial. You may
not use the pow( ) function within your polynomial evaluation function. The
value of the polynomial evaluated at X must be returned as the value of the
function.
Write a main program to test your function, when you are sure your function is
working correctly move on to Part 2.
Horner’s Algorithm
When evaluating a polynomial or order n (or its derivative a polynomial of order n-1) your program should complete each of the following steps in order.
⋮
As an equation this looks like (… ( (CnX + Cn-1)
X + Cn-2) X + Cn-3) …) +
C0
This approach requires many less multiplications that using the power function and is thus more efficient (and accurate).
PART 2: (14 points)
Evaluate the derivative of a polynomial of order N where N>0
Write a
function to evaluate the derivative of the polynomial or order Order. This function will be used in the Newton Raphson method. The prototype of the function should be
double PolyDeriv(double Coefs[ ], double X, int polynomialOrder);
This function will be very similar to the function above. You will not need to
use Coef0, but it will still be available in array Coefs.
Remember that the derivative of a polynomial of order polynomialOrder
is a polynomial of order polynomialOrder-1. You can start with your PolyEval function and make a few small changes to create
this funtion. You will need to multiply each
coefficient by the power of X it modifies in the original polynomial, before
using it in the algorithm from Part 1. The value of the derivative of the
polynomial evaluated at X must be returned as the value of the function.
Write a main program to test your function, when you are sure your function is
working correctly move on to Part 3
.
PART 3: (24 points) Finding the root of a polynomial using the bisection method
Next you should write a
function find the root using the bisection method. The function should return
the value of X at which a root occurs. The bisection method is summarized below
and is discussed in your textbook (beginning on pages 280 and 528). You my base your program on the treatment in the textbook up to and
including the statement of inputs and outputs. Your function must implement the
bisection method iteratively (not recursively as give in your textbook), this means that your bisection function may not call
itself. Also, your function must work for any polynomial, not just the specific
ones given in the text. The prototype of the function should be
double Bisect( double Coefs[
], double IntervalEnd1, double IntervalEnd2, int polynomialOrder,
int *NumIterp );
Variables IntervalEnd1 and IntervalEnd2 are the ends of the interval in which
you are searching for a root of the polynomial. Variable polynomialOrder
contains the order of the polynomial whose roots are being searched for.
Variable NumInterp counts the number of time the
series of steps (steps 2-4) below are executed before the
root is located. The bisection method for finding the root of a polynomial
consists of the following steps
Addition points to keep in mind include:
Write a main program to test your function, when you are sure your function is working correctly move on to Part 4.
PART 4: (24 points) Implementing the
Next
you should write a function find a root using the Newton Raphson
method. This function should return the value of X at which the root occurs.
The Newton Raphson method is discussed in your text
beginning on page 529. You may use the code and development presented in your
text as a basis for your Newton Raphson algorithm.
The prototype of your function should be
double NewtRaph( double Coefs[], double Estimate,
int Order, int *NumIterp);
Write a main program to test your function, when you are sure your function is
working correctly move on to Part 5.
PART 5: (24 points)
Your main routine should
REMEMBER
Call you’re the file containing your program polyroot.c