RAGGIUNGIBILITA’ E RAGGIUNGIBILITA’ DEBOLE

DEI SISTEMI POSITIVI A TEMPO DISCRETO

Maria Elena ValcherUniversita’ di Padova

Bertinoro, 10-11 Luglio 2006

PRELIMINARI SUI CONI

Un insieme K in Rn e’ detto CONO se

Un cono K in Rn e’ detto PROPRIO se§ Convesso§ Pointed, i.e.§ Solido, i.e. il piu’ piccolo sottospazio vettoriale di Rn

che contiene K e’ Rn stesso.Un cono K e’ detto POLIEDRICO se ammette un numero

finito di generatori, ovvero esistono v1, v2,…,vN in K tali che

v K v K, 0

v K e v K v 0

K { v ic i,c i 0} Cone v1 ... vN i1

N

PRELIMINARI SUI VETTORI NON NEGATIVI

Indichiamo con ei, i=1,2,…,n, l’i-esimo vettore della BASE CANONICA in Rn, ovvero il vettore le cui componenti sono tutte nulle ad eccezione della i-esima che vale 1. Ad esempio, in R4

Un vettore v viene detto i-MONOMIO se v = ei per qualche > 0.

Una matrice quadrata M viene detta MONOMIA se M e’ una matrice non singolare le cui colonne sono n vettori monomi linearmente indipendenti. Ad esempio:

e3

0

0

1

0

M 0 5 0

2 0 0

0 0 0.5

SISTEMI POSITIVI A TEMPO DISCRETO

In questa presentazione consideriamo sistemi positivi a tempo discreto, descritti dall’equazione alle differenze del primo ordine:

dove x(t) e’ lo stato n-dimensionale, non negativo,u(t) l’ingresso m-dimensionale, non negativo,

A e B sono matrici non negative (nxn e nxm, rispettivamente).

Con riferimento a questo sistema dinamico introduciamo le definizioni di raggiungibilita’ e raggiungibilita’ debole.

x(t 1) Ax(t) Bu(t)

DEFINIZIONI DI RAGGIUNGIBILITA’

Un sistema positivo a tempo discreto e’:RAGGIUNGIBILE se per ogni stato xf > 0 esiste k e una

successione di ingresso u(0), u(1),…, u(k-1) a valori nonnegativi che porta lo stato da x(0)=0 a x(k)= xf;

RAGGIUNGIBILE IN SENSO DEBOLE se per ogni stato xf >> 0 esiste k e una successione di ingresso u(0), u(1),…, u(k-1) a valori nonnegativi che porta lo stato da x(0)=0 a x(k)= xf.

OSSERVAZIONE: nel caso di raggiungibilita’ debole gli stati che si trovano sul boundary dell’ortante positivo possono essere raggiunti o in un tempo finito o in un tempo infinito.

APPROCCIO ALGEBRICO ALLA RAGGIUNGIBILITA’ (1)

Introduciamo la MATRICE DI RAGGIUNGIBILITA’ IN k PASSI

E’ chiaro che lo stato al tempo k, ottenuto a partire da x(0)=0 applicando una successione di ingresso u(0), … , u(k-1) non negativa, e’ dato da

Pertanto xf e’ RAGGIUNGIBILE AL TEMPO k se e solo se xf

appartiene a

Rk B AB ... Ak 1B

x(k) Ak 1 iBu(i)i0

k 1

Rk Cone(Rk ) {x Rkc,c 0}

APPROCCIO ALGEBRICO ALLA RAGGIUNGIBILITA’ (2)

Chiaramente

Tuttavia poiche’ abbiamo a che fare con coni e non con sottospazi questa successione non e’ detto che raggiunga la saturazione, ovvero e’ possibile che

Se definiamo

e’ chiaro che il sistema =(A,B) e’ RAGGIUNGIBILE se e solo se

R1 R2 ...Rn Rn1 ... Rn

Rk Rk1,k N

R Rkk1

R Rn

APPROCCIO ALGEBRICO ALLA RAGGIUNGIBILITA’ (3)

PROPOSIZIONE 1: Il sistema e’ raggiungibile se solo se tutti i vettori della base canonica ei sono raggiungibili (MONOMIAL REACHABILITY).

Sia ki il numero di passi necessario per raggiungere il vettore e i e sia k = max ki. Allora e’ chiaro che

§ ogni vettore ei e’ raggiungibile in k passi

§ ogni vettore xf non negativo e’ raggiungibile in k passi

§ se una combinazione non negativa di vettori vk non negativi genera un vettore monomio e.g. ei, allora almeno uno dei vk e’ un vettore i-monomio.

PROPOSIZIONE 2: Il sistema e’ raggiungibile se solo se esiste k tale che la matrice di raggiungibilita’ in k passi Rk contiene una sottomatrice nxn monomia.

APPROCCIO ALGEBRICO ALLA RAGGIUNGIBILITA’ (4)

Ecco le buone notizie!

PROPOSIZIONE 3: Il sistema e’ raggiungibile se solo se la matrice di raggiungibilita’ in n passi Rn contiene una sottomatrice nxn monomia.

APPROCCIO MEDIANTE GRAFI ALLA RAGGIUNGIBILITA’ (1)

Consideriamo un sistema positivo =(A,B) di dimensione n con m ingressi. A tale sistema possiamo associare un GRAFO D’INFLUENZA G(A,B) con

§ n VERTICI v1, v2,…, vn

§ m SORGENTI s1,s2,…,sm

§ arco (j,i) da vj a vi se [A]ij > 0

§ arco (j,i) da sj a vi se [B]ij > 0

Esiste un cammino dalla sorgente sj al vertice vi di lunghezza k se e solo se Ak-1B ha la componente (i,j) positiva.Sia bj=colj (B), i.e. la colonna j-esima della matrice B.

Se Ak-1bj e’ un vettore i-monomio allora dalla sorgente sj in k passi posso raggiungere solo il vertice vi . In questo caso diciamo che esiste un CAMMINO DETERMINISTICO DI LUNGHEZZA k da sj a vi .

APPROCCIO MEDIANTE GRAFI ALLA RAGGIUNGIBILITA’ (2)

Possiamo allora riformulare la condizione di raggiungibilita’ in termini del grafo d’influenza G(A,B).

PROPOSIZIONE 4: Il sistema =(A,B) e’ raggiungibile se solo se per ogni i in {1,2,…,n} esiste un cammino deterministico da una qualche sorgente sj al vertice vi di lunghezza al piu’ n.

OSSERVAZIONE: se confiniamo la nostra attenzione al caso di grafi di influenza in cui non compaiano vertici privi di archi uscenti (= la matrice A non ha colonne nulle), possiamo considerare solo quei cammini che

§ partono da sorgenti che al primo passo raggiungono un solo vertice

§ rimangono deterministici ad ogni passo

APPROCCIO MEDIANTE GRAFI ALLA RAGGIUNGIBILITA’ (3)

In questo caso, l’algoritmo per determinare se un certo sistema positivo e’ raggiungibile o meno diventa particolarmente semplice:

1) si determinano tutti i cammini (di lunghezza al piu’ n) che partono da una qualche sorgente e rimangono deterministici ad ogni passo

2) si eliminano cammini o tratti di cammino che vengono duplicati

3) se in questo modo si e’ passati per ciascun vertice, allora il sistema e’ raggiungibile, in caso contrario non lo e’.

Questo tipo di ragionamento permette di ottenere una forma canonica a cui tutti i sistemi raggiungibili possono essere condotti:

APPROCCIO MEDIANTE GRAFI ALLA RAGGIUNGIBILITA’ (4)

PROPOSIZIONE 5: Un sistema =(A,B) in cui la matrice A sia priva di colonne nulle e’ RAGGIUNGIBILE se e solo se esistono una matrice di permutazione P e una matrice di selezione S tali che

dove

PAP T

A11 A12 ... A1k

A21 A22 ... A2k

Akk Ak2 ... Akk

PBST

B1 0 ... 0

0 B2 0 0 0 ... Bk

Aii

* 0

* 0 0

* 0 ... 0

Aij

* 0 ... 0

* 0 0

* 0 ... 0

,i j

B j

0

0

APPROCCIO MEDIANTE GRAFI ALLA RAGGIUNGIBILITA’ (5)

PROPOSIZIONE 6: Un sistema =(A,B) ad un solo ingresso in cui la matrice A sia priva di colonne nulle e’ RAGGIUNGIBILE se e solo se esiste una matrice di permutazione P tale che

PAP T

* 0

* 0 * 0 0

PB

0

0

RAGGIUNGIBILITA’ DEBOLE

Ricordiamo la definizione:DEFINIZIONE: Un sistema positivo a tempo discreto e’RAGGIUNGIBILE IN SENSO DEBOLE se per ogni stato xf >> 0

esiste k e una successione di ingresso u(0), u(1),…, u(k-1) a valori nonnegativi che porta lo stato da x(0)=0 a x(k)= xf.

Mentre la raggiungibilita’ e’ una proprieta’ strutturale, nel senso che dipende solo dalla struttura di zeri e non-zeri delle due matrici A e B, e per questa ragione viene completamente catturata dal grafo d’influenza G(A,B), la proprieta’ di raggiungibilita’ debole dipende non solo dalla struttura delle due matrici ma anche dai valori degli elementi della matrice A e, in particolare, dai raggi spettrali delle classi di comunicazione di G(A,B).

MATRICI RIDUCIBILI/IRRIDUCIBILI E CLASSI DI IRRIDUCIBILITA’ IN G(A,B)

(1)Data una matrice A non negativa di dimensioni nxn, diciamo che A e’ RIDUCIBILE se esiste una matrice di permutazione P tale che dove A11 e A22 sono due matrici quadrate.

In caso contrario, A e’ IRRIDUCIBILE.

Ogni matrice A riducibile puo’ essere ricondotta, attraverso un’opportuna matrice di permutazione P alla FORMA NORMALE DI FROBENIUS

dove ciascun blocco Aii e’ scalare oppure una matrice irriducibile.

PAP T A11 0

A21 A22

PAP T

A11

A21 A22

Ak1 Ak 2 ... Akk

MATRICI RIDUCIBILI/IRRIDUCIBILI E CLASSI DI IRRIDUCIBILITA’ IN G(A,B)

(2)In un grafo d’influenza diciamo che due vertici vi e vj COMUNICANO se esiste un cammino da vi a vj e un cammino da vj a vi . Il concetto di vertici “comunicanti” partiziona l’insieme{v1,…,vn} dei vertici in CLASSI DI COMUNICAZIONE.

Come possiamo evidenziare le classi di comunicazione?Se A e’ in forma normale di Frobenius, e’ immediato verificare che esiste una corrispondenza biunivoca tra classi di comunicazione e blocchi diagonali irriducibili Aii.

Chiamiamo RAGGIO SPETTRALE (o AUTOVALORE DI FROBENIUS) DELLA CLASSE DI COMUNICAZIONE i-esima (Ci) il raggio spettrale di Aii: (Aii).

D’altra parte se A non e’ in forma di Frobenius, esiste P di permutazione tale che PAPT lo e’ e i grafi d’influenza G(A,B) e G(PAPT,PB) coincidono. Pertanto definiamo ancora (Ci) =(Aii).

CARATTERIZZAZIONE DELLA RAGGIUNGIBILITA’ DEBOLE (1)

Sia I(A,B) l’insieme degli indici dei vettori monomi che compaiono tra le colonne di Rn. Se un sistema non e’ raggiungibile

Pertanto gli indici che non appartengono a I(A,B) corrispondono a vettori monomi che possono essere raggiunti non in un numero finito di passi, bensi’ solo asintoticamente.

PROPOSIZIONE 6: Un sistema = (A,B) e’ debolmente raggiungibile se e solo se per ogni > 0 esiste k() > 0 tale che nella matrice di raggiungibilita’ in k() passi esistono n colonne che (una volta normalizzate) differiscono dagli n vettori ei per meno di

I(A,B) {1,2,...,n}

Aki 1bn i

|| Aki 1bn i||

ei

i,1ki k(),1ni m

CARATTERIZZAZIONE DELLA RAGGIUNGIBILITA’ DEBOLE (2)

PROPOSIZIONE 6: Dato un sistema positivo = (A,B) sono fatti equivalenti:

1 = (A,B) e’ debolmente raggiungibile

(2) per ogni indice i non appartenente a I(A,B), vale

(2a) il vertice vi appartiene ad una classe di comunicazione C j di G(A,B) che consiste di un solo vertice oppure di h i vertici connessi in un singolo anello

(2b) esiste una colonna bni di B tale che per ogni intero t > n-1

il blocco di componenti di At bni relativo alla classe Cj e’ un vettore monomio. Inoltre per ogni classe C diversa da C j se il blocco di componenti di At bni relativo alla classe C e’ non nullo per qualche t, allora

e accede a

(C) (C j )

(C) (C j ) C C j

CARATTERIZZAZIONE DELLA RAGGIUNGIBILITA’ DEBOLE (3)

PROPOSIZIONE 7: Un sistema positivo ad un solo ingresso = (A,B) e’ debolmente raggiungibile se e solo se esiste una matrice di permutazione P tale che

dove aii+1> 0 per i=1,…,r-1,r+1,…,n-1, an1> 0, anr+1 > 0

aj1 > 0 per j< r+1 implica n-r divide j e il raggio spettrale del blocco diagonale inferiore e’ maggiore o uguale del raggio spettrale del blocco diagonale superiore.

PAP T

a11 a12

a21 a23

ar 11 ar 1r

ar1 0

0 0 ... 0 0 0 ar1r2

0 0 0 ar2r3

0 0 0 an 1n

an1 0 ... 0 0 anr1 0

PB

0

0

0

br

0

0

0

0

RAGGIUNGIBILITA’ SISTEMI POSITIVI A

COMMUTAZIONE A TEMPO DISCRETO

Maria Elena ValcherUniversita’ di Padova

Bertinoro, 11 Luglio 2006

PRELIMINARI SULLO ZERO PATTERN

Dato un vettore v in R+n, chiamiamo ZERO PATTERN di v, e

lo indichiamo con il simbolo ZP(v), l’insieme degli indici corrispondenti a componenti nulle del vettore v:

Similmente definiamo NONZERO PATTERN di v l’insieme delle componenti positive di v:

In modo analogo definiamo i concetti di zero pattern e nonzero pattern di una matrice non negativa A.

PROPRIETA’: 1)

2)

ZP(v) {i {1,2,...,n} : v i 0}

ZP(v) {i {1,2,...,n} : v i 0}

ZP(Av ) ZP(Aei)iZP(v )

ZP(A(v w)) ZP(Av ) ZP(Aw)

COSA SONO I SISTEMI A COMMUTAZIONE (SWITCHED)?

Un SISTEMA A COMMUTAZIONE e’ un sistema le cui equazioni descrittive commutano, secondo una legge tra piu’ modelli distinti, che catturano le leggi a cui il sistema obbedisce nelle diverse condizioni di funzionamento.

Un SISTEMA A COMMUTAZIONE A TEMPO DISCRETO, che commuti tra sottosistemi lineari, viene descritto da un’equazione alle differenze del tipo

dove la legge di commutazione viene definita su Z+ ed assume valori in un insieme P che, per semplicita’, supporremo finito

Per ogni i in P, Ai e’ matrice reale nxn, mentre Bi e’ matrice nxm.

x(t 1) A (t )x(t) B (t )u(t)

P {1,2,..., p}

COSA SONO I SISTEMI POSITIVI A COMMUTAZIONE (SWITCHED)?

Un SISTEMA POSITIVO A COMMUTAZIONE A TEMPO DISCRETO, viene descritto da un’equazione alle differenze del tipo

dove x(t) e’ lo stato n-dimensionale, non negativo,u(t) l’ingresso m-dimensionale, non negativo,

e per ogni i in P, Ai e’ matrice positiva nxn, e Bi e’ matrice positiva nxm.

Questi modelli emergono nella descrizione di sistemi positivi per i quali si possono ravvedere diverse condizioni di funzionamento, a ciascuna dei quali corrisponde un diverso modello descrittivo positivo.

x(t 1) A (t )x(t) B (t )u(t)

DEFINIZIONE DI RAGGIUNGIBILITA’ E DI INDICE DI RAGGIUNGIBILITA’

DEFINIZIONE: Un sistema positivo a commutazione viene detto RAGGIUNGIBILE se per ogni stato xf > 0 esistono

• un intero positivo k • una sequenza di commutazione a valori in P, e • una successione di ingresso u(0), u(1),…, u(k-1) a valori

nonnegativi che portano lo stato da x(0)=0 a x(k)= xf. Diciamo, allora, che xf

e’ raggiungibile in k passi.

DEFINIZIONE: Se un sistema positivo a commutazione e’ raggiungibile, definiamo suo INDICE DI RAGGIUNGIBILITA’ IR come il minimo numero di passi entro il quale siamo in grado di raggiungere ogni stato di R+

n:

IR supx0 min ,u0{numero di passi necessari per raggiungere x}

ESPRESSIONE DELLO STATO AL TEMPO k

Osserviamo preliminarmente che l’espressione dello stato al tempo k, a partire da x(0)=0, in corrispondenza alla sequenza di commutazione e alla successione di ingresso non negativa u(0),…,u(k-1), e’ data da

Se definiamo per compattezza per i< k-1

l’espressione precedente diventa:

x(k) B (k 1)u(k 1) A (k 1)B (k 2)u(k 2) ... A (k 1)A (k 2)...A (1)B (0)u(0)

A i

k 1 A (k 1)A (k 2)...A (i)

A k

k 1 In

x(k) B (k 1)u(k 1) A k 1

k 1B (k 2)u(k 2) ... A 1

k 1B (0)u(0)

MATRICI DI RAGGIUNGIBILITA’

Sia una sequenza di commutazione di lunghezza k, con cio’ intendendo che {0,1,...,k-1} P. Definiamo MATRICE DI RAGGIUNGIBILITA’ RELATIVA ALLA SEQUENZA DI LUNGHEZZA kla matrice

Definiamo MATRICE DI RAGGIUNGIBILITA’ IN k PASSIla matrice ottenuta giustapponendo le matrici di raggiungibilita’ relative a tutte le possibili sequenze di commutazione i di lungezza k a valori in P:

Rk () B (k 1) A k 1

k 1B (k 2) ... A 1

k 1B (0)

Rk Rk (1) Rk ( 2) ... Rk (N ) ,N Pk

STATI RAGGIUNGIBILI IN k PASSI

E’ importante evidenziare come l’insieme degli stati raggiungibili in k passi Rk in questo caso sia ancora un cono ma probabilmente non il cono che ci aspettiamo! Infatti

bensi’Anche nel caso di sistemi positivi a commutazione vale

e puo’ capitare che

Si ha raggiungibilita’ se e solo se dove

Rk Cone(Rk )

Rk Cone(Rk ( i)i1

N

)

R1 R2 ...Rn Rn1 ... Rn

Rk Rk1,k N

R Rkk1

R Rn

ALCUNE BRUTTE NOTIZIE (1)

(1) Un sistema puo’ essere raggiungibile senza che esista un upper bound sul numero di passi necessari per raggiungere ogni stato, ovvero IR puo’ essere infinito.

Attenzione: tutti gli stati vengono raggiunti in un numero finito di passi. Questo concetto e’ diverso dalla raggiungibilita’ debole!

(2) La MONOMIAL REACHABILITY, ovvero la possibilita’ di raggiungere, a partire da x(0)=0, attraverso un’opportuna sequenza di commutazione (di lunghezza k) e una successione di ingresso non negativa u(0),…,u(k-1), ogni vettore monomio e’ CONDIZIONE NECESSARIA ma NON SUFFICIENTE per la raggiungibilita’!

ALCUNE BRUTTE NOTIZIE (2)

(3) Nel caso di sistemi a commutazione (lineari ma non positivi) a tempo discreto, si dimostra che il sistema e’ raggiungibile se e solo se esiste una sequenza di commutazione di lunghezza finita k tale che

Purtroppo questo risultato non si estende al caso positivo e

rappresenta solo una CONDIZIONE SUFFICIENTE per la raggiungibilita’.

(4) Nemmeno la condizione piu’ debole che esista un numero finito di sequenze di commutazione 1 …, tali che

e’ necessaria ma solo SUFFICIENTE.

Span(Rk ()) Rn

Cone(R 1(1))Cone(R 2

( 2)) ...Cone(R N( N )) R

n

Cone(Rk ()) Rn

MONOMIAL REACHABILITY (1)

PROPOSIZIONE 8: Un sistema positivo a commutazione e’ MONOMIALLY REACHABLE se e solo se esiste un intero positivo k tale che la matrice di raggiungibilita’ in k passi Rk contenga una sottomatrice nxn monomia.

A questo punto uno puo’ sperare che almeno per la raggiungibilita’ dei vettori della base canonica (equivalentemente, dei vettori monomi) esista un upper bound sul numero massimo di passi necessari per poter raggiungere ciascuno di essi. Per fortuna cosi’ e’, anche se come upper bound e’ un po’ altino!

PROPOSIZIONE 9: Un sistema positivo a commutazione e’ MONOMIALLY REACHABLE se e solo se la matrice di raggiungibilita’ in 2n-1 passi contiene una sottomatrice nxn monomia.

MONOMIAL REACHABILITY (2)

Abbiamo sbagliato mira? Abbiamo trovato un upper bound molto conservativo? Fortunatamente/sfortunatamente no!

ESEMPIO: Sia W l’insieme (il vocabolario) di cardinalita’ 2n-2 formato da tutte la parole di lunghezza compresa tra 1 ed n-1, ottenute a partire dall’alfabeto {1,2,…,n} e ordinate secondo l’ordine lessicografico:

Definiamo la successione di 2n-1 vettori n-dimensionali {bj}j tali che

W {1,2,...,n,12,13,...,n 1n,....,12...n 1,...,23...n}

b0

1

1

1

1

b1

0

1

1

1

b2

1

0

1

1

b2n 2

1

0

0

0

MONOMIAL REACHABILITY (3)

Insomma b0 e’ il vettore di soli 1, mentre per j = 1, 2, …, 2n-2, bj e’ il vettore di zeri e 1 per il quale ZP(bj) coincide con la famiglia dei simboli della j-esima parola in W. Per semplicita’ lavoriamo in GF(2) invece che sui reali.

Definiamo ora una famiglia di matrici {Aj}j, j=1,2,…,2n-2, secondo la seguente legge:

E’ possibile dimostrare che se assumiamo (i)=i, per i=1,2,…,2n-2,

otteniamo per k = 1, 2, …, 2n-2

Cio’ equivale a dire che scegliendo come sistemi (Ai,b0) per i= 1, 2, …, 2n -2,otteniamo un sistema raggiungibile e quindi monomially

reachable.

[Ai]rc 0 se (r ZP(bi)) e (c ZP(bi 1))

1 altrimenti

A 1

k 1b0 bk 1

MONOMIAL REACHABILITY (4)

Esiste almeno un vettore monomio (il vettore e1) che viene raggiunto in esattamente 2n-1 passi e non prima.

Non esistono sequenze di commutazione di lunghezza inferiore che permettono di raggiungere e1.

Pertanto viene raggiunto l’UPPER BOUND DI 2n-1 PASSI!

CONCLUSIONI

(1) Lo studio dei sistemi positivi a commutazione e’ ancora allo stadio iniziale, tuttavia abbiamo gia’ evidenziato come valutare la raggiungibilita’ non sia facile ed in genere se un sistema e’ raggiungibile non e’ detto che IR sia finito.

(2) Lo studio della controllabilita’ a zero e’ stato portato avanti ed abbiamo ottenuto un algoritmo che permette di decidere in un numero finito di passi se un sistema e’ controllabile oppure no.

(3) La raggiungibilita’ debole rappresenta un campo completamente inesplorato.

GRAZIE PER LA VOSTRA ATTENZIONE(GRANDE ITALIA!)