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.

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