CORSO DI LAUREA IN INFORMATICA
Bilanciamento di matrici non-negative
Teoria e metodi numerici
TESI DI LAUREA MAGISTRALE
6 Dicembre 2019
RELATORE
CANDIDATO
Prof. Luca Gemignani
Alessandro Conticelli
Indice
I Introduzione
4
1 Fondamenti 5
2 La soluzione come punto sso 6 3 Esistenza e unicità del punto sso 8
3.1 Proprietà di un generico operatore P∞→ P∞ . . . 9
3.2 Proprietà dell'operatore di Menon . . . 11
3.3 Teorema di esistenza e unicità . . . 13
4 Matrici scalabili 14 5 La soluzione come autovettore 17 5.1 Jacobiana di T . . . 17
5.2 Jacobiana in un punto x ∈ P+. . . 18
5.3 Jacobiana nel punto sso . . . 20
5.4 Il problema equivalente . . . 21
6 Dominanza dell'autovettore 21
II Il metodo di Sinkhorn-Knopp
23
7 Convergenza del metodo 24 7.1 Sull'espansività di T . . . 257.1.1 Il cono P . . . 25
7.1.2 Distanze e metriche . . . 27
7.1.3 Convergenza in norma . . . 27
7.1.4 Completezza delle metriche . . . 28
7.1.5 Condizioni di non-espansività . . . 29
7.1.6 Quanti care l'espansività . . . 30
7.2 Teoria della convergenza . . . 30
7.3 Applicabilità della teoria . . . 35
7.3.1 Vincoli su T . . . 35 7.3.2 Vincoli su A . . . 35 7.3.3 Iterazione normalizzata . . . 36 7.4 Teorema di convergenza . . . 37 8 Il caso simmetrico 38 9 Velocità di convergenza 39 9.1 Il caso simmetrico . . . 39 9.2 Il caso generale . . . 41
10 Dinamica nel punto sso 42
III Il metodo delle Potenze
43
11 Il metodo generale 43
12 Il metodo su JT(u) 45
13 La variante SK` 47
14 La variante SK∞ ovvero PowerSK 48
IV I metodi di proiezione ortogonale
50
15 Vettori ortogonali 50
16 Proiezioni 52
16.1 Proiezione su una retta . . . 52
16.2 Proiezione su un piano . . . 53
16.3 Proiezione su un sottospazio . . . 54
16.4 Proiettori . . . 55
17 Vettori ortonormali 57 17.1 Proiettare su una base ortonormale . . . 58
17.2 Costruire una base ortonormale . . . 58
18 Il metodo generale 60 18.1 Proiettare per approssimare . . . 61
18.2 La procedura di Rayleigh-Ritz . . . 61
18.3 Convergenza . . . 62
18.3.1 Approssimazioni esatte . . . 63
18.3.2 Risultati fondamentali per matrici hermitiane . . . 64
18.3.3 Maggiorare con la quantità ku − PW(u)k2 . . . 65
18.3.4 Convergenza degli autovettori . . . 66
18.3.5 Convergenza degli autovalori . . . 67
19 I metodi su sottospazi di Krylov 68 19.1 Approssimare su un sottospazio Km(A, v) . . . 68
19.2 Costruire una base ortonormale per Km(A, v) . . . 70
19.3 Il metodo di Arnoldi . . . 71
19.4 Il metodo di Lanczos . . . 75
19.5 Convergenza del Metodo di Lanczos . . . 76
19.5.1 Polinomi di Chebyshev . . . 77
19.5.2 Convergenza degli autovalori . . . 79
20 Il metodo LanczosSK 85 20.1 Il metodo su GGT . . . 85
20.2 Autovalori di JT(u)clusterizzati . . . 87
21 LanczosSK vs SK 88
21.1 Esperimento 1 - Una matrice di Hessemberg . . . 89 21.2 Esperimento 2 - Una matrice decomponibile . . . 92
V Conclusioni e sviluppi futuri
96
A Appendice. Il problema agli autovalori 102 A.1 Il caso non-negativo . . . 106
Parte I
Introduzione
Bilanciare una matrice A ad elementi non-negativi, quadrata di ordine n, si-gni ca trovare una seconda matrice S con la stessa struttura di A, ma che sia doppiamente stocastica. Ovvero la somma di tutti gli elementi su ciascuna riga e su ciascuna colonna, deve dare in entrambe i casi 1 come risultato.
Il problema qui viene posto nei termini della ricerca di una matrice doppia-mente stocastica della forma S = D1AD2, per due matrici diagonali D1, D2. Al
ne di trovare queste due matrici diagonali è possibile esplorare possibili solu-zioni a partire da due punti di vista distanti ma equivalenti, aventi in comune la costruzione di D1, D2a partire da un solo vettore u, a componenti strettamente
positive:
• u può esser visto come un punto sso per l'operatore T , una funzione non-lineare associata alla matrice A;
• uin alternativa può considerarsi un autovettore, relativo all'autovalore 1, della jacobiana di T in u.
Restringendosi ad una classe di matrici non-negative, in particolare quelle ir-riducibili con diagonale principale positiva, è possibile dimostrare l'esistenza e l'unicità di u (a meno di fattori moltiplicativi) o, equivalentemente, che u sia autovettore associato all'autovalore dominante della jacobiana di T .
Questa tesi vuole rappresentare un ex-cursus su alcuni degli approcci dispo-nibili in analisi numerica per arontare il problema. Il primo punto di vista dà luogo al Metodo classico di Sinkhorn-Knopp. Il secondo invece è di più moderna concezione e conduce alla trasformazione del problema del bilanciamento in un problema di calcolo dell'autovettore dominante.
Del Metodo di Sinkhorn-Knopp è illustrata la convergenza verso l'unico pun-to sso u di T , allegando uno studio sulla velocità di convergenza del mepun-todo stesso, dipendente dalle proprietà della matrice risultante S.
Ma il Metodo di Sinkhorn-Knopp può essere visto come un Metodo delle Potenze applicato alla jacobiana di T calcolata nel punto sso. Questo intro-duce ai metodi di calcolo di autovettori, in linea al secondo punto di vista. E conduce poi a diverse variazioni sul Metodo delle Potenze, culminando in ne ad un'iterazione di tipo inner-outer che applica una sequenza di problemi di calcolo dell'autovettore dominante di matrici, di recentissima de nizione, la cui conver-genza resta ancora da dimostrare teoricamente: si congettura che la sequenza di autovalori dominanti tenda a 1, di pari passo alla sequenza di autovettori dominanti che dovrebbe convergere a u.
Sempre con a nità al secondo punto di vista, è possibile sfruttare tutte le potenzialità dei metodi di proiezione ortogonale per accelerare la convergenza del metodo. Infatti il Metodo di Sinkhorn-Knopp e i metodi basati sul Metodo delle Potenze, risultano lenti se la matrice risultante S gode di una proprietà: avere almeno i primi due valori singolari massimali vicini tra loro. E' possibile
accelerare il calcolo dell'autovettore u applicando i metodi di proiezione orto-gonale, particolarmente e caci quando A è sparsa e di grandi dimensioni. In particolar modo in questo lavoro è stata messa alla prova una versione presente in letteratura del Metodo di Lanczos, nella sua variante a blocchi, che però non risulta limitato al caso di A simmetrica.
Il Metodo di Lanczos a blocchi, nell'implementazione denominata irbleigs, è stato testato con successo su due matrici potenzialmente di cili da trattare: una in forma di Hessenberg e una parzialmente decomponibile, sulle quali il Metodo di Sinkhorn-Knopp può eventualmente nemmeno convergere. Come criterio di convergenza del metodo non viene usato un test sul punto sso T (u(k)) =
u(k), ma cercando di confermare la congettura suddetta sulla convergenza della
procedura inner-outer, il criterio utilizzato è la monotonia della sequenza di autovalori dominanti prodotti. Come già visto in recenti lavori sull'argomento sul Metodo di Arnoldi, anche l'applicazione del Metodo di Lanczos può risultare e cace per il calcolo di u e quindi della matrice bilanciata S.
1 Fondamenti
De nizione 1.1. Una matrice A è non-negativa, ovvero A ≥ 0, se aij ≥ 0
per ogni i, j. Invece è detta positiva, cioè A > 0, se aij > 0 per ogni i, j.
Valgono le stesse de nizioni se al posto di una matrice si prende un vettore. Per comodità si introducono i seguenti insiemi, che raccolgono in loro i vettori non-negativi e positivi: • P = {x ∈ Rn|x ≥ 0} • P+= {x ∈ Rn|x > 0} • P∞= {x ∈ R n |x ≥ 0}
dove R = R ∪ {±∞}. Quindi si contemplano vettori con alcune componenti non nite. Allora è opportuno entendere l'aritmetica usuale su R ponendo: 1
0 = ∞, 1
∞ = 0, ∞ + ∞ = ∞, 0 · ∞ = 0 e se a > 0 allora a · ∞ = ∞. Inoltre sull'insieme
P∞, che include gli altri due, si de niscono le seguenti relazioni:
• x ≤ ydef≡ xi≤ yi ∀i = 1, . . . , n
• x < ydef≡ xi< yi ∀i = 1, . . . , n
• x ydef≡ x ≤ y ∧ x 6= y
Il problema del bilanciamento di matrici prevede di associare ad una matrice non-negativa A ∈ Rn×nuna matrice S ∈ Rn×nche sia doppiamente stocastica:
De nizione 1.2. Una matrice S è doppiamente stocastica se S ≥ 0 e soddisfa le condizioni
Se = e
dove e = (1, . . . , 1)T, cioè se gli elementi di ogni sua riga e di ogni sua colonna,
sommati assieme, danno 1.
Quindi il problema di bilanciamento consiste nella ricerca di una versione della matrice di partenza A che sia stata normalizzata per righe e per colonne. Un modo per evidenziare questo legame tra la matrice A di partenza e la matrice doppiamente stocastica di arrivo prevede l'introduzione di due matrici diagonali D1 e D2 che poste rispettivamente a pre-moltiplicare e post-moltiplicare A,
permettono la transizione da A ad S. Quindi il problema dello scaling si può de nire anche come la ricerca di due matrici diagonali D1, D2∈ Rn×n tali che
D1> 0e D2> 0per cui
S = D1AD2 (2)
sia una matrice doppiamente stocastica.
Ma una matrice diagonale è de nibile sulla base del vettore che ne compone la diagonale. Per far questo è utile introdurre l'operatore D : Rn
→ Rn×n
D(v) = diag(v1, . . . , vn)
e riformulare il problema di bilanciamento in un terzo e ultimo modo:
De nizione 1.3. Data A ≥ 0 di ordine n, il problema del bilanciamento o scaling consiste nel determinare l'esistenza di due vettori r, c ∈ P+ tali che la
matrice
S = D(r)AD(c) (3)
sia doppiamente stocastica. In caso aermativo, la matrice A è detta scalabile. Osservazione 1.1. Una prima osservazione da fare è che la struttura di A viene conservata in S, infatti per come è de nito il prodotto dell'Equazione (3), si ha che
sij = ricjaij
quindi in particolare la i-esima componente del vettore r ∈ P+ in uisce sulla
riga i-esima di A, mentre la j-esima di c ∈ P+ sulla colonna j-esima. Siccome
entrambe le componenti sono non nulle, allora sij = 0 se e solo se aij = 0.
2 La soluzione come punto sso
Lo scopo di questa sezione è dimostrare come sia possibile ricondurre la ricerca di una coppia di vettori (r, c) tali da risolvere il Problema (1.3), al rinvenimento del punto sso di un particolare operatore non-lineare.
Prima di tutto è necessario focalizzarsi su alcune proprietà elementari del-l'operatore D:
Proposizione 2.1. L'operatore D : Rn→ Rn×n gode di due proprietà:
1) Per ogni a ∈ Rn vale D(a) · e = a
2) Per ogni a, b ∈ Rn vale D(a) · b = D(b) · a
3) Per ogni p ∈ Rn vale D(p) · b = e se p
che si possono struttare immediatamente: mescolando le Equazioni (1) e (3), si ottiene che a nchè una coppia (r, c) sia soluzione del Problema, allora debbano soddisfare il Sistema
D(r)AD(c)e = e
D(c)ATD(r)e = e (4)
Applicando le proprietà 1) e 2) si trasformano le due identità nel modo seguente: D(r)AD(c)e = D(r)Ac
= D(Ac)r = e
D(c)ATD(r)e = D(c)ATr
= D(ATr)c
= e
adesso basta invertire le due matrici diagonali per ottenere il sistema mutua-mente ricorsivo:
c = D−1(ATr)e
r = D−1(Ac)e (5)
Nel nuovo sistema si ha un'operazione di inversione delle componenti vetto-riali. Si tratta di un'operazione non-lineare, che quindi si può incapsulare in un operatore ad hoc:
De nizione 2.1. Sia U : P∞ → P∞ tale che U(x)i = 1/xi, l'operatore che
esprime l'inversione delle componenti di un vettore, così de nito U (x) = D−1(x)e = (x−11 , . . . , x−1n )T
Per alleggerire la notazione, l'operatore U verrà spesso e volentieri usato senza parentesi:
U x := U (x)
a seconda della complessità del termine x, la valutazione di U procede sempre da destra a sinistra.
Osservazione 2.1. E' per la presenza di U che è necessario introdurre l'insieme P∞, infatti l'unico vincolo A ≥ 0 non esclude l'esistenza di una riga nulla in A,
per esempio la i-esima, di fronte alla quale risulta (Ax)i = 0 e U(Ax)i = ∞.
Se ogni riga di A possedesse almeno un elemento positivo (a patto che x non sia tutto nullo), allora sarebbe possibile restringersi a P+.
Questa notazione rendere più semplice la stesura del teorema fondamentale della sezione:
Teorema 2.1. Sia A ≥ 0. Si associ ad essa l'operatore T : P∞ → P∞ detto
operatore di Menon, così de nito:
T (x) = U ATU Ax
oppure T x := T (x). Allora A è scalabile se e solo se ∃u ∈ P+ punto sso di T ,
ovvero tale che
T (u) = u Perciò A è riscalata nella matrice
Dimostrazione. A è scalabile se e solo se esistono due vettori r, c ∈ P+ tali che
S = D(r)AD(c). Si dimostra che c debba essere punto sso di T e r = UAc. Infatti considerando il sistema dell'Equazione (5), sostituendo l'espressione per rin quella per c e generalizzando nella variabile u ∈ P+, i due vettori esistono
se e solo se
u = D−1(ATD−1(Au)e)e = D−1(ATU Au)e = U ATU Au = T (u)
ovvero se e solo se u è punto sso per T ed r scelto di conseguenza. Così necessa-riamente la matrice doppiamente stocastica è della forma S = D(UAu)AD(u). Tradurre il Sistema (5) in termini dell'operatore T rende così il Problema del Bilanciamento equivalente alla ricerca di un punto sso u di T a componenti tutte positive:
T (u) = u u ∈ P+ (6)
Resta da vedere ora quando T ammette punto sso. Siccome T dipende strettamente da A, questo accadrà per certe classi di matrici A non-negative.
3 Esistenza e unicità del punto sso
Quindi il problema di bilanciamento per A viene ricondotto al calcolo di un punto sso per T .
Come de nito dall'Equazione (6) è evidente che il punto sso possa esse-re visto anche come una sorta di autovettoesse-re associato all'autovaloesse-re λ = 1 dell'operatore T . Ma non essendo T stesso una matrice e nemmeno un ope-ratore lineare associato alla matrice A, è preferibile parlare di punto sso per T piuttosto che autovettore associato all'autovalore 1 di T , sebbene esista una forte analogia tra i due concetti. Infatti il principale teorema di questa sezione prevede di stabilire un risultato analogo al classico Teorema (A.7) di Perron-Frobenius in versione forte sul raggio spettrale di una matrice A ≥ 0, ma trasportato sull'operatore non-lineare T .
Similmente al caso lineare del Teorema (A.7), l'esistenza e l'unicità del punto sso per T sono dimostrate per una speci ca classe di matrici non-negative: De nizione 3.1. Una matrice A ≥ 0 è detta irriducibile se per ogni suo elemento aij≥ 0 esiste un esponente q(i, j) > 0 tale che [Aq]ij> 0.
Una sottoclasse di matrici irriducibili sono le matrici primitive, che è utile introdurre per de nire sulla loro base una versione ancora più forte del Teorema di Perron-Frobenius, qui citato come Teorema (A.8):
De nizione 3.2. Una matrice A ≥ 0 è detta primitiva se esiste un esponente p > 0tale che Ap > 0.
La versione non-lineare del Teorema di Perron-Frobenius, per matrici irridu-cibili ma non necessariamente primitive, riesce a garantire l'esistenza e soprat-tutto l'unicità di una soluzione per l'Equazione (6) e quindi permette di dare una versione più speci ca per il Teorema (2.1).
3.1 Proprietà di un generico operatore P
∞→ P
∞Per andare a dimostrare il suddetto Teorema, è necessario che l'operatore T soddis alcune proprietà fondamentali:
De nizione 3.3. Sia T : P∞→ P∞ un operatore:
1) T è monotono su P∞ se ∀x, y ∈ P∞ x ≤ y ⇒ T (x) ≤ T (y) 2) T è strettamente monotono su P+ se ∀x, y ∈ P+ x y ⇒ T (x) T (y) ∧ ∃m ∈ N+: Tm(x) < Tm(y) 3) T è omogeneo di grado k su P se ∀x ∈ P, ∀α ∈ R≥0 T (αx) = αkT (x)
dove il caso k = 1 copre la de nizione basilare di omogeneità per un'applicazione lineare.
4) T è continua su P∞ se
∀x ∈ P∞, ∀ > 0, ∃δ > 0 kx − yk ≤ δ ⇒ kT (x) − T (y)k ≤
La garanzia che T le soddis si ha quando è l'operatore associato ad una matrice A ≥ 0 irriducibile con diagonale principale positiva:
Proposizione 3.1. Sia A ≥ 0 di ordine n irriducibile con diagonale principale positiva. Sia T l'operatore di Menon ad essa associato. Allora valgono:
1) T è continua su P∞ (e quindi su P+); 2) T (P+) ⊆ P+; 3) T (P) ⊆ P; 4) T è omogeneo di grado 1 su P; 5) T è monotono su P∞; 6) T è strettamente monotono su P+. Dimostrazione. Vedere [2].
Osservazione 3.1. Queste proprietà sono garantire nell'ipotesi che A sia irri-ducibile con diagonale principale positiva. Sotto queste ipotesi la matrice A non ammette righe nulle e quindi, come accennato nell'Osservazione (2.1), cada la necessità di operare su P∞ (a patto di operari su vettori non tutti nulli). Da
ora in poi quindi si considererà un operatore di Menon della seguente forma: T : P → P
Un ulteriore operatore di fondamentale importanza per determinare l'auto-valore dominante dell'applicazione T di Menon è il seguente:
De nizione 3.4. Sia T : P → P. Sia x ∈ P\{0}, si de nisce Λ(x) = sup{λ | T (x) ≥ λx}
Restringendosi a x ∈ P+ si ha Λ(x) < ∞, infatti in questo caso per
l'o-peratore si può dare anche la seguente caratterizzazione in termini di minimo: Λ(x) = min T (x)i
xi
| xi> 0
(7) Dando un'interpretazione a Λ: ssato un vettore ¯x ≥ 0, la quantità Λ(¯x) de nisce il massimo scalare tale che T (¯x) > Λ(¯x)¯x oppure T (¯x) = Λ(¯x)¯x. Quin-di, quando Λ(¯x) esiste nito, Λ(¯x) è l'unico candidato ad essere autovalore dominante per T . A nchè lo sia ¯x deve essere autovettore per T .
Quindi per studiare l'insieme dei candidati ad essere autovettori, si de nisce un'ulteriore quantità:
De nizione 3.5. Sia T : P → P. Si de nisce ρ = sup{Λ(x) | x ∈ P\{0}}
per studiare come varia il Λ(x) stavolta al variare del vettore x ∈ P\{0}, escludendo appunto la soluzione banale x = 0.
Su P non ci sono garanzie che ρ < ∞, cioè che esista un vettore ¯x ∈ P tale che ρ = Λ(¯x) sia una quantità nita. Un vettore come ¯x è un candidato ad essere autovettore dominante per T . Ma prima di poter giungere a questo, serve avere garanzia della continuità di Λ:
Lemma 3.1. Sia T : P → P un operatore continuo. L'operatore Λ : P\{0} → R è semicontinuo superiormente.
Dimostrazione. Vedere [2].
Il prossimo Lemma inizia a dire qualcosa sulla nitezza di Λ, garantita per almeno un elemento di P\{0}:
Lemma 3.2. Sia T : P → P un operatore continuo, omogeneo su P e stretta-mente monotono su P+. Allora esiste u ∈ P\{0} tale che
ρ = Λ(u) per cui 0 < ρ < ∞.
Dimostrazione. Sia K = {x ∈ P\{0} : kxk1 = 1}. Poichè T è omogeneo su
P, vale ρ = sup{Λ(x) : x ∈ K} ed essendo K compatto e Λ semicontinua superiormente, Λ realizza il supremo su K e quindi esiste un vettore u ∈ K ⊂ P\{0}tale che ρ = Λ(u) e ρ < ∞.
Inoltre ρ > 0. Infatti sia x > 0, per ipotesi di stretta monotonicità esiste un m > 0 tale che Tmx > 0. Da cui T (Tm−1x) > λ(Tm−1x) per λ > 0
Adesso si può stabilire un primo risultato sugli autovalori di un operatore della famiglia di T :
Teorema 3.1. Sia T : P → P continuo, omogeneo su P e strettamente mono-tono su P+. Se esiste u ∈ P+ tale che ρ = Λ(u) allora questo è l'unico vettore
in P+ (a meno di multipli scalari) tale che
T (u) = ρu Dimostrazione. Vedere [2].
3.2 Proprietà dell'operatore di Menon
Andando nella direzione di avere ρ = 1 per l'operatore di Menon di una matrice A ≥ 0 irriducibile con diagonale positiva, il prossimo passo prevede di dare alcune limitazioni a Λ:
Lemma 3.3. Sia A ≥ 0 di ordine n irriducibile con diagonale positiva. Sia T l'operatore di Menon ad essa associato. Allora
Λ(x) ≤ 1 x ∈ P+ n − 1 n x ∈ P\{P+∪ 0}
dove la seconda disuguaglianza vale per vettori con almeno 1 elemento nullo, ma non più di n − 1.
Dimostrazione. Dimostrando la prima disuguaglianza:
Presi x ∈ P+ e y = UAx e costruite le corrispodenti matrici X = D(x) e
Y = D(y). Si vuole dimostrare che la matrice S = XAY è stocastica per righe, infatti per ogni i = 1, . . . , n vale
(Y AXe)i= (Y Ax)i= yi(Ax)i= (Ax)−1i (Ax)i= 1
quindi la somma di tutti i suoi elementi da esattamente n, ovvero n = n X i=1 n X j=1 yiaijxj (8)
Preso z = T (x) e la corrispondente matrice Z = D(z), si vuole dimostrare che Y AZ è stocastica per colonne, ovvero ZATY è stocastica per righe, infatti
per ogni i = 1, . . . , n vale
(ZATY e)i= (ZATy)i= zi(ATU Ax)i= (ATU Ax)−1i (A T
U Ax)i = 1
e ugualmente pure la somma di tutti gli elementi di Y AZ da n come risultato, ovvero n = n X i=1 n X j=1 yiaijzj (9)
Per ipotesi x ∈ P+, quindi si può applicare la caratterizzazione di Λ
dell'E-quazione (7) per componenti e ricavare che zj = T (x)j≥ xjΛ(x) j = 1, . . . , n
Quindi, riconsiderando le due Equazioni (8) e (9) e andando a sostituire: n = n X i=1 n X j=1 yiaijzj ≥ n X i=1 n X j=1 yiaijxjΛ(x) = nΛ(x) che implica Λ(x) ≤ 1. Per la dimostrazione di Λ(x) ≤ n−1 n fare riferimento a [2].
Dopo aver dato delle limitazioni dall'alto per Λ, è il momento di dare una limitazione dal basso per ρ:
Lemma 3.4. Sia A ≥ 0 di ordine n irriducibile con diagonale principale po-sitiva. Sia T il suo operatore di Menon. Allora per ρ = Λ(x), con x ∈ P+,
vale
ρ ≥ 1 Dimostrazione. Vedere [2].
Adesso si può dimostrare la specializzazione del Teorema (3.1), relativa all'operatore di Menon:
Lemma 3.5. Sia A ≥ 0 di ordine n irriducibile con diagonale principale po-sitiva. Sia T il suo operatore di Menon. Se esiste x ∈ P+ tale che ρ = Λ(x)
allora
ρ = 1 e T (x) = x per un unico x ∈ P+.
Dimostrazione. Si procede similmente al Lemma (3.3). Presi x ∈ P+, y = UAx
e z = T (x), si costruiscono le matrici X = D(x), Y = D(y) e Z = D(z). La matrice Y AX è stocastica per righe, come già dimostrato nel Lemma (3.3).
Si dimostra che la matrice ρY AX è stocastica per colonne. Siccome T (x) = ρxper il Teorema (3.1), allora T (X) = ρX = Z e perciò
ρY AX = Y A(ρX) = Y AZ
Quindi, andando a sommare tutti gli elementi rispettivamentedi Y AX e ρY AX, si ottiene che entrambi danno n come risultato:
n X i=1 n X j=1 yiaijxj= n = ρ n X i=1 n X j=1 yiaijxj da cui ρ = 1.
3.3 Teorema di esistenza e unicità
Una volta assodato tutto questo, è nalmente possibile dimostrare il Teorema di Perron-Frobenius per l'operatore non-lineare T :
Teorema 3.2. (Perron-Frobenius non-lineare) Se A ≥ 0 è irriducibile con diagonale principale positiva e T è il suo operatore di Menon, allora
1) Esiste un unico u ∈ P+ (a meno di costanti moltiplicative) tale che sia
punto sso di T
T (u) = u
2) Per ogni v ∈ P+\{u} tale che T (v) = λv allora λ < 1.
Dimostrazione. Riguardo al punto 1), si tratta di applicare i Lemmi appena visti:
Per il Lemma (3.2) esiste un u ∈ P\{0} (cioè non tutto nullo) tale che ρ = Λ(u)su P\{0}.
Per il Lemma (3.4) ρ = Λ(u) ≥ 1. Adesso se esistesse ui= 0per i = 1, . . . , n
allora per il Lemma (3.3) sarebbe ρ = Λ(u) ≤ n−1
n < 1; ma questo è assurdo.
Quindi deve essere u ∈ P+.
Per il Lemma (3.1) allora ρ = Λ(u) = 1 e u ∈ P+ è l'unico vettore tale che
T (u) = u. In altri termine ρ = 1 è autovalore di T e u è l'unico autovettore di T in P+.
Ma u è anche unico anche in P, infatti se esistesse un altro vettore x ∈ P\P+
(cioè non tutto positivo), allora per il Lemma (3.4) sarebbe ρ = Λ(x) < 1, quindi sarebbe T (x) 6= x, ossia x non sarebbe relativo a ρ = 1.
2) Preso un v ∈ P+\{u}, siccome Λ(v) ≤ 1 per il Lemma (3.3) questo
signi ca l'esistenza di un λmax= 1tale che
T (v) > λmaxv oppure T (v) = λmaxv
Ovvero non può esistere un λ > 1 tale che T (v) = λv, altrimenti sarebbe λmax= λ > 1, che è assurdo. Avendo posto v 6= u, allora deve essere λ < 1.
Corollario 3.1. Se A ≥ 0 è irriducibile con diagonale principale positiva, al-lora A è scalabile in modo unico nella matrice doppiamente stocastica S = D(U Au)AD(u), dove u è l'unico punto sso dell'operatore T . L'unicità è sempre intesa a meno di un fattore moltiplicativo.
Dimostrazione. Sotto questa ipotesi il Teorema (3.2) garantisce che esista un unico (a meno di costanti moltiplicative) punto sso u per l'operatore T as-sociato ad A. Quindi per il Teorema (2.1) A è scalabile nella matrice S = D(U Au)AD(u).
4 Matrici scalabili
Per quanto visto dal Teorema (2.1), le matrici scalabili sono tutte e quelle quelle A ≥ 0tali che il loro operatore di Menon T ammetta almeno un punto sso.
Invece dal Corollario (3.1) consegue che, prese tra tutte le A ≥ 0 quelle che sono irriducibili e con diagonale principale positiva, allora il corrispondente T ammette un unico punto sso.
C'è un margine tra i due risultati, entro il quale giacciono tutte quelle matrici A ≥ 0 tali che T ammetta un punto sso, ma che questo non sia unico. E' interessante quindi avere un'idea generale di quale sia la più ampia classe di matrici non-negative tali che il Problema del Bilanciamento ammetta soluzione, ovvero determinare l'estensione dell'insieme delle matrici per cui vale il Teorema (2.1). Per fare questo è fondamentale una nozione di diagonale che generalizza quella di diagonale principale di una matrice:
De nizione 4.1. Sia A ∈ Rn×n e π una permutazione di {1, . . . , n}. Una
diagonale di A è una n-upla
(a1,π(1), . . . , an,π(n))
che si riduce ad essere la diagonale principale quando π(i) = i per ogni i = 1, . . . , ne nel caso risulta (a11, . . . , ann).
Una diagonale è positiva quando è composta di tutti elementi positivi. Osservazione 4.1. In altre parole una diagonale è una scelta di n elementi di A, ciascuna su una riga e una colonna dierente dagli altri. Sia A(ij) il
minore di una matrice A, ovvero la matrice quadrata di ordine n − 1 ottenuta da A eliminando la riga i e la colonna j. Allora d = aij∪ d0 è una diagonale se
e solo se d0 è una diagonale per A(ij).
Il concetto di diagonale permette di de nire un'importante classe di matrici non-negative:
De nizione 4.2. Sia A ≥ 0 di ordine n.
A ha supporto se esistono n elementi positivi che formano una diagonale positiva.
Aha supporto totale se ogni aij> 0è contenuto in una diagonale positiva.
Osservazione 4.2. Chiaramente l'insieme delle matrici con supporto contiene, strettamente, quello delle matrici con supporto totale. Quindi se una matrice non ha supporto, non ha nemmeno supporto totale. E una matrice non ha supporto quando non esiste una diagonale con tutti elementi positivi, ovvero quando ogni diagonale contiene almeno un elemento nullo.
Si dimostrerà che le matrici scalabili, nel senso del Teorema (2.1), sono tutte e sole le matrici con supporto totale. Rilevando l'ipotesi che lo scaling di A debba essere una matrice della forma S = D1AD2, allora è su ciente che A abbia
supporto a nchè sia riducibile in forma doppiamente stocastica. Andando per esclusione, si può riformulare un risultato classico per determinare quando A non abbia supporto totale, sulla base dell'Osservazione (4.2):
Teorema 4.1. (Frobenius-König) Sia A ∈ Rn×n. A non ha supporto se e solo
se esiste in A una sottomatrice nulla di ordine n1× n2 dove n1+ n2= n + 1.
In questo modo si comincia ad intuire l'importanza che A non contenga ma-trici nulle di una forma particolare, ai ni dello scaling. O comunque che A non abbia una disposizione di zeri al suo interno tale che, esista una qualche per-mutazione delle sue righe e delle sue colonne in grado di riordinare gli elementi nulli in una matrice tutta nulla. A questo ne è interessante ra nare una classi- cazione delle matrici all'interno delle quali è possibile isolare una sottomatrice tutta nulla; in questo modo si andrà infatti a trovare una de nizione equivalente di matrice irriducibile a quella data con la De nizione (3.1):
De nizione 4.3. Data una matrice A ∈ Rn×n. Sia A
ij il blocco di elementi di
Adi posizione (i, j) e dimensioni arbitrarie. Allora A è detta:
1) completamente decomponibile se esiste una matrice di permutazione P ∈ Rn×n tale che
P APT =A11 O O A22
2) decomponibile oppure riducibile se esiste una matrice di permutazione P ∈ Rn×n tale che
P APT =A11 O A21 A22
dove i blocchi diagonali A11, A22 sono quadrati e quindiA21 (potenzialmente
nulla) è in generale rettangolare. Se P non esiste allora A è detta irriducibile; 3) quasi completamente decomponibile se esiste una matrice di permu-tazione P ∈ Rn×n tale che
P APT =A11 O O A22
+ E
dove > 0 è piccolo ed E ∈ [0, 1]n×n;
4) quasi decomponibile se esiste una matrice di permutazione P ∈ Rn×n
tale che P APT =A11 O A21 A22 + E dove > 0 è piccolo ed E ∈ [0, 1]n×n;
5) parzialmente decomponibile se esistono due matrici di permutazione P, Q ∈ Rn×n tali che
P AQ =A11 O A21 A22
dove i blocchi diagonali A11, A22 sono quadrati e quindi A21
(potenzialmen-te nulla) è in generale rettangolare. Se P, Q non esistono allora A è detta completamente indecomponibile.
Osservazione 4.3. Si può osservare che una matrice decomponibile/riducibile è anche parzialmente decomponibile (prendendo Q = PT), mentre il viceversa
non è vero in generale; per esempio la matrice A1=
0 1 1 1
è parzialmente decomponibile ma non riducibile. Si può notare anche che se una matrice è completamente indecomponibile allora è anche irriducibile, mentre il viceversa non è vero in generale; per esempio la matrice
A2=
0 1 1 0
è irriducibile, ma prendendo P = A2 e Q = I si ha che P AQ = I che è
parzialmente decomponibile.
Rientrando nei con ni delineati dal Teorema (2.1), ovvero tra le matrici con supporto totale. Coloro le quali ammettono uno scaling unico, sono le matrici irriducibili con diagonale principale positiva. Quindi non basta la sola irriducibilità a garantire l'esistenza e l'unicità del punto sso per T . Mentre si può dimostrare che è su ciente la completa indecomponibilità della matrice di partenza, infatti:
Proposizione 4.1. Sia A ≥ 0 si ordine n. A è completamente indecomponibile se e solo se le sue colonne possono essere permutate in modo da ottenere una matrice irriducibile con diagonale principale positiva.
Dimostrazione. Vedere [2].
Quest'ultimo risultato quindi dice che ogni matrice irriducibile con diago-nale positiva è sostanzialmente equivalente ad una matrice completamente in-decomponibile. Quindi si può formulare una versione alternativa del Corollario (3.1):
Corollario 4.1. Se A ≥ 0 è completamente indecomponibile, allora A è scalabile in modo unico nella matrice S = D(UAu)AD(u), dove u è l'unico punto sso di T . L'unicità è intesa a meno di un fattore moltiplicativo.
Sempre con l'obiettivo di dimostrare che le matrici con supporto totale sono tutte e sole le matrici scalabili, è utile evidenziare il collegamento tra queste e le matrici completamente indecomponibili:
Proposizione 4.2. Sia A 0 di ordine n.
1) Se A è completamente indecomponibile allora A ha supporto totale. 2) Se A ha supporto totale allora esistono due matrici di permutazione P, Q tali che
P AQ = diag(A11, . . . , Akk)
Dimostrazione. 1) Se A è completamente indecomponibile. Supponendo per assurdo che A non abbia supporto totale. Allora esiste un elemento aij 6= 0
che non appartiene ad alcuna diagonale positiva. Allora la minore A(ij) non ha
proprio alcuna diagonale positiva (se ne avesse, estesa ad A, conterrebbe aij).
Ne segue che per il Teorema (4.1) esiste una sottomatrice tutta nulla di A(ij) (e
quindi di A) di dimensione n1× n2con n1+ n2= n; quindi A è decomponibile.
Assurdo. Quindi A deve avere supporto totale. 2) Vedere [2].
In sintesi è stato dimostrato che:
• le matrici irriducibili con diagonale strettamente positiva sono equivalenti alle matrici completamente indecomponibili;
• le matrici completamente indecomponibili sono anche a supporto totale; quindi le matrici completamente indecomponibili formano una sorta di ponte tra le prime, per le quali l'operatore T ammette un unico punto sso e le seconde, per le quali si dimostra adesso che T ammette almeno un punto sso:
Teorema 4.2. (Sinkhorn-Knopp) Sia A ≥ 0 di ordine n.
A è scalabile se e solo se A ha supporto totale, ovvero esistono due matrici diagonali D1, D2> 0tali che S = D1AD2 sia doppiamente stocastica.
Se A è anche completamente indecomponibile (ovvero irriducibile con diago-nale principale positiva) allora D1, D2 sono uniche (a meno di fattori
moltipli-cativi).
Dimostrazione. Vedere [2].
Quindi le matrici per cui T ammette almeno un punto sso sono le matrici a supporto totale.
5 La soluzione come autovettore
Il problema del bilanciamento viene quindi ricondotto al calcolo del punto sso di T . Ma è possibile anche vederlo sotto un altro punto di vista.
In questa sezione si vedrà come la dinamica di T in un punto di P+ sia
mo-dellata esattamente dalla jacobiana di T calcolata in quel punto. Questo per-metterà di tradurre il problema di punto sso non-lineare, in un altro equivalente posto come ricerca di un autovettore.
Detto questo da adesso in poi con u sarà inteso in maniera indierente il punto sso di T come uno speci co autovettore della jacobiana di T .
5.1 Jacobiana di T
Ricordando che la jacobiana di una funzione f : Rn → Rn nel punto x ∈ Rn è
una matrice quadrata annotata come Jf(x)tale che
[Jf(x)]ij=
∂fi(x)
∂xj
allora se ne può dedurre un'espressione esplicita:
Proposizione 5.1. Sia A ≥ 0 e T l'operatore di Menon ad essa associato. Allora
JT(x) = D(T x)2· AT · D(U Ax)2· A (10)
Dimostrazione. In primo luogo serve usare la regola di derivazione per le funzioni composte dapplicata su T (x) = UATU A(x), ottenendo così:
JT(x) = JU(ATU Ax) · JAT(U Ax) · JU(Ax) · JA(x) (11)
dove si può applicare due volte la regola della derivata del reciproco ∂y−1 j = −1/y2 j e ottenere JU(y) = − 1 D(y)2 = D(U y) 2
Inoltre applicando la derivazione di una somma a (Ay)i=P n
j=1aijyj, si ottiene
che ∂(Ay)i/∂yj= aij. Per questo
JA(y) = A JAT(y) = AT
Allora si può riscrivere l'Equazione (11) sostituendo i vari pezzi e ottenere la tesi.
5.2 Jacobiana in un punto x ∈ P
+Proposizione 5.2. Sia A ≥ 0 e T l'operatore di Menon ad essa associato. Per ogni x ∈ P+ vale che
ρ(JT(x)) ≥ 1
Dimostrazione. Dall'Equazione (10) segue che la similarità di JT(x)con un'altra
matrice
JT(x) = D(T x)2· AT · D(U Ax)2· A
= D(T x) · D(T x) · AT · D(U Ax) · D(U Ax) · A
= D(T x) · D(T x) · AT · D(U Ax) · D(U Ax) · A · D(T x) · D(T x)−1
= D(T x) · GGT · D(T x)−1
dove è posto Gdef
= D(T x) · AT · D(U Ax). Quindi
JT(x) ∼ GGT
Adesso si dimostra che (1, e) è un'autocoppia per G Ge = D(T x) · AT· D(U Ax) · e
= D(T x) · ATU Ax
= D(U ATU Ax) · ATU Ax
ma siccome ρ(G) ≤ kGk2 allora 1 ≤ kGk2.
Passando ai valori singolari, dato che σmax(G) = kGk2 e ricordando che
σi(G) =pλi(GGT)si ottiene che
1 ≤ ρ(GGT) = ρ(JT(x))
Tornando al legame tra i due problemi delle Equazioni (6) e (12). Questo si inizia a costruire col prossimo risultato, che esprime precisamente come la jacobiana di T modelli la dinamica di T in un punto:
Lemma 5.1. Sia A ≥ 0 e T l'operatore di Menon ad essa associato. Per ogni x ∈ P+ vale
T (x) = JT(x)x
Dimostrazione. Cominciando dalla solita Equazione (10) JT(x)x = D(T x)2· AT · D(U Ax)2· Ax
= D(T x)2· AT · D(U Ax) · D(U Ax) · Ax
= D(T x)2· AT · D(U Ax) · e = D(T x)2· AT · U Ax
= D(T x) · D(U ATU Ax) · ATU Ax = D(T x) · e
= T (x)
Ma la relazione del Lemma (5.1) si può estendere, seppur approssimativa-mente, ad un intorno di x ∈ P+:
Lemma 5.2. Sia T una funzione vettoriale. Preso un x ∈ P+, allora per ogni
y 6= xappartenente ad un intorno di x vale: T (y) ≈ JT(x)y
Dimostrazione. Basta linearizzare al prim'ordine in x T (y) = T (x) + JT(x)(y − x) + o(ky − xk)
≈ T (x) + JT(x)(y − x)
= T (x) + JT(x)y − JT(x)x
= T (x) + JT(x)y − T (x)
= JT(x)y
5.3 Jacobiana nel punto sso
In particolare però è necessario studiare il caso in cui il vettore sia proprio il punto sso u ∈ P+ di T :
Proposizione 5.3. Sia A ≥ 0 e T l'operatore di Menon ad essa associato. Se u ∈ P+ è punto sso di T , allora
ρ(JT(u)) = 1
Dimostrazione. Riprendendo di nuovo l'Equazione (10), dato che T u = u si ha: JT(u) = D(T u)2· AT· D(U Au)2· A
= D(u)2· AT· D(U Au)2· A
= D(u) · D(u) · AT · D(U Au) · D(U Au) · A · D(u) · D(u)−1
= D(u) · STS · D(u)−1
dove S è la matrice doppiamente stocastica del Teorema (2.1). Da questa nuova similitudine si ha
JT(u) ∼ STS
Per la doppia stocasticità di S ha in particolare che Se = e, quindi come nella precedente dimostrazione (1, e) è autocoppia di S e quindi
1 ≤ kSk2
La doppia stocasticità si può scrivere anche come kSk1 = 1 e kSk∞ = 1.
Inoltre vale in generale che kSk2≤pkSk1kSk∞, dal quale risultato discende
kSk2≤ 1
Mettendo insieme le disuguaglianze se ne trae che kSk2 = 1. Da questo la
conclusione segue in modo analogo alla dimostrazione della Proposizione (5.2): 1 = ρ(STS) = ρ(JT(u))
Osservazione 5.1. Siccome JT(u) ∼ STS, è bene tenere a mente che per ogni
autovalore positivo di JT(u) vale
λi(JT(u)) = σ2i(S)
5.4 Il problema equivalente
Adesso è possibile giusti care la soluzione del problema del bilanciamento co-me ricerca di un autovettore per JT(u), piuttosto che come punto sso per
l'operatore T di Menon:
Teorema 5.1. Sia A ≥ 0 e T l'operatore di Menon ad essa associato. Esiste un u ∈ P+ punto sso per T se e solo se (1, u) è autocoppia di JT(u)
T (u) = u ⇐⇒ JT(u)u = u
Dimostrazione. Infatti basta notare che u = T (u) = JT(u)uper il Lemma (5.1),
da cui segue che u sia autovettore di JT(u)u.
In altre parole, la ricerca del punto sso dell'Equazione (6) è quindi equi-valente alla ricerca dell'autovettore associato all'autovalore λ = 1 della matrice JT(u), ovvero
JT(u)u = u u ∈ P+ (12)
6 Dominanza dell'autovettore
Quindi per l'Equazione (12) i problemi delle Equazioni (6) e (12) si equivalgono e quindi ammettono soluzione sotto le stesse condizioni.
Dal Teorema (4.2) risulta che A è a supporto totale se e solo se esiste almeno un punto sso u ∈ P+ per T , se e solo se (1, u) è autocoppia di JT(u).
Dal Teorema (3.2) risulta che se A è irriducibile con diagonale principale positiva allora esiste un unico punto sso u ∈ P+ per T .
Sarà visto adesso che sotto la stessa condizione adesso l'autocoppia (1, u) risulta dominante per JT(u)e per mezzo di essa si giunga ad una soluzione del
Problema (1.3) del Bilanciamento.
Lemma 6.1. Sia A ≥ 0 irriducibile con diagonale principale positiva (ovvero completamente indecomponibile). Allora A è primitiva.
Dimostrazione. Vedere il Teorema 3 di [7].
Adesso si può dire che il raggio spettrale ρ(JT(x))sia autovalore associato
ad un qualche autovettore di JT(x):
Proposizione 6.1. Sia A ≥ 0 irriducibile con diagonale principale positiva e T l'operatore di Menon ad essa associato. Per ogni x ∈ P+ il raggio spettrale
ρ(JT(x)) ≥ 1è autovalore dominante
relativo ad un unico autovettore v ∈ P+. Cioè esiste un'unica autocoppia
(ρ(JT(x)), v)che soddisfa l'identità
JT(x)v = ρ(JT(x))v (13)
Dimostrazione. Si vuole dimostrare che per JT(x) esiste un autovalore λ =
ρ(JT(x))che sia dominante nel senso della De nizione (A.6). Si cerca di ottenere
questo, dimostrando essere JT(x) primitiva.
Come visto nella Proposizione (5.2) allora JT(x) = D(T x) · GGT · D(T x)−1
dove
G = D(T x) · AT · D(U Ax)
Siccome A ha diagonale positiva per ipotesi e x ∈ P+, allora Ax > 0 perchè
ogni prodotto scalare che costituisce questo prodotto è positivo almeno per via dell'addendo aiixi > 0. Di conseguenza UAx > 0 e T (x) > 0. Inoltre per
l'Osservazione (1.1) vale gij= T (x)iU (Ax)jaji
ma i due fattori sono positivi, quindi gij = 0 ⇐⇒ aji = 0. Ovvero G ha la
stessa struttura di elementi nulli di AT, che l'ha speculare ad A.
Siccome A è completamente indecomponibile, allora lo è anche AT e quindi
G. Per il Lemma 2 di [8] allora anche GGT è completamente indecomponibile
e quindi primitiva per il Lemma (6.1).
Quindi per il Teorema (A.8) ρ(GGT)è autovalore dominante di GGT. Ma
JT(x)è simile a GGT, quindi ρ(JT(x))è dominante anche per JT(x).
Sempre per lo stesso Teorema (A.8) a ρ(JT(x))è associato un unico
autovet-tore v ∈ P+. Quindi si esclude che esistano altri autovettori in w ∈ P+\{v}che
siano allo stesso tempo relativi a ρ(JT(x))e tra loro linearmente indipendenti.
In questo senso l'Equazione (13) ammette come unica soluzione (ρ(JT(x)), v),
anche se ogni altro autovettore appartenente all'autospazio di ρ(JT(x)) è una
soluzione alternativa ammissibile.
Osservazione 6.1. L'ipotesi su A è necessaria a garantire che il raggio spettra-le sia autovalore dominante, ma non che l'autovettore v ∈ P+ ad esso associato
sia unico. Richiedendo solo l'irriducibilità di A si ha comunque la garanzia che esista un unico autovettore relativo al raggio spettrale, solo in questo modo non si esclude la presenza di altri autovalori di modulo uguale al raggio spettrale. Quindi al sola irriducibilità non riesce, da sola, a garantire l'esistenza di un'u-nica autocoppia, ma basta per garantire l'esistenza di un unico autovettore (a meno di multipli scalari ovviamente).
Corollario 6.1. Se A ≥ 0 è irriducibile con diagonale principale positiva, allora A è scalabile in modo unico nella matrice doppiamente stocastica S = D(U Au)AD(u), dove u è l'unico autovettore in P+relativo all'autovalore
domi-nante ρ(JT(u)) = 1 della matrice JT(u). L'unicità è sempre intesa a meno di
un fattore moltiplicativo.
Dimostrazione. Mettendo insieme la Proposizione (6.1) con la Proposizione (5.3) segue che ρ(JT(u)) = 1sia autovalore dominante di JT(u)relativo all'unico
u ∈ P+. Quindi l'Equazione (13) si riduce a
Attraverso il Teorema (5.1) si risale al concetto di scalabilità per A enunciato nel Teorema (2.1).
Questo risultato permetterà di trattare il problema della ricerca del punto sso come ricerca dell'autovettore dominante della matrice JT(u). Siccome
l'autovettore dominante è proprio u, sembra un circolo vizioso cercare u per la matrice JT(u)de nita proprio in u. Una possibilità sarà quindi sviluppare un
metodo basato su una doppia iterazione inner-outer, denominato SKK∞, in cui
la sequenza degli autovettori dominanti converge a u, senza mai richiedere di calcolare esplicitamente JT(u).
Parte II
Il metodo di Sinkhorn-Knopp
Sia A ≥ 0 una matrice scalabile nel senso del Teorema (2.1).Si può de nire adesso un metodo eettivo che permetta di trovare i due vettori r, c ∈ P+
richiesti alla de nizione della matrice S doppiamente stocastica. Il Sistema (5) si può tradurre immediatamente in un metodo iterativo mutuamente ricorsivo: De nizione 6.1. Il Metodo di Sinkorn-Knopp è de nito dalla ricorrenza:
r(0)∈ P + c(k+1)= D−1(ATr(k))e r(k+1)= D−1(Ac(k+1))e (14) Ma se ne possono trovare almeno tre versioni equivalenti, tutte quante ca-ratterizzate dagli stessi criteri di convergenza. Dalla dimostrazione del Teorema (2.1), si può ricavare che:
c(k+1)= U ATU Ac(k) k ≥ 0 (15) evidenziando la natura composizionale dell'iterazione. Usando l'operatore T di Menon e chiamando da ora in poi u(k)l'approssimazione corrente del punto sso
di T , si ri-de nisce il Metodo di Sinkhorn-Knopp non nella sua natura originale, ma in modo da evidenziare l'iterazione di punto sso che ne è implicita:
u(0)∈ P+
u(k+1)= T (u(k)) k ≥ 0 (16)
Nell'ottica invece di inquadrare la soluzione come l'autovettore dominante della jacobiana di T , come si è stabilita l'equivalenza tra i due problemi delle Equazioni (6) e (12), si può trovare un metodo esattamente equivalente al Me-todo (16). Infatti avendo T (x) = JT(x)xper ogni x ∈ P+, basta porre x := u(k)
nel Metodo (16) per ottenere il nuovo metodo
u(0)∈ P +
u(k+1)= J
che trasforma un'iterazione di punto sso per l'operatore non-lineare T , in un metodo iterativo tradizionale che richiede solo moltiplicazioni matrice-vettore (ma pure la costruizione della jacobiana nell'approssimazione corrente). Que-st'ultimo metodo può essere riferito come SK.
Quindi, esattamente come il Metodo (16) converge al punto sso di T , il Metodo (17) converge all'autovettore u relativo all'autovalore ρ(JT(u)) = 1
della jacobiana.
7 Convergenza del metodo
L'esistenza di un punto sso per T è una proprietà del problema e il Teorema (4.2) di Sinkhorn-Knopp garantisce che, sotto l'ipotesi che A sia completamente indecomponibile oppure irriducibile con diagonale principale positiva, la solu-zione al Problema (1.3) del Bilanciamento esista e sia unica. Adesso resta da provare che il Metodo (16) raggiunga eettivamente questa soluzione.
Per studiare la convergenza dei Metodi di Sinkorn-Knopp si torna a consi-derare la formulazione del Problema di Bilanciamento espresso dal Sistema (4), ovvero la ricerca di una coppia di vettori (r, c) ciascuno in P+ tali che
D(r)AD(c)e = e D(c)ATD(r)e = e
viste come la composizione di due equazioni in cascata, a partire da una matrice A ≥ 0. In questo modo si cerca di inquadrare il problema iniziale in una teoria leggermente più generale in cui un vettore può essere visto come una funzione x : {1, . . . , n} → R, appartenente ad uno spazio di Banach X. La composizione delle due equazioni corrisponde all'operatore di Menon T (c) = UATU Ac, per
cui tra le tre versioni del Metodo suddette, quella di riferimento per dimostrare la convergenza sarà l'iterazione di punto sso descritta dal Metodo (16): se questo Metodo converge, allora l'approssimazione u del punto sso rinvenuta permette di dare una soluzione al problema del bilanciamento in termini di due vettori (r, c) tali che c = u e r = UAu, come visto nel Teorema (2.1).
In estrema sintesi l'iterazione suddetta su A ≥ 0 irriducibile a diagonale positiva è globalmente convergente dal momento che T risulta essere una funzio-ne non-espansiva secondo la metrica di Hilbert associata al cono P dei vettori non-negativi. In simboli: l'obiettivo di questa sezione è dimostrare che per ogni u(0)∈ P
+ esiste un λ > 0 tale che
lim
k→∞u
(k)= λu
dove u è il punto sso di T . E la convergenza avviena alla velocità del secondo valore singolare della matrice risultante S = D(UAu)AD(u).
E' comunque possibile dimostrare la convergenza del metodo pure sotto l'i-potesi più generale di A con supporto totale, non necessariamente irriducibile con diagonale principale positiva. In questo caso, nel quale non si ha certezza dell'unicità del punto sso, non si hanno nemmeno informazioni sulla velocità di convergenza.
7.1 Sull'espansività di T
7.1.1 Il cono P
De nizione 7.1. Uno spazio metrico è una struttura matematica costituita da una coppia (X, d) di elementi, dove X è un insieme e d una funzione distanza, detta anche metrica, che associa a due punti x, y ∈ X un numero reale non negativo d(x, y) in modo che valgano queste proprietà per ogni x, y, z ∈ X:
1) d(x, y) > 0 per x 6= y 2) d(x, y) = 0 per x = y 3) d(x, y) = d(y, x)
4) d(x, y) ≤ d(x, z) + d(z, y)
De nizione 7.2. Una successione di vettori {x(k)
∈ Rn}
k∈N è convergente
a x ∈ Rn se per ogni i = 1, . . . , n vale |x(k)
i − xi| → 0per k → ∞.
In particolare x(k)→ xse e solo se kx(k)− xk → 0per k → ∞.
De nizione 7.3. Una successione di Cauchy è una successione {x(k)} k∈N
a valori in uno spazio metrico (X, d) tale che
∀ > 0 ∃N ∀m, n ≥ N =⇒ d(x(m), x(n)) <
cioè, al tendere dell'indice all'in nito, la distanza tra due elementi nello spa-zio X tende ad annullarsi. Infatti un caso particolare di successione di Cauchy è una successione convergente. Non essendo sempre vero il contrario, gli spazi metrici in cui tutte le successioni di Cauchy risultano convergenti ad un elemen-to dello spazio stesso, sono detti spazi metrici completi. Per l'appunelemen-to, uno spazio normato completo, dove si assume come metrica la norma, è il seguente: De nizione 7.4. Uno spazio di Banach X è uno spazio vettoriale de nito su un campo scalare, dotato di norma k · kX che è completo rispetto alla
di-stanza indotta da tale norma, ovvero tale che ogni successione di Cauchy sia convergente a un elemento dello spazio stesso
lim
k→∞kx
(k)− xk X = 0
Inoltre, le funzioni che non allontano due elementi appartenti allo stesso spazio sono le seguenti:
De nizione 7.5. Sia (X, d) uno spazio metrico. Sia data una funzione f : X → X che per ogni x, y ∈ X soddisfa
d(f (x), f (y)) ≤ Cd(x, y) allora
1) Se C = 1 allora f è detta non-espansiva; 2) Se C ∈ [0, 1) allora f è detta contrattiva.
Adesso è tempo di andare a costruire gli spazi e le relative metriche entro cui studiare la dinamica delle iterate di punto sso.
L'insieme P ={x ∈ Rn : x ≥ 0} usato nora è un caso particolare di cono
convesso positivo. Mentre P0 ne è la parte interna IntP, ossia l'insieme dei
punti di P tali che esista almeno un intorno di essi completamente contenuti strettamente in P. Ovvero, l'insieme dei punti non giacenti sul bordo del cono. De nizione 7.6. Sia X uno spazio di Banach reale. Un sottoinsieme K ⊆ X si dice cono convesso positivo se:
1) x, y ∈ K =⇒ x + y ∈ K 2) x ∈ K, λ ∈ R≥0 =⇒ λx ∈ K
3) x ∈ K, −x ∈ K =⇒ x = 0
da ora in poi denominato come cono.
All'interno di un cono è indotta naturalmente una relazione d'ordine parziale su X: x ≤K y def ≡ y − x ∈ K x <K y def ≡ y − x ∈ IntK
che verrà scritta semplicemente come ≤ a patto di non avere ambiguità. Questa de nizione va a richiamare quella già data per P∞.
De nizione 7.7. Due elementi x, y ∈ K sono confrontabili, ovvero x ∼K y
se esistono α, β > 0 tali che
αx ≤ y ≤ βx
In connessione a questa relazione di confrontabilità si de niscono due quan-tità:
M (x/y)def= inf{λ ∈ R : x ≤ λy} m(x/y)def= sup{µ ∈ R : µy ≤ x} che fungono, quando ristrette su K\{0}, come limitazioni al rapporto x/y:
• M (x/y)è il più piccolo scalare tale che x/y ≤ M(x/y); • m(x/y)è il più grande scalare tale che m(x/y) ≤ x/y;
da cui si deduce il più piccolo intervallo che contiene il rapporto x/y: m(x/y) ≤ x/y ≤ M (x/y)
Inoltre questa relazione induce un partizionamento su K in insiemi disgiunti detti componenti. Per esempio le componenti del cono dei vettori non negativi di R2 sono:
C0= {0} C1= {(x1, 0) : x1> 0} C2= {(0, x2) : x2> 0} C3= IntK
Questo signi ca che un vettore che non sta completamente nell'interno di K, ovvero nella componente C3, possiede almeno un elemento nullo.
Quest'ordine ≤K può dover essere preservato dall'applicazione di una
De nizione 7.8. Sia K un cono e f : K → K una funzione su di esso. Se per ogni x, y ∈ K vale x ≤ y =⇒ f(x) ≤ f(y) allora f è monotòna. Se per ogni x, y ∈ K vale x ≤ y =⇒ f(x) ≥ f(y) allora f è antitòna. 7.1.2 Distanze e metriche
Una volta introdotto l'insieme dei valori, è necessario presentare le metriche che permettono di veri care le condizioni di non-espansività dell'iterazione di punto sso:
De nizione 7.9. Sia K ⊆ X un cono. Dati x, y ∈ K\{0} tali che x ∼K y, si
de niscono le due distanze:
1) La distanza proiettiva di Hilbert dH(x, y) = log
M (x/y) m(x/y)
2) La distanza di Thompson
dT(x, y) = max {log M (x/y), log M (y/x)}
in entrambi i casi dH(x, y) = dT(x, y) = ∞se x K y.
Lemma 7.1. La distanza proiettiva di Hilbert ristretta alla componente Σ = {x ∈ C : kxk = 1} e la distanza di Thompson su ogni componente C 6= {0} sono metriche,
Dimostrazione. Vedere [2]. 7.1.3 Convergenza in norma
Una volta provato che queste due distanze siano eettivamente metriche, resta da dimostrare che la convergenza rispetto alle metriche di Thompson e Hilbert implica la convergenza rispetto alla norma consueta. Si parte con una de nizione di monotonia:
De nizione 7.10. Sia K ⊂ X un cono in uno spazio di Banach. La norma di X si dice monotona rispetto a K se
∀x, y ∈ K x ≤Ky =⇒ kxk ≤ kyk
Adesso si possono mostrare due prime limitazioni: una sulla dierenza kx−yk e l'altra per la distanza dT:
Lemma 7.2. Sia K ⊂ X un cono in uno spazio di Banach.
Se la norma di X è monotona rispetto a K, allora se x ≤K λy, y ≤K
λx,kxk ≤ m e kyk ≤ m si ha
Dimostrazione. Vedere [2].
Lemma 7.3. Sia K ⊂ X un cono in uno spazio di Banach. Supponendo che la norma di X sia monotona rispetto a K.
Allora ∀x, y ∈ Σ = {x ∈ C : kxk = 1} per una qualche componente C 6= {0} di K, vale
1
2dH(x, y) ≤ dT(x, y) ≤ dH(x, y) Dimostrazione. Vedere [2].
Ecco così il risultato che da una limitazione dall'alto alla norma di due elementi del cono, mediante le distanze dT e dH:
Proposizione 7.1. Sia K ⊂ X un cono chiuso in uno spazio di Banach. Supponendo che la norma su X sia monotona rispetto a K.
Se x, y ∈ K e kxk ≤ m e kyk ≤ m allora
kx − yk ≤ 3medT(x,y)− 1
Se x, y ∈ Σ = {x ∈ C : kxk = 1} per una qualche componente C 6= {0} di K, vale
kx − yk ≤ 3edH(x,y)− 1
Dimostrazione. Ponendo ¯λ := edT(x,y) allora vale per de nizione che x ≤
K ¯λy
e y ≤K λx¯ , quindi la prima disuguaglianza è un'immediata applicazione del
Lemma (7.2).
La seconda disuguaglianza discende dalla prima, ricordando il Lemma (7.3). 7.1.4 Completezza delle metriche
Nella dimostrazione dei teoremi di convergenza sarà importanza avere a che fare con spazi metrici completi, per cui è necessario accertarsi che le componenti dei coni in questione lo siano, rispettivamente secondo le metriche dT e dH:
Teorema 7.1. Sia K ⊆ X un cono in uno spazio di Banach reale e sia C una componente di K. Allora (C, dT)è uno spazio metrico completo.
Dimostrazione. Vedere [2].
Teorema 7.2. Sia K ⊆ X un cono chiuso in uno spazio di Banach reale e sia C una componente di K, u ∈ C e sia Σ = {x ∈ C : kxk = 1}.
Se la norma di X è monotona rispetto a K, cioè allora (Σ, dH)è uno spazio
metrico completo.
7.1.5 Condizioni di non-espansività
Adesso si possono iniziare a intrecciare i concetti di metrica con quello di non-espansività, iniziando da una Proposizione che dice qualcosa di simile ma riguardando le quantità M(x/y) e m(x/y):
Proposizione 7.2. Sia K ⊂ X un cono inn uno spazio di Banach.
1) Sia f : K → K monotona e omogenea di grado r > 0. Allora per ogni x, y ∈ K tali che x ∼K y valgono le seguenti
M (f (x)/f (y)) ≤ M (x/y)r m(x/y)r≤ m(f (x)/f (y))
2) Sia f : K → K antitona e omogenea di grado r < 0. Allora per ogni x, y ∈ K tali che x ∼K y valgono le seguenti
M (f (y)/f (x)) ≤ M (x/y)r m(x/y)r≤ m(f (y)/f (x))
Dimostrazione. 1) Se x, y ∈ K sono confrontabili tra loro, allora per ogni β > 0 tale che x ≤ βy, per monotonia e omogeneità si ha
f (x) ≤ f (βy) = βrf (y)
Quindi per de nizione M(f(x)/f(y)) ≤ βr per ogni β > M(x/y). Se ne trae
che M(f(x)/f(y)) ≤ M(x/y)r. Analogamente per il secondo caso monotono.
2) Il secondo caso si ottiene allo stesso modo, osservando inizialmente che se x ≤ βysi ha f(y) ≤ βrf (x).
Corollario 7.1. Sia K ⊂ X un cono in uno spazio di Banach.
1) Sia f : K → K monotona e omogenea di grado 1. Allora la funzione f è non-espansiva rispetto a dH (o dT) su ciascuna componente di K.
2) Sia f : K → K antitona e omogenea di grado −1. Allora la funzione f è non-espansiva rispetto a dH (o dT) su ciascuna componente di K.
Ovvero, per ogni x, y ∈ K tali che x ∼Ky
dH(f (x), f (y)) ≤ dH(x, y) dT(f (x), f (y)) ≤ dT(x, y)
Dimostrazione. Usando per esempio la metrica dH, dato che per dT la
dimo-strazione è identica.
1) Segue immediatamente dalla Proposizione (7.2), dalla de nizione di dH e
dalla monotonia del logaritmo.
2) Segue come sopra ma osservando che dH(f (x), f (y)) = log M (x/y) m(x/y) = log M (y/x) m(y/x) = dH(f (y), f (x))
7.1.6 Quanti care l'espansività
Adesso che sono state trovate delle condizioni sotto le quali una funzione f è non-espansiva, resta da quanti care l'eettiva misura di quanto f avvicina tra loro due punti. Si comincia dando una de nizione atta a valutare prima di tutto la massima istanza tra due immagini di f:
De nizione 7.11. Sia K un cono in uno spazio di Banach X e f : X → X un'applicazione lineare tale che f(K) ⊆ K. Il diametro proiettivo di f rispetto alla metrica dH è de nito come
∆(f ) = sup{dH(f (x), f (y)) : x, y ∈ IntK}
e poi l'eettivo coe ciente di contrazione delle funzione f, ovvero la misura di quanto la funzione avvicina due punti sotto il suo eetto:
De nizione 7.12. Sia K un cono in uno spazio di Banach X e sia f : X → X un'applicazione lineare tale che f(K) ⊆ K. Il coe ciente di contrazione di f rispetto alla metrica dH è de nito come
κ(f ) = inf{C : dH(f (x), f (y)) ≤ CdH(x, y) x, y ∈ Int(K)}
Queste due quantità sono legate dal seguente teorema:
Teorema 7.3. (di Birkho) Sia K un cono chiuso in uno spazio di Banach X e sia f : X → X un'applicazione lineare tale che f(K) ⊆ K. Vale
κ(f ) = tanh ∆(f ) 4
Dimostrazione. Vedere [2].
7.2 Teoria della convergenza
Tornando al punto di vista iniziale, in cui il Problema del Bilanciamento veniva visto come la composizione di due equazioni. Più in generale: supponendo di avere da risolvere un sistema mutuamente ricorsivo composto da p equazioni, de nite sugli insiemi:
• Siano X1, . . . , Xp spazi di Banach delle funzioni continue a valori reali;
• Siano K1, . . . , Kp con Ki⊆ Xi i coni delle funzioni non negative su Xi;
• Supponendo che la norma di Xi sia monotona rispetto all'ordine di Ki.
e dai seguenti operatori:
• p operatori lineari continui Li: Xi→ Xi+1 tali che Li(IntXi) ⊂ IntXi+1;
• p operatori di moltiplicazione Mx : Xi → Xi tali che (Mx(y))(t) =
• p operatori di inversione Ui : IntKi → IntKi tali che (Uix)(t) = x(t)−1
per ogni t ∈ {1, . . . , n};
• p funzioni costanti ei = 1per ogni i = 1, . . . , p;
ci si chiede se esistano p funzioni xi∈ IntKi, per i = 1, . . . , p e 0 < λ ∈ R tali
che {Mxi+1LiMxiei = ei+1} p−1 i=1 Mx1LpMxpep = λe1 (18) dove è posto Xp+1 = X1e Kp+1= K1.
Nel caso particolare p = 2, quest'ultimo sistema si riduce a
Mx2L1Mx1e1 = e2
Mx1L2Mx2e2 = λe1
(19) la cui ricerca delle funzioni x1, x2 e dello scalare λ corrisponde al problema del
bilanciamento quando si prendono:
• X1= X2= Rn, dove il vettore xiè visto come una funzione che all'indice
t ∈ {1, . . . , n}associa la componente xi(t) ∈ R;
• K1= K2= P, il cono dei vettori non-negativi; mentre IntK1= IntK2 =
P+ è il cono dei vettori strettamente positivi. In particolare P è un cono
chiuso e la norma euclidea è monotona rispetto all'ordine indotto da P; • L1, L2 rispettivamente come le applicazioni lineari associate alle matrici
A, AT;
• Mxrappresenta il prodotto scalare Mx(y) = hx, yi;
• Ui, che è de nito su IntP, inverte ogni componente del suo argomento
Ui(x) = (x−11 , . . . , x−1n );
• ei corrisponde al vettore (1, . . . , 1)T.
Quindi la questione sulla ricerca di due vettori r, c ∈ P+ che soddis no il
Si-stema (4) si trasforma nella ricerca di due funzioni x1∈ X1 e x2∈ X2 e di un
qualche scalare λ ∈ R tali che sia soddisfatto il Sistema (19). Ricollocondosi al livello più generale di prima, però il seguente Lemma stabilisce un risultato esistenziale. Anche nel Teorema (3.2) si trovava una connessione tra la soluzio-ne al problema di bilanciamento e l'esistenza di un punto sso per l'iteraziosoluzio-ne comandata dall'operatore di Menon. Nel Lemma seguente si stabilisce qualcosa di simile, ma relativamente al sistema mutuamente ricorsivo del Sistema (18), nel cui schema rientra il Sistema (4):
Lemma 7.4. Siano gi: IntKi→ IntKi+1 tali che gi= Ui+1Li per i = 1, . . . , p
e
T : IntK1→ IntK1 T def
= gpgp−1· · · g1
Allora esistono x1,. . . , xp e λ > 0 che risolvono il Sistema (18) se e solo se
esiste un u ∈ IntK1 (ovvero in P+) tale che
Dimostrazione. (⇒) Siano xi e λ che soddisfano il Sistema (18).
Dall'i-esima equazione del sistema Mxi+1LiMxiei= ei+1, per i = 1, . . . p−1,
applicando ad entrambi i membri l'operatore Ui+1 e risolvendo rispetto a xi+1
si ottiene
xi+1= Ui+1Lixi= gi(xi) i = 1, . . . , p − 1
Analogamente dalla p-esima equazione Mx1LpMxpep= λe1 se ne trae
λ−1x1= gp(xp)
Mettendo assieme queste ultime due equazioni si ha che λ−1x1= T (x1)
ovvero u := x1 è il vettore cercato.
(⇐) Viceversa supponendo che per T esista µ > 0 tale che T (x) = µx per un qualche x ∈ IntK1. Ponendo x1 = x, xi+1 = g(xi) per i = 1, . . . , p − 1 e
λ = µ−1 il Sistema (18) risulta soddisfatto.
Una volta accertata l'esistenza di una soluzione per il Sistema (18), si può scendere nel dettaglio per capire se la successione delle p equazioni in casca-ta, composte nella funzione T del Lemma precedente, converga eettivamente alla soluzione; quest'ultima sotto forma di autovettore per T . Prima di tutto va tenuto a mente che, come espresso dalla Proposizione (7.1), la convergenza secondo la metrica di Hilbert o di Thompson implica la convergenza in norma; questo giusti ca le operazioni di passaggio a limite per gli elementi degli insiemei Xi:
Teorema 7.4. Siano {Li : Xi → Xi+1}pi=1 continui, monotoni, omogenei di
grado 1 e tali che Li(IntKi) ⊂ IntKi. Sia di la metrica proiettiva di Hilbert su
IntKi.
Se esiste un j tale che ∆(Lj) < ∞ su IntKi allora la normalizzazione di
T ha un unico punto sso u ∈ IntK1 di norma unitaria (a meno di multipli
scalari)
T (u) kT (u)k = u
tale che per ogni z ∈ IntK1 la successione normalizzata converga ad esso
lim
k→∞
Tk(z) kTk(z)k = u
Dimostrazione. Prima di tutto si dimostra che T è contrattiva.
L'operatore Ui è antitono e omogeneo di grado −1, pertanto Ui è
non-espansivo per il Corollario (7.1)
Similmente l'operatore Li è monotono e omogeneo di grado 1, quindi Li è
non-espansivo sempre per il Corollario (7.1)
di+1(Lix, Liy) ≤ di(x, y) ∀x, y ∈ IntKi
Per ipotesi esiste un j tale che ∆(Lj) < ∞. Inoltre per il Teorema (7.3) esiste
una costante di contrazione C ∈ [0, 1) tale che dj+1(Ljx, Ljy) ≤ Cdj(x, y) ∀x, y ∈ IntKj
Combinando la prima e la terza disuguaglianza si ottiene d1(T (x), T (y)) ≤ Cd1(x, y) ∀x, y ∈ IntK1
ovvero che T è contrattiva su IntK1.
Per applicare il Teorema del punto sso di Banach è necessario che IntK1
sia uno spazio metrico completo. Quindi ci si riconduce su Σ1= {x ∈ IntK1 : kxk = 1}
con cui, applicando il Teorema (7.2) nell'ipotesi che la norma sia monotona, si ha la completezza di (Σ1, d1).
De nendo la normalizzazione si T g(z) = T (z)
kT (z)k
si ha quindi che g(IntK1) ⊆ Σ1. Da cui anche g risulta contrattiva su IntK1.
Applicando il Teorema di punto sso allora ne segue che g ha un unico punto sso u ∈ Σ1, ma pure che si ha convergenza globale ad esso, ossia per
ogni z ∈ IntK1vake
lim
k→∞g
k(z) = u
Ora basta applicare l'omogeneità di T a nche gk(z) = Tk(z)
kTk(z)k e ne risulti così
la tesi.
Adesso si può nalmente provare il risultato principale della sezione, relativo alla convergenza di T per iterazioni non-normalizzate, restringendosi a p pari, di cui il Sistema (35) è un caso particolare:
Teorema 7.5. Siano {Li : Xi → Xi+1}pi=1 continui, monotoni, omogenei di
grado 1 e tali che Li(IntKi) ⊂ IntKi.
Se T è non espansiva, p pari e
T (u) = u
Allora per ogni z ∈ IntK1 esiste λ(z) > 0 tale che
lim
k→∞T
Dimostrazione. Se p è pari T risulta essere monotona ed omogenea di grado 1. Dalla non-espansività di T rispetto alla metrica dT e da T (u) = u, la successione
dT(Tk(z), T (u))è non crescente e non negativa al variare k; quindi la successione
ammette limite lim
k→∞dT(T
k(z), T (u)) = ` (20)
Se ` = 0 allora si ottiene la tesi, limk→∞Tk(z) = ucon λ(z) = 1.
Se ` > 0 si applica la disuguaglianza triangolare per dT alla distanza tra la
sequenza normalizzata e quella originale, spezzando nel punto sso u dT Tk(z), T k(z) kTk(z)k ≤ dT Tk(z), u + dT u, T k(z) kTk(z)k
dunque per l'Equazione (20) il primo addendo vale ` e per il Teorema (7.4) il secondo si annulla, quindi
lim k→∞dT Tk(z), T k(z) kTk(z)k = `
La distanza dT gode della proprietà dT(v, αv) = | log(α)|per ogni v ∈ IntK
e α > 0. Ponendo v = Tk(z)e α = kTk(z)k−1 si ha che
` = log kTk(z)k−1 = log 1 − log kTk(z)k
log kTk(z)k
quindi si hanno due casi, a seconda del segno lim
k→∞kT
k(z)k ∈ {e`, e−`}
Se il limite fosse e−`, essendo ` > 0 per ipotesi, allora si avrebbe la tesi.
Altrimenti è possibile supporre che per una qualche sottosuccessione ki→ ∞
si abbia lim
i→∞kT
ki(z)k = e` (21)
e si cerca di dimostrare per la successione di partenza che kTk(z)k → e`e quindi
Tk(z) → e`u.
Intanto si dimostra la convergenza della sottosuccessione, infatti dal Teorema (7.4) si ha che ogni sottosuccessione di Tk(z)/kTk(z)ktende a u, quindi anche
Tki(z)/kTki(z)k per i → ∞; il denominatore tende a e` per l'Equazione (21),
per cui lim
i→∞T
Per l'omogeneità di T vale T (cu) = cu, quindi cu è punto sso di T per ogni costante c. Siccome T è non-espansiva allora per ogni q ≥ ki si ha
dT Tq(z), e`u = dT Th(Tki(z)), T (e`u) ≤ dT Tki(z), e`u
ma per l'Equazione (22) il membro di destra tende a 0 per i → ∞ e di conse-guenza il limite del membro di sinistra è anch'esso limitato superiormente da 0 (oltre che inferiormente, per de nizione di dT), perciò si ha la tesi:
lim
q→∞T
q(z) = e`u
dove λ(z) := e`> 0.
Quindi l'applicazione T , nel caso in cui p = 2, corrisponde all'operatore di Menon introdotto nella Sezione precedente. Infatti essendo gi = Ui+1Li, in
questo caso si ha
T = g2g1= U3L2U2L1= U1L2U2L1= U ATU A
perciò il Teorema appena enunciato diviene un risultato di convergenza globale verso il punto sso dell'operatore di Menon, ossia per il Metodo (16). Una volta ottenuto il punto sso u, si può costruire la matrice S = D(UAu)AD(u) doppiamente stocastica richiesta dal Teorema (2.1) e così facendo risolvere il problema di bilanciamento.
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 vol-ta soddisfatte per la Proposizione (3.1) nell'ipotesi che A sia complevol-tamente 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 de nizione 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
