Itereret funktion - Iterated function

I matematik er en itereret funktion en funktion $X \to X$ (det vil sige en funktion fra et sæt $X$ til sig selv), som opnås ved at sammensætte en anden funktion $f : X \to X$ med sig selv et bestemt antal gange. Processen med gentagne anvendelser af den samme funktion kaldes iteration . I denne proces, med udgangspunkt i et indledende tal, fødes resultatet af at anvende en given funktion igen i funktionen som input, og denne proces gentages.

Itererede funktioner er studieobjekter inden for datalogi , fraktaler , dynamiske systemer , matematik og renormaliseringsgruppefysik .

Definition

Den formelle definition af en itereret funktion på et sæt X følger.

Lad $X$ være et sæt og $f : X \to X$ være en funktion .

Definerer $f$ $n$ som n -th iterat af $f$ (en notation introduceret af Hans Heinrich Bürmann og John Frederick William Herschel ), hvor n er et ikke -negativt heltal, af:

{\ displaystyle f^{0} ~ {\ stackrel {\ mathrm {def}} {=}} ~ \ operatorname {id} _ {X}}

og

{\ displaystyle f^{n+1} ~ {\ stackrel {\ mathrm {def}} {=}} ~ f \ circ f^{n},}

hvor $id X$ er identitetsfunktionen på $X$ og $f ○ g$ betegner funktionssammensætning . Det er,

(f ○ g) (x) = f (g (x))

,

altid associativ .

Fordi notationen $f n$ kan referere til både iteration (sammensætning) af funktionen $f$ eller eksponentiering af funktionen $f$ (sidstnævnte bruges almindeligvis i trigonometri ), vælger nogle matematikere at bruge $\circ$ til at betegne den kompositoriske betydning, skrive $f \circ n (x)$ for $n$ -th iteraten af funktionen $f (x)$ , som f.eks. $f \circ3 (x), der$ betyder $f (f (f (x)))$ . Til samme formål blev $f [n] (x)$ brugt af Benjamin Peirce, mens Alfred Pringsheim og Jules Molk foreslog $n f (x) i$ stedet.

Abelsk ejendom og iterationssekvenser

Generelt gælder følgende identitet for alle ikke-negative heltal $m$ og $n$ ,

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

Dette er strukturelt identisk med eksponentieringens egenskab, at $a m a n = a m + n$ , dvs. specialtilfældet $f (x) = ax$ .

Generelt for vilkårlige generelle (negative, ikke-heltal, osv.) Indeks $m$ og $n$ , kaldes denne relation oversættelsesfunktionelle ligning , jf. Schröders ligning og Abel -ligning . På en logaritmisk skala, reducerer dette til indlejring egenskab af Chebyshev polynomier , $T m (T n (x)) = T m n (x)$ , idet $T n (x) = cos (n arccos (x))$ .

Forholdet $(f m) n (x) = (f n) m (x) = f mn (x)$ holder også analogt med eksponentieringens egenskab, at $(a m) n = (a n) m = a mn$ .

Funktionssekvensen $f n$ kaldes en Picard -sekvens , opkaldt efter Charles Émile Picard .

For en given $x$ i $X$ , den sekvens af værdier $f n (x)$ kaldes bane af $x$ .

Hvis $f n (x) = f n + m (x)$ for et helt tal $m$ , kaldes kredsløbet en periodisk bane . Den mindste værdi af $m$ for et givet $x$ kaldes kredsløbets periode . Selve punktet $x$ kaldes et periodisk punkt . Den afsløring cyklus problem i datalogi er den algoritmiske problemet med at finde det første periodiske punkt i en bane, og den periode af kredsløb.

Faste punkter

Hvis $f (x) = x$ for nogle $x$ i $X$ (det vil sige perioden for kredsløbet for $x$ er $1$ ), kaldes $x$ et fast punkt i den itererede sekvens. Sættet med faste punkter betegnes ofte som $Fix (f)$ . Der findes en række fastpunktssætninger, der garanterer eksistensen af faste punkter i forskellige situationer, herunder Banach-fastpunktssætningen og Brouwer-fastpunktssætningen .

Der er flere teknikker til konvergensacceleration af sekvenserne frembragt ved fastpunkts iteration . For eksempel er Aitken -metoden, der anvendes på et itereret fast punkt, kendt som Steffensens metode og frembringer kvadratisk konvergens.

Begrænsende adfærd

Ved iteration kan man opleve, at der er sæt, der krymper og konvergerer mod et enkelt punkt. I et sådant tilfælde er det punkt, der konvergeres til, kendt som et attraktivt fast punkt . Omvendt kan iteration give udseende af punkter, der afviger fra et enkelt punkt; dette ville være tilfældet for et ustabilt fast punkt . Når de punkter i kredsløb konvergerer til en eller flere begrænsninger, sættet af fortætningspunkter er i kredsløb kendt som indstillede grænse eller ω-limit sæt .

Ideerne om tiltrækning og frastødning generaliseres på samme måde; man kan kategorisere iterater i stabile sæt og ustabile sæt , alt efter adfærden i små kvarterer under iteration. (Se også Uendelige sammensætninger af analytiske funktioner .)

Andre begrænsende adfærd er mulige; for eksempel er vandringspunkter punkter , der bevæger sig væk og aldrig kommer tilbage, selv tæt på hvor de startede.

Uforanderlig foranstaltning

Hvis man overvejer udviklingen af en densitetsfordeling, snarere end den for individuel punktdynamik, så er den begrænsende adfærd givet af den invariante måling . Det kan visualiseres som opførelsen af en punktsky eller støvsky under gentagen iteration. Den invariante måling er en egenstat for Ruelle-Frobenius-Perron-operatøren eller overførselsoperatoren , svarende til en egenværdi på 1. Mindre egenværdier svarer til ustabile, forfaldne tilstande.

Generelt, fordi gentagen iteration svarer til et skift, overførselsoperatøren og dets tilstødende, kan Koopman -operatøren begge tolkes som skifteoperatørers handling på et skiftrum . Teorien om underforskydninger af endelig type giver generel indsigt i mange itererede funktioner, især dem, der fører til kaos.

Brøkdele itererer og flyder, og negative itererer

g : R → R er en triviel funktionel 5. rod af f : R ⁺ → R ⁺ , f ( x ) = sin ( x ) . Beregningen af f ( π ⁄ 6 ) = 1 ⁄ 2 = g ⁵ ( π ⁄ 6 ) vises.

Begrebet $f 1/ n$ skal bruges med forsigtighed, når ligningen $g n (x) = f (x)$ har flere løsninger, hvilket normalt er tilfældet, som i Babbages ligning af identitetskortets funktionelle rødder. For eksempel, for $n = 2$ og $f (x) = 4 x - 6$ , er både $g (x) = 6 - 2 x$ og $g (x) = 2 x - 2$ løsninger; så udtrykket $f 1/2 (x)$ betegner ikke en unik funktion, ligesom tal har flere algebraiske rødder. Spørgsmålet ligner ganske meget udtrykket " 0/0 " i aritmetik. En trivial rod til f kan altid opnås, hvis f ' s domæne kan udvides tilstrækkeligt, jf. billede. De valgte rødder er normalt dem, der tilhører den undersøgte bane.

Fraktioneret iteration af en funktion kan defineres: for eksempel er en halv iterat af en funktion $f$ en funktion $g$ sådan, at $g (g (x)) = f (x)$ . Denne funktion $g (x)$ kan skrives ved hjælp af indeksnotationen som $f 1/2 (x)$ . På samme måde er $f 1/3 (x)$ den definerede funktion, så $f 1/3 (f 1/3 (f 1/3 (x))) = f (x)$ , mens $f 2/3 (x)$ kan være defineret som lig med $f 1/3 (f 1/3 (x))$ og så videre, alt baseret på det tidligere nævnte princip, at $f m ○ f n = f m + n$ . Denne idé kan generaliseres, så iterationstællingen $n$ bliver til en kontinuerlig parameter , en slags kontinuerlig "tid" for en kontinuerlig bane .

I sådanne tilfælde omtaler man systemet som et flow . (jf. afsnit om konjugation nedenfor.)

Negative iterater svarer til funktionsinverser og deres sammensætninger. For eksempel er $f -1 (x)$ den normale inverse af $f$ , mens $f -2 (x)$ er den inverse, der er sammensat med sig selv, dvs. $f -2 (x) = f -1 (f -1 (x))$ . Fraktionelle negative iterater defineres analogt med fraktionelle positive; for eksempel er $f -1/2 (x)$ defineret således, at $f -1/2 (f -1/2 (x)) = f -1 (x)$ , eller, tilsvarende, at $f -1/2 (f 1/2 (x)) = f 0 (x) = x$ .

Nogle formler til fraktioneret iteration

En af flere metoder til at finde en serieformel for fraktioneret iteration, ved hjælp af et fast punkt, er som følger.

Bestem først et fast punkt for funktionen, således at $f (a) = a$ .
Definer $f n (a) = a$ for alle n, der tilhører realerne. Dette er på nogle måder den mest naturlige ekstra betingelse at placere på fraktionerede iterater.
Udvid $f n (x)$ omkring det faste punkt a som en Taylor -serie , ${\ displaystyle f^{n} (x) = f^{n} (a)+(xa) \ venstre. {\ frac {d} {dx}} f^{n} (x) \ højre | _ { x = a}+{\ frac {(xa)^{2}} {2}} \ venstre. {\ frac {d^{2}} {dx^{2}}} f^{n} (x) \ højre | _ {x = a}+\ cdots}$
Udvid ud ${\ displaystyle f^{n} (x) = f^{n} (a)+(xa) f '(a) f' (f (a)) f '(f^{2} (a)) \ cdots f '(f^{n-1} (a))+\ cdots}$
Erstat ind for $f k (a) = a$ , for enhver k , ${\ displaystyle f^{n} (x) = a+(xa) f '(a)^{n}+{\ frac {(xa)^{2}} {2}} (f' '(a) f '(a)^{n-1}) \ venstre (1+f' (a)+\ cdots+f '(a)^{n-1} \ højre)+\ cdots}$
Brug den geometriske progression til at forenkle udtryk, ${\ displaystyle f^{n} (x) = a+(xa) f '(a)^{n}+{\ frac {(xa)^{2}} {2}} (f' '(a) f '(a)^{n-1}) {\ frac {f' (a)^{n} -1} {f '(a) -1}}+\ cdots}$ Der er et særligt tilfælde, når $f'(a) = 1$ , ${\ displaystyle f^{n} (x) = x+{\ frac {(xa)^{2}} {2}} (nf '' (a))+{\ frac {(xa)^{3}} {6}} \ venstre ({\ frac {3} {2}} n (n-1) f '' (a)^{2}+nf '' '(a) \ højre)+\ cdots}$

Dette kan fortsætte på ubestemt tid, selv om det er ineffektivt, da sidstnævnte udtryk bliver mere og mere komplicerede. En mere systematisk procedure er beskrevet i det følgende afsnit om konjugation .

Eksempel 1

For eksempel giver indstilling $f (x) = Cx + D$ det faste punkt $a = D /(1 - C)$ , så ovenstående formel slutter til bare

{\ displaystyle f^{n} (x) = {\ frac {D} {1-C}}+\ venstre (x-{\ frac {D} {1-C}} \ højre) C^{n} = C^{n} x+{\ frac {1-C^{n}} {1-C}} D ~,}

hvilket er trivielt at kontrollere.

Eksempel 2

Find værdien af, hvor dette gøres n gange (og muligvis de interpolerede værdier, når n ikke er et heltal). Vi har $f$ $($ $x$ $) =$ $\sqrt$ $2$ $x$ . Et fast punkt er $a$ $=$ $f$ $(2) = 2$ . ${\ displaystyle {\ sqrt {2}}^{{\ sqrt {2}}^{{\ sqrt {2}}^{\ cdots}}}}}$

Så sæt $x = 1$ og $f n (1)$ udvidet omkring fastpunktværdien på 2 er så en uendelig serie,

{\ 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 }

som kun tager de første tre termer, er korrekt til den første decimal, når n er positiv - jf. Tetration :

f n (1) = n \sqrt 2

. (Brug af det andet faste punkt

a = f (4) = 4

får serien til at afvige.)

For $n = -1$ beregner serien den inverse funktion 2+ln x/I 2.

Eksempel 3

Med funktionen $f (x) = x b$ , udvide omkring det faste punkt 1 for at få serien

{\ 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}+\ cdots ~,}

som simpelthen er Taylor -serien med x ^{( b ⁿ )} udvidet omkring 1.

Bøjning

Hvis $f$ og $g$ er to itererede funktioner, og der findes en homomorfisme $h$ sådan, at $g$ $=$ $h$ $-1$ $○$ $f$ $○$ $h$ , siges $f$ og $g$ at være topologisk konjugeret .

Det er klart, topologisk konjugation bevares under iteration, da $g n = h -1 ○ f n ○ h$ . Således, hvis man kan løse for et itereret funktionssystem, har man også løsninger til alle topologisk konjugerede systemer. For eksempel telt kortet er topologisk konjugeret til den logistiske kortet . Som et specielt tilfælde, når man tager $f (x) = x + 1$ , har man iterationen af $g (x) = h -1 (h (x) + 1)$ som

g n (x) = h -1 (h (x) + n)

for enhver funktion

h

.

Gør substitutionen $x = h -1 (y) = ϕ (y)$ giver

g (ϕ (y)) = ϕ (y +1)

, en form kendt som Abel -ligningen .

Selv i mangel af en streng homomorfisme, nær et fast punkt, her antaget at være på $x$ = 0, $f$ (0) = 0, kan man ofte løse Schröders ligning for en funktion Ψ, hvilket får $f (x)$ lokalt konjugeret til en simpel udvidelse, $g (x) = f'(0) x$ , det vil sige

f (x) = Ψ -1 (f'(0) Ψ (x))

.

Således udgør dets iterationsbane eller -strøm under passende bestemmelser (f.eks. $F'(0) \neq 1$ ) konjugatet af monomialets bane,

Ψ -1 (f'(0) n Ψ (x))

,

hvor $n$ i dette udtryk fungerer som en almindelig eksponent: funktionel iteration er reduceret til multiplikation! Her behøver eksponenten $n imidlertid$ ikke længere at være et helt tal eller positivt, og er en kontinuerlig "tid" for evolution for hele kredsløbet: monoiden i Picardsekvensen (jf. Transformation semigruppe ) har generaliseret til en fuld kontinuerlig gruppe .

Iterater af sinusfunktionen ( blå ) i den første halvperiode. Halv iterat ( orange ), dvs. sinusens funktionelle kvadratrod; den funktionelle kvadratrod deraf, kvart-iteraten (sort) over den; og yderligere fraktionerede iterater op til 1/64. Funktionerne under den ( blå ) sinus er seks integrerede iterater under den, der starter med den anden iterat ( rød ) og slutter med den 64. iterat. Den grønne konvolutstriangel repræsenterer den begrænsende nul -iterat, savtandfunktionen fungerer som udgangspunkt for sinusfunktionen. Den stiplede linje er den negative første iterat, dvs. inversen af sinus (arcsin). (Fra den generelle pædagogiske hjemmeside. For notationen, se [2] .)

Denne metode (perturbativ bestemmelse af den primære egenfunktion Ψ, jf. Carleman -matrix ) svarer til algoritmen i det foregående afsnit, om end i praksis mere kraftfuld og systematisk.

Markov kæder

Hvis funktionen er lineær og kan beskrives ved en stokastisk matrix , det vil sige en matrix, hvis rækker eller kolonner summerer til en, så er det itererede system kendt som en Markov -kæde .

Eksempler

Der er mange kaotiske kort . Kendte itererede funktioner omfatter Mandelbrot-sættet og itererede funktionssystemer .

Ernst Schröder , i 1870, udarbejdede særlige tilfælde af det logistiske kort , såsom det kaotiske tilfælde $f (x) = 4 x (1 - x)$ , så $Ψ (x) = buesin 2 (\sqrt x)$ , derfor $f n (x) = sin 2 (2 n buesin (\sqrt x))$ .

En ikke -kaotisk sag Schröder illustrerede også med sin metode, $f (x) = 2 x (1 - x)$ , gav $Ψ (x) = - 1 / 2 ln (1-2 x)$ , og dermed $f n (x) = - 1 / 2 ((1-2 x) 2 n - 1)$ .

Hvis $f$ er handlingen af et gruppeelement på et sæt, svarer den itererede funktion til en fri gruppe .

De fleste funktioner har ikke eksplicitte generelle lukkede udtryk for n -iteratet. Tabellen nedenfor viser nogle, der gør. Bemærk, at alle disse udtryk er gyldige, selv for ikke-heltal og negative n , samt ikke-negative heltal n .

${\ displaystyle f (x)}$	${\ displaystyle f^{n} (x)}$
${\ displaystyle x+b}$	${\ displaystyle x+nb}$
${\ displaystyle ax+b \ (a \ neq 1)}$	${\ displaystyle a^{n} x+{\ frac {a^{n} -1} {a-1}} b}$
${\ displaystyle ax^{b} \ (b \ neq 1)}$	${\ displaystyle a^{\ frac {b^{n} -1} {b-1}} x^{b^{n}}}$
${\ displaystyle ax^{2}+bx+{\ frac {b^{2} -2b} {4a}}}$ (se note)	${\ displaystyle {\ frac {2 \ alpha ^{2 ^{n}}-b} {2a}}}$ hvor: ${\ displaystyle \ alpha = {\ frac {2ax+b} {2}}}$
${\ displaystyle ax^{2}+bx+{\ frac {b^{2} -2b-8} {4a}}}$ (se note)	${\ displaystyle {\ frac {2 \ alpha ^{2 ^{n}}+2 \ alpha ^{-2 ^{n}}-b} {2a}}}$ hvor: ${\ displaystyle \ alpha = {\ frac {2ax+b \ pm {\ sqrt {(2ax+b)^{2} -16}}} {4}}}$
${\ displaystyle {\ frac {ax+b} {cx+d}}}$ ( ligning af rationel forskel )	${\ displaystyle {\ frac {a} {c}}+{\ frac {bc-ad} {c}} \ venstre [{\ frac {(cx-a+\ alpha) \ alpha ^{n-1}-( cx-a+\ beta) \ beta ^{n-1}} {(cx-a+\ alpha) \ alpha ^{n}-(cx-a+\ beta) \ beta ^{n}}} \ right]}$ hvor: ${\ displaystyle \ alpha = {\ frac {a+d+{\ sqrt {(ad)^{2}+4bc}}} {2}}}$ ${\ displaystyle \ beta = {\ frac {a+d-{\ sqrt {(ad)^{2}+4bc}}} {2}}}$
${\ displaystyle g^{-1} {\ Big (} h {\ bigl (} g (x) {\ bigr)} {\ Big)}}$	${\ displaystyle g^{-1} {\ Bigl (} h^{n} {\ bigl (} g (x) {\ bigr)} {\ Bigr)}}$
${\ displaystyle g^{-1} {\ bigl (} g (x)+b {\ bigr)}}$ (generisk Abel -ligning )	${\ displaystyle g^{-1} {\ bigl (} g (x)+nb {\ bigr)}}$
${\ displaystyle {\ sqrt {x^{2}+b}}}$	${\ displaystyle {\ sqrt {x^{2}+bn}}}$
${\ displaystyle g^{-1} {\ Bigl (} a \ g (x)+b {\ Bigr)} \ (a \ neq 1 \ vee b = 0)}$	${\ displaystyle g^{-1} {\ Bigl (} a^{n} g (x)+{\ frac {a^{n} -1} {a-1}} b {\ Bigr)}}$
${\ displaystyle {\ sqrt {ax^{2}+b}}}$	${\ displaystyle {\ sqrt {a^{n} x^{2}+{\ frac {a^{n} -1} {a-1}} b}}}$
${\ displaystyle T_ {m} (x) = \ cos (m \ arccos x)}$ ( Chebyshev -polynom for heltal m )	${\ displaystyle T_ {mn} = \ cos (m^{n} \ arccos x)}$

Bemærk: disse to specielle tilfælde af $ax 2 + bx + c$ er de eneste tilfælde, der har en lukket form. At vælge henholdsvis b = 2 = - a og b = 4 = - a reducerer dem yderligere til de ikke -kaotiske og kaotiske logistiske sager, der blev diskuteret forud for tabellen.

Nogle af disse eksempler hænger indbyrdes sammen med simple konjugacier. Et par yderligere eksempler, der i det væsentlige svarer til simple konjugacier af Schröders eksempler, findes i ref.

Studiemidler

Itererede funktioner kan studeres med Artin – Mazur zeta -funktionen og med overførselsoperatorer .

Inden for datalogi

Inden for datalogi forekommer itererede funktioner som et specielt tilfælde af rekursive funktioner , som igen forankrer undersøgelsen af så brede emner som lambda calculus eller smallere, såsom denotationssemantik i computerprogrammer.

Definitioner med hensyn til itererede funktioner

To vigtige funktionaliteter kan defineres i form af itererede funktioner. Disse er summering :

{\ displaystyle \ left \ {b+1, \ sum _ {i = a}^{b} g (i) \ right \} \ equiv \ left (\ {i, x \} \ rightarrow \ {i+1 , x+g (i) \} \ højre)^{b-a+1} \ {a, 0 \}}

og det tilsvarende produkt:

{\ displaystyle \ left \ {b+1, \ prod _ {i = a}^{b} g (i) \ right \} \ equiv \ left (\ {i, x \} \ rightarrow \ {i+1 , xg (i) \} \ højre)^{b-a+1} \ {a, 1 \}}

Funktionelt derivat

Det funktionelle derivat af en iteret funktion er givet ved den rekursive formel:

{\ 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)}

Lies datatransportligning

Itererede funktioner dukker op i serieudvidelsen af kombinerede funktioner, f.eks. $G (f (x))$ .

I betragtning af iterationshastigheden eller betafunktionen (fysik) ,

{\ displaystyle v (x) = \ venstre. {\ frac {\ delvis f^{n} (x)} {\ delvis n}} \ højre | _ {n = 0}}

for $n$ ^den iterate af funktionen $f$ , har vi

{\ displaystyle g (f (x)) = \ exp \ venstre [v (x) {\ frac {\ partial} {\ delvis x}} \ højre] g (x).}

For eksempel ved stiv advektion, hvis $f (x) = x + t$ , så $v (x) = t$ . Følgelig er $g (x + t) = exp (t \partial/\partial x) g (x)$ handling fra en almindelig skiftoperatør .

Omvendt kan man angive $f (x)$ givet et vilkårligt $v (x)$ gennem den generiske Abel -ligning, der er diskuteret ovenfor,

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

hvor

{\ displaystyle h (x) = \ int {\ frac {1} {v (x)}} \, dx.}

Dette er tydeligt ved at bemærke det

{\ displaystyle f^{n} (x) = h^{-1} (h (x)+n) ~.}

For kontinuerligt iterationsindeks $t$ , altså nu skrevet som et abonnement, svarer dette til Lies berømte eksponentielle erkendelse af en kontinuerlig gruppe,

{\ displaystyle e^{t ~ {\ frac {\ partiel ~~} {\ delvis h (x)}}} g (x) = g (h^{-1} (h (x)+t)) = g (f_ {t} (x)).}

Den indledende strømningshastighed $v er$ tilstrækkelig til at bestemme hele flowet i betragtning af denne eksponentielle erkendelse, der automatisk giver den generelle løsning til oversættelsesfunktionelle ligning ,

{\ displaystyle f_ {t} (f _ {\ tau} (x)) = f_ {t+\ tau} (x) ~.}

Languages

In other projects