The algorithm of polynomials real roots calculation

The basic idea of this algorithm is very simple and can be described in two sentences. A real root of the polynomial can always be calculated on the area of monotonic variation of the polynomial, between the roots of the derivative of a polynomial. But the derivative of a polynomial - is also a polynomial, however, with fewer exponents, so if you find its real roots, it will be necessary to calculate the roots of the original polynomial between the roots of the derivative by a bisection method.

---

The problem of finding roots of algebraic polynomials is known for a long time, at least since the Middle Ages. There is a well-known Lobachevskian method for solving algebraic equations of arbitrary exponent. The essence of the Lobachevskian method can briefly summarize as follows.

Having some initial polynomial it is not difficult to build polinomial2 that have the same roots as the original polynomial, but with the opposite sign. Multiplying the original polynomial and polinomial2, we obtain a polynomial whose roots are the squares of the roots of the original polynomial.

It is very good to repeat it several times. As a result, if the original roots of the polynomial are not equal to each other, their squared values would be really different, and their approximate values are very simply expressed in terms of the coefficients of the corresponding squared polynomial.

In particular, if the coefficient of the highest exponent of the argument of the polynomial is equal to one, then the next-highest coefficient is equal (with opposite sign) to the sum of the roots of the equation, and as the values of these roots are strongly separated, then it can be approximately assumed that this amount is equal to the largest root modulo.

For a polynomial of the 4th exponent with the roots 1, 2, 3, 4 Lobachevskian method after the fourth squaring gives the right roots values. At the same time to represent the polynomial coefficients, only a long double format is necessary.

Now I'll start to describe a different method.

This algorithm is about the investigation of serial intervals of monotonic variation of the original polynomial. If on the boundaries of this monotony interval the values of the polynomial have different signs, then the procedure of dividing the interval in half starts to calculate the exact value of the next root. The boundaries of the monotony intervals are the points at which the derivative of a polynomial equals zero, they are the roots of the derivative polynomial.

Derived polynomial has got a exponent one time less than the original polynomial has, and the process of calculating the coefficients of the derivatives of polynomials must be continued to a polynomial of the first exponent, the root of which could be calculated without the involvement of a procedure of dividing the interval in half. As a result of this step, we obtain two intervals of monotonic changes for a derivative polynomial of the second exponent.

Now we can find two real roots of a derivative polynomial of the second exponent (if they exist), and then come up to the roots of the original polynomial.

We normalize the polynomial so that the coefficient of the highest exponent of the argument was equal to one. Let M be the largest value modulo among its other coefficients. Then a polynomial value is greater than one for all values of argument larger than M + 1.

Thus, if you want to determine the sign of the polynomial at the infinite value of the argument, the argument should be taken equal to M + 1.

Now I want to comment feature of the implementation of the procedure of dividing the interval in half.

Pilot point pt, located midway between the current ends of ng and vg ng of the interval is calculated by the operator pt = 0.5 * (ng + vg); and the cycle of dividing the interval in half is aborted by (pt <= ng || pt> = vg) break ;

Due to the finite accuracy of the representation of real numbers in the machine sooner or later there comes a condition in which the operation of division in half, instead of giving the new value gives the value of one original boundary. In this state, we should stop this cycle. This state corresponds to the maximum achievable accuracy of the result.

---

Undoubtedly, this method is a valuable tool in the hands of the researcher. However, it's programming for modern computer technologies causes serious difficulties in need of strict guarantees of reliable results in all sorts of special root locations.

References: 1, 2

Follow me, to learn more about popular science, math, and technologies

With Love,
Kate

Image credit: 1, 2, 3, 4