Apri il menu principale

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 .

AlgoritmoModifica

Sia   un polinomio di grado  , definiamo la successione di polinomi

 

dove con   si indica il polinomio resto nella divisione del polinomio   per il polinomio  .

Il numero di distinti zeri reali di   nell'intervallo  , con   e  , è uguale a  , dove   indica il numero di volte che gli elementi della successione   cambiano di segno, ignorando gli zeri.

DimostrazioneModifica

La successione   è una sequenza di Sturm, abbiamo che

 

dove   è uno zero reale di   con molteplicità   mentre   è un polinomio senza radici reali. Per cui

 

considerando che le molteplicità sono tutte positive si ottiene

 

dove si è usato l'indice di Cauchy, il teorema sulle sequenze di Sturm afferma

 

da cui la tesi.

Collegamenti esterniModifica

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