# How does Horner method evaluate the derivative of a function

From my understanding, Horner method is mainly used to evaluate polynomial functions by altering the equation into a simpler recursive relation with lesser number of operations. Say for example, I was given $f (x) = 4x^4 + 3x^3 +2x^2+x+5$ This can be rewritten as $5 +x (1+x (2+x (3+x (4)))$

Were we can evaluate the function as a recurrent relation of simpler terms starting from:

$b_n=4$

$b_{n-1} = 3 + b_n* x$

And $b_0$ would be the whole term evaluated and therefore the image of the function. What I want to understand how is running horner method to the $b_n$ values result in the derivative?

• @JeanMarie: Links are overlapped therefore clicking doesn't lead to any of them. Commented Feb 11, 2017 at 9:23
• Here is the first link, the most interesting :(cut-the-knot.org/Curriculum/Calculus/HornerMethod.shtml) Commented Feb 11, 2017 at 9:28

If you apply the Horner scheme, or perhaps the Ruffini method (both originally published papers on variants of the Newton method that use a trick for fast polynomial evaluation that was previously well-known), then you perform a polynomial division with remainder by a linear term. From the Horner table, you can read off the coefficients for a polynomial $q$ so that $$p(x)=p(a)+(x-a)q(x)\iff q(x)=\frac{p(x)-p(a)}{x-a}$$ which tells you that $q(a)=p'(a)$. A second Horner evaluation below the first table will thus evaluate the derivative value.

You can also see this as algorithmic differentiation, if the original algorithm is

val = 0
for k=0 to deg
val = val*x + a[deg-k]
end for


then the derivative by using the chain rule in every step gives

dval = 0; val = 0
for k=0 to deg
dval = dval*x + val
val = val*x + a[deg-k]
end for


The derivative steps needs to be computed first as it uses the last value of val.

I do not know if this will answer the question; if it does not, please forgive me.

Consider the polynomial to be $$p=\sum_{i=1}^n c_i\, x^{i-1}\implies p'=\sum_{i=1}^n (i-1)\, c_i\, x^{i-2}$$ As a pseudo code, you would have

  p  = c(n)
dp = 0
do j = n-1 , 1 , -1
dp = dp * x + p
p  = p  * x + c(j)
enddo


which computes at the same time the polynomial and its derivative with a minimum number of basic operations.

• The first summation (the polynomial $p$, not the derivative $p'$) should have $i=0$. I assume that code is Fortran "pseudocode" - as Fortran isn't all that mainstream, a comment explaining the loop might help. It's not hard to work out that the loop body runs for $j=n-1$ down to $j=0$ inclusive, but that do syntax doesn't clearly express that IMO (actually it seems actively misleading, and makes me wonder if the , 1 , should be a , 0 ,).
– user510
Commented Nov 22, 2018 at 11:25
• @Steve314. You are right ! Typo that I shall fix. Commented Nov 22, 2018 at 11:50

The key is to make the indices the same and use original Horner's rule in the same for loop to evaluate both polynomial and its derivative.

Let's say the original problem is to compute f(x)=sum[ c[n] x^n, for {n,0 ,k }].

The derivative is of the form f'(x)=sum[ m c[m] x^(m-1), for {m,1 ,k }]. A change of index n=m-1 make the base of iterator the same, i.e. f'(x)=sum[ (n+1) c[n+1] x^(n), for {n,0 ,k-1 }]

Now we have same iterator which can be used except the case n=k which only applies to evaluation of function and not the derivative. This case can be computed outside the loop easily.

Here is the way to do it in Python:

def horner_eval(x, a):

'''Uses Horner's rule to return the polynomial
a[n] + a[n+1] x^1 + a[n+2] x^2 + ... + a[0] x^(n)
AND its derivative evaluated at x.
NOTICE: coefficient vector is given backward for ease of indexing
'''

dist, speed = 0, 0

for i in range(len(a) - 1):
dist = a[i] + (x * dist)
speed = i * a[i] + (x * speed)

dist = a[-1] + (x * dist) # since function has one term more that the derivative
return dist, speed


dist stores the values of the polynomial at x.

speed stores the values of derivative of the polynomial at x.

• You might want to include a little about why this evaluates the derivative Commented Dec 22, 2017 at 17:18