2
$\begingroup$

How can I test whether a given 1D root-finding procedure is robust? I know that there are data sets and resources online for different kinds of optimization, but I have yet to find anything with regard to 1D root-finding. Do you happen to know of any data sets or functions that are commonly used to test the robustness of 1D root-finding procedures?

In particular, I would like to see some functions that will break software that has not been written carefully to account for finite-precision arithmetic.

Thanks for your input!

$\endgroup$
6
$\begingroup$

There are many good open-source implementations of root-finding methods out there already. One example is boost, whose implementation of Newton-Raphson and related methods you can find here. If you read its source code, you will be able to see what issues the authors wanted to address, and how they dealt with issues like convergence, user-specified tolerance parameters, and round-off errors.

One of the algorithms boost implements is TOMS748. If you look at the original paper that introduced this algorithm, by Alefeld, Potra, and Shi, you will see what functions they used to test their algorithm (Table I on p. 341), and you can also compare your implementation with all the ones they ran. This is perhaps the simplest and most robust way to do this, and the one I'd personally prefer.

Another way is to look at the testing code for open-source root-finding libraries, and see what functions the libraries' authors use to test them. For example, GSL's source code is here, and roots/test_funcs.c contains its testing functions.

$\endgroup$
  • $\begingroup$ Thanks for your answer, I had not thought of looking at the existing test suites for open-source libraries. There's a lot of useful information there. $\endgroup$ – void-pointer Sep 19 '14 at 8:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.