Algoritmo di Sturm

Template:F 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

$\{\begin{array}{c}{f}_1(x)=f(x)\\ f_2(x)=f^{\prime }(x)\\ f_i(x)=-\{f_{i-2}(x)mod{f}_{i-1}(x)\}& \mathrm{\forall }i=3,2,...,m\end{array}$

dove con $A(x)modB(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)\ne 0$ e $f(b)\ne 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 ${\{f_i(x)\}}_{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^{\prime }(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

• Template:Collegamenti esterni