Horner's Method

Horner's Method

Evaluation of a Polynomial

Let the polynomial of degree n have coefficients .Then has the familiar form

Horner's method (or synthetic division) is a technique for evaluating polynomials.It can be thought of as nested multiplication.For example, the fifth-degree polynomial



can be written in the "nested multiplication" form

.

Theorem (Horner's Method for Polynomial Evaluation)Assume that

(1)

andis a number for which is to be evaluated.Then can be computed recursively as follows.

(2)Set,
and
for.

Then.

Moreover, the coefficientscan be used to constructand

(3)
and
(4),

whereis the quotient polynomial of degreen-1andis the remainder.

Example.Use synthetic division (Horner's method) to find for the polynomial
.
Solution.

Heuristics

In the days when "hand computations" were necessary, the Horner tableau (or table) was used.The coefficientsof the polynomial are entered on the first row in descending order, the second row is reserved for the intermediate computation step()and the bottom row contains the coefficientsand.

Lemma (Horner's Method for Derivatives)Assume that



and is a number for which and are to be evaluated.We have already seen that can be computed recursively as follows.

,and
for.

The quotient polynomial and remainder form the relation

.

We can compute can be computed recursively as follows.

(i),and
for.

The quotient polynomial
and remainderform the relation

(ii).

The Horner tableau (or table) was used for computing the coefficients is given below.

Using vector coefficients

As mentioned above, it is efficient to store the coefficientsof a polynomial of degree n in the vector.Notice that this is a shift of the index for and the polynomialis written in the form

.

Given the value,the recursive formulas for computing the coefficientsand of and , have the new form


for.


for.

Then

Newton-Horner method

Assume that is a polynomial of degree and there exists a number , where .If, then there exists a such that the sequence defined by the Newton-Raphson iteration formula

for

will converge torfor any initial approximation.The recursive formulas in the Lemma can be adapted to computeandand the resulting Newton-Horner iteration formula looks like

for

Algorithm (Newton-Horner Iteration).To find a root ofgiven an initial approximationusing the iteration

for.

Mathematica Subroutine (Newton-Horner Iteration).

Mathematica Subroutine (Newton-Raphson Iteration).

Lemma (Horner's Method for Higher Derivatives)Assume that the coefficientsof a polynomial of degree n are stored in the first row of the matrix.Then the polynomialcan written in the form

.

Given the value,the subroutine for computing all the derivativesis



and

for.

Polynomial Deflation

Given the polynomialin example 5,the iteration



will converge to the rootof.The Mathematica command NewtonHorner[3.0,6] produces the above sequence, then the quotient polynomialis constructed with the command.

The root stored in the computer is located in the variabler1.

The coefficients ofQ[x]printed above have been rounded off.Actually there is a little bit of round off error in the coefficients forming,we will have to dig them out to look at them.

Now we have a computer approximation for the factorization.

We should carry out one more step in the iteration using the commandNewtonHorner[3.0,7]and get a more accurate calculation for the coefficients of.When this is done the result will be:

If the other roots ofare to be found, then they must be the roots of the quotient polynomial.The polynomialis referred to as the deflated polynomial, because its degree is one less than the degree of.For this example it is possible to factoras the product of two quadratic polynomials.Therefore, has the factorization

,

and the five roots ofare

.

This can be determined by using Mathematica and the command Factor.

This still leaves some unanswered questions that we will answer in other modules.The quadratic factors can be determined using the Lin-Bairstow method.Or if one prefers complex arithmetic, then Newton's method can be used.For example, starting with the imaginary numberNewton's method will create a complex sequence converging to the complex rootof.

However, starting with purely imaginary numberwill create a divergent sequence.

For cases involving complex numbers the reader should look at the Lin-Bairstow and the Fundamental Theorem of Algebra modules.

Getting Real Roots

The following example illustrates polynomial deflation and shows that the order in which the roots are located could be important.In light of example 6 we know that better calculations are made for evaluating whenxis small.The Newton-Horner subroutine is modified to terminate early if evaluates close to zero (when a root is located).

Mathematica Subroutine (Newton-Horner Iteration).