info prev up next book cdrom email home

Sturm Function

Given a function $f(x)\equiv f_0(x)$, write $f_1\equiv f'(x)$ and define the Sturm functions by

\begin{displaymath}
f_n(x)=-\left\{{f_{n-2}(x)-f_{n-1}(x) \left[{f_{n-2}(x)\over f_{n-1}(x)}\right]}\right\},
\end{displaymath} (1)

where $[P(x)/Q(x)]$ is a polynomial quotient. Then construct the following chain of Sturm functions,
$\displaystyle f_0$ $\textstyle =$ $\displaystyle q_0f_1-f_2$  
$\displaystyle f_1$ $\textstyle =$ $\displaystyle q_1f_2-f_3$  
$\displaystyle f_2$ $\textstyle =$ $\displaystyle q_2f_3-f_4$ (2)
  $\textstyle \vdots$    
$\displaystyle f_{s-2}$ $\textstyle =$ $\displaystyle q_{s-2}f_{s-1}-f_s,$  

known as a Sturm Chain. The chain is terminated when a constant $-f_s(x)$ 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 $x=a$ and $x=b$ gives the number of real roots in the interval $(a,b)$. This powerful result is known as the Sturm Theorem.


\begin{figure}\begin{center}\BoxedEPSF{SturmFunction.epsf scaled 800}\end{center}\end{figure}

As a specific application of Sturm functions toward finding Polynomial Roots, consider the function $f_0(x)=x^5-3x-1$, plotted above, which has roots $-1.21465$, $-0.334734$, $0.0802951\pm 1.32836i$, and 1.38879 (three of which are real). The Derivative is given by $f'(x)=5x^4-3$, and the Sturm Chain is then given by

$\displaystyle f_0$ $\textstyle =$ $\displaystyle x^5-3x-1$ (3)
$\displaystyle f_1$ $\textstyle =$ $\displaystyle 5x^4-3$ (4)
$\displaystyle f_2$ $\textstyle =$ $\displaystyle {\textstyle{1\over 5}}(12x+5)$ (5)
$\displaystyle f_3$ $\textstyle =$ $\displaystyle {\textstyle{59083\over 20736}}.$ (6)

The following table shows the signs of $f_i$ and the number of sign changes $\Delta$ obtained for points separated by $\Delta x=2$.


$x$ $f_0$ $f_1$ $f_2$ $f_3$ $\Delta$
$-2$ $-1$ 1 $-1$ 1 3
0 $-1$ $-1$ 1 1 1
2 1 1 1 1 0


This shows that $3-1=2$ real roots lie in $(-2,0)$, and $1-0=1$ real root lies in $(0,2)$. Reducing the spacing to $\Delta
x=0.5$ gives the following table.


$x$ $f_0$ $f_1$ $f_2$ $f_3$ $\Delta$
$-2.0$ $-1$ 1 $-1$ 1 3
$-1.5$ $-1$ 1 $-1$ 1 3
$-1.0$ 1 1 $-1$ 1 2
$-0.5$ 1 $-1$ $-1$ 1 2
0.0 $-1$ $-1$ 1 1 1
0.5 $-1$ $-1$ 1 1 1
1.0 $-1$ 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 $(-1.5,-1.0)$, $(-0.5,0.0)$, and $(1.0,1.5)$. 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 Area surrounding a zero point of $f_0(x)$, $f_1(x)$ is everywhere greater than zero or everywhere smaller than zero.

See also Descartes' Sign Rule, Sturm Chain, Sturm Theorem


References

Acton, F. S. Numerical Methods That Work, 2nd printing. Washington, DC: Math. Assoc. Amer., p. 334, 1990.

Dörrie, H. ``Sturm's Problem of the Number of Roots.'' §24 in 100 Great Problems of Elementary Mathematics: Their History and Solutions. New York: Dover, pp. 112-116, 1965.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, p. 469, 1992.

Rusin, D. ``Known Math.'' http://www.math.niu.edu./~rusin/known-math/polynomials/sturm.

Sturm, C. ``Mémoire sur la résolution des équations numériques.'' Bull. des sciences de Férussac 11, 1929.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26