Horner's method
Horner scheme ( according to William George Horner ) is a forming method for polynomials, to facilitate calculation of feature values. It can be used to simplify the polynomial division, and the calculation of zeros and outlets.
- 3.1 derivation
- 3.2 Example
- 4.1 Conversion between different number systems 4.1.1 Conversion to decimal
- 4.1.3 Simplified spelling
- 4.1.4 process for the reverse direction
- 4.2.1 polynomial with linear divisor
- 4.2.2 polynomial division with a divisor 2nd degree 4.2.2.1 An example of
- 4.3.1 example
- 4.4.1 example 4.4.1.1 sample
Definition
Function of the Horner scheme
Computational advantages
On polynomials in the classic style, the powers must be so calculated when the function value is to be calculated at a point. The transformed polynomial according to the Horner scheme are not powers, but only prior to multiplication and addition. The calculation is accelerated because fewer multiplications are needed: their number is reduced by the application of the Horner scheme to almost half.
In classical notation multiplications are needed for a polynomial of degree:
- Multiplications for the formation of the powers;
- More multiplications for multiplication of powers with their coefficients.
Overall, it therefore comes out with multiplications for the calculation.
In the Horner scheme, however, it comes out with multiplications.
The number of - less computationally expensive - additions in both cases is the same, ie.
Method
By continuing to factoring out the free Polynomvariablen the polynomial is represented as nesting of products and sums.
Example
The following example illustrates the reduced computational complexity at the Horner scheme:
In the classical representation (left side) 7 multiplications are required, including 3 in the formation of the powers. In the Horner scheme (right side) to get the other hand, with 4 multiplications.
Application
In calculus, often the values of a polynomial and its derivative must be calculated: Be it to determine a zero, perform a curve discussion or to sketch a graph.
The form shown here is particularly well suited for the computation in the reverse Polish notation (RPN ).
Tabular spelling of the Horner scheme
Derivation
Consider again the example above and set:
Now you transfer coefficients, the intermediates and sub-totals in a three-line table are being entered in the first line of the coefficients. In the third line of the partial sums come. Here, the first coefficient of the polynomial is taken directly. Multiplied by the previously calculated partial sum is then given the next summand, which can then enters into the second row under the following coefficients.
Thus, for by and by the following calculation scheme:
Example
The calculation of the above polynomial for using the Horner scheme is as follows:
The value for which you want to calculate the polynomial, one case usually writes in the second line before the schema. Then multiply the first number in the schema with this value and adds the result to the first row ( last row ). Multiplying this result value in the last row with the value for which you want to calculate the polynomial, each returns the following result value. The last number ( here five) is the final result.
However, for results in substantially higher intermediate results:
By using the cascaded Horner scheme (see below), although the number of multiplications increases, but decreases the intermediate results, which is more advantageous for a calculation of the polynomial by hand:
Applications of the Horner scheme
Conversion between different number systems
Our familiar representation of numbers in the decimal place value system is nothing more than a shorthand notation for special polynomials, namely polynomials with the base. The same applies to all other value systems, such as the binary system. There is. We can make ourselves Horner's advantage to convert numbers from any other place value system to the decimal system, and vice versa.
Conversion to decimal
For example, the binary number 110101 to be converted to the decimal system. What is the resulting decimal number?
We write 110101binär as a polynomial:
So is
We need that now do not calculate in a course, but can proceed step by step. Each step consists of a multiplication by 2 and an addition. For clarity, we write the steps with each other and record the intermediate results:
We have searched our decimal place.
Generalizing is the procedure: A number from one place value system to the base is converted to the decimal system by
- The value of the first digit is taken as the initial value
- Then gradually the result of the previous step with multiplied and the next digit is added
- Have been used up until all digits.
The easiest way to write the bill again in tabular form:
The drawback of the single stage Horner scheme is that multiplication factors may be necessary with large ( in the above example 2 * 26 = 52). To stay within the square one, one applies the cascaded or multi Horner scheme.
In this case, only one is used for the multiplication. The decimal is written as a carry to the next line under the One. At 13 from the above example, the three is written with the 12 and 1 3 at the next step is only 3 * 2 0 = 6 calculated (instead of 13 * 2 0 = 26). This result is well treated; the number is here 0 The last statement (6 * 2 1 ), again yields 13 The One result of this is the last digit of the final result.
To calculate the other digits, the standing in the last row of ten ( 00101 ) is applied the same scheme again. In this case one can neglect the leading zeros:
Since now only zeros are in the transfer line, the process is terminated. The overall results ( 53) one reads in the last column of A from bottom to top.
Simplified notation
The digits of the original number is first written vertically beneath each other. To the left of a vertical line is drawn. Below the last digit is a horizontal line at the end is the result of the.
First, the most significant digit (the first one ) is transmitted down a line in the previous column. This is now left of the second digit (another one ). The left number is multiplied by the number base ( 2 here ), the right number added ( 1 * 2 1). From the result ( 3) the number of one one row is a column written on the left, deeper.
The same procedure is performed with the one of the result of ( 3) and the next number (0). The result ( 3 * 2 0 = 6) is also listed as the previous result.
The third bill is 6 * 2 1 = 13, then 3 * 2 0 = 6, and then again 6 * 2 1 = 13 to calculate. As in the previous steps and tens of the result are written diagonally with each other.
Under the horizontal line is now the last digit of the final result (3).
To calculate the additional digits, the leading column will now be treated the same with the so far non- tens as the initial number.
The first valid digit is transmitted down a line in the previous column. This number (1 ) is multiplied by the base (2 ) and the product ( 2) the next digit (0 ) is added. Tens and units of the result ( 02) are diagonal as shown above entered into the scheme.
The result of the last statement ( 2 * 2 1 = 05) is also entered. The units of this result (5 ), the next digit of the final result.
As in the tens column contains only zeros, the calculation is complete. The final result (53 ) can now be read in the result line, this time in in the correct order.
A method for the reverse direction
On the reverse way, a decimal number convert into a number of another number system. Instead a continuous multiplication with the number base of the other system comes continued dividing by that number. The digits of the number in other number system arise from right to left through the Division residues.
In the table notation, the digits of the original number will be written below each other and for the result of a horizontal line is drawn. The vertical line is drawn, however, the digits on the right. As a reminder, the number base can be listed right below.
The first digit, increased by a leading zero (05) is divided by the number base ( 2). The quotient ( 2) is written in the preceding column. The rest ( 1) in the line below.
This residue forms with the next number ( 3) a new two-digit number (13). This number is in turn divided by the base, the result ( 6 Rest 1) as diagonal entered above in the schema.
Now that all digits have been processed, the rest of the last statement (1 ) is the last digit of the final result.
The non-processed as a new quotient decimal treated (26) is applied to the same procedure.
The figure obtained is a 0 when the unprocessed quotients column is now a 13
After this step is in the ratio column is a 06 The leading zero is ignored, the method starts with the 6th
The now to be treated is number 3
Now only one is still left.
After the last statement is in the quotient column a 0 The procedure is now complete. In the result line is the desired number in the correct order.
Polynomial
Polynomial with a linear divisor
The following example
Is represented by a linear divisor in the Horner scheme, the first polynomial division.
The polynomial is usually carried out in a written form.
If we let now the powers of away, we obtain the following representation:
Is compacted now this scheme on three lines and takes the first coefficient of the dividend in the third row, we obtain:
As you can now see, the double-underlined values of the last row are the coefficients of the Ergebnispolynoms and the last value behind this is the remainder ( here zero).
If we multiply the sign in the second line, the calculation is made in the following sequence:
The above example can now be summarized in the following formula:
Has the division problem:
As a result
So the coefficients determined by the following rule:
Consider the division by
Polynomial division with a divisor 2nd degree
Has the division problem:
As a result
So the coefficients determined by the following rule:
An example of
This results in:
Linear transformation
In some cases, for example for improving the convergence of the Newton method, it can be very useful in a polynomial is a polynomial constant transform, so that, with the following applies:
Such a linear transformation can be obtained by employing in place of, and then multiplying. Much more efficient can this statement be performed with the complete Horner scheme.
Consider the polynomial of degree, which we want to develop in powers of: For this purpose, we divide the polynomial by means of the Horner scheme. As shown above, we can see the polynomial and the rest of the scheme, so that applies:
Now, the division is performed on the result of polynomial and we obtain or the radical:
By division we obtain:
It follows:
By then the linear transformation
That the remains in the continued division by the linear factor form the coefficients of the transformed polynomial.
Example
If you want to, for example, calculate the root of the polynomial, so one can easily guess the point as a first approximation. For further calculations, it is now useful to develop according to (see " Methodus fluxionum et serierum infinitarum "). So Wanted is the polynomial.
The desired polynomial is so.
Calculating the derivative
Consider the Division
With the result
Which we can read off from the Horner scheme. Further up, you could also see that. Thus:
The derivative can be calculated using the difference quotient. The following applies:
It follows:
That the numbers in the third line of Horner's scheme are the coefficients. By repeated application of the Horner scheme, including the value of the derivative can be calculated.
Example
Consider the polynomial at x = 2
From the diagram we can read now: and
Sample
Followed.
Multiple derivations
The polynomial which we can read off the complete Horner scheme (see above ), it is
Obtain the root of
The Horner scheme can be used in various numerical methods for the determination of zeros of polynomials.
If one has for example a zero "guess", so you can, as shown above, quickly check that the conjecture is true.
In order not to shorten the " guessing " of zero in complex tasks, one can use the theorem on rational zeros. From this it follows that an integer is a divisor of zero. Should be a factor in front of the highest power of standing (eg 3 on: ), so are the divisor of and best to share the entire function by these (→ ).
Example: Consider with. The potential divider 6, and thus candidates for zeros are 1, 2, 3, 6, and -1, -2, -3, -6. With the Horner scheme you can now calculate the function values at these points and thus determine the actual zeros. As zeros then you get -1, 1, 6. If you have determined a zero, you can use the Horner scheme also, as discussed above, may also cleave a linear factor.
Another field of application is the Newtonian approximation methods. For the Newton's method is required in each iteration step. These values can be as described above, rather quickly calculate the Horner scheme.
History
William George Horner was not the first to discover this method. He had to thank in particular De Morgan, that the method was known by his name. Paolo Ruffini published 15 years ago Horner already a corresponding method; it is thus referred to in Spain as regla de Ruffini. First known descriptions of the process dates back to the early 14th century. The Chinese Zhu Shijie described already in 1303 in his book Siyuan yujian a transformation method for solving equations, which he called fan fa. The Arabs also used the method ( Sharaf al -Din al - Tusi ).