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 .

Algoritmo[modifica | modifica wikitesto]

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.

Dimostrazione[modifica | modifica wikitesto]

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.

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