Algoritmo di Sturm

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 $(a,b)$.

Algoritmo

Sia $f(x)$ un polinomio di grado $n$, definiamo la successione di polinomi

$\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.$

dove con $A(x)\mod B(x)$ si indica il polinomio resto nella divisione del polinomio $A(x)$ per il polinomio $B(x)$.

Il numero di distinti zeri reali di $f(x)$ nell'intervallo $[a,b]$, con $f(a)\neq 0$ e $f(b)\neq 0$, è uguale a $V(a)-V(b)$, dove $V(x)$ indica il numero di volte che gli elementi della successione $f_{1}(x),f_{2}(x)...f_{m}(x)$ cambiano di segno, ignorando gli zeri.

Dimostrazione

La successione $\left\{f_{i}(x)\right\}_{i=1,2,...,m}$ è una sequenza di Sturm, abbiamo che

$f(x)=(x-z_{1})^{\mu _{1}}(x-z_{2})^{\mu _{2}}...(x-z_{r})^{\mu _{r}}g(x)$

dove $z_{i}$ è uno zero reale di $f(x)$ con molteplicità $\mu _{i}$ mentre $g(x)$ è un polinomio senza radici reali. Per cui

${\frac {f'(x)}{f(x)}}={\frac {f_{2}(x)}{f_{1}(x)}}=\sum _{k=1}^{r}{\frac {\mu _{k}}{x-z_{k}}}+g(x)$

considerando che le molteplicità sono tutte positive si ottiene

$I_{a}^{b}{\frac {f_{2}(x)}{f_{1}(x)}}=r$

dove si è usato l'indice di Cauchy, il teorema sulle sequenze di Sturm afferma

$I_{a}^{b}{\frac {f_{2}(x)}{f_{1}(x)}}=V(a)-V(b)$

da cui la tesi.

Collegamenti esterni

• (EN) Sturm’s theorem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Algoritmo di Sturm, su MathWorld, Wolfram Research.