Calcolo numerico

Formattazione del testo

TB = A Apotrebbe usare la sua fattorizzazione di Cholesky. Tuttavia tale sistema è solitamente mal condizionato; inoltre, a causa degli errori di arrotondamento, nel calcolo di possono andar perdute cifreTA Asignificative con conseguente perdita della definita positività o addirittura della non singolarità dellamatrice. È quindi in generale più conveniente impiegare la fattorizzazione introdotta in precedenzaQR(Definizione 3.1).

Teorema 3.18. Consideriamo un sistema lineare sovradeterminato , SeR m⇥n2Ax = b, A m n.ha rango n (pieno), la soluzione di tale sistema nel senso dei minimi quadrati è data daA ⇤ 1 Tx = R̃ Q̃ bdove e sono le matrici della fattorizzazione ridotta diR̃ Q̃ QR A.26Si assuma che tutte le matrici con rango pieno ammettano un’unica fattorizzazioneDimostrazione.Essendo ortogonale (Q avremo che , infattiT T 22 22 T 22kyk kQyk kQQR. Q Q = QQ = I), = = yk22 T T T T 22kyk kQyk= y y = y Q Qy = (Qy) Qy =22 T T T T T T

T 22kyk kQ= y y = y QQ y = (Q y) Q y = yk

Scriviamo il residuo nella norma euclidea sostituendo A = QR22 22 22 T 22

usiamo la proprietà kAx kQRx kyk kQbk = bk = yk

T 22 T 22 ricordando che è trapezoidale superiorekQ k kRx= (QRx b) = Q bk RmXT 22 T 2k= R̃x Q̃ bk + (Q b) ii=n+1

Quindi è minimo quando ⇤ ⇤ ⇤22 T 22 T 1 TkAx k ! !bk R̃x Q̃ bk = 0 R̃x Q̃ b = 0 x = R̃ Q̃ b.

274 Autovalori ed autovettori

Consideriamo il seguente problema: data una matrice quadrata , trovare uno scalare edC Cn⇥n2 2Aun vettore non nullo tali che Il vettore è detto associato all’autovaloreautovettoreC n2x Ax = x. xe l’insieme degli autovalori di A è detto lo di A, denotato con Diciamo che espettro (A). x ysono rispettivamente un autovettore destro e sinistro di A, associati all’autovalore , se Ax = x,.H Hy A = yIl numero è soluzione dell’equazione caratteristica det(A dove è il polinomiop ( ) = I) = 0, p ( )A AEssendo

quest’ultimo un polinomio di grado rispetto a , la matrice A ha esattamentecaratteristico. nautovalori, non necessariamente distinti. Gli autovettori associati a tali autovalori sono infiniti enverificano il sistema lineare L’autovalore , corrispondente all’autovettore si ottiene(A I)x = 0. x,calcolando il .quoziente di Rayleigh H H H 2= x Ax/(x x) = x Ax/(kxk )2Q Pn nSi può dimostrare che det(A) , tr(A) di conseguenza se A è una matrice diagonale= =i ii=1 i=1o triangolare, gli autovalori sono dati direttamente dagli elementi diagonali. Una matrice è singolarese e solo se ha almeno un autovalore nullo. Gli autovalori di sono i reciproci degli autovalori di1ASi dimostra che gli autovettori di ed sono gli stessi.1A. A AEssendo si deduce che ed analogamenteT T Tdet(A I) = det((A I) ) = det(A I), (A) = (A )che Se gli elementi di A sono numeri reali, è un polinomio a coefficienti reali eH(A ) = ( Ā). p ( )Adunque gli autovalori complessi

metodoparziale) si ottiene un'approssimazione di una particolare coppia autovalore/autovettore. Il metodoQR (un metodo globale) può fornire invece l'approssimazione diretta di tutti gli autovalori di A, ma non dei corrispondenti autovettori.

4.1 Il metodo delle potenze

In molte applicazioni non è necessario conoscere l'intero spettro di A, ma ci si può limitare ad A, individuare gli autovalori estremi, così come l'autovalore più vicino ad un dato numero C.

2µCalcolo dell'autovalore di modulo massimo

Data una matrice A, vogliamo trovare l'autocoppia con autovalore di modulo massimo, autovettore associato avente norma euclidea unitaria (kx = 1).

1 1 1

1 1 2

che ciò che rende ben posto (unica soluzione) il problema della ricerca dell'autovettore è l'avere posto A.

Tal fine consideriamo la seguente procedura, nota come metodo delle potenze.

kx k = 1

1 2

1. Assegnato

un arbitrario vettore iniziale si poneC(0) n2y(0)y (0) (0) H (0)(0)x = , = (x ) Ax(0)ky k2 28dove abbiamo sfruttato il quoziente di Rayleigh per il calcolo dell'autovalore associato (con(0) 2k(kx ) = 1).22. Per finché risulta verificato il criterio d'arresto (test sull'incremento)k = 1, 2, ..., (k) (k 1) (k)| | | |< "dove è una tolleranza assegnata (al passo 1 faccio in modo che tale test sia verificato), si calcola" (k)y(k) (k 1) (k) (k) (k) H (k)y = Ax , x = , = (x ) Ax(k)ky k2(si noti che il calcolo di serve soltanto per verificare il criterio d'arresto al passo 1).(0)Si noti che, procedendo in modo ricorsivo, si ottienek (0)A x(k)x = , k 1k (0)kA kx 2La presenza delle potenze di A giustifica il nome del metodo.Si noti che nel caso in cui il vettore coniugato trasposto coincide con il traspostoR n⇥n (k) H2A (x ) =. Questo non ha implicazioni in sede di programmazione in quanto in Matlab entrambe tali(k) T(x )operazioni si

Indicano con x’ il seguente risultato di convergenza.

Vale il seguente risultato di convergenza. Teorema 4.1 del metodo delle potenze.

(Convergenza Consideriamo il metodo delle potenze applicato ad una matrice per la ricerca dell’autocoppia con autovalore di modulo C n⇥n2A ( , x ),1 1 1 massimo, autovettore associato avente norma euclidea unitaria (kx Se è diagonalizzabile ed inoltre l’autovalore di modulo massimo è isolato (| distinto dai moduli dei restanti(b) |1 autovalori, che implica che deve avere molteplicità algebrica pari a 1), ovvero1 | | | | | | ··· | |>1 2 3 n allora la successione di autocoppie generata dal metodo delle potenze converge all’autocoppia(k) (k)( , x )( , x ).1 1 Se è diagonalizzabile, esiste una base di formata da auto-Dimostrazione (convergenza di ). C(k) nx Avettori di A. Indichiamo tali autovettori con , per È possibile pertanto rappresentarex i = 1, ..., n.icome combinazione lineare di tali autovettori,

zero.Osserviamo ora che in aritmetica non esatta per qualsiasi scelta di . Ovvero(0)6lim ↵ = 0 yk!1 1anche prendendo il vettore iniziale ortogonale all’autovettore relativo all’autovalore di modulo massimo(↵ l’insorgere degli errori di arrotondamento comporta la comparsa di una componente nella= 0)1direzione di anche se questa non era presente nel vettore iniziale (questo è evidentemente uno deix 1rari casi in cui gli errori di arrotondamento giocano a nostro favore). Di conseguenza non si rendenecessaria nessuna restrizione sulla scelta di (la scelta di un vettore non ortogonale a sarebbe(0)y x 1comunque impossibile, essendo tale vettore incognito).Supponendo invece di lavorare in aritmetica esatta, si può dimostrare che se il metodo delle↵ = 0,1potenze converge alla coppia (l’autovalore trovato è quindi quello di modulo massimo tra quelli( , x )2 2che hanno autovettori non ortogonali a ).(0)yAlla luce delle ultime