Horner Polynomial Evaluation Algorithm

A Horner Polynomial Evaluation Algorithm is a Polynomial Evaluation Algorithm that is based on the Horner's Rule:

$a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0=\left(\left(a_nx+a_{n-1}\right)x+\ldots\right)x+a_0$.

• AKA: Horner's Method Algorithm, Horner's Scheme Algorithm.
• Example(s):
  • https://www.geeksforgeeks.org/horners-method-polynomial-evaluation/
  • …
• Counter-Example(s):
  • Clenshaw Algorithm,
  • De Casteljau's Algorithm,
  • De Boor's Algorithm,
  • Estrin's Scheme Algorithm,
  • Lill's Method Algorithm,
  • Ruffini's Rule Algorithm.
• See: Recurrence Relation, Numerical Analysis, Recursion, Polynomial Root-Finding Algorithm, Newton's Method, Mathematics, Computer Science, William George Horner, Joseph-Louis Lagrange, Polynomial.

---

---

References

2021a

• (MathWorld, 2021) ⇒ https://mathworld.wolfram.com/HornersMethod.html Retrieved:2021-9-5.
  • QUOTE: A method for finding roots of a polynomial equation $f(x)=0$. Now find an equation whose roots are the roots of this equation diminished by $r$, so

$0=f(x+r)=f(r)+xf^{\prime}(r)+\dfrac{1}{2}x^2f^{\prime\prime}(r)+\dfrac{1}{3}x^3f^{\prime\prime\prime}(r)+\ldots\quad\quad$ (1)

The expressions for $f\left(r\right),\; f^{\prime}\left(r\right),\; \ldots$ are then found as in the following example, where

$f\left(x\right)=Ax^5+Bx^4+Cx^3+Dx^2+Ex+F.\quad\quad$(2)

Write the coefficients $A, B, \ldots, F$ in a horizontal row, and let a new letter shown as a denominator stand for the sum immediately above it so, in the following example, $P=Ar+B$.

2021b

• (MathWorld, 2021) ⇒ https://mathworld.wolfram.com/HornersRule.html Retrieved:2021-9-5.
  • QUOTE: A rule for polynomial computation which both reduces the number of necessary multiplications and results in less numerical instability due to potential subtraction of one large number from another. The rule simply factors out powers of $x$, giving
    $a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0=\left(\left(a_nx+a_{n-1}\right)x+\ldots\right)x+a_0$.

2021c

• (Wikipedia, 2021) ⇒ https://en.wikipedia.org/wiki/Horner's_method Retrieved:2021-9-5.
  • In mathematics and computer science, Horner's method (or Horner's scheme) is an algorithm for polynomial evaluation. Although named after William George Horner, this method is much older, as it has been attributed to Joseph-Louis Lagrange by Horner himself, and can be traced back many hundreds of years to Chinese and Persian mathematicians. After the introduction of computers, this algorithm became fundamental for computing efficiently with polynomials. The algorithm is based on Horner's rule: :

    [math]\displaystyle{ \begin{align} a_0 &+ a_1x + a_2x^2 + a_3x^3 + \cdots + a_nx^n \\ &= a_0 + x \bigg(a_1 + x \Big(a_2 + x \big(a_3 + \cdots + x(a_{n-1} + x \, a_n) \cdots \big) \Big) \bigg). \end{align} }[/math]

    This allows the evaluation of a polynomial of degree with only [math]\displaystyle{ n }[/math] multiplications and [math]\displaystyle{ n }[/math] additions. This is optimal, since there are polynomials of degree that cannot be evaluated with fewer arithmetic operations

    Alternatively, Horner's method also refers to a method for approximating the roots of polynomials, described by Horner in 1819. It is a variant of the Newton–Raphson method made more efficient for hand calculation by the application of Horner's rule. It was widely used until computers came into general use around 1970.

---