Unknown

176 5. Approximation and Location of Zeros

n(t) = pl(t)ql(t) - dt), degpz < degpl

n(t) = n(Mt) - n(t), degp3 < dem

m(t) = m(Mt) - p&), degp4 < dew3

and so on until a zero remainder is reached. Thus, at each stage for k 1 2,
pk(t) is the negative of the remainder when p&z(t) is divided by p&i(t).
If there are multiple roots, the last nonzero remainder will not be constant.
Call this the Sturm sequence for p(t).
Verify that two such sequences, taken to the last nonzero term, are

(t3 - t + 1, 3t2 - 1, (2/3)t - 1, -23/4)

tt3 -3t+2,3P-3,2t-2).
Let 21 < v. Suppose that U is the number of sign changes in the se-
quence (po(~),p1(~),p2(~),p3(~),.. .) and V is the number of sign changes
in the sequence (p0(v),p~(v),p2(~),p3(~),.. .). Sturm’s Theorem says that
the number of real roots of p(t) between u and v (with each multiple root
counted exactly once) is exactly U - V.
To see how it works, consider the following -example: find the number
of roots between -2 and +2 for each of the following polynomials (i) t2 -
t, (ii) t2 - t + l/4, (iii) t2 - t + 1. First, verify that the Fourier-Budan
Theorem does not allow us to distinguish the behaviour of these three
polynomials. Now verify that the Sturm sequences of polynomials for the
three are respectively:

(i) (t2 - t,2t - 1,1/4)

(ii) (t” - t + 1/4,2t - 1)

(iii) (t2 - t + 1,2t - 1, -3/4).

Use Sturm’s Theorem to determine the number of roots between -2 and
+2 for each and check the result directly.
Use Sturm’s Theorem to locate the real roots of the polynomial t5 - t4 -
t3 + 4t2 - t - 1 and 2t6 - 7t5 + t4 + t3 - 12t2 - 5t + 1 to within intervals
bounded by consecutive integers. Approximate each root to two places of
decimals.
Obtain from Sturm’s Theorem the following corollary: all roots of a manic
polynomial are real if and only if all the nonzero polynomials in its Sturm
sequence have positive leading coefficients.
Having worked out a couple of Sturm series, you will probably feel the
need for some simplification. Note first that, since we are interested only in
the sign of the values of certain polynomials, we can replace any polynomial
in Sturm’s sequence by a positive constant multiple of it. What this means
is that we can set up our division at each stage in such a way as to clear
all the fractions and deal only with integers.