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'iterazione 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.