Horner's Method for Evaluating and Deflating Polynomials

C. Sidney Burrus, James W. Fox, Gary A. Sitton, and Sven Treitel

Rice University
Houston, TX 77251-1892
 
November 26, 2003
 

Abstract

Horner's method is a standard minimum arithmetic method for evaluating and deflating polynomials. It can also efficiently evaluate various order derivatives of a polynomial, therefore is often used as part of Newton's method. This note tries to develop the various techniques called Horner's method, nested evaluation, and synthetic division in a common framework using a recursive structure and difference equations. There is a similarity to Goertzel's algorithm for the DFT, Z-transform inversion by division, and Padé's and Prony's methods. This approach also allows a straight forward explanation of "stability" or numerical errors of the algorithms. Matlab implementations are given.

Related software