Finding All the Roots: Sturm’s Theorem

1 Root- Finding AlgorithmsInstructor: Padraic BartlettFindingAllthe Roots: sturm s TheoremDay 2 Mathcamp 2013In our last lecture, we studied two root- Finding methods that each took in a polynomialf(x) and an interval [a,b], and returned a root of that function on that interval. This wasgreat for the problem we asked at the start of the class how to find a root of a quinticpolynomial but is not necessarily so great for many other problems we may want tostudy. For example, we may want to find a root of a degree-6 polynomial! In this situation,we can t obviously use either of the methods we ve examined earlier: we have no obviousway to find an interval on which an even-order polynomial changes sign.

2 Also, we may oftenwant to find not just one root, butall of the rootsof a given polynomial! Our earliermethods only give us one root, which is not necessarily very useful to us in this lecture we re going to study sturm s Theorem , a tool that helps with both ofthese sturm s TheoremIn order to state sturm s Theorem , we need to make some Definitions and chainis a finite sequence of polynomialsp0(x),p1(x),..pm(x) ofdecreasing degree with the following (x) is square-free: it has no factors of the form (q(x))2, for any polynomialq(x).2. Ifais a root ofp(x), then the sign ofp1(a) is the same as the sign ofp (a),and inparticular is Ifais a root ofpi(x) for someiwith 0< i < m, then bothpi 1(a),pi+1(a) arenonzero.

3 Moreover, the sign ofpi 1(a) is the opposite of the sign ofpi+1(a). (x) s sign is constant and nonzero for chains look very strange initially. Before we get into why we d want to studythem, however, we offer an example of how to construct sturm a square-free polynomialp(x), the following construction gives us aSturm chain: p(x) =p0(x). p1(x) =p (x).1 p2(x) = rem(p0(x),p1(x)) =p1(x)q0(x) p0(x), where rem(p0(x),p1(x)) is the re-mainder whenpolynomial long division1is is used to dividep0(x) byp1(x), andq0(x) is the quotient of said long division. p3(x) = rem(p1(x),p2(x)) =p2(x)q1(x) p1(x). In general, definepkinductively as rem(pk 2(x),pk 1(x)) =pk 1(x)qk 2(x) pk 2(x).

4 Repeat this process until we arrive at somemsuch that rem(pm 1,pm) = 0, wherepm(x)6= 0. (Because our degrees are decreasing by at least one at each step, this willeventually occur.) definition, we know the first two properties in the definition of sturm chainshold. So the only nontrivial conditions that we need to examine are the last two propertiesof sturm see the third property, we ll use a proof by induction. First notice thatp0(x) andp1(x) do not share any common roots: this is because ifais a root ofp(x), we can writep(x) = (x a) q(x), for some other polynomialq(x) that doesn t have a root ata(we knowthatq(x) doesn t have a root atabecausep(x) is squarefree.)

5 Then, if we differentiate, weget thatp (x) =q(x) + (x a)q (x), which is equal toq(a) ata, and in particular is our inductive step, notice thatpi 1(x) =pi(x)qi 1(x) pi+1(x). Therefore, ifpi+1(x),pi(x) had a common root for somei, this root would be shared withpi 1(x), and(by recursion) this root would be shared with all of our polynomials. We showed, however,thatp0(x),p1(x) do not share a common root, so this is impossible. Therefore, at any rootaofpi(x), for 0< i < m, we ve shown that bothpi 1(a) andpi+1(a) must be see that at any rootaofpi(x),the sign ofpi 1(a) is the opposite of the sign ofpi+1(a): just look at our construction. We know thatpi+1(x) =pi(x)qi 1(x) pi 1(x), bydefinition.

6 If we plug inato this equation, we getpi+1(a) = pi 1(a), our claim. Thisfinishes our proof that the third property are left with the last property: showing thatpm(x) s sign is a nonzero prove this, we refer to our construction again. We know that deg(pi)>deg(pi+1),for anyi, by construction, because we re using polynomial long division. So our processeventually terminates, and yields somepm(x) such thatpm(x) is both nonzero and satisfiespm 1(x) =qi 1(x) pm(x).Ifpm(x) is not a constant, is this possible? Well, ifpm(x) andpm 1(x) sharepm(x) asa common factor, then by definitionpm 1(x) also shares this factor, and (by recursion) sodoeseverypolynomial in our this happen?

7 Well: again, look atp0(x) andp1(x). We know that ifpm(x) is a factorofp0(x), then if we writep0(x) =pm(x) q(x), we havep1(x) =p m(x) q(x) +pm(x) q (x).Ifpm(x) is a factor ofp1(x) as well, we can use this equation to conclude thatpm(x) is alsoa factor ofp m(x) q(x). Becausep m(x) has strictly lower degree thanpm(x), we know thatin order for this to be true, there must be some factor ofpm(x) that is a factor ofq(x).However, this means that this factor occurs twice inp0(x) =pm(x) q(x). In order forp0(x)to be squarefree, as claimed, thispm(x) must be a constant, as two polynomialsp0, p1, there is a unique pair of polynomialsq, rsuch thatp0=p1 q+rand thedegree ofris either 0 or lower than the degree ofp1.

8 The process we use to find thisq, ris polynomial longdivision; come talk to me if you haven t done this before, or have forgotten how it goes!2So this process generates a sturm chain, as Stating and Proving sturm s TheoremSturm chains are pretty odd things; from their construction, it s not immediately obviouswhat they are, or why we care about them. As it turns out, however, they re incrediblyuseful things, that were very carefully and cleverly constructed so that the following theoremwould be any squarefree polynomialp(x), and any interval (a,b) such thatpi(a),pi(b)6=0, for anyi. Letp0(x),..pm(x) denote the sturm chain corresponding top(x). For anyconstantc, let (c) denote the number of changes in sign in the sequencep0(c).

9 Pm(c).Thenp(x) has (a) (b) distinct roots in the interval (a,b). , notice that near any rootaofp(x), our functionp(x) is negative on one sideofaand positive on the other side ofa. This is because our function, when factored, lookslike (x a) g(x), for some functiong(x) that does not have a root ata(becausep(x) issquarefree) and therefore has constant sign Imagine, for the moment, the function sweeping left-to-right across the realnumber line. We know that cannot change unless the sign of one of our polynomialspi(x)changes. Because polynomials are continuous, this can only happen if we pass over a zeroof somepi(x). Therefore: at any such root of somepi(x), we want to show that decreasesby 1 if we pass over a root ofp0(x), and does not change if we pass over a zero of any otherpi(x).

10 We first consider the case wherepi(x) has a root, for somei 1. Call ita. Ata,we know thatpi 1(a),pi+1(a) are both nonzero and opposite signs. Furthermore, becausethese functions do not have a root ata, nearathese signs do not (x) switches from being positive to negative, our sign pattern here goes from either + + to + or + to + + , depending on the signs ofpi 1(a),pi+1(a). Similarly, ifpi(x) switches from negative to positive, our sign pattern goes from either + to + + orfrom + to + + . In any of these cases, the total number of sign changes is does not , suppose thatp0(x) has a root ata. If it switches from positive to negative, weknow that in a small neighborhood ofaour function must have negative derivative, as ourpolynomial is decreasing.