Funzione iterata

In matematica , una funzione iterata è una funzione ottenuta componendo ripetutamente un'altra funzione con se stessa un certo numero di volte. Il processo di applicazione della stessa funzione più e più volte è chiamato iterazione .

Le funzioni iterate compaiono nell'informatica , nei sistemi dinamici , nei gruppi di rinormalizzazione e sono alla base dei frattali .

Definizione

L'iterato, più precisamente il secondo iterato, di una funzione f , definita su un insieme X e con valori in questo stesso insieme X , è la funzione dove denota la composizione delle funzioni . In altre parole, per ogni elemento x di X ${\ displaystyle f \ circ f,}$ $\ circo$

{\ displaystyle (f \ circ f) (x) = f (f (x)).}

Più in generale, essendo n un intero positivo o nullo, l' n - esimo iterato di una funzione f , definita su un insieme X e con valori in questo stesso insieme X , è definita per induzione tramite la relazione ${\ stile di visualizzazione f ^ {n}}$

{\ displaystyle f ^ {n} ~ {\ stackrel {\ mathrm {def}} {=}} ~ f \ circ f ^ {n-1}.}

Per convenzione, per n = 0, dove è la funzione identità su $X$ . ${\ displaystyle f ^ {0} ~ {\ stackrel {\ mathrm {def}} {=}} ~ \ operatorname {id} _ {X}}$ ${\ displaystyle \ nomeoperatore {id} _ {X}}$

La notazione può essere ambigua, poiché viene utilizzata non solo per l'iterazione, ma anche per l'elevazione. Per questo motivo, alcuni matematici notare la n- esima iterazione di una funzione $f$ . ${\ stile di visualizzazione f ^ {n}}$ $f ^ {\ circ n}$

Sequenze di iterazione

Le seguenti identità vengono controllate per tutti gli interi positivi o nulli $m$ e $n$ :

{\ displaystyle f ^ {m} \ circ f ^ {n} = f ^ {n} \ circ f ^ {m} = f ^ {m + n} ~.}

{\ displaystyle (f ^ {m}) ^ {n} (x) = (f ^ {n}) ^ {m} (x) = f ^ {mn} (x).}

Per un elemento $x$ di $X$ , la sequenza dei valori è l' orbita di $x$ . ${\ stile di visualizzazione f ^ {n} (x)}$

Se per un intero $m$ diverso da zero si ha allora (per ogni $n$ ), l'orbita si dice periodica e il più piccolo intero $m$ per un dato $x$ è il periodo dell'orbita corrispondente; il punto $x$ stesso è un cosiddetto punto periodico. In informatica, il problema del rilevamento del ciclo è il problema algoritmico di trovare il primo punto periodico di un'orbita e il periodo dell'orbita. ${\ stile di visualizzazione x = f ^ {m} (x)}$ ${\ stile di visualizzazione f ^ {n} (x) = f ^ {n + m} (x)}$

Punti fissi

Se f ( x ) = x per un elemento x di X (in altre parole, il periodo dell'orbita di x è 1), allora x è un punto fisso della sequenza iterata. L'insieme dei punti fissi è indicato con Fix ( f ). Vari teoremi garantiscono l'esistenza di punti fissi in determinate situazioni, come il teorema del punto fisso di Banach o il teorema del punto fisso di Brouwer .

Diverse tecniche consentono inoltre di accelerare la convergenza delle successioni prodotte dall'iterazione di punti fissi.

Durante l'iterazione possono esserci insiemi che si contraggono e convergono in un unico punto: in questo caso, questo punto è un punto fisso attrattivo. L'iterazione può anche dare l'impressione di punti che si allontanano da un punto fisso, che viene quindi chiamato punto fisso instabile. Sono possibili anche altri comportamenti borderline. Quando i punti dell'orbita convergono verso uno o più limiti, l'insieme dei punti di accumulazione dell'orbita è detto insieme limite o insieme -limite.

Le idee di attrazione e repulsione sono generalizzate: si possono classificare gli insiemi stabili e instabili secondo il comportamento dei piccoli quartieri sotto l'iterazione.

misura invariante

Se siamo interessati all'evoluzione di una distribuzione di densità, anziché di una distribuzione discreta o di un singolo punto, il comportamento limite è dato dalla misura invariante. Può essere visualizzato come il comportamento di una nuvola di punti o polvere durante un'iterazione. La misura invariante è un autovettore dell'operatore Ruelle-Frobenius-Perron o dell'operatore di trasferimento , corrispondente all'autovalore 1. Autovalori più piccoli corrispondono a stati instabili e contraenti.

In generale, poiché l'iterazione corrisponde a uno spostamento, l' operatore di trasferimento e il suo aiutante , l'operatore di Koopman, possono essere interpretati entrambi come l'azione di un operatore di spostamento su un sistema dinamico simbolico. La teoria dei sistemi dinamici simbolici fornisce un quadro per comprendere molte funzioni iterate, specialmente quelle che portano al caos .

Iterato frazionario e negativo

Sotto determinate ipotesi, è possibile definire un frazionario iterato di una funzione. Ad esempio, il semi-iterato di una funzione $f$ è una funzione $g$ tale che . Questa funzione $g$ può essere scritta con notazione esponenziale . Analogamente, la funzione è tale che , e può essere definita come , e così via, dal principio che l' idea può essere generalizzata nel caso in cui il numero di iterazioni $n$ diventi un parametro continuo; il sistema è quindi un flusso legato ad un'equazione di Schröder . ${\ stile di visualizzazione g (g (x)) = f (x)}$ ${\ displaystyle f ^ {\ frac {1} {2}} (x)}$ ${\ displaystyle f ^ {\ frac {1} {3}} (x)}$ ${\ displaystyle f ^ {\ frac {1} {3}} (f ^ {\ frac {1} {3}} (f ^ {\ frac {1} {3}} (x))) = f (x )}$ ${\ displaystyle f ^ {\ frac {2} {3}} (x)}$ ${\ displaystyle f ^ {\ frac {1} {3}} (f ^ {\ frac {1} {3}} (x))}$ ${\ displaystyle f ^ {m} \ circ f ^ {n} = f ^ {n} \ circ f ^ {m} = f ^ {m + n} ~.}$

Le iterazioni negative corrispondono ai reciproci delle funzioni e alle loro composizioni. Ad esempio, è il solito reciproco della funzione $f$ , è il reciproco composto con se stesso, ecc. Le iterazioni frazionarie negative sono definite analogamente alle frazioni positive. Ad esempio, è definito in modo tale che . ${\ stile di visualizzazione f ^ {- 1} (x)}$ ${\ stile di visualizzazione f ^ {- 2} (x)}$ ${\ displaystyle f ^ {- {\ frac {1} {2}}} (x)}$ ${\ displaystyle f ^ {- {\ frac {1} {2}}} (f ^ {- {\ frac {1} {2}}} (x)) = f ^ {- 1} (x)}$

Formule per l'iterazione frazionaria

Esistono diversi metodi per determinare gli iterati frazionari. La seguente si basa sull'uso di un punto fisso.

Determinare un punto fisso a della funzione, ovvero un punto a tale che . ${\ stile di visualizzazione f (a) = a}$
Imposta , per tutti gli n appartenenti ai numeri reali. Ciò corrisponde alla condizione aggiuntiva più naturale da imporre agli iterati. ${\ displaystyle f ^ {n} (a) = a}$
Scrivi nell'intorno del punto fisso a come una serie di Taylor : ${\ stile di visualizzazione f ^ {n} (x)}$ ${\ displaystyle f ^ {n} (x) = f ^ {n} (a) + (xa) {\ frac {d} {dx}} f ^ {n} (x) | _ {x = a} + {\ frac {(xa) ^ {2}} {2}} {\ frac {d ^ {2}} {dx ^ {2}}} f ^ {n} (x) | _ {x = a} + \ punti}$
Sviluppare : ${\ displaystyle f ^ {n} \ sinistra (x \ destra) = f ^ {n} (a) + (xa) f '(a) f' (f (a)) f '(f ^ {2} ( a)) \ cdots f '(f ^ {n-1} (a)) + \ cdots}$
Usando la condizione impostata nel passaggio 2 , per ogni k , otteniamo: ${\ stile di visualizzazione f ^ {k} (a) = a}$ ${\ displaystyle f ^ {n} \ sinistra (x \ destra) = a + (xa) f '(a) ^ {n} + {\ frac {(xa) ^ {2}} {2}} (f' ' (a) f '(a) ^ {n-1}) \ sinistra (1 + f' (a) + \ cdots + f '(a) ^ {n-1} \ destra) + \ cdots}$
Semplificare usando la progressione geometrica : ${\ displaystyle f ^ {n} \ sinistra (x \ destra) = a + (xa) f '(a) ^ {n} + {\ frac {(xa) ^ {2}} {2}} (f' ' (a) f '(a) ^ {n-1}) {\ frac {f' (a) ^ {n} -1} {f '(a) -1}} + \ cdots}$
Un caso speciale è dove ; in quel caso : ${\ stile di visualizzazione f '(a) = 1}$ ${\ displaystyle f ^ {n} \ sinistra (x \ destra) = x + {\ frac {(xa) ^ {2}} {2}} (nf '' (a)) + {\ frac {(xa) ^ {3}} {6}} \ sinistra ({\ frac {3} {2}} n (n-1) f '' (a) ^ {2} + nf '' '(a) \ destra) + \ punti}$
Se n non è un intero, usiamo la formula . ${\ displaystyle y ^ {n} = \ exp (n \ ln (y))}$

Questo processo può essere continuato indefinitamente, ma generalmente non è efficiente, poiché i termini diventano sempre più complicati.

Esempio 1

La funzione f è definita da $f ( x ) = Cx + D$ , con C ≠ 1 , ha un punto fisso $a = '' D / (1- C )$ .

Il processo spiegato sopra dà:

{\ displaystyle f ^ {n} (x) = {\ frac {D} {1-C}} + (x - {\ frac {D} {1-C}}) C ^ {n} = C ^ { n} x + {\ frac {1-C ^ {n}} {1-C}} D.}

Esempio 2

Si tratta di trovare il valore di , per n iterazioni. La funzione è qui definita da $f$ $($ $x$ $) =$ $\sqrt$ $2$ $x$ . Un punto fisso è . ${\ displaystyle {\ sqrt {2}} ^ {{\ sqrt {2}} ^ {{\ sqrt {2}} ^ {\ cdots}}}}$ ${\ stile di visualizzazione a = f (2) = 2}$

Espandendo $f n (x)$ come spiegato sopra in un intorno di 2, e ponendo x = 1, otteniamo,

{\ displaystyle {\ sqrt {2}} ^ {{\ sqrt {2}} ^ {{\ sqrt {2}} ^ {\ cdots}}} = f ^ {n} (1) = 2 - (\ ln 2) ^ {n} + {\ frac {(\ ln 2) ^ {n + 1} ((\ ln 2) ^ {n} -1)} {4 (\ ln 2-1)}} \ cdots. }

Per n intero positivo, i primi tre termini danno il primo decimale corretto: $f n (1) = n \sqrt 2$ .

(Nota che se usiamo al posto del punto fisso 2 l'altro punto fisso $a = f (4) = 4$ , la serie diverge.)

A $n$ $= -1$ , la serie calcola la funzione reciproca . ${\ displaystyle 2 \ ln x / \ ln 2}$

Esempio 3

Sviluppando in prossimità del punto fisso 1 la funzione $f ( x ) = x b$ , si ottiene la serie

{\ displaystyle f ^ {n} (x) = 1 + b ^ {n} (x-1) + {\ frac {1} {2}} b ^ {n} (b ^ {n} -1) ( x-1) ^ {2} + {\ frac {1} {3!}} b ^ {n} (b ^ {n} -1) (b ^ {n} -2) (x-1) ^ { 3} + \ punti,}

che è semplicemente la serie di Taylor di x ( b n ) in prossimità di 1.

Coniugazione

Se $f$ e $g$ sono due funzioni iterate, e se esiste un omeomorfismo $h$ tale che , si dice che $f$ e $g$ sono topologicamente coniugati. ${\ displaystyle g = h ^ {- 1} \ circ f \ circ h}$

L'iterazione conserva la coniugazione topologica: infatti ,. Quindi, se sappiamo determinare un sistema di funzioni iterate, sappiamo anche come determinare tutti i sistemi topologicamente coniugati. ${\ displaystyle g ^ {n} = h ^ {- 1} \ circ f ^ {n} \ circ h}$

Ad esempio, la funzione triangolare è topologicamente coniugata alla sequenza logistica . Un caso speciale è $f ( x ) = x +1$ , che dà come iterazione di ${\ stile di visualizzazione g (x) = h ^ {- 1} (h (x) +1)}$

{\ displaystyle g ^ {n} (x) = h ^ {- 1} (h (x) + n),}

per qualsiasi funzione $h$ .

Facendo la sostituzione otteniamo ${\ displaystyle x = h ^ {- 1} (y) = \ phi (y)}$

{\ displaystyle g (\ phi (y)) = \ phi (y + 1)}

, in altre parole l'equazione di Abele.

In assenza di un vero omeomorfismo globale, è spesso possibile risolvere l' equazione di Schröder nell'intorno di un punto fisso per una funzione $Ψ$ . Prendendo ad esempio $x$ = 0, $f$ (0) = 0, $f ( x )$ è localmente coniugato ad una dilatazione, $g ( x ) = f '(0) x$ , in altre parole

{\ displaystyle f (x) = \ psi ^ {- 1} (f (0) \ psi (x)).}

L'orbita di iterazione, o flusso, in opportune condizioni (ad esempio $f '(0) \neq 1$ ), diventa il coniugato dell'orbita del monomio:

{\ displaystyle \ psi ^ {- 1} (f '(0) ^ {n} \ psi (x)),}

dove $n$ in questa espressione è un esponente ordinario: cioè, l'iterazione funzionale è stata ridotta a una semplice moltiplicazione. L'esponente $n non$ può essere né positivo né intero; corrisponde quindi ad un tempo continuo di evoluzione per l'orbita.

L'esempio 2 sopra restituisce ad esempio , per ogni n (non necessariamente intero), dove $Ψ$ è la soluzione dell'equazione di Schröder corrispondente, . Questa soluzione è anche il limite, per m tendente all'infinito, di . ${\ displaystyle f ^ {n} (x) = \ psi ^ {- 1} ((\ ln 2) ^ {n} \ psi (x))}$ ${\ displaystyle \ psi ({\ sqrt {2}} ^ {x}) = \ ln 2 \ psi (x)}$ ${\ displaystyle {\ frac {f ^ {m} (x) -2} {(\ ln 2) ^ {m}}}}$

Questo metodo è equivalente all'algoritmo descritto nella sezione precedente, ma in pratica più potente e sistematico.

Esempi

Per esempi di funzioni iterate, vedere anche l' insieme di Mandelbrot ei sistemi di funzioni iterate .

Ernst Schröder studiò nel 1870 casi particolari della sequenza logistica :

(caso caotico): dà , da dove . ${\ stile di visualizzazione f (x) = 4x (1-x)}$ ${\ displaystyle \ psi (x) = \ arcsin ^ {2} ({\ sqrt {x}})}$ ${\ displaystyle f ^ {n} (x) = \ sin ^ {2} (2 ^ {n} \ arcsin ({\ sqrt {x}}))}$

(caso non caotico): dà , e quindi . ${\ stile di visualizzazione f (x) = 2x (1-x)}$ ${\ displaystyle \ psi (x) = - {\ frac {1} {2}} \ ln (1-2x)}$ ${\ displaystyle f ^ {n} (x) = - {\ frac {1} {2}} ((1-2x) ^ {2 ^ {n}} - 1)}$

Iterato di funzioni che hanno un'espressione chiusa

Per la maggior parte delle funzioni, non esiste un'espressione chiusa per l' iterazione n th . La tabella seguente elenca alcune funzioni per le quali esiste tale espressione. Tutte queste espressioni sono valide per n , ns negativi o frazionari, nonché per interi positivi.

$f(x)$	$f ^ {n} (x)$
${\ stile di visualizzazione x + b}$	${\ stile di visualizzazione x + nb}$
${\ displaystyle ax + b \ (a \ neq 1)}$	${\ displaystyle a ^ {n} x + {\ frac {a ^ {n} -1} {a-1}} b}$
${\ displaystyle ascia ^ {b} \ (b \ neq 1)}$	${\ displaystyle a ^ {\ frac {b ^ {n} -1} {b-1}} x ^ {b ^ {n}}}$
${\ displaystyle ax ^ {2} + bx + {\ frac {b ^ {2} -2b} {4a}}}$	${\ displaystyle {\ frac {2 \ alfa ^ {2 ^ {n}} - b} {2a}}}$ o : ${\ displaystyle \ alpha = {\ frac {2ax + b} {2}}}$
${\ displaystyle ax ^ {2} + bx + {\ frac {b ^ {2} -2b-8} {4a}}}$	${\ displaystyle {\ frac {2 \ alpha ^ {2 ^ {n}} + 2 \ alpha ^ {- 2 ^ {n}} - b} {2a}}}$ o : ${\ displaystyle \ alpha = {\ frac {2ax + b \ pm {\ sqrt {(2ax + b) ^ {2} -16}}} {4}}}$
${\ displaystyle {\ frac {ax + b} {cx + d}}}$	${\ displaystyle {\ frac {a} {c}} + {\ frac {bc-ad} {c}} \ left [{\ frac {(cx-a + \ alpha) \ alpha ^ {n-1} - ( cx-a + \ beta) \ beta ^ {n-1}} {(cx-a + \ alpha) \ alpha ^ {n} - (cx-a + \ beta) \ beta ^ {n}}} \ giusto]}$ o : ${\ displaystyle \ alpha = {\ frac {a + d + {\ sqrt {(ad) ^ {2} + 4bc}}} {2}}}$ ${\ displaystyle \ beta = {\ frac {a + d - {\ sqrt {(ad) ^ {2} + 4bc}}} {2}}}$
${\ displaystyle {\ sqrt {x ^ {2} + b}}}$	${\ displaystyle {\ sqrt {x ^ {2} + bn}}}$
${\ displaystyle {\ sqrt {ax ^ {2} + b}} \ (a \ neq 1)}$	${\ displaystyle {\ sqrt {a ^ {n} x ^ {2} + {\ frac {a ^ {n} -1} {a-1}} b}}}$
${\ displaystyle g ^ {- 1} {\ Big (} f {\ bigl (} g (x) {\ bigr)} {\ Big)}}$	${\ displaystyle g ^ {- 1} {\ Bigl (} f ^ {n} {\ bigl (} g (x) {\ bigr)} {\ Bigr)}}$
${\ displaystyle g ^ {- 1} {\ bigl (} g (x) + b {\ bigr)}}$ (equazione generica di Abel)	${\ displaystyle g ^ {- 1} {\ bigl (} g (x) + nb {\ bigr)}}$
${\ displaystyle g ^ {- 1} {\ Bigl (} a \ g (x) + b {\ Bigr)} \ (a \ neq 1)}$	${\ displaystyle g ^ {- 1} {\ Bigl (} a ^ {n} g (x) + {\ frac {a ^ {n} -1} {a-1}} b {\ Bigr)}}$
${\ displaystyle T_ {m} (x) = \ cos (m \ arccos x)}$ ( Polinomio di Chebyshev di ordine m )	${\ displaystyle T_ {m ^ {n}} = \ cos (m ^ {n} \ arccos x)}$

Nota: i due esempi di $ax 2 + bx + c$ sono gli unici casi che hanno una soluzione in forma chiusa. Scegliendo rispettivamente b = 2 = - a e b = 4 = - a , si riducono inoltre ai casi non caotici e caotici discussi sopra.

Alcuni di questi esempi sono collegati tra loro da semplici coniugazioni.

catene di Markov

Se la funzione è lineare e può essere descritta da una matrice stocastica , cioè una matrice in cui la somma degli input di una riga (o di una colonna) è sempre uguale a 1, allora il sistema di iterazioni è chiamato catena di Markov .

In informatica

In informatica , le funzioni iterate appaiono come casi speciali di funzioni ricorsive e sono coinvolte nel lambda calcolo , o in materie più specializzate, come la semantica denotazionale dei programmi per elaboratore.

Definizioni basate su funzioni iterate

Due importanti funzionalità , la sommatoria e il prodotto corrispondente, possono essere definite in termini di funzioni iterate. La sommatoria è definita da:

{\ displaystyle \ left \ {b + 1, \ sum _ {i = a} ^ {b} g (i) \ right \} \ equiv \ left (\ {i, x \} \ rightarrow \ {i + 1 , x + g (i) \} \ destra) ^ {ba + 1} \ {a, 0 \}}

e il prodotto da:

{\ displaystyle \ left \ {b + 1, \ prod _ {i = a} ^ {b} g (i) \ right \} \ equiv \ left (\ {i, x \} \ rightarrow \ {i + 1 , xg (i) \} \ destra) ^ {ba + 1} \ {a, 1 \}.}

derivata funzionale Function

La derivata funzionale di una funzione iterata è data dalla formula di ricorrenza:

{\ displaystyle {\ frac {\ delta f ^ {N} (x)} {\ delta f (y)}} = f '(f ^ {N-1} (x)) {\ frac {\ delta f ^ {N-1} (x)} {\ delta f (y)}} + \ delta (f ^ {N-1} (x) -y).}

Riferimenti

(fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato " Funzione iterata " ( vedere l'elenco degli autori ) .

(in) L. Carleson e TDW Gamelin , Dinamiche complesse , Berlino/New York, Springer-Verlag , al. "Universitext: Tratti in Matematica",1993, 174 pag. ( ISBN 0-387-97942-5 ).
Vasile Istratescu , Teoria del punto fisso, Introduzione , D. Reidel,diciannove ottantuno( ISBN 90-277-1224-7 ).
Tosihusa Kimura, “Sull'iterazione delle funzioni analitiche ”, Funkcialaj Ekvacioj , vol. 14,1971, pag. 197-238 ( leggi in linea ).
Thomas Curtright e Cosmas Zachos, " Profili di evoluzione ed equazioni funzionali ", Journal of Physics A , vol. 42, n ° 48,2009, pag. 485208 ( DOI 10.1088 / 1751-8113 / 42/48/485208 , Bibcode 2009JPhA… 42V5208C , arXiv 0909.2424 ).
(de) Ernst Schröder , “ Ueber iterirte Functionen ” , Mathematische Annalen , vol. 3, n o 21870, pag. 296-322 ( DOI 10.1007 / BF01443992 ).
Louis Brand, " Una sequenza definita da un'equazione alle differenze ", American Mathematical Monthly , vol. 62,settembre 1955, pag. 489–492 ( leggi online ).
Per altri esempi, principalmente coniugati degli esempi di Schröter, vedere S. Katsura e W. Fukuda, “ Modelli esattamente risolvibili che mostrano comportamento caotico ”, Physica A: Statistical Mechanics and its Applications , vol. 130, n . 3,1985, pag. 597 ( DOI 10.1016 / 0378-4371 (85) 90048-2 ).