Editing Horner's method (section)

{{short description|Algorithm for polynomial evaluation}}
{{cleanup|reason = See [[Talk:Horner's method#This Article is about Two Different Algorithms]]|date=November 2018}}

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.<ref>600 years earlier, by the Chinese mathematician [[Qin Jiushao]] and 700 years earlier, by the Persian mathematician [[Sharaf al-Dīn al-Ṭūsī]]</ref> After the introduction of computers, this algorithm became fundamental for computing efficiently with polynomials.

The algorithm is based on '''Horner's rule''', in which a polynomial is written in ''nested form'':
<math display="block">\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 {{mvar|n}} with only <math>n</math> multiplications and <math>n</math> additions. This is optimal, since there are polynomials of degree {{mvar|n}} that cannot be evaluated with fewer arithmetic operations.<ref>{{harvnb|Pan|1966}}</ref>

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