Algoritmo di Sturm

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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.

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