in black and white
Main menu
Share a book About us Home
Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics

Mathematics for computer algebra - Mignotte M.

Mignotte M. Mathematics for computer algebra - New York, 1992. - 92 p.
ISBN 0-387-97675-2
Download (direct link): mathforcomputer1992.djvu
Previous << 1 .. 7 8 9 10 11 12 < 13 > 14 15 16 17 18 19 .. 25 >> Next

u< jjct j Lrc iiicuuuuic uvci ^ui

over any algebraically closed field of characteristic zero). Suppose that there exist two infinite subsets of C, I and J, and two positive integers p and q such that, for x in I, the polynomial P(x, Y) has exactly q roots, and P(X, y) has exactly p roots for in J. Demonstrate that deg x P = p and degy P = q

[Consider the polynomial A(Y) = Res*(P, Px)- Prove that this polynomial is nonzero. Show that there exists J such that () 0. Conclude that degx P =p . Same proof for degy P.]

29. Let and d be two positive integers, 2 < < d. Prove that the polynomial Xd 2 (aX l)k has roots very close to the point 1/a. [Use the theorem of Rouche.]

Deduce that proposition 4.11 cannot be much improved. [Notice that this result generalizes Proposition 4.12.]

Chapter 5


In this chapter, we call R an ordered field such that the field C = R[\/1] is algebraically closed. Usually, we consider that K is the field of real numbers and that C is the field of complex numbers. We study algorithms to separate the real roots of polynomials.

I. Polynomials irreducible over R

Here, we demonstrate Proposition 4.1.

Proposition 5.1. The polynomials with coefficients in R and irreducible over R are first-degree polynomials or second-degree polynomials with a strictly negative discriminant.


Let P be a monic polynomial, with real coefficients, that is irreducible over the field R (thus, by definition, P is non constant). If P admits a real root q, then X a is a polynomial with real coefficients that divides P, hence, since P is irreducible, P = X a. If P has no real roots then it admits at least two imaginary conjugate roots a + ib and a ib, where a and 6 are real and b ^ 0. Then, the polynomial

(X-a-ib)(X-a + ib) = X2- 2 aX + a2 + b2

has real coefficients and divides P, hence it is equal to P. And the discriminant of P is Discr (P) = -62 < 0.

Inversely, it is clear that any polynomial with real coefficients of degree one or of degree two and of negative discriminant is irreducible over R (Indeed, since R is ordered field, its negative elements are not squares. Prove this as an exercise.) Q
-----Jt. U -I ID a quouiai/ic polynomial WXtH real coefficients,

irreducible over the field R, then P(x) has constant sign when x runs over the set of real numbers.

2. The theorem of Rolle

I. The theorem of intermediate values

This theorem is a consequence of the following result.

Theorem 5.1. Let f be a polynomial with real coefficients, and let a and b be two real numbers, where a < b, such that the values /(a)

and f (b) are nonzero. Then the numbers of roots of f in the open interval

]a, b[, counted with their multiciplities, is even or odd whether the product f(a)f(b) is positive or negative.


Let us write

m n

f(X) = ( - ) (*2 + Pi* + ).

I J = I

where each of the polynomials on the right-hand side is irreducible over M. As we have just seen it, each of the quadratic polynomials this decomposition has positive values at any real point. Suppose that , ..., oik are exactly the roots of polynomial / lying between the points a and b. Then, we have

/(a) _ Q ~ Qfc TT- Q ~ Qj 2 + PjQ- + 7j

f(b) b-ai b-ak b- Cti AA b? + fyb +

which immediately leads to the relation

sign{/(a)/(6)} = (-1)*.

Hence we have the result. []

The theorem of intermediate values is the following corollary.

Corollary. Let f be a polynomial with real coefficients, and let a and b be two real numbers, where a <b, such that we have f(a) f(b) < 0. Then the polynomial f has at least one root in the open interval ]a, b[.
Z. The theorem oj Kolle

The theorem of Rolle is shown in the following theorem.

Theorem 5.2 (Rolle). Let f be a polynomial with real coefficients and Ieta and 6 be two real successive roots off, with a <b. Then the derivative of f has an odd number of roots in the real interval ]a,b[.


Let m be the order of a, then the polynomial / is written f(X) = (X - a)mg(X), with g(a) 0,


f'(X) = m(X - a)m~1g(X) + (X- a)mg'(X).

For a real number h, which is non zero and small enough, we have the estimate

f(a + h)/f'(a + h) h/m.

This implies the relation

SignjZ(X)Z7(X)) > 0 for x - a > 0, small enough.

In the same way

sign{Z(x)Z'(x)} <0 for x - 6 < 0, small enough.

Because Z never takes the value zero on the open interval ]a, b[ (since a and b are two successive roots of f), by the corollary of Theorem 5.1, the polynomial f does not change of sign on the interval ] a,b[. Hence, for any real h > 0 small enough,

f{a + h)f{b-h)< 0.

We reach the conclusion via theorem 5.1. []


Corollary I. Let f be a polynomial with real coefficients that has m roots (counted with their orders of multiplicity) in a closed interval of R. Then its derivative has at least m I roots in this interval.
Previous << 1 .. 7 8 9 10 11 12 < 13 > 14 15 16 17 18 19 .. 25 >> Next