MATLAB Central Newsreader - Question on evaluating polynomials/polyval

Question on evaluating polynomials/polyval

adam — Tue, 16 Jun 2009 19:09:14 -0400

So the main method that is used by programs/computers to evaluate
polynomials is Horner's Method. That's cool...but i was reading
polyval.m, Matlab's polynomial evaluator, and noticed:

% Make it scream for scalar x. Polynomial evaluation can be
% implemented as a recursive digital filter.
y = filter(1,[1 -x],p);
y = y(nc);

Here x is the point of evaluation and p is a vector of polynomial
coefficients. I've tried to work out the filter equation and see how
poly evaluation is a filter, but I don't see it. Can anyone help?

Thanks!

Re: Question on evaluating polynomials/polyval

John D'Errico — Tue, 16 Jun 2009 20:49:02 -0400

adam <adam.attarian@gmail.com> wrote in message <d8a640f2-ec55-4e7c-bc30-ef3249f46abf@j12g2000vbl.googlegroups.com>...
> So the main method that is used by programs/computers to evaluate
> polynomials is Horner's Method. That's cool...but i was reading
> polyval.m, Matlab's polynomial evaluator, and noticed:
>
> % Make it scream for scalar x. Polynomial evaluation can be
> % implemented as a recursive digital filter.
> y = filter(1,[1 -x],p);
> y = y(nc);
>
> Here x is the point of evaluation and p is a vector of polynomial
> coefficients. I've tried to work out the filter equation and see how
> poly evaluation is a filter, but I don't see it. Can anyone help?
>
> Thanks!

Here is a fragment from the help to filter.

Y = FILTER(B,A,X) filters the data in vector X with the
    filter described by vectors A and B to create the filtered
    data Y. The filter is a "Direct Form II Transposed"
    implementation of the standard difference equation:

    a(1)*y(n) = b(1)*x(n) + b(2)*x(n-1) + ... + b(nb+1)*x(n-nb)
                          - a(2)*y(n-1) - ... - a(na+1)*y(n-na)

Now, look at how filter is called.

B = 1
A = [1, -x]
X = p

So the vector X is our list of polynomial coefficients.

a(1) * y(n) = b(1)*p(n) - a(2)*y(n-1)

We have B = 1,

a(1) * y(n) = p(n) - a(2)*y(n-1)

Likewise, a(1) = 1 is known, and a(2) = -x, is the
point to be evaluated.

y(n) = p(n) - x*y(n-1)

This is a difference equation. Start out with n = 1.

y(1) = p(1) + x*y(0)

Define y(0) = 0. So y(1) = p(1). Step forwards in
the loop. When n = 2, what happens?

y(2) = p(2) + x*y(1) = p(2) + x*p(1)

Look at n = 3.

y(3) = p(3) + x*y(2) = p(3) + x*(p(2) + x*p(1))

      = p(3) + P92)*x + p(1)*x^2

Continue until we run out of polynomial coefficients.

See that it really is just Horner's rule, implemented
as a recursive filter.

John

Re: Question on evaluating polynomials/polyval

Adam Attarian — Tue, 16 Jun 2009 21:35:08 -0400

On Jun 16, 4:49 pm, "John D'Errico" <woodch...@rochester.rr.com>
wrote:
> adam <adam.attar...@gmail.com> wrote in message <d8a640f2-ec55-4e7c-bc30-ef3249f46...@j12g2000vbl.googlegroups.com>...
> > So the main method that is used by programs/computers to evaluate
> > polynomials is Horner's Method. That's cool...but i was reading
> > polyval.m, Matlab's polynomial evaluator, and noticed:
>
> > % Make it scream for scalar x. Polynomial evaluation can be
> > % implemented as a recursive digital filter.
> > y = filter(1,[1 -x],p);
> > y = y(nc);
>
> > Here x is the point of evaluation and p is a vector of polynomial
> > coefficients. I've tried to work out the filter equation and see how
> > poly evaluation is a filter, but I don't see it. Can anyone help?
>
> > Thanks!
>
> Here is a fragment from the help to filter.
>
> Y = FILTER(B,A,X) filters the data in vector X with the
> filter described by vectors A and B to create the filtered
> data Y. The filter is a "Direct Form II Transposed"
> implementation of the standard difference equation:
>
> a(1)*y(n) = b(1)*x(n) + b(2)*x(n-1) + ... + b(nb+1)*x(n-nb)
> - a(2)*y(n-1) - ... - a(na+1)*y(n-na)
>
> Now, look at how filter is called.
>
> B = 1
> A = [1, -x]
> X = p
>
> So the vector X is our list of polynomial coefficients.
>
> a(1) * y(n) = b(1)*p(n) - a(2)*y(n-1)
>
> We have B = 1,
>
> a(1) * y(n) = p(n) - a(2)*y(n-1)
>
> Likewise, a(1) = 1 is known, and a(2) = -x, is the
> point to be evaluated.
>
> y(n) = p(n) - x*y(n-1)
>
> This is a difference equation. Start out with n = 1.
>
> y(1) = p(1) + x*y(0)
>
> Define y(0) = 0. So y(1) = p(1). Step forwards in
> the loop. When n = 2, what happens?
>
> y(2) = p(2) + x*y(1) = p(2) + x*p(1)
>
> Look at n = 3.
>
> y(3) = p(3) + x*y(2) = p(3) + x*(p(2) + x*p(1))
>
> = p(3) + P92)*x + p(1)*x^2
>
> Continue until we run out of polynomial coefficients.
>
> See that it really is just Horner's rule, implemented
> as a recursive filter.
>
> John

Thanks John; this helped clear things up.

Adam