Sturm chain

The Sturm chain , named after Jacques Charles François Sturm , is - similar to the sign rule of Descartes - a mathematical aid with which the number of zeros of a real polynomial can be calculated in a given interval .

Sturm's chain of a polynomial without multiple zeros

To explain the procedure, a special case is first considered. Let be a real polynomial without multiple zeros. The Sturm chain of is a finite sequence of polynomials , the degree of these polynomials decreasing strictly monotonically . is the given polynomial, its derivative . ${\ displaystyle f (x)}$ ${\ displaystyle f (x)}$ ${\ displaystyle P_ {0} (x), P_ {1} (x), \ ldots, P_ {k} (x)}$ ${\ displaystyle P_ {0} (x)}$ ${\ displaystyle P_ {1} (x)}$

{\ displaystyle P_ {0} (x): = f (x) \,}

{\ displaystyle P_ {1} (x): = f '(x) \,}

The other polynomials of the Sturm chain are recursively defined by a variant of the Euclidean algorithm for determining the greatest common divisor . For the polynomial is clearly defined by the equation ${\ displaystyle n \ geq 0}$ ${\ displaystyle P_ {n + 2} (x)}$

{\ displaystyle P_ {n} (x) = Q_ {n} (x) P_ {n + 1} (x) -P_ {n + 2} (x), \,}

if one demands that the degree of should be smaller than that of . (This definition differs from the Euclidean algorithm only by the minus sign instead of a plus sign.) ${\ displaystyle P_ {n + 2} (x)}$ ${\ displaystyle P_ {n + 1} (x)}$

The sequence ends in the special case under consideration (no multiple zeros) with a constant polynomial . For every real number let the number of sign changes in the finite number sequence . ${\ displaystyle P_ {0} (x), P_ {1} (x), \ ldots, P_ {k} (x)}$ ${\ displaystyle P_ {k} (x)}$ ${\ displaystyle a}$ ${\ displaystyle \ sigma (a)}$ ${\ displaystyle P_ {0} (a), P_ {1} (a), \ ldots, P_ {k} (a)}$

The rule of storm now states that the number of zeros of the half-open interval (with ) the same is. ${\ displaystyle f (x)}$ ${\ displaystyle (a, b]}$ ${\ displaystyle a <b}$ ${\ displaystyle \ sigma (a) - \ sigma (b)}$

example

For the polynomial

{\ displaystyle P_ {0} (x) = f (x) = x ^ {4} -5x ^ {3} + 7x ^ {2} -5x + 6 \,}

the number of zeros in the half-open interval should be determined. To do this, the derivation is first formed: ${\ displaystyle (1,4]}$

{\ displaystyle P_ {1} (x) = f '(x) = 4x ^ {3} -15x ^ {2} + 14x-5 \,}

The relationship is obtained by polynomial division

{\ displaystyle x ^ {4} -5x ^ {3} + 7x ^ {2} -5x + 6 = \ left ({\ frac {1} {4}} x - {\ frac {5} {16}} \ right) \ left (4x ^ {3} -15x ^ {2} + 14x-5 \ right) - {\ frac {1} {16}} \ left (19x ^ {2} -10x-71 \ right) }

,

so

{\ displaystyle P_ {2} (x) = {\ frac {1} {16}} \ left (19x ^ {2} -10x-71 \ right)}

.

Here and in the following calculation steps it is advisable to modify the procedure somewhat. The polynomial obtained is multiplied by a suitable positive number (in this case by 16) in order to avoid unpleasant fractions. It does not affect the end result.

{\ displaystyle {\ tilde {P}} _ {2} (x) = 19x ^ {2} -10x-71}

Another polynomial division leads to

{\ displaystyle 4x ^ {3} -15x ^ {2} + 14x-5 = \ left ({\ frac {4} {19}} x - {\ frac {245} {361}} \ right) \ left ( 19x ^ {2} -10x-71 \ right) + {\ frac {1} {361}} (8000x-19200)}

and

{\ displaystyle P_ {3} (x) = {\ frac {1} {361}} (- 8000x + 19200)}

.

Multiplication by gives the simpler polynomial ${\ displaystyle {\ frac {361} {1600}}}$

{\ displaystyle {\ tilde {P}} _ {3} (x) = - 5x + 12}

.

The last round of the procedure runs accordingly:

{\ displaystyle 19x ^ {2} -10x-71 = \ left (- {\ frac {19} {5}} x - {\ frac {178} {25}} \ right) (- 5x + 12) + { \ frac {361} {25}}}

{\ displaystyle P_ {4} (x) = - {\ frac {361} {25}}}

{\ displaystyle {\ tilde {P}} _ {4} (x) = - 1}

Inserting the number 1 results in:

{\ displaystyle P_ {0} (1) = 4; \ quad P_ {1} (1) = - 2; \ quad {\ tilde {P}} _ {2} (1) = - 62; \ quad {\ tilde {P}} _ {3} (1) = 7; \ quad {\ tilde {P}} _ {4} (1) = - 1}

There are exactly three sign changes, namely between 4 and −2, between −62 and 7 and between 7 and −1. Hence applies . ${\ displaystyle \ sigma (1) = 3}$

Correspondingly for the number 4:

{\ displaystyle P_ {0} (4) = 34; \ quad P_ {1} (4) = 67; \ quad {\ tilde {P}} _ {2} (4) = 193; \ quad {\ tilde { P}} _ {3} (4) = - 8; \ quad {\ tilde {P}} _ {4} (4) = - 1}

Here there is only one sign change: . The number of zeros in the interval has the value . In this interval there are exactly two zeros (namely 2 and 3). ${\ displaystyle \ sigma (4) = 1}$ ${\ displaystyle (1; 4]}$ ${\ displaystyle \ sigma (1) - \ sigma (4) = 3-1 = 2}$

Sturm's chain of any polynomial

The general case in which the given polynomial may have multiple zeros can be reduced to the special case already considered. Using the Euclidean algorithm, the greatest common divisor of and its derivative can be determined. If you divide by , you get a new polynomial that has the same zeros as , but no multiple zeros. The number of different zeros of in an interval is obtained by forming the Sturm chain of the polynomial and determining the number of zeros of this polynomial as above. ${\ displaystyle g (x)}$ ${\ displaystyle f (x)}$ ${\ displaystyle f \, '(x)}$ ${\ displaystyle f (x)}$ ${\ displaystyle g (x)}$ ${\ displaystyle f (x)}$ ${\ displaystyle f (x)}$ ${\ displaystyle f (x) / g (x)}$