Sturm's theorem

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

Sturm sequence of a polynomial without multiple zeros

To explain the method, a special case is considered first. Be a real polynomial without multiple roots. The Sturm sequence of a finite sequence of polynomials, the degree of these polynomials decreases monotonically. is the given polynomial, its derivative.

The other polynomials of the storm between chain are defined recursively by a variant of the Euclidean algorithm for finding the greatest common divisor. For the polynomial is uniquely defined by the equation

If we require that the degree of less than should be the of. ( This definition differs from the Euclidean algorithm only by the minus sign instead of a plus sign. )

The episode ends in the considered special case ( no multiple roots ) with a constant polynomial. Now is the number of sign changes in the finite sequence of numbers for every real number.

The rule of storm now states that the number of zeros of the half-open interval ( with ) is the same.

Example

For the polynomial

Is the number of zeros in the half-open interval can be determined. For this, the derivative is formed:

By polynomial division we obtain the relationship

So

Here and in the steps of calculation, it is useful to modify the process somewhat. Multiplying the resulting polynomial with an appropriate positive value ( in this case 16) in order to avoid unpleasant breaks. The end result will not be affected.

Re polynomial leads to

And

Multiplication results in the simpler polynomial

According to the last pass of the process runs:

Inserting the number 1 now yields:

Here occur exactly three sign changes, ie from 4 to -2, -62 to 7 and 7 to -1. Accordingly applies.

Accordingly, for the number 4:

Here there is only one sign change. The number of zeros in the interval thus has a value of. In this interval exactly two zeros exist (namely 2 and 3).

Sturm sequence of any polynomial

The general case in which the given polynomial can have multiple zeros, can be traced back to the special case already considered. By using the Euclidean algorithm can be the greatest common divisor of and its derivative determine. Dividing by, we obtain a new polynomial that such has the same zeros, but no multiple roots. The number of distinct zeros of an interval is obtained now by the fact that it forms the Sturm sequence of the polynomial and determined as above, the number of zeros of this polynomial.