Polynomials and Equations

APPENDIX: TWO THEOREMS ON SEPARATION OF ROOTS

ApPENDIX TWO THEOREMS ON SEPARATION OF ROOTS In Chapter Nine we have used Sturm's theorem and Fourier's theorem to isolate the real roots of an equation without having proved their validity. We shall redress this omission in this appendix. In order to prove Sturm's theorem, we need two preliminary results concerning the signs of the values of a polynomial function and its derivative in a neighbourhood of a given point. A.1 LEMMA. H c is not a root of an equation !(x) = 0, then the value of !(x) has the same sign at all points of a sufficiently small neighbourhood of the point c. PROOF: Taylor's formula gives !(c + h) = !(c) + !'(c)h + f'~~c) h2 + ... which is a polynomial in h with a non-vanishing constant term !(c). By 6.2.1 we can find a positive number H such that for all h such that \h\ ~ H This means that for all d in the neighbourhood (c - H, c+ H) of c, ! (d) and !(c) will have same sign. This completes the proof of the lemma. The lemma can be interpreted geometrically as follows. If c is not a root of !(x) = 0, then there is a neighbourhood of c such that the entire portion of the graph of y = !(x) over this neighbourhood lies either above or below the x-axis: 207 Polynomials and Equations f(x) ------~~~----------~~------------~x f(d) A.2 LEMMA. Let c be a root of an equation /(x) = O. Then as the value of x decreases, the values of / (x) and /'(x) have the same sign immediately before and have opposite signs immediately after the passage through the point c. PROOF: We have to prove that for sufficiently small positive values of h, /(c +h) and f'(c +h) have the same sign while /(e - h) and f'(e - h) have oppositive signs. Let us first consider the case in which e is a simple root of /(x) = O. In this case /(c) =0 and f'(e) =f:. O. Then by Taylor's formula, we have /(c + h) = h{!,(e) + f'~~e) h + ... } /'(c + h) = /'(e) + /"(e)h + f':~c) h2 /"(c) /(e - h) = -h{!,(e) - 2!h + ... } /'(c - h) = /'(e) - /"(e)h + f':~c) h2 - ...• The conclusion of the lemma follows from 6.2.1. In the case where e is an m-fold root of /(x) = 0, we have /(e) /'(e) = ... = /(m-l)(e) = 0 and /(m)(e) =f:. O. Then the four expressions above become 208 Two Theorems on Separation 01 Roots I (m) () I(m+l){) I(c + h) = hm{ c + c + ... } m! (m+ I)! I (m) ( ) I(m+l) ( ) I'(c + h) = hm - 1 { c + C h + ... } (m-l)! m! I (m) () I(m+l) ( ) I(c - h) = {_h)m{ c _ c h + ... } m! (m+ I)! I (m) () I(m+l)() I'(c - h) = (_h)m-l { c _ c h + ... } . (m-l)! m! Therefore the same conclusion follows. We may interpret Lemma A.2 schematically as follows. If c is a root of the equation I(x) = 0, then for sufficiently small positive values of h, the signs of the values of I{x) and I'(x) have one of the following configurations: x I /' V:e x I /' V:e c+h + + 0 c+h + + 0 c-h + - 1 c-h - + 1 x I I' V:e x I I' V:e c+h 0 x+h 0 c- h + 1 x-h - + 1 Let us first recall the definition of the Sturm functions. Let Ilx) be a polynomial with real coefficients and I'(x) its derivative. We put initially lo(x) = I(x) and 11(x) = /'(x), and then carry out successive Euclidean algorithms: to obtain a series of Sturm functions lo{x), l1(x), ... ,/m(x) where Itn(x) = HCF(/(x),/'(x)). Therefore the equation I(x) = 0 has all simple roots if and only if Im(x) is a non-zero constant. The following lemma concerning the Sturm functions is also needed in the proof of Sturm's theorem. 209 Polynomials and Equations A.3 LEMMA. Htwo consecutive Sturm functions Ii (x) and li+l(X) vanish simultaneously at c, then c is a multiple root of f(x) = o. PROOF: Suppose li(x) and fi+l(X) have a common root c. Then (x-c) is a common factor of these two polynomials. On...