Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!q14g2000vbn.googlegroups.com!not-for-mail
From: Adam Attarian <adam.attarian@gmail.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Question on evaluating polynomials/polyval
Date: Tue, 16 Jun 2009 14:35:08 -0700 (PDT)
Organization: http://groups.google.com
Lines: 74
Message-ID: <c6b70560-59be-4dc2-af17-7cd2346bd6c4@q14g2000vbn.googlegroups.com>
References: <d8a640f2-ec55-4e7c-bc30-ef3249f46abf@j12g2000vbl.googlegroups.com> 
	<h190fu$fcd$1@fred.mathworks.com>
NNTP-Posting-Host: 69.134.147.254
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1245188108 23113 127.0.0.1 (16 Jun 2009 21:35:08 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Tue, 16 Jun 2009 21:35:08 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: q14g2000vbn.googlegroups.com; posting-host=69.134.147.254; 
	posting-account=b5XPCgoAAACMm0vaAgzmCW_FglXLm79I
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10_5_7; en-us) 
	AppleWebKit/530.17 (KHTML, like Gecko) Version/4.0 Safari/530.17,gzip(gfe),gzip(gfe)
Xref: news.mathworks.com comp.soft-sys.matlab:548098


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