REMEMBER: your program is looking for a MINIMUM or MAXIMUM of the functions `f', NOT a root!
In order to be able to comment on the accuracy of each root-finding method, you need to know where the actual roots are! So, here's a list of the roots of the derivatives of functions 1 and 2.
Question:
If I start the program with the same arguments except using
a different root-finding method, I get slightly different answers;
does this mean my program is wrong?
Answer:
No. Because the root-finding methods work differently, it's
normal that they will produce slightly different answers even
when they're started with the same information.
Unlike the bisection and fast bisection methods, Newton's method requires a single initial point to start. But the arguments to the program don't change: you still have to provide a starting interval. So how does that work? Well, if you have a look at the `find_extremum' function, you'll see that the `newton' function is actually called with ( x_left + x_right) / 2.0 as the initial point...
Many students have asked what "interesting" means for the third function you have to choose. Here's how you should think about it: your function should demonstrate some "special" or "unusual" behaviour of at least one of the root-finding methods. Of course, "special" or "unusual" is still vague, but you should have a good idea of what the "normal" or "expected" behaviour of the methods is, so you have a point of reference.
Also, the term "classes of functions" is a little bit vague. Let me point you in the right direction: think of the largest classes you can think of, for example, all continuous functions, all differentiable functions, etc. And try to think how the methods behave for these large classes of functions.
Don't make the methods smarter than they are! Just write code for the basic methods, the way that they were described to you. In particular, don't add any "improvements" that perform some extra checking for special conditions, etc. The methods themselves are not that smart: your code shouldn't be either!
To have `gcc' check that your programs conform to the ANSI C standard, use the two options "-ansi -pedantic". For example, to compile `minmax.c', you would use the following command line:
gcc -ansi -pedantic -Wall -o minmax minmax.c -lm
This will ensure that you are following all standard ANSI C
conventions and not inadvertantly using any features special to
GCC.
In order to print the output of the program for Assignment 1, you may use the useful feature of "output redirection" available on UNIX. Just invoke the program using the same command-line that you normally would, except add the character ">" and the name of a file at the end. For example,
minmax 1 b -10 10 1e-10 1000 > file1b
will execute the program and write the output to a file called
"file1b". Warning: using the ">" character will
erase the contents of the file if it already exists. If
you want to simply append the output of the program to
the end of a file, use ">>" instead of ">".
I have posted an outline of the marking scheme for the assignment on the main page. Have a look at it! In particular, note that only half of the marks are for your code, so make sure to budget your time accordingly... In other words, don't spend 90% of your time on the code and only 10% of your time on the report: that would be stupid! Especially since the code should be quite easy to write, so if you find yourself spending a lot of time on it, you're probably doing something wrong (so ask questions).
Question:
Are we allowed to add "helper" functions to the code?
Answer:
Yes, but they are not necessary. The code that you have to write
is very simple (less than 15 lines per function) and there is no
need for "helper functions". So if you find yourself writing lots
of code outside of the functions we've already provided, chances
are there's something you're not getting quite right...
Question:
How exactly does this "fast bisection" work?
Answer:
The description in the assignment handout should be clear, but
here's a hint: the computation done to get the value "x_next" is
the same as for the secant method.
Note that the stopping conditions for all three root-finding methods are the same: stop when either you have reached the maximum number of iterations, or the last two values of the root are closer together than the tolerance parameter. There are many other stopping conditions we could have used, but these are the ones you should implement.
Don't panic if you don't understand everything in the skeleton program! Especially, don't worry if you don't understand the definition of "result_type" and how it is used in the root-finding methods. The only thing you have to remember when you write the body of the root-finding methods is that you should follow the instructions given in the comments: use the variable `num_iter' to keep track of the number of iterations, and assign a value to the variable `root' before the last statements in the function body.