Autovalori

6 febbraio 2017

In questo documento i diversi fonti di caratteri utilizzati hanno il seguente si-gnificato:

corsivo italico: a → qualsiasi quantita scala-re (complessa, reale ointera);

sans-serif minuscolo: a → vettore con componentireali;

SANS-SERIF MAIUSCOLO: A → matrice con elementi reali;

grassetto minuscolo: a → vettore con componenticomplesse;

CALLIGRAFICO MAIUSCOLO: A → matrice con elementicomplessi;

Inoltre quando si utilizzeranno lettere greche s’intendera sistematicamente, esalvo esplicito avviso contrario, indicare angoli del primo quadrante, con le soleeccezioni di π, che denominera, come in tutto l’Universo, la ben nota costante,di λ e µ, riservate piuttosto agli autovalori delle matrici, e di δ, che indichera ilsimbolo di Kronecker.In tutto il testo si adottera, salvo esplicito avviso contrario, la convenzione diEinstein della somma sottintesa sugli indici ripetuti, vale a dire che scrivere, inuno spazio di dimensione n:

aikakj

implica e sottintenden∑

k=1

aikakj

1

1 Considerazioni generali

In questa sezione si fara un breve compendio di nozioni provenienti dall’algebralineare.

1.1 il prodotto scalare

Dati due vettori reali n-dimensionali a = ak, k = 1, · · ·n e b = bk, k = 1, · · ·n, illoro prodotto scalare e il numero reale p:

p ≡ a · b = akbk (1)

Se p e nullo senza che lo siano ne a ne b i due vettori sono ortogonali.Esempio: a = {1,−1} e ortogonale a b = {1, 1}Il prodotto scalare tra vettori reali e evidentemente commutativo e bilineare;∀qi (coppia di numeri reali) vale:

a · b = b · a (2)

(q1a+ q2b) · c = q1a · c+ q2b · c (3)

Altresı il prodotto scalare di ogni vettore reale con se stesso ne da il quadratodel modulo:

a · a = |a|2 (4)

Nel caso di vettori con componenti complesse, proprio il rispetto della (4) im-pone la seguente definizione di prodotto scalare, che contiene la (1) come casoparticolare; se a = ak, k = 1, · · ·n e b = bk, k = 1, · · ·n sono due vettori concomponenti complesse, il loro prodotto scalare e il numero complesso p:

p ≡ a · b = akbk (5)

in cui, come d’abitudine, la sovralineatura indica l’operazione di complessa co-niugazione. Le proprieta di commutativita e di bilinearita si conservano proprioa prezzo di questa operazione aggiuntiva, nel senso che ∀qi (coppia di numericomplessi) vale:

a · b = b · a (6)

(q1a+ q2b) · c = q1a · c+ q2b · c (7)

mentre la (4) permane appunto inalterata ∀a con componenti complesse.

1.2 le matrici

Una matrice A con elementi complessi non e altro che

A = B+ iC (8)

ove B e C sono due matrici con elementi reali che potrebbero a buon diritto esserechiamate rispettivamente “parte reale” e “parte immaginaria” di A. Pertanto le

2

matrici reali stesse non sono altro che matrici complesse con parte immaginarianulla, ne piu ne meno di quel che accade per gli scalari.Con le matrici complesse si eseguono le stesse operazioni che si e abituati acompiere con le matrici reali, ovviamente tenendo conto dell’algebra complessae quindi con l’aggiunta della complessa coniugazione (che e neutra per le ma-trici reali) e dei suoi frutti. Verra, con ogni ovvieta, denominata “complessaconiugata” della matrice A in (8) la matrice:

A = B− iC (9)

con le stesse B e C cola introdotte. Si puo osservare che, diversamente da quantoavviene per gli scalari, il prodotto matriciale AA non e, in generale, una matricecon parte immaginaria nulla: affinche cio accada occorre che B e C commutino.In effetti si vede facilmente che

AA = B2 + C

2 + i(BC− CB) = AA (10)

Non e certo questa ne la sola ne la prima conseguenza del fatto che l’algebradelle matrici non sia commutativa.

Nel campo dei numeri reali il concetto di matrice trasposta AT di una matrice

A nasce da semplici considerazioni sul prodotto scalare tra un arbitrario vettoreb e quello che si ottiene applicando A a un altrettanto arbitrario vettore a, ossiadalla valutazione di:

b · (Aa) (11)

domandandosi quale matrice occorrerebbe applicare a b affinche il prodottoscalare a · (Bb) abbia esattamente lo stesso valore. Applicando (1) e tenutoconto che la componente k−esima di Aa e data da (A)klal si ha:

b · (Aa) ≡ bk(A)klal (12)

a · (Bb) ≡ ak(B)klbl (13)

Data la totale arbitrarieta di a e b le due ultime espressioni possono coincideresolo se (B)kl ≡ (A)lk ossia, appunto, quando B e la matrice trasposta di A.

Analoghe considerazioni, se esportate al campo dei numeri complessi, portanoalla definizione di matrice aggiunta: A†. In effetti, mutatis mutandis, dalle dueespressioni, omologhe alle (12) e (13):

b · (Aa) ≡ bk(A)klal (14)

a · (Bb) ≡ ak(B)klbl (15)

richiedendo stavolta, per coerenza di definizione, che la seconda sia la complessaconiugata della prima, si vede immediatamente che questo puo essere vero solose (B)kl = (A)lk, ed e questa, appunto, la definizione di matrice aggiunta:

(A†)kl = (A)lk (16)

3

In termini di parti reale e immaginaria, ricordando (8), si ha

A† = BT − iCT (17)

Si apprezzi la differenza rispetto alla definizione di A in (9). Una matricecomplessaA che abbia la propria aggiunta uguale a se stessa si dice autoaggiuntao anche hermitiana: dall’esame congiunto della (8) e della (17) si deduce subitoche cio richiede alla parte reale di una siffatta matrice di essere simmetrica(BT = B) e a quella immaginaria di essere antisimmetrica (CT = −C); ne segueche una matrice autoaggiunta ha sulla propria diagonale solo elementi reali.

Una matrice complessa invertibile U che abbia come propria inversa la propriaaggiunta si dice unitaria. La denominazione risente del fatto che, in tal caso, siha:

U†U = UU† ≡ I (18)

ove, ovviamente, I e la matrice identita di uguale dimensione. Cio significa,esprimendo il prodotto tra matrici, come d’abitudine, in termini degli elementidelle matrici stesse:

(U†)lk(U)km ≡ (U)kl(U)km = δlm (19)

vale a dire che le righe di U (o le colonne, utilizzando il prodotto commutato)sono costituite da una base di versori ortogonali a due a due. La stessa (18) diceche, se U e una matrice unitaria, lo e anche U†, essendo evidente che (U†)† ≡ U .Scrivendo U in termini delle sue parti reale R e immaginaria S si vede che lacondizione (18) impone:

(RT − iST )(R+ iS) ≡ I = RTR+ S

TS+ i(RTS− S

TR) (20)

e quindi il prodotto RTS (o, equivalentemente, quello S

TR) deve essere una

matrice simmetrica, mentre a coincidere con la matrice identita deve essere lasomma R

TR+ S

TS. Nel caso particolare in cui o R o S siano nulle, l’altra deve

essere una matrice ortogonale.

Esempi:(

1 1 + i1− i 2

)

=

(

1 11 2

)

+ i

(

0 1−1 0

)

(21)

e una matrice autoaggiunta non invertibile, mentre

1

2

(

eiπ4 −

√3e−i

π4

i√3 1

)

=1

2

(

1√2−√

32

0 1

)

+i

2

(

1√2

√

32√

3 0

)

(22)

e una matrice unitaria: si osservi che ne la parte reale ne quella immaginariasono individualmente ortogonali e tuttavia valgono sia la (19) sia la (20).

4

1.3 caratteristiche delle matrici in relazione ai loro auto-

valori

Se esiste un sottospazio lineare dello spazio vettoriale ambiente un cui vettorea soddisfa l’equazione

Aa = λa (23)

per qualche matrice A e qualche numero complesso λ si dice che a e un au-tovettore di A per l’autovalore λ e il sottospazio lineare cui appartiene si diceautospazio di A per quell’autovalore.E essenziale che a non sia il vettore nullo, che non genera alcun sottospazio; delresto affermare che il vettore nullo verifichi la (23) e una volgarita, perche in talcaso la (23) stessa sarebbe un’identita, non un’equazione.Il significato geometrico della (23) consiste nell’individuazione di un sottospaziolineare su cui A agisca come uno scalare.Il teorema di Rouche–Capelli assicura l’esistenza di a se λ e una soluzionedell’equazione caratteristica di A:

det(A− λI) = 0 (24)

e, poiche il primo membro di questa equazione e un polinomio in λ di gradopari alla dimensione dello spazio ambiente, il teorema fondamentale dell’algebraci fa concludere che ogni matrice quadrata in uno spazio n−dimensionale pos-siede n autovalori nel campo complesso, eventualmente contati con multiplicitaalgebriche maggiori di uno.

Tuttavia per talune matrici, segnatamente quelle autoaggiunte e quelle unitarie,il sottoinsieme in cui vanno collocati gli autovalori risulta notevolmente ristret-to, riducendosi per le prime all’asse reale e per le seconde al cerchio di raggio 1,vale a dire a sottoinsiemi del piano complesso con misura zero rispetto a quelladel piano. E poiche il determinante di una matrice ne e il prodotto degli auto-valori possiamo concludere immediatamente che il determinante di una matriceautoaggiunta e un numero reale e che quello di una matrice unitaria e un numerocomplesso di modulo 1. Cio e verificabile direttamente sui due esempi fornitialla fine della sezione precedente e puo essere dimostrato in quattro parole sesolo si ricorda la definizione di autovalore e di autovettore corrispondente.

1.3.1 matrici autoaggiunte

Come gia detto tutti gli autovalori λk, k = 1, · · · , n di una matrice autoaggiuntasono reali e tutti gli autovettori corrispondenti, quale ne sia il numero, eventual-mente minore di n in presenza di autovalori multipli, sono a due a due ortogonalirispetto al prodotto scalare definito in (5): si tratta di un’ovvia estensione alcampo complesso di quanto dovrebbe essere gia noto, in campo reale, per lematrici simmetriche rispetto al prodotto scalare ordinario (1). In effetti bastadimostrare che gli autovalori della matrice aggiunta sono i complessi coniugati

5

di quelli della matrice originale per giungere alla conclusione enunciata: se λ eun generico autovalore di A, con autovettore corrispondente a, e µ e un genericoautovalore di A†, con autovettore corrispondente b, si ha, in successione:

µa · b ≡ a · (A†b) ≡ (A†b) · a ≡ b · (Aa) ≡ λb · a ≡ λ b · a ≡ λa · b (25)

e per l’assunta genericita tanto di λ quanto di µ si conclude appunto che l’insiemedegli autovalori di A† e costituito dai complessi coniugati degli autovalori di A.Quanto all’ortogonalita reciproca degli autovettori di una matrice autoaggiuntabasta considerarne due, k e l, corrispondenti ad autovalori diversi, e, a questopunto, reali, λk 6= λl:

0 ≡ k · (Al)− k · (A†l) ≡ k · (Al)− (Ak) · l ≡ (λl − λk)k · l (26)

che prova l’asserto. Va notato che le stesse dimostrazioni si possono ripete-re per le matrici reali simmetriche, semplicemente sostituendo l’operazione ditrasposizione a quella di aggiunzione e abolendo la necessita della complessaconiugazione del prodotto scalare commutato; come immediata conseguenza dicio si deduce che, nel campo reale, gli autovalori di AT sono gli stessi di A, ∀A.

1.3.2 matrici unitarie

Tutti gli autovalori di una matrice unitaria sono situati sul cerchio di raggio 1 delpiano complesso; se la matrice unitaria e anche autoaggiunta i suoi autovalorisono soltanto ±1. Quest’ultima proposizione e evidentemente una conseguenzadiretta della precedente e di quanto affermato circa gli autovalori delle matriciautoaggiunte. In effetti, se U e una matrice unitaria e λ un suo generico auto-valore con corrispondente autovettore u, che, senza perdita di generalita, si puosupporre normalizzato a 1, si ha, in successione:

|λ|2 ≡ |λ|2u · u ≡ (λu) · (λu) ≡ (Uu) · (Uu) ≡ u · (U†Uu) ≡ u · u ≡ 1 (27)

Si puo osservare che, nella catena di uguaglianze appena scritta, l’ipotesi diunitarieta sopravviene solo nella penultima: tutte le precedenti valgono perqualsiasi matrice. Ne consegue che, data una matrice complessa qualsiasi A,A†A (e anche AA†) e una matrice autoaggiunta i cui autovalori reali sono iquadrati dei moduli degli autovalori di A (e di A†). In sostanza, per le matricicomplesse, non e il prodotto AA, come gia si e visto, a fungere da matrice“reale”, come avviene con gli scalari, ma piuttosto il prodotto A†A. D’altraparte, che A†A e AA† siano autoaggiunte risulta palese dalla stessa definizionedi matrice aggiunta, che porta in se, come conseguenza immediata, il fatto che lamatrice aggiunta di un prodotto e il prodotto delle matrici aggiunte dei singolifattori, eseguito in ordine invertito, esattamente come accade con l’operazionedi trasposizione nelle matrici reali:

(AB)† ≡ B†A† (28)

6

1.3.3 i cerchi di Gerschgoring

Se una matrice non ha doti particolari i suoi autovalori, in linea di principio,possono trovarsi ovunque nel piano complesso. Tuttavia e ugualmente possibileindividuarne un preciso sottoinsieme che di certo li conterra tutti: a questoservono i cerchi di Gerschgoring.

Ogni matrice quadrata n × n, complessa o reale che sia, individua nel pianocomplesso n cerchi–riga di Gerschgoring e altrettanti cerchi–colonna: con ognievidenza i cerchi–riga sono i cerchi–colonna della matrice aggiunta (o trasposta,nel caso di matrice reale) e viceversa.La definizione del k–esimo cerchio–riga di Gerschgoring, sia denominato Rk, ela seguente:

Rk := {z} ∈ C→ |z − (diagA)k| ≤ rk ≡∑

j 6=k|akj | (29)

quella del k–esimo cerchio–colonna, Ck, essendo completamente analoga conla sola sostituzione di akj con ajk e avendo indicato con diagA il vettore n–dimensionale formato con gli elementi diagonali di A. Restando sui cerchi–riga,si tratta appunto di cerchi nel piano complesso coi centri situati nei punti rap-presentati dai valori dei numeri complessi posti lungo la diagonale della matricee coi raggi rk dati dalla somma dei moduli degli elementi di matrice posti sullariga k–esima, escludendone appunto l’elemento diagonale; si osservi che solo perle matrici autoaggiunte (o, in particolare, reali simmetriche) i cerchi–riga coin-cidono esattamente con i cerchi–colonna, con tutti i centri situati lungo l’assereale.

Come e evidente dalla loro stessa definizione i cerchi di Gerschgoring sono tantopiu piccoli quanto piu la matrice che li definisce e prossima a essere diagonale,finendo col collassare in cerchi di raggio nullo, ossia in punti del piano complessoche ne costituiscono il centro, per le matrici diagonali. Dato che e altrettantoevidente che, in un caso simile, gli elementi diagonali della matrice, ossia i centridei cerchi di Gerschgoring degenerati in un solo punto, sono gli autovalori stessidella matrice, si puo facilmente comprendere il significato del primo teorema diGerschgoring il cui enunciato recita:

gli autovalori λ di qualsiasi matrice A, con elementi complessi, si trovano nel-l’unione dei cerchi–riga della matrice; quelli di A† si trovano nell’unione deicerchi–colonna.

La seconda proposizione dell’enunciato e una conseguenza diretta della prima edelle definizioni di matrice aggiunta e di cerchi–colonna. Altrettanto evidente eil corollario secondo cui, se la matrice ha elementi reali, allora gli autovalori sitrovano nell’intersezione fra le due unioni, data la coincidenza degli autovaloridi A con quelli di AT .

7

Resterebbe quindi da provare solo la prima proposizione dell’enunciato, e questosi fa in poche battute; se A ha l’autovalore λ, con autovettore corrispondentea, ossia vale la (23), allora esiste certamente una componente am di a che ha ilmassimo modulo rispetto a tutte le altre componenti, e questo massimo moduloe non nullo, altrimenti sarebbe nullo a stesso.Si riscriva dunque la (23), per la sua componente m–esima, nel seguente modo:

∑

k 6=m(A)mkak + (diagA)mam = λam (30)

ossia evidenziando il contributo di am alla sommatoria sottintesa al primo mem-bro dell’equazione. Allora, poiche e di certo am 6= 0, risulta lecito dividere peram trovando:

λ− (diagA)m =∑

k 6=m(A)mk

akam

(31)

Valutando i moduli dei due membri dell’ultima equazione si ha:

|λ− (diagA)m| ≡

∣

∣

∣

∣

∣

∣

∑

k 6=m(A)mk

akam

∣

∣

∣

∣

∣

∣

≤∑

k 6=m|(A)mk|

|ak||am|

(32)

Per l’ipotesi assunta su |am| tutte le frazioni nell’ultima sommatoria sono mag-giorabili con la costante 1, per cui, in definitiva:

|λ− (diagA)m| ≤∑

k 6=m|(A)mk| ≡ rm (33)

essendo appunto rm il raggio dell’m–esimo cerchio–riga di Gerschgoring; l’ulti-ma disuguaglianza dice appunto che λ e contenuto in quel cerchio e quindi, perla genericita sia di λ che dim, l’asserto e provato. Non e poi difficile provare che,se l’unione dei cerchi di Gerschgoring e costituita di diverse componenti connes-se a intersezione vuota, ciascuna componente connessa contiene un numero diautovalori pari al numero di cerchi che concorrono a formare quella componentee, al limite in cui tutti i cerchi di Gerschgoring fossero a due a due disgiunti,ciascun cerchio contiene un solo autovalore.I cerchi di Gerschgoring sono, per quanto fin qui detto, uno strumento sempliceatto a fornire una prima localizzazione approssimativa degli autovalori, utilecome punto di partenza per algoritmi di ricerca basati sul raffinamento di unastima iniziale del valore vero.

1.4 Le trasformazioni di similarita

Per ogni matrice con elementi complessi A, e per ogni altra matrice invertibileB, il prodotto

A′ ≡ B−1AB (34)

genera un’altra matrice A′ che viene detta simile ad A: la trasformazione (34)e appunto detta trasformazione di similitudine o di similarita.

8

Si osservi che la relazione di similitudine tra matrici e reciproca, nel senso chese A′ e simile ad A, anche A e simile ad A′ tramite la matrice inversa B−1,come si evince facilmente dalla stessa (34).

Due matrici simili, A e A′, hanno gli stessi autovalori.

In effetti, se a e un autovettore di A, corrispondente a un suo generico autovaloreλ, per l’invertibilita di B e possibile definire univocamente un altro vettoreb = B−1a di modo che si abbia:

Aa ≡ λa←→ ABb ≡ λBb (35)

Ma moltiplicando da sinistra per B−1 entrambi i membri dell’ultima eguaglianzasi ottiene:

B−1ABb ≡ A′b = λB−1Bb = λb (36)

che, per la genericita di λ, prova l’asserto.

Se la matrice A dispone di un sistema completo di autovettori linearmenteindipendenti {al}, l = 1, 2, · · ·n, allora, scegliendo B come la matrice che recaordinatamente nelle proprie colonne tali autovettori, invertibile per costruzione,la matrice simile A′ generata dalla (34) risulta diagonalizzata, ossia ha tutti glielementi nulli tranne, al piu, quelli diagonali che coincidono con gli autovalo-ri di A, come gia detto, disposti nello stesso ordine con cui sono disposti gliautovettori corrispondenti in B.

In effetti, poiche con una tale scelta di B e immediato constatare che al ≡ Bel∀l,ove con el si sono indicati i versori della base canonica, e subito evidente che ivettori bl ottenuti partendo da ciascun al sono i versori canonici stessi, per cuile equazioni che determinano gli autovalori di A′ (e quindi di A) non sono altroche (sospendendo qui la convenzione della sommatoria sottintesa)

A′bl ≡ A′el ≡ λlel l = 1, 2, · · ·n (37)

che e la formalizzazione dell’asserto.

Se la matrice B che produce la trasformazione (34) e unitaria, allora la suainversa non solo certamente esiste, ma e null’altro che la sua aggiunta (cfr.(18)); allo stesso modo, restringendosi al campo delle matrici reali, se si esegueuna trasformazione di similitudine mediante una matrice B ortogonale, alloral’inversa e semplicemente la matrice trasposta B

T .Tutto quanto esposto nella presente sezione lascia chiaramente intendere che ilproblema della determinazione degli autovalori di una matrice si trasforma inquello della ricerca di una matrice simile per la quale il calcolo degli autovalorisia di gran lunga piu semplice o addirittura inutile, in quanto gli autovalori stessiappaiono esplicitamente come elementi della matrice simile. E sara senz’altro

9

preferibile cercare la matrice simile mediante una matrice di trasformazioneunitaria (ortogonale) che non necessita di alcun calcolo per la determinazionedella matrice inversa.

1.5 I casi triviali per il calcolo degli autovalori

Una matrice A, con elementi appartenenti a qualunque campo numerico, si dicetriangolare superiore (inferiore) se ogni suo elemento ajk con j > k (j < k) enullo. La matrice trasposta di una matrice triangolare superiore e dunque unamatrice triangolare inferiore, e viceversa.Una matrice triangolare che sia anche simmetrica si dice matrice diagonale: unesempio e stato dato nella precedente sezione (cfr. (37)); una matrice diagonalee dunque una matrice triangolare simultaneamente inferiore e superiore.

Ogni matrice triangolare A (intendendo con questo l’unione delle triangolarisuperiori e inferiori) ha i propri autovalori coincidenti con le componenti delvettore diag(A), ossia con i suoi elementi diagonali.

In effetti l’equazione secolare (24) di una tale matrice risulta completamentefattorizzata:

0 = det(A− λI) ≡n∏

l=1

(diag(A)l − λ) (38)

e l’asserto ne segue per evidenza; pertanto per determinare gli autovalori di unamatrice triangolare non e necessario svolgere alcun calcolo.

Un caso particolarissimo di matrice triangolare e dato dalle matrici nihilpotenti,ossia quelle matrici N per le quali esiste una loro potenza intera 1 < k ≤ n,ove n e, come al solito, la dimensione dello spazio ambiente, tale che N k ≡0. Una matrice cotale ha SOLO l’autovalore nullo, con multiplicita n (si puodimostrare facilmente che il suo polinomio caratteristico “degenera” appuntonel solo monomio λn).

Una matrice P, con elementi appartenenti a qualsiasi campo numerico, si diceidempotente, o anche matrice di proiezione, se P2 = P, e quindi Pk = P perqualsiasi potenza intera k ≥ 1. Una matrice cotale ha SOLO gli autovalori 1 e 0(quindi non e mai invertibile, a meno che non sia l’identita, che e chiaramenteidempotente ma che peraltro NON ha l’autovalore nullo, bensı SOLO l’autova-lore 1 con multiplicita n); l’autovalore 1 ha multiplicita pari al rango r < n diP, con la multiplicita residua (n− r) che pertiene all’autovalore 0.

2 Algoritmi

In questa sezione si parlera di tecniche numeriche idonee alla determinazionedegli autovalori di una matrice qualsiasi; come gia sottolineato si trattera, indefinitiva, di ricercare la migliore trasformazione di similitudine possibile ai

10

fini del conseguimento del risultato ossia, possibilmente, di trovare una matricesimile che sia triangolare. Si parte introducendo alcune definizioni e alcunistrumenti utili.

2.1 Matrici in forma di Hessenberg

Una matrice qualsiasi A, con elementi presi in qualsiasi campo numerico, sidice in forma di Hessenberg superiore (inferiore) se tutti i suoi elementi ajkcon j > k + 1 (k > j + 1) sono nulli: si tratta di una generalizzazione delladefinizione delle matrici triangolari e, ovviamente, una matrice triangolare eanche una matrice in forma di Hessenberg.Affinche pero la definizione non risulti vuota occorre applicarla a matrici cheabbiano almeno 3 righe e colonne.Come per le matrici triangolari, la trasposta di una Hessenberg inferiore e unaHessenberg superiore e viceversa; una matrice in forma di Hessenberg che siaanche simmetrica diventa una matrice tridiagonale simmetrica, senza per questoescludere la possibilita dell’esistenza di matrici tridiagonali NON simmetricheche restano comunque matrici di Hessenberg simultaneamente superiori e infe-riori.

Esempio:

La matrice

A =

1 1 1 11 2 2 20 1 3 30 0 1 1

(39)

e in forma di Hessenberg superiore (non e invertibile, ma questo non inficial’esempio).

2.2 Matrici di Givens

Una matrice Grs con elementi complessi (ovvero una matrice Grs con elementi

reali) si dice matrice di Givens rispetto alle righe r e s, con r 6= s, se e ottenutasostituendo ordinatamente i quattro elementi che si trovano agli incroci tra lerighe e colonne r e s della matrice identita di pari rango con i quattro elementidi una matrice unitaria (ortogonale) 2 × 2. Tali matrici sono evidentementeunitarie (ortogonali) per costruzione.

Esempio:

11

Nello spazio reale quadridimensionale una valida espressione per la matrice diGivens G24 potrebbe essere, ∀α:

G24(α) =

1 0 0 00 cos(α) 0 − sin(α)0 0 1 00 sin(α) 0 cos(α)

(40)

Dovrebbe essere abbastanza evidente che in uno spazio ambiente di dimensionen esistono n(n− 1)/2 matrici di Givens “geometricamente” diverse.

2.3 Matrici di Householder

Una matrice H, con elementi complessi (reali) si dice matrice di Householder sei suoi elementi (H)kl hanno la seguente espressione generale:

(H)kl ≡ δkl − 2 u(r)k u

(r)l (41)

in cui δ e il simbolo di Kronecker (e quindi δkl e l’espressione generica per glielementi di una matrice identita) e i vettori u(m),m = 1, 2, · · · d ≤ n sono ver-sori ortogonali nello spazio ambiente n–dimensionale. Se lo spazio ambiente ereale la definizione e la stessa, vista la neutralita, in tal caso, dell’operazionedi complessa coniugazione; ovviamente, come sempre convenuto, la ripetizio-ne dell’indice r nell’espressione data implica sommatoria su tutti i d versoriconsiderati.La matrice (41) e evidentemente autoaggiunta (simmetrica), per costruzione:H† ≡ H; meno evidente potrebbe apparire il fatto che essa sia anche unitariae che, di conseguenza, coincida con la propria inversa. Per esserne persuasi esufficiente mostrare che il quadrato di H e la matrice identita. In effetti:

(H2)kl ≡ (H)kp(H)pl ≡ [δkp − 2 u(r)k u(r)p ][δpl − 2 u(s)p u

(s)l ] (42)

in cui si e semplicemente ricopiata due volte la definizione (41) e tenuto contodel fatto che il nome attribuito a ogni indice sommato e irrilevante. Proseguendolo svolgimento dei calcoli (algebra di scuola media) si ha:

(H2)kl ≡ δkpδpl − 2 δkp u(s)p u

(s)l − 2 u

(r)k u(r)p δpl + 4 u

(r)k u(r)p u(s)p u

(s)l (43)

Si tratta ora di portare a compimento la sommatoria sull’indice p (significa, difatto, eseguire effettivamente il quadrato); nel primo dei quattro addendi si hasemplicemente

δkpδpl −→ δkl (I2 ≡ I) (44)

Il secondo e il terzo addendo, una volta eseguita la somma su p, sono identici,stante l’irrilevanza del cambio di nome tra r e s, che sono comunque sommatisu tutti i loro possibili valori; dunque, tenuto conto di quanto fin qui detto:

(H2)kl ≡ δkl − 4 u(s)k u

(s)l + 4 u

(r)k u(r)p u(s)p u

(s)l (45)

12

Eseguendo infine la somma su p nell’ultimo addendo e facile riconoscere in

u(r)p u

(s)p null’altro che il prodotto scalare del vettore u(r) con il vettore u(s):

per l’ipotesi assunta su tali vettori il prodotto scalare fra loro vale δrs, rendendocosı l’ultimo addendo opposto al penultimo. In definitiva (H2)kl ≡ δkl, ossia,come si voleva provare, H2 ≡ I←→ H† = H−1 = H.Il risultato appena ottenuto implica, come conseguenze immediate, che qualsiasipotenza intera dispari di H coincide con H, mentre qualsiasi potenza intera parida l’identita.

2.3.1 significato geometrico delle matrici di Householder

Se si ricorda quanto detto nella sezione 1.3.2 si riconosce nelle matrici di Hou-seholder un caso evidente di matrici che sono simultaneamente autoaggiunte eunitarie e quindi i loro autovalori possono essere soltanto ±1. Dato che ope-rano in spazi di dimensione arbitraria e evidente che debba esserci un’ampiadegenerazione per quanto attiene alle dimensionalita degli spazi generati dagliautovettori corrispondenti a questi due soli autovalori distinti. Non e difficilericonoscere che qualsiasi vettore v che sia una combinazione lineare dei vettoriu(m) che concorrono alla definizione di H, e quindi, in particolare, ciascuno diquei d vettori, e autovettore di H corrispondente all’autovalore −1, mentre qual-siasi vettore w appartenente al complemento ortogonale (n − d)–dimensionaledel sottospazio generato dagli u(m) e autovettore di H corrispondente all’altroautovalore. Pertanto, dato che qualsiasi vettore x, arbitrariamente scelto nellospazio ambiente, puo essere decomposto in maniera univoca come somma di duealtri vettori v e w: x = w + v, con v situato nel sottospazio lineare generatodagli u(m) e w nel suo complemento ortogonale, l’azione di H su un tale vettorearbitrario si esplica nel modo seguente:

Hx ≡ H(w+ v) = Hw+Hv = w− v (46)

Le matrici di Householder sono pertanto degli specchi che riflettono sottospazilineari di dimensione d attorno ai loro complementi ortogonali: solo cosı possonoessere simultaneamente autoaggiunte (autovalori reali, per autovettori riflessi(−1) o lasciati inalterati (+1)) e unitarie (conservazione di distanze e angoli).E solo cosı la loro successiva applicazione per un numero pari di volte lasciaqualsiasi vettore nel suo stato iniziale (H2k = I).Le matrici di Householder hanno determinante pari a +1 se d e pari (e sonoquindi delle rotazioni se d < n) e −1 se d e dispari (e sono quindi riflessioni ∀d ≤n). In ogni caso, qualora sia d = n, una matrice di Householder degenererebbe in

−I, essendo evidente, in tal caso, che nella definizione (41) l’espressione u(r)k u

(r)l

degenererebbe in δkl.

2.3.2 esempi di matrici di Householder

Nel piano reale bidimensionale la matrice con elementi reali

H =

(

cos(α) sin(α)sin(α) − cos(α)

)

(47)

13

e una matrice di Householder: e facile verificare che gode di TUTTE le proprietaenunciate. Il sottospazio dell’autovalore −1 e generato dall’unico autoversore(reale)

u =(

sin(α

2

)

,− cos(α

2

))

(48)

e il suo complemento ortogonale e ovviamente generato dall’autoversore dell’au-tovalore +1:

w =(

cos(α

2

)

, sin(α

2

))

(49)

L’espressione di u consente di riscrivere H, in accordo con la definizione (41),come

H =

1− 2(

sin(

α2

))22 sin

(

α2

)

cos(

α2

)

2 sin(

α2

)

cos(

α2

)

1− 2(

cos(

α2

))2

(50)

E immediato constatare la perfetta identita delle due espressioni di H.

Nello spazio quadridimensionale complesso, dati i tre vettori u, v e w seguenti:

u =1√3(1, i, 1, 0) v =

1√2(1, 0,−1, 0) w = (0, 0, 0, 1) (51)

e immediato convincersi che si tratta di versori a due a due tra loro ortogonali;pertanto, applicando la definizione (41), la seguente, in cui si omette il con-tributo delle componenti nulle per salvaguardia dello spazio, e una matrice diHouseholder:

H =

1− 2|u1|2 − 2|v1|2 −2u1u2 −2u1u3 − 2v1v3 0

−2u2u1 1− 2|u2|2 −2u2u3 0

−2u3u1 − 2v3v1 −2u3u2 1− 2|u3|2 − 2|v3|2 0

0 0 0 1− 2|w4|2

≡

≡

− 23

23 i

13 0

− 23 i

13 − 2

3 i 0

13

23 i − 2

3 0

0 0 0 −1

(52)

14

Si lascia come esercizio per chi legge la verifica che effettivamente si tratti diuna matrice autoaggiunta unitaria.

2.3.3 utilita delle matrici di Householder

La piu palese e che consentono di eseguire trasformazioni di similitudine attra-verso SOLTANTO loro stesse: in altri termini due matrici A′ e A che sianolegate dalla relazione

A′ = HAH, (53)

con H di Householder, sono senz’altro simili e anzi vale anche la relazionereciproca

A = HA′H (54)

con la STESSA H.Ma le matrici di Householder hanno anche un’altra capacita interessante: quelladi poter trasformare facilmente qualsiasi vettore non nullo che abbia una com-ponente reale in una certa direzione in un altro che abbia una sola componentenon nulla in quella stessa direzione; quest’unica componente non nulla residua,a questo punto, puo solo coincidere, a meno del segno, con la lunghezza del vet-tore originale (le matrici di Householder sono UNITARIE e quindi non possonocambiare la lunghezza dei vettori su cui agiscono). In altre parole le matricidi Householder possono trasformare qualsiasi vettore non nullo in uno di parilunghezza che sia multiplo scalare di uno dei versori della base canonica, lungoil quale il vettore originale avesse una componente reale.Per dimostrarlo basta considerare un vettore qualsiasi, x, che, per ipotesi, nonsia nullo, ossia tale che |x| 6= 0, e neppure gia diretto esattamente lungo uno deiversori canonici; e la matrice di Householder H costruita, nello spazio ambientein cui si trova x, secondo la definizione (41), usando il seguente UNICO versoreu(l):

u(l) =x− |x|el|x− |x|el|

(55)

ove el e uno dei versori canonici lungo cui, per ulteriore ipotesi, x ha unacomponente reale xl; tutto cio garantisce che u(l) e, a sua volta, un versore bendefinito. Allora si puo verificare senza eccessiva fatica che vale:

x′ ≡ Hx = |x|el (56)

ossia esattamente quanto si era anticipato. In effetti, essendo evidentementex = xmem, la componente generica k di x′ e data da:

x′k ≡ (H)kmxm ≡[

δkm − 2u(l)k u

(l)m

]

xm = xk − 2u(l)k u

(l)m xm (57)

Chiamando, per brevita, z il denominatore non nullo di (55), l’esecuzione dellasomma sull’indice m conduce a:

x′k ≡ xk −2

zu(l)k (|x|2 − |x|xl) (58)

15

Tenuto ancora conto di (55) si ha:

x′k = xk −2

z2(xk − |x|δkl)(|x|2 − |x|xl) (59)

Ora, per la definizione stessa di z, e facile constatare che, essendo

z2 ≡ (x− |x|el) · (x− |x|el) = x · x− |x|x · el − |x|el · x+ |x|2el · el (60)

si ha, identicamente,z2 = 2(|x|2 − |x|xl) (61)

per cui, in definitiva,x′k = |x|δkl (62)

che e l’asserto.

Con ragionamenti e procedure perfettamente equivalenti si puo anche trasfor-mare x in un vettore che abbia un certo numero maggiore di 1 di componentinon nulle: ad esempio, e senza perdita di generalita, per ottenere un vettoretrasformato x′ che avesse le ultime d < n componenti nulle e le restanti n − dnon nulle (reali), si potrebbe costruire una matrice di Householder tramite ilversore u ≡ v/|v| con il vettore v scelto come segue:

v ≡ (0, 0, 0, . . . , 0, xn−d − |(x · u)u|, xn−d+1, . . . , xn−2, xn−1, xn) (63)

Non vi sara chi non si avveda che il versore u scelto in tal guisa coincide conquello di cui si e parlato finora nel caso in cui, appunto, sia d = n − 1: na-turalmente qui, per chi non lo avesse intuito per proprio conto, con |(x · u)u|s’intende il modulo della proiezione di x sul sottospazio (n − d)–dimensionalegenerato da u, ossia dagli n − d versori canonici di cui u e una combinazionelineare.

2.3.4 Riduzione di una matrice alla forma triangolare o alla forma

di Hessenberg

La conclusione del precedente paragrafo ci dice che e senz’altro possibile ottenereuna matrice in forma di Hessenberg moltiplicando da sinistra una matrice qual-siasi per un certo numero di matrici di Householder e che cio puo essere portatoa compimento senza uscire dal campo numerico cui appartengono gli elementidella matrice assegnata: ossia e possibile ottenere una matrice di Hessenberg dauna matrice reale moltiplicandola per matrici di Householder anch’esse reali.

Sia data, ad esempio, la matrice A, con elementi reali:

A =

2 1 1−1 2 11 1 2

(64)

16

Questa matrice non ha particolari virtu di simmetria, e tuttavia possiede treautovalori reali e distinti, pari a 1, 2, e 3, come e facile verificare con un calcolodiretto.Sia ora u(1) il versore reale costruito a partire dal vettore a(1) = (2,−1, 1), cheoccupa la prima colonna di A, nel modo seguente (cfr. (55)):

u(1) =

a(1) − |a(1)|e1|a(1) − |a(1)|e1|

(65)

ove, ovviamente, e1 = (1, 0, 0) e il primo versore canonico; esplicitamente si ha,dopo semplicissimi calcoli:

u(1)1 =

2−√6

2√

3−√6≃ −0.30290544652768623275

u(1)2 = − 1

2√

3−√6≃ −0.67388733867904916157

u(1)3 =

1

2√

3−√6≃ 0.67388733867904916157

(66)

La matrice reale di Householder, H1, costruita tramite questo versore in accordocon la (41) e:

H1 =

√63 −

√66

√66

−√66

3−√6

63+

√6

6

√66

3+√6

63−

√6

6

=

0.81649658092772603273 −0.40824829046386301637 0.40824829046386301637

−0.40824829046386301637 0.09175170953613698363 0.90824829046386301637

0.40824829046386301637 0.90824829046386301637 0.09175170953613698363

(67)

La matrice T1 ≡ H1A dovra avere, in base alle conclusioni della sezione pre-cedente, la prima colonna con il secondo e il terzo elemento entrambi nulli; in

17

effetti, eseguendo il prodotto:

T1 ≡ H1A =

√6

√66

√62

0 32 −

√63

32

0 32 +

√63

32

=

2.4494897427831780982 0.40824829046386301637 1.2247448713915890491

0 0.68350341907227396727 1.5

0 2.31649658092772603273 1.5

.

(68)

Si introduce ora un secondo versore u(2) col quale sara costruita, sempre allostesso modo, una seconda e ultima matrice di Householder H2: tale versore siottiene partendo dalla seconda colonna di T1 o, meglio, dai due ultimi elementidi tale colonna; u(2) sara pertanto definito come

u(2) ≡ (0, r, s) (69)

con r2 + s2 = 1 e (r, s) coerentemente definiti da:

r =

32 −

√63 −

√

356

√

353 − 3

√

356 + 2

√353

= 0.59874982191366363486

s =32 +

√63

√

353 − 3

√

356 + 2

√353

= 0.80093610903639254171

(70)

La matrice di Householder H2, al termine di calcoli noiosi, ma semplici, ha ilseguente aspetto:

H2 =

1 0 0

0 xz

yz

0 yz−xz

(71)

in cui si apprezza visivamente la simmetria e si deduce l’ortogonalita sotto lasola condizione che valga x2 + y2 ≡ z2. In effetti, portando a compimento

18

TUTTI i calcoli, le grandezze che compaiono in H2 hanno i seguenti valori:

z =35

3+

2

3

√35− 3

√

35

6= 8.36503148230502474152

x = 2√6− 2

3

√35 + 3

√

35

6− 35

6= 2.36728133659466478821

y = 3

√

35

6+

2

3

√35− 19

6= 8.02307489516112998191

(72)

per cui, in definitiva,

H2 =

1 0 00 0.28299730151671216501 0.959120705299525427020 0.95912070529952542702 −0.28299730151671216501

(73)

Eseguendo ora il prodotto T2 ≡ H2T1 si perviene a una matrice triangolaresuperiore cosı fatta:

T2 ≡ H2T1 =

√6

√66

√62

0√35 (2+

√35)

√6−9

6√35−9

√6+12

54√35−81

√6+108

70√6−18

√35+4

√6√35

0 0 6√35

=

2.4494897427831780982 0.40824829046386301637 1.22474487139158904910 2.41522945769823976229 1.863177010224356388050 0 1.01418510567421989301

(74)

Ora, eseguendo il prodotto T2H1H2, si perviene a una matrice A′ che, per costruzione,e simile ad A. Risulta:

A′ ≡ T2H1H2 ≡ H2H1AH1H2 =

=

2.333333333333333333 1.464934041529428734 −0.2760262237369416871−0.2253744679276044207 2.809523809523809524 1.1664236870396086180.4140393356054125306 0.3499271061118825854 0.8571428571428571428

(75)

Ognuno riconoscera che A′ ha tutti gli elementi sub–diagonali di valore assolu-

to nettamente inferiore rispetto a quello degli omologhi elementi di A. Sorgedunque spontaneamente l’intuizione induttiva secondo cui, ripetendo l’identi-co procedimento su A

′, si possa pervenire a un’ulteriore matrice simile A′′ con

elementi sub–diagonali ancora piu vicini a zero e via seguitando...

19

In effetti, iterando il procedimento indicato per sole 25 volte (provare percredere), la matrice simile finale che si ottiene e:

A(25) =

2.00000003366811 1.41421355747812 −0.81649657565968−0.00000001190535 3.00000000692254 1.154700506951790.00000002061850 −0.00000001198713 0.99999995940935

(76)Non c’e Fisico degno di questo nome che non dica che questa matrice e trian-golare superiore entro un errore relativo non maggiore di 10−6 ≃ 10−7 e quindi,entro lo stesso errore, i suoi autovalori (ossia quelli di A, entro lo stesso errore)sono 2± i0, 3± i0, e 1± i0.Il metodo usato, pero, a questo punto satura, ossia non consente ulteriori raf-finamenti della valutazione degli autovalori; la ragione e piuttosto chiara: se sivolesse proseguire, avendo come matrice di partenza A

(25), le matrici di Hou-seholder che dovrebbero essere costruite a partire dalle sue colonne, essendoper natura quadratiche nelle componenti dei versori u, finiscono con l’essere“numericamente indistinguibili” dalla matrice identita e quindi ogni ulterioretrasformazione di similarita eseguita con esse riuscirebbe piu vana dei tentativiche potrei fare io per invitare a cena Angelina Jolie. Nella maggior parte deicasi della vita quotidiana la stima degli autovalori che si e ottenuta e largamenteadeguata; se la si volesse raffinare ulteriormente si possono utilizzare metodi diNewton o di bisezione che usino tali stime come valore iniziale: a quel puntonon e difficile raggiungere precisioni molto maggiori. Oppure si puo far dare unultimo colpo di coda al metodo usato in questa sezione applicandolo NON adA(25), che e inutile, ma alla sua trasposta, che ha pur sempre gli stessi autovalori,

essendo una matrice reale. Se lo si fa si perviene a (provare per credere)

A(25)′ =

3.00000006519583 −1.41421351627268 0.000000065195830.00000004610041 1.99999993480417 −1.41421356237309−0.00000000000000 0.00000000000000 1.00000000000000

(77)Le stime degli autovalori 2 e 3 non sono migliorate (anzi, e accaduto il contra-rio, anche se non tragicamente); tuttavia si e notevolmente rimpicciolito il primocerchio di Gerschgoring, e questo e grasso che cola per ogni ulteriore metododi raffinamento. In compenso la stima dell’autovalore 1 e, di fatto, diventatauna certezza, entro il rumore di macchina, e cio consente, per esempio, di ri-durre anche la dimensionalita dello spazio ambiente in cui raffinare gli altri dueautovalori.

2.3.5 ...e se gli autovalori non sono reali?

La matrice della sezione precedente si e lasciata facilmente addomesticare, senzauscire dal campo reale, solo perche era dotata di autovalori reali (e si era dettofin dall’inizio); in generale non ci si puo aspettare che il metodo proposto rie-sca per qualsiasi matrice, semplicemente perche un’eventuale matrice reale concoppie di autovalori complessi coniugati non puo ammettere l’esistenza di unamatrice simile a se e che sia reale e triangolare. Per persuadersi della veridicita

20

dell’ultima affermazione, che ha comunque in se una logica inattaccabile, ba-stera provare ad applicare il metodo della sezione precedente alla piu semplicematrice reale dotata di autovalori complessi coniugati che esista al mondo: lamatrice di rotazione 2× 2 di un angolo α, ossia

R =

(

cos(α) − sin(α)sin(α) cos(α)

)

(78)

che e risaputo possieda la coppia di autovalori complessi coniugati di modulo 1:exp(±iα).Il metodo della sezione precedente richiederebbe la costruzione di UNA SOLAmatrice reale di Householder, H, generata dal versore reale (65). Sostituendoivi i contenuti dovuti di R tale versore risulta essere, nel caso presente,

u = ((cos(α)− 1), sin(α)) /√

(cos(α)− 1)2 + (sin(α))2 (79)

E con ovvia evidenza esclusa la situazione cos(α) = 1 (R si ridurrebbe all’iden-tita), sicche u e ben definito nel piano reale e si puo riscrivere, utilizzando bennote identita trigonometriche, come

u =(

− sin(α

2

)

, cos(α

2

))

(80)

Da tale versore si origina una matrice di Householder che si era gia incontratacome esempio e che qui si riproduce per comodita:

H =

(

cos(α) sin(α)sin(α) − cos(α)

)

(81)

Senza nemmeno eseguire la trasformazione di similitudine HRH si capisce che lacosa non puo andare a buon fine, anche solo basandosi sui significati geometricidi R e H; ma se i lettori sono obnubilati ecco eseguita la trasformazione:

R′ = HRH =

(

cos(α) sin(α)− sin(α) cos(α)

)

(82)

E pur vero che la matrice R′ e simile a R, come doveva, ma per il piu banale

motivo dell’Universo: ne e semplicemente la trasposta; un’eventuale iterazionedel processo generera quindi novamente R tramite il versore generatore

u =(

− sin(α

2

)

,− cos(α

2

))

(83)

che produce la matrice di Householder

H =

(

cos(α) − sin(α)− sin(α) − cos(α)

)

(84)

e cosı via all’infinito, senza mai poter raggiungere una forma triangolare reale.

21

Aver toccato con mano, almeno una volta nella vita, il problema posto dagliautovalori complessi alle matrici reali conduce a comprendere come mai, nelcaso generale, si preferisca non partire in tromba con l’intento di rendere trian-golare qualsiasi matrice, ma accontentarsi piuttosto di portarla solo in forma diHessenberg, cosı da concedere asilo politico agli eventuali autovalori complessinegli elementi non nulli sub–diagonali. Questo sı che e effettivamente semprepossibile senza uscire dal campo numerico della matrice; e infatti la matrice R,per il solo fatto di essere 2×2, e gia in forma di Hessenberg (cfr. definizione). Lastrategia generale sara dunque definitivamente esposta nella sezione successiva.

3 Strategie di calcolo

Facendo tesoro di quanto esposto fin qui ecco come procedere per affrontare erisolvere nel migliore dei modi il problema della ricerca degli autovalori di unamatrice: ci sara una prima sottosezione per le matrici reali e una seconda perquelle complesse.

3.1 matrici reali

3.1.1 matrici reali simmetriche

In questo caso si sa che anche gli autovalori devono essere reali e pertanto si puotentare di trovarli senza mai uscire da tale campo numerico. Ad esempio si puoapplicare il metodo iterativo descritto nella sezione 2.3.4; la cosa riuscira, piuo meno brillantemente secondo la natura dello spettro da trovare: in presenzadi autovalori multipli si otterranno stime assai peggiori rispetto a quelle che sipotrebbero avere per spettri completi di autovalori distinti. Anche il rango dellematrici svolge un ruolo importante: e piuttosto evidente che le stime ottenutesaranno tanto peggiori quanto maggiore sara il rango delle matrici cui il metodosi applichi, sia per la propagazione di errori dovuta al gran numero di operazionisia perche, aumentando evidentemente anche il tempo necessario al calcolo, sifinira fatalmente per accontentarsi di stime meno raffinate di quelle che puresarebbero state accessibili aspettando piu a lungo la fine dell’algoritmo.

Va osservato che tra le matrici reali simmetriche vanno annoverate pure le ma-trici reali di Householder stesse: il fatto di conoscerne aprioristicamente i duesoli autovalori reali possibili salva gli sprovveduti programmatori dalla tentazio-ne di farne oggetto di indagine da parte dello stesso algoritmo che le usa comestrumento di ricerca, finendo nella clamorosa “impasse” di innescare un metodoiterativo il cui primo passo reciterebbe, ad esempio nel piano bidimensionale(cfr. (82))

H′ = HHH ≡ H3 ≡ H (85)

In alternativa si puo applicare un altro metodo iterativo basato sulla ricerca dimatrici simili ricavate per applicazione di matrici di Givens reali Grs con r es scelti in tutti i modi possibili lungo la diagonale, ossia sfruttando TUTTE

22

le possibili matrici di Givens a ogni iterazione: ognuna di tali matrici avra unangolo di rotazione α scelto in modo tale da annullare simultaneamente i dueelementi uguali che occupano le posizioni simmetriche rs e sr. Il pregio di que-sto metodo consiste nel fatto che la matrice prodotto ordinato di tutte le matricidi Givens utilizzate finisce per contenere nelle proprie colonne ANCHE gli auto-vettori della matrice di partenza, essendo quest’ultima, alla fin fine, ridotta adessere simile a una matrice diagonale (cfr. (37)). Anche questo tipo di approcciorisente comunque dei problemi legati alla presenza di eventuali autovalori realimultipli, pertanto in tutti i casi in cui fosse INDISPENSABILE una stima ac-curata degli autovalori non si potra prescindere dall’uso di appropriate tecnichedi raffinamento.

3.1.2 matrici reali qualsiasi

Viene meno la presunzione certa dell’appartenenza degli autovalori all’insiemedei numeri reali; pertanto ci si limita, in una prima fase in cui NON si abbandonail campo reale, a portare la matrice data in una forma di Hessenberg che siaSIMILE all’originale. Cio si ottiene con lo STESSO metodo iterativo citato nellasezione precedente e basato su matrici di Householder reali, ma rinunciando adazzerare interamente la parte sub–diagonale (o sovra–diagonale) della matricedata. Una volta conseguito questo risultato si dovra forzatamente uscire dalcampo reale e applicare, a una matrice gia molto piu “mansueta” dell’originale,le tecniche che saranno discusse nella sezione dedicata alle matrici complesse.

Per esempio la matrice reale 4× 4 senza virtu notevoli

A =

−1 2 3 41 2 3 4−2 −1 0 11 1 0 1

(86)

si lascia portare, al termine di SOLE TRE iterazioni del metodo ampiamente de-scritto (provare per credere) nella seguente forma simile (verificare per credere)di Hessenberg

A′ =

−1.00000000000000 0.00000000000000 4.38178046004133 3.13049516849971

2.44948974278318 0.33333333333333 1.19256958799989 2.37346441585572

0.00000000000000 0.74535599249993 0.26666666666667 −0.08164965809277

0.00000000000000 0.00000000000000 4.40908153700972 2.40000000000000

(87)entro un errore confrontabile col rumore di macchina, mentre, se si fosse pretesodi ottenere la forma triangolare, dopo ben 1000 (MILLE) iterazioni, interrotte

23

per disperazione, si sarebbe pervenuti alla seguente matrice simile

A′′ =

3.71464761599133 −6.15631443376881 2.20537301204227 −0.66926765114038

−0.00000003343713 −0.50118745612283 2.27496156225413 1.69011319793957

−0.00000001530975 −1.52639562112639 −0.32482241638460 −0.69383322145366

−0.00000000000000 −0.00000000743828 0.00000000274753 −0.88863774348397

(88)che e sı in forma di Hessenberg (di peggior qualita), ma di certo non triangolare,chiaro indizio che la matrice di partenza possiede almeno una coppia di auto-valori complessi coniugati. Quella che si e ottenuta, in effetti, e la cosiddetta“forma di Schur” triangolare a blocchi, ossia una matrice che sarebbe triango-lare se non fosse per la presenza di qualche elemento sub–diagonale non nullo:una via di mezzo fra una triangolare vera e una Hessenberg vera. Nel caso pre-sente havvi UN SOLO elemento non nullo (entro gli errori) sotto la diagonale:l’elemento a32 = −1.52639562112639. Pertanto si potrebbe gia concludere chela matrice A ha due autovalori reali distinti: 3.7146476, situato in posizionea11, e −0.88863774, situato in posizione a44; inoltre una coppia di autovaloricomplessi coniugati che sono quelli della sotto–matrice principale 2× 2:

A2×2 =

(

−0.50118745612283 2.27496156225413−1.52639562112639 −0.32482241638460

)

(89)

e che anche un alunno di scuola media trova essere, entro gli stessi errori,

λ± = −0.4130049± i 1.8613745 (90)

3.2 matrici complesse

3.2.1 matrici autoaggiunte

Non si dovrebbe far altro che ripetere quanto detto per le matrici reali simme-triche, con la sola variante che, in questo caso, si deve lavorare con l’algebracomplessa e con matrici di Householder con elementi a loro volta complessi.

3.2.2 matrici complesse qualsiasi

Senza dimenticare che a questa categoria di matrici appartengono ANCHE quel-le reali, si potrebbe ripetere lo stesso discorso fatto qui sopra per le matrici au-toaggiunte; una strategia alternativa contempla una prima riduzione in formasimile di Hessenberg tramite matrici complesse di Householder, la qual cosa,come si e visto, riesce sempre (o quasi) in modo lusinghiero.

Una volta ottenuta la matrice simile di Hessenberg, questa, se la dimensionedello spazio ambiente e n, possiede esattamente n−1 elementi sub–diagonali nonnulli: non resta quindi che applicare iterativamente n−1 ulteriori trasformazionidi similarita, non una di piu non una di meno, con matrici di Givens Gk+1,k, k =1, 2, . . . , n−1, ciascuna delle quali azzerera l’elemento sub–diagonale in posizione

24

k+1, k. Le iterazioni convergeranno, salvo casi patologici, a una matrice similetriangolare.

Per essere certi che una matrice di Givens riesca ad azzerare per similitudineun elemento sub–diagonale, sara sufficiente darne una dimostrazione costruttivanel caso n = 2, per cui TUTTE le matrici sono in forma di Hessenberg senzanemmeno toccarle e di matrici di Givens ne occorre e ne basta UNA SOLA:G2,1 ≡ G, ove si sono eliminati gli indici superflui. Tale matrice e, per definizione,unitaria; pertanto l’affermazione che si vuol provare e che:

e SEMPRE possibile trovare una matrice unitaria G tale che, nella trasforma-zione di similarita

A′ = G†AG (91)

l’elemento (A′)21 della matrice trasformata sia NULLO.

Come si e detto verra data una dimostrazione costruttiva di questo asserto e,per questo, assumeremo senz’altro che

• la matrice originale NON sia gia triangolare, ossia che tanto l’elemento(A)21 quanto l’elemento (A)12 siano entrambi NON nulli (ipotesi 1);

• La matrice G sia la piu generale matrice unitaria 2× 2 che possa esistere(ipotesi 2).

In base alla seconda ipotesi e abbastanza immediato scrivere G e contare daquanti parametri dipende; dovendo avere elementi complessi si preferira espri-merli con modulo e fase e pertanto, tenuto conto delle condizioni di unitarieta,uno solo dei quattro moduli resta libero, mentre per quanto attiene alle fasi neresteranno libere tre su quattro. In definitiva G, nella sua forma piu generalepossibile, ha il seguente aspetto:

G =

reiǫ −√1− r2ei(ψ−φ+ǫ)

√1− r2eiφ reiψ

(92)

con 0 ≤ r ≤ 1 e le fasi φ, ψ ed ǫ scelte arbitrariamente nell’intervallo ] − π, π].Qualsiasi matrice unitaria, complessa o reale, e valutabile come frutto di unaparticolare scelta dei quattro parametri reali presenti in (92): ad esempio conr = 1; ǫ = ψ = 0 si ottiene la matrice identita, qualunque sia φ; mentre laclassica matrice ortogonale di rotazione reale di un angolo α del primo quadrantesi ottiene con ǫ = ψ = φ = 0 e r = cos(α) con la matrice simmetrica reale diHouseholder ottenuta quando r = cos(α), ǫ = φ = 0 e ψ = π.

Scritta G si ha immediatamente la sua aggiunta (e inversa) G†:

G† =

re−iǫ√1− r2e−iφ

−√1− r2e−i(ψ−φ+ǫ) re−iψ

(93)

25

Si lascia a chi legge la verifica che effettivamente G†G = GG† = I.

Per conseguire il fine che ci siamo preposti e sufficiente calcolare l’espressionegenerale di (A′)21 in (91) e vedere se e possibile spendere qualcuna delle quattromonete che ci ha lasciato Mangiafuoco (r, φ, ψ, ǫ) per acquistare, fra le tantepossibili, almeno una matrice G che ce lo annulli. Al termine di calcoli tantonoiosi quanto semplici risulta (rifarli per credere):

(A′)21 =− a11r√

1− r2e−i(ψ−φ) + a21r2ei(ǫ−ψ)

− a12(1− r2)e−i(ψ−2φ+ǫ) + a22r√

1− r2ei(φ−ψ)(94)

in cui fanno bella mostra di se tutti e quattro gli elementi di A. Per averesperanza che questa espressione possa annullarsi identicamente sara opportunointrodurre qualche semplificazione che non ne comprometta la validita: tantoper cominciare, per l’ipotesi 1, entrambi i termini

a21r2ei(ǫ−ψ)

a12(1− r2)e−i(ψ−2φ+ǫ)

(95)

devono essere non nulli, perche e evidentemente da escludere che r possa assu-mere uno dei suoi due valori estremi (0 o 1), altrimenti la stessa ipotesi sarebbeflagrantemente contraddetta. E pertanto lecito dividere l’equazione (A′)21 = 0per uno qualsiasi dei due termini citati (scegliamo di dividerla per il secondo, mala scelta e totalmente irrilevante) trovando la seguente equazione equivalente:

0 =− a11a12

r√1− r2

ei(ǫ−φ)

+a21a12

r2

1− r2 e2i(ǫ−φ)

− 1 +a22a12

r√1− r2

ei(ǫ−φ) (96)

La prima bella notizia e che la moneta ψ e destinata a rimanerci in saccoccia,il che significa che esisteranno almeno ∞1 matrici unitarie idonee alla nostrabisogna; l’ultima equazione, riscritta piu ordinatamente, diventa:

a21a12

r2

1− r2 e2i(ǫ−φ)

+

(

a22 − a11a12

)

r√1− r2

ei(ǫ−φ) − 1 = 0

(97)

Chi non riconosce in quest’ultima un’equazione di secondo grado a coefficienticomplessi nell’incognita complessa z = r√

1−r2 ei(ǫ−φ)? Per chi fosse talmen-

te orbo ecco ricopiata l’equazione, tenuto conto della definizione di z appena

26

fornita:a21a12

z2 +

(

a22 − a11a12

)

z − 1 = 0 (98)

Si tratta di un’equazione di secondo grado VERA, nel senso che, per l’ipotesi 1,il coefficiente del termine quadratico e certamente non nullo, tanto che la sipotrebbe riscrivere anche in forma monica:

z2 +

(

a22 − a11a21

)

z − a12a21

= 0 (99)

e anche se si fosse diviso per l’altro termine in (95) nulla sarebbe cambiato, senon la definizione di z, che avrebbe avuto come modulo il reciproco di quelloattuale, e i coefficienti dell’equazione. C’e un’altra buona notizia, ossia un’altramoneta risparmiata: per soddisfare l’equazione conta soltanto la differenza tra lefasi ǫ e φ, NON il valore di ciascuna di esse. A questo punto non occorre altro cheinvocare il teorema fondamentale dell’algebra il quale ci assicura che l’equazionecui siamo pervenuti ammette senz’altro addirittura due soluzioni complesse, z1 ez2, NON necessariamente tra loro coniugate ed entrambe NON NULLE: ognunadi esse, con la propria fase, che risulta quindi perfettamente definita, ci fornisceun valore per la differenza ǫ − φ e col proprio modulo ci fissa il valore da darea r (tale modulo e essenzialmente la tangente o la cotangente trigonometricadi un determinato angolo del primo quadrante). Sara poi compito del buonprogrammatore scegliere e utilizzare una delle due, secondo opportunita: adesempio scegliere la “piu reale” oppure la “piu lontana/vicina” all’origine (omagari l’uno e l’altro).

In definitiva la matrice di Givens che triangolarizza A, effettuando le scelte

semplificative (e libere!) ψ = φ = 0, ǫ = arg(z∗), r = |z∗|√1+|z∗|2

, in cui si e

indicata con z∗ l’opportuna soluzione dell’equazione quadratica trovata, risultaessere

G =1

√

1 + |z∗|2

z∗ −ei arg(z∗)

1 |z∗|

(100)

ove trova conferma il fatto che r non sia ne zero ne uno (z∗ e finito e non nullo)con G†, di conseguenza:

G† = 1√

1 + |z∗|2

z∗ 1

−e−i arg(z∗) |z∗|

(101)

3.3 casi “patologici”

Ci sono matrici talmente “perfide” che non si lasciano persuadere a rendere notii propri autovalori coi metodi iterativi discussi in questo testo; fortunatamentenon sono tante e sovente sono tali da permettere il calcolo degli autovalori “a

27

mano”. Prendiamo per esempio la seguente matrice reale 3× 3:

S =

0 0 11 0 00 1 0

(102)

Che cosa c’e di piu (apparentemente) innocente? Si tratta di una matrice giain forma di Hessenberg superiore e per giunta ortogonale di dimensione disparie con determinante pari a +1; cio basta a dire che uno dei suoi autovalorie senz’altro reale e pari a 1 e gli altri due saranno una coppia di complessiconiugati di modulo 1 facilmente calcolabile: si tratta delle altre due radicicubiche complesse di 1

−1

2± i√3

2(103)

Il problema e dunque felicemente risolto “a mano”, ma se si prova a dare in pastoS all’algoritmo iterativo che dovrebbe tendere a triangolarizzare una matrice diHessenberg ci si dovra accorgere che quel che si ottiene e una successione dimatrici simili, periodica di periodo 3, tale che, allo scadere di ogni periodo, Ssi ripresenta intonsa. La morale e che, a volte, per un algoritmo iterativo lapresenza di “troppi zeri” finisca per essere piu dannosa che utile...Ora facciamo agire S nello spazio ambiente dei vettori con componenti com-plesse per determinare quali siano i suoi tre autoversori u(1), u+ e u−, il primoessendo quello corrispondente all’autovalore reale e gli altri due quelli corrispon-denti rispettivamente ai due autovalori complessi coniugati λ± gia calcolati. Informule:

Su(1) = u(1)

Su+ = λ+u+

Su− = λ−u−

(104)

Ma poiche S e ortogonale, e quindi la sua trasposta e la sua inversa, moltipli-cando ambo i membri delle precedenti equazioni per ST si trova

u(1) = STu(1)

u+ = λ+STu+

u− = λ−STu−

(105)

Dunque la terna degli u costituisce anche gli autoversori di ST , ma i due auto-versori corrispondenti agli autovalori complessi coniugati si scambiano tra loro

28

gli autovalori medesimi:

STu(1) = u(1)

STu+ = λ−u

+

STu− = λ+u

−

(106)

Determiniamo esplicitamente i due autoversori u+ e u−; non e difficile trovareche

u+ =1√3(1, λ−, λ+)

u− =1√3(1, λ+, λ−)

(107)

Se si volessero ora calcolare i prodotti scalari degli autoversori di S e ST che

corrispondano allo stesso autovalore si dovrebbero valutare u(1) · u(1), u+ · u−

e u− · u+. Il primo vale evidentemente 1 e gli altri due sono fra loro complessiconiugati; basta quindi valutarne uno solo. Se lo si fa, ecco il risultato:

u+ · u− ≡ 1

3

(

1 + λ−λ+ + λ+λ−)

(108)

ossia

u+ · u− =1

3

(

1 + 2Re(λ2±))

=1

3

(

1 + 2

(

−1

2

))

= 0 (109)

come si doveva intuire fin dall’inizio. Il risultato ottenuto, per quanto ovvio,spiega la “perfidia” di S nei confronti dell’algoritmo iterativo; in effetti ogniautovalore di qualsiasi matrice, appartenendo anche all’insieme degli autovaloridella matrice trasposta (ovvero, previa complessa coniugazione, a quello dellamatrice aggiunta) si dice tanto piu “ben condizionato” (significa, in soldi spicci,che si tratta di un bell’autovalore) quanto maggiore e il modulo del prodottoscalare dei due autoversori corrispondenti a quell’autovalore (o al suo coniuga-to) nei sottospazi invarianti delle due matrici in questione. Zero e dunque ilpessimo valore che si potrebbe ottenere per tale modulo, ed e proprio quelloche abbiamo appena ricavato per i due autovalori complessi coniugati di S. Si-gnifica che quei due autovalori non potrebbero essere “peggio condizionati” dicosı e questo comporta che siano estremamente instabili, dal punto di vista siaanalitico sia, a peggiore ragione, numerico, per qualsiasi pur minuscola pertur-bazione che venisse inflitta a S. Si osservi, come corollario di quanto appenafinito di enunciare, che le matrici autoaggiunte/simmetriche si trovano semprenella “miglior condizione possibile” dal punto di vista del buon condizionamentodei propri autovalori: tutti i prodotti scalari valgono 1.Un altro esempio palese di cattivo condizionamento di un autovalore e fornitodalla seguente matrice, addirittura 2 × 2, ossia la dove tutto parrebbe rose e

29

fiori, come in una ripristinata eta dell’oro:

N =

(

1 a0 1

)

(110)

Questa matrice e perfida per due ragioni: oltre all’eventuale cattivo condiziona-mento ha anche la patologia di un autovalore doppio pari a 1. La ricerca degliautovalori e finita prima ancora di cominciare, trattandosi di una matrice trian-golare, ma determiniamo l’autoversore corrispondente a quest’unico autovaloresia per N sia per NT

N u = u

NTv = v

(111)

Si trova immediatamente

u = (1, 0)

v = (0, 1)

(112)

e anche in questo caso si ha il peggior condizionamento possibile. Un ultimocaso di studio, stavolta con dipendenza del condizionamento da un parametro,e fornito dalla matrice reale, ancora 2× 2:

M =

(

0 a1 0

)

(113)

Gli autovalori sono λ± = ±√a e saranno reali o immaginari puri secondo ovvietaconcernenti il segno di a. Considerando l’autovalore λ+ (per l’altro autovaloresi fara esattamente la stessa cosa) determiniamo ancora una volta l’autoversorecorrispondente sia per M sia per MT :

M u =√a u

MTv =

√a v

(114)

in cui si e ammessa la possibilita che i due autoversori abbiano componenticomplesse. Si trova, senza troppa fatica,

u =1

√

1 + |a|(√a, 1)

v =1

√

1 + |a|(

1,√a)

(115)

30

e il modulo del prodotto scalare vale

|u · v| = 2|Re (√a) |1 + |a| (116)

Ora accade che |Re (√a) | valga semplicemente√a solo se a ≥ 0, altrimenti

vale zero qualunque sia a < 0. Ne segue che l’autovalore in questione ha ilcondizionamento peggiore possibile ∀a ≤ 0, mentre il condizionamento miglioraquando a > 0 raggiungendo il massimo valore possibile (1) quando a = 1 (Min quel caso e simmetrica!) tornando poi a decrescere fino a tendere a zero pera→ +∞.

4 Raffinamenti

Si e sovente accennato a questo argomento nel corso di questo testo, ogni voltache si e posto l’accento sull’eventualita che occorresse una stima degli autovalorimolto piu precisa rispetto a quella ottenibile con i metodi fin qui esposti, i quali,nel caso, sono da considerare idonei a fornire un valore iniziale da cui partireper il processo di raffinamento. Uno dei metodi piu efficaci, e che consente diraggiungere precisioni tali che gli errori residui siano confrontabili col rumore dimacchina e il metodo di bisezione, che puo essere messo in atto se si conoscono,con un ottimo grado di confidenza, i coefficienti del polinomio caratteristicodella matrice originale.

Si ricorda che il polinomio caratteristico P (λ) ha grado n ed e monico

P (λ) ≡ λn +

n∑

k=1

pkλn−k (117)

I coefficienti dei monomi di grado minore di n sono espressi dalla formula

pk = (−1)k∑

l

det[k×k]

(A)ll k = 1, 2, . . . , n (118)

dove con det[k×k](A)ll s’intende il determinante di un minore principale di rango

k e con∑

l s’intende che vadano sommati TUTTI i(n

k

)

minori principali di tale

rango. Ad esempio, p1 e sempre dato da p1 ≡ −Tr(A) mentre il termine noto pnvale pn ≡ (−1)n det(A). Come ulteriore e familiarissimo esempio, il polinomiocaratteristico di una matrice 2× 2 si materializza, partendo dalle (117) e (118),nella ben nota espressione quadratica

λ2 − λTr(A) + det(A) (119)

Essendo pertanto relativamente semplice calcolare il polinomio caratteristico diqualsiasi matrice (entro la doverosa ragionevolezza di non pretendere di far ten-dere n a infinito, ed essendo disposti ad aspettare con pazienza la fine del calcolo,

31

almeno per matrici relativamente piccole ...), e possibile innescare un metodo diraffinamento per bisezione che parta da una stima degli autovalori ottenuta coimetodi fin qui discussi. In alternativa all’uso di P (λ) si potrebbe consideraredirettamente la funzione, reale o complessa che sia, f(λ) ≡ det(A − λ), chereca in se, evidentemente, la stessa informazione senza la necessita di conoscereesplicitamente i coefficienti del polinomio caratteristico. I due tipi di approcciosono sostanzialmente equivalenti per matrici piccole; per matrici di media taglia(rango attorno a 8 ∼ 12) e preferibile usare il polinomio caratteristico, il cui va-lore si calcola piu velocemente rispetto a quello di un determinante. Al cresceredel rango, pero, la maggiore velocita di calcolo del polinomio viene ognor piufrustrata dal tempo necessario per calcolarne, sia pure una tantum, i coefficientie quindi diventa preferibile l’uso di f(λ), specialmente se si dispone di un buonalgoritmo per il calcolo di un determinante.

4.1 esempio concreto

Come esempio concreto di una tecnica di raffinamento riprenderemo la matricereale

A =

2 1 1−1 2 11 1 2

(120)

che si e gia utilizzata in una precedente sezione e per la quale erano state ottenutestime numeriche dei suoi autovalori esatti (1, 2 e 3) qui appresso riportate

λ1 = 0.99999995940935

λ2 = 2.00000003366811

λ3 = 3.00000000692254

(121)

Il polinomio caratteristico di A e, da (117) e (118):

λ3 − 6λ2 + 11λ− 6 (122)

e ci si puo divertire a constatare che effettivamente 1, 2 e 3 sono sue radici.Per raffinare, ad esempio, la stima λ1 si sceglie un numero d, che nel casopresente puo tranquillamente essere reale positivo, abbastanza piccolo (tale, adesempio, che λ1 ± d sia amplissimamente contenuto nel cerchio di Gerschgoringcon centro in λ1) ma tale che P (λ1−d) abbia segno opposto al segno di P (λ1+d):cio e senz’altro possibile, dato che P (λ) si annulla “nelle vicinanze” di λ1 (ameno che non ci si imbatta in una radice multipla: ecco perche gli autovaloricon multiplicita maggiore di 1 sono un’autentica rogna; ma questo e un altrodiscorso). Trovato un d cotale si prendono in considerazione i due semi–intervalli[λ1 − d, λ1] e [λ1, λ1 + d]; per UNO SOLO di essi continueranno a essere disegno discorde le due determinazioni di P (λ) agli estremi: siccome sappiamo inanticipo come debba andare a finire, possiamo affermare che sara il secondo deidue a godere di questa lodevole caratteristica. A questo punto si assume come

32

“nuova stima” dell’autovalore da trovare il punto mediano di quest’intervallo(λ1+

d2 ) e si itera il procedimento: in capo a pochissime iterazioni (la lunghezza

degli intervalli decresce esponenzialmente con un coefficiente di decrescita pari alog(2)) si giunge a un intervallo il cui punto mediano dista dagli estremi quantoappunto il rumore di macchina consente di discriminare, e sara quest’ultimopunto mediano il valore accettato come “esatto” per l’autovalore in questione.Applicando questa tecnica, un programma di 25 righe perviene, in 49 iterazioni,alla seguente stima di λ1:

λ1 = 1.00000000000000000 (123)

(non per nulla 2−49 = 0.00000000000000177636).

4.2 raffinamento di un autovalore non reale

Indipendentemente dal fatto che esista o no un “compare” coniugato, il raffi-namento di un autovalore che non giaccia sull’asse reale del piano complessopresenta delle evidenti complicanze perche occorre “raffinare” simultaneamentesia la parte reale sia quella immaginaria del polinomio caratteristico (questonon avverrebbe per una matrice autoaggiunta con elementi complessi che ha,comunque, un polinomio caratteristico con coefficienti reali); ma quel che piuconta e che ciascuna delle due e, a sua volta, funzione di DUE variabili reali,ossia la parte reale e quella immaginaria dell’autovalore complesso da trovare.Ne segue che l’intorno dell’autovalore da raffinare non sia un semplice intervallodella retta reale, ma piuttosto un quadrilatero del piano complesso i cui quattrovertici presentino, nell’ordine, tutte le quattro possibili combinazioni delle se-gnature di parte reale e immaginaria del polinomio, ossia (−−, −+, ++, +−),un po’ come accade nella circonferenza goniometrica per le segnature di seno ecoseno.

Gia il reperimento di un tale quadrilatero e significativamente piu complicatodi quanto non fosse la ricerca di d; vieppiu complicata ne e la successiva “bi-sezione” iterativa, perche si tratta di secare tutti e quattro i lati in modo taleche il nuovo quadrilatero (di area piu piccola) conservi le quattro segnature ca-ratteristiche nei suoi vertici, che sono null’altro che i punti di sezione dei latioriginari. Solo cosı si ha garanzia che l’autovalore cercato non se ne scappi fuoridal quadrilatero: tutti capiscono che non si potranno scegliere semplicemente ipunti mediani dei quattro lati, con la stessa noncuranza che potrebbe avere unbue in una serra di orchidee... Per carita, niente di impossibile, ma anche nientedi cosı banale; fortunatamente l’autore di queste note ha gia scritto da tempoimmemorabile un programma che affronta e risolve questo problema (talmenteimmemorabile che neppure ricordo esattamente quando) per cui, all’occorrenza,chiunque potra chiederlo e utilizzarlo senza doverlo riscrivere.

4.3 il caso degli autovalori multipli

Si e gia detto che si tratta di una rogna. Se le stime iniziali sugli autovaloridanno evidenza che ce ne siano di multipli, i metodi di raffinamento propo-

33

sti semplicemente NON FUNZIONANO, sicche sembra di essere condannati atenersi soltanto la stima iniziale (il che potrebbe anche essere sufficiente...).

Tuttavia la buona notizia e che una radice multipla del polinomio caratteristico,di multiplicita m > 1, e radice, di multiplicita m− k, anche di tutti i polinomiderivati k–esimi, fino al derivato (m − 1)–esimo; e per quest’ultimo polinomioderivato si tratta quindi di una radice di multiplicita 1. Dato che il calcolodei coefficienti di un polinomio derivato di un altro e una colossale banalita,in presenza di autovalori multipli si andranno quindi a utilizzare le tecniche diraffinamento indicate avendo come polinomio da azzerare NON quello caratte-ristico della matrice assegnata, ma il suo derivato di ordine opportuno, che, perricompensa delle pene affrontate, ha anche un grado minore: n−m+ 1.

5 “Interscambiabilita” tra polinomi e matrici

Che ogni matrice quadrata, reale o complessa, in uno spazio ambiente di dimen-sione n, abbia un proprio “polinomio caratteristico” di grado n, le cui radici so-no gli autovalori della matrice e stato ripetutamente detto e sfruttato in questenote.

Vale anche il viceversa:

Ogni polinomio di grado n in una variabile, reale o complessa, con coefficien-ti reali o complessi, ha una matrice quadrata, reale o complessa, nello spazioambiente n–dimensionale che ha per autovalori le sue radici.

L’affermazione, in se, non dovrebbe avere nulla di sorprendente visto tutto ilpregresso di queste note; anzi, si dovrebbe affermare senza timore che, in realta,di matrici cotali ne esistono qualche potenza di infinito... Cio che potrebbeinvece essere sorprendente e quanto sia semplice scrivere immediatamente unadi tali matrici e quanto sia accattivante il suo aspetto. Tanto per cominciaree del tutto evidente che qualsiasi polinomio di grado n ha le STESSE radicidel polinomio monico di pari grado ottenuto dividendo ogni coefficiente perquello del monomio di grado maggiore. Non ci sara quindi alcuna perdita disignificativita se si considereranno solo polinomi monici Q(z) (cfr. (117)):

Q(z) = zn +n∑

k=1

qkzn−k (124)

in cui sia alla variabile z sia ai coefficienti qk e consentito di appartenere aqualunque campo numerico.

34

Si consideri ora la seguente matrice n× n, in forma di Hessenberg superiore:

C =

0 0 0 · · · 0 −qn1 0 0 · · · 0 −qn−1

0 1 0 · · · 0 −qn−2

0 0 1 · · · 0 −qn−3

......

... · · · 0 −q20 0 0 · · · 1 −q1

(125)

ossia una matrice TUTTA PIENA DI ZERI, eccetto l’ultima colonna, in cuitrovano posto, nell’ordine indicato, i coefficienti di Q(z) cambiati di segno, egli elementi sub–diagonali (quelli per cui e in forma di Hessenberg) che sonoTUTTI uguali a 1.

Non e difficile constatare che C ha proprio Q(λ) per polinomio caratteristico, equindi i suoi autovalori sono le radici di quello. Ad esempio la versione 2× 2 diC e, coerentemente:

C =(

0 −q21 −q1

)

(126)

e l’asserto e, in questo caso (ma anche in ogni altro), evidente. Pertanto, dallaconoscenza dei coefficienti del polinomio caratteristico si puo passare diretta-mente alla ricerca degli autovalori mettendosi a cercare quelli di una matricecome C, che e gia in una forma di Hessenberg molto, ma mooolto, addomesti-cata. Un corollario evidente di questa sezione consiste nella constatazione cheanche la ricerca degli zeri di un polinomio in una variabile equivale a quella degliautovalori di una matrice.

6 Se o quando TUTTO va male...

Qualora, nonostante l’accurata applicazione di tutto quanto fin qui esposto, enonostante il fatto che quasi tutte le matrici del mondo siano prone a rivelareai nostri codici i loro segreti piu nascosti, se ne incontrasse una particolarmentestr..., voglio dire, refrattaria..., c’e pur sempre ancora qualcosa da fare.

6.1 ...magari e una matrice “notevole”

Se fosse idempotente? Gli autovalori sarebbero noti senza colpo ferire, e peresplorare quest’eventualita basterebbe confrontarla col suo quadrato...

6.2 ...e farsi aiutare dalla grafica, no?

Non e per nulla difficile, ad esempio, disegnare i cerchi di Gerschgoring e poi ilgrafico del polinomio caratteristico (magari, eventualmente, sia della parte realesia di quella immaginaria) nella regione del piano complesso da essi occupata:questo consentirebbe di ricavare la posizione degli autovalori con una precisione

35

sufficiente a innescare un processo di raffinamento, oppure a scoprire la presenzadi autovalori multipli qualora il grafico presentasse delle tangenze con l’asse λ.

6.3 ...iterare, iterare, iterare...

Una cosa relativamente semplice da fare consiste nell’estrarre a sorte un vettorev0 6= 0 nello spazio ambiente e generare una successione di vettori vk conl’operazione

vk = Avk−1 k = 1, 2, · · · (127)

ove, ovviamente, A e la nostra “refrattaria”: poiche questa sua spregevole ca-ratteristica non puo comunque privarla del suo spettro e dei suoi autoversoriak, questi da qualche parte dovranno pur essere, il che significa che il vettoreestratto a sorte v0 e tacitamente una loro combinazione lineare, completamenteignota a tutti, tranne che ad A.

v0 ≡ c1a1 + c2a2 + · · ·+ cnan (128)

Qui neppure si pretende che ogni autovettore corrisponda a un diverso autova-lore, ma solo, ragionevolissimamente, che tutti insieme generino l’intero spazioambiente; dall’espressione di v0 segue immediatamente che, ∀k ≥ 0, il vettorevk sia esprimibile come

vk ≡ c1λk1a1 + c2λk2a2 + · · ·+ cnλ

knan (129)

con, ancora una volta, nessuna pretesa che tutti i λ siano distinti. Ce ne saratuttavia uno, o piu di uno in caso di coincidenza, che abbia, fra tutti, il massimomodulo: dopo tutto si tratta di un insieme finito. Osserviamo che la veridicitadi quest’ultima affermazione impone ad A di NON ESSERE un multiplo scalaredi una matrice unitaria: ma se questo fosse stato non dovremmo essere qui adannarci l’anima...Poniamoci a stimare il valore del seguente numero complesso (in meccanicaquantistica sarebbe il valor medio dell’operatore A nello stato quantico vk):

µk ≡vk · (Avk)vk · vk

(130)

I numeri complessi µk costituiscono essi stessi una successione di cui ci chiediamoora se esista, e quale sia, un limite. Tenuto conto di tutto, un’espressioneesplicita di µk e la seguente

µk ≡vk · vk+1

|vk|2=

(crλkrar)j(

cpλk+1p ap

)

j(

cfλkfaf

)

j

(

cgλkgag)

j

(131)

Sia ora λ∗ l’autovalore, di eventuale multiplicita s, che ha appunto il massimomodulo fra tutti gli autovalori: λ∗ e evidentemente non nullo, altrimenti sareb-bero nulli TUTTI gli autovalori e A sarebbe stata nihilpotente, rendendo nulli

36

gli stessi vettori vk da un certo k in poi. Evidenziando il contributo di λ∗ allecombinazioni lineari dei versori a potremo scrivere ogni vettore vk nel seguentemodo:

vk ≡ λ∗kb+∑

λp 6=λ∗

cpλkpap = λ∗k

b+∑

λp 6=λ∗

cpεkap

(132)

in cui si e denominata b la combinazione lineare di tutti i versori a corrispon-denti all’autovalore λ∗ e ci si e ricordati che λ∗ 6= 0 definendo i numeri com-plessi di modulo strettamente minore di 1 che costituiscono i rapporti degli altri

autovalori con λ∗: εp =λpλ∗

. Con questa convenzione µk assume la forma:

µk =

λ∗|λ∗k|2

b+∑

λr 6=λ∗

crεkrar

·

b+∑

λp 6=λ∗

cpεk+1p ap

|λ∗k|2

b+∑

λf 6=λ∗

cfεkfaf

·

b+∑

λg 6=λ∗

cgεkgag

(133)

in cui appare flagrante chelimk→∞

µk = λ∗ (134)

ossia che l’autovalore di A col modulo piu grande e stato scovato. La velocitadella convergenza al limite dipende ovviamente da quanto minore sia il modulodegli altri autovalori rispetto a quello di λ∗, ma e comunque certa, vista l’espres-sione analitica di µk. A quel punto si puo facilmente valutare la multiplicita diλ∗ andando a controllare se, e fino a quale ordine di derivazione, annulla anchei polinomi derivati del polinomio caratteristico di A. Trovata la multiplicita mdi λ∗ si effettuera la semplicissima divisione del polinomio caratteristico per ilpolinomio (λ − λ∗)m trovando i coefficienti di un polinomio monico di grado(n−m) che avra come radici i restanti autovalori di A e cui sara possibile asso-ciare una matrice di Hessenberg con (n−m) righe e colonne, come quella dellasezione 5 e i cui autovalori si spera siano piu facili da trovare...Questo metodo mostra evidentemente la corda, come si e gia piu volte accennato,per quelle matrici che possedessero autovalori distinti di modulo uguale; ancheuna matrice reale che avesse per autovalori reali, di qualsiasi multiplicita, adesempio 5, −5, 1, 2, e 3 non sarebbe adatta a questo procedimento perche unodegli ε varrebbe ±1 e le sue potenze k–esime non tenderebbero a zero al cresceredi k. Ma una matrice cotale appare essere invertibile, con autovalori reciproci diquelli originali; e per l’inversa 1 sarebbe l’autovalore di maggior modulo, senzache ce ne siano altri di modulo uguale... Talvolta occorre anche un po’ d’astuzia.Buona fortuna.

37