Horner's scheme

Horner's scheme (or Horner's rule, Horner 's method, Ruffini-Horner's method ) is an algorithm for calculating the value of a polynomial written as the sum of monomials (monomials) for a given value of a variable. Horner's method allows finding the roots of the polynomial ^[1] , as well as calculating the derivatives of the polynomial at a given point. Horner's scheme is also a simple algorithm for dividing a polynomial by a bin of the form $x-c$ ${\ displaystyle xc}$ $x-c$ . The method is named after William George Horner , but Paolo Ruffini was 15 years ahead of Horner, and the Chinese knew this method in the 13th century.

Algorithm Description

Polynomial given

P(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\ldots +a_{n}x^{n},\quad a_{i}\in \mathbb {R} .

{\ displaystyle P (x) = a_ {0} + a_ {1} x + a_ {2} x ^ {2} + a_ {3} x ^ {3} + \ ldots + a_ {n} x ^ {n }, \ quad a_ {i} \ in \ mathbb {R}.}

P(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\ldots +a_{n}x^{n},\quad a_{i}\in \mathbb {R} .

Let it be required to calculate the value of a given polynomial for a fixed value $x=x_{0}$ ${\ displaystyle x = x_ {0}}$ $x = x_0$ . Imagine a polynomial $P(x)$ ${\ displaystyle P (x)}$ $P(x)$ in the following form:

P(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots x(a_{n-1}+a_{n}x)\dots )).

{\ displaystyle P (x) = a_ {0} + x (a_ {1} + x (a_ {2} + \ cdots x (a_ {n-1} + a_ {n} x) \ dots)).}

P(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots x(a_{n-1}+a_{n}x)\dots )).

We define the following sequence:

b_{n}=a_{n},

{\ displaystyle b_ {n} = a_ {n},}

b_{n}=a_{n},

b_{n-1}=a_{n-1}+b_{n}x_{0},

{\ displaystyle b_ {n-1} = a_ {n-1} + b_ {n} x_ {0},}

b_{n-1}=a_{n-1}+b_{n}x_{0},

...

b_{i}=a_{i}+b_{i+1}x_{0},

{\ displaystyle b_ {i} = a_ {i} + b_ {i + 1} x_ {0},}

b_{i}=a_{i}+b_{i+1}x_{0},

...

b_{0}=a_{0}+b_{1}x_{0}.

{\ displaystyle b_ {0} = a_ {0} + b_ {1} x_ {0}.}

b_{0}=a_{0}+b_{1}x_{0}.

Sought value $P(x_{0})$ ${\ displaystyle P (x_ {0})}$ $P(x_{0})$ there is $b_{0}$ ${\ displaystyle b_ {0}}$ $b_{0}$ . We show that this is so.

In the received entry form $P(x)$ ${\ displaystyle P (x)}$ $P(x)$ substitute $x=x_{0}$ ${\ displaystyle x = x_ {0}}$ $x = x_0$ and we will calculate the value of the expression, starting with the inner brackets. To do this, we will replace the subexpressions through $b_{i}$ ${\ displaystyle b_ {i}}$ $b_{i}$ :

{\begin{aligned}P(x_{0})&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}(a_{n-1}+a_{n}x_{0})\dots ))=\\&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}b_{n-1}\dots ))=\\&~~\vdots \\&=a_{0}+x_{0}b_{1}=\\&=b_{0}.\end{aligned}}

{\ displaystyle {\ begin {aligned} P (x_ {0}) & = a_ {0} + x_ {0} (a_ {1} + x_ {0} (a_ {2} + \ cdots x_ {0} ( a_ {n-1} + a_ {n} x_ {0}) \ dots)) = \\ & = a_ {0} + x_ {0} (a_ {1} + x_ {0} (a_ {2} + \ cdots x_ {0} b_ {n-1} \ dots)) = \\ & ~~ \ vdots \\ & = a_ {0} + x_ {0} b_ {1} = \\ & = b_ {0} . \ end {aligned}}}

{\begin{aligned}P(x_{0})&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}(a_{n-1}+a_{n}x_{0})\dots ))=\\&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}b_{n-1}\dots ))=\\&~~\vdots \\&=a_{0}+x_{0}b_{1}=\\&=b_{0}.\end{aligned}}

Using Horner's scheme for dividing a polynomial by a bin

When dividing a polynomial $a_{0}x^{n}+a_{1}x^{n-1}+\cdots +a_{n-1}x+a_{n}$ ${\ displaystyle a_ {0} x ^ {n} + a_ {1} x ^ {n-1} + \ cdots + a_ {n-1} x + a_ {n}}$ on $x-c$ ${\ displaystyle xc}$ it turns out a polynomial $b_{0}x^{n-1}+b_{1}x^{n-2}+\cdots +b_{n-2}x+b_{n-1}$ ${\ displaystyle b_ {0} x ^ {n-1} + b_ {1} x ^ {n-2} + \ cdots + b_ {n-2} x + b_ {n-1}}$ with the remainder $b_{n}$ ${\ displaystyle b_ {n}}$ .

Moreover, the coefficients of the resulting polynomial satisfy the recurrence relations

b_{0}=a_{0},\quad b_{k}=a_{k}+cb_{k-1}.

{\ displaystyle b_ {0} = a_ {0}, \ quad b_ {k} = a_ {k} + cb_ {k-1}.}

In the same way, one can determine the multiplicity of roots (use the Horner scheme for a new polynomial). Also, the scheme can be used to find the coefficients in the expansion of the polynomial in powers $(x-c)$ ${\ displaystyle (xc)}$ :

P(x)=A_{0}+A_{1}(x-c)+A_{2}(x-c)^{2}+\cdots +A_{n}(x-c)^{n}.

{\ displaystyle P (x) = A_ {0} + A_ {1} (xc) + A_ {2} (xc) ^ {2} + \ cdots + A_ {n} (xc) ^ {n}.}

Use

Calculate $f(x)=2x^{3}-6x^{2}+2x-1$ ${\ displaystyle f (x) = 2x ^ {3} -6x ^ {2} + 2x-1}$ for $x=3.$ ${\ displaystyle x = 3.}$ We use synthetic division:

  x ₀│ x ³ x ² x ¹ x ⁰
  3 │ 2 −6 2 −1
    │ 6 0 6
    └─────────────────────────
        2 0 2 5

Here, in the first line, the value x0 and the coefficients of the polynomial are written.

The values (in columns) in the third row correspond to the sum of the values of the first and second rows ( $b_{n-1}=a_{n-1}+b_{n}x_{0}$ ${\ displaystyle b_ {n-1} = a_ {n-1} + b_ {n} x_ {0}}$ ), and the values of the second row are the product of x by the value in the third row of the previous column ( $b_{n}x_{0}$ ${\ displaystyle b_ {n} x_ {0}}$ )

For example, if $a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1$ ${\ displaystyle a_ {3} = 2, a_ {2} = - 6, a_ {1} = 2, a_ {0} = - 1}$ we see that $b_{3}=2,b_{2}=0,b_{1}=2,b_{0}=5$ ${\ displaystyle b_ {3} = 2, b_ {2} = 0, b_ {1} = 2, b_ {0} = 5}$ - The values in the third row. So synthetic fission is based on the Horner method.

Divide $x^{3}-6x^{2}+11x-6$ ${\ displaystyle x ^ {3} -6x ^ {2} + 11x-6}$ on $x-2$ ${\ displaystyle x-2}$ :

  2 │ 1 −6 11 −6
    │ 2 −8 6
    └─────────────────────────
        1 −4 3 0

New polynomial $x^{2}-4x+3$ ${\ displaystyle x ^ {2} -4x + 3}$ .

Let be $f_{1}(x)=4x^{4}-6x^{3}+3x-5$ ${\ displaystyle f_ {1} (x) = 4x ^ {4} -6x ^ {3} + 3x-5}$ and $f_{2}(x)=2x-1$ ${\ displaystyle f_ {2} (x) = 2x-1}$ . Divide $f_{1}(x)$ ${\ displaystyle f_ {1} (x)}$ on $f_{2}\,(x)$ {\ displaystyle f_ {2} \, (x)} using Horner's method.

  2 │ 4 −6 0 3 │ −5
 ────┼───────────────────────────────
   1 │ 2 −2 −1 │ 1
     └───────────────────────────────
        2 −2 −1 1 │ −4

The third line is the sum of the first two divided by two. Each value of the second row matches the value of the third row in the previous column. Division answer:

{\frac {f_{1}(x)}{f_{2}(x)}}=2x^{3}-2x^{2}-x+1-{\frac {4}{2x-1}}.

{\ displaystyle {\ frac {f_ {1} (x)} {f_ {2} (x)}} = 2x ^ {3} -2x ^ {2} -x + 1 - {\ frac {4} {2x -one}}.}

Using Horner's scheme, you can also calculate the value of a number in a positional calculus.

Notes

↑ If the integer polynomial has integer roots, then they will be found among the divisors of the free term. Kurosh A. G. § 57. Rational roots of integer polynomials // Course of higher algebra . - The science. - Moscow, 1968.

Literature

Levitin A. V. Chapter 6. Transformation method: Horner scheme and exponentiation // Algorithms. Introduction to the development and analysis - M .: Williams , 2006. - S. 284–291. - 576 p. - ISBN 978-5-8459-0987-9
<a href=" https://wikidata.org/wiki/Track:Q21694518 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21694521 "</a> <a href = " https://wikidata.org/wiki/Track:Q21694522 "> </a>
Volkov EA. § 2. Calculation of polynomial values. Horner's scheme // Computational methods. - Textbook. manual for universities. - 2nd ed., Rev. - M .: Nauka, 1987 .-- 248 p.
S. B. Gashkov. § 14. Horner's scheme and translation from one positional system to another // Number systems and their application . - M .: ICMMO , 2004 .-- S. 37-39. - (Library "Mathematical Education"). - ISBN 5-94057-146-8 .

Links

Horner's scheme
The calculation of multidimensional polynomials is a generalization of the Horner scheme to the case of a polynomial in several variables.
Horner Method in a Complex Field

[корни-1] If the integer polynomial has integer roots, then they will be found among the divisors of the free term. Kurosh A. G. § 57. Rational roots of integer polynomials // Course of higher algebra . - The science. - Moscow, 1968.