CSC270F, 1996, St. George Campus Assignment 1 was marked by Mikhail Soutchanski ( at270sou@cdf ). Marking policy and explanations of error codes. CORRECTNESS (of bisect and secant). ------------ (C1) -0 : if program can miss a root in _a_ or _b_. (C2) -3 : bisect program finds a spurious root z. In some cases, this happens if user entered a=b=z (any epsilon, arbitrary z). Typical problem function is f(x)=1.0/x - when main loop in the program halts, carefull program must check what value function has in the middle point after the last bisection. Otherwise, x=0 is erroneously reported as a root. (C3) -0 : wrong termination condition in secant.c In this case, secant can find a false root. Let Xn-1 and Xn be successive approximations. If "secant" program terminates when Xn+1 is very close to Xn (Xn-1), or when | f(Xn) - f(Xn-1) | is a small value, but value of function is not tested, then "secant" may find a spurious root. It will happen whenever f(x) has a very steep slope. For example, a wrong version of secant will find that pi/2 is a root of tan(x). Correct termination condition: while( fabs( f(Xn) ) > epsilon ) Several correctness-related errors occur due to wrong termination condition. (C4) -0: program may not terminate under certain initial values because of numerical rounding errors. Sometimes, "bisect" diverges if there is not counter-divergence check inside the while loop. For example, if we use 1st sample function x*x*x - 10*x + 4, and enter values: -100 1000 0.0000001 some versions of bisect will not terminate, unless we put lines m=(a+b)*0.5; if ( f(m) == 0.0 || fabs(m-b)<= eps || fabs (m-a)<= eps ) return m; into the while-loop. Similarly, "secant" may diverge. (C5) -2: "secant" program does not check whether | f(Xn) - f(Xn-1) | is a small value or not. Note that if it is really very small, then a constructed secant is almost flat and does not intersect x; hence, new value Xn+1 cannot be computed. In the worst case, program performs division by 0. This problem can occur after any iteration. (C6) -3: some recursive versions of bisect and secant give rise to Segmentation Fault error. This can happen in cases discussed above, when termination condition is not "safe". Points were deducted for this error only if a submitted program at least once was aborted with the segmentation fault error. (C7) -2: predefined number of iterations. Some students, define the constant MAXITER=number of iteration; so, their secant and bisect cannot iterate more than MAXITER times. This is unacceptable technique. (C8) -1: wrong termination condition in bisect.c , for example: while ( fabs( f(m) ) > epsilon ) { m = 0.5*(a+b) ; ...... } (C9) -5: incorrect implementation; a major error in C code. The typical problem function in this case is f(x)=x*x-1, a=0, b=2, any tolerance value. Wrong implementation cannot find the root in x=1. The error code (C9) also denotes fatal syntactic errors in code. (A1) -1 files with C code were submitted incorrectly (e.g., a1 was omitted). ERROR CHECKING. --------------- (E1) -3: program does not check that the tolerance should be greater than zero. If code assigns |eps| to eps, this is acceptable, no points were deducted. Note that, if tolerance is negative, program may never terminate ! (E2) -5: incorrect error checking: bisect.c does NOT check whether f(a) * f(b) < 0 Note that the bisection method (and IVT) guarantee solution only if function has different signs in _a_ and _b_. During marking, I disregarded whether programs perform range and domain checking. Meanwhile, some students used "errno", some printed an "error message", but it seems that majority ignored these issues. Just a few students followed instructor's suggestion: function must return (an arbitrary) value in any case. By the way, implementation of this suggestion is straightforward. For example: float f (float x) { if (x < 4) return x ; else return x + sqrt(4 - x); } STYLE. ------ (S1) -1: bisect or secant calculate values of function f(x) more than 2 times during each iteration (it is sufficient to compute a value of f(x) only once during each iteration). Excessive calls to f(x) can be a computational burden, if calculation of f(x) takes a lot of time. (S2) -1: main() is declared incorrectly. For example, NEVER write: void main() or double main() This is a serious mistake. Read C-faq, King's book are messages posted to the newsgroup (Hyper-News version). (S3) -1 code for a test function is incorporated using #include f2.c (BAD !) where f2.c is a code with test function. This is unacceptable. Some students claim that instructor suggested this during a lecture. This is wrong: he suggested to include (i.e., put in, copy-and-paste) code of function in the main code. (S4) -1: clumsy code. For example: complicated combinations of else-if instead of 1 or 2 easy understandable comparisons; format of expected input is not scanf("%f%f%f", &a, &b, &eps); but, say: scanf("%f, %f, %f", &a, &b, &eps); or another error in implementation of input (sometimes, these errors result in non-terminating programs). bad organization of code. For example, or code is not split up into separate purposeful functions in a reasonable way, i.e. either code contains too many specific functions, or code obfuscates reader; declarations (prototypes) of functions appear inside code of other function or inside main(), or a function returns value of the wrong type; a problem with implementation: user cannot enter a value of tolerance less than, say, 0.000001 (why not 0.00000001 ?) (S5) -1: no comments on the top of code about its purpose and no comments regarding what each function does. TESTING. ------- Some students submitted only code of sample and/or other test functions, but did NOT hand-in printed results of test runs and did NOT demonstrated how their programs check for errors. This is NOT acceptable (read "testing" section in the assignment). (T1) -1: no runs with sample functions are provided (printed). (T2) -2: no runs with other test functions are provided (printed). (T3a) -1: no runs which illustrate error checking whether IVT applies. (T3b) -1: no runs which illustrate successful error checking whether tolerance is positive. ----------------------------------------------------- REPORT. Because the assignment asked to compare the bisection and secant *methods* and give examples of functions that will not necessarily produce a solution, points were deducted if the following general properties of methods were NOT mentioned in the report. (R1) -3: rate of convergence: secant is faster than bisect, in general. (R2) -3: bisect always converges to a root for functions which satisfy conditions of the IVT; secant can find a root of a function even for those initial values which do not bracket a root. In other words, secant should work even if initial values f(a) and f(b) do not have opposite signs. secant does not always converge. (R3) -3: (a) In particular, if initial interval is far from a root, and 2nd derivative f''(x) changes signs between the root and the initial interval. See the Theorem 2.3.4 and examples on pages 64-69. (R3) -3: (b) it can never terminate if secant is flat (in this case, secant does not intersect x); this can happen after any iteration. (R4) -0: secant returns undetermined result if the equation f(x)=0 has no solution (of course, some functions have no roots). (R5) -0: bisect and secant are not able to find more than one root. ------------------------------------------------------------- Some students complain in their README files, that they did not understand how to work with library functions (sqrt, sin, pow). First, the header file "main.h" contains ONLY prototypes of standard mathematical functions. In other words, in "main.h" they are declared as having float arguments and returning a float value. Second, _*the standard mathematical library*_ (acronym: lm) contains object files (machine instructions) which IMPLEMENT library functions. A compiler generates object files from your own original source files written on C. A linker (called immediately after a compiler) extracts object files from libraries and link them to your object files and performs other operations to make an executable file. When you run from a command line gcc -o -lm you tell _gcc_ that after compiling, your object files must be linked with standard functions in the lm library. If you would like to link some other non-standard libraries, you must mention their names on the command line. -------------------------------------------------------------