Horner Polynomial Evaluation Algorithm

From GM-RKB
(Redirected from Horner's Scheme Algorithm)
Jump to navigation Jump to search

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


References

2021a

$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

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. [1] 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.

  1. 600 years earlier, by the Chinese mathematician Qin Jiushao and 700 years earlier, by the Persian mathematician Sharaf al-Dīn al-Ṭūsī