How is Horner’s method linked to synthetic division?

Horner’s method is a computationally efficient algorithm for evaluating a polynomial at a certain point or value.

But how does Horner’s method link to synthetic division? The process of Horner’s method gives coefficients that are identical in the synthetic division. But why? does Horner’s algorithm give the coefficients of the quotient of the polynomial divided by the linear division that it is evaluated at.

http://en.wikipedia.org/wiki/Horner_scheme

Description of the algorithm

Given the polynomial

p(x) = \sum_{i=0}^n a_i x^i = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n,

where a_0, \ldots, a_n are real numbers, we wish to evaluate the polynomial at a specific value of x, say x_0.

To accomplish this, we define a new sequence of constants as follows:

b_n := a_n

b_{n-1} :=a_{n-1}+b_n x_0

b_0 :=a_0+b_1 x_0

Then b_0 is the value of p(x_0).

To see why this works, note that the polynomial can be written in the form

p(x) = a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n-1} + a_n x)\cdots)). \,

Thus, by iteratively substituting the b_i into the expression,

p(x_0)=a_0+x_0(a_1+x_0(a_2+...+x_0(a_{n-1}+b_n x_0)...))

=a_0+x_0(a_1+x_0(a_2+...+x_0(b_{n-1})...)) = ... =a_0+x_0(b_1) =b_0.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s