Horner scheme

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

In numerical analysis, the Horner scheme (also known as Horner algorithm), named after William George Horner, is an algorithm for the efficient evaluation of polynomials in monomial form.Horner’s method describes a manual process by which one may approximate the roots of a polynomial equation. The Horner scheme can also be viewed as a fast algorithm for dividing a polynomial by a linear polynomial with Ruffini’s rule.

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 x0.

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

 \begin{align} b_n & := a_n \\ b_{n-1} & := a_{n-1} + b_n x_0 \\ & {}\  \  \vdots \\ b_0 & := a_0 + b_1 x_0. \end{align}

Then b0 is the value of p(x0).

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 bi into the expression,

 \begin{align} p(x_0) & = a_0 + x_0(a_1 + x_0(a_2 + \cdots x_0(a_{n-1} + b_n x_0)\cdots)) \\ & = a_0 + x_0(a_1 + x_0(a_2 + \cdots x_0(b_{n-1})\dots)) \\ & {} \ \  \vdots \\ & = a_0 + x_0(b_1) \\ & = b_0. \end{align}

Examples

Evaluate

f(x)=2x^3-6x^2+2x-1\, for x=3\;.

We use synthetic division as follows:

 x₀│   x³    x²    x¹    x⁰
 3 │   2    -6     2    -1
   │         6     0     6    
   └────────────────────────
       2     0     2     5

The entries in the third row are the sum of those in the first two. Each entry in the second row is the product of the x-value (3 in this example) with the third-row entry immediately to the left. The entries in the first row are the coefficients of the polynomial to be evaluated. Then the remainder of f(x) on division by x − 3 is 5.

But by the remainder theorem, we know that the remainder is f(3). Thus f(3) = 5

In this example, if a3 = 2,a2 = − 6,a1 = 2,a0 = − 1 we can see that b3 = 2,b2 = 0,b1 = 2,b0 = 5, the entries in the third row. So, synthetic division is based on Horner Scheme.

As a consequence of the polynomial remainder theorem, the entries in the third row are the coefficients of the second-degree polynomial, the quotient of f(x) on division by x − 3. The remainder is 5. This makes Horner’s method useful for polynomial long division.

Divide x^3-6x^2+11x-6\, by x-2\,:

 2 │   1    -6    11    -6
   │         2    -8     6    
   └────────────────────────
       1    -4     3     0

The quotient is x^2-4x+3\,.

Let f_1(x)=4x^4-6x^3+3x-5\, and f_2(x)=2x-1\,. Divide f_1(x)\, by f_2\,(x) using Horner’s scheme.

  2 │  4    -6    0    3   │   -5
────┼──────────────────────┼───────
  1 │        2   -2   -1   │    1
    │                      │  
    └──────────────────────┼───────
       2    -2    -1   1   │   -4

The third row is the sum of the first two rows, divided by 2. Each entry in the second row is the product of 1 with the third-row entry to the left. The answer is

\frac{f_1(x)}{f_2(x)}=2x^3-2x^2-x+1-\frac{4}{(2x-1)}.

 

Advertisements

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