Riprendiamo il sistema a tempo continuo dell’esempio 18. La funzione di trasferimento della cor-rispondente macchina ricorsiva M∆ `e data dalla (3.15) per cui M∆ evolve secondo la legge:
xn+1= xn(1 + ∆) , n = 0, 1, 2, ...
x0 = 1 (3.24)
E per quanto discusso nella sezione2.5, un tale sistema evolve deterministicamente dallo stato iniziale (x0, ˙x0) divergendo verso il punto all’infinito:
P∞ = lim
x→+∞ ˙x→+∞
(x, ˙x) (3.25)
L’evoluzione deterministica e divergente all’infinito `e ben visibile (grafico 3.11). L’orbita della
5 10 15 20 25 xn 5 10 15 20 25 xn+1
Figura 3.11: Il diagramma di K¨onig-Lemaray relativo alla macchina ricorsiva (3.24) con ∆ = 14. macchina `e
Ω∆= {(xn, (1 + ∆) xn)}n∈N (3.26)
Per ogni ∆ > 0 l’insieme (3.26) ha come unico punto di accumulazione il punto all’infinito P∞= lim
Tale punto `e un punto attrattivo per M∆, giacch`e: ∀x0 ∈ (0, +∞) , lim
n→+∞(xn, (1 + ∆) xn) = P∞
In altri termini, comunque assegniamo lo sato iniziale (x0, ˙x0), lo stato di M∆ tende a P∞. Tale circostanza si generalizza nel caso di qualunque una macchina ricorsiva
M∆ :
xn+1 = f∆(xn)
x0 ∈ X (3.27)
Abbiamo cos`ı dimostrato la seguente propriet`a: Propriet`a 20
P∗ `e un punto attrattivo per M∆
=⇒ (P∗ `e di accumulazione per Ω∆ ,
Si osservi che tale implicazione non `e invertibile. In altri termini, condizione necessaria ma non sufficiente affinch`e P∗ sia un punto attrattivo `e che P∗ sia di accumulazione per Ω∆.
Siamo ora in grado di ricostruire in software l’evoluzione di un sistema autonomo lineare omogeneo
˙x = − |α0| x x (0) = x0 ,
gi`a studiato nella sezione 2.5, dove abbiamo trovato la soluzione (decrescita esponenziale):
x (t) = x0e−τct , (3.28)
con τc = |α0|−1. La funzione di trasferimento della corrispondente macchina ricorsiva M∆`e: f∆(x) = (1 − ∆) x,
dove abbiamo assunto |α0| = 1. Facendo “partire” la macchina dallo stato iniziale x0 = 1 M∆:
xn+1 = (1 − ∆) xn
x0 = 1 , (3.29)
otteniamo l’evoluzione plottata in fig. 3.12, da cui vediamo che l’origine O (0, 0) del sistema di assi coordinati Oxnxn+1 `e di accumulazione per Ω∆= {(xn, (1 − ∆) xn)}n∈N, giacch`e:
lim
n→+∞(xn, (1 − ∆) xn) = (0, 0) , ∀x0 ∈ (0, +∞) (3.30) La (3.30) implica
∀Iδ(O) , ∃Pn(xn, (1 − ∆) xn) ∈ Ω∆∩ Iδ(O) − {Pn} ,
essendo Iδ(O) un intorno circolare di raggio δ centrato in O (0, 0). Ne consegue che O (0, 0) `e un punto attrattivo per la macchina ricorsiva (3.29). Tale conclusione `e in perfetto accordo con l’analisi nel dominio del tempo. Infatti, la soluzione (3.28) `e infinitesima all’infinito:
lim
t→+∞x (t) = 0
Ci`o si traduce in una propriet`a topologica notevole per la macchina ricorsiva (3.29) , nel senso che l’insieme degli stati ha un punto di accumulazione al finito. Utilizzando un linguaggio suggestivo
CAPITOLO 3. MACCHINE RICORSIVE 0.2 0.4 0.6 0.8 1.0 xn 0.2 0.4 0.6 0.8 1.0 xn+1
Figura 3.12: Evoluzione dinamica della macchina ricorsiva M∆=1/4 con funzione di trasferimento f∆(x) = (1 − ∆) x. Assegnato lo stato iniziale (x0 = 1, x1 = 1 − ∆), M∆ tende asintoticamente allo stato (0, 0).
ma efficace, la macchina M∆ – attraverso il diagramma 3.12 – permette di visualizzare un processo infinito in modo finito.
Consideriamo, ora, il caso della salita esponenziale. Come visto, il sistema dinamico `e: ˙x = − |α0| x + β0, con α0 6= 0, β0 > 0
da cui il problema di Cauchy:
˙x = 1 − x
x (0) = 0 , (3.31)
dove abbiamo assunto |α0| = 1, β0 = 1. La soluzione di (3.31) `e: x (t) = 1 − e−t,
mentre la funzione di trasferimento della corrispondente macchina ricorsiva M∆ `e: f∆(x) = (1 − ∆) x + ∆
Facendo “partire” la macchina dallo stato iniziale x0 = 0 M∆:
xn+1= (1 − ∆) xn+ ∆
x0 = 0 , (3.32)
plottata in fig. 3.13, da cui vediamo che M∆ evolve deterministicamente dallo stato iniziale (0, ∆) per convergere asintoticamente allo stato (1, 1), onde tale punto `e attrattivo:
lim
n→+∞(xn, (1 − ∆) xn+ ∆) = (1, 1)
I risultati trovati non sono altro che una conseguenza del Teorema 26. Pi`u precisamente e nel caso generale, si ricercano i cosiddetti punti fissi, ovvero gli (eventuali) zeri al finito della funzione F (x):
f∆(x) = x ⇐⇒ F (x) = 0, Supponiamo che F (x) sia dotata di uno zero al finito x∗, cosicch´e:
∃x∗ ∈ X | F (x∗) = 0 =⇒ ∃t∗ ∈ ¯R | x (t∗) = x∗,
essendo ¯R = [−∞, +∞] l’insieme ampliato dei numeri reali. E tenendo conto della (3.4), riesce: lim
t→t∗ d
dtx (t) = limx→x∗
F (x) = 0 Abbiamo i seguenti casi:
1. |t∗| < +∞ =⇒ t∗ `e punto estremale per la funzione x (t);
2. |t∗| = +∞ =⇒ Nello spazio delle configurazioni x ˙x, la retta orizzontale x = x∗ `e asintoto orizzontale2 per il grafico della funzione x (t). Cio`e:
lim
|t|→+∞x (t) = x∗
CAPITOLO 3. MACCHINE RICORSIVE 0.2 0.4 0.6 0.8 1.0 xn 0.2 0.4 0.6 0.8 1.0 xn+1
Figura 3.13: Evoluzione dinamica della macchina ricorsiva M∆=1/4(3.32). Assegnato lo stato iniziale (x0 = 0, x1 = ∆), M∆ tende asintoticamente allo stato (1, 1).
Ad esempio, nel caso della salita esponenziale `e F (x) = 1 − x,
per cui l’unico zero al finito di F (x) `e x∗ = 1. Lo stato del sistema “parte” dal punto iniziale P0(0, 1) ∈ Γ (F ), dove Γ (F ) `e il grafico F (x), cio`e la retta di equazione ˙x = 1 − x, per tendere asintoticamente al punto finale P∗(1, 0) ∈ Γ (F ). L’orbita del sistema `e:
Ω =(x, ˙x) ∈ R2 | 0 ≤ x ≤ x∗, ˙x = 1 − x ⊂ Γ (F ) , ovvero il segmento di estremi P0 e P∗ (cfr. fig. 3.14).
x* x
x 0 x
P0
P*
Figura 3.14: Orbita del sistema a tempo continuo regolato dall’equazione differenziale ˙x = 1 − x. Lo stato iniziale `e (x0 = 0, ˙x0 = 1). Il sistema evolve asintoticamente verso lo stato (x∗, 0).
Abbiamo considerato macchine ricorsive lineari, cio`e corrispondenti a sistemi a tempo continui governati da un’equazione differenziale lineare. Consideriamo ora un sistema non lineare, ad esempio:
˙x = F (x) x (t0) = x0 , (3.33) con F (x) = cos x − x, ∀x ∈h0,π 2 i , (3.34)
che `e lipschitziana con coefficiente α = 2. Grafichiamo tale funzione in fig. 3.15, da cui vediamo la presenza di uno zero x∗, radice dell’equazione
cos x = x, che pu`o essere risolta per via numerica, ottenendo
x∗ ≃ 0.739085
Lo stato del sistema “parte” dal punto iniziale P0(x0, F (x0)) ∈ Γ (F ) per tendere asintoticamente al punto finale P∗(x∗, 0) ∈ Γ (F ). L’orbita del sistema `e:
CAPITOLO 3. MACCHINE RICORSIVE Π 2 x* x0 x 1 -1 x 0 x P0 P*
Figura 3.15: Orbita del sistema a tempo continuo regolato dall’equazione differenziale ˙x = cos x − x. Lo stato iniziale `e x0 = 0.2.
ovvero l’arco di curva Γ (F ) di estremi P0 e P∗ (cfr. fig. 3.15). Si noti che abbiamo supposto x0
∈ (0, x∗).
La suddetta analisi `e confermata da un’integrazione numerica dell’equazione differenziale ˙x = cos x − x con la condizione iniziale x (0) = x0, ottenendo (per x0 = 0.2) la soluzione graficata in3.16, da cui vediamo:
lim
t→+∞x (t) = x∗, (3.35)
Tale comportamento asintotico `e indipendente da x0, come risulta dai grafici di fig. 3.17
2
t x0=0.2
x*
x
Figura 3.16: Grafico della soluzione del problema di Cauchy (3.33). Nel linguaggio delle orbite, tali conclusioni si traducono nel grafico di fig. 3.18. Conclusione 21 Comunque assegniamo lo stato iniziale x0 ∈0,π2 del sistema
˙x = cos x − x
t
x*
x
Figura 3.17: Grafico della soluzione del problema di Cauchy (3.33) per diversi valori dello stato iniziale x0. Π 2 x* x0 x 1 -x1 0 x P0 P*
Figura 3.18: Orbita del sistema a tempo continuo regolato dall’equazione differenziale ˙x = cos x − x. Lo stato iniziale `e x0 = 1.2.
CAPITOLO 3. MACCHINE RICORSIVE lo stato (x, ˙x) converge a P∗(x∗, 0): lim t→+∞(x (t) , ˙x (t)) = (x0, 0) , ∀x0 ∈h0,π 2 i
Al sistema (3.36) corrisponde la macchina ricorsiva M∆ con funzione di trasferimento:
f∆(x) = x (1 − ∆) + ∆ cos x, (3.37)
e per quanto precede:
f∆(x) = x ⇐⇒ x = x∗ ≃ 0.739085 L’evoluzione dinamica `e retta dall’equazione di ricorrenza:
xn+1 = xn(1 − ∆) + ∆ cos xn, n = 0, 1, 2, ...
E il diagramma di K¨onig-Lemaray `e mostrato in fig. 3.19, da cui vediamo che lo stato del sistema tende asintoticamente a x∗. 0.5 1.0 Π2 xn 0.5 1.0 1.5 xn+1
Figura 3.19: Il diagramma di K¨onig-Lemaray relativo al sistema a tempo discreto con funzione di trasferimento f1/4(x) = 3
4x +1 4cos x.
Se invece poniamo ∆ = 1, la funzione di trasferimento si scrive: f1(x) = cos x,
0.5 1.0 Π2 xn 0.5 1.0 1.5 xn+1
Figura 3.20: Il diagramma di K¨onig-Lemaray relativo al sistema a tempo discreto con funzione di trasferimento f1(x) = cos x.
CAPITOLO 3. MACCHINE RICORSIVE 0.5 1.0 Π2 xn 0.5 1.0 1.5 xn+1
Figura 3.21: Il diagramma di K¨onig-Lemaray relativo al sistema a tempo discreto con funzione di trasferimento f1(x) = cos x, avendo assunto come stato iniziale x0 = 0.4.
0.5 1.0 1.5 xn 0.2 0.4 0.6 0.8 1.0 xn+1
Figura 3.22: Il diagramma di K¨onig-Lemaray relativo al sistema a tempo discreto con funzione di trasferimento f1(x) = cos x, avendo assunto come stato iniziale x0 = 1.4
CAPITOLO 3. MACCHINE RICORSIVE
e otteniamo il diagramma di fig. 3.20.
Rimane poi confermata l’indipendenza dallo stato iniziale, come mostrato nei grafici riportati nelle figg. 3.21-3.22. Abbiamo, quindi:
lim
n→+∞xn= x∗, ∀x ∈h0,π 2 i
ovvero la successione {xn} converge a x∗. Cio`e: lim
n→+∞Pn= P∗(x∗, x∗) ,
Ne consegue che P∗(x∗, x∗) `e punto di accumulazione per l’orbita Ω∆e per la propriet`a20`e un punto attrattivo.
D’ora in avanti, assumiamo definitivamente ∆ = 1, lasciando cadere l’indice ∆ nelle rispettive notazioni. Premettiamo la seguente definizione:
Definizione 22 Una contrazione di [a, b] ⊂ R `e una funzione f : [a, b] → R tale che ∃µ ∈ (0, 1) | |f′(x)| ≤ µ, ∀x ∈ [a, b]
Proposizione 23
f `e una contrazione di [a, b] =⇒ f ([a, b]) ⊂ [a, b] , essendo f ([a, b]) il codominio di f , i.e. l’immagine di [a, b] attraverso f . Dimostrazione. Per il teorema di Lagrange:
x′, x′′ ∈ [a, b] =⇒ ∃ξ ∈ (x′, x′′) | f (x ′′) − f (x′) x′′− x′ = f′(ξ) Cio`e: ∀x′, x′′∈ [a, b] , |f (x′′) − f (x′)| = |f′(ξ)| · |x′′− x′| ≤ µ |x′′− x′| < µ∈(0,1)|x′′− x′| (3.38) Quindi: |f (b) − f (a)| < |b − a| = b − a, da cui l’asserto.
Osservazione 24 La proposizione appena dimostrata giustifica la definizione 22, giacch`e una con-trazione di [a, b] riduce le distanze ( |f (x′′) − f (x′)| < |x′′− x′|).
Osservazione 25 Le asserzioni seguenti sono equivalenti: • f `e una contrazione di [a, b]
• f `e lipschitziana di coefficiente µ ≤ 1
Teorema 26 Teorema del punto fisso di Brouwer
f `e una contrazione di [a, b] =⇒ ∃!x∗ ∈ [a, b] | f (x∗) = x∗ (3.39) In altri termini, se f `e una contrazione di [a, b], l’equazione f (x) = x `e compatibile e determinata in [a, b]. Inoltre, la successione ricorsiva {xn}n∈N definita da
xn+1 = f (xn) , con x0 ∈ [a, b] (3.40)
converge alla radice x∗:
lim
Dimostrazione. Poniamo g (x) = x − f (x), onde:
g′(x) = 1 − f′(x) ≥ 1 − µ > 0, (3.42)
giacch`e `e per ipotesi −µ ≤ f′(x) ≤ µ con 0 < µ < 1. Per la proposizione 23 `e f ([a, b]) ⊂ [a, b]. Senza perdita di generalit`a, se f (a) < f (b) =⇒ [f (a) , f (b)] ⊂ [a, b], quindi:
g (a) = a − f (a) < 0, g (b) = b − f (b) > 0
Dunque, g `e continua in [a, b] ed assume valori di segno opposto agli estremi dell’intervallo [a, b]. Per il teorema di esistenza degli zeri, esiste almeno un punto x∗ ∈ [a, b] tale che g (x∗) = 0. Ma tale punto `e unico, in forza della monotonia della funzione g (x) (eq. 3.42). Perci`o:
∃!x∗ ∈ [a, b] | g (x∗) = 0 =⇒ ∃!x∗ ∈ [a, b] | f (x∗) = x∗
Dimostriamo la seconda parte del teorema. Assegnando ad arbitrio un punto iniziale x0 ∈ [a, b], iteriamo: x1 = f (x0) x2 = f (x1) ... xn = f (xn−1) ...
Abbiamo cos`ı costruito la successione {xn}n∈N. I casi possibili sono: 1. ∃ν ∈ N | xν+1 = f (xν) = xν =⇒ ∀n > ν, xn= xν =⇒ limn→+∞xn= xν = x∗ 2. ∄ν ∈ N | xν+1 = f (xν) = xν
Per il teorema di Lagrange:
∀k > 1, ∃ξk ∈ (xk−1, x∗) | |xk− x∗| = |f (xk−1) − f (x∗)| = f′(ξk) |xk−1− x∗| ≤ µ |xk−1− x∗| < |xk−1− x∗|
Cio`e:
|xk− x∗| < |xk−1− x∗| , ∀k > 1,
da cui segue che la successione {|xn− x∗|} `e strettamente decrescente. Inoltre: |x1− x∗| ≤ µ |x0 − x∗| |x2− x∗| ≤ µ |x1 − x∗| ≤ µ2|x0− x∗| ... |xn− x∗| ≤ µn|x0− x∗| ≤ µn(b − a) Risulta: lim n→+∞µn= 0, giacch`e `e 0 < µ < 1. Quindi: lim n→+∞µn(b − a) = 0 =⇒ limn→+∞|xn− x∗| = 0
CAPITOLO 3. MACCHINE RICORSIVE
Osserviamo che il punto x∗ ∈ [a, b] `e invariante rispetto all’azione della contrazione f. Per tale ragione, x∗ si chiama punto fisso di f (fixed point). Tale definizione si generalizza a una qualunque funzione f che non sia necessariamente una contrazione.
Definizione 27 Un punto fisso di una macchina ricorsiva M con funzione di trasferimento f, `e una radice dell’equazione f (x) = x.
La proposizione (23) e il teorema (26) hanno una semplice interpretazione geometrica. Precisa-mente, il grafico di una contrazione f : [a, b] → R ha una pendenza < 1. Ad esempio, se consideriamo la trasformazione identica di [a, b] :
f : [a, b] → R, f : x → x, ∀x ∈ [a, b] ,
vediamo che f non `e una contrazione, poich`e |f′(x)| = 1, ∀x ∈ [a, b]. E infatti, risulta: f ([a, b]) = [a, b]. Il caso opposto a quello della trasformazione identica `e dato dalla contrazione degenere, ovvero dalla trasformazione costante:
f : [a, b] → R, f : x → c, ∀x ∈ [a, b] ,
dove c `e una costante reale. Risulta f′(x) = 0, per cui f `e una contrazione di [a, b]. `E degenere, poich`e f ([a, b]) = {c}, cio`e contrae l’intervallo [a, b] nell’insieme {c}.
Conclusione 28 Dal teorema (26) segue che condizione sufficiente affinch`e l’equazione f (x) = x sia compatibile e determinata, `e che f sia una contrazione. Incidentalmente, se f `e la trasformazione identica, l’equazione f (x) = x risulta compatibile e indeterminata, giacch`e ∀x ∈ [a, b] `e soluzione. Se invece f `e un contrazione degenere di [a, b], l’unica soluzione di f (x) = x `e la costante c.
Utilizzando un linguaggio intuitivo ma efficace, possiamo dire che le contrazioni sono una “via di mezzo” tra la trasformazione identica e la contrazione degenere3.
Definizione 29 Una funzione f `e una contrazione locale di [a, b] se esiste un intervallo [ξ<, ξ>] ⊂ [a, b] tale che f `e una contrazione di [ξ<, ξ>].
In generale, dobbiamo distinguere i due casi:
1. f′(x) > 0, cosicch`e la funzione risulta crescente in [a, b]. Se assumiamo come punto iniziale x0 < x∗, si ha che la successione {xn} `e crescente. Viceversa, se si parte da x0 > x∗, la successione {xn} `e decrescente.
2. f′(x) < 0, cosicch`e la funzione risulta decrescente in [a, b].
Ritornando all’esempio visto in inizio paragrafo, vediamo che f (x) = cos x `e una contrazione di 0,π2, poich`e |f′(x)| = |sin x| < 1, ∀x ∈ 0,π2. Per quanto precede, l’equazione cos x = x `e compatibile e determinata in 0,π2.
Segue, inoltre, il seguente corollario al teorema del punto fisso:
Corollario 30 Assegnata una qualunque contrazione f di [a, b] ⊂ R, la successione di funzioni {fn(x)}n∈N converge alla funzione costante g (x) ≡ f (x∗), essendo x∗ il punto fisso di f . Cio`e:
lim
Π Π 2 3 Π 2 2 Π x -1 1 x* y
Figura 3.23: Grafico delle funzioni fn(x) per n = 0, 1, 2, ..., 6, dove f (x) = cos x. La linea in tratteggio `e il grafico della funzione costante g (x) = x∗.
Π 2 Π 3 Π 2 2 Π x x* y
Figura 3.24: Grafico della funzione fn=2(x) dove f (x) = cos x. La linea in tratteggio `e il grafico della funzione costante g (x) = x∗.
CAPITOLO 3. MACCHINE RICORSIVE Π 2 Π 3 Π 2 2 Π x x* y
Figura 3.25: Grafico della funzione fn=10(x). dove f (x) = cos x. La linea in tratteggio `e il grafico della funzione costante g (x) = x∗. Al crescere indefinito di n le oscillazioni di fn(x) si attenuano per smorzarsi nel limite per n → +∞.
Le figg. 3.23–3.24–3.25 illustrano rispettivamente le prime 2 e 10 iterazioni nel caso f (x) = cos x, ∀x ∈0,π
2
.
Esempio 31 Consideriamo il sistema dinamico a tempo continuo:
˙x = F (x) x (0) = x0
con
F (x) = x2− x, ∀x ∈ [0, 1] per cui i punti fissi della corrispondente macchina ricorsiva M sono:
x∗ = 0, x′∗ = 1
L’equazione differenziale ˙x = x2 − x si integra per separazione di variabili (§ B.1) ottenendo la soluzione:
x (t) = x0
x0− (x0− 1) et, ∀t ∈ R, (3.44)
da cui vediamo che per x0 6= x∗, x′
∗ la x (t) non `e una costante. Inoltre, comunque prendiamo x0 ∈ (0, 1). la soluzione x (t) converge asintoticamente a zero, come mostrato nel grafico di fig. 3.26. Cio`e
lim
t→+∞x (t) = 0, ∀x0 ∈ (0, 1) La funzione di trasferimento di M `e:
f (x) = x2, ∀x ∈ [0, 1] (3.45)
Il punto fisso x′
∗ = 1 `e repulsivo nel senso che per ogni punto iniziale x0 ∈ (x′
∗− δ, x′
∗), la successione {xn} non converge a x′
∗. Anzi, si allontana definitivamente da esso. Ad esempio, per x0 = 0.999 otteniamo il diagramma delle orbite di fig. 3.27.
3Si osservi che mentre la trasformazione identica `e unica, di contrazioni degenere ne esistono infinite (per un assegnato intervallo [a, b]).
2 4 6 8 10 t 0.2 0.4 0.6 0.8 1.0 x
Figura 3.26: Andamento della soluzione (3.44) per diversi valori dello stato iniziale x0 ∈ (0, 1).
0.2 0.4 0.6 0.8 1.0 xn 0.2 0.4 0.6 0.8 1.0 xn+1
Figura 3.27: Diagramma di K¨onig-Lemaray della macchina ricorsiva con funzione di trasferimento (3.45) e stato iniziale x0 = 0.999.
CAPITOLO 3. MACCHINE RICORSIVE
Abbiamo la seguente definizione:
Definizione 32 Il punto fisso x∗ di una macchina ricorsiva con funzione di trasferimento f , `e repulsivo se e solo se:
∃Iδ(x∗) = (x∗− δ, x∗+ δ) | (x0 ∈ Iδ(x∗) − {x∗} =⇒ ∃n ∈ N − {0} | fn(x0) /∈ Iδ(x0) Dal teorema 26 segue il corollario:
Corollario 33 Sia f : [a, b] → R. Se x∗ `e un punto fisso una macchina ricorsiva con funzione di trasferimento f , segue:
• x∗ `e un punto fisso attrattivo se |f′(x∗)| < 1 • x∗ `e un punto fisso repulsivo se |f′(x∗)| > 1
Infatti, nell’esempio precedente riesce f′(0) = 0 e f′(1) = 2.
Conclusione 34 Se f : [a, b] → R `e una contrazione di [a, b], il sistema ha un unico punto fisso attrattivo x∗.