Vincoli su T

7.3 Applicabilità della teoria

7.3.1 Vincoli su T

L'operatore di Menon T è non-espansivo, ossia soddisfa l'ipotesi di base del Teorema di convergenza nel caso normalizzato, sulla base del Corollario (7.1); le cui richieste di monotonia e omogeneità di grado 1 per T sono a loro volta soddisfatte per la Proposizione (3.1) nell'ipotesi che A sia completamente indecomponibile, ovvero irriducibile con diagonale principale positiva.

7.3.2 Vincoli su A

Invece le applicazioni L1, L2, corrispondenti rispettivamente alle matrice A, AT,

devono essere continue, monotone, omogenee di grado 1 e soddisfare L(P+) ⊂

P+, dove P+= IntK1= IntK2.

La monotonia segue immediatamente dalla corrispondente denizione ma- triciale: Ax ≤ Ay per x ≤ y, come si vede analizzando una riga per volta della matrice: Aix = n X j=1 aijxj hp ≤ n X j=1 aijyj= Aiy

L'omogeneità di grado 1 segue dalla denizione di applicazione lineare. Riguardo alla continuità, ogni applicazione lineare associata ad una matrice è continua, come si dimostra:

Proposizione 7.3. Sia L : Rn

→ Rn _{l'applicazione lineare associata alla}

matrice A ∈ Rn×n_{. Allora L è continua su R}n_.

Dimostrazione. Preso un qualunque x ∈ Rn_{. L è continua in x se e solo se per}

ogni sequenza x(k) _{→ x} _{si ha L(x}(k)_{) → L(x)}_{. Presa una generica sequenza}

convergente x(k)_{, allora kx}(k)_{− xk → 0}_{per k → ∞.}

Sia adesso Ai l'i-esima riga di A. Per la disuguaglianza di Cauchy-Schwarz

si ha kAxk2₌ n X i=1 (ATi x)2≤ n X i=1 kAik2 ! kxk2_{= Zkxk}2 Supponendo x(k)_{= x + x} 0 si ha che kAx(k)− Axk ≤ Zkx(k)− xk

quindi se kx(k)_{− xk → 0}_{allora kAx}(k)_{− Axk → 0}_{, ovvero L(x}(k)_{) → L(x)}_.

Adesso la condizione più importante, che impone un vincolo preciso su A: Proposizione 7.4. Sia L : Rn _{→ R}n _{l'applicazione lineare associata alla ma-}

trice A ∈ Rn×n_{. Se A ≥ 0 è a diagonale principale positiva, allora L(P} +) ⊂

P+.

Dimostrazione. Infatti prendendo un x ∈ P+, ovvero tale che xi > 0 per ogni

i = 1, . . . , n. Siccome per ipotesi aij≥ 0e aii> 0, questo implica che [Ax]i> 0;

ovvero Ax ∈ P+.

Ma per l'esistenza e l'unicità del punto sso di T è già richiesto che A sia irriducibile a diagonale positiva, quindi anche questa ipotesi è vericata. 7.3.3 Iterazione normalizzata

Questo per quanto riguarda le ipotesi alla base del Teorema (7.5). Invece per il Teorema (7.4) la condizione cruciale che rimane da dimostrare riguarda la nitezza del diametro:

Proposizione 7.5. Sia L : Rn

→ Rn _{l'applicazione lineare associata alla}

matrice A. Allora ∆(L) < ∞ secondo la metrica di Hilbert.

Dimostrazione. Presi due vettori x, y ∈ Rn_{, in questo caso particolare la metrica}

di Hilbert si esprime in modo combinatorio: dH(p, q) = max

i,j log

piqj

qipj

E' possibile limitarsi a calcolare ∆(L) = sup{dH(Ax, Ay)} sui vettori di

norma unitaria contenuti in IntP = P+. Siano mi ed Mi rispettivamente il

minimo e massimo elemento sulla riga i-esima di A. Sfruttando che x è di norma unitaria: mi= mi n X j=1 xj≤ n X j=1 aijxj≤ Mi n X j=1 xj= Mi

ovvero mi ≤ [Ax]i ≤ Mi. In modo analogo si può provare mi ≤ [Ay]i ≤ Mi,

per kyk1 = 1. Quindi basta sostituire nell'espressione per dH rispettivamente

i massimi al numeratore e i minimi al denominatore, operando la sostituzione p := Axe q := Ay:

∆(L) = sup{dH(Ax, Ay) : x, y ∈ IntP}

= max{dH(Ax, Ay) : x, y ∈ P+, kxk1= 1, kyk1= 1}

≤ max

i,j log

MiMj

mimj

che è una quantità nita.

7.4 Teorema di convergenza

Per fare una semplice summa dei risultati ottenuti, alla luce delle condizioni in cui la teoria generale diviene applicabile per il Metodo (14) in una delle sue versioni, si può stabilire:

Teorema 7.6. Sia A ≥ 0. Se A è irriducibile con diagonale principale positiva (ovvero completamente indecomponibile) allora il Metodo di Sinkhorn-Knopp nelle forme descritte dalle Equazioni (14), (15), (16) o (17) converge global- mente all'unico punto sso u di T (a meno di multipli scalari). Ovvero per ogni u(0)_{∈ P}

+ esiste un λ > 0 tale che

lim

k→∞T (u

(k)_{) = λu}

Dimostrazione. Segue dal Teorema (7.5) a cui si aggiungono le condizioni su A imposte su T nella Proposizione (3.1), che ne garantiscono la non-espansività. Vale però la pena sottolineare che il Metodo può convergere anche sot- to ipotesi più generali. Per questo di nuovo tornano in gioco le matrici con supporto:

Teorema 7.7. Sia A ≥ 0.Il Metodo (14) converge ad un limite doppiamente stocastico se e solo se A ha supporto. Se ha anche supporto totale allora il limite è della forma S = D1AD2.

Quindi se A ha solamente supporto non totale, allora il Metodo (14), in una delle sue forme, può non convergere verso una matrice S ottenuta dal prodotto di A con due matrici diagonali D1, D2. Questo risultato è po' contro-intuitivo se

inteso entro la formulazione del Problema (1.3). Infatti si riferisce all'algoritmo come pensato originariament da Sinkhorn in [5]: partendo da una matrice A si costruisce una sequenza di matrici alternativamente scalate per righe (·)r o per

colonne (·)c:

A → Ar→ (Ar)c→ ((Ar)c)r→ · · ·

dove lo scaling per ogni riga i = 1, . . . , n prevede i due passaggi ri=

j=1

aij (A)r= D(r1, . . . , rn) · A

e analogamente per ogni colonna j = 1, . . . , n cj=

i=1

aij (A)c= A · D(c1, . . . , cn)

In questo senso esiste una matrice limite che risulta doppiamente stocastica, ottenuta riscalando successivamente righe e colonne per un certo numero di volte, determinando direttamente la matrice S doppiamente stocastica, piuttosto che due matrici diagonali D1, D2> 0 tali che S = D1AD2.

8 Il caso simmetrico

Quando A = AT _{si può ottenere una versione semplicata del Metodo di}

Sinkhorn-Knopp.

In questo caso il Sistema (5) si riduce al caso

c = D(Ar)−1e

r = D(Ac)−1_e (23)

in cui è evidente la simmetria tra le due equazioni. Si dimostra che in realtà le due equazioni ammettono la stessa soluzione, ovvero

r = c

infatti dal Teorema (3.2) si è visto che l'operatore di Menon ammette un unico punto sso u > 0, dal quale si ricavano i vettori r, c tali che S = D(r)AD(c) sia doppiamente stocastica. L'unicità del punto sso implica che se (r, c) e (r0_{, c}0₎

sono due soluzioni del problema del bilanciamento, allora devono essere una multiplo dell'altra, ovvero deve esistere un ξ > 0 tale che

r = ξr0 c = 1 ξc

Ma se (r, c) è una soluzione, allora per la simmetria del Sistema (23) anche (c, r) è una soluzione; in altre parole si pone r0 _{:= c}_{e c}0 _{:= r}_{. Perciò anchè le due}

soluzioni siano una multiplo dell'altra deve essere r = ξc c = 1 ξr Scegliendo c = √r ξ e r = √ ξcsi ottiene ξc = 1 ξr ⇐⇒ ξ r √ ξ = 1 ξ p ξc ⇐⇒ pξr =pξc ⇐⇒ r = c

Quindi si può sempre supporre r = c e dunque ridurre il problema del bilanciamento alla ricerca di un unico vettore u tale che S = D(u)AD(u) sia doppiamente stocastica, ovvero alla sola condizione

D(u)AD(u)e = e

In linea all'Equazione (5) si trova che questo equivale a cercare un vettore u tale che u = D(Au)−1_e_{da cui origina il caso particolare del Metodo di Sinkhorn-}

Knopp su matrice simmetrica:

u(k+1)= D−1(Au(k))e (24) corrispondente all'iterazione di punto sso semplicata u(k+1)_{= T}

S(u(k))dove

TS(x) = U Ax è l'operatore di Menon associato alla matrice A simmetrica. Di

conseguenza si specica il Teorema di esistenza e unicità della soluzione al caso simmetrico:

Corollario 8.1. del Teorema (2.1). A ≥ 0 è scalabile se e solo se ∃u ∈ P+ tale

che TS(u) = u. Nel qual caso A viene riscalata nella matrice S = D(u)AD(u).

9 Velocità di convergenza

Quando A è irriducibile con diagonale principale positiva (o completamente indecomponibile) il Metodo di Sinkhorn-Knopp, in ciascuna delle sue versioni, converge verso l'unico punto sso di l'operatore di Menon T associato ad A. Resta da determinare con quale velocità lo faccia. Per capirlo serve prima studiare il caso simmetrico e ricondurre ad esso il caso generale.

9.1 Il caso simmetrico

Considerando il Metodo di Sinkhorn-Knopp nel caso generale dell'Equazione (14) e nella versione alleggerita data dall'Equazione (24), si studiano le sequenze prodotte dai due algoritmi se applicati ad una matrice A simmetrica. Il Metodo (14) su una matrice A simmetrica si può ridurre all'iterazione

   r(0)∈ P+ c(k+1)_{= D}−1_(Ar(k)_{)e = U Ar}(k) r(k+1)_{= D}−1_(Ac(k+1)_{)e = U Ac}(k+1)

da confrontarsi con l'iterazione alleggerita u(h+1)_{= T} S(u(h)) = U Au(h). Si nota che: u(h)= ( r(k) _{h = 2k ≥ 0} c(k+1) h = 2k + 1 ≥ 1

infatti partendo dallo stesso vettore r(0)_{= u}(0)_{eapplicando la stessa matrice A}

simmetrica, alla prima iterazione si otterrà c(1) _{= x}(1)_{, r}(1) _{= u}(2)_{, c}(2) _{= u}(3)

e così via: a fronte di un continuo accrescersi di u(·)_{, le successioni r}(k)_{, c}(k)

aggiorneranno il proprio valore ogni 2 aggiornamenti di u(·)_.

Ma le due sottosequenze dei pari e dei dispari che formano la sequenza com- plessiva u(h) _{in generale hanno limiti diversi, quindi non è possibile studiare}

direttamente l'iterazione TS(z) per un qualche z ∈ P+, come fatto in prece-

denza e determinarne la velocità di convergenza: la sequenza non ammette limite. Una possibilità è concentrarsi su una delle due sottosequenze e studiare il comportamento asintotico di T2

S. Questo è coerente col fatto che, nel caso

simmetrico, la doppia composizione TS corrisponda proprio a T , infatti:

T (x) = U ATU Ax = U AU Ax = T_S2(x)

D'altra parte però l'Iterazione (24) converge ad unico punto sso u ∈ P+

per TS quando A è completamente indecomponibile. Ma unico si indende

sempre a meno di una costante moltiplicativa; si capisce bene dall'analogia con gli autovettori della jacobiana nel punto sso: ogni vettore multiplo di un autovettore è a sua volta autovettore, e tutti appartengono al solito autospazio

U def= {αu : TS(u) = u}

. Mettendo insieme questo punto al precedente, se ne trae che i due limiti delle sottosuccessioni {r(k)_} _{e {c}(k)_} _{debbano essere uno multiplo dell'altro:}

lim k→∞r (k) ∈ U 3 lim k→∞c (k)

Il prossimo passo è cercare di dimostrare che l'iterazione doppia T2

S tende ad

avvicinarsi a U e che lo fa in modo proporzionale all'autovalore subdominante di S:

Lemma 9.1. Sia A ≥ 0 simmetrica e completamente indecomponibile. Sia u punto sso di TS e µ2 secondo autovalore di modulo maggiore per S =

D(u)AD(u).

Se ˆx è tale che kˆx − αuk < per una qualche norma di Rn _{e un α > 0 allora}

min

v∈UkT 2

S(ˆx) − vk ≤ |µ2|2 + o()

Questo Lemma è di fondamentale importanza: stabilisce un risultato sulla velocità di convergenza nelle ipotesi in cui si ha eettivamente convergenza, come espresso dal Teorema (7.6). Quindi si può immediatamente enunciare il risultato sulla velocità di convergenza nel caso simmetrico:

Teorema 9.1. Sia A ≥ 0 simmetrica e completamente indecomponibile. Sia u punto sso di TS.

Per ogni > 0 esistono due successioni limitate {αk}, {d(k)} tali che deni-

tivamente

u(k)= αku + d(k)

con kd(k)_{k ≤} _{e questo avviene ad una velocità lineare governata dal secondo}

autovalore di modulo maggiore per S: kd(k+2)_{k ≤ |µ}

2|2kd(k)k + o(kd(k)k)

Nel precedente teorema la successione {d(k)_} _{esprime proprio la distanza}

dalla retta U, ovvero man mano che d(k) _{→ 0}_{sempre più u}(k) _{→ α}

ku ∈ U. E

questa distanza, come provato nel Lemma (9.1) si abbatte in modo proporzionale all'autovalore subdominante di S (ogni due iterazioni di TS).

9.2 Il caso generale

Si può arrivare ad enunciare un teorema sulla velocità di convergenza al caso generale, che sia molto simile al Teorema (9.1).

Prima di tutto serve notare che applicare il Metodo (14), in ciascuna delle sue versioni, sulla matrice A non-simmetrica in generale, equivale ad applicare il Metodo (24) sulla matrice

B = 0 A AT 0

che è simmetrica. Ma non completamente indecomponibile (è per denizione in una forma a blocchi, con alcuni blocchi nulli). Quindi questa equivalenza, per quanto interessante, non è utile allo scopo.

Il Teorema nel caso generale si basa invece sulla seguente osservazione: se A è completamente indecomponibile allora è scalabile e perciò per il Teorema (2.1) esistono due vettori r, c ∈ P+ tali che S = D(r)AD(c) sia doppiamente

stocastica. Ma allora il vettore (r, c)T _{di dimensione 2n permette di trovare uno}

scaling per B: Dr c 0 A AT ₀ Dr c = 0 D(r)AD(c) D(c)AT_D(r) ₀ = 0 S ST ₀ = Q

che è doppiamente stocastica per costruzione. Ma soprattutto, se A è completamente indecomponibile, allora SST _{è completamente indecomponibile. Questo}

permette non tanto di applicare il Teorema (9.1), ma piuttosto di studiare lo sprettro di Q, connesso coi valori singolari di S. Saltando alla conclusione e rimandando alla letteratura per la dimostrazione, si può enunciare il seguente risultato conclusivo:

Teorema 9.2. Sia A ≥ 0 completamente indecomponibile. Sia u punto sso di T.

Per ogni > 0 vale denitivamente ku(k+1)_{− uk ≤ σ}2

2ku(k)− uk + o() (25)

dove σ2 è il secondo più grande valore singolare di S = D(UAu)AD(u).

Dimostrazione. Vedere [6].

10 Dinamica nel punto sso

Nell'analisi della convergenza è stato trovato che la velocità del Metodo di Sinkhorn-Knopp dipende dal secondo valore singolare più grande σ2 della ma-

trice S = D(UAu)AD(u), dove u è il punto sso desiderato.

Dal Lemma (5.2) si ricava un'importanza osservazione: linearizzando attorno al punto sso u ∈ P+ si ha che in un intorno di u il comportamento di T viene

descritto dalla jacobiana calcolata in quel punto T (x) ≈ JT(u)x

arrivando a coincidere proprio con T quando x = u. Questo signica che la dinamica delle iterazioni di punto sso x = u(k)_{è determinata proprio da J}

T(u).

In questa sezione, nora l'esistenza del punto sso è stata vista dipendere da T e la sua velocità dal secondo valore singolare della matrice bilanciata S risultante. Nell'ottica invece del Problema (12), si può riassumere il comportamento dell'iterazione di punto sso in dipendenza dallo spettro di JT(u). La

schematizzazione è semplice ed elegante:

• λ1= 1determina l'esistenza del punto sso u ∈ P+ verso cui converge il

Metodo di Sinkhorn-Knopp, grazie al Teorema (5.1).

• λ2< 1determina la velocità con cui il Metodo converge al punto sso u

ku(k+1)_{− uk ≤ λ}

2ku(k)− uk + o()

In particolare la seconda aermazione deriva dal fatto che il Metodo converge nell'ipotesi che A sia irriducibile con diagonale principale positiva, condizione sotto la quale la Proposizione (6.1) decreta λ1 = 1 autovalore dominante di

JT(u)e quindi strettamente maggiore di λ2. In base all'Osservazione (5.1) vale

che

σ22(S) = λ2(JT(u))

Parte III

Il metodo delle Potenze

Se A ≥ 0 è irriducibile con diagonale principale positiva, allora per il Corollario (6.1) l'autocoppia (1, u) di JT(u)è dominante. Quindi introdurre la risoluzione

del Problema del Bilanciamento come ricerca di un autovettore (vedi Equazione (12)) e in particolare dell'autovettore associato all'autovalore dominante, permette di avvicinarsi gradualmente dal Metodo di Sinkhorn-Knopp al Metodo delle Potenze.

Infatti l'iterazione T (u(k)_{) = J}

T(u(k))u(k) del Metodo (17) assomiglia ad un

passo della classica iterazione del Metodo delle Potenze. Per denizione quest'ultimo metodo consiste nella semplice moltiplicazione di una matrice ssata per approssimazioni successive dell'autovettore dominante, convergenti denitivamente a questo autovettore. Siccome la JT(u(k)) del Metodo (17) non è

ssata, ma dipende dall'iterazione precedente, non si può dire che il Metodo (17) sia il Metodo delle Potenze invocato sulla jacobiana di T .

Si può introdurre una vera e propria iterazione basata sul Metodo delle Potenze grazie al Lemma (5.2). Sulla sua base si può decretare che

T (u(k)) ≈ JT(u)u(k) (26)

per ogni iterazione u(k)_{∈ P}

+ sucientemente limitata in un intorno del punto

sso u.

Quest'ultimo è un primo passo concettuale. Lo scopo di questa sezione sarà però dimostrare come poter usare il Metodo delle Potenze per trovare il punto sso u di T , rilasciando l'ipotesi di conoscere JT(u).

Come noto la velocità di convergenza del Metodo delle Potenze dipende dalla separazione dei primi due autovalori dominanti della matrice su cui è applicato. Questo è compabile col fatto che la velocità del Metodo di Sinkhorn-Knopp dipenda da λ2 di JT(u). Infatti grazie all'Equazione (26) si può interpretare il

Metodo di Sinkhorn-Knopp come un Metodo delle Potenze applicato a JT(u).

Ma allora non è importante solamente il valore di λ2: conta molto anche la

separazione di λ2 da λ1= 1ai ni della velocità di convergenza del Metodo di

Sinkhorn-Knopp.

11 Il metodo generale

Sia una matrice A ∈ Cn×n _{il cui autovalore dominante sia ben separato, cioè}

|λ1| > |λ2| ≥ · · · ≥ |λn| (27)

e i cui autovettori B = {u1, . . . , un}formino una base (ossia A sia diagonalizza-

bile).

Se della matrice si vuole trovare l'autocoppia (λ1, u1)tale che Au1= λ1u1,

costruzione della sequenza    ku(0)_k 2= 1 u(k)= norm(Au(k−1)) k ≥ 0 λ(k)₌_u(k)_{, Au}(k)

Sia α1 il coeciente di u(0) relativo al vettore u1 di B nella scomposizione

u(0) = α1u1+ · · · + αnun. Allora la successione u(k) si può dimostrare essere

convergente all'autovettore dominante: per k → ∞ il vettore u(k) _{va a giacere}

lungo la stessa direzione dell'autovettore dominante u1, ma con modulo unitario:

Teorema 11.1. Sia A ∈ Cn×n _{una matrice soddisfacente le ipotesi iniziali. Se}

α16= 0 allora u(k)= sign(α1λk1) u1+ (k) ku1+ (k)k2 dove (k)_{→ 0}_{per k → ∞.} Dimostrazione. Vedere [3].

La convergenza inoltre avviene con una velocità che dipende dal rapporto tra i moduli dei primi due autovalori:

Teorema 11.2. Sia A ∈ Cn×n _{una matrice soddisfacente le ipotesi iniziali. Se}

α16= 0 allora esistono due costanti C, D > 0 tale che per k ≥ 0

k˜u(k)− u1k ≤ C λ2 λ1 k |λ(k)_{− λ} 1| ≤ D λ2 λ1 k dove ˜ u(k) def= u(k)kA k_u(0)_k α1λk1

permette di trasportare la stessa limitazione su x(k)_.

Dimostrazione. Vedere [3].

Siccome sarà importante confrontare il Metodo delle Potenze col Metodo di Lanczos, allora serve specializzare il risultato di convergenza verso l'autovalore dominante al caso di A hermitiana, visto che il Metodo di Lanczos è applicabile su questo genere di matrici. In particolare al caso di A reale e simmetrica, come sarà di interesse:

Teorema 11.3. Sia A ∈ Rn×n _{simmetrica soddisfacente le ipotesi iniziali. Se}

α16= 0 allora |λ(k)− λ1| ≤ |λ1− λn| λ2 λ1 2k tan2θ(u1, u(0)) Dimostrazione. Vedere [3].

Algoritmo 1 Metodo delle Potenze 1. Dato u0tale che ku0k = 1;

2. for k = 1, . . . do (a) y(k)_{= Au}(k−1)_; (b) u(k)_{= y}(k)_/ky(k)_k_; (c) λ(k)₌_u(k)_{, y}(k) ; (d) if(ky(k)_{− λ}(k)_u(k)_k 2< ) i. STOP;

Si procede nell'approssimazione dell'autocoppia dominante no a che kAu(k−1)_{− λ}(k)_u(k)_k

per una qualche soglia di tolleranza > 0, ovvero no a quando non esiste un K tale che non valga numericamente l'identità Au(K) _{= λ}(K)_u(K) _{e quindi}

(λ(K)_{, u}(K)₎ _{non sia l'approssimazione cercata. In alternativa si può sfrutta-}

re un criterio più preciso che sfrutta una stima della distanza tra l'autovalore dominante e la sua approssimazione:

|λ(k)_{− λ} 1| ≈ kAu(k−1)_{− λ}(K)_u(K)_k 2 w(k)_{, u}(k) <

dove w(k) _{è la stima dell'autovettore sinistro associato allo stesso autovalore}

dominante λ1.

Quindi il metodo delle Potenze si può scrivere come nell'Algoritmo (1).

12 Il metodo su J

(u)

Una prima idea quindi prevederebbe di denire un Metodo delle Potenze non normalizzato che ssa come matrice JT(u)una volta per tutte e lascia variare

invece solo il punto in cui si applica T :

u(0)_{∈ P} +

u(k+1)_{= J}

T(u)u(k) k ≥ 0 (28)

In linea di principio però è possibile accelerare la convergenza considerando piuttosto che T , il suo operatore composto

T` def = ( T ` = 1 T ◦ T`−1 ` > 1 (29)

L'operatore T` ha gli stessi punti ssi di T , ovvero vale T`(u) = u se e solo se

T (u) = u, infatti andando per induzione il caso base è vero per ipotesi; perciò assumendo l'ipotesi induttiva T`−1(u) = u ci si riconduce facilmente ad essa

visto che T`(u) = T (T`−1(u)). Dal momento che T`(u) = JT`(u)uallora anche

le jacobiane di T e T` hanno gli stessi autovettori. Di questo operatore si può

calcolare una linearizzazione come la precedente ottenendo T`(v) ≈ JT`(u)v ∀v ∈ P+\{u}

Ma attorno al punto sso u la composizione dell'operatore T per ` volte si trasforma nel prodotto della jacobiana JT(u) con se stessa per ` volte, infatti

vale:

Proposizione 12.1. Sia T` denito come nell'Equazione (29) e JT(u)la jaco-

biana di T nel punto sso. Allora

JT`(u) = J

` T(u)

Dimostrazione. Usando la notazione generale della derivazione, va dimostrato per induzione che (T`)0(u) = (T0(u))`.

Al caso base ` = 1 si ha T0_{(u) = T}0_(u)_.

Assumendo l'ipotesi induttiva (T`−1)0(u) = (T0(u))`−1, si dimostra la tesi

induttiva: (T`)0(u) = (T ◦ T`−1)0(u) = T0(T`−1(u)) · (T`−1)0(u) = T0(u) · (T`−1)0(u) hp = T0(u) · (T0(u))`−1 = (T0(u))` Siccome T0_{(u) = J}

T(u)allora vale la tesi.

Quindi, riprendendo la linearizzazione di T`si può dire adesso che

T`(v) ≈ JT`(u)v ∀v ∈ P+\{u}

e su questa base denire una seconda versione del Metodo delle Potenze che converge al punto sso u di T :

u(0)_{∈ P} + u(k+1)_{= J}` T(u)u(k) k ≥ 0 (30) Sia per quanto riguarda il Metodo (28) che il Metodo (30), sarebbe preferi- bile considerare la versione normalizzata, per ricadere nella teoria suddetta. Si introduce per esprimere questo un operatore di normalizzazione Rn _{→ B(0, 1)}

che rende più chiara l'esposizione dei metodi: norm(x)def= x

Perciò dai teoremi di convergenza del Metodo delle Potenze, ovvero i Teore- mi (11.1) e (11.2), si ha la garanzia che i Metodi (28) e (30) convergano al- l'autovettore dominante u di JT(u), che è lo stesso di JT`(u) come visto poco

sopra: u(k)→ u kuk2 k q k˜u(k)_{− uk → Cλ}` 2= σ2`2

dove λ2 è il secondo autovalore dominante di JT(u), visto che λ1 = 1è l'auto-

valore dominante di JT(u) per il Teorema (5.1). Essendo quindi λ2 < 1 si ha

convergenza. Sotto un'altra ottica la velocità di convergenza è determinata equi- valentemente dal secondo valore singolare λ2= σ22 < 1di S = D(UAu)AD(u),

per via dell'Equazione (5.1).

13 La variante SK

` Non avendo a disposizione la matrice J`

T(u)non è ovviamente possibile sfruttare

il Metodo (30), ma è possibile ipotizzare una sostituzione: usare J` T(u

(k)₎ _al

posto di J` T(u).

Il metodo ottenuto, detto SK`,è una semplice generalizzazione, normalizzata,

del Metodo (17): u(0)∈ P+ u(k+1)_{= norm(J}` T(u(k))u(k)) k ≥ 0 (31) Dato che la matrice di iterazione torna ad essere dipendente da u(k)_{, con}

questa modica non è più possibile appoggiarsi alla teoria del Metodo delle Potenze, per avere garanzie sulla convergenza del metodo verso l'autovettore udi JT(u), ovvero al punto sso di T . Però, sotto opportune ipotesi, si può

dimostrare che il Metodo (31) converge comunque al punto sso u di T , senza interessarsi di quale sia l'autocoppia dominante di J`

T(u (k)₎_:

Teorema 13.1. Sia u punto sso di T tale che kuk2= 1. Sia {u(k)}la sequenza

prodotta da SKK` per un qualche u(0)∈ P+. Se valgono le ipotesi

1) ∃η > 0 tale che J`

T(u(k)) = JT`(u)+Ek dove kEkk2≤ ησ22`k per k ≥ 0;

2) ∃γ > 0 tale che k Qm

k=0JT`(u(k))k2≥ γ per m ≥ 0

Allora il metodo converge al punto sso di T lim

k→∞u (k)_{= u}

e questo avviene con una velocità di convergenza dipendente da ` lim sup k→∞ k q ku(k)_{− uk} 2≤ λ`2= σ 2` 2

dove σ2 è il secondo valore singolare della matrice doppiamente stocastica S =

D(U Au)AD(u) del Teorema (2.1) e λ2 è il secondo autovalore dominante di

JT(u) per l'Osservazione (5.1).

14 La variante SK

∞

ovvero PowerSK

Considerando la successione di metodi SK1, SK2, . . . , SK` per ` → ∞. Per

ognuno di essi vale il Teorema (13.1), secondo il quale il limite sulla velocità di convergenza diventa sempre più stringente tanto più si sceglie ` grande, dal momento che σ2 < 1. Questa osservazione suggerisce di scegliere un ` il più

grande possibile, ai ni della qualità dell'approssimazione; possibilmente un ` illimitato.

Il metodo SK∞ si può quindi intuire prendendo l'iterazione (non norma-

lizzata) u(k+1) _{= J}`

T(u(k))u(k) del Metodo SK` e introducendo un'iterazione

secondaria che, una volta giunta a convergenza per ` → ∞, lasci a disposizione un valore che si può schematizzare come u(k+1)_{= J}∞

T (u(k))u(k).

Per calcolare questa inner iteration secondaria si può usare il Metodo delle Potenze su JT(u(k)), forti della Proposizione (6.1). Così facendo, presa l'appros-

simazione corrente u(k) _{del punto sso di T , l'iterazione nella matrice ssata}

JT(u(k))

v(`+1)= JT(u(k))v(`) ` ≥ 0

convergerà all'autovettore di JT(u(k))corrispondente all'autovalore dominante.

Operando per sostituzione, si può ottenere una forma chiusa per le prime ` iterazioni del metodo:

v(`)= J_T`(u(k))v(0)= J_T`(u(k))u(k) si avrà in v(∞) _{= J}∞

T (u(k))u(k) l'autovettore dominante di JT(u(k)), che può

essere scelta come nuova approssimazione u(k+1)_{per il punto sso di T .}

Denizione 14.1. Introducendo una normalizzazione intermedia, si denisce così il Metodo SK∞, detto anche PowerSK, per il calcolo del punto sso di T :

       u(0)∈ P+ v(0)_{= u}(k) v(`+1)_{= norm(J} T(u(k))v(`)) ` ≥ 0 u(k+1)_{= v}(∞) _{k ≥ 0} (32) Nell'ipotesi che la matrice A ≥ 0 sia irriducibile con diagonale principale positiva, la matrice di iterazione JT(u(k))ha in ρ(JT(u(k))) ≥ 1 il proprio au-

tovalore dominante, quindi il Metodo delle Potenze è lecitamente applicabile e converge all'autovettore corrispondente v(∞)_{, come garantito dai Teoremi (11.1)}

e (11.2). Ma se questo dà solide basi alla inner iteration, non si può dire altret- tanto sulla outer iteration; infatti la convergenza del Metodo (32) nel complesso non è stata dimostrata:

Congettura 14.1. Per k ≥ 0 il Metodo (32) produce una successione di autovalori e autovettori che, almeno concettualmente, dovrebbe convergere rispettivamente all'autovalore 1 e all'autovettore u di JT(u)

dove la convergenza dall'alto verso 1 è dovuta alla Proposizione (5.2), che fornisce 1 come valore minimo assunto da ρ(JT(u(k))).

Parte IV

I metodi di proiezione ortogonale

Nel documento Bilanciamento di matrici non-negative: teoria e metodi numerici (pagine 36-53)