Función iterada

En matemáticas , una función iterada es aquella que se obtiene al combinar otra función consigo misma dos o más veces. El proceso de aplicar repetidamente la misma función se denomina iteración . En este proceso, partiendo de un objeto inicial, el resultado de aplicar una función dada se introduce nuevamente en la función como entrada, y este proceso se repite.

Por ejemplo, en la imagen de la derecha:

${\displaystyle L=F(K),\ M=F\circ F(K)=F^{2}(K).}$

Las funciones iteradas se estudian en informática , fractales , sistemas dinámicos , matemáticas y física del grupo de renormalización .

A continuación se presenta la definición formal de una función iterada sobre un conjunto X.

Sea X un conjunto y f : X → X una función .

Definimos f ⁿ como la n -ésima iteración de f , donde n es un entero no negativo, de la siguiente manera: $${\displaystyle f^{0}~{\stackrel {\mathrm {def} }{=}}~\operatorname {id} _{X}}$$ y $${\displaystyle f^{n+1}~{\stackrel {\mathrm {def} }{=}}~f\circ f^{n},}$$

donde id _X es la función identidad en X y ( f${\displaystyle \circ }$g )( x ) = f ( g ( x )) denota composición de funciones . Esta notación se remonta a John Frederick William Herschel en 1813. ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]} Herschel se la atribuyó a Hans Heinrich Bürmann , pero sin hacer referencia específica al trabajo de Bürmann, que permanece sin descubrir. ^{[ 5 ]}

Debido a que la notación f ⁿ puede referirse tanto a la iteración (composición) de la función f como a la exponenciación de la función f (esta última se usa comúnmente en trigonometría ), algunos matemáticos optan por usar ∘ para denotar el significado compositivo, escribiendo f ^{∘ n} ( x ) para la n -ésima iteración de la función f ( x ) , como en, por ejemplo, f ^∘3 ( x ) que significa f ( f ( f ( x ))) . Con el mismo propósito, Benjamin Peirce usó f ^{[ n ]} ( x ) ^{[ 6 ] [ 4 ] [ nb 1 ]} mientras que Alfred Pringsheim y Jules Molk sugirieron ⁿ f ( x ) en su lugar. ^{[ 7 ] [ 4 ] [ nb 2 ]}

En general, la siguiente identidad se cumple para todos los enteros no negativos m y n :

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

Esto es estructuralmente idéntico a la propiedad de la exponenciación de que a ^m a ⁿ = a ^{m + n} .

En general, para índices generales arbitrarios (negativos, no enteros, etc.) m y n , esta relación se denomina ecuación funcional de traslación , cf. ecuación de Schröder y ecuación de Abel . En una escala logarítmica, esto se reduce a la propiedad de anidamiento de los polinomios de Chebyshev , T _m ( T _n ( x )) = T _{m n} ( x ) , ya que T _n ( x ) = cos( n arccos( x )) .

La relación ( f ^m ) ⁿ ( x ) = ( f ⁿ ) ^m ( x ) = f ^mn ( x ) también se cumple, análoga a la propiedad de la exponenciación de que ( a ^m ) ⁿ = ( a ⁿ ) ^m = a ^mn .

La secuencia de funciones f ⁿ se llama secuencia de Picard , ^{[ 8 ] [ 9 ]} nombrada en honor a Charles Émile Picard .

Para un x dado en X , la secuencia de valores f ⁿ ( x ) se llama la órbita de x .

Si f ⁿ ( x ) = f ^{n + m} ( x ) para algún entero m > 0 , la órbita se denomina órbita periódica . El menor valor de m para un x dado se denomina período de la órbita . El punto x en sí mismo se denomina punto periódico . El problema de detección de ciclos en informática es el problema algorítmico de encontrar el primer punto periódico en una órbita y el período de la misma.

Si x = f ( x ) para algún x en X (es decir, el período de la órbita de x es 1 ), entonces x se denomina punto fijo de la secuencia iterada. El conjunto de puntos fijos se suele denotar como Fix ( f ) . Existen varios teoremas de punto fijo que garantizan la existencia de puntos fijos en diversas situaciones, entre ellos el teorema del punto fijo de Banach y el teorema del punto fijo de Brouwer .

Existen varias técnicas para acelerar la convergencia de las secuencias producidas por iteración de punto fijo . ^{[ 10 ]} Por ejemplo, el método de Aitken aplicado a un punto fijo iterado se conoce como método de Steffensen y produce convergencia cuadrática.

Al iterar, se puede encontrar que existen conjuntos que se contraen y convergen hacia un único punto. En tal caso, el punto al que converge se conoce como punto fijo atractivo . Por el contrario, la iteración puede dar la apariencia de que los puntos divergen alejándose de un único punto; este sería el caso de un punto fijo inestable . ^{[ 11 ]}

Cuando los puntos de la órbita convergen a uno o más límites, el conjunto de puntos de acumulación de la órbita se conoce como conjunto límite o conjunto ω-límite .

Las ideas de atracción y repulsión se generalizan de manera similar; se pueden clasificar las iteraciones en conjuntos estables e inestables , según el comportamiento de los entornos pequeños durante la iteración. Véase también composiciones infinitas de funciones analíticas .

Son posibles otros comportamientos limitantes; por ejemplo, los puntos errantes son puntos que se alejan y nunca regresan ni siquiera cerca del punto de partida.

Si se considera la evolución de una distribución de densidad, en lugar de la dinámica de puntos individuales, el comportamiento límite viene dado por la medida invariante . Esta puede visualizarse como el comportamiento de una nube de puntos o de polvo bajo iteración repetida. La medida invariante es un autoestado del operador de Ruelle-Frobenius-Perron o del operador de transferencia , que corresponde a un autovalor de 1. Los autovalores menores corresponden a estados inestables y en descomposición.

En general, dado que la iteración repetida corresponde a un desplazamiento, el operador de transferencia y su adjunto, el operador de Koopman , pueden interpretarse como la acción de operadores de desplazamiento sobre un espacio de desplazamiento . La teoría de subdesplazamientos de tipo finito proporciona una comprensión general de muchas funciones iteradas, especialmente aquellas que conducen al caos.

La noción f ^{1/ n} debe usarse con precaución cuando la ecuación g ⁿ ( x ) = f ( x ) tiene múltiples soluciones, lo cual suele ser el caso, como en la ecuación de Babbage de las raíces funcionales de la función identidad. Por ejemplo, para n = 2 y f ( x ) = 4 x − 6 , tanto g ( x ) = 6 − 2 x como g ( x ) = 2 x − 2 son soluciones; por lo tanto, la expresión f ^1/2 ( x ) no denota una función única, al igual que los números tienen múltiples raíces algebraicas. Siempre se puede obtener una raíz trivial de f si el dominio de f se puede extender suficientemente, véase la imagen. Las raíces elegidas suelen ser las que pertenecen a la órbita en estudio.

Se puede definir una iteración fraccionaria de una función: por ejemplo, una media iteración de una función f es una función g tal que g ( g ( x )) = f ( x ) . ^{[ 12 ]} Esta función g ( x ) se puede escribir usando la notación de índices como f ^1/2 ( x ) . De manera similar, f ^1/3 ( x ) es la función definida tal que f ^1/3 ( f ^1/3 ( f ^1/3 ( x ))) = f ( x ) , mientras que f ^2/3 ( x ) se puede definir como igual a f ^1/3 ( f ^1/3 ( x )) , y así sucesivamente, todo basado en el principio, mencionado anteriormente, de que f ^m ○ f ⁿ = f ^{m + n} . Esta idea se puede generalizar de modo que el número de iteraciones n se convierta en un parámetro continuo , una especie de "tiempo" continuo de una órbita continua . ^{[ 13 ] [ 14 ]}

En tales casos, se hace referencia al sistema como un flujo (véase la sección sobre conjugación más adelante).

Si una función es biyectiva (y por lo tanto posee una función inversa), entonces las iteraciones negativas corresponden a las inversas de la función y sus composiciones. Por ejemplo, f ⁻¹ ( x ) es la inversa normal de f , mientras que f ⁻² ( x ) es la inversa compuesta consigo misma, es decir, f ⁻² ( x ) = f ⁻¹ ( f ⁻¹ ( x )) . Las iteraciones negativas fraccionarias se definen de forma análoga a las positivas fraccionarias; por ejemplo, f ^−1/2 ( x ) se define de tal manera que f ^−1/2 ( f ^−1/2 ( x )) = f ⁻¹ ( x ) , o, equivalentemente, de tal manera que f ^−1/2 ( f ^1/2 ( x )) = f ⁰ ( x ) = x .

Si f y g son dos funciones iteradas, y existe un homeomorfismo h tal que g = h ⁻¹ ○ f ○ h , entonces se dice que f y g son topológicamente conjugadas .

Claramente, la conjugación topológica se conserva bajo iteración, ya que g ⁿ  = h ⁻¹ ○ f ⁿ ○ h    . Por lo tanto, si se puede resolver un sistema de funciones iteradas, también se tienen soluciones para todos los sistemas topológicamente conjugados. Por ejemplo, el mapa de la tienda es topológicamente conjugado al mapa logístico . Como caso especial, tomando f ( x ) = x  +  1 , se tiene la iteración de g ( x ) = h ^{− 1} ( h ( x )  +  1) como

g ⁿ ( x ) = h ^{− 1} ( h ( x )  + n )  ,   para cualquier función h .

Al realizar la sustitución x = h ^{− 1} ( y ) = ϕ ( y ) se obtiene

g ( ϕ ( y )) = ϕ ( y +1) ,  una forma conocida como la ecuación de Abel .

Incluso en ausencia de un homeomorfismo estricto, cerca de un punto fijo, aquí tomado en x = 0, f (0) = 0, a menudo se puede resolver ^{[ 16 ]} la ecuación de Schröder para una función Ψ, que hace que f ( x ) sea localmente conjugada a una mera dilatación, g ( x ) = f '(0) x , es decir

f ( x ) = Ψ ⁻¹ ( f '(0) Ψ( x )) .

Así, su órbita de iteración, o flujo, bajo disposiciones adecuadas (por ejemplo, f '(0) ≠ 1 ), equivale al conjugado de la órbita del monomio,

Ψ ⁻¹ ( f '(0) ⁿ Ψ( x )) ,

donde n en esta expresión sirve como un exponente simple: ¡ la iteración funcional se ha reducido a una multiplicación! Aquí, sin embargo, el exponente n ya no necesita ser entero o positivo, y es un "tiempo" continuo de evolución para la órbita completa: ^{[ 17 ]} el monoide de la secuencia de Picard (cf. semigrupo de transformación ) se ha generalizado a un grupo continuo completo . ^{[ 18 ]}

Este método (determinación perturbativa de la autofunción principal Ψ, cf. matriz de Jabotinsky ) es equivalente al algoritmo de la sección anterior, aunque, en la práctica, más potente y sistemático.

Si la función es lineal y puede describirse mediante una matriz estocástica , es decir, una matriz cuyas filas o columnas suman uno, entonces el sistema iterado se conoce como cadena de Markov .

Hay muchos mapas caóticos . Entre las funciones iteradas más conocidas se incluyen el conjunto de Mandelbrot y los sistemas de funciones iteradas .

Ernst Schröder , ^{[ 20 ]} en 1870, desarrolló casos especiales del mapa logístico , como el caso caótico f ( x ) = 4 x (1 − x ) , de modo que Ψ( x ) = arcsin( √ x ) ² , por lo tanto f ⁿ ( x ) = sin(2 ⁿ arcsin( √ x )) ² .

Un caso no caótico que Schröder también ilustró con su método, f ( x ) = 2 x (1 − x ) , produjo Ψ( x ) = − ⁠ 1 / 2 ⁠ ln(1 − 2 x ) , y por lo tanto f ⁿ ( x ) = − ⁠ 1 / 2 ⁠ ((1 − 2 x ) ^{2 n} − 1) .

Si f es la acción de un elemento de grupo sobre un conjunto, entonces la función iterada corresponde a un grupo libre .

La mayoría de las funciones no tienen expresiones explícitas de forma cerrada general para la n -ésima iteración. La tabla siguiente enumera algunas ^{[ 20 ]} que sí las tienen. Nótese que todas estas expresiones son válidas incluso para n no entero y negativo , así como para n entero no negativo .

Nota: estos dos casos especiales de ax² + bx + c son los únicos que tienen una solución analítica. Al elegir b = ² = – a y b = 4 = – a , respectivamente, se reducen aún más a los casos logísticos no caóticos y caóticos que se analizaron antes de la tabla.

Algunos de estos ejemplos están relacionados entre sí mediante conjugaciones simples.

Las funciones iteradas pueden estudiarse con la función zeta de Artin-Mazur y con operadores de transferencia .

En informática , las funciones iteradas se presentan como un caso especial de funciones recursivas , que a su vez constituyen la base del estudio de temas tan amplios como el cálculo lambda , o de otros más específicos, como la semántica denotacional de los programas informáticos.

Dos funcionales importantes pueden definirse en términos de funciones iteradas. Estos son la sumatoria :

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

y el producto equivalente:

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

La derivada funcional de una función iterada viene dada por la fórmula recursiva:

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

Las funciones iteradas aparecen en el desarrollo en serie de funciones combinadas, como g ( f ( x )) .

Dada la velocidad de iteración , o función beta (física) ,

${\displaystyle v(x)=\left.{\frac {\partial f^{n}(x)}{\partial n}}\right|_{n=0}}$

Para la n ^-ésima iteración de la función f , tenemos ^{[ 22 ]}

${\displaystyle g(f(x))=\exp \left[v(x){\frac {\partial }{\partial x}}\right]g(x).}$

Por ejemplo, para la advección rígida, si f ( x ) = x + t , entonces v ( x ) = t . En consecuencia, g ( x + t ) = exp( t ∂/∂ x ) g ( x ) , acción de un operador de desplazamiento simple .

Por el contrario, se puede especificar f ( x ) dado un v ( x ) arbitrario , a través de la ecuación de Abel genérica discutida anteriormente,

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

dónde

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

Esto se evidencia al observar que

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

Para un índice de iteración continuo t , entonces, ahora escrito como un subíndice, esto equivale a la célebre realización exponencial de Lie de un grupo continuo,

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

La velocidad de flujo inicial v es suficiente para determinar todo el flujo, dada esta realización exponencial que proporciona automáticamente la solución general a la ecuación funcional de traslación , ^{[ 23 ]}

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

• Gill, John (enero de 2017). "Introducción a la teoría elemental de composiciones infinitas de funciones complejas" . Universidad Estatal de Colorado.