5.3 Graeffe's Method: By Graeffe's method, all roots of a polynomial are calculated simultaneously without any previous separation of them or any other preparator measure.The method leads very quickly to useful results when the roots are different and real. It is often difficult to estimate the error made in neglecting higher decimals; thus one should check the results afterwards.

5.3.1 Real distinct roots: Let b₁, b₂, ··· , b_n be the roots of the polynomial a₀xⁿ+a₁x^n-1 + ··· + a_n and let

then

If |b_i : b_i+1| is very large for i = 1, ··· , n, the numbers e _i can be omitted. In this case, one gets the approximation

(2)

In general, (2) is not a consequence of (1), but for a suitable exponent m the quotients b_i+1^m : b_i^m become negligible. Therefore, one has to find a polynomial the roots of which are b₁^m : b_n^m. The coefficients of this polynomial are symmetric functions of b₁, ··· ,b_n, whence it is possible to compute them as rational functions of a₀, a₁, ··· , a_n with rational coefficients. The calculation for an arbitrary m is tiresome, but it is easy to find out a polynomial the roots of which are the squares of the roots of f(x), and by repeating this construction obtain polynomials with the roots

Let have the roots and choose m so large that b_i+1^m : b_i^m may be neglected, then

The corresponding result applies to the polynomial with the roots b₁^2m,···,b_n^2m, whence the absolute values of its coefficients become approximately the squares of the corresponding coefficients a'_i. Hence one has to repeat the construction of polynomials till the calculation shows that after a further repetition the coefficients are practically the squares of the coefficients of the preceding polynomial. In order to get a polynomial, the roots of which are the squares of the roots of f(x), you compute

The coefficients of f₂ will be calculated by the scheme

As in the first pair of lines corresponding numbers differ only by their signs, one writes only the signs in the second line. The numbers increase very quickly, whence it is convenient to omit the last digits, simultaneously recording the decimals very clearly. For this purpose, replace the decimal point by a subscript which is equal to the exponent of the power of 10 by which the decimal fraction is to be multiplied. For example, you write

In order to extract the roots at the end of the calculations, use logarithms. It is therefore senseless to calculate more decimals than the tables of logarithms contain.

Example:

At the next step, the coefficients will be the squares of the preceding coefficients, and in no case the error will affect the first 5 digits. Hence you stop the procedure and compute now the roots by means of logarithms:

The sign of the roots cannot be determined by Graeffe's method; in every case, one must make a special investigation for the sign. In this example, the coefficients have alternating signs, whence all the roots are positive.

Verification: Form the elementary symmetric functions of the approximate roots and compare:

5.3.2 Complex roots: If a real polynomial has complex roots, always two of them are conjugate, and these have therefore the same absolute value. Thus, in this case, Graeffe's method has to be modified. An example will give valuable hints for the required modifications.

Example:

This polynomial has already been considered in 5.1.1 and it is known to have two real and two complex roots. Apply now the scheme of Graeffe's method, omitting the + sign present throughout the second line:

If this process is repeated, the two first and the two last coefficients will become the squares of the corresponding coefficients of Line (8), but the third coefficient will depend also upon the second and the fourth. We cannot expect that a further repetition of this process will make the third coefficient independent of its neighbours, as the absolute values of the two roots of the polynomial are equal. If d₁ is larger than the absolute value of the complex roots, then

A rough mental calculation shows that b₁² ~ 60, b⁸ l ⁷ 2.

The same treatment for f(1/x) shows that, if b₄^m < |b₂|^m, then - a'₄/a'₂ ~ b₄^m, whence the complex roots only depend on the three central coefficients. In order to find the law of dependence, the considerations will now be generalized.

Let B and C be two intervals, so that every number of C is very small compared with the numbers of B, and let

have two sets of roots:

b₁, b₂, ··· , b_r, the absolute values of which belong to B,
c₁, c₂, ··· , c_s, the absolute values of which belong to C,

where r + s = n.

Let y be a number of B and d a number of C; represent the coefficients of f(x) by its roots and approximate these by y and d, respectively. As d is small compared with y:

Hence

Let y be one of the roots b_i, then f₁(y) ~ 0. Hence the roots b_i can be approximated by the roots of f₁(x).

Let x = 1 : z, then a_nzⁿ + ··· + a₁z + a₀ has the roots

the absolute values of b'_i belong to an interval B', the absolute values of c'_k belong to C', and every number of C' is small in comparison to those of B. Hence the roots b'_i can be approximated by the roots of a_nzⁿ + ··· + a_r and therefore the roots c_i of f(x) can be approximated by the roots of

Thus, the polynomial f(x) has to be split into two polynomials, the first is defined by the r +1 upper terms and leads to the upper class of roots, the second one is defined by the s + 1 lower :terms and leads to the lower class of roots. The two classes may also be subdivided into classes, etc. Finally, one has the classes

each root being small in comparison with the roots of the preceding classes, and to each class corresponds a polynomial, which can be cut out from f(x). The ratio of the absolute value of the roots increases when we replace these roots by their higher powers, whence we get finally by Graeffe's method k polynomials each of which has only roots with the same absolute value. In the previous example, these polynomials are

They yield the roots

In order to finish this calculation, one must fix the signs of the real roots and determine the integral number k. As the signs of the coefficients are alternating, there is no negative root. Hence b₁ = 7.592 ···, b₄ = 0.093,532 ···. These numbers correspond to the results obtained in 5.1 by Horner's method and Lagrange's method.

Since . However, as 2r = 3.356 ···, then f must be a very small angle, whence k = 0,

Check:

This result can be corrected by further calculations. As is seen from the results of 5.1 and from the check given here, b₁, b₄ and r are very exact. The correction is therefore expected to concern mainly the angle f, the true value of which may be a little smaller. As f is a small angle, this correction will substantially affect sin f, whence the imaginary parts of b₂ and b₃ are only correct to the second decimal.

If a polynomial with roots of equal absolute value has a degree > 2, it has either multiple or non-conjugate roots with the same absolute value. Multiple roots can be removed by division by the h.c.f. of the polynomial and its derivative. Non-conjugate roots of equal absolute value can be removed by Horner's scheme, i.e., if |x| = |x'| and x' differs from and x, then |x - a| ¹ |x' - a|.

Hence real and complex roots of f(x) can be determined in each case by a combination of Graeffe's method and Horner's scheme. The results should be verified and it is possible to minimize the error by the methods of 6.1.

5.4 Roots of complex polynomials: Let f (x) be a polynomial with complex coefficients

then f₁(x) and f₂(x) are real polynomials and every root of f (x) is either a root of f₁(x) or f₂(x). Only one of the two conjugate roots of f₂(x) is a root of f (x), the other one is a root of . Thus, applying Graeffe'a method to f₁(x) and f₂(x) and to eventually verifying the result, it is always possible to find the roots of f (x).

5.41 Circles enclosing the roots of f (x): As in 5.2.4, set

We will show that the roots of f (x) are located inside a circle of radius t about the origin. It is necessary and sufficient to prove that |f (x)| is positive for |x|³t. The proof is nearly the same as in. 5.2.4:

whence

The following argument allows you to find a smaller circular domain with a centre different from the origin such that all the roots of f (x) lie inside it. Without loss of generality, one may assume that all the coefficients of f (x) are real (as is every root of f (x)) is a root of (f₁(x)f₁(x). By a suitable transformation, x = x' + a, one obtains a polynomial f(x') = f (x) with only positive coefficients. There corresponds to a circular domain |x'| £ b a circular domain in the x-plane with the centre a and radius b. Thus, one can apply the following generalization of Kakeya's Theorem to find that the roots of f (x) are located between two concentric circles.

Theorem: Let the coefficients of f(x) = a₀ + a₁x + ··· + a_nxⁿ be positive and 0< p < a_k-1/a_k < q for k = 1, ··· , n, then the roots of f(x) satisfy the condition

Proof: Let then b_k = q^k a_k, whence b_k-1:b_k< 1. By Kakeya's Theorem, one has for the roots |y| < 1, |x| < q. The roots of F(z) = a₀zⁿ + ··· + a_n-1z + a_n are reciprocal to the roots of f(x). As a_n+k+1/a_n-k < 1/p, it follows from the first part of the proof that the roots of F must satisfy |z| < 1/p, whence |x| =|1/z| > p for the roots of f(x) and the theorem applies.

5.4.2 Link between the roots of a polynomial and those of its derivative:

Gauss' Theorem: Every convex polygon enclosing all the roots of f (x) contains every root of f '(x).

Proof: Let g be an arbitrary root of f ' and b₁, ··· , b_n be the roots of f. Without any loss of generality, it may be assumed that g is not a root of f. Then

whence

where every b_i is positive. In the complex plane, the numbers b _i - g represent vectors which start from g and lead to b₁, ··· , b_n. Project the vectors b_i(b_i - g) ortbogonally onto any straight line of the complex plane; then the sum of those components must be zero, as the sum of the vectors themselves is zero. In particular, consider two straight lines g₁ and g₂ intersecting at right angles at y. If all the points b_i are situated on the same side of g₁, then all the components of b₁ - g have the same sign, and the same applies to the components of b_i(b_i-g) as the numbers b_i are positive. This is impossible, as the sum of the components of those vectors along g₂ is equal to zero. Hence there exists no line g₁, which passes through any root of f '{x) such that all the roots b_i of f(x) lie on the same side of g₁. Now let P be a convex polygon containing all the roots of f. If g lies outside P, we can draw through g a straight line g which does not intersect P. Hence P, and therefore all the roots of f are located on the same side of g. Hence g is not a root of f ' and the theorem has been proved.

Let P₀ be the smallest convex polygon containing the roots of f (the reader may prove that such a polygon exists and is unique!), P₁ the corresponding polygon defined by f ', ··· , P_i the smallest polygon containing the roots of f⁽ⁱ⁾. The polygons with higher indices are included in the preceding ones. f⁽ⁿ⁾ degenerates into the point 1/n - a_n-1/a_n.=(Sb _k)/n. This point is the centre of gravity of the roots of f, and for the same reason it is the centre of gravity of the roots of f ' and of the roots of each derivative.

5.5 Interpolation: Let

be n + 1 different elements of an arbitrary field K and

n + 1 arbitrary elements of K. Find a polynomial f(x) of K[x] such that f(b_i) = l_i for i = 1, ··· , n + 1, and the degree of f(x) £ n.

Let f(x) = a₀ + ··· + a_nxⁿ. This polynomial has the proposed properties if and only if its coefficients satisfy

The determinant of this system of n + 1 linear equations (cf. 3.5.3) is equal to and is ¹ 0, as the n + 1 elements b _i are supposed to be different. Hence the problem has one and only one solution. This solution can be calculated by the methods explained in Chapter 1, but it is easier to obtain it from special cases.

5.5.1 Lagrange's formula: Let f_k(x) be the solution if l_i¹k = 0, l_k = 1, then

is the solution for arbitrary l-elements. But

satisfies the above requirements, whence one obtains Lagrange's interpolation formula

5.5.2 Interpolation by iteration: By Lagrange's formula, the problem of interpolation has been solved in the most complete and general manner, but the formula is not convenient for practical calculations. It is easier to calculate the coefficients of the product representation of f(x)

where

and one may compute the coefficients g_i by iteration. When K is the field of real numbers, it is convenient to arrange the calculations as follows:

Let f_i (x) be defined by f₀(x) = f (x) and for k = 1, ··· , n

then

whence compute the quantities

using

and {0, m} = l_m. Compute these values, column by column, by the scheme

The first elements of the different columns form here the set g₀, g₁, ··· , g_n of the coefficients of (1). This scheme is easier for calculations than Lagrange's formula.

5.5.3 Newton's formula: The calculation becomes simpler if the elementsb₁,···,b_n are equidistant, i.e. if

for every k, then

where D_k+1,i = (k - 1, i +l} - {k - 1, i} is the difference of two consecutive elements in the preceding column. Thus, D{k, m} is the mean-value of the differences of consecutive elements of the rows m to k in the column k —1. Now, in the cases under consideration, the scheme will be transformed in such a manner that one computes only the differences of consecutive elements. For this purpose, introduce the notation of the Calculus of Differences:

Let D_xu = x - b₁, so that D_x(u - k - 1) = x - b_k and

Let

With

repetition of these steps yields

Now, the abbreviation

yields

whence follows Newton's formula

The elements D^k_i can be computed readily by the scheme:

The degrees of f(x), Df(x), ··· , Dⁿf(x) are decreasing and the last one is a constant; so you can use the above scheme also for extrapolation to get the value of f(x) for every arbitrary integral value of x, i.e., for every value x=b₁+kD_x, where k is an arbitrary integral number.

last next