Il metodo QR per matrici semiseparabili: aspetti teorici e computazionali

(1)

Universit`

a degli studi di Pisa

Facolt`

a di Scienze Matematiche Fisiche e Naturali

Corso di Laurea in Matematica

tesi di laurea

Il metodo QR applicato a matrici

semiseparabili: aspetti teorici e

computazionali

Candidato

Manuela Bagnasco

Relatore

Controrelatore

Prof. Dario Andrea Bini

Prof. Luca Gemignani

(2)

(3)

Indice

Introduzione iii

1 Il concetto di semiseparabilit`a 1

1.1 Notazioni e definizioni . . . 1

1.2 Matrici semiseparabili . . . 3

1.2.1 Il teorema della nullit`a . . . 5

1.3 Inverse di matrici tridiagonali e matrici a banda . . . 6

1.4 Semiseparabilit`a per generatori . . . 9

1.5 Aspetti computazionali . . . 12 1.6 Semiseparabilit`a generalizzata . . . 18 1.7 Matrici di Green . . . 20 1.8 Rotazioni di Givens . . . 23 2 Il metodo QR 27 2.1 La fattorizzazione QR . . . 27 2.2 Metodo QR e semiseparabilit`a . . . 33

2.3 Il metodo QR applicato ad una struttura semiseparabile ge-neralizzata . . . 36

3 L’algoritmo 41 3.1 Riduzione in forma di Hessenberg superiore . . . 43

3.2 Riduzione in forma triangolare superiore . . . 57

3.3 Calcolo della nuova iterata . . . 75

4 Risultati numerici 93 4.1 Implementazione . . . 93

4.2 Risultati numerici . . . 98

4.2.1 Matrici diagonali pi`u rango uno . . . 99

4.2.2 Matrici a freccia . . . 102

4.2.3 Matrici diagonali pi`u semiseparabili hermitiane . . . . 106

(4)

Indice

4.3 Applicazione al calcolo di zeri di polinomi . . . 110

4.3.1 Polinomi di Laguerre . . . 111

4.3.2 Polinomi di Chebyshev . . . 113

4.3.3 Conclusioni . . . 114

A Listati dei programmi 117

(5)

Introduzione

In questa tesi vengono studiate le propriet`a strutturali e computazionali delle matrici semiseparabili e il loro utilizzo per il disegno di un nuovo algoritmo tipo QR di basso costo computazionale.

Il metodo QR per il calcolo degli autovalori di una matrice `e stato intro-dotto da Francis nel 1961 [14] come uno sviluppo del metodo di Rutishauser [18] del 1958.

Data una matrice n × n A, posto A1 = A, il metodo QR genera una

successione di matrici {Ak} nel modo seguente: per k = 1, 2, . . . si calcola la

fattorizzazione QR di Ak: Ak = QkRk, dove Qk `e una matrice unitaria e Rk

`e triangolare superiore, e la matrice Ak+1 `e definita dalla relazione Ak+1 =

RkQk. Sotto opportune ipotesi la successione {Ak} converge ad una matrice

triangolare superiore che ha per elementi principali gli autovalori di A [5]. Il metodo QR in generale si applica a matrici ridotte in forma di Hessenberg

superiore o tridiagonali ed ha ad ogni passo un costo computazionale di 2n2

operazioni moltiplicative nel primo caso, un costo computazionale di 12n operazioni nel secondo caso.

Si trovano in letteratura recenti studi sul metodo QR applicato a classi di matrici semiseparabili [7], [19], [6]. Una matrice è detta semiseparabile se ogni sottomatrice estratta dalla parte triangolare inferiore (e superiore) ha rango minore o uguale ad uno. I primi studi sulle matrici semiseparabili sono dovuti a Gantmacher e Krein intorno al 1930. L’interesse verso le matrici semiseparabili si è sviluppato per due motivi principali: innanzitutto perché tali matrici hanno ricche ed interessanti proprietà di struttura ed inoltre, poiché esse si incontrano in numerosi problemi applicativi di vari settori della matematica, della fisica, dell’ingegneria o della biologia [8], fra questi: problemi di statistica [16], problemi di analisi di equazioni integrali e di equazioni differenziali con condizioni al bordo [15].

Inizialmente lo studio delle matrici semiseparabili era principalmente mo-tivato dallo studio della struttura delle matrici inverse di matrici a banda. L’idea che sta alla base di questa analisi `e che l’inversa di una matrice a banda A, pur essendo in generale “piena”, `e definita dallo stesso numero di

(6)

parame-Introduzione

tri della matrice A che `e quindi inferiore ad n2_{. In [17] vengono studiate le}

relazioni tra matrici semiseparabili e matrici a banda in senso stretto, in [3] invece, vengono mostrate alcune relazioni tra l’annullarsi di alcuni minori di una matrice non singolare generale e l’annullarsi in corrispondenza di alcuni minori della matrice inversa. Successivamente il concetto di matrice semi-separabile `e stato generalizzato in varie forme in modo da includere matrici le cui sottomatrici estratte dalla parte triangolare superiore e dalla parte triangolare inferiore abbiano rango limitato superiormente da due costanti assegnate.

Fino agli anni ’80 l’interesse computazionale era rivolto alla risoluzione di problemi come il calcolo della fattorizzazione LU , la risoluzione di siste-mi lineari, il calcolo dell’inversa di tali matrici. Pi`u di recente l’interesse algoritmico si `e rivolto a matrici semiseparabili generalizzate e ai problemi del calcolo degli autovalori di matrici semiseparabili dove diversi gruppi di ricerca hanno dato contributi interessanti.

Una classe di matrici importanti appartenente alle matrici semiseparabili generalizzate è la classe delle matrici companion generalizzate, cioè matrici della forma D + ueT_{, dove D è una matrice diagonale, u è un vettore ed e è il}

vettore formato da tutti 1. Queste sono matrici il cui polinomio caratteristico `e facilmente calcolabile e viceversa, dati i coefficienti di un polinomio p(x) e gli elementi diagonali di D, `e facile costruire un vettore u tale che D +ueT _ha

per polinomio caratteristico p(x). Quindi l’analisi di algoritmi efficienti per il calcolo di autovalori `e di grande interesse perch´e prelude al calcolo degli zeri di polinomi.

In questa tesi si sono studiate le proprietà strutturali delle matrici semi-separabili cercando di mettere ordine alla disuniformità notazionale presente in letteratura [19], [4], [7], [9]. Le definizioni di matrici semiseparabili che si trovano possono essere ricondotte a due tipologie: la definizione di matrice semiseparabile come matrice avente una struttura particolare definibile in termini del rango [19] e la definizione di matrice semiseparabile come matri-ce le cui strutture triangolari superiore ed inferiore sono date dalla somma di diadi [4]. In questa tesi è stata adottata la prima definizione, si conside-ra quindi semisepaconside-rabile una matrice in cui ogni sottomatrice estconside-ratta dalla parte triangolare inferiore (superiore) ha rango minore o uguale ad 1. Le pro-prietà delle matrici semiseparabili sono state usate per l’analisi e la sintesi di

algoritmi basati sul metodo QR per il calcolo degli autovalori. `E stata svolta

l’implementazione dell’algoritmo QR per matrici semiseparabili e un’ampia sperimentazione numerica.

La tesi `e organizzata come segue. Nel primo capitolo si introduce la definizione di matrice semiseparabile data utilizzando la nozione di rango strutturato [19]. Vengono inoltre mostrati alcuni risultati, tra cui il teorema

(7)

Introduzione

della nullità e alcune sue conseguenze, che permettono di ricavare le rela-zioni tra matrici semiseparabili e matrici a banda. In seguito viene presa in considerazione la definizione di matrice semiseparabile data per generato-ri e la relativa rappresentazione. Il vantaggio di questa rappresentazione è quello di permettere la descrizione della matrice con un numero di parametri lineare nella dimensione n, e di poter costruire metodi di basso costo com-putazionale per la risoluzione di sistemi lineari e per l’inversione di matrici. Si mostra inoltre che utilizzando tale rappresentazione si possono incontra-re gravi problemi di instabilità numerica e di non robustezza. Vengono poi definite le matrici di Green; tali matrici sono state introdotte da Asplund [1] con l’obiettivo di descrivere le inverse delle matrici a banda; nella tesi vengono analizzate le relazioni che queste matrici hanno con le matrici se-miseparabili. Infine viene introdotta una classe di matrici che generalizza le matrici semiseparabili che avrà un ruolo importante nei metodi per il calcolo di autovalori.

Il secondo capitolo è relativo al metodo QR. Nella prima parte viene de-scritto il metodo QR e si studiano le ipotesi di convergenza. Vengono inoltre descritte la tecnica di traslazione dello spettro degli autovalori di A, neces-saria per aumentare la velocità di convergenza del metodo, e la tecnica di deflazione che consiste nel ridurre l’ordine della matrice una volta approssi-mato con sufficiente precisione un autovalore. Nella seconda parte vengono studiate le proprietà della fattorizzazione QR in relazione alla struttura se-miseparabile. Richiamando il teorema della nullità si traggono importanti caratterizzazioni della struttura dei fattori Q ed R della fattorizzazione QR di una matrice semiseparabile. Infine nell’ultima parte del secondo capitolo si studia il metodo QR applicato ad una particolare struttura semiseparabile generalizzata. Viene dimostrato che questa struttura è mantenuta dal QR,

cio`e le matrici Ak generate dal QR a partire da una matrice semiseparabile

generalizzata hanno ancora una struttura semiseparabile generalizzata. Que-sto permette di costruire un algoritmo tipo QR per il calcolo degli autovalori che ha un costo computazionale per passo dell’ordine di O(n) operazioni moltiplicative ed inoltre, lo spazio di memoria richiesto da tale algoritmo `e lineare.

Nel terzo capitolo viene data una descrizione dettagliata di tale algorit-mo, mediante una suddivisione in tre fasi: riduzione in forma di Hessenberg superiore, riduzione in forma triangolare e il calcolo del prodotto RkQk.

Infine nel quarto capitolo viene descritta un’implementazione in FOR-TRAN95 del metodo presentato nel capitolo 3 e viene svolta un’ampia speri-mentazione numerica. Nella sperisperi-mentazione abbiamo verificato le proprietà di stabilità numerica e di complessità di calcolo dell’algoritmo usando matrici test di varie dimensioni. La nostra implementazione è stata confrontata con i

(8)

Introduzione

programmi del pacchetto IMSL per il calcolo di autovalori mediante metodo QR. Dalla sperimentazione svolta `e risultato che la nostra implementazione

`e pi`u veloce nel caso di matrici di dimensione maggiore a 200. Inoltre gli

errori generati dai due programmi sono confrontabili. Il grande vantaggio della nostra implementazione `e che l’ingombro di memoria richiesto `e O(n)

mentre i metodi IMSL richiedono O(n2_{) locazioni di memoria e il costo}

com-putazionale `e proporzionale a n2 _{anzich´e a n}3_{. Questo permette di trattare}

problemi di grandi dimensioni in tempi molto pi`u bassi. Infatti, in alcuni

casi, gi`a per dimensioni 1600 il fattore di accelerazione nei tempi di CPU `e circa 84 . Abbiamo poi applicato il programma per l’approssimazione di zeri di polinomi utilizzando la strategia di S. Fortune [13] applicata a matrici companion generalizzate.

(9)

Capitolo 1

Il concetto di semiseparabilit`

a

In questo primo capitolo vengono introdotte alcune definizioni e propriet`a che saranno utili in seguito.

1.1 Notazioni e definizioni

Cominciamo con le notazioni adottate:

indicheremo con Cm×n _{lo spazio delle matrici m×n ad elementi complessi}

e l’elemento in posizione (i, j) di una matrice A sar`a indicato con ai,j.

Inol-tre, con A[i : j, k : l] si intender`a la sottomatrice di A avente indice di riga compreso tra i e j e indice di colonna compreso tra k ed l. Denoteremo

con AT _{la matrice trasposta di A e con A}H _{la matrice trasposta coniugata.}

Una matrice Q ∈ Cn×n _{`e unitaria se Q}H_{Q = QQ}H _{= I, `e hermitiana se}

Q = QH_{, simmetrica se Q = Q}T_{. Inoltre A = (a}

i,j) `e triangolare superiore

(rispettivamente inferiore) se ai,j = 0 per i > j (rispettivamente i < j).

Definizione 1.1. Sia A una matrice m × n. Indichiamo con M l’insieme dei numeri {1, 2, . . . , m} e con N l’insieme {1, 2, . . . , n}. Detti α e β rispet-tivamente due sottoinsiemi non vuoti di M ed N , con la notazione α × β indicheremo l’insieme {(i, j) | i∈α, j∈β} mentre con A[α; β] verr`a indicata la sottomatrice di A con indici di riga in α e indici di colonna in β.

Definizione 1.2. Data una matrice A ∈ Cn×n_{, con B = (b}

i,j) = triu(A, p)

viene indicata la matrice triangolare superiore che contiene la parte triango-lare superiore di A. Cio´e

bi,j = ai,j per j − i≥p,

(10)

1. Il concetto di semiseparabilit`a

Analogamente, la matrice B = tril(A, p) `e la matrice triangolare inferiore

formata dagli elementi della parte triangolare inferiore di A tali che bi,j =

ai,j per j − i ≤ p e bi,j = 0 altrimenti.

Diamo ora la definizione di matrice in forma di Hessenberg superiore (analogamente inferiore) che utilizzeremo nei seguenti capitoli.

Definizione 1.3. Una matrice A `e detta in forma di Hessenberg superiore se i suoi elementi soddisfano la relazione

ai,j = 0 per ogni i − j≥2;

analogamente, A `e detta in forma di Hessenberg inferiore se AT _{`e in forma}

di Hessenberg superiore.

Introduciamo a questo punto le definizioni di matrice tridiagonale e ma-trice a banda; tali classi di matrici hanno particolare interesse e nel resto del capitolo verranno studiate le caratteristiche delle loro matrici inverse. Definizione 1.4. Una matrice A `e detta tridiagonale se

aij = 0 per | i − j |> 1.

A `e detta tridiagonale in senso stretto se tutti gli elementi della sopradiago-nale e della sottodiagosopradiago-nale non sono nulli, cio`e:

ai+1,i 6= 0 e aj,j+1 6= 0 per i, j = 1, . . . , n − 1.

Definizione 1.5. Una matrice A ∈ Cn×n _{`e detta a banda di ordine {r, s}}

con 1 ≤ r, s ≤ n se ha la seguente propriet`a:

ai,j = 0 per ogni i − j > r , j − i > s

e se inoltre esistono un indice i e un indice j per i quali ai+r,i 6= 0 e aj,j+s 6= 0.

Definizione 1.6. Una matrice A ∈ Cn×n _{`e detta a banda in senso stretto}

di ordine {r, s} con 1 ≤ r, s ≤ n se è a banda di ordine {r, s} ed ha tutti gli elementi sulle diagonali più esterne non nulli, cioè

aj,j+s6=0 per ogni j = 1, . . . , n − s,

(11)

Matrici semiseparabili

Vediamo ora la definizione di fattorizzazione QR di una matrice e un particolare tipo di matrici diagonali che ci saranno utili nel prossimo capitolo: Definizione 1.7. Una matrice A ammette fattorizzazione QR se esistono una matrice unitaria Q e una matrice triangolare superiore R tali che :

A = QR.

Definizione 1.8. Una matrice S di ordine n `e detta matrice di fase se S `e diagonale e unitaria, ossia:

S =      θ1 θ2 . .. θn      .

1.2 Matrici semiseparabili

Le matrici semiseparabili sono matrici la cui struttura pu`o essere espressa in termini di rango. Per questo gioca un ruolo importante il concetto di rango strutturato che definiamo di seguito.

Definizione 1.9. Sia A una matrice m × n. Siano α e β rispettivamente due sottoinsiemi non vuoti di M ed N . Una struttura Σ `e definita come un sottoinsieme non vuoto di M × N. Il rango strutturato r(Σ; A) relativo a Σ `e definito come:

r(Σ; A) = max{rank(A[α; β]) | α×β⊆ Σ}.

Prima di passare alla definizione delle matrici semiseparabili, occorre definire le strutture corrispondenti.

Definizione 1.10. Siano M = {1, . . . , m} e N = {1, . . . , n}. Definiamo le seguenti strutture:

• Il sottoinsieme

Σl= {(i, j)| i≥j, i ∈ M, j ∈ N}

`e detto struttura triangolare inferiore, infatti gli elementi della struttura corrispondono agli indici della parte triangolare inferiore della matrice.

(12)

• Il sottoinsieme

Σωl= {(i, j)| i > j, i ∈ M, j ∈ N}

`e detto struttura strettamente triangolare inferiore. • Il sottoinsieme

Σ(p)_l _{= {(i, j)| i > j − p, i ∈ M, j ∈ N}}

`e detto struttura p-triangolare inferiore e corrisponde agli indici della matrice A sotto la p-esima diagonale. La 0-esima diagonale corrisponde alla diagonale principale, mentre la p-esima diagonale si riferisce alla p-esima sopradiagonale (p > 0) e la −p-esima diagonale si riferisce alla p-esima sottodiagonale per p > 0.

Si osservi che Σ(1)_l = Σl, Σ(0)_l = Σωl e Σωl ( Σl; inoltre la struttura Σ(p)_l

con p > 1 contiene tutti gli indici della parte triangolare inferiore, ma contiene anche qualche indice della sopradiagonale della parte strettamente superiore della matrice. Per la parte triangolare superiore della matrice, le strutture Σu, Σωu e Σ(p)u sono definite in modo simile e sono chiamate rispettivamente:

struttura triangolare superiore, struttura strettamente triangolare superiore e struttura p-triangolare superiore.

Il rango strutturato connesso alla struttura triangolare inferiore `e detto rango triangolare inferiore. Simili definizioni sono date per le altre strutture.

A questo punto possiamo dare la nozione di matrice semiseparabile [19]: Definizione 1.11. Una matrice n×n S `e detta matrice {p, q}-semiseparabile, con p≥0 e q≥0, se sono soddisfatte le seguenti propriet`a:

r(Σ(p)_l _{; S)≤p,} r(Σ(−q)u ; S)≤q.

Questo significa che il rango p-triangolare inferiore `e minore o uguale a p e il rango q-triangolare superiore `e minore o uguale a q.

La precedente definizione ci dice che tutte le sottomatrici della matrice che stanno al di sotto della p-esima sopradiagonale hanno rango massimo minore o uguale a p e tutte le sottomatrici della matrice che stanno al di sopra della q-esima sottodiagonale hanno rango massimo minore o uguale a q. Quando si parla di matrice {p}-semiseparabile, o matrice di rango di semiseparabilit`a

(13)

Matrici semiseparabili

p, si intenderà una matrice {p, p}-semiseparabile. L’abbreviazione matrice semiseparabile indicherà invece, una matrice di rango di semiseparabilità 1, questo significa che tutti i sottoblocchi contenuti nella parte triangolare

inferiore (rispettivamente superiore) hanno rango al pi`u 1.

Vediamo ora alcuni risultati che ci serviranno per dimostrare che l’inversa di una matrice invertibile tridiagonale `e una matrice invertibile semisepara-bile e viceversa. Vedremo inoltre, che l’inversa di una matrice invertisemisepara-bile {p, q}-semiseparabile `e una matrice a banda di ordine {p, q}.

1.2.1 Il teorema della nullit`

a

Enunciamo ora il teorema della nullit`a, per la dimostrazione si veda [19]. Grazie a questo teorema potremo dedurre due corollari che verranno applicati in seguito a matrici legate alle matrici semiseparabili.

Definizione 1.12. Sia data una matrice A∈Rm×n_{. La nullit`a n(A) `e definita}

come la dimensione del nucleo di A.

Teorema 1.13 (teorema della nullit`a). Supponiamo sia data la matrice

invertibile A ∈ Rn×n _{partizionata nel modo seguente:}

A = A11 A12

A21 A22

con A11 di dimensione p × q. L’inversa B di A sia partizionata come

B = B11 B12

B21 B22

con B11 di dimensione q × p. Allora le nullit`a n(A11) e n(B22) sono uguali.

Vediamo due conseguenze del teorema della nullit`a che ci saranno parti-colarmente utili in seguito:

Corollario 1.14. Sia A ∈ Rn×n _{una matrice non singolare e siano α e β}

sottoinsiemi non vuoti di N con |α| < n e |β| < n. Allora

rank(A−1_{[α; β]) = rank(A[N \ β; N \ α]) + |α| + |β| − n.}

Dimostrazione. Permutando le righe e le colonne della matrice A, possiamo

spostare la sottomatrice A[N rβ; N rα] nella parte A11 in alto a sinistra. In

corrispondenza, la sottomatrice B[α; β] della matrice B = A−1 _{si sposta nella}

parte in basso a destra B22. Abbiamo allora:

(14)

n(B22) = |β| − rank(B22)

e dal momento che n(A11) = n(B22) si ha:

n − |α| − rank(A[Nrβ; Nrα]) = |β| − rank(B[α; β]) da cui

rank(B[α; β]) = |β| + |α| − n + rank(A[Nrβ; Nrα]). In particolare, scegliendo α = N rβ otteniamo:

Corollario 1.15. Data una matrice A ∈ Rn×n _{non singolare e α⊆N}

abbia-mo:

rank(A−1[α; N rα]) = rank(A[α; N rα]).

1.3 Inverse di matrici tridiagonali e matrici a

banda

Cerchiamo ora di capire in che modo matrici {p, q}-semiseparabili e matrici a banda di ordine {p, q} sono correlate. I risultati che vedremo prendono in considerazione la parte triangolare inferiore della matrice A di partenza; propriet`a analoghe valgono per la parte triangolare superiore.

Teorema 1.16. La differenza tra il rango triangolare inferiore di A e il rango triangolare inferiore di A−1 _{`e al pi`}_{u 1 :}

|r(Σl; A) − r(Σl; A−1)|≤1.

Dimostrazione. Abbiamo

r(Σl; A) = max

k=1,...,nrankA[{k, k + 1, . . . , n}; {1, . . . , k}].

Vale anche la seguente relazione:

rankA[{k, k + 1, . . . , n}; {1, . . . , k}] = rankA−1_{[{k + 1, . . . , n}; {1, . . . , k − 1}]}

(il secondo termine `e 1 per k = 1 o k = n). Combinando le osservazioni precedenti:

rankA−1_{[{k, k + 1, . . . , n}; {1, . . . , k}]≤} (1.1)

≤rankA−1[{k + 1, . . . , n}; {1, . . . , k − 1}] + 2 = rankA[{k, k + 1, . . . , n}; {1, . . . , k}] + 1.

(15)

Inverse di matrici tridiagonali e matrici a banda

Vediamo con un esempio la connessione di questo teorema con le matrici semiseparabili.

ESEMPIO 1.17. Consideriamo la seguente matrice tridiagonale invertibile A =   1 1 0 1 1 1 0 1 1  

che ha rango triangolare inferiore 2. L’inversa `e una matrice semiseparabile

A−1 =   0 _{1 −1} 1 −1 1 −1 1 0  

di rango triangolare inferiore 1.

Questo esempio mostra che `e necessario un ulteriore studio per capire

pi`u chiaramente il legame tra il rango triangolare inferiore di una matrice e

quello dell’inversa.

Limitiamoci per ora a considerare la relazione tra la classe delle matrici tridiagonali e la classe delle matrici semiseparabili. Ci restringeremo alle matrici con rango strettamente superiore e inferiore uguale a 1. Osserviamo infatti che, sia la classe delle matrici tridiagonali sia quella delle matrici semiseparabili, sono incluse in questa classe.

Nonostante tale restrizione, questi teoremi possono essere generalizzati

per matrici aventi rango di semiseparabilit`a pi`u alto e per matrici a banda

come vederemo in seguito.

ESEMPIO 1.18. Consideriamo una matrice tridiagonale T con inversa S :

T = 1/5     2 1 0 0 1 2 1 0 0 1 2 1 0 0 1 2     S = T−1 ₌     4 −3 2 −1 −3 6 −4 2 2 −4 6 −3 −1 2 −3 4    

Si vede che T−1_{ha rango strettamente inferiore e superiore 1 mentre l’inversa}

di una matrice che soddisfa tali condizioni non `e necessariamente una matrice tridiagonale.

Prendendo A e la sua inversa A−1_:

A =       1 2 2 2 2 1 1 2 2 2 1 1 1 2 2 1 1 1 1 2 1 1 1 1 1       A−1 ₌       −1 0 0 0 2 1 ₋₁ 0 0 0 0 1 ₋₁ 0 0 0 0 1 ₋₁ 0 0 0 0 1 ₋₁      

(16)

La matrice A come A−1 _{ha rango strettamente triangolare inferiore e}

superiore uguale a 1 ma A−1 _{non `e una matrice tridiagonale.}

Vediamo un teorema [12] che chiarir`a l’esempio precedente.

Teorema 1.19. Sia A una matrice non singolare n × n con rango stretta-mente triangolare inferiore uguale a uno. Per ogni k tale che 1 < k < n, sono fatti equivalenti:

1. Il rango strettamente triangolare inferiore di A rimane uno anche se la struttura strettamente triangolare inferiore viene estesa con l’elemento diagonale in posizione (k, k);

2. In A−1 _{c’`e un blocco di zeri nella sottomatrice A}−1_{[N r N}

k; Nk−1] con

Nk = {1, . . . , k}.

Dimostrazione. La dimostrazione si ottiene applicando il corollario 1.14 in quanto 1 si pu`o riscrivere come:

rankA[N r N_k−1; Nk] = 1,

mentre 2 equivale a

rankA−1[N r Nk; Nk−1] = 0.

Ma dal corollario 1.14 segue:

rankA−1[N r Nk; Nk−1] = rankA[N r Nk−1; Nk] − 1.

Ogni matrice semiseparabile, che non sia triangolare superiore (in tal caso è noto che l’inversa è ancora una matrice triangolare superiore), verifica l’ipotesi 1 del teorema precedente. Da tale teorema quindi se ne deduce che l’inversa di una matrice semiseparabile è una matrice tridiagonale.

Possiamo estendere questo teorema al caso pi`u generale:

Teorema 1.20. Sia A una matrice n × n non singolare il cui rango (p − 1)-triangolare inferiore `e minore o uguale a p. Per ogni k tale che 1 < k < n−p sono fatti equivalenti:

1. Il rango (p − 1)-triangolare inferiore rimane minore o uguale a p anche estendendo la struttura Σ(p−1)_l con l’elemento in posizione

(17)

Semiseparabilit`a per generatori

2. In A−1 _{c’`e un blocco di zeri in A}−1_{[N r N}

k+p−1; Nk−1].

Dimostrazione. La dimostrazione di questo risultato `e del tutto analoga alla precedente, basta osservare che in questo caso 1 equivale a

rankA[N r N_k−1; N_k+p−1_{] ≤ p,} mentre 2 `e equivalente a

rankA−1[N r N_k+p−1; N_k−1] = 0 e si ha

rankA[N r N_k−1; N_k+p−1] = rankA−1[N r N_k+p−1; N_k−1] + p.

Come in [19], da questi teoremi possiamo dedurre il seguente: Teorema 1.21. L’inversa di:

• una matrice tridiagonale invertibile `e una matrice semiseparablie; • una matrice a banda di ordine {p, q} invertibile `e una matrice {p,

q}-semiseparabile.

Analogamente, dal teorema 1.20, segue anche il viceversa dell’ultima af-fermazione, ossia che l’inversa di una matrice {p, q}-semiseparabile `e una matrice a banda di ordine {p, q}.

1.4 Semiseparabilit`

a per generatori

Molto spesso la definizione usata per le matrici semiseparabili `e quella data per generatori (vedi [4], [9]). Il vantaggio che questa definizione ha rispetto a quella qui adottata `e che le matrici semiseparabili per generatori sono facilmente rappresentabili con O(n) elementi. Vediamo la definizione:

Definizione 1.22. Una matrice quadrata S = (si,j) di ordine n `e detta

semi-separabile per generatori se esistono quattro vettori u, v, z e w di lunghezza n tali che:

sij = uivj per i≤j,

sij = wizj per i≥j.

S `e detta propriamente semiseparabile per generatori se:

(18)

Da questa definizione segue la relazione:

uivi = wizi i = 1, . . . , n.

I vettori u, v, z e w sono detti i generatori di S.

Diamo anche la definizione pi`_{u generale di matrice {p, q}-semiseparabile}

per generatori [4].

Definizione 1.23. Una matrice quadrata di ordine n S = (sij) `e detta

{p, q}-semiseparabile per generatori se esistono quattro matrici U = (uij),

V = (vij), W = (wij) e Z = (zij) rispettivamente di dimensioni: n×q, q×n, n×p e p×n tali che: sij = q X k=1 ui,kvk,j per i − j < q, sij = p X k=1 wi,kzk,j per j − i < p.

S `e detta propriamente {p, q}-semiseparabile per generatori se inoltre:

p X k=1 wikzkj − q X k=1 uikvkj6=0 per i − j = q e j − i = p.

Da questa definizione segue che U, V, Z e W devono soddisfare le equa-zioni: p X k=1 wi,kzk,j− q X k=1 ui,kvk,j = 0 per − p < i − j < q.

Questo significa che la matrice B = U V − W Z ha tutti elementi nulli nel-la banda centrale composta da q − 1 sottodiagonali e p − 1 sopradiagona-li. Inoltre se S `e propriamente {p, q}-semiseparabile per generatori, allora B ha tutti elementi non nulli sulla q-esima sottodiagonale e sulla p-esima sopradiagonale.

Limitiamoci a considerare le matrici semiseparabili per generatori (di rango di semiseparabilit`a 1).

Si vede dalla definizione che tali matrici sono matrici semiseparabili ma il viceversa non vale.

Consideriamo infatti una generica matrice semiseparabile per generatori:

S =      u1v1 u1v2 . . . u1vn w2z1 u2v2 . . . ... ... . . .. ... wnz1 wnz2 . . . unzn      .

(19)

Semiseparabilit`a per generatori

Poich´e per definizione

uivi = wizi per i = 1, . . . , n

si vede facilmente che ogni sottomatrice estratta dalla sottomatrice triango-lare inferiore ( analogamente superiore ) di S ha rango minore o uguale ad 1.

Consideriamo invece la seguente matrice A:

A =   0 1 0 1 0 0 0 0 1  .

Se A fosse semiseparabile per generatori allora esisterebbero quattro vettori u, v, z e w tali che

aij = uivj i ≤ j,

aij = wizj i ≥ j.

Vediamo il caso dei vettori u e v, il caso di w e z `e analogo. Occorre risolvere    u1v1 = 0 u1v2 = 1 u2v3 = 0 u1v3 = 0 u2v3 = 0 u3v3 = 1 Ma da u1v1 = 0 e u1v2 = 1 segue u1 6= 0 , v1 = 0 e v2 = 1 u1 ;

inoltre da u1v3 = 0 si ha v3 = 0, ma u3v3 = 1 implica v3 6= 0. Quindi si vede

che A non `e semiseparabile per generatori.

Un’importante proprietà delle matrici semiseparabili per generatori è che tali matrici hanno per inversa una matrice tridiagonale in senso stretto. Si può dimostrare infatti (si veda ad esempio[4]) che:

Teorema 1.24. L’inversa di una matrice non singolare propriamente semi-separabile per generatori `e una matrice tridiagonale in senso stretto.

Vale anche il viceversa:

Teorema 1.25. L’inversa di una matrice non singolare tridiagonale in senso stretto `e una matrice propriamente semiseparabile per generatori.

(20)

Analoghi teoremi valgono per matrici propriamente {p, q}-semiseparabili per generatori e per matrici a banda. Ci limitiamo ad enunciarli in quanto li applicheremo in seguito.

Teorema 1.26. L’inversa di una matrice non singolare a banda di ordine {p, q} in senso stretto `e una matrice propriamente {p, q}-semiseparabile per generatori.

Vale anche il viceversa.

Teorema 1.27. L’inversa di una matrice non singolare propriamente {p, q}-semiseparabile per generatori `e una matrice a banda di ordine {p, q} in senso stretto.

Come conseguenza si ha il seguente corollario che verr`a utilizzato pi`u

avanti.

Corollario 1.28. Sia A una matrice {p, q}-semiseparabile per generatori, definita dalle matrici U, V, W e Z come nella definizione 1.23; A `e non singolare se e solo se:

• `e propriamente {p, q}-semiseparabile per generatori e

• il blocco q × q in alto a destra di UV e il blocco p × p in basso a sinistra di W Z sono non singolari.

In questo paragrafo abbiamo visto la convenienza che si ha nel definire le matrici semiseparabili per generatori, questa definizione per`o comporta alcuni svantaggi che saranno lo studio del prossimo paragrafo.

1.5 Aspetti computazionali

Il vantaggio della definizione di matrice semiseparabile per generatori `e che

tali matrici sono costruite con O(n) elementi, al contrario degli n2 _elementi

necessari per una generica matrice di ordine n.

A tale definizione però sono legati problemi di instabilità numerica. Per questo paragrafo, salvo diverse indicazioni, quando parleremo di ma-trici semiseparabili o semiseparabili per generatori intenderemo mama-trici sim-metriche di rango di semiseparabilità 1 e indicheremo con S(u, v) la matrice

(21)

Aspetti computazionali

semiseparabile rappresentata dai genaratori u e v, cio`e una matrice della forma: S(u, v) =      u1v1 u2v1 . . . unv1 u2v1 u2v2 . . . unv2 ... ... ... ... unv1 . . . unvn      .

Con il seguente esempio sarà chiaro in che modo la definizione per gene-ratori può creare problemi di instabilità numerica.

ESEMPIO 1.29. Consideriamo la matrice A = (ai,j) definita da:

ai,j = ε|i−j| = ε

i_ε−j _i≥j

εj_ε−i _i≤j

quindi la matrice A `e la matrice:

A =      1 ε . . . εn−1 ε . .. ... ... . .. ... εn−1 1      .

Volendo usare la definizione per generatori di A, si definiscano u e v: ui = (εi−1) vj = (ε−j+1)

quindi

u = 1 ε . . . εn−1 T

v = 1 ε−1 _{. . . ε}−(n−1) T .

Quando rappresentiamo A con uvT_{, se ε `e “piccolo”, ad esempio ε'}1

10, e

n > 309, la rappresentazione floating point in precisione doppia degli elementi

εi _{per i > 309 non potr`a essere ottenuta se non generando condizioni di}

underflow per cui tali elementi vengono rappresentati con zero. Quindi nella rappresentazione floating point di A troviamo due blocchi di zeri che sono

simmetricamente al di sotto della (¯_{n − 2)-sottodiagonale e al di sopra della}

(¯_{n − 2)-sopradiagonale per ¯n = 309. La rappresentazione floating point del}

vettore u invece avr`a tutti zeri dalla ¯n-sima componente in poi. Quindi

quando rappresentiamo A come uvT_{, otteniamo una fascia di zeri dall’¯}

n-sima riga in poi, e questo non coincide con la rappresentazione floating point della matrice A.

Si vede allora, che questa rappresentazione per generatori pu`o portare ad errori che non sono trascurabili quando si utilizza necessariamente la rappresentazione floating point.

(22)

A questo punto cerchiamo di capire dov’`e il problema. Dimostreremo che il problema `e nella definizione data in quanto, le matrici diagonali non appartengono alla classe delle matrici rappresentabili con due generatori u e v.

Facciamo alcune considerazioni sulle matrici tridiagonali simmetriche. Una proprietà importante delle matrici tridiagonali simmetriche è che ta-li matrici sono definite dagta-li elementi della diagonale e della sottodiagona-le cioè, occorrono 2n − 1 esottodiagona-lementi per conoscere una matrice tridiagonasottodiagona-le simmetrica.

Un’altra propriet`a, molto importante per alcune applicazioni, `e la seguen-te: data una matrice T tridiagonale simmetrica, applicando ad essa l’algo-ritmo QR per calcolarne gli autovalori, otteniamo una successione di matrici tridiagonali simmetriche:

T(0) _{→ T}(1) _{→ . . . → T}(n) _{→ . . .}

convergente ad una matrice diagonale. Le matrici diagonali appartengono alla classe delle matrici tridiagonali (simmetriche).

Entriamo nel dettaglio e iniziamo con la definizione di limite.

Definizione 1.30. Il limite di una famiglia di matrici A ∈ Rn×n (se esiste)

per →0, con , 0 ∈ R, dove A `e la matrice data da:

A =    (a1,1) . . . (a1,n) ... ... (an,1) . . . (an,n)    `e definito come lim →0 A =    lim_→0(a1,1) . . . lim→0(a1,n) ... ... lim_→0(an,1) . . . lim→0(an,n)   .

Riassumiamo quindi le propriet`a delle matrici tridiagonali simmetriche: Corollario 1.31. La classe delle matrici tridiagonali simmetriche ha le se-guenti propriet`a:

• possono essere rappresentate con O(n) elementi; • tale classe di matrici `e chiusa.

(23)

Consideriamo ora la classe delle matrici semiseparabili per generatori. Le matrici di tale classe possono essere descritte con O(n) elementi, co-me abbiamo già osservato. Tuttavia, le matrici diagonali non appartengono alla classe delle matrici semiseparabili per generatori, però si può facilmente costruire una successione di matrici semiseparabili per generatori (esempio con l’algoritmo QR) convergente ad una matrice diagonale. In altre parole la classe delle matrici semiseparabili per generatori non è chiusa.

Vediamo allora come sono legate le matrici semiseparabili e le matrici semiseparabili per generatori in termini di convergenza. Dimostreremo che la classe delle matrici semiseparabili `e chiusa ed inoltre, la chiusura del-le matrici semiseparabili per generatori coincide con la classe deldel-le matrici semiseparabili.

Prima di fare questo per`o, enunciamo un risultato [19] che ci servir`a in seguito:

Proposizione 1.32. Sia data una matrice S simmetrica, semiseparabile che non si possa rappresentare con due generatori. Allora S si pu`o scri-vere come una matrice diagonale a blocchi ciascuno dei quali, `e una matrice semiseparabile rappresentabile con due generatori.

Possiamo ora dimostrare il teorema principale.

Teorema 1.33. La chiusura della classe delle matrici semiseparabili rappre-sentabili con due genaratori `e la classe delle matrici semiseparabili.

Dimostrazione. Dimostriamo le due inclusioni mostrando per prima co-sa che data una matrice appartenente alla chiusura della classe delle ma-trici semiseparabili rappresentabili con due generatori, essa `e una matrice semiseparabile.

Sia data una famiglia di matrici semiseparabili rappresentabili con due generatori

S(u(), v()) ∈ Rn×n _{con ∈ R e →}

0

tale che il limite esista e sia S ∈ Rn×n, cio`e: lim

→0S(u(), v()) = S ∈ R n×n_.

Occorre dimostrare che S `e una matrice semiseparabile.

Dall’ipotesi si sa che lim_→0(ui(), vj()) ∈ R. Bisogna provare che, per

ogni i∈{2, . . . , n}: rank( lim

(24)

Abbiamo per ogni i ∈ {2, . . . , n}:

rank(S[i : n; 1 : i]) = max {rank(M)|M sottomatrice quadrata non vuota di S[i : n; 1 : i]}.

Consideriamo allora una sottomatrice 2 × 2 non vuota M di S[i : n; 1 : i] e indichiamo con M () la corrispondente sottomatrice di S(u(), v()).

Per ipotesi abbiamo che, per ogni il rank(M ()) ≤ 1, cio`e det(M()) = 0.

Poich´e il determinante `e una funzione continua: det M = det( lim

→0 M ()) = lim →0 (det(M ())) = 0 ne segue che rankS[i : n; 1 : i] ≤ 1. Dimostriamo l’altra inclusione.

Sia data una matrice S semiseparabile tale che non si possa rappresentare con due generatori. Allora dimostriamo che esiste una famiglia di matrici

S(u(), v()) con →0 convergente ad S, cio`e:

lim

→0

S(u(), v()) = S.

Per la proposizione precedente, la matrice S si pu`o scrivere come una ma-trice composta di due blocchi diagonali in cui ogni blocco `e semiseparabile

rappresentabile con due generatori (se ci sono pi`u blocchi la dimostrazione `e

analoga), cio`e S ha la seguente struttura:

S = S(u, v) 0 0 S(s, t) Definiamo i vettori: u() =hu1 , . . . , uk , s1, . . . , sl i , v() = [v1, . . . , vk, t1, . . . , tl] .

Si vede allora che la successione di matrici S(u(), v()) converge, ossia: lim

→0

(25)

Abbiamo quindi dimostrato che la classe delle matrici semiseparabili `e un’estensione della classe delle matrici semiseparabili per generatori.

Inoltre da questo teorema segue che la classe delle matrici semiseparabili `e chiusa.

A questo punto, vista la chiusura della classe delle matrici semiseparabili, viene naturale chiedersi se ci sia un modo per rappresentare le matrici semise-parabili con O(n) elementi. Per rispondere a questa domanda, consideriamo la seguente classe di matrici:

Definizione 1.34. Sia S0 _{la classe di matrici tale che S ∈ S}0 _{ha la seguente}

struttura: si,j =    uiti−1ti−2. . . tjvj 1 ≤ j < i ≤ n uivi 1 ≤ i = j ≤ n ujtj−1tj−2. . . tivi 1 ≤ i < j ≤ n

con ui, vi ∈ R per 1 ≤ i ≤ n e ti ∈ R per 1 ≤ i ≤ n.

Mostriamo che questa nuova classe di matrici S0 _{coincide proprio con la}

classe delle matrici semiseparabili.

Teorema 1.35. La classe di matrici S0 _{definite in 1.34 e la classe delle}

matrici semiseparabili S sono uguali.

Dimostrazione. Dimostriamo le due inclusioni.

S0_{⊂S Sia S ∈ S}0_{. Dobbiamo dimostrare che S `e una matrice semiseparabile,}

quindi che per ogni 1 ≤ i ≤ n vale:

rank(S[i : n; 1 : i]) ≤ 1.

Ma questo equivale a dire che il determinante di ogni sottomatrice 2×2 della parte triangolare inferiore di S `e uguale a zero. Consideriamo allora una generica sottomatrice 2 × 2 di S (con i ≥ k, l > i, e k > j )

si,j si,k sl,j sl,k = uiti−1. . . tk. . . tjvj uiti−1. . . tkvk ultl−1. . . tk. . . tjvj ultl−1. . . ti−1. . . tkvk

che possiamo scrivere come una matrice diagonale per una matrice di rango 1: uiti−1. . . tk 0 0 ultl−1. . . tk tk+1. . . tjvj vk tk+1. . . tjvj vk

Da qui si ha che il determinante di ogni sottomatrice 2 × 2 della parte triangolare inferiore di S `e zero, quindi S∈S.

(26)

S⊂S0 _{Sia S ∈ S. Sappiamo che S `e una matrice diagonale a blocchi}

do-ve ciascun blocco `e semiseparabile rappresentabile con due generatori. Supponiamo, senza perdere di generalit`a, che S sia diagonale costituita

da due blocchi e indichiamo con ˜u e ˜v i generatori del primo blocco,

entrambi di lunghezza n1, e con ˆu e ˆv, entrambi di lunghezza n2, i

generatori del secondo blocco. Definiamo ora i due vettori:

u = ˜ u ˆ u , v = ˜ v ˆ v e t1 = t2 = . . . = tn1−1 = 1, tn1 = 0 e tn1+1 = . . . = tn1+n2 = 1;

costruendo allora la matrice S come nella definizione 1.34 con u, v e t, questa `e uguale ad S. In altre parole S ∈ S0_.

Questo teorema mostra quindi che la classe delle matrici semiseparabi-li simmetriche è rappresentabile con un numero semiseparabi-lineare di parametri. La proprietà di una matrice di essere rappresentabile con un numero lineare di parametri è molto vantaggiosa in quanto può permettere di abbassare il costo computazionale delle operazioni che richiedono l’utilizzo di tale matrice.

Nel prossimo paragrafo viene introdotta la classe di matrici Cn dette

matrici semiseparabili generalizzate; queste matrici sono un’estensione della classe delle matrici semiseparabili ed hanno l’importante propriet`a di essere rappresentabili con un numero lineare di elementi. La classe delle matrici semiseparabili generalizzate avr`a un ruolo importante nei capitoli successivi.

1.6 Semiseparabilit`

a generalizzata

Introduciamo la classe delle matrici semiseparabili generalizzate definite in [6].

Indichiamo la nuova classe di matrici con Cn.

Definizione 1.36. Una matrice A = (ai,j) ∈ Cn×n appartiene a Cn se

esi-stono d1, . . . , dn numeri reali, t2, . . . , tn−1 numeri complessi e quattro vettori

u = [u1, . . . , un]T ∈ Cn, v = [v1, . . . , vn]T ∈ Cn, z = [z1, . . . , zn]T ∈ Cn e w = [w1, . . . , wn]T ∈ Cn tali che:    ai,i = di+ ziwi 1≤i≤n;

ai,j = uit×i,jvj 1≤j < i , 2≤i≤n;

ai,j = uit×j,ivi+ ziwj − zjwi 1≤i < j , 2≤j≤n,

(1.2) dove t×_i,j = t_i−1. . . tj+1 per i − 1≥j + 1, altrimenti t×i,i+1 = 1.

(27)

Semiseparabilit`a generalizzata

Le matrici appartenenti a Cn vengono dette semiseparabili generalizzate

in quanto hanno rango strettamente triangolare inferiore uguale a 1 e rango strettamente triangolare superiore uguale a 3.

Facciamo alcune osservazioni su questa nuova classe Cn, che verranno

provate in seguito.

1. La classe Cn include diverse classi di matrici companion generalizzate

e loro sottoclassi;

2. La fattorizzazione QR di una matrice appartenente a Cnha una

struttu-ra particolare e il prodotto RQ è chiuso rispetto a questa classe, cioè da-ti i fattori Q ed R della fattorizzazione QR di una matrice semisepara-bile generalizzata, il prodotto RQ è ancora una matrice semiseparasemisepara-bile generalizzata;

3. Grazie a questa struttura, il calcolo della fattorizzazione QR, come pure

il prodotto RQ, di una matrice appartenente a Cn pu`o essere effettuato

in un tempo lineare e occupando uno spazio di memoria lineare.

Vediamo ora, a seconda di come vengono scelti i vettori che definiscono una

matrice appartenente a Cn, quali sottoclassi di matrici otteniamo.

Se z = u, w = v e ti = 1 per i = 2, . . . , n − 1, otteniamo una matrice

diagonale pi`u rango 1 della forma A = D+uvH _{dove D = [d}

1, . . . , dn] ∈ Rn×n.

Se invece assumiamo w = wen e ti = 0 per i = 2, . . . , n − 1, A si riduce a

una matrice Hermitiana tridiagonale pi`u una correzione di rango 1 data da

wzeT

n.

Scegliendo poi w = z e ti6=0 per i = 2, . . . , n−1, vediamo che Cncontiene

anche le matrici Hermitiane diagonali pi`u semiseparabili (dpss).

Infine, se v2 = . . . = vn = 0 e z2 = . . . = zn= 0, A diventa una matrice a

freccia, ossia della forma:

A =        d1 + z1w1 u2v1+ z1w2 . . . untn−1. . . t2v1 + z1wn u2v1 d2 0 . . . 0 ... 0 . .. ... ... ... ... ... untn−1. . . t2v1 0 . . . 0 dn        .

(28)

Sia A = (ai,j) ∈ Cn×n una matrice semiseparabile genaralizzata, si ha:

tril(A, −1) =         0 . . . 0 u2v¯1 0 . . . ... ... u3v¯2 . .. ... . . . ... 0 ... untn−1. . . t2v¯1 untn−1. . . t3v¯2 . . . unvn−1 0         . (1.3)

Dati gli elementi u2, . . . , un, v1, . . . , vn e t2, . . . , tn−1 indicheremo con

L({ui}ni=2, {vi}n−1i=1, {ti}n−1i=2) la matrice triangolare inferiore di destra della

(1.3). Invece:

R({ui}ni=2, {vi}n−1i=1, {ti}n−1i=2) = (L({ui}ni=2, {vi}n−1i=1, {ti}n−1i=2))H

`e la matrice triangolare superiore di parametri u2, . . . , un, t2, . . . , tn−1, e

v1, . . . , vn−1. Indicheremo inoltre con R0(·) la sottomatrice di R(·)

ottenu-ta eliminado da R(·) la prima colonna e l’ultima riga. Analogamente con

L0_{(·) denoteremo la sottomatrice ottenuta da L(·) eliminado la prima riga e}

l’ultima colonna. La matrice L({ui}ni=2, {vi}n−1i=1, 0) `e una matrice con tutti

elementi nulli esclusa la sottodiagonale che ha per elementi ηi = uivi−1 per

2≤i≤n. Tale matrice in seguito sar`a indicata con Bidiag[ηi].

Poniamo xi = [zi, wi] e yi = [wi, −zi] con i = 1, . . . , n. Si ha:

triu(A, 1) − R({ui}ni=2, {vi}n−1i=1, {ti}n−1i=2) =

     0 x1y2H . . . x1ynH ... . .. ... ... x_n−1yH n 0 . . . 0      . (1.4) Dati i vettori x1, . . . , xn−1, y2, . . . , yn, U ({xi}n−1i=1, {yi}ni=2) `e la matrice a

de-stra della (1.4). Analogamente a quanto detto prima, con U0_{(·) sar`a indicata}

la sottomatrice di U (·) ottenuta eliminado la prima colonna e l’ultima riga. Date due successioni di elementi {ai}ni=1e {bi}mi=1, indicheremo con {ai}ni=1

{bi}mi=1 la successione ottenuta concatenando le due successioni, cio`e

{ai}ni=1 {bi}i=1m = {a1, . . . , an, b1, . . . , bm}.

Utilizzeremo la notazione appena introdotta nel prossimo capitolo.

1.7 Matrici di Green

Introduciamo in questo paragrafo una classe di matrici legata alle matrici semiseparabili.

(29)

Matrici di Green

Le matrici di Green sono state definite da Asplund [1] con l’obiettivo di descrivere le inverse di matrici a banda. Se infatti nel teorema 1.26 conside-riamo una matrice a banda di ordine {p, q}, anzich`e una matrice a banda in senso stretto, otteniamo che l’inversa di tale matrice `e una matrice di Green di ordine {p, q}.

Diamo innanzitutto la definizione di matrice di Green di ordine {p, q}.

Definizione 1.37. Una matrice quadrata R = (rij) `e detta matrice di Green

di ordine {p, q} se tutte le sottomatrici formate dagli elementi rij per i quali

i −j > p hanno rango al pi`u p e tutte le sottomatrici composte dagli elementi rij per i quali j − i > q hanno rango al pi`u q.

Osservazione 1.38. Una matrice {p, q}-semiseparabile `e una matrice di Green di ordine {p, q}. Il viceversa non vale, vedremo in seguito qualche esempio per provarlo.

Osservazione 1.39. Una matrice {p, q}- semiseparabile per generatori `e una matrice di Green di ordine {p, q}.

Il viceversa per`o in generale non `e vero, infatti vale il seguente:

Lemma 1.40. Sia R una matrice di Green di ordine {p, q}. Se la sottomatri-ce in alto a destra q×q e la sottomatrisottomatri-ce in basso a sinistra p×p sono entrambe non singolari, allora R `e una matrice {p, q}-semiseparabile per generatori.

Possiamo ora provare il risultato preannunciato all’inizio del paragrafo. Teorema 1.41. Una matrice quadrata non singolare `e una matrice a banda di ordine {p, q} se e solo se la sua inversa `e una matrice di Green di ordine {p, q}.

Dimostrazione. Sia A una matrice a banda non singolare di ordine {p, q} (cio`e con p sottodiagonali e q sopradiagonali).

Se A è a banda di ordine {p, q} in senso stretto, dal teorema 1.26 si ha che l’inversa è una matrice propriamente {p, q}-semiseparabile per generatori quindi è una matrice di Green di ordine {p, q}.

Supponiamo allora che A sia una matrice a banda di ordine {p, q} ma non in senso stretto; consideriamo la matrice A(t) ottenuta da A nel modo seguente:

A(t) = A + t(E + F )

dove E = (eij) e F = (fij) sono matrici con tutti elementi nulli tranne:

eij = 1 per j − i = q e fij = 1 per i − j = p.

Possiamo dire che esiste un intervallo aperto T = (0, τ ) tale che, per t ∈ T , A(t) `e una matrice a banda di ordine {p, q} in senso stretto e non singolare,

(30)

allora, dal teorema 1.26, A−1_{(t) = (r}

ij) `e una matrice propriamente {p,

q}-semiseparabile per generatori. Quindi ogni sottomatrice quadrata di ordine

p + 1 estratta dalla parte di A−1_{(t) composta dagli r}

ij per i quali j − i < p

`e singolare e analogamente, ogni sottomatrice di ordine q + 1 estratta dalla

parte di A−1_{(t) composta dagli r}

ij per i quali i − j > q `e singolare (quindi in

particolare A−1_{(t) `e una matrice {p, q}-semiseparabile).}

Dalla continuit`a dell’argomento, questo vale ancora prendendo il limite

per t → 0, cio`e A−1 _{`e una matrice di Green di ordine {p, q}.}

Viceversa, sia R una matrice non singolare di Green di ordine {p, q}. Se R è una matrice {p, q}-semiseparabile per generatori, allora dal corollario 1.28 si ha che R è propria ed inoltre, dal teorema 1.27, si ha che la sua inversa è una matrice a banda di ordine {p, q} in senso stretto.

Altrimenti, consideriamo la matrice

R(t) = R + t(G + H)

dove G = (gij) e H = (hij) sono matrici con tutti elementi nulli tranne:

gij = 1 per i − j = n − p e hij = 1 per j − i = n − q. Allora esiste un

intervallo aperto T0 _{= (0, τ}0_{) tale che, per t ∈ T}0_{, R(t) `e non singolare e}

soddisfa le condizioni del lemma 1.40, allora R−1_{(t) `e una matrice a banda}

di ordine {p, q} in senso stretto.

Dalla continuit`a degli elementi di R−1_{(t), se consideriamo il limite per}

t → 0, R−1 _{`e una matrice a banda di ordine {p, q}.}

Dalla dimostrazione di questo teorema si può ricavare anche un’ulteriore prova del fatto che l’inversa di una matrice a banda di ordine {p, q} è una matrice {p, semiseparabile ed anche che l’inversa di una matrice {p, q}-semiseparabile è una matrice a banda di ordine {p, q}.

Concludiamo questo paragrafo con un esempio il quale mostra che le ma-trici di Green di ordine {p, q} in generale non sono mama-trici {p, q}-semiseparabili. ESEMPIO 1.42. Consideriamo il caso n = 5.

Sia A una matrice di Green di ordine {2, 3}, questo significa che tutte

le sottomatrici composte dagli aij che stanno al di sotto della seconda

sot-todiagonale hanno rango al pi`u 2, mentre tutte le sottomatrici formate da

(31)

Rotazioni di Givens

pi`u 3. Quindi la matrice

A =       1 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 1 0 0 0 1 0 1      

`e una matrice di Green di ordine {2, 3} ma non `e una matrice {2, 3}-semise-parabile.

1.8 Rotazioni di Givens

Introduciamo in questo paragrafo la definizione di matrici di Givens e ne vediamo alcune propriet`a che ci serviranno in seguito [5].

Definizione 1.43. Siano 1 ≤ i, j ≤ n con ϕ∈R e ψ∈C, con | ψ |= 1. La matrice Gij =                     1 . .. 1 c _−s 1 . .. 1 s c 1 . .. 1                     ↑ ↑ i j ← i ← j

in cui c = cos ϕ e s = ψ sin ϕ `e detta matrice di rotazione di Givens, o pi`u

semplicemente matrice di Givens.

Le matrici di Givens si ottengono dalla matrice identica per mezzo di correzioni di rango due e sono matrici unitarie.

Queste matrici sono usate, in alternativa alle matrici di Householder, nel-la riduzione di una matrice in forma di Hessenberg superiore, in particonel-lare, rivestono un ruolo importante nel calcolo della fattorizzazione QR di una ma-trice. In generale per fattorizzare una matrice A nella forma QR si usano le

(32)

matrici di Householder in quanto, l’applicazione di una matrice di Househol-der alla matrice A permette di annullare simultaneamente tutti gli elementi di una colonna di A che stanno sotto l’elemento principale ed inoltre, questo metodo richiede la met`a delle operazioni richieste dal metodo di Givens.

Vi sono però alcuni casi particolari, in cui la matrice A ha una particolare struttura e quindi occorre annullare solo particolari elementi; in tal caso è conveniente usare le matrici di Givens e, nel caso di matrici sparse, il metodo di Givens può risultare competitivo con quello di Householder. Come già anticipato, una proprietà importante delle matrici di Givens è che: data una matrice A è possibile, applicando una matrice di Givens, annullare un particolare elemento della matrice risultante, vediamo in dettaglio come.

Sia A ∈ Cn×n_{, fissati gl’indici i e j, la matrice B = G}

ijA differisce dalla

matrice A per i soli elementi delle righe di indici i e j. Se aij 6= 0, `e possibile

scegliere ϕ e ψ in modo tale che l’elemento bij sia uguale a zero. Se aii6= 0,

posto ψ = −a_aji ii aii aji , cos ϕ = | aii| p| aii|2 + | aji |2 , sin ϕ = | aji | p| aii |2 + | aji |2 , (1.5) si ha

bji = saii+ caji = ψ sin ϕaii+ cos ϕaji = ψ| aqj,i|ai,i+ | ai,i | aj,i | ai,i|2+ | aj,i|2 = = q | aj,i| ai,i |ai,i|2+ |aj,i|2 ψ + aj,i ai,i ai,i aj,i = 0.

Al posto delle (1.5) conviene in genere usare le seguenti formule che sono numericamente pi`u stabili:

se |aji| ≥ |aii|, si pone t = aii aji , sin ϕ = 1 √ 1+t2, cos ϕ = tsin ϕ, se |aji| < |aii|, si pone t = aji aii , cos ϕ = 1 √ 1+t2, sin ϕ = tcos ϕ. (1.6)

(33)

Rotazioni di Givens

Nei capitoli seguenti denoteremo con G(γ) la matrice di Givens 2 × 2 complessa di paramentro γ ∈ C ∪ ∞ data da:

G(γ) = 1 γ −¯γ 1 /p1+ | γ |2 ₌ ϕ ψ − ¯ψ ϕ con γ, ψ ∈ C, ϕ ∈ R, | ϕ |2 _{+ | ψ |}2_{= 1 e} G(∞) = 0 1 −1 0 .

Di conseguenza indicheremo con Gk,k+1(γ) la matrice di Givens n × n di

parametro γ di indici k, k + 1, cio`e la matrice:

Gk,k+1(γ) = Ik−1⊕ G(γ) ⊕ In−k−1 =   I_k−1 0 0 0 _G(γ) 0 0 0 I_n−k−1  .

(34)

(35)

Capitolo 2

Il metodo QR

Questo capitolo è diviso in tre parti. Nella prima viene descritto il metodo QR per il calcolo degli autovalori di una matrice. Descritto l’algoritmo, ven-gono analizzate le ipotesi di convergenza; infine si introducono le tecniche usate per accelerare la velocità di convergenza e per ridurre il costo com-putazionale. Per questa parte si farà riferimento principalmente a [5]. Nel secondo paragrafo analizziamo la struttura dei fattori Q ed R della fattoriz-zazione QR di una matrice semiseparabile. Infine, nell’ultimo paragrafo, si considera il metodo QR applicato a matrici semiseparabili generalizzate. Si dimostra per prima cosa che la struttura triangolare inferiore è conservata dal QR e, come risultato finale, si prova che le iterate generate dal QR, a partire da una matrice della forma (1.2), ammettono ancora una rappresentazione della forma (1.2).

2.1 La fattorizzazione QR

Il metodo QR è il metodo più usato per calcolare gli autovalori di matrici per la sua particolare efficienza e robustezza numerica, e per la sua semplicità. Tale metodo richiede comunque una serie di accorgimenti sui quali si basa la sua efficienza computazionale:

• riduzione della matrice in forma di Hessenberg superiore, oppure tri-diagonale quando la matrice di partenza `e hermitiana, al fine di ridurre il costo computazionale per passo.

• Traslazione dello spettro di A per aumentare la velocit`a di convergenza. • Riduzione dell’ordine della matrice quando un autovalore `e stato

(36)

2. Il metodo QR

Passiamo alla descizione dell’algoritmo:

posto A1 = A, il metodo QR genera una successione di matrici {Ak} nel

modo seguente:

Ak = QkRk (2.1)

dove Qk `e una matrice unitaria ed Rk `e una matrice triangolare superiore; si

definisce la matrice Ak+1 secondo la relazione:

Ak+1 = RkQk. (2.2)

Da (2.1) e (2.2) si ottiene

Ak+1 = QHkAkQk (2.3)

dalla quale segue che le matrici ottenute sono tutte simili fra di loro. Dalla

relazione (2.3) segue anche che, se A `e hermitiana, le matrici {Ak} ottenute

dal metodo QR sono tutte hermitiane.

Un’altra struttura preservata dal QR `e la forma di Hessenberg superiore.

Supponiamo che la matrice Ak sia in forma di Hessenberg superiore.

Fat-torizzando Ak con matrici elementari di Householder (o di Givens) al primo

passo si ha:        × × × × 1 . .. 1                ∗ . . . ∗ ∗ . . . ... 0 . .. ... ... ... 0 _{∗ ∗}         =         ∗ . . . ∗ 0 _∗ ... 0 _∗ ... ... . .. ... 0 . . . ∗ ∗         .

A questo punto si considera la matrice (n − 1) × (n − 1) principale di coda, tale matrice `e ancora in forma di Hessenberg superiore e si applica la stessa tecnica annullando il primo elemento della sottodiagonale. Si procede induttivamente in questo modo fino ad arrivare ad una matrice 2 × 2. Alla

fine saranno stati annullati tutti gli elementi della sottodiagonale di Ak e

quindi la matrice ottenuta sar`a una matrice Rkin forma triangolare superiore.

La matrice unitaria Qk `e data dal prodotto di n − 1 matrici elementari di

Householder ( o di Givens), che sono in forma di Hessenberg superiore, prese

dall’ultima alla prima. Quindi Ak+1, essendo ottenuta tramite un prodotto

di una matrice triangolare superiore e una matrice in forma di Hessenberg superiore, risulta essere ancora in forma di Hessenberg superiore.

Abbiamo osservato che sia la struttura hermitiana sia quella in forma di Hessenberg superiore sono preservate dal QR, da ci`o si deduce facilmente

che, se la matrice iniziale A `e tridiagonale hermitiana, la successione {Ak}

generata dal QR sar`a composta da matrici tridiagonali hermitiane. Analizziamo un primo risultato sulla convergenza di questo metodo.

(37)

La fattorizzazione QR

Teorema 2.1. Sia A ∈ Cn×n _{tale che i suoi autovalori λ}

i, i = 1, 2, . . . , n,

abbiano moduli tutti distinti, cio`e:

| λ1 |>| λ2 |> . . . >| λn|> 0. (2.4)

Indicata con X la matrice degli autovettori di A, tale che:

A = XDX−1,

dove D `e la matrice diagonale il cui i-esimo elemento principale `e λi, si

supponga che la matrice X−1 _{ammetta fattorizzazione LU . Allora esistono}

delle matrici di fase Sk tali che:

lim k→∞S H k RkSk−1 = lim k→∞S H k−1AkSk−1 = T, e lim k→∞S H k−1QkSk = I,

dove T `e triangolare superiore con gli elementi principali uguali a λ1, λ2, . . . ,

λn. Quindi gli elementi principali di Ak tendono agli autovalori di A. Se A

`e una matrice hermitiana, allora T `e diagonale.

Le ipotesi di questo teorema sono piuttosto restrittive al fine di renderne

pi`u semplice la dimostrazione. Questo per`o non significa che il metodo QR

non sia convergente in mancanza di tali ipotesi. Se `e verificata l’ipotesi che la

matrice X−1 ammette fattorizzazione LU , gli elementi principali di T

coin-cidono, nell’ordine, con λ1, λ2, . . . , λn. Se X−1 non ammette fattorizzazione

LU , si può dimostrare [20] che il metodo QR è ancora convergente, l’unica cosa che si perde, è l’ordine degli elementi diagonali di T ossia, in questo

caso, gli elementi principali di T coincidono ancora con i λi ma non sono

pi`u in ordine di modulo decrescente. Un’altra ipotesi fatta nel teorema 2.1 `e

che tutti gli autovalori di A abbiano modulo distinto; se questa ipotesi non `e

verificata, la successione formata dagli elementi diagonali di Ak non

conver-ge. Questa ipotesi è troppo restrittiva e non consente di utilizzare il metodo QR in casi importanti nelle applicazioni come quelli in cui la matrice A ha elementi reali e autovalori non reali. Anche in questo caso però è possibile utilizzare il metodo QR con opportune varianti. Supponiamo ad esempio:

| λ1 |>| λ2 |> . . . >| λr |= |λr+1| > . . . > |λn| > 0,

dove λr e λr+1 sono due numeri complessi coniugati oppure due numeri

rea-li. Da questo segue che le matrici SH

(38)

2. Il metodo QR

I perch´e in posizione (r + 1, r) ci sono elementi che non tendono a zero. Consideriamo: A(k)_r = " a(k)r,r a(k)_r,r+1 a(k)r+1,r a (k) r+1,r+1 #

la sottomatrice principale di ordine 2 di Ak formata dalle righe e colonne di

indici r e r + 1. La successione {A(k)r } non converge, ma gli autovalori delle

sottomatrici A(k)r convergono a λr e λr+1 [20]. Gli elementi diagonali di Ak

di indice diverso da r e r + 1 convergono agli altri autovalori.

Si possono presentare situazioni analoghe quando la matrice A ha pi`u

autovalori di modulo uguale, in questo caso il metodo QR genera matrici Rk

con struttura triangolare a blocchi in cui gli autovalori dei blocchi diagonali convergono agli autovalori di A.

Il metodo QR applicato ad una matrice di ordine n ha ad ogni passo un costo computazionale dell’ordine di n3_{operazioni moltiplicative (per il calcolo}

della fattorizzazione Ak = QkRk e per moltiplicare la matrice triangolare Rk

per le matrici elementari della fattorizzazione).

Per ridurre il costo computazionale globale conviene prima portare la ma-trice A in forma di Hessenberg superiore. Questa trasformazione viene fatta una sola volta, abbiamo infatti osservato prima che tale struttura `e conser-vata dal QR quindi, il metodo QR applicato a matrici in forma di

Hessen-berg superiore, produce matrici Ak che sono ancora in forma di Hessenberg

superiore.

Se la matrice A è hermitiana, la matrice in forma di Hessenberg superio-re ottenuta applicando ad A i metodi di Householder o di Givens, è ancora hermitiana, e quindi risulta tridiagonale. Inoltre, come già osservato

prece-dentemente, in tal caso tutte le matrici Akgenerate sono hermitiane e quindi

tridiagonali.

Il metodo QR applicato ad una matrice A in forma di Hessenberg

superio-re ha ad ogni passo un costo computazionale di 2n2 _{operazioni moltiplicative}

(che `e il costo computazionale per calcolare la fattorizzazione Ak = QkRk,

infatti il numero delle operazioni richieste per moltiplicare la matrice trian-golare Rk per le matrici elementari della fattorizzazione `e di ordine inferiore

al secondo). Se A `e una matrice tridiagonale, il costo computazionale di ogni passo del metodo `e lineare in n.

In [20] si dimostra che il metodo gode della stessa propriet`a di stabilit`a di cui gode la fattorizzazione QR di una matrice.

Fissato un valore ε di tolleranza, si procede applicando il metodo QR alla matrice A in forma di Hessenberg superiore fino a quando per un indice

(39)

La fattorizzazione QR

p: 1≤p≤n, l’elemento a(k)p+1,p diventa sufficientemente piccolo. Un criterio di

arresto usato, ad esempio, `e il seguente: |a(k)p+1,p| < ε(|a(k)p,p| + |a

(k)

p+1,p+1|). (2.5)

Quando la condizione (2.5) `e verificata nella matrice Ak

Ak= Bk Dk

Ek Ck

}p righe }n − p righe

dove Bk ∈ Cp×p, Ck ∈ C(n−p)×(n−p), la sottomatrice Ek ha un elemento di

modulo piccolo e gli altri tutti nulli. A questo punto si procede separatamente con le matrici Bk e Ck.

Per accelerare la velocità di convergenza del metodo QR è possibile utiliz-zarne una variante detto QR con shift. La velocità di convergenza di questo metodo dipende dai rapporti |λi/λj| per i > j, quindi dal numero:

max 1≤i≤n−1 λi+1 λi . (2.6)

Se questo rapporto `e vicino ad 1, la convergenza pu`o risultare molto lenta. In questo caso si utilizza una tecnica di traslazione dello spettro di A detta, appunto, di shift. Detto µ un valore che approssima un autovalore λ meglio degli altri autovalori, consideriamo come matrice iniziale A − µI. La

succes-sione di matrici Ak generate dal QR con shift sar`a determinata dalle seguenti

relazioni:

Ak− µI = QkRk

Ak+1= RkQk+ µI (2.7)

dalle quali si ha

QkAk+1 = AkQk− µQk+ µQk = AkQk,

quindi, anche in questo caso, le matrici generate sono tutte simili tra loro.

Gli autovalori della matrice A −µI sono i λi−µ; dal momento che la velocit`a

di convergenza `e regolata dalla (2.6), si pu`o scegliere il parametro µ in modo

tale da accelerare la velocit`a di convergenza del metodo QR con shift. `E

conveniente scegliere per µ un valore che approssima λn. Questo `e possibile

applicando il metodo QR senza shift per un certo numero p di iterazioni e scegliendo µ = a(p)n,n per le successive iterazioni con shift.

Un’altra possibilit`a `e quella di far variare lo shift ad ogni iterazione ponendo

(40)

2. Il metodo QR

Nel caso di matrici hermitiane si pu`o dimostrare [21] che con questa strategia

la convergenza a zero dell’elemento a(k)_n,n−1 `e del terzo ordine. Quando la

condizione (2.5) `e verificata per p = n − 1, si passa a considerare la matrice

Bkdi ordine n − 1 ottenuta da Ak eliminando l’ultima riga e l’ultima colonna

e si procede con l’approssimazione dei restanti autovalori.

La tecnica di shift `e applicabile anche al caso in cui la matrice A abbia

degli autovalori di modulo uguale. Supponiamo ad esempio |λ1| > |λ2| >

. . . > |λn−1| = |λn|. Consideriamo allora la sottomatrice:

A(k)_n−1 = " a(k)_n−1,n−1 a(k)_n−1,n a(k)_n,n−1 a(k)n,n # .

Scegliamo come µ l’autovalore della sottomatrice A(k)_n−1 pi`u vicino a a(k)n,n. In

questo modo per`o, la tecnica di shift pu`o portare ad avere matrici Ak a valori

complessi, questo implica un aumento del costo computazionale.

Per evitare questo problema, si possono fare due passi consecutivi di iterazione QR scegliendo come valori di shift α e β, dove α e β sono gli autovalori della sottomatrice A(k)_n−1. Otteniamo cos`ı:

Ak− αI = QkRk

Ak+1 = RkQk+ αI

Ak+1− βI = Qk+1Rk+1

Ak+2 = Rk+1Qk+1+ βI

dalle quali

QkQk+1Rk+1Rk = Qk(Ak+1− βI)Rk = Qk(RkQk+ αI − βI)Rk=

= QkRk(QkRk+ αI − βI) = (Ak− αI)(Ak− βI).

Ponendo quindi Z = QkQk+1 ed S = Rk+1Rk, otteniamo una fattorizzazione

QR della matrice M = (Ak− αI)(Ak− βI) che `e ad elementi reali perch´e α

e β sono radici di un’equazione di secondo grado a coefficienti reali. Inoltre si ottiene: ZAk+2 = QkQk+1Ak+2 = QkQk+1(Rk+1Qk+1+ βI) = = Qk(Qk+1Rk+1+ βI)Qk+1 = QkAk+1Qk+1 = = Qk(RkQk+ αI)Qk+1 = (QkRk+ αI)QkQk+1 = AkZ da cui Ak+2 = ZHAkZ.

(41)

Metodo QR e semiseparabilit`a

Otteniamo perci`o Ak+2 dalla matrice Ak utilizzando la fattorizzazione QR

della matrice reale M .

Tale procedimento per`o ha un costo computazionale piuttosto alto in

quanto, la sola costruzione della matrice M , richiede n3_{/6 operazioni}

mol-tiplicative. Si pu`o abbassare tale costo computazionale a n2 _operazioni

moltiplicative utilizzando un procedimento suggerito da Francis [14]:

1. Si costruisce la prima colonna m1 della matrice M e la matrice

elemen-tare di Householder P0 tale che

P0m1 = γe1 dove |γ| = ||m1||2.

2. Si costruiscono le matrici di Householder P1, P2, . . . , Pn−2tali che, posto

Z0 _{= P}

0P1. . .Pn−1, la matrice (Z0)HAkZ0 sia in forma di Hessenberg

superiore. Si pu`o dimostrare che le matrici:

Ak+2 = ZHAkZ e Ak+20 = (Z0)HAkZ0

sono “essenzialmente” uguali, nel senso che esiste una matrice di fase reale D tale che

Ak+2 = D−1A0k+2D.

2.2 Metodo QR e semiseparabilit`

a

In generale, le strutture conservate dal metodo QR si riducono ad alcuni casi molto particolari quali le matrici in forma di Hessenberg o le tridiagonali

simmetriche. `E facile mostrare che la struttura semiseparabile viene persa e

questo pu`o accadare gi`a dopo il primo passo del metodo QR.

ESEMPIO 2.2. Consideriamo la matrice semiseparabile S data da:

S =     1 5 _{−10 −5} 2 3 _{−6 −3} 6 9 4 2 12 18 8 6    

Facendo un passo di iterazione QR otteniamo come nuova iterata S1 la

matrice: S1 =     11.9514 12.7573 _{−19.2509 −4.04422} 8.01665 0.657344 _−4.86192 7.02455 6.63187 _−0.488908 _{0.991304 −4.74763} 0.789115 −0.0581743 0.117954 0.4    

(42)

2. Il metodo QR

Si vede facilmente che il rango triangolare inferiore `e ancora 1 ma il rango triangolare superiore `e 2, infatti basta considerare il minore:

12.7573 −19.2509 0.657344 −4.86192

che ha determinante diverso da zero.

Quindi, se si applica il metodo QR ad una matrice semiseparabile, le

matrici {Ak} generate, non sono pi`u matrici semiseparabili. Tuttavia, le

matrici semiseparabili hanno una struttura particolare e, come dimostreremo in questo paragrafo, anche i fattori Q ed R della fattorizzazione QR di una tale matrice hanno una particolare struttura definita in termini del rango.

Si possono trarre informazioni sul fattore Q della fattorizzazione QR di una matrice semiseparabile da una generalizzazione del teorema della nullit`a. Teorema 2.3. Sia A una matrice invertibile, avente fattorizzazione QR: A = QR. Supponiamo che A sia partizionata nel seguente modo:

A = A11 A12

A21 A22

con A11 di dimensione p × q. L’inversa B di Q sia partizionata:

Q−1 = B = B11 B12

B21 B22

con B11 di dimensione q × p. Allora n(A21) = n(B21).

Dimostrazione. Dimostriamo per prima cosa che n(B21) ≥ n(A21).

Sup-poniamo che n(A21) = c. Allora esiste una matrice F con c colonne

linear-mente indipendenti tale che A21F = 0. Partizioniamo la matrice R nel modo

seguente:

R = R11 R12

0 R22