Sturm Function

Given a function , write and define the Sturm functions by

(1)

where is a polynomial quotient. Then construct the following chain of Sturm functions,

			(2)
			(3)
			(4)
			(5)
			(6)

known as a Sturm chain. The chain is terminated when a constant is obtained.

Sturm functions provide a convenient way for finding the number of real roots of an algebraic equation with real coefficients over a given interval. Specifically, the difference in the number of sign changes between the Sturm functions evaluated at two points and gives the number of real roots in the interval . This powerful result is known as the Sturm theorem. However, when the method is applied numerically, care must be taken when computing the polynomial quotients to avoid spurious results due to roundoff error.

As a specific application of Sturm functions toward finding polynomial roots, consider the function , plotted above, which has roots , , , and 1.38879 (three of which are real). The derivative is given by , and the Sturm chain is then given by

			(7)
			(8)
			(9)
			(10)

The following table shows the signs of and the number of sign changes obtained for points separated by .

		1		1	3
0			1	1	1
2	1	1	1	1	0

This shows that real roots lie in , and real root lies in . Reducing the spacing to gives the following table.

		1		1	3
		1		1	3
	1	1		1	2
	1			1	2
0.0			1	1	1
0.5			1	1	1
1.0		1	1	1	1
1.5	1	1	1	1	0
2.0	1	1	1	1	0

This table isolates the three real roots and shows that they lie in the intervals , , and . If desired, the intervals in which the roots fall could be further reduced.

The Sturm functions satisfy the following conditions:

1. Two neighboring functions do not vanish simultaneously at any point in the interval.

2. At a null point of a Sturm function, its two neighboring functions are of different signs.

3. Within a sufficiently small interval surrounding a zero point of , is everywhere greater than zero or everywhere smaller than zero.