Automi Ibridi

(1)

Automi Ibridi

Carla Piazza¹

1Dipartimento di Matematica ed Informatica Universit `a di Udine

carla.piazza@dimi.uniud.it

(2)

Indice del Corso (Dis)Ordinato

Automi Ibridi: Sintassi e Semantica Sistemi a stati finiti(breve ripasso) Il problema dellaRaggiungibilit `a Risultati diIndecidibilit `a

Classinotevoli di Automi Ibridi: timed, rectangular, o-minimal, . . . Tecniche di Decisione:(Bi)Simulazione, Cylindric Algebraic Decomposition, Teoremi di Selezione, Semantiche approssimate Equazioni Differenziali

. . . e tanto altro:

Logiche temporali Composizione di Automi Il caso Stocastico

Stabilit à, Osservabilit à, Controllabilit à Strumenti Software

Applicazioni

(3)

Equazioni differenziali

Definition (Equazioni Differenziali)

Un’equazione differenziale `e un’equazione che stabilisce una relazione tra una funzione incognitaf : R → Re le sue derivate Unsistema di equazioni differenziali `e un’insieme di equazioni che stabiliscono relazioni trak funzioni incognitef_i : R → Re le loro derivate

Example

X⁰=X oppure dX

dT =X (T ) che ha come soluzioni

X (T ) = e^T

X (T ) = k ∗ e^T conk costante

(4)

Classificazione delle Equazioni Differenziali

ordinarieo alle derivate parziali (tipo di derivate) del primo ordine o di ordinen(grado delle derivate) in formaesplicitao implicita

linearionon lineari autonomionon autonomi

In questa lezione useremo le notazioni:

X per indicare una variabile/un vettore di variabili X⁰per indicare la derivata prima diX

X⁰=F (X , T )per indicare un’equazione/sistema di equazioni differenziali

(5)

Da ordine n a primo ordine

Osservazione

Da un’equazione di ordinen

F (X⁽ⁿ⁾,X⁽ⁿ⁻¹⁾, . . . ,X⁰,X ) = 0

posso passare a unsistemadinequazioni del primo ordine











X⁰ = Y₁

Y₁⁰ = Y₂

. . .

Y_n−1⁰ = Y_n

F (Y_n,Y_n−1, . . . ,Y₁,X ) = 0

(6)

Da Integrali a Equazioni Differenziali

Un’equazione differenziale molto semplice

X⁰ =F (T ) Si trova una soluzione integrando

X (T ) = Z

F (T )dT E unica?`

(7)

Da Integrali a Equazioni Differenziali

X (T ) = Z

F (T )dT E unica?`

(8)

Da Integrali a Equazioni Differenziali

X (T ) = Z

F (T )dT E unica?`

(9)

Esempio

X⁰ =4T²− 5T + 1 Una soluzione `e

X (T ) = 4 ∗1

3T³− 5 ∗ 1

2T²+T Un’altra soluzione `e

X (T ) = 4 ∗1

3T³− 5 ∗ 1

2T²+T + 3

Due soluzioni differiscono per una costante ovvero devo specificareX (0) = X₀

(10)

Esempio

X (T ) = 4 ∗1

3T³− 5 ∗ 1

X (T ) = 4 ∗1

3T³− 5 ∗ 1

2T²+T + 3

(11)

Esempio

X (T ) = 4 ∗1

3T³− 5 ∗ 1

X (T ) = 4 ∗1

3T³− 5 ∗ 1

2T²+T + 3

(12)

Esempio

X (T ) = 4 ∗1

3T³− 5 ∗ 1

X (T ) = 4 ∗1

3T³− 5 ∗ 1

2T²+T + 3

(13)

Problema di Cauchy

Definition (Problema di Cauchy)

Trovare una soluzione di un’equazione differenziale di ordinen F (X⁽ⁿ⁾,X⁽ⁿ⁻¹⁾, . . . ,X⁰⁰,X⁰,X , T ) = 0

che soddisfi le condizioni iniziali

X⁽ⁿ⁻¹⁾(t₀) =x_n−1, . . . ,X⁰(t₀) =x₁,X (t₀) =x₀

(14)

Campo Vettoriale

Definition (Campo Vettoriale)

Un campo vettoriale `e una funzioneF che associa ad ogni punto inR^k (o in un suo sottoinsieme) un vettore (tangente)

(15)

Campi Vettoriale ed Equazioni Differenziali

Uncampo vettorialecorrisponde ad un’equazione differenziale

il campo vettoriale descrive le direzioni delle traiettorie nellospazio delle fasi

il vettoreF (p)indicala direzione e l’intensit `a della derivata di una funzione incognitaf nel puntop

in un campo vettorialela direzione e l’intensit `a della derivatadipende dal punto, ma non dal tempo, quindi si tratta di un’equazioneautonoma

(16)

Domande

Dato un sistema di equazioni differenziali Quando esistealmeno una soluzione?

Quando esisteuna sola soluzione?

Chepropriet `ahanno le soluzioni?

Come letrovo/approssimo?

Concentriamoci su sistemiordinaridelprimo ordinein forma esplicitaeautonomi











X₁⁰ = F₁(X₁, . . . ,X_n) X₂⁰ = F₂(X₁, . . . ,X_n) . . .

X_n⁰ = Fn(X₁, . . . ,Xn)

(17)

Non Esistenza

Osserviamo che:

la soluzione di un’equazione differenziale `e differenziabile e quindicontinua

esistono funzioni differenziabili che hanno derivata discontinua (e.g.,X (T ) = T²sin(1/T ))

le derivate sono sempre funzioni diDarboux(soddisfano il teorema del valor medio)

Quindi il sistema

X⁰ =

0 X ≤ 0 1 X ≥ 0 non ha soluzioni

(18)

Non Esistenza

Osserviamo che:

Quindi il sistema

X⁰ =

(19)

Non Esistenza

Osserviamo che:

Quindi il sistema

X⁰ =

(20)

Non Esistenza

Osserviamo che:

Quindi il sistema

X⁰ =

(21)

Esistenza

Theorem (Esistenza Locale)

Consideriamo il problema di Cauchy

X⁰ =F (X , T ) X (t₀) =x₀

SeF `econtinua(in un intorno di(x₀,t₀)), allora esiste una soluzionelocaledel problema di Cauchy

Non `e garantita l’unicit `a

(22)

Esistenza

Theorem (Esistenza Locale)

X⁰ =F (X , T ) X (t₀) =x₀

SeF `econtinua(in un intorno di(x₀,t₀)), allora esiste una soluzionelocaledel problema di Cauchy

Non `e garantita l’unicit `a

(23)

Pennello di Peano

X⁰=3X^2/3 X (0) = 0 Una soluzione `e

X (T ) = 0 Un’altra soluzione `e

X (T ) = T³ Combinando le due ottengo infinite soluzioni

(24)

Pennello di Peano

(25)

Pennello di Peano

(26)

Pennello di Peano

(27)

Unicit `a

Definition (Funzioni Lipschitziane)

Una funzionef si dicelipschitzianase esistek tale che

|f (x) − f (y )| ≤ k |x − y |

(28)

Unicit `a

Theorem (Esistenza e Unicit `a Locale) Consideriamo il problema di Cauchy

X⁰ =F (X , T ) X (t₀) =x₀

SeF `econtinua e lipschitziana(in un intorno di(x₀,t₀)), allora esiste ed `e unica una soluzionelocaledel problema di Cauchy

(29)

Propriet `a

Le soluzioni dei sistemiautonomi continui lipschitziani X⁰ =F (X )sono tali che:

seF (p) = 0, allorap `e un punto di equilibrio eX (T ) = p `e una soluzione

se una soluzione arriva in un punto di equilibrio,non si muove pi `u

se una soluzione passaduevolte per lo stesso punto, allora ci passainfinitevolte

se due soluzioni siincrociano,non si separanopi `u setraslonel tempo una soluzione ottengo un’altra soluzione

(30)

Esempio: Lotka-Volterra

Consideriamo il sistema

X⁰ = (a − bY )X Y⁰ = (cX − d )Y

(31)

Esempio: Lotka-Volterra

X⁰ = (a − bY )X Y⁰ = (cX − d )Y

I punti di equilibrio si ottengono risolvendo il sistema

0 = (a − bY )X 0 = (cX − d )Y e sono(0, 0)e(d /c, a/b)

(32)

Esempio: Lotka-Volterra

X⁰ = (a − bY )X Y⁰ = (cX − d )Y Le traiettorie nello spazio delle fasi sono

(33)

Esempio: Lotka-Volterra

X⁰ = (a − bY )X Y⁰ = (cX − d )Y Le traiettorie nel tempo sono

(34)

Come si integrano/approssimano?

Esistono

metodi diintegrazione esattiper classi ristrette tecniche dianalisi qualitativa

metodi diintegrazione numerica:

Eulero, Runge-Kutta, . . . sviluppo inserie di Taylor

(35)

Metodo di Eulero

X⁰ =F (X , T ) X (t₀) =x₀

Idea: approssimoX (t₀+ δ)con il valore della retta perx₀ avente coefficiente angolareF (X (t₀),t₀)

X (t₀+ δ) ≈x₀+F (x₀,t₀) ∗ δ

Problema: pi ùδ è grande pi ù l’approssimazione è grande Soluzione: usoδ piccolo eitero

X (t₀) =x₀

X (t₀+ δ) =X (t₁) ≈x₀+F (x₀,t₀) ∗ δ =x₁ X (t₀+2δ) = X (t₂) ≈x₁+F (x₁,t₁) ∗ δ =x₂ . . .

(36)

Metodo di Eulero

X⁰ =F (X , T ) X (t₀) =x₀

X (t₀+ δ) ≈x₀+F (x₀,t₀) ∗ δ

X (t₀) =x₀

(37)

Metodo di Eulero

X⁰ =F (X , T ) X (t₀) =x₀

X (t₀+ δ) ≈x₀+F (x₀,t₀) ∗ δ

X (t₀) =x₀

(38)

Esempio

(39)

Domande

Possostimarel’approssimazione?

Possomigliorare/generalizzareil metodo?

(40)

Sviluppo in serie di Taylor

Theorem (Taylor con Resto di Lagrange) Siaf : R → Rdi classeC^∞

f (t) =

n

X

k =0

f^{(k )}(t₀)

k ! (t − t₀)^k+f^{(k +1)}(ξ)

(k + 1)!(t − t₀)ⁿ⁺¹ conξ ∈ [t₀,t]

Nel nostro caso seF `e di classeC^∞: calcoloX⁰(t0) =F (x0,t0)

determinoX⁰⁰=F⁰(X , T ) ∗ X⁰ =F⁰(X , T ) ∗ F (X , T ) calcoloX⁰⁰(t₀)

. . .

(41)

Esempio

X⁰ =X² X (0) = x₀

Approssimiamo la soluzione con lo sviluppo in serie di Taylor X⁰(0) = x₀²

X⁰⁰=2 ∗ X ∗ X⁰ =2 ∗ X³e quindiX⁰⁰(0) = 2 ∗ x₀³ X⁰⁰⁰ =6 ∗ X²∗ X⁰ =6 ∗ X⁴e quindiX⁰⁰⁰(0) = 6 ∗ x₀⁴ Quindi

X (T ) ≈ x₀+x₀²∗ T + 2 ∗x₀³

2 T²+6x₀⁴ 6 T³

(42)

Esempio

X⁰ =X² X (0) = x₀

X (T ) ≈ x₀+x₀²∗ T + 2 ∗x₀³

2 T²+6x₀⁴ 6 T³

(43)

Esempio

X⁰ =X² X (0) = x₀

X (T ) ≈ x₀+x₀²∗ T + 2 ∗x₀³

2 T²+6x₀⁴ 6 T³

(44)

Osservazioni

il metodo pu `o essere implementatosimbolicamente

ipolinomimi permettono di approssimare arbitrariamente bene “qualsiasi” soluzione di equazione differenziale