Algoritmo di Sturm
Mattia Costantini
calcolare il numero di soluzioni reali di un'equazione polinomiale in un
intervallo fissato
Grazie anticipatamente
Andrea Francinelli
7bgq4.141519$C3.15...@news.infostrada.it...
Scusa il ritardo con cui rispondo ma ho dovuto rispolverare i miei vecchi
appunti di "Sintesi
delle reti lineari" (risalenti giusto a 10 anni fa).
Per prima cosa occorre definire la sequenza delle funzioni di Sturm.
La prima funzione di Sturm e' lo stesso polinomio P0(x), di cui vuoi
conoscere il
numero di radici reali positive.
La seconda funzione di Sturm e' la derivata prima rispetto a x di P0(x),
cioe'
P1(x) = d/dx P0(x)
La terza funzione di Sturm, P2(x), e' il resto, col segno cambiato, della
divisione tra P0(x) e
P1(x), cioe' vale la relazione:
P0(x) = P1(x) Q1(x) - P2(x)
dove Q1(x) e' il quoziente della divisione.
Questa ultima definizione si applica per definire tutte le rimanenti
funzioni di
Sturm. Quindi in generale, per la (N+1)-esima funzione di Sturm, PN(x), vale
la relazione
P(N-2)(x) = P(N-1)(x) Q(N-1)(x) - PN(x).
cioe' e' il resto, col segno cambiato, della divisione tra le due precedenti
funzioni di
Sturm.
Capisci bene che ogni operazione abbassa come minimo di uno il grado della
funzione di
Sturm successiva. Questo assicura che la successione delle funzioni di Sturm
e' finita.
A questo punto vale il seguente teorema, noto appunto come Teorema di Sturm:
Il numero delle radici reali distinte (nota bene il reali e il distinte!)
della equazione
P0(x) = 0, comprese tra due valori a e b della variabile x, è uguale al
valore assoluto
|Va - Vb| della differenza tra le variazioni di segno Va dei valori che le
successive funzioni
di Sturm assumono per x = a e le variazioni Vb di segno dei valori che le
successive funzioni di
Sturm assumono per x = b.
Come vedi l'affermazione del teorema di Sturm e' un po' piu' generale
rispetto all'utilizzo
"pratico" che se ne fa (che e' quello di verificare la realita' e la
positivita' di una funzione di
rete). Poiche' in generale e' interessante il caso di radici reali positive,
in genere si
esegue il test di Sturm con a = 0 e b = oo.
Alcune note:
1) il teorema vale anche se prima di calcolare la successiva funzione di
Sturm, moltiplico la
funzione per una costante reale positiva. Questo puo' far comodo per
semplificare i calcoli.
2) i quozienti QN(x) di cui sopra sono della forma (px + q), cioe' binomi di
grado 1.
3) il teorema parla in generale di radici distinte, indipendentemente
dall'ordine
di molteplicita'. Poiche' in generale si e' interessati a conoscere la
parita' o
disparita' del grado di molteplicita', l'algoritmo procedera'
differentemente a seconda
dei due casi.
CASO 1: radici distinte (molteplicita' 1)
Si applica pedissequamente il teorema di Sturm. Come esempio considera il
polinomio
P(x)= x^4-5x^2+4 che, come puoi verificare facilmente ha radici 2,
1, -1, -2. La sequenza
di funzioni di Sturm e':
P0(x) = x^4-5x^2+4
P1(x) = 2x^3-5x
P2(x) = 5x^2-8
P3(x) = 9x
P4(x) = 8
(attenzione che nel calcolo e' stata applicata la proprieta' al punto 1 e
quindi i valori
numerici potrebbero risultare differenti rifacendo il calcolo).
Si costruisce quindi la seguente tabella:
P0 P1 P2 P3 P4
x = 0 4 0 -8 0 +8 V0 = 2
x = oo +oo +oo +oo +oo +8 Voo= 0
Dove gli elementi che compaiono nella tabella sono i valori di Pn(x)
calcolati per x = 0
e x = oo. Quindi |V0 - Voo| = 2.
Il numero di radici reali > di 0 (positive) e' quindi 2. Lo zero non
contribuisce al
computo della variazione, a meno che non compaia come primo termine. Cio'
significa che la x per cui si calcola P0 e' proprio una soluzione. In questo
caso
il criterio si presta malamente perche' si ha una variazione o meno a
seconda che
si consideri un piu' o meno delta rispetto al valore di x calcolato. In ogni
caso non
c'e' nessun problema perche' conosco lo zero e posso ridurre il polinomio,
oppure
cambio il punto per cui calcolo il valore di P0 in maniera da escludere o
includere
questa particolare soluzione nel totale di quelle trovate.
Nota bene che, come dicevo prima, nessuno ti vieta di utilizzare il teorema
di Sturm
per determinare il numero di soluzioni in un intervallo qualsiasi, anche
negativo.
Puoi fare la prova se ti va.
CASO 2: radici coincidenti (molteplicita' >1)
In questo caso osserva che P1(x) ha le stesse radici di P0(x) con grado di
molteplicita'
diminuito di 1 rispetto a P0(x). In questo caso la successione di divisioni
che origina le
funzioni di Sturm si arresta prematuramente, senza arrivare al termine noto.
L'ultimo
resto non nullo e' il fattore comune di P0(x) e P1(x), il cui prodotto dei
fattori ha
molteplicita' diminuita di 1. Poiche' questo polinomio e' piu' semplice di
quello
di partenza, si potrebbe scomporlo in fattori e semplificare il problema.
Qualora anche questo risulti di difficile fattorizzazione, si puo' applicare
a questo
polinomio il teorema di Sturm e quindi calcolare la derivata etc....
Purtroppo non ho esempi pronti da darti per questo caso, ma non dovrebbe
essere difficile costruirli.
Questo e' quanto deduco dai miei appunti, lungi dall'essere un trattato sul
teorema di Sturm.
Sicuramente qualcosa di piu', nonche' qualche applicazione, puoi trovare in
qualche testo
di "sintesi di reti lineari analogiche".
E' un vero pecato IMO che queste tecniche di sintesi siano sempre meno
insegnate nei corsi
di elettronica, in favore delle piu' moderne tecniche di sintesi digitale.
Non che queste
ultime non siano importanti, ma e' sbagliato gettare in ingiusto
dimenticatoio la gloriosa sintesi
analogica. Sarebbe bello avere l'opportunita' di studiarle entrambe.
Andrea Francinelli
a.fran...@libero.it