CSC270F, 1996, St. George Campus Assignment 1 Due Monday, September 30, at 6:10 pm in any tutorial FINDING ROOTS OF AN EQUATION IN A SINGLE UNKNOWN This assignment solves one of the most basic problems in numerical analysis: finding a value of the variable x that satisfies f(x) = 0 for a given function f. This is sometimes called a zero of f or a root of f(x) = 0. For simple polynomials, formulas can be used to solve this problem. For many other equations, solving the problem algebraically is very complicated. There are several methods of approximating a solution. This assignment will examine two methods: bisection and secant. Bisection method The bisection method starts with two values of x (let's call them left and right) with corresponding function values that have opposite signs. In other words, the range of values between the two initial values includes at least one solution to the function (where the function crosses the x axis). At each step in the algorithm, check whether the difference between right and left is less than some acceptable tolerance. If not, find the midpoint of the range and discard the one or the other of the old end points, replacing it by the midpoint. Pick the value to discard based on the requirement that the values of the function at the endpoints of the range must have opposite signs. Repeat the process until the tolerance is achieved. Secant method The secant method also starts with two approximate solutions, x_0 and x_1. The line that passes through the points (x_0, f(x_0)) and (x_1, f(x_1)) is a secant of the curve defined by f. This line should cross the x axis somewhere. The x value where the line crosses the x axis is defined as x_2. The secant method involves solving for x_{n+1} based on the secant defined by (x_n, f(x_n)) and (x_{n-1}, f(x_{n-1})). This process is iterated, keeping the new approximations, x_{n+1} and x_n, and discarding the oldest of the approximations, x_{n-1}, until the absolute value of the difference between successive pairs of approximations, | x_{n} - x_{n+1} |, is less than some tolerance. Your assignment Write a pair of C programs: bisect.c that implements the bisection method and secant.c that implements the secant method. Once you have written the programs, copy into them the sample functions that are provided in the web page. Your programs should read three values from the input: the two initial x values and the tolerance value. Your programs should print the successive approximations to the root and the size of the current x-interval in table form. The last row in the table should contain the final, computed root. For example, eddie: gcc bisect.c -o bisect eddie: bisect Enter a, b, and epsilon: 2 4 .01 3.000000 2.000000 2.500000 1.000000 2.750000 0.500000 2.875000 0.250000 2.937500 0.125000 2.968750 0.062500 2.953125 0.031250 2.945313 0.015625 2.941406 0.007813 eddie: Your solution should include appropriate error checking of the input. Read the newsgroup and post any questions to the newsgroup. Testing Provide sample runs of your programs with the functions and input values provided on the Web page. Provide sample runs of your programs with some other functions that you choose. Provide test runs that illustrate your successful error checking. Report Compare the bisection and secant methods in a paragraph or two. Give examples of functions that will not necessarily produce a solution in each case and explain why this happens. To aid in the marking, illustrate (plot) your problem functions. Describe any limitations of your program. Based on your choice of functions and input values, describe your testing strategy. Refer to the specific functions and values you used. Hand-in details Hand in printouts of your programs and test functions, printouts of your testing results, and your report. Clearly label each of the parts of your assignment. Organize the parts and put them into an ENVELOPE. Fill in, sign and attach the assignment cover page (shown below) to the envelope. Your programs must also be submitted electronically by the deadline. You must have EXACTLY the following files with EXACTLY these names: bisect.c secant.c f1.c \ each contains one of YOUR test functions in the f2.c +--- same format as on the Web page. Include as many f3.c / f*.c files as you have test functions. Submit these by the deadline with the command eddie: submit -N a1 csc270h bisect.c secant.c f1.c f2.c f3.c You may, if you wish, also submit a README file that the tutor will read. For more information on the submit command, type `man submit' on CDF. The tutors will compile and run your programs. MAKE SURE that the following commands work with the programs that you submit: eddie: gcc -o bisect bisect.c eddie: bisect ... eddie: gcc -o secant secant.c eddie: secant ... For each program, the tutors will enter three numbers: the initial x-values and the tolerance. Your program must accept them IN THAT ORDER. YOU WILL LOSE MARKS if you don't follow these submission instructions exactly. This is because the tutors will be marking more than 160 of these assignments and any deviations from these instructions will cost them time and frustration. Please help keep the tutors happy. ------------------------------------------------------------------------ COVER SHEET FOR ASSIGNMENT 1 Surname Given Name(s) Student Number TA's name Tutorial location I declare that this assignment is my own work and is submitted in accordance with the University of Toronto Code of Behavior on Academic Matters, the Code of Student Conduct, and the guidelines for avoiding plagiarism described in the course syllabus. I discussed this assignment with the following people: Signature ------------------------------------------------------------------------ GRADING Programs Bisection method correctness /10 Secant method correctness /10 Error checking /5 Style /5 Testing /5 Report and Discussion Content /15 Style and readability /5 ----------- Total /55