Horner scheme

The Horner scheme (based on William George Horner ) is a transformation method for polynomials to facilitate the calculation of function values. It can be used to simplify the polynomial division and the calculation of zeros and derivatives .

definition

For a polynomial of degree from any polynomial ring , the Horner scheme is defined as: ${\displaystyle p(x)=b_{0}+b_{1}x+b_{2}x^{2}+\dotsb +b_{n}x^{n}}$ ${\displaystyle n}$

${\displaystyle p(x)=(\dotso (b_{n}x+b_{n-1})x+\dotsb )x+b_{0}.}$

Function of the Horner scheme

Computing advantages

For polynomials in the classical style, which must potencies , etc. calculated when the function value at one point to be calculated. In the transformed polynomial according to the Horner scheme, there are no powers, only multiplication and addition . The calculation is accelerated because fewer multiplications are required: the number of these is reduced to almost half by using the Horner scheme. ${\displaystyle a^{2}}$ ${\displaystyle a^{3}}$ ${\displaystyle x=a}$

In the classical notation, multiplications are necessary for a polynomial of degree : ${\displaystyle 2n-1}$ ${\displaystyle n}$

• ${\displaystyle n-1}$Multiplications to form the powers ; ${\displaystyle x^{2},\,x^{3},\dotsc ,x^{n}}$
• further multiplications to multiply the powers by their coefficients. ${\displaystyle n}$ ${\displaystyle x,\,x^{2},\,x^{3},\dotsc ,x^{n}}$

Overall, you therefore need multiplications for the calculation. ${\displaystyle 2n-1}$

In the Horn scheme, however, one gets by with multiplications. ${\displaystyle n}$

The number of - arithmetically less complex - additions is the same in both cases, namely . ${\displaystyle n}$

Procedure

By continuing to exclude the free polynomial variables , the polynomial is displayed as a nesting of products and sums. ${\displaystyle x}$

example

The following example illustrates the lower computational effort in the Horn scheme:

${\displaystyle 11+7x-5x^{2}-4x^{3}+2x^{4}\;=\;(((2\cdot x-4)\cdot x-5)\cdot x+7)\cdot x+11}$

In the classic representation (left side), in addition to the additions, subtractions and multiplications, four powers are formed, which are recorded by the multiplications by using the Horner scheme (right side) and are therefore omitted. If the intermediate results are reused, this saves four multiplications.

application

In analysis , the values ​​of a polynomial and its derivative often have to be calculated: be it to determine a zero, to discuss a curve or to sketch a graph.

The form shown here is particularly suitable for calculating in the reverse Polish notation (UPN) .

Between 1975 and 2003 income tax in the FRG was calculated according to the Horner scheme in order to avoid rounding errors when calculating with electronic pocket calculators or computers and thus to ensure legal security.

Tabular notation of the Horn scheme

Derivation

Let's look at the above example again and put:

${\displaystyle \alpha \;:=}$	${\displaystyle \;\;2}$
${\displaystyle \beta \;:=}$	${\displaystyle \;\,\;2\cdot x-4=\alpha \cdot x-4}$
${\displaystyle \gamma \;:=}$	${\displaystyle \;\;(2\cdot x-4)\cdot x-5=\beta \cdot x-5}$
${\displaystyle \delta \;:=}$	${\displaystyle \;((2\cdot x-4)\cdot x-5)\cdot x+7=\gamma \cdot x+7}$
${\displaystyle \epsilon \;:=}$	${\displaystyle (((2\cdot x-4)\cdot x-5)\cdot x+7)\cdot x+11=\delta \cdot x+11}$

The coefficients, intermediate products and partial sums are now transferred to a three-line table, with the coefficients being entered in the first line. The subtotals are in the third line. The first coefficient of the polynomial is taken over directly. The previously calculated partial sum multiplied by results in the next summand, which is then entered in the second line under the following coefficients. ${\displaystyle x}$

So you gradually get the following calculation scheme:

${\displaystyle {\,2}}$

${\displaystyle {\,-4}}$

${\displaystyle {\,-5}}$

${\displaystyle {\,7}}$

${\displaystyle {\,11}}$

${\displaystyle {\Bigg \downarrow }}$

${\displaystyle +}$

${\displaystyle +}$

${\displaystyle +}$

${\displaystyle +}$

${\displaystyle \,\alpha x}$

${\displaystyle \,\beta x}$

${\displaystyle \,\gamma x}$

${\displaystyle \,\delta x}$

${\displaystyle \nearrow }$

${\displaystyle \mid }$

${\displaystyle \nearrow }$

${\displaystyle \mid }$

${\displaystyle \nearrow }$

${\displaystyle \mid }$

${\displaystyle \nearrow }$

${\displaystyle \mid }$

${\displaystyle \cdot {x}}$

${\displaystyle {=}}$

${\displaystyle \cdot {x}}$

${\displaystyle {=}}$

${\displaystyle \cdot {x}}$

${\displaystyle {=}}$

${\displaystyle \cdot {x}}$

${\displaystyle {=}}$

${\displaystyle \nearrow }$

${\displaystyle \downarrow }$

${\displaystyle \nearrow }$

${\displaystyle \downarrow }$

${\displaystyle \nearrow }$

${\displaystyle \downarrow }$

${\displaystyle \nearrow }$

${\displaystyle \downarrow }$

${\displaystyle {\,2=\alpha }}$

${\displaystyle {\,\alpha x-4=\beta }}$

${\displaystyle {\,\beta x-5=\gamma }}$

${\displaystyle {\,\gamma x+7=\delta }}$

${\displaystyle {\,\delta x+11=\epsilon }}$

example

The calculation of the above polynomial for with the help of the Horner scheme is as follows: ${\displaystyle x=2}$

	2	−4	−5	7th	11
2)		4th	0	−10	−6
	2	0	−5	−3	5

As a reminder, the value for which the polynomial is to be calculated is usually written in the middle line in front of the scheme, the first number in the upper line is also written in the lower line. Then you multiply this number by the value for which you want to calculate the polynomial, write the result in the middle line of the second column, add the two values ​​in the second column and write the result in the bottom line. Then the column sum from the bottom line is repeatedly multiplied by the value for which the polynomial is to be calculated and the result is written in the middle line of the next column, the column is added, etc. The last number (here five) is the final result.

However , there are much higher interim results for: ${\displaystyle x=5}$

	2	−4	−5	7th	11
5)		10	30th	125	660
	2	6th	25th	132	671

Using the cascaded Horner scheme ( see below ) increases the number of multiplications, but reduces the intermediate results, which is more advantageous for calculating the polynomial by hand:

			2
		06	−4
		25th	−5
	13	32	7th
06	17th	71	11
6th	7th	1	(5)

Possible uses of the Horn schema

Conversion between different number systems

Our familiar representation of numbers in the decimal place value system is nothing more than an abbreviated notation for special polynomials, namely polynomials with the base . The same applies to all other place value systems, for example the binary system . There is . We can take advantage of the Horner scheme to convert numbers from any other place value system to the decimal system, and vice versa. ${\displaystyle x=10}$ ${\displaystyle x=2}$

Conversion to the decimal system

Example: The binary number 110101 is to be converted into the decimal system. What is the resulting decimal number ? ${\displaystyle d}$

We write 110101 in _binary as a polynomial:

${\displaystyle P_{110101}(x)=1\cdot x^{5}+1\cdot x^{4}+0\cdot x^{3}+1\cdot x^{2}+0\cdot x^{1}+1\cdot x^{0}}$

so is

${\displaystyle \mathrm {d} =P_{110101}(2)=1\cdot 2^{5}+1\cdot 2^{4}+0\cdot 2^{3}+1\cdot 2^{2}+0\cdot 2^{1}+1\cdot 2^{0}}$

According to the Horner scheme:

${\displaystyle \mathrm {d} =((((1\cdot 2+1)\cdot 2+0)\cdot 2+1)\cdot 2+0)\cdot 2+1}$

We don't need to calculate this in one go, but can proceed step by step. Each step consists of a multiplication by 2 and an addition. For the sake of clarity, we write the steps one below the other and note the intermediate results:

${\displaystyle {\begin{matrix}d_{0}&=&&&&&1&&{\text{(1. Ziffer)}}\\d_{1}&=&d_{0}\cdot 2+1&=&1\cdot 2+1&=&3&&{\text{(2. Ziffer)}}\\d_{2}&=&d_{1}\cdot 2+0&=&3\cdot 2+0&=&6&&{\text{(3. Ziffer)}}\\d_{3}&=&d_{2}\cdot 2+1&=&6\cdot 2+1&=&13&&{\text{(4. Ziffer)}}\\d_{4}&=&d_{3}\cdot 2+0&=&13\cdot 2+0&=&26&&{\text{(5. Ziffer)}}\\d_{5}&=&d_{4}\cdot 2+1&=&26\cdot 2+1&=&53&&{\text{(6. Ziffer)}}\\\mathbf {d} &=&d_{5}&&&=&\mathbf {53} \\\end{matrix}}}$

We have found the decimal representation we were looking for.

In general terms, the procedure is as follows: A number from a place value system is converted into the decimal system by adding ${\displaystyle x}$

• the value of the first digit is taken as the initial value
• then gradually multiply the result from the previous step by and add the next digit ${\displaystyle x}$
• until all digits are used up.

The easiest way to write down the invoice again in tabular form:

	1	1	0	1	0	1
2)		2	6th	12	26th	52
	1	3	6th	13	26th	53

Cascaded Horner scheme

The disadvantage of the one-step Horner scheme is that multiplications with large factors can be necessary (in the above example 2 * 26 = 52). To stay within the multiplication table, the cascaded or multi-level Horner scheme is used.

Only the one is used for the multiplication. The tens is written like a carry over to the next line under the ones. With the 13 from the example above, the 3 is written under the 12 and the 1 under the 3. In the next step, only 3 * 2 + 0 = 6 is calculated (instead of 13 * 2 + 0 = 26). This result is treated as well; the tens here is 0. The last calculation (6 * 2 + 1) results in 13. The one of this result is the last digit of the final result.

	1	1	0	1	0	1
2)		2	6th	12	6th	12
	1	3	6th	3	6th	3
		0	0	1	0	1

To calculate the other digits, the same scheme is used again for the tens (00101) in the last line. The leading zeros can be neglected:

	1	1	0	1	0	1
2)		2	6th	12	6th	12
	1	3	6th	3	6th	3
		0	0	1	0	1
2)					2	4th
				1	2	5
					0	0

Since there are now only zeros in the carry line, the process is ended. The total result (53) is read in the last column of the units from bottom to top.

Simplified notation

The cascaded Horner scheme can be represented in a very simplified way by doing a little more mental arithmetic. This speeds up the calculation considerably.

The digits of the initial number are first written vertically one below the other. A vertical line is drawn to the left of it. Below the last digit a horizontal line, below which the result is at the end.

First the most significant digit (the first 1) is transferred one line lower into the previous column. This is now to the left of the second digit (also a 1). The left number is multiplied by the number base (here 2), the right number is added (1 * 2 + 1). The tens of the result (3) is written one column further to the left, the one one line lower.

The same procedure is followed with the one of the result (3) and the next digit (0). The result (3 * 2 + 0 = 6) is noted in the same way as the previous result.

The third calculation is 6 * 2 + 1 = 13, then 3 * 2 + 0 = 6 and finally 6 * 2 + 1 = 13 again. As in the previous steps, the ones and tens of the result are written diagonally below each other.

The last digit of the final result (3) is now under the horizontal line.

1         1         0         1         0         1         (2)

1       1 1         0         1         0         1         (2)

1     0 1 1       3 0         1         0         1         (2)

1     0 1 1     0 3 0       6th 1         0         1         (2)

1     0 1 1     0 3 0     1 6th 1       3 0         1         (2)

1     0 1 1     0 3 0     1 6th 1     0 3 0       6th 1         (2)

1     0 1 1     0 3 0     1 6th 1     0 3 0     1 6th 1       3 (2)

To calculate the other digits, the leading column with the tens that have not been taken into account so far is now treated in the same way as the starting number.

The first valid digit is transferred one line down to the previous column. This number (1) is multiplied by the base (2) and the next digit (0) is added to the product (2). Tens and ones of the result (02) are entered diagonally in the scheme as shown above.

The result of the last calculation (2 * 2 + 1 = 05) is also entered. The ones of this result (5) are the next digit of the final result.

1     0 1 1     0 3 0     1 6th 1     0 3 0     1 6th 1       3 (2)

1     0 1 1     0 3 0     1 6th 1   1 0 3 0     1 6th 1       3 (2)

1     0 1 1     0 3 0     1 6th 1 0 1 0 3 0   2 1 6th 1       3 (2)

1     0 1 1     0 3 0     1 6th 1 0 1 0 3 0 0 2 1 6th 1   5   3 (2)

1     0 1 1     0 3 0     1 6th 1 0 1 0 3 0 0 2 1 6th 1   5   3 (2)

Since there are only zeros in the tens column, the calculation is over. The final result (53) can now be read in the result line, this time in the correct order.

Procedure for the reverse direction

In the opposite way, a decimal number can be converted into a number in another number system. Instead of a continued multiplication by the base of the other number system, there is a continued division by this number. The digits of the number in the other number system result from right to left by the division remainders.

In the table notation, the digits of the output number are written one below the other and a horizontal line is drawn for the result. The vertical line is drawn here to the right of the digits. As a reminder, the number base can be noted at the bottom right.

	5
	3
		(2)

The first digit, increased by a leading zero, (05) is divided by the number base (2). The quotient (2) is written in the previous column. The rest (1) in the line below.

05     3       (2)

2 05     1 3       (2)

This remainder forms a new two-digit number (13) with the next digit (3). This number is again divided by the base, the result (6 remainder 1) is entered diagonally in the scheme as above.

2 05     13       (2)

2 05   6th 13     1 (2)

Since all digits have now been processed, the remainder of the last calculation (1) is the last digit of the final result.

The quotients that have not been edited are treated as a new decimal number (26) using the same procedure.

02 05     6th 13       1 (2)

1 02 05     0 6 13       1 (2)

1 02 05     06 13       1 (2)

1 02 05   3 06 13     0 1 (2)

The digit obtained is a 0. There is now a 13 in the column of the unprocessed quotients.

01 02 05     3 06 13       0 1 (2)

0 01 02 05     1 3 06 13       0 1 (2)

0 01 02 05     13 06 13       0 1 (2)

0 01 02 05   6th 13 06 13     1 0 1 (2)

After this step there is a 06 in the quotient column. The leading zero is ignored, the process starts with the 6th.

0 01 02 05     06 13 06 13       1 0 1 (2)

0 01 02 05   3 06 13 06 13     0 1 0 1 (2)

The number to deal with now is 3.

0 01 02 05     03 06 13 06 13       0 1 0 1 (2)

0 01 02 05   1 03 06 13 06 13     1 0 1 0 1 (2)

Now there is only one 1 left.

0 01 02 05     01 03 06 13 06 13       1 0 1 0 1 (2)

0 01 02 05   0 01 03 06 13 06 13     1 1 0 1 0 1 (2)

0 01 02 05   0 01 03 06 13 06 13     1 1 0 1 0 1 (2)

After the last calculation there is a 0 in the quotient column. The procedure is now complete. The number you are looking for is in the correct order in the result line.

Polynomial division

Polynomial division with linear divisor

Using the following example

${\displaystyle (x^{5}-4x^{4}+4x^{3}+3x^{2}-8x+4)\,:\,({x-2})}$

First the polynomial division is represented with a linear divisor in the Horner scheme.

The polynomial division is usually done in a written form.

${\displaystyle {\begin{matrix}{}&(1x^{5}&-4x^{4}&+4x^{3}&+3x^{2}&-8x&+4)&:&({1x-2})={1x^{4}-2x^{3}+0x^{2}+3x-2}\\-(&{\underline {1x^{5}}}&{\underline {-2x^{4}}})\\&&-2x^{4}\\&-(&{\underline {-2x^{4}}}&{\underline {+4x^{3}}})\\&&&0x^{3}\\&&-(&{\underline {0x^{3}}}&{\underline {-0x^{2}}})\\&&&&3x^{2}\\&&&-(&{\underline {3x^{2}}}&{\underline {-6x}})\\&&&&&-2x\\&&&&-(&{\underline {-2x}}&{\underline {+4}})\\&&&&&&0\\\end{matrix}}}$

If you omit the powers of , you get the following representation: ${\displaystyle x}$

(	1	−4	4th	3	−8	4th	)	:	( 1	−2	)	=	1	−2	0	3	−2
- (	1	−2	)
		−2
	- (	−2	4th	)
			0
		- (	0	0	)
				3
			- (	3	−6	)
					−2
				- (	−2	4th	)
						0

If you now condense this scheme onto three lines and transfer the first coefficient of the dividend to the third line, you get:

(	1	−4	4th	3	−8	4th	)	:	( 1	−2	)
	−2	4th	0	−6	4th	)
	1	−2	0	3	−2	0

As you can see now, the values ​​underlined twice in the last line are the coefficients of the result polynomial and the last value behind is the remainder of the division (here zero).

If you multiply the sign in the second line, the calculation is carried out as follows:

${\displaystyle {\,1}}$

${\displaystyle {\,-4}}$

${\displaystyle {\,4}}$

${\displaystyle {\,3}}$

${\displaystyle {\,-8}}$

${\displaystyle {\,4}}$

${\displaystyle {\Bigg \downarrow }}$

${\displaystyle +}$

${\displaystyle +}$

${\displaystyle +}$

${\displaystyle +}$

${\displaystyle +}$

${\displaystyle \,2}$

${\displaystyle \,-4}$

${\displaystyle \,0}$

${\displaystyle \,6}$

${\displaystyle \,-4}$

${\displaystyle \nearrow }$

${\displaystyle \mid }$

${\displaystyle \nearrow }$

${\displaystyle \mid }$

${\displaystyle \nearrow }$

${\displaystyle \mid }$

${\displaystyle \nearrow }$

${\displaystyle \mid }$

${\displaystyle \nearrow }$

${\displaystyle \mid }$

${\displaystyle \cdot {2}}$

${\displaystyle {=}}$

${\displaystyle \cdot {2}}$

${\displaystyle {=}}$

${\displaystyle \cdot {2}}$

${\displaystyle {=}}$

${\displaystyle \cdot {2}}$

${\displaystyle {=}}$

${\displaystyle \cdot {2}}$

${\displaystyle {=}}$

${\displaystyle \nearrow }$

${\displaystyle \downarrow }$

${\displaystyle \nearrow }$

${\displaystyle \downarrow }$

${\displaystyle \nearrow }$

${\displaystyle \downarrow }$

${\displaystyle \nearrow }$

${\displaystyle \downarrow }$

${\displaystyle \nearrow }$

${\displaystyle \downarrow }$

${\displaystyle {\,1}}$

${\displaystyle {\,-2}}$

${\displaystyle {\,0}}$

${\displaystyle {\,3}}$

${\displaystyle {\,-2}}$

${\displaystyle {\,0}}$

If you now note the reversed sign of the absolute term of the divisor in front of the scheme, you get the general representation of the Horner scheme:

	1	−4	4th	3	−8	4th
2)		2	−4	0	6th	−4
	1	−2	0	3	−2	0

The above example can now be summarized in the following formula:

Has the division task:

${\displaystyle (a_{n}x^{n}+a_{n-1}x^{n-1}+\dotsb +a_{2}x^{2}+a_{1}x^{1}+a_{0}):(x+d)}$

as a result

${\displaystyle e_{n-1}x^{n-1}+e_{n-2}x^{n-2}+\dotsb +e_{2}x^{2}+e_{1}x^{1}+e_{0},{\mbox{ mit dem Rest }}r}$

the coefficients are determined according to the following rule:

${\displaystyle {\begin{matrix}e_{n-1}&=&a_{n}\\e_{k}&=&a_{k+1}-d\cdot e_{k+1},&{\text{für }}k=n-2,n-3,\dotsc ,1,0\\r&=&a_{0}-d\cdot e_{0}\\\end{matrix}}}$

The Horner scheme is then as follows:

	${\displaystyle \,a_{n}}$	${\displaystyle \,a_{n-1}}$	${\displaystyle \,a_{n-2}}$	${\displaystyle \dotso }$	${\displaystyle \,a_{2}}$	${\displaystyle \,a_{1}}$	${\displaystyle \,a_{0}}$
${\displaystyle {-d\,})}$		${\displaystyle -d\,e_{n-1}}$	${\displaystyle -d\,e_{n-2}}$	${\displaystyle \dotso }$	${\displaystyle -d\,e_{2}}$	${\displaystyle -d\,e_{1}}$	${\displaystyle -d\,e_{0}}$
	${\displaystyle \,e_{n-1}}$	${\displaystyle \,e_{n-2}}$	${\displaystyle \,e_{n-3}}$	${\displaystyle \dotso }$	${\displaystyle \,e_{1}}$	${\displaystyle \,e_{o}}$	${\displaystyle \,r}$

Note: With this result, the calculation can function values of a polynomial on the site also derived as follows: ${\displaystyle P}$ ${\displaystyle a}$ Let's look at the division through ${\displaystyle P(x)}$ ${\displaystyle {x-a}}$ ${\displaystyle {\frac {P(x)}{(x-a)}}=E(x)+{\frac {r}{x-a}}}$ ${\displaystyle \Rightarrow P(x)={(x-a)}E(x)+{r}}$ ${\displaystyle \Rightarrow P(a)=0\cdot E(a)+{r}=r}$

Polynomial division with a divisor of the 2nd degree

Has the division task:

${\displaystyle (a_{n}x^{n}+a_{n-1}x^{n-1}+\dotsb +a_{2}x^{2}+a_{1}x^{1}+a_{0}):(x^{2}+d_{1}x+d_{0})}$

as a result

${\displaystyle e_{n-2}x^{n-2}+e_{n-3}x^{n-3}+\dotsb +e_{2}x^{2}+e_{1}x^{1}+e_{0},{\mbox{ mit dem Rest }}r_{1}x+r_{0},}$

the coefficients are determined according to the following rule:

${\displaystyle {\begin{matrix}e_{n-2}&=&a_{n}\\e_{n-3}&=&a_{n-1}-d_{1}\,e_{n-2}\\e_{k}&=&a_{k+2}-d_{1}\,e_{k+1}-d_{0}\,e_{k+2}&{\text{für }}k=n-4,n-5,\dotsc ,1,0\\r_{1}&=&a_{1}-d_{1}\,e_{0}-d_{0}\,e_{1}\\r_{0}&=&a_{0}-d_{0}\,e_{0}\\\end{matrix}}}$

The generalized Horner scheme is then as follows:

	${\displaystyle \,a_{n}}$	${\displaystyle \,a_{n-1}}$	${\displaystyle \,a_{n-2}}$	${\displaystyle \,a_{n-3}}$	${\displaystyle \dotso }$	${\displaystyle \,a_{3}}$	${\displaystyle \,a_{2}}$	${\displaystyle \,a_{1}}$	${\displaystyle \,a_{0}}$
${\displaystyle {-d_{0}\,})}$			${\displaystyle -d_{0}\,e_{n-2}}$	${\displaystyle -d_{0}\,e_{n-3}}$	${\displaystyle \dotso }$	${\displaystyle -d_{0}\,e_{3}}$	${\displaystyle -d_{0}\,e_{2}}$	${\displaystyle -d_{0}\,e_{1}}$	${\displaystyle -d_{0}\,e_{0}}$
${\displaystyle {-d_{1}\,})}$		${\displaystyle -d_{1}\,e_{n-2}}$	${\displaystyle -d_{1}\,e_{n-3}}$	${\displaystyle -d_{1}\,e_{n-4}}$	${\displaystyle \dotso }$	${\displaystyle -d_{1}\,e_{2}}$	${\displaystyle -d_{1}\,e_{1}}$	${\displaystyle -d_{1}\,e_{0}}$
	${\displaystyle \,e_{n-2}}$	${\displaystyle \,e_{n-3}}$	${\displaystyle \,e_{n-4}}$	${\displaystyle \,e_{n-5}}$	${\displaystyle \dotso }$	${\displaystyle \,e_{1}}$	${\displaystyle \,e_{0}}$	${\displaystyle \,r_{1}}$	${\displaystyle \,r_{0}}$

An example

${\displaystyle (-6x^{6}+14x^{5}-8x^{4}-2x^{3}+8x-6)\,:\,(x^{2}-2x+1)}$

In the Horner scheme:

	−6	14th	−8	−2	0	8th	−6
−1)			6th	−2	−2	0	2
2)		−12	4th	4th	0	−4
	−6	2	2	0	−2	4th	−4

This results in:

${\displaystyle {\frac {(-6x^{6}+14x^{5}-8x^{4}-2x^{3}+8x-6)}{(x^{2}-2x+1)}}\,=\,-6x^{4}+2x^{3}+2x^{2}-2{\mbox{ Rest }}4x-4}$

Linear transformation

In some cases, for example to improve convergence in Newton's method , it can be very helpful to transform a polynomial into a polynomial , constant, so that with : ${\displaystyle P}$ ${\displaystyle P_{a}}$ ${\displaystyle a}$ ${\displaystyle x=a+y}$

${\displaystyle P(x)=P(a+y)\;=\;P_{a}(y)=P_{a}(x-a)}$

Such a linear transformation can be obtained by substituting instead of and then multiplying out. This calculation can be carried out much more efficiently with the complete Horner scheme. ${\displaystyle a+y}$ ${\displaystyle x}$

Let us consider the polynomial of degree , which we want to expand in terms of powers of : To do this, we divide the polynomial by using the Horner scheme . As shown above, we can read off the polynomial and the remainder from the scheme , so that: ${\displaystyle P(x)=\sum _{i=0}^{n}a_{i}x^{i}}$ ${\displaystyle n}$ ${\displaystyle y=x-a}$ ${\displaystyle P(x)}$ ${\displaystyle (x-a)}$ ${\displaystyle E_{1}(x)}$ ${\displaystyle r_{0}}$

${\displaystyle P(x)\;=E_{1}(x)(x-a)+r_{0}}$

Now the division is carried out on the result polynomial , and we get or the remainder : ${\displaystyle E_{1}(x)}$ ${\displaystyle E_{2}}$ ${\displaystyle r_{1}}$

${\displaystyle E_{1}(x)\;=E_{2}(x)(x-a)+r_{1}}$

After divisions you get: ${\displaystyle n}$

${\displaystyle E_{n-1}(x)\;=E_{n}(x)(x-a)+r_{n-1}}$ With ${\displaystyle E_{n}(x)\;=a_{n}=:r_{n}}$

It follows:

${\displaystyle {\begin{matrix}P(x)&=&E_{1}(x)(x-a)+r_{0}\\&=&\left(E_{2}(x)(x-a)+r_{1}\right)(x-a)+r_{0}\\&=&\left(\dotso \left(r_{n}(x-a)+r_{n-1}\right)(x-a)+\dotsb +r_{1}\right)(x-a)+r_{0}\\\end{matrix}}}$

With is then the linear transformation ${\displaystyle y=x-a}$ ${\displaystyle P_{a}}$

${\displaystyle {\begin{matrix}P_{a}(y)&=&\left(\dotso \left(r_{n}y+r_{n-1}\right)y+\dotsb +r_{1}\right)y+r_{0}\\&=&\sum _{i=0}^{n}r_{i}y^{i}\end{matrix}}}$

I.e. the remainder of the continued division with the linear factor form the coefficients of the transformed polynomial . ${\displaystyle (x-a)}$ ${\displaystyle P_{a}}$

example

Would you like If, for example, you calculate the zero of the polynomial , you can easily guess the point as the first approximation. For the further calculation it is now helpful to develop according to (see “Methodus fluxionum et serierum infinitarum” ). So we are looking for the polynomial . ${\displaystyle P(x)\,=\,x^{3}-2x-5}$ ${\displaystyle x=2}$ ${\displaystyle P(x)}$ ${\displaystyle x-2}$ ${\displaystyle P_{2}(x)=P(2+x)}$

	1	0	−2	−5
2)		2	4th	4th
	1	2	2	−1
2)		2	8th
	1	4th	10
2)		2
	1	6th

So the polynomial we are looking for is . ${\displaystyle P_{2}(x)\,=\,x^{3}+6x^{2}+10x-1}$

Calculation of the derivative

Another property of the Horner scheme is that the first derivative can be calculated very quickly at this point . ${\displaystyle x_{0}}$

Let's look at the division

${\displaystyle {\frac {P(x)}{(x-x_{0})}}}$

with the result

${\displaystyle P_{e}(x)+{\frac {r}{(x-x_{0})}},}$

which we can read from the Horner scheme. Further up you could see that it is. The following applies: ${\displaystyle r=P(x_{0})}$

${\displaystyle {\frac {P(x)}{(x-x_{0})}}=P_{e}(x)+{\frac {P(x_{0})}{(x-x_{0})}}}$

${\displaystyle \Rightarrow \;{\frac {P(x)-P(x_{0})}{(x-x_{0})}}=P_{e}(x)}$

The derivative can be calculated using the difference quotient . The following applies: ${\displaystyle P^{\prime }(x)}$

${\displaystyle P^{\prime }(x_{0})={\frac {\mathrm {d} P(x_{0})}{\mathrm {d} x}}=\lim _{x\rightarrow x_{0}}{\frac {P(x)-P(x_{0})}{(x-x_{0})}}}$

It follows:

${\displaystyle P^{\prime }(x_{0})=P_{e}(x_{0})}$

I.e. the numbers in the third line of the Horner scheme form the coefficients for . By applying the Horner scheme again, the value of the derivative can finally be calculated. ${\displaystyle P_{e}(x_{0})}$ ${\displaystyle P^{\prime }(x_{0})}$

example

Let us consider the polynomial at the point x = 2 ${\displaystyle P(x)=x^{5}-4x^{4}+4x^{3}+3x^{2}-8x+4}$

	1	−4	4th	3	−8	4th
2)		2	−4	0	6th	−4
	1	−2	0	3	−2	0
2)		2	0	0	6th
	1	0	0	3	4th

From the scheme you can now read: and ${\displaystyle P(2)\,=\,0}$ ${\displaystyle P^{\prime }(2)\,=4}$

sample

${\displaystyle P^{\prime }(x)=5x^{4}-16x^{3}+12x^{2}+6x-8}$

From the Horner scheme

	5	−16	12	6th	−8
2)		10	−12	0	12
	5	−6	0	6th	4th

follows . ${\displaystyle P^{\prime }(2)\,=4}$

Multiple derivatives

The values ​​of the other derivatives can also be read from the Horner scheme. Be

${\displaystyle P(x)=\sum _{i=0}^{n}a_{i}x^{i}}$and , with ${\displaystyle P_{a}(y)=\sum _{i=0}^{n}r_{i}y^{i}}$ ${\displaystyle x=a+y}$

the polynomial which we can read from the complete Horner scheme ( see above ) is

${\displaystyle P^{(k)}(a)=P^{(k)}(a+0)=P_{a}^{(k)}(0)=k!\,r_{k}}$

Determination of zeros

The Horner scheme can be used in various numerical methods for determining the roots of polynomials.

Has one z. For example , you can "guess" a zero , as shown above, so you can quickly check whether the assumption is correct.

In order to shorten the “guessing” of the root in some simple tasks, one can use the theorem about rational zeros . From this it follows that an integer zero is a divisor of . If there is a factor in front of the highest power of (e.g. 3 for:) , then the divisors of and, ideally, the entire function are to be divided by it (→ ). ${\displaystyle b_{0}}$ ${\displaystyle x}$ ${\displaystyle 3x^{3}-18x^{2}-3x+18=0}$ ${\displaystyle b_{0}}$ ${\displaystyle x^{3}-6x^{2}-x+6=0}$

Example: Take a look at . The possible divisors of 6 and thus candidates for zeros are 1, 2, 3, 6, and also −1, −2, −3, −6. With the Horn scheme you can now calculate the function values ​​at these points and thus determine the actual zeros. The zeros are then −1, +1, +6. If you have determined a zero, you can also split off a linear factor with the Horn scheme, as explained above. ${\displaystyle x^{3}-6x^{2}-x+6=0}$ ${\displaystyle b_{0}=6}$

Another area of ​​application is the Newtonian approximation method . For Newton's method is required in each iteration -Step and . As described above, these values ​​can be calculated very quickly using the Horner scheme. ${\displaystyle P(x_{n})}$ ${\displaystyle P'(x_{n})}$

history

William George Horner was not the first to discover this process. It was mainly thanks to De Morgan that the process became known by his name. Paolo Ruffini published a corresponding procedure 15 years before Horner; it is therefore also known as regla de Ruffini in Spain . The first known descriptions of the process go back to the 11th century ( Jia Xian in China and as-Samaw'al in the Middle East). The Chinese Zhu Shijie described a conversion method for solving equations, which he called fan fa , in his book Siyuan yujian in 1303 . The Arabs also used the method (as-Samawal, Sharaf al-Din al-Tusi ).

literature

• William George Horner: A new method of solving numerical equations of all orders, by continuous approximation. In: Philosophical Transactions of the Royal Society of London. 1819, pp. 308-335.
• Charles D. Miller, Margaret L. Lial, David I. Schneider: Fundamentals of College Algebra. 3rd revised edition. Scott & Foresman / Little & Brown Higher Education, 1990, ISBN 0-673-38638-4 , pp. 204-209.
• Gisela Engeln-Müllges , Klaus Niederdrenk, Reinhard Wodicka: Numerical algorithms: procedures, examples, applications. Springer 2005, ISBN 3-540-62669-7 , pp. 92-100 ( excerpt in Google book search)

Web links

• Online calculator for polynomial division with the Horner scheme
• Markus Bauer: The Horner scheme . Technical work, Ottobrunn grammar school 2001
• The Hornerschema and other tricks on Matroids Matheplanet on July 27, 2003
• Olaf Schimmel: Calculation with the Horner scheme ( Memento from November 11, 2014 in the Internet Archive )

Wikibooks: Horner scheme  - implementations in the algorithm collection

References and comments

1. ↑ Josef Stoer: Numerical Mathematics 1 . 9th edition. Springer, 2004.
2. ↑ When calculating the powers , k≥2, one can first calculate the lower and then the higher powers. This makes use of the fact that it is already calculated when it is needed. For one therefore needs only one more multiplication and not their . ${\displaystyle x^{k}}$ ${\displaystyle x^{k-1}}$ ${\displaystyle x^{k}}$ ${\displaystyle x^{k}}$ ${\displaystyle (k-1)}$
3. ↑ Interactive wage and income tax calculator: rounding rule ( Memento from May 21, 2014 in the Internet Archive ) Federal Ministry of Finance: Interactive wage and income tax calculator: rounding rule
4. ^ The income tax rate formulas since 1958 Wolfgang & Johannes Parmentier: The income tax rate formulas since 1958
5. ↑ John J. O'Connor, Edmund F. Robertson :  Horner scheme. In: MacTutor History of Mathematics archive .