title: Algoritmo di Sturm
text: # 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.
  
  