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

{\begin{matrix} f_{1} (x) = f (x) \\ f_{2} (x) = f^{'} (x) \\ f_{i} (x) = - {f_{i - 2} (x) mod f_{i - 1} (x)} & \forall i = 3, 2, ..., m \end{matrix}

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 ${f_{i} (x)}_{i = 1, 2, ..., m}$ è una sequenza di Sturm, abbiamo che

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

dove $z_{i}$ è uno zero reale di $f (x)$ con molteplicità $μ_{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{μ_{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, Sturm Theorem, su MathWorld, Wolfram Research.

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