java

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.

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.

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.