Polynomial Evaluation Using Horner Method

1 Canonical Polynomial

Given a canonical polynomial f(x)=å_i=0ⁿ a_ixⁱ, the Horner method is an efficient way to calculate a polynomial value with respect to the given x. For simplicity, we take a cubic polynomial as an example. If we write a cubic polynomial as

f(x)= 3
å
i=0
a_ixⁱ=x[x(a₃x+a₂)+a₁]+a₀

the Horner method to compute a polynomial value may be stated as follows:

Let f_x=a₃.

Compute f_x ×x+a₂ and assign the value to f_x.

Compute f_x ×x+a₁ and assign the value to f_x.

Compute f_x ×x+a₀ and output the result f_x.

As indicated above, only three multiplications are used. For a polynomial of degree n, the well-known Horner method is

   fx = a(n)
   do i=n, 1, -1
      fx = fx * x + a(i-1)
   enddo

There are, in toltal, n multiplications and n additions.

2 Legendre Polynomial

Given a Legendre polynomial f(x)=å_i=0ⁿ a_il_i(x), we have a recursive formula to calculate l_i(x):

l₀(x)=1, l₁(x)=x

l_i(x)= (2i-1)xl_i-1(x)-(i-1)l_i-2(x)
i
=b+a(b-l_i-2(x))

where, a = (i-1)/i, b = xl_i-1(x). Therefore, we have the following Horner type recursive method to calculate the polynomial value:

   fx = a(0) + a(1)*x
   lg_2 = 1.0
   lg_1 = x
   do i=2, n
      alpha = (i-1)/i
      beta = x*lg_1
      lg_i = beta + alpha*(beta-lg_2)
      fx += a(i)*lg_i 
      lg_2 = lg_1
      lg_1 = lg_i
   enddo

There are in toltal 3×n multiplications, n division and 4×n additions.

3 Tchebyshev Polynomial

Given a Tchebyshev polynomial f(x)=å_i=0ⁿ a_it_i(x), we have a recursive formula to calculate t_i(x):

t₀(x)=1, t₁(x)=x, t_i(x)=2xt_i-1(x)-t_i-2(x)

Therefore, we have the following Horner type recursive method to calculate the polynomial value:

   fx = a(0) + a(1)*x
   t_2 = 1.0
   t_1 = x
   do i=2, n
      t_i = (2*x*t_1 - t_2)
      fx += a(i)*t_i
      t_2 = t_1
      t_1 = t_i
   enddo

There are in toltal 3×n multiplications and 2×n additions.

RETURN