3
$\begingroup$

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?

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

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 ,). $\endgroup$
    – user510
    Nov 22, 2018 at 11:25
  • $\begingroup$ @Steve314. You are right ! Typo that I shall fix. $\endgroup$ Nov 22, 2018 at 11:50
-1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ You might want to include a little about why this evaluates the derivative $\endgroup$
    – eepperly16
    Dec 22, 2017 at 17:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .