Horner scheme Guide, Meaning , Facts, Information and Description

In the mathematical subfield of numerical analysis the Horner scheme or Horner algorithm, named after William George Horner, is an algorithm for the efficient evaluation of polynomials in monomial form.

Table of contents

1 History 2 Basic idea 3 Horner algorithm 4 Application 5 See also

History

Even though it is named after William George Horner, who described the algorithm in 1819, it was already known to Isaac Newton in 1669 and even to the Chinese mathematician Ch'in Chiu-Shao around 1200s.

Basic idea

Assume we want to evaluate the polynomial in the monomial form

for given a₀,...,a_n. That is we want to know

for a given x. When using the monomial form of the polynomial we we need n additions and n²+n/2 multiplications for the calculation of p(x). Our aim is to decrease the number of multplications because they are slow and numerically instable compared to the additions. The Horner algorithm rearranges the polynomial into the recursive form

and then evalutes the polynomial recursivly using only n additions and n mulitplications. Additionally it is numerically more stable because we eliminated some multiplications. Alternatively it could be computed with n fused multiply-adds.

Horner algorithm

Given the polynomial

we rearrange it into

Then starting from the innermost parentheses and working outwards we define

If we put the b_n in the polynomial we see that

so b₀ is the is the value of the polynomial p at x.

Application

The Horner scheme is often used to convert between different positional numeral systems (in which case x is the base of the number system, and the a_i are the digits) and can also be used if x is a matrix, in which case the gain is even larger.

The Horner scheme can also be viewed as a fast algorithm for dividing a polynomial by a linear polynomial (see Ruffini's rule).

See also

• Clenshaw algorithm to evaluate polynomials in Chebyshev form
• De Casteljau's algorithm to evalute polynomials in Bézier form

This is an Article on Horner scheme. Page Contains Information, Facts Details or Explanation Guide About Horner scheme

	Web www.E-paranoids.com