19.5 Convergenza del Metodo di Lanczos
19.5.1 Polinomi di Chebyshev
Ogni x ∈ Km(A, v)si può rappresentare in forma polinomiale come x = p(A)v.
Nello studio della convergenza del Metodo di Lanczos quindi sarà fondamentale poter approssimare fedelmente e maggiorare aderentemente il polinomio p(t). Questo è realizzato mediante i polinomi di Chebyshev, così de niti:
De nizione 19.5. Un polinomio di Chebyshev del primo tipo di grado k si esprime come
oppure mediante la relazione è di ricorrenza Ck+1(t) = 2tCk(t) − Ck−1(t) k ≥ 2 C1(t) = cos θ = t k = 1 C0(t) = 1 k = 0
La relazione vale ancora quando si estende la de nizione dei polinomi al caso |t| ≥ 1, nel modo seguente:
Ck(t) = cosh(karccosh(t)) = cosh(kθ) per |t| ≥ 1
Osservazione 19.1. Dal momento che per ogni t ∈ R valgono cos(t) ≤ 1 e cosh(t) ≥ 1, si ha che
Ck(t) ≤ 1 |t| ≤ 1
Ck(t) ≥ 1 |t| ≥ 1
in particolare per |t| ≥ 1 il polinomio Ck(t) cresce tanto velocemente quanto
cresce la funzione cosh.
Per questa espressione si può trovare un'approssimazione valida quando k → ∞, infatti ponendo t = cosh θ si ha
Ck(t) = cosh(kθ) = e kθ+ e−kθ 2 = 1 2[(sinh θ + cosh θ) k+ (sinh θ + cosh θ)−k] = 1 2 t +pt2− 1k+(t +pt2− 1−k
da cui, per grandi k, si può avere Ck(t) ≈
1 2
t +pt2− 1k per t > 1 (55)
Adesso, sia Pk l'insieme dei polinomi di grado ≤ k.
Vale il seguente teorema di fondamentale importanza per alcuni risultati di approssimazione:
Teorema 19.6. Sia [α, β] un intervallo non vuoto di R e sia γ ≥ β un punto tale che p(γ) = 1 per un polinomio p ∈ Pk. Allora il minimo
min
p∈Pk
max
t∈[α,β]|p(t)|
è raggiunto dal polinomio ˆCk de nito sull'intervallo [α, β], tale che ˆCk(γ) = 1
ˆ Ck(t) = Ck 1 + 2t − β β − α Ck 1 + 2γ − β β − α
Dimostrazione. Vedere [10], pagina 109.
Osservazione 19.2. Siccome Ck(t) ≤ 1 per t ∈ [−1, 1], allora
min p∈Pk max t∈[α,β]|p(t)| = 1 Ck 1 + 2γ − β β − α (56)
19.5.2 Convergenza degli autovalori
Iniziando col caso dell'autovalore dominante λ1 di A.
Teorema 19.7. Sia A ∈ Cn×n hermitiana con autovalori λ
1 ≥ λ2≥ · · · ≥ λn
e corrispondenti autovettori u1, . . . , un.
Per l'autovalore dominante ˜λ1 di Hm, ottenuto dopo m passi del Metodo di
Lanczos sul sottospazio Km:= Km(a, v), vale la limitazione
λ1≥ ˜λ1≥ λ1− (λ1− λn) 1 Cm−1(1 + 2γ1) 2 tan2(u1, v) dove γ1= λ1− λ2 λ2− λn
è misura la separazione tra i primi due autovalori rispetto a tutti i successivi. Dimostrazione. La limitazione dall'alto discende dal Teorema (18.2), per cui
˜ λ1≤ λ1
La limitazione dal basso invece si basa sulla Proposizione (19.1): ogni vettore ˜
u ∈ Km(A, v)è esprimibile come
˜
u = p(A)v
dove p ha grado al più m−1. Si inizia considerando che per l'Osservazione (46), per y ∈ Cmsi ha la seguente caratterizzazione dell'autovalore massimale:
˜ λ1 = max y6=0 hHmy, yi hy, yi = max y6=0 hA(Qmy), Qmyi hQmy, Qmyi = max ˜ u∈Km\{0} hA˜u, ˜ui h˜u, ˜ui = max p∈Pm−1 hAp(A)v, p(A)vi hp(A)v, p(A)vi
Essendo A hermitiana esiste una base di autovettori ortonormali. Supponendo che questa sia composta proprio da u1, . . . , un. Allora
per certi coe cienti di= hui, vi. Allora si può decomporre l'espressione per ˜λ1 appena rinvenuta: ˜ λ1 ≥ hAp(A)v, p(A)vi hp(A)v, p(A)vi = Pn i=1d 2 ip(λi)2λi Pn i=1d 2 ip(λi)2 (∗) ≥ λ1d 2 1p(λ1)2+ λnδ d2 1p(λ1)2+ δ (#) = λ1− (λ1− λn)δ d2 1p(λ1)2+ δ
dove al punto (∗) è stato posto δ =
n
X
i=2
d2ip(λi)2 e al punto (#) si raccoglie
aggiungendo λ1δ − λ1δal numeratore.
Adesso resta da trovare una buona approssimazione per il polinomio p. Guar- dando l'ultima espressione trovata si vede che se fosse p(λ1) δallora sarebbe
˜
λ1 ≥ λ1+ O(1), quindi il limite dal basso per l'approssimazione risulterebbe
stringente a meno di una costante. Si può ottenere questo eetto approssiman- do p con un polinomio di Chebyshev Cm−1applicato sull'intervallo [λn, λ2]con
Cm−1(λ1) = 1. Scegliendo quindi p(t) = Cm−1 1 + 2 t − λ2 λ2− λn
si ottiene che p(λi) ≤ 1per λi∈ [λn, λ2]e quindi la maggiorazione per δ
δ ≤
n
X
i=2
d2i = 1 − d21
e inoltre p(λ1) ≥ 1, che de nendo γ1=λλ1−λ2
2−λn assume la forma
p(λ1) = Cm−1(1 + 2γ1)
Allora riprendendo la derivazione della maggiorazione per ˜λ1:
˜ λ1 ≥ λ1− (λ1− λn)δ d2 1p(λ1)2+ δ ≥ λ1− (λ1− λn) d2 1p(λ1)2 (1 − d21) = λ1− (λ1− λn) 1 Cm−1(1 + 2γ1)2 1 − d2 1 d2 1 = λ1− (λ1− λn) 1 Cm−1(1 + 2γ1)2 tan(u1, v)2
L'uso dei polinomi di Chebyshev nel Teorema (19.7) per limitare ˜λ1consiste
nel considerare l'espressione del generico elemento di un sottospazio di Krylov x = p(A)v e, ponendo p(t) = Cm−1(1 + 2γ1), ampli care la componente di
p(A)vnella direzione dell'autovettore u1. Un'idea simile si può sviluppare nel
prossimo Teorema (19.8) per dare una limitazione all'i-esima approssimazione ˜
λi:
Teorema 19.8. Sia (λi, ui) un'autocoppia esatta e ˜λi il corrispondente valore
di Ritz approssimato col Metodo di Lanczos. Allora vale la limitazione: 0 ≤ λi− ˜λi≤ (λ1− λn) κ˜ i Cm−i(1 + 2γi) 2 tan2θ(ui, v) dove ˜ κi def = 1 i = 1 Qi−1 j=1 ˜ λj− λn ˜ λj− λi i > 1γi= λi− λi+1 λi+1− λn
Dimostrazione. Vedere Teorema 6.4 di [10].
Confrontando il Teorema (19.7) col Teorema (19.8) se ne deduce che: • Si ha la migliore approssimazione per l'autovalore dominante λ1 di A.
Infatti in primo luogo vale ˜κi ≥ 1, mentre nel Teorema (19.7) al nu-
meratore si ha costantemente 1. Ma soprattutto il polinomio Cm−i(1 +
2γi) è di grado via-via decrescente al crescere di i, come si vede usando
l'approssimazione dell'Equazione (55) Cm−i(1 + 2γi) ≈ 1 2 1 + 2γi+ p (1 + 2γi)2− 1 ,m−i
ma ciò implica una maggiora inaccuratezza della stessa per i > 1 rispetto alla bontà della stima per i = 1.
• Al ne che λ1 sia ben approssimato però è importante anche che λ1 sia
ben separato da λ2. Infatti Cm−1(1 + 2γ1) è direttamente proporzionale
a γ1che sua volta è di valore direttamente proporzionale (solamente) alla
dierenza λ1− λ2: se questa è grande, allora Cm−1(1 + 2γ1)assume valori
maggiori e quindi la limitazione dal basso per ˜λ1 risulterà più stringente.
19.5.3 Convergenza degli autovettori
Sia (λi, ui)un'autocoppia di A e ˜uiil corrispondente vettore di Ritz. Come visto
per il metodo generale di proiezione, per dare una garanzia di qualità a questa approssimazione, serve valutare l'angolo θ(ui, ˜ui)compreso tra l'autovettore e
la sua stima.
Per arrivare a poter dare una limitazione a questa quantità però, serve prima dare una limitazione all'angolo tra ui e l'intero sottospazio di approssimazione
Lemma 19.1. Sia A ∈ Cn×nhermitiana e (λ
i, ui)una sua autocoppia, kuik = 1
e v ∈ Cn che dia origine al sottospazio K
m(A, v).
Se hui, vi 6= 0per ogni i = 1, . . . , n allora
tan θ(ui, Km) = min p∈Pm−1
p(λi)=1
kp(A)yik tan θ(ui, v)
dove yi def = v − uihui, vi kv − uihui, vi k2 v − uihui, vi 6= 0 0 altrimenti Dimostrazione. Vedere [10], Lemma 6.1.
Quest'ultimo Lemma conduce alla dimostrazione del Teorema fondamentale: Teorema 19.9. Sia (λi, ui)un'autocoppia di A, kuik = 1e v ∈ Cn dia origine
al sottospazio Km:= Km(A, v).
Se hui, vi 6= 0per ogni i = 1, . . . , n allora
tan θ(ui, Km) ≤ κi Cm−i(1 + 2γi) tan θ(ui, v) dove κi def = 1 i = 1 Qi−1 j=1 λj− λn λj− λi i > 1γi def = λi− λi+1 λi+1− λn
Dimostrazione. Iniziando dal caso i = 1. Sia y1 ∈ span{u1}⊥, come de nito
nel Lemma (19.1). Poichè la matrice A è per ipotesi hermitiana, il sottospazio ortogonale a u1 è generato da n − 1 autovettori linearmente indipendenti e
ortonormali a u2, . . . , un. Si ha quindi y1= n X j=2 αjuj con Pn
j=2|αj|2 = 1 dal momento che y1 ha norma euclidea unitaria. In que-
st'ultima relazione si introduce p(A), ottenendo p(A)y1=
n
X
j=2
p(λj)αjuj
e passando ai quadrati delle norme kp(A)y1k22 = n X j=2 |p(λj)αj|2 ≤ max j=2,...,n|p(λj)| 2 ≤ max λ∈[λn,λ2] |p(λ)|2
Ancora una volta applicando Lemma (19.1), si ottiene una maggiorazione per l'angolo tra il sottospazio e l'autovettore
tan θ(ui,Km) ≤ min p∈Pm−1
p(λi)=1
max
λ∈[λn,λ2]
|p(λ)| tan θ(ui, v)
a cui basta applicare l'Equazione (56).
Per il caso generico i 6= 1 ci si può restringere ai polinomi della forma p(λ) = i−1 Y j=1 λj− λ λj− λi q(λ)
con q polinomio di grado k − i tale che q(λi) = 1. Procedendo come nel caso
precedente, si ottiene kp(A)yik2 ≤ max λ∈[λn,λi+1] i−1 Y j=1 λj− λ λj− λi q(λ) ≤ i−1 Y j=1 λj− λn λj− λi max λ∈[λn,λi+1] |q(λ)|
a cui si applica sempre l'Equazione (56) per giungere alla tesi.
Tornando al problema principale di dare una limitazione all'angolo θ(u, ˜u). Nel contesto della Procedura di Rayleigh-Ritz è stato enunciato il Teorema (18.3) atto a limitare il seno di quest'angolo mediante il seno tra l'autovettore e l'intero spazio di approssimazione. Quando si tratta del Metodo di Lanczos invece, il Teorema (19.9) permette di trovare una diversa maggiorazione più speci ca:
Teorema 19.10. Sia (λi, ui) un'autocoppia di A e (˜λi, ˜ui) la corrispondente
approssimazione. Allora l'approssimazione ˜ui trovata dal Metodo di Lanczos e
l'autovettore ui soddisfano la disuguaglianza
sin θ(ui, ˜ui) ≤ κi Cm−i(1 + 2γi) s 1 + β 2 m+1 δ2 2 tan θ(ui, v)
dove δ2 è la distanza sub-minimale del Teorema (18.3) tra λi e la seconda
approssimazione più vicina ad esso.
Dimostrazione. Prima di tutto, grazie alla ricorrenza propria del Metodo di Lanczos dell'Equazione (54), si può trovare la forma speci ca che assume φ in questo caso: φ = kQmQHmA(I − QmQHm)k2 = k(I − QmQHm)AQmQHmk2 = k(I − QmQHm)(QmHm+ βm+1qm+1eHm)Q H mk2 = kβm+1qm+1qmHk2 = βm+1
Allora per ottenere la maggiorazione su sin θ(ui, ˜ui) si può sostituire quanto
trovato all'interno della tesi del Teorema (18.3): sin θ(ui, ˜ui) ≤ s 1 +β 2 m+1 δ2 2 sin θ(ui, Km) ≤ s 1 +β 2 m+1 δ2 2 tan θ(ui, Km) ≤ s 1 +β 2 m+1 δ2 2 κi Cm−i(1 + 2γi) tan θ(ui, v)
dove le costanti κi e γi sono quelle de nite nel Teorema (19.9).
Per trarre delle conclusioni su quando si abbiano le migliori stime per gli autovettori serve guardare alla frazione
κi
Cm−i(1 + 2γi)
del Teorema (19.10), dove in κisi danno per noti gli autovalori della matrice in
questione. Le approssimazioni migliori si trovano quindi per due casi:
• Per l'autovettore massimale u1. Il numeratore infatti è minimo quando
i = 1, perchè vale
κi≥ 1
come si vede impostando la disuguaglianza: essa si riduce a λn ≤ λi,
vero per ipotesi. E in particolare l'uguaglianza è vera quando κ1= κn =
1. Inoltre, riprendendo quanto detto per Cm−i nel caso degli autovalori,
questi polinomi risultano di qualità sempre peggiore tanto più i è grande. • Per gli autovettori ui corrispondenti ad autovalori λi ben separati. Per
minimizzare la frazione in questione, serve avere un piccolo numeratore e un grande denominatore. Il numeratore κi è tanto più piccolo quanto
più l'autovalore λi è ben separato da quelli maggiori, come si vede dai
denominatori della produttoria che lo de nisce κi∝
1 λj− λi
j < i
Mentre il denominatore Cm−i(1 + 2γi)è direttamente proporzionale a γi,
ma questa quantità è tanto maggiore quanto più λi è ben separato dagli
autovalori minori di esso
γi∝ (λi− λj) j > i
infatti si studia la variazione di γiuna volta ssato l'insieme di autovalori
[λn, λ1] in questione: quindi la dierenza λ1− λn è ssata una volta per
tutte. Allora γi è tanto maggiore quanto più il numeratore λi − λi+1
è maggiore e al contempo il denominatore λi+1 − λn è minore, ovvero
tanto più il sottointervallo [λn, λi+1]si compatta verso λn (che è ssato),
20 Il metodo LanczosSK
Adesso è il momento di prestare il Metodo di Lanczos alla soluzione del Problema (1.3) del Bilanciamento. Riassumendo questo visto, si ha che la matrice A ∈ Rn×n risulta scalabile se e solamente se l'operatore di Menon T associata ad Aammette almeno un punto sso u ∈ P+, ovvero se e solo se A è a supporto
totale. Studiando la dinamica di T nel punto sso mediante la sua jacobiana JT(u) in esso calcolata, se ne ricava un problema equivalente: la matrice A è
scalabile se e solamente se u è autovettore relativo all'autovalore λ = 1 per JT(u). In particolare interessa il caso in cui A sia scalabile in modo unico
(a meno di costanti moltiplicative), ovvero esista un unico punto sso per T , ovvero un unico autovettore per JT(u): a nchè questo avvenga è su ciente che
Asia irriducibile con diagonale principale positiva; se questo è vero allora esiste un unico u ∈ P+ tale che S = D(UAu)AD(u) è lo scaling di A. Questo caso
corrisponde all'essere u autovettore relativo all'autovalore dominante di JT(u).
I Metodi (28), (30) e (31) sono iterazioni composte da un unico ciclo che convergono ad u sotto opportune ipotesi.
Il Metodo (32) detto SK∞ invece introduce un'iterazione con due cicli an-
nidati, ovvero di tipo inner-outer, la cui iterazione interna risolve il problema descritto nell'Equazione (33) mediante il Metodo delle Potenze, ossia sceglie co- me vettore u(k+1)l'autovettore di J
T(u(k))relativo al suo autovalore dominante
ρ(JT(u(k))) ≥ 1. Infatti se A è irriducibile con diagonale positiva, allora an-
che JT(u(k)) lo viene ad essere e quindi il suo raggio spettrale risulta essere il
suo autovalore dominante. Idealmente la successione degli autovettori dominan- ti {u(k+1)}
k≥0 converge all'autovettore dominante u di JT(u), rappresentando
così la soluzione al Problema (1.3).
Lo scopo di questa sezione è de nire un Metodo LanczosSK che sfrutti il Metodo di Lanczos, piuttosto che il Metodo delle Potenze, al questo ne di calcolare ciascun u(k+1).
Inoltre, verrà provato come il Metodo di Lanczos possa risultare più robusto e veloce rispetto al Metodo di Sinkhorn-Knopp su due particolari tipi di matrici: una matrice in forma di Hessenberg superiore, ovvero una matrice per struttura vicina a non avere supporto e una matrice quasi-decomponibile nel senso della De nizione (4.3). Al ne di questi esperimenti verrà sperimentato come criterio di arresto non tanto il rinvenimento del punto sso, ma piuttosto verrà messa alla prova la monotonia della successione {ρ(JT(u(k))}k≥0.
20.1 Il metodo su GG
TIl metodo descritto nell'Algoritmo (5) può essere concettualizzato come una funzione
v0= Lanczos(X, v, m) dove v0∈ P
+è l'autovettore dominante di X ∈ Rn×n, v ∈ P+è il vettore iniziale
su cui costruire il sottospazio di Krylov Km(A, v) e m appunto è il numero
massimo di iterazioni previste, cioè la dimensione massima del sottospazio. Ai ni dell'e cienza del calcolo è cruciale che sia m < n.
Condizione necessaria al metodo visto però è che X sia simmetrica. Il metodo andrà applicata sulla matrice JT(u(k)), che non è simmetrica in generale se A
non è simmetrica. Ma questo non è un problema, infatti dal Teorema (5.2) si sa che per ogni x ∈ P+
JT(x) = D(T x) · GGT · D(T x)−1 (57)
dove G := G(x) = D(T x)·AT·D(U Ax), quindi che J
T(x)ha gli stessi autovalori
di GGT ed in più è simmetrica:
Proposizione 20.1. La matrice C = GGT è simmetrica.
Dimostrazione. Applicando la de nizione:
CT = (GGT)T = (GT)TGT = GGT = C
Osservazione 20.1. Analogamente la matrice STS, simile a J
T(u), è simme-
trica.
Anche se le due matrici risultano simili, hanno in generale diversi autovettori associato allo stesso autovalore:
Proposizione 20.2. Sia x ∈ P+. Se (λ, v) è un'autocoppia di GGT allora
(λ, D(T x) · v)è un'autocoppia di JT(x).
Dimostrazione. Post-moltiplicando D(T x) nell'Equazione (57) si ha che JT(x) ·
D(T x) = D(T x)·GGT. Per ipotesi GGTv = λv, quindi applicando i due membri
sull'autovettore v si ottiene che
JT(x) · D(T x)v = D(T x) · GGTv
= λD(T x)v quindi D(T x)v è autovettore di JT(x).
Adesso è possibile de nire il metodo su GGT:
De nizione 20.1. Sia u(k) l'approssimazione corrente dell'autovettore domi-
nante di JT(u). Il Metodo LanczosSK consiste nell'applicazione ripetuta del
Metodo di Lanczos sulla matrice simmetrica GGT, simile a J
T(u(k)), prendendo
come nuova approssimazione u(k+1) l'autovettore dominante di GGT.
u(0)∈ P+ v = Lanczos(GGT, u(k), m) y = D(T x)v u(k+1)= y k ≥ 0 (58) Come nel caso del Metodo SKK∞, anche in questo caso però non c'è ga-
ranzia teorica che il metodo converga verso l'autovettore dominante di JT(u),
Congettura 20.1. Per k ≥ 0 il Metodo (58) produce una successione di auto- vettori {u(k)} e una successioni di autovalori {ρ(J
T(u(k)))}convergenti rispet-
tivamente all'autovettore dominante di JT(u) e all'autovalore 1 = ρ(JT(u)):
ρ(JT(u(k))) ↓ 1 u(k)→ u
In linea alla Congettura (20.1) come criterio di arresto verrà usata la mono- tonia della successione {ρ(JT(u(k)))}k≥0verso 1, supponendo che sia monotona
decrescente
ρ(JT(u(k−1))) > ρ(JT(u(k))) k ≥ 0
quindi si può implementare un algoritmo che realizzi il Metodo (58) bloccando la ricerca dell'autovettore dominante u quando la sequenza di autovalori dovesse iniziare a crescere o dovesse eettivamente risultare uguale a 1.
20.2 Autovalori di J
T(u)
clusterizzati
Sia A ≥ 0 la matrice da riscalare e sia S = D(UAu)AD(u) il suo scaling per un punto sso u di T , allora S ha n valori singolari, che si possono supporre ordinati
σ1≥ σ2≥ · · · ≥ σn
Sotto la consueta ipotesi vale un caso particolare:
Proposizione 20.3. Se A è irriducibile con diagonale principale positiva, allora σ1= 1 è dominante per S
1 > σ2≥ · · · ≥ σn
Dimostrazione. Se A è irriducibile con diagonale principale positiva, allora λ1=
1di JT(u)è dominante, ma λ1e σ1 sono legati dall'Osservazione (5.1) e quindi
anche σ1 è dominante per S.
Come si vede dal Teorema (9.2), il Metodo di Sinkhorn-Knopp espresso dal- l'Equazione (16) converge ad una velocità proporzionale a σ2
2, ovvero al secondo
più grande autovalore λ2 di JT(u)per l'Osservazione (5.1). Quindi ai ni del-
la velocità di convergenza, intesa come numero di iterazioni, è importante che valga
σ1 σ2
cioè λ2 λ1= 1. Infatti vale lo stesso principio del Metodo delle Potenze su
JT(u)vale lo stesso ragionamento: è importante che l'autovalore dominante sia
ben separato dal secondo, a nchè si abbia una convergenza veloce.
Nel Metodo di Lanczos, applicato sulla matrice X, la separazione è ugual- mente importante, ma da quanto visto in cia anche la bontà dell'approssima- zione del Metodo: se λ1(X) ≈ λ2(X) il limite dal basso nel Teorema (19.7) si
fa più lasco e quindi l'approssimazione ˜λ1 ottenuta diviene meno a dabile. In
[11] vengono derivate delle stime che esplicitano pure la dipendenza del numero di iterazioni del Metodo di Lanzos, dalla dierenza ∆X= λ1(X) − λ2(X):
Niter(Lanczos)= O 1 √ ∆X log1
Nel Metodo LanczosSK dell'Equazione (58) il Metodo di Lanczos viene ap- plicato sulla matrice GGT, simile a J
T(u(k)). Quindi ciò che importa è la se-
parazione dell'autovalore dominante λ1(JT(u(k))) = ρ(JT(u(k))) ≥ 1dal secon-
do autovalore dominante. Supponendo vera la Congettura (20.1) allora vale il seguente legame tra autovalori dominanti e valori singolari dominanti
σ1(G) = q λ1(GGT) = q λ1(JT(u(k))) hp −→pλ1(JT(u)) = q λ1(STS) = σ1(S)
in particolare che pλ1(GGT) → σ1(S)per iterazioni k crescenti nel ciclo esterno
di LanczosSK. Siccome tutti gli autovalori {λ1(JT(u(k)))}k≥0 sono dominanti,
allora deve valere la stessa relazione per tutti gli autovalori e i valori subdomi- nanti, per cui vale anche pλ2(GGT) → σ2(S). Di conseguenza se la Congettura
(20.1) è vera, allora una buona separazione dei valori singolari di S è importante anche per la bontà delle approssimazioni del Metodo di Lanczos su GGT.
Nel caso generale non solo questa buona separazione può non avvenire, ma ci possono essere più di due autovalori simili tra loro. Se è questa la situazione, si parla di cluster dominante per gli autovalori per JT(u)o analogamente per i
valori singolari di S. In letteratura esistono diversi riferimenti ad un legame tra la numerosità di questo cluster e il numero di blocchi diagonali esistenti in S: Fatto 1. Se la matrice doppiamente stocastica S possiede K valori singolari su cientemente vicini a 1
1 ≈ σ2≈ · · · ≈ σK > σK+1≥ · · · ≥ σn
allora dalla matrice S emergono K blocchi lungo la diagonale principale dopo un opportuna permutazione simmetrica dei suoi elementi. Questo è espresso in [1, 2] o per quanto riguarda gli autovalori di S, quando questa in più è simmetrica, in [12].
Questo caso è sfavorevole a tutti i metodi presentati e il con ne tra 1 > σ2
e 1 ≈ σ2è talmente fumoso da non ottenere alcuna garanzia dalla solita ipotesi
di irriducibilità per A.
In una situazione simile, con un cluster dominante per S ovvero per JT(u),
di solito viene sfruttata la versione a blocchi di un algoritmo per il calcolo degli autovalori dominanti: piuttosto che calcolare il solo autovalore dominante λ1 mal-separato da λ2, è preferibile calcolare simultaneamente l'intero blocco
di autovalori {λ1, . . . , λK}. In questo modo, se fosse λK λK+1, allora si
andrebbe a sfruttare la buona separazione del cluster dei primi K autovalori rispetto ai successivi (o al solo cluster successivo), ottenendo in linea di massima risultati migliori e dalle proprietà analoghe al caso scalare qui descritto. Per un'esposizione del Metodo di Lanczos a blocchi riferirsi a [15].
21 LanczosSK vs SK
Vengono adesso riportati due casi esemplari in cui il Metodo LanczosSK del- l'Equazione (58) ha prestazioni migliori rispetto al Metodo SK in una delle sue versioni equivalenti; in particolare è stata implementato il Metodo (16).
Mentre il Metodo SK, nella sua semplicità, è stato implementato ex-novo esattamente col codice dell'Algoritmo (6), per realizzare il Metodo LanczosSK è stato fatto uso della funzione irbleigs implementata da Baglama et al, de- scritto in [13] e supportato da casi d'uso in [14]. Questa funzione realizza un Metodo di Lanczos a K blocchi con restart implicito, ovvero una versione ac- celerata che fa uso limitato della memoria nel corso delle iterazioni, che tiene di conto di tutte le accortezze necessarie a implementare realisticamente il Me- todo di Lanczos. Come tipico per un metodo di proiezione ortogonale, durante il calcolo sfrutta solamente moltiplicazioni matrice-vettore che coinvolgono A. Essendo applicato alla matrice simmetrice GGT, il codice di irbleigs prevede
il passaggio di un m- le esterno che implementi l'iterazione z = GGTy (dove
y, z sono blocchi n × K), dove la matrice GGT non è prodotta esplicitamente.
Infatti, considerando la sua forma esplicita:
GGT = D(T x) · AT · D(U Ax) · D(U Ax) · A · D(T x)
si può implementare in maniera e ciente GGTymediante sue applicazioni par-
ziali, calcolando y1 = D(T x)y, y2 = Ay1 e così via. Inoltre le matrici diago-
nali non vengono generate, ma implementate mediante gli operatori di molti- plicazione vettoriale per componenti. Tutto questo è più chiaro nell'Algoritmo (8).
In entrambi gli esperimenti che seguono sono stati ssati i due parametri: • τ = 2.220446049250313 · 10−16, la precisione di macchina, per l'iterazione
di SK e per l'iterazione interna di LanczosSK, ai ni dell'algoritmo irbleigs; • Come vettore iniziale per SK e LanczosSK rispettivamente un vettore
casuale 198 × 1 e un blocco casuale 198 × K.
e vengono eseguito in ambiente MATLAB R2018b, su un'architettura Intel(R) Core(TM) i5-7200U a 64 bit, con 8GB di RAM a disposizione.
21.1 Esperimento 1 - Una matrice di Hessemberg
Questo primo esempio usa una matrice arti ciale di ordine 256, così de nita
aij= 1 i < j 256 i = j 1 i = j + 1 0 altrimenti
ovvero in forma di Hessenberg superiore a predominanza diagonale stretta (tale che Pj6=iaij < aii). Questa matrice ha supporto totale per de nizione, nel
dettaglio è irriducibile con diagonale principale positiva, ma è vicina a non avere proprio supporto: infatti avendo molti 0 nella sua metà triangolare inferiore, basta eliminare pochissimi elementi nella parte alta delle prime due colonne per applicare il Teorema (4.1).
Algoritmo 6 Implementazione MATLAB del Metodo SK dell'Equazione (16) nella sua versione normalizzata.
function [u, errors] = sk(A,tau,maxit,gamma) [n,n] = size(A);
err = inf;
errors = zeros(maxit,1);
AFUN = @(w) A*w + gamma*sum(w); AFUNT = @(w) A'*w + gamma*sum(w); u = rand(n,1);
k = 1;
while(err > tau) && (k <= maxit)
v = 1./AFUNT(1./AFUN(u)); %v = T(u)
v = v/sum(v); err = norm(v - u); errors(k) = err; u = v;
k = k+1;
end end
Inoltre la versione doppiamente stocastica di questa matrice, come si vede in Figura (4), è caratterizzata da valori singolari tutti distinti tra loro, quindi formalmente soddisfa la condizione σ26= σ1= 1; ma tutti e 256 di valori molto
vicino tra loro: giacciono tutti nell'intervallo [1, 0.98]. In base a quanto detto riguardo al cluster dominante di valori singolari, il metodo SK dovrebbe avere una convergeza molto lenta e similmente il Metodo di Lanczos potrebbe avere problemi nel calcolo dello spettro di JT(u(k)), dal momento che
σ1≈ σ2 (59)
Un possibile rimedio a questo inconveniente è quindi calcolare gli autovalori di JT(u(k))a blocchi.
In questo esperimento è stata confrontata l'esecuzione del Metodo SK con diverse esecuzioni di LanczosSK al variare del numero di blocchi di autovalori calcolati. In Tabella (1) si nota come il tempo di esecuzione di SK su questa matrice sia molto alto, pur non producendo uno scaling perfetto. Considerando il Metodo LanczosSK al variare di K, come si vede dalla Figura (5), si ha sempre e comunque convergenza, ma il Metodo non si comporta bene quando viene evocato su K = 1, 2, 3, 4 blocchi; questo a riprova di quanto visto sulla dipendenza del Metodo di Lanczos dalla separazione degli autovalori di GGT.
Invece, appena si considera il calcolo combinato di molti autovalori, la situazione cambia drasticamente. In Figura (6) si nota un brusco miglioramento della qualità dello scaling delle colonne a partire da K = 8 blocchi, no ad arrivare a stabilizzarsi al livello ottimale dello scaling delle righe con K = 64. Infatti la matrice doppiamente stocastica prodotta ha norma 1. Tutto questo mantenendo
Algoritmo 7 Implementazione MATLAB del Metodo LanczosSK (a blocchi) dell'Equazione (58) nella sua versione normalizzata.
function [u, lambdas]=LanczosSK(A, tau, gamma, K) GGclosure.A = A;
GGclosure.gamma = gamma;
AFUN = @(w) A*w + gamma*sum(w); AFUNT = @(w) A'*w + gamma*sum(w); lambda = inf; lambda_old = lambda; lambdas = []; n = lenght(A); U0 = rand(n,K); u = U0(:,1); u = u/sum(u);
while(lambda <= lambda_old) d1 = 1./(AFUN(u)); %D(Tx) d2 = 1./AFUNT(d1); %D(UAx) GGclosure.d1 = d1; GGclosure.d2 = d2; OPTS.V0=U0; OPTS.sigma = 'LE'; OPTS.k = K; OPTS.blsz = K; OPTS.funpar = GGclosure; OPTS.tol=tau;
[V,D]=irbleigs('GGiteration', n, speye(n), OPTS); v = V(:,1); %autovettore dominante di GG^T