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 ${\displaystyle (a,b)}$.

Algoritmo

Sia ${\displaystyle f(x)}$ un polinomio di grado ${\displaystyle n}$, 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.}$

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

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

Dimostrazione

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

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

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

${\displaystyle {\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

${\displaystyle 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

${\displaystyle 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, Sturm Theorem, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica