Matematica discreta 2 Complementi ed esercizi dell'Unità 10. |
![]() |
Algoritmi per il calcolo degli autovalori. Il calcolo degli autovalori di una matrice A può essere ricondotto al calcolo delle radici del polinimio caratteristico P(l) della matrice A. Tale polinomio, se la matrice è una matrice nxn, è un polinomio di grado n i cui coefficienti sono funzioni intere dei coefficienti della matrice. La sua espressione esplicita può essere determinata calcolando il determinante della matrice A - lI La condizione precedente garantisce infatti che il sistema ammetta qualche soluzione x non nulla. Il calcolo di questo determinate per matrici grandi diventa molto dispendioso
dal punto di vista algoritmico richiedendo in generale n! operazioni.
Per aggirare queste difficoltà si sono cercati diversi metodi per il calcolo degli autovalori, i quali, come vedremo possono, viceversa, essere anche
usati per
risolvere, per approssimazioni successive, le equazioni algebriche. essendo L la matrice diagonale che ha gli autovalori sulla diagonale principale. Se eseguiamo le potenze successive di A otteniamo, essendo il prodotto di matrici associativo Dato che sappiamo calcolare le potenze della matrice L facendo le potenze degli elementi sulla diagonale, possiamo, con ovvio significato dei simboli, esplicitare il prodotto ![]() eseguendo anche l'ultimo prodotto indicato troviamo che l'elemento si posto i,j della matrice Ak, cioè il prodotto della i-esima riga della matrice P-1 = ((qi,j)) per la j-esima colonna della matrice a sinistra LkP, è dato da ![]() Supponiamo ora che autovalori distinti abbiano moduli dististinti, che l1 sia l'autovalore di modulo massimo (eventualmente ripetuto) |l1| > |ls+1| > |ls+2| > ... > |ln| e che gli elementi di posto i,j (ad esempio 1,1) di tutte le matrici Ak siano non nulli in modo che si possa formare il rapporto ![]() dividendo, a secondo membro numeratore e denominatore per l'autovalore di modulo massimo elevato a k e facendo il limite per k tendente all'infinito, otteniamo ![]() Dato che, per h=s+1,s+2, ... , n, abbiamo ![]() e, in definitiva ![]() Se dunque la matrice A è diagonalizzabile ed esiste un solo autovalore (eventualmente ripetuto s volte) di modulo massimo,
questo autovalore
si approssima col rapporto tra due elementi, il primo
della matrice Ak+1 e il secondo nella matrice Ak, che abbiano la stessa posizione. Maggiore è k, migliore è
l'approssimazione dell'autovalore. ![]() calcolando le sue prime 8 potenze otteniamo le matrici ![]() calcoliamo ora i rapporti tra gli elemeti di posto 1,1 in due matrici successive: abbiamo ![]() Notiamo che già dopo A4 la prima cifra decimale si stabilizza al valore 4, dopo A5 anche la seconda
cifra decimale si stabilizza sul valore 1, per ottenere la terza cifra decimale dobbiamo arrivare ad A6. In definitiva dopo sole 8 potenze
abbiamo il valore dell'autovalore con 3 cifre decimali chiaramente stabili. ![]() le cui radici sono ![]() Questa matrice infatti ha due autovalori distiniti ![]() permettono di calcolare, col metodo precedente, un valore approssimato della radice cubica di n. Il polinomio caratteristico della matrice A è infatti che ha una sola radice di modulo massimo, la radice ![]() permette, tramite le sue potenze, di approssimare la radice di modulo massimo dell'equazione cubica Esercizi (non alla portata di tutti) |