Assignment 4 Real roots of a polynomial

CMPS 12A
Introduction to Programming
Programming Assignment 4
In this assignment you will write a java program that determines the real roots of a polynomial that lie
within a specified range. Recall that the roots (or zeros) of an n
th degree polynomial
n
n
n
n
f x  c  c x  c x   c x  c x


1
1
2
0 1 2
( ) 
are those numbers x for which
f (x)  0 . In general an n
th degree polynomial has at most n roots, some of
which may be real and some complex. Your program, which will be called Roots.java, will find only the
real roots.
Program Operation
Your program will prompt the user to enter the degree of the polynomial, the coefficients, and the left and
right endpoints of the interval in which to search. For example, to find the roots of the cubic polynomial
6 11 6
3 2
x  x  x  in the interval [-10, 10], your program would run as follows.
% java Roots
Enter the degree: 3
Enter 4 coefficients: -6 11 -6 1
Enter the left and right endpoints: -10 10
Root found at 1.00000
Root found at 2.00000
Root found at 3.00000
%
Notice that the user enters the coefficients from lowest power of x to highest power. The degree can be
any non-negative integer, while the coefficients and range limits are doubles. No error checking on these
inputs are required for this project. You may therefore assume that your program will be tested only on
inputs that conform to these requirements. The root values will be rounded to 5 decimal places of
accuracy.
Consider the fourth degree polynomial
2 ( 2)( 1)
4 2 2 2
x  x   x  x 
. Written in factored form it is easy to
see that the roots are
2,  2, i, and  i . (See http://en.wikipedia.org/wiki/Imaginary_unit if you are
unfamiliar with the number i.) As we can see the program does not the find complex roots.
% java Roots
Enter the degree: 4
Enter 5 coefficients: -2 0 -1 0 1
Enter the left and right endpoints: -5 5
Root found at -1.41421
Root found at 1.41421
%
Your program will find only those roots that are contained in the interval specified by the user. If no roots
are found in that interval, a message to that effect is printed to stdout. We illustrate this with two more
searches on the same polynomial:
2 ( 2)( 1)
4 2 2 2
x  x   x  x  .
2
% java Roots
Enter the degree: 4
Enter 5 coefficients: -2 0 -1 0 1
Enter the left and right endpoints: 0 2
Root found at 1.41421
% java Roots
Enter the degree: 4
Enter 5 coefficients: -2 0 -1 0 1
Enter the left and right endpoints: 0 1
No roots were found in the specified range.
%
Notice that after typing the degree, your program will ask the user for the correct number of coefficients.
An n
th degree polynomial has
n 1
coefficients, including the zero terms, all of which must be entered by
the user. When testing your program you may find it useful to store the inputs in a file and redirect stdin
to read from that file rather than the keyboard. In that case the program operation will appear as follows.
% more infile
5
30 0 -10 -3 0 1
-10 10
% java Roots < infile
Enter the degree: Enter 6 coefficients: Enter the left and right endpoints:
Root found at -1.73205
Root found at 1.73205
Root found at 2.15443
%
The prompts all appear on a single line because there is no one at the keyboard hitting return to enter the
inputs. All of these examples have served only to demonstrate program operation for this project. So far
we've said nothing about how your program will accomplish these calculations. To start, read section
4.11 in the text, especially the example FindRoot.java at the end of that section which uses the Bisection
Method to compute the square root of 2. This example is also posted on the class website.
The Bisection Method
If
f (x)
is a continuous function on an interval
[a, b]
, and if
f (a)
and
f (b)
have different signs, then
f (x)
must have a zero in
[a, b]
. This fact is known as the Intermediate Value Theorem, and is clear from
the figure below.
a b
3
The bisection method is an iterative technique that traps the zero in smaller and smaller subintervals, until
the size of the subinterval containing the zero is sufficiently small. The location of the root is then known
with an error no more than the width of that final subinterval. To begin let
m  (a  b)/ 2
be the midpoint
of
[a, b]. This midpoint serves as the current approximation to the root. Look at the two subintervals
[a, m]
and
[m, b]
. If
f (a)
and
f (m)
have different signs, then the root is contained in
[a, m]
. If
f (m)
and
f (b)
have different signs, then the root is contained in
[m, b]
. If the original interval
[a, b]
contained one root, then exactly one of these two alternatives must hold. Let us assume that it is the first
subinterval
[a, m]
that contains the root. The other subinterval is discarded and the search continues on
the next iteration in
[a, m]. Its midpoint will serve as the next approximation to the root. Notice that the
“search space” has been halved on one iteration. This means that each iteration increases the accuracy of
our root estimate by one binary digit, and about 4 iterations gains one decimal digit of accuracy. The
algorithm continues to loop until the interval in which the root is known to exist has width less than some
predefined tolerance.
If the initial interval contains more than one root of
f (x)
then this method will only find one of them. If
we wish to find all roots within some range L to R we must partition
[L, R]
into a sequence of sufficiently
small subintervals
[a, b]
of equal width, then run the Bisection Method on each such subinterval for
which
f (a)
and
f (b)
have different signs. The width
b  a
of these smaller subintervals therefore
constitutes a limit on the possible resolution with which roots can be detected. In other words, roots in
[L, R]
that are closer together than the resolution
b  a
cannot be distinguished. When run on the
example pictured below, this procedure will find all three roots.
The procedure will break down however when
f (x)
has two roots that are "infinitely close". For
instance the polynomial
( ) ( 1)( 2) 5 8 4
2 3 2
f x  x  x   x  x  x  has a so-called double root at the point
x  2
and a single root at
x 1.
L [ ] [ ] [ ] R
a b
a 2 b
[ ]
even root
odd root
1
( ) 5 8 4
3 2
y  f x  x  x  x 
4
No matter how fine a resolution we pick, we cannot distinguish between the "two" roots at
x  2
. In fact
the bisection method cannot find this root at all since it is not the case that
f (a)
and
f (b)
have different
signs, no matter how small
b  a
is.
We can divide the roots of a polynomial
f (x)
into two classes called the odd roots and the even roots,
respectively. The point
0
x
is an odd root if and only if the graph of
f (x)
crosses the x-axis at
0
x
. We
call
0
x
an even root if and only if the graph touches the x-axis at
0
x . Since it requires a sign change, the
bisection method can only find the odd roots of a polynomial. However the even roots of
f (x)
are
among the odd roots of a related polynomial called its derivative
f (x). We illustrate this with the
polynomial from the previous example.
As we can see, not all the odd roots of the derivative
f (x)
are even roots of the original polynomial
f (x)
. It can be shown however that every even root of
f (x)
is an odd root of
f (x).
Representing Polynomials
Derivatives are studied extensively in Calculus. It is not necessary however to know how to differentiate
general functions or even to know what a derivative is in order to use the above fact, so students who have
not had Calculus need not be dismayed. The world of polynomials is much simpler than the world of
general continuous functions in Mathematics. To specify an n
th degree polynomial
f (x)
one need only
specify a list of
n 1
numbers, namely its coefficients.
n
n
n
n
f x  c  c x  c x  c x   c x  c x


1
1
3
3
2
0 1 2
( ) 
In this project these numbers
k
c
(for
0  k  n
) will be stored an array of length
n 1
. For us then, a
polynomial is an array. The derivative
f (x)
is a polynomial of degree
n 1
whose n coefficients are
given by a simple rule.
2 1
1
2
1 2 3
( ) 2 3 ( 1)
 
      
n
n
n
n
f x c c x c x  n c x nc x
In other words, if the coefficient array for
f (x)
is
( , , , , , , )
0 1 2 3 n 1 n
c c c c c c  
then the coefficient array for
f (x)
is
( , 2 , 3 , , ( 1) , )
1 2 3 n 1 ncn
c c c n c   
. To put it another way, if
k
c
(for
0  k  n
) are the coefficients
of
f (x)
and
k d
(for
0  k  n 1
) are the coefficients of
f (x)
, then
1
( 1)
k   k  d k c
(for
0  k  n 1
).
( ) 3 10 8
2
y  f 
x  x  x 
odd root at
x  2
new odd root at
3
4
x 
5
Once the coefficients of
f (x)
are calculated, one can run the Bisection Method on
f (x)
to find its odd
roots. Each of the roots
0
x
of
f (x)
are then plugged into
f (x)
to see if
f (x0
)  0
. If so, we have
found an even root of
f (x)
. We run into another problem at this stage though. All of these calculations
will be done using the type double. Whenever two quantities u and v are independently computed and
stored using a floating point data type, round off and approximation errors are introduced. Even if some
Mathematical theory tells us that
u  v
, the stored floating point values may not in general be equal. We
can expect however that
u  v
is less than some positive threshold value which is close to zero, but not
closer than the accuracy that the calculation allows. In particular we cannot directly confirm that
f (x0
)  0
since
0
x
is at best only an approximation to a root of
f (x)
, and for that matter our computed
value for
( )
0
f x
is only an approximation to its actual value. Instead, to check whether
0
x
is also a root
of
f (x)
, we check that
f (x0
)  threshold.
Program Specifications
Your program is required to implement the following static functions to carry out the operations described
above. Your functions must match the ones below in their name, return type, and parameter list. Your
initial task is to fill in the braces with appropriate Java code and test each function thoroughly.
static double poly(double[] C, double x){....}
A call to poly(C, x) will return the value at x of the polynomial with coefficient array C. You can
accomplish this by writing a loop that multiplies each coefficient by an appropriate power of x, and
accumulates the sum of all such terms. When the loop terminates return the sum.
static double[] diff(double[] C){....}
The call diff(C) will return a reference to a newly allocated array D containing the coefficients of the
polynomial that is the derivative of the polynomial with coefficient array C. In other words the function
poly(D, x) will be the derivative of the function poly(C, x).
static double findRoot(double[] C, double a, double b, double tolerance){....}
Assuming poly(C, a) and poly(C, b) have different signs, a call to findRoot(C, a, b, tolerance)
will return an approximation to a root of poly(C, x) in the interval [a, b] whose error is no more than
tolerance. Implement this function by using the Bisection Method illustrated at the end of section 4.11
and in the examples FindRoot1.java, FindRoot2.java and FindRoot3.java on the class webpage. This
function has a precondition that says the polynomial takes opposite signs at the endpoints of the interval.
Therefore it should only be called when that precondition is satisfied. Only after these functions are
working, should you begin writing function main() for the project. The following steps are offered as a
rough outline of program logic for function main().
1. Declare double variables resolution, tolerance and threshold, and initialize them to
2
10
,
7
10
and
3
10
respectively. Declare any other variables needed by function main().
2. Get the degree of the polynomial and its coefficients, along with the left and right endpoints of the
search interval [L, R] from the user.
3. Calculate the coefficients of the derivative polynomial by calling your function diff().
4. Begin a loop iterating over all subintervals [a, b] of width resolution forming a partition of [L, R].
5. For each such subinterval [a, b]
6. If the polynomial changes signs across [a, b]
7. Find an odd root of the polynomial in [a, b] accurate to within tolerance
8. Print the value of the root rounded to 5 decimal places
6
9. Else if the derivative polynomial changes signs across [a, b]
10. Find an odd root of the derivative polynomial in [a, b] accurate to within tolerance
11. If the absolute value of the polynomial evaluated at this root is less than threshold
12. Print the value of the root rounded to 5 decimal places
13. If no even or odd root was found in [L, R] print a message to that effect
The above outline is an example of what programmers call pseudo-code. Something closer to English
than actual Java code, but structured to express algorithm steps. Note that indentation is significant in
pseudo-code, unlike in Java. Loop bodies, as well as the true and false branches of conditionals are
indicated solely by indentation.
You may define other functions as you see fit, but the ones described above are required for full credit.
An example will be posted on the webpage illustrating how one can round and format a double value to a
specific number of decimal places. You may play with the parameters resolution, tolerance and
threshold, but the specific values mentioned above should result in your output matching the examples
exactly. More such examples will be posted on the webpage for testing purposes.
What to turn in
Your final task is to write a Makefile for this project along the lines of the one in lab assignment 4. This
Makefile should create an executable jar file called Roots allowing one to run the program without having
to type java at the command line. Include a clean target as in lab4. You may also write a submit target
like the one in lab4. You may also try to write another phony target called check that checks the files you
submitted.
Submit the two files Makefile and Roots.java to the assignment name pa4. This project is considerably
more involved than any of the earlier ones, so you will have more time to complete it. You should
nevertheless start early, work on one thing at a time, and ask questions of myself, the TAs and on Piazza.