09 January 2010

Another Library: 1-D Root Finding in Ocaml

...and here's another library for 1-D root finding (non-linear equation solving) in OCaml. Get it with
git clone git://github.com/farr/ocaml-solve.git
I'm particularly proud of this one for two reasons:
  1. All the algorithms, even the ones requiring derivatives, use bracketing. If a step in the algorithm would fall outside the brackets for the root, the algorithms perform a bisection step instead, and then try again. In this way, all algorithms are guaranteed to converge on a root. (It's always annoyed me that the GSL doesn't do this with its "algorithms that require derivatives".)
  2. One of the algorithms in the library is a higher-order Newton's method. Given an arbitrary number of derivatives, this algorithm takes advantage of the additional information to implement higher-order convergence. I learned this trick from Danby's book, where he is trying to solve Kepler's equation using a fourth-order method.

Polynomials in OCaml

I just posted some code on GitHub to manipulate polynomials in one variable in OCaml. It's pretty simplistic, and only works for polynomials whose coefficients are floating-point real numbers (so beware of roundoff error!), but I have found it to be useful in many quick-and-dirty situations. To grab it, use
git clone git://github.com/farr/ocaml-poly.git