Sistemas de funções iterativas

Chama fractal usando sistemas de funções iteradas não lineares em três dimensões.

 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.

Definição

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

Seja um espaço $X$ e seu correspondente espaço métrico $(X,d)$ (onde $d$ é uma métrica para o espaço $X$), uma transformação $F:X\rightarrow X$ é contrativa (também dito um mapeamento contrativo) se existir um fator de contratividade $s|0\leq s\leq 1$ tal que: $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 $f_{i}:X\rightarrow X$, que pode ser definido também da seguinte forma:

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

onde

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

e

$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 $f_{i}$. 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, podemos considerar que um sistema de funções iteradas é um conjunto de transformações afins $S=\bigcup _{i}^{N}w_{i}(S),w_{i}:\mathbb {R} ^{2}\to \mathbb {R} ^{2}$.

Cálculo dos fractais

Curva do dragão de Lévy

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 $A_{0}\subset \mathbb {R} ^{2}$ e aplicar as transformações $w_{n}\in S$ nos elementos do conjunto $A_{0}$, de forma a gerar um novo conjunto $A_{1}$, e repetir o mesmo procedimento nos novos conjuntos gerados iterativamente de forma que:

$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 $A_{0}$ não precisa ser relacionado com o atrator, que será o conjunto final $A_{n}$ quando $n$ tender a $\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]}

Jogo do Caos

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 $w_{n}$ é atribuída uma probabilidade de aplicação $p_{n}$. Escolhe-se um ponto inicial $d_{0}\in X$ (onde $X$ é o conjunto métrico definido anteriormente, em geral $X=\mathbb {R} ^{2}$) de forma aleatória (alternativamente pode-se escolher $d_{0}$ como um ponto pertencente ao atrator). Aplica-se então as funções $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.

As probabilidades de aplicação das funções $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 $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.

Exemplos

Triângulo de Sierpinski

Esponja de Menger, um exemplo de fractal tridimensional

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:

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

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

$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:

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

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

$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 $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.

Implementação

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);
	}

Ver também

• Fractal
• Arte fractal

Ligações externas

• 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.