# Mathematics for computer algebra - Mignotte M.

ISBN 0-387-97675-2

**Download**(direct link)

**:**

**18**> 19 20 21 22 23 24 .. 25 >> Next

Pm-I

ø = _ßò-1

— a

2m. _a

Qm

which implies ø > I. Up to a multiplicative constant, the polynomial G is equal to

G(u) = (u-u>) (u + l + ei)---(u + l + e„_i),

where the Si axe arbitrarily small for m big enough and where n designates the degree of /.

By Lemma 5.1 below, the sequence of the quotients of consecutive coefficients of the polynomial (u + l)n_1 is decreasing; indeed, an easy direct computation shows that it is strictly decreasing. The same property holds, at least when m is big enough, for the polynomial

(u + I + Si) — (u + I + Sn-x) .

Finally, a new application of Lemma 5.1 shows that the list of the coefficients of the polynomial G has exactly one change of sign and the theorem is demonstrated. []

Lemma 5.1. — Let

f{x) = O0Xn + aixn_1 H---------(- an

be a polynomial with real positive coefficients.Then, the two following properties hold :

1°) If all the roots of f are real, then the sequence of the quotients ai+i/ai is decreasing.

2?) If the sequence of the quotients of consecutive coefficients Ci+i/ai is decreasing, then for any positive real number ?, the list of the coefficients of the product polynomial (x — ?) f(x) has exactly one change of sign.

Proof

First suppose that all the roots of / are real; since the coefficients of the polynomial / are all positive, its roots are necessarily negative. Let ? be any positive real number. Since the product polynomial (x — ?)/(x) ^ias only real roots, with only one which is positive, Proposition 5.7 shows that the list of its coefficients has exactly one change of sign. In other words, for any positive number ?, there exists one index j, such that

³ < j =>• flj+i - ?a, > 0 and ³ > j ==> ai+i — ?à* < 0,

where we have written a_x = 0, which shows, indeed, that the sequence of

the quotients ai+i/a,i is decreasing. This proves the first assertion.

Suppose now that the sequence of the quotients Oj+i/ai is decreasing. Then, for any real number ? > 0, there exists an index j such that

³ < j ==> a.i+i - ?à* > 0 and i> j => ai+i - ^ai < 0,

where again a_i = 0. Which shows, indeed, that the sequence of the

coefficients of the polynomial (x — ?)/(*) has exactly one change of sign. Hence, we have the second property. []

Vincent proposes the following method to separate the real roots of a polynomial f with real coefficients and without multiple roots.

1°) Determine two positive integers L and V such that all the real roots of / are between -L1 and L. In order to simplify the notations, we just consider the separation of the positive roots. Studying the polynomial f(—x), we can, however, just look for positive real roots.

2°) Let, then a and a' be two rational integers with 0 < a < a! < L. We know, by the theorem of Budan-Fourier, that the polynomial f can have a root in the interval [a, a'] only if we have v (a) > v (a') where — let us remind it — the notation v (æ) designates the number of changes of signs in the sequence f(x), f'(x), f{x), ..., f^(x), and where n is the degree of the polynomial /. To simplify, say that v (x) is the variation of / at the point x. When it is useful to mention which is the considered polynomial, this variation is written v(/; x).

206

5. POLYNOMIALS WITH REAL COEFFICIENTS

If we suppose that a' = a + I, and that we have v(a) > v(a'), we write

I

x = a H------

Xi

In this way, we get a polynomial /i in Xi such that the roots of / belonging to the interval [a, a+1] correspond to the roots > I of /i. If r is the number of these roots, then we have

Ã < v(/i; I).

Then, we try to separate the roots > I of the polynomial /õ, applying the Scime process ... and so on.

This procedure produces the beginning of the development in continued fractions of each of the real roots of /. And, thanks to Vincent’s theorem, we can suppose that all these computations have been done until, for each of the real roots of the polynomial /, we have got a transformed polynomial that has exactly a single variation of sign.

3°) For some real root of /, let us call g the last computed transformed polynomial of / and ó the variable associated to g. We suppose that the variation of g is equal to I and that we have found an approximate value 7 such that the unique positive root of the polynomial g is equal to 7 + A, with 0 < A < ? < I. By the theorem of Budan-Fourier, we have V(S> 7) = I- We suppose also, which is always possible, that the leading coefficient of g is positive. Finally, we add the condition

ff'(7) > 0,

which is satisfied for h small enough, since we have

?^7-3(7)/^(7), where 7 <?,

and hence g(7) < 0.

The conditions v(<j; 7) = I and g'(7) > 0 imply

g{i)(7) >0, for ã = I, 2, ..., n,

4. THE NUMBER OF ZEROS OF A POLYNOMIAL IN A REAL INTERVAL 207

and Taylor’s development of <7(7 + h) shows that we have

? < 7-0(7)/^(7)-Finally, a classical error computation leads to the inequality

? 9b) 1^(7 + 0^

9'{l) 2 g’{ 7)

This allows us to find rapidly a good approximate value for the number ? and, consequently, thanks to the computation of æ in terms of ó done during the proof of Vincent’s theorem, to find a good approximate value for the considered root a of /.

**18**> 19 20 21 22 23 24 .. 25 >> Next