7
$\begingroup$

What are the most accurate algorithms for evaluating a polynomial using floating point arithmetic? The internet seems to suggest that Horner's method is commonly used. In particular I have a cubic polynomial of the form f(x) = a x^3 + b x^2 + c x + d, which I am evaluating in the naive way with floating point arithmetic, and was curious whether some recursive approach or some refactoring would give a more accurate result. That is, a result closer to what I would get if I were to evaluate the polynomial exactly or with a metric ton of precision in Mathematica.

$\endgroup$
7
$\begingroup$

Horner is indeed the most stable way to evaluate a polynomial (and you get the bonus of evaluating its derivatives with not too much extra cost). Higham presents a nice error analysis of the algorithm (Accuracy and stability of numerical algorithms, 2nd edition, p.94). He also presents an algorithm that includes a running error bound so you have an idea on the difference between the real value and what Horner calculated (Algorithm 5.1 on p.95).

If your case is limited to cubic polynomials and you're worried about loop overhead, you could unroll the loops by hand. But I doubt you will gain much. Stick to the tried and tested.

$\endgroup$
  • 2
    $\begingroup$ The accuracy of the Horner scheme can be improved by using compensated arithmetic. See: Philippe Langlois and Nicolas Louvet. "How to ensure a faithful polynomial evaluation with the compensated Horner algorithm." In 18th IEEE Symposium on Computer Arithmetic (ARITH'07), pp. 141-149. IEEE, 2007 (draft online); Stef Graillat, Philippe Langlois, and Nicolas Louvet. "Algorithms for Accurate, Validated and Fast Polynomial Evaluation", Japan J. Indust. Appl. Math., 26 (2009), 191–214 (online) $\endgroup$ – njuffa Jun 19 '16 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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