Sistemas de funções iterativas

 Nota: Se procura Ifs, uma comuna francesa, veja Ifs.

Sistemas de funções iterativas ou sistemas de funções iteradas, também conhecidos pela sigla IFS (do inglês Iterated Function Systems) é uma técnica de se construir figuras fractais através da repetição em escala de uma mesma figura. Apesar de poder ser aplicada em qualquer número de dimensões, a técnica de sistemas de funções iterativas é mais comum em figuras bidimensionais, por questões práticas.

A técnica consiste em selecionar uma figura inicial qualquer e aplicar iterativamente a ela uma série de transformações afins (de onde o nome "sistemas de funções iterativas"), em geral com redução de escala, que geram "cópias" menores da mesma imagem. Este procedimento é repetido infinitamente até se obter uma imagem composta de infinitas cópias cada vez menores da mesma imagem.

Os sistemas de funções iterativas podem ser matematicamente definidos da seguinte maneira:

Seja um espaço ${\displaystyle X}$ e seu correspondente espaço métrico ${\displaystyle (X,d)}$ (onde ${\displaystyle d}$ é uma métrica para o espaço ${\displaystyle X}$), uma transformação ${\displaystyle F:X\rightarrow X}$ é contrativa (também dito um mapeamento contrativo) se existir um fator de contratividade ${\displaystyle s|0\leq s\leq 1}$ tal que: ${\displaystyle d(f(x),f(y))\leq s.d(x,y),\forall x,y\in X}$.

Um sistema de funções iterativas é um conjunto finito de funções contrativas ${\displaystyle f_{i}:X\rightarrow X}$, que pode ser definido também da seguinte forma:

${\displaystyle S=\bigcup _{i}^{N}f_{i}(S),\,}$

onde

${\displaystyle S\subset \mathbb {R} ^{n}\,}$

e

${\displaystyle f_{i}:\mathbb {R} ^{n}\to \mathbb {R} ^{n}.}$

Sendo S o ponto fixo de uma operador de Hutchinson, que é a união das funções ${\displaystyle f_{i}}$^[1]. Por se tratarem sempre de funções contrativas, o sistema eventualmente converge para um atrator, que é a figura final do fractal.

O uso mais comum sendo restrito a transformações afins bidimensionais,^[2] podemos considerar que um sistema de funções iteradas é um conjunto de transformações afins ${\displaystyle S=\bigcup _{i}^{N}w_{i}(S),w_{i}:\mathbb {R} ^{2}\to \mathbb {R} ^{2}}$.

Existem basicamente duas técnicas de se calcular os fractais definidos por um sistema de funções iterativas: uma forma determinística, e uma não determinística, conhecida também como Jogo do caos (ou em inglês Chaos Game).

A forma determinística consiste em em escolher um conjunto inicial ${\displaystyle A_{0}\subset \mathbb {R} ^{2}}$ e aplicar as transformações ${\displaystyle w_{n}\in S}$ nos elementos do conjunto ${\displaystyle A_{0}}$, de forma a gerar um novo conjunto ${\displaystyle A_{1}}$, e repetir o mesmo procedimento nos novos conjuntos gerados iterativamente de forma que:

${\displaystyle A_{n+1}=\bigcup _{i=1}^{N}w_{i}(A_{n})}$

Na figura abaixo vemos a construção de um Triângulo de Sierpinski:

Deve-se notar que o conjunto inicial ${\displaystyle A_{0}}$ não precisa ser relacionado com o atrator, que será o conjunto final ${\displaystyle A_{n}}$ quando ${\displaystyle n}$ tender a ${\displaystyle \infty }$. O exemplo abaixo mostra isso intuitivamente para o Triângulo de Sierpinski:

Entretanto o poder computacional para executar o cálculo dessa forma cresce exponencialmente com poucos passos, por isso utiliza-se quase sempre o cálculo não determinístico. ^{[carece de fontes?][3]}

O Jogo do Caos é a forma não determinística de se calcular os sistemas de funções iterativas, e funciona da seguinte maneira: A cada uma das funções ${\displaystyle w_{n}}$ é atribuída uma probabilidade de aplicação ${\displaystyle p_{n}}$. Escolhe-se um ponto inicial ${\displaystyle d_{0}\in X}$ (onde ${\displaystyle X}$ é o conjunto métrico definido anteriormente, em geral ${\displaystyle X=\mathbb {R} ^{2}}$) de forma aleatória (alternativamente pode-se escolher ${\displaystyle d_{0}}$ como um ponto pertencente ao atrator).^[4] Aplica-se então as funções ${\displaystyle w_{i}}$ de forma aleatória, escolhendo cada uma de acordo com sua probabilidade. Pode-se provar que aplicação das funções de forma indefinida acaba por convergir para o atrator do sistema.^[5]

As probabilidades de aplicação das funções ${\displaystyle w_{n}}$ não influenciam na figura final, mas são um importante recurso para otimizar computacionalmente o processo. Comparativamente com o método determinístico, pode-se ajustar as probabilidades de aplicação de cada uma das funções ${\displaystyle w_{i}}$ de forma que os pontos mais facilmente visualizados na figura sejam calculados mais rapidamente, enquanto os pontos menos visíveis demorem mais tempo a serem encontrados.^[5]

O exemplo mais comum de sistema de funções iterativas é o sistema conhecido como Sierpinski Gasket, ou Triângulo de Sierpinski. As funções que compões este sistema são:

${\displaystyle f_{1}(x,y)=({\tfrac {1}{2}}x,{\tfrac {1}{2}}y)}$

${\displaystyle f_{2}(x,y)=({\tfrac {1}{2}}x+1,{\tfrac {1}{2}}y)}$

${\displaystyle f_{3}(x,y)=({\tfrac {1}{2}}x+{\tfrac {1}{2}},{\tfrac {1}{2}}y+1)}$

Ou ainda, na notação complexa mais comumente usada:

${\displaystyle f_{1}(c)={\frac {c}{2}}}$

${\displaystyle f_{2}(c)={\frac {c}{2}}+1}$

${\displaystyle f_{3}(c)={\frac {c}{2}}+{\tfrac {1}{2}}+i}$

Ou seja, 3 cópias do conjunto inicial são feitas, na metade do tamanho, cada uma se posicionando em um dos extremos de um triângulo, deixando o centro do triângulo livre.

Para o Jogo do Caos pode se usar as probabilidades uniformes ${\displaystyle p_{1}=p_{2}=p_{3}={\tfrac {1}{3}}}$. O resultado se assemelha a figura ao lado, onde cada cor corresponde a uma das funções.

Um exemplo de sistema de funções iterativas tridimensional é a esponja de Menger que também pode ser vista ao lado. A Técnica pode ser estendida além das 3 dimensões, gerando fractais multi-dimensionais.

Abaixo temos uma implementação simples em javascript que desenha um fractal do tipo Triângulo de Sierpinski usando o método de Jogo do Caos.

	function run() {
	    // cria o elemento onde será desenhado o fractal
	    var canvas = document.getElementById('canvas');
	    var context = canvas.getContext("2d");
	    // seleção da cor
	    context.fillStyle = 'RED';
	    // inicia com pontos aleatórios
	    var x = Math.random();
	    var y = Math.random();
	    // 500 iterações
	    for (var i = 0; i < 500; i++) {
	    	var prob = Math.random();
	    	var xy;
	    	// executa aleatóriamente uma das funções.
	    	if (prob < 1/3)
	    		xy = gasket1(x, y);
	    	else if (prob < 2/3)
	    		xy = gasket2(x, y);
	    	else
	    		xy = gasket3(x, y);
	    	x = xy[0];
	    	y = xy[1];
	    	// converte a escala para a escala da tela
	    	xy = scale(xy);
	    	// marca o ponto na tela
	    	context.fillRect(xy[0], xy[1], 1, 1);
	    }
	}
	
	// converte a escala de (-1,1) para (0, 500);
	function scale(xy) {
	  return new Array(
	    xy[0] * 250,
	    (2 - xy[1]) * 250);
	}
	
	// systema de funções para triangulo e Sierpinski
	function gasket1(x, y) {
	  return new Array(0.5 * x, 0.5 * y);
	}
	function gasket2(x, y) {
	  return new Array(0.5 * x + 1, 0.5 * y);
	}
	function gasket3(x, y) {
	  return new Array(0.5 * x + 0.5, 0.5 * y + 1);
	}

• Fractal
• Arte fractal

• Geometria Fractal no site do LVCoN
• Tutorial sobre fractais
• Applet java que calcula fractais usando IFS
• Página em javascript que calcula fractais usando IFS.