L'algoritmo di Sturm è un algoritmo usato per calcolare il numero di radici reali di un polinomio a coefficienti reali che cadono in un determinato intervallo
.
Sia
un polinomio di grado
, definiamo la successione di polinomi
![{\displaystyle \left\{{\begin{matrix}f_{1}(x)=f(x)\\f_{2}(x)=f'(x)\\f_{i}(x)=-\left\{f_{i-2}(x)\mod f_{i-1}(x)\right\}&\forall i=3,2,...,m\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ce65723d6b90aeca6bc481f9e1addf60a0e5a18)
dove con
si indica il polinomio resto nella divisione del polinomio
per il polinomio
.
Il numero di distinti zeri reali di
nell'intervallo
, con
e
, è uguale a
, dove
indica il numero di volte che gli elementi della successione
cambiano di segno, ignorando gli zeri.
La successione
è una sequenza di Sturm, abbiamo che
dove
è uno zero reale di
con molteplicità
mentre
è un polinomio senza radici reali. Per cui
considerando che le molteplicità sono tutte positive si ottiene
dove si è usato l'indice di Cauchy, il teorema sulle sequenze di Sturm afferma
da cui la tesi.