En matemáticas , los sistemas de funciones iteradas ( IFS ) son un método para construir fractales ; los fractales resultantes suelen ser autosemejantes . Los fractales IFS están más relacionados con la teoría de conjuntos que con la geometría fractal. [1] Fueron introducidos en 1981.
Los fractales IFS , como normalmente se les llama, pueden tener cualquier cantidad de dimensiones, pero comúnmente se calculan y dibujan en 2D. El fractal está formado por la unión de varias copias de sí mismo, siendo cada copia transformada por una función (de ahí "sistema de funciones"). El ejemplo canónico es el triángulo de Sierpiński . Las funciones normalmente son contractivas , lo que significa que acercan puntos y hacen que las formas sean más pequeñas. Por lo tanto, la forma de un fractal IFS está formada por varias copias más pequeñas de sí mismo posiblemente superpuestas, cada una de las cuales también está formada por copias de sí mismo, ad infinitum . Ésta es la fuente de su naturaleza fractal autosemejante.
Formalmente, un sistema de funciones iteradas es un conjunto finito de asignaciones de contracción en un espacio métrico completo . [2] Simbólicamente,
Es un sistema de funciones iteradas si cada una es una contracción en el espacio métrico completo .
Hutchinson demostró que, para el espacio métrico , o más generalmente, para un espacio métrico completo , tal sistema de funciones tiene un conjunto fijo S único, compacto , no vacío (cerrado y acotado) . [3] Una forma de construir un conjunto fijo es comenzar con un conjunto inicial no vacío, cerrado y acotado S 0 e iterar las acciones de f i , tomando S n +1 como la unión de las imágenes de S n bajo f i ; luego tomando S como el cierre del límite . Simbólicamente, el conjunto único fijo (compacto no vacío) tiene la propiedad
El conjunto S es, por tanto, el conjunto fijo del operador de Hutchinson definido para vía
La existencia y unicidad de S es una consecuencia del principio de mapeo de contracción , al igual que el hecho de que
para cualquier conjunto compacto no vacío en . (Para IFS contractivo, esta convergencia tiene lugar incluso para cualquier conjunto acotado cerrado no vacío ). Se pueden obtener elementos aleatorios arbitrariamente cercanos a S mediante el "juego del caos", que se describe a continuación.
Recientemente se demostró que los IFS de tipo no contractivo (es decir, compuestos de mapas que no son contracciones con respecto a ninguna métrica topológicamente equivalente en X ) pueden producir atractores. Estos surgen de forma natural en espacios proyectivos, aunque también se puede adaptar la rotación irracional clásica en el círculo. [4]
La colección de funciones genera un monoide bajo composición . Si sólo hay dos funciones de este tipo, el monoide se puede visualizar como un árbol binario , donde, en cada nodo del árbol, se puede componer con una u otra función ( es decir, tomar la rama izquierda o derecha). En general, si hay k funciones, entonces se puede visualizar el monoide como un árbol k -ario completo , también conocido como árbol de Cayley .
A veces se requiere que cada función sea una transformación lineal , o más generalmente afín , y por lo tanto representada por una matriz . Sin embargo, los IFS también pueden construirse a partir de funciones no lineales, incluidas transformaciones proyectivas y transformaciones de Möbius . La llama Fractal es un ejemplo de IFS con funciones no lineales.
El algoritmo más común para calcular fractales IFS se llama " juego del caos ". Consiste en elegir un punto aleatorio en el plano y luego aplicar iterativamente una de las funciones elegidas al azar del sistema de funciones para transformar el punto y obtener el siguiente punto. Un algoritmo alternativo consiste en generar cada secuencia posible de funciones hasta una longitud máxima determinada y luego trazar los resultados de aplicar cada una de estas secuencias de funciones a un punto o forma inicial.
Cada uno de estos algoritmos proporciona una construcción global que genera puntos distribuidos a lo largo de todo el fractal. Si se dibuja un área pequeña del fractal, muchos de estos puntos quedarán fuera de los límites de la pantalla. Esto hace que no sea práctico hacer zoom en una construcción IFS dibujada de esta manera.
Aunque la teoría de IFS requiere que cada función sea contractiva, en la práctica el software que implementa IFS solo requiere que todo el sistema sea contractivo en promedio. [5]
Los PIFS (sistemas de funciones iteradas particionadas), también llamados sistemas de funciones iteradas locales, [6] ofrecen una compresión de imagen sorprendentemente buena, incluso para fotografías que no parecen tener los tipos de estructura autosimilar que muestran los fractales IFS simples. [7]
Existen algoritmos muy rápidos para generar una imagen a partir de un conjunto de parámetros IFS o PIFS. Es más rápido y requiere mucho menos espacio de almacenamiento para almacenar una descripción de cómo se creó, transmitir esa descripción a un dispositivo de destino y regenerar esa imagen nuevamente en el dispositivo de destino, que almacenar y transmitir el color de cada píxel de la imagen. . [6]
El problema inverso es más difícil: dada alguna imagen digital arbitraria original, como una fotografía digital, intente encontrar un conjunto de parámetros IFS que, cuando se evalúe mediante iteración, produzca otra imagen visualmente similar a la original. En 1989, Arnaud Jacquin presentó una solución a una forma restringida del problema inverso utilizando únicamente PIFS; la forma general del problema inverso sigue sin resolverse. [8] [9] [6]
A partir de 1995, todo el software de compresión fractal se basa en el enfoque de Jacquin. [9]
El diagrama muestra la construcción de un IFS a partir de dos funciones afines. Las funciones se representan por su efecto sobre el cuadrado biunitario (la función transforma el cuadrado delineado en el cuadrado sombreado). La combinación de las dos funciones forma el operador de Hutchinson . Se muestran tres iteraciones del operador y luego la imagen final es del punto fijo, el fractal final.
Los primeros ejemplos de fractales que pueden generarse mediante un IFS incluyen el conjunto de Cantor , descrito por primera vez en 1884; y las curvas de Rham , un tipo de curva autosemejante descrita por Georges de Rham en 1957.
Los IFS fueron concebidos en su forma actual por John E. Hutchinson en 1981 [3] y popularizados por el libro Fractals Everywhere de Michael Barnsley .
Los IFS proporcionan modelos para ciertas plantas, hojas y helechos, en virtud de la autosimilitud que a menudo ocurre en las estructuras ramificadas en la naturaleza.
—Michael Barnsley y otros. [10]