Sistemas de funções iterativas

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Chama fractal usando sistemas de funções iteradas não lineares em três dimensões.

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[editar | editar código-fonte]

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 \le s \le 1 tal que: d(f(x), f(y)) \le 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[1] :

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[2] . 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[1] , 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[editar | editar código-fonte]

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:

Sierpinski triangle evolution.svg

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:

Sierpinski triangle evolution square.svg

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]

Jogo do Caos[editar | editar código-fonte]

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)[4] . 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[5] .

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[5] .

Exemplos[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]

Notas e referências[editar | editar código-fonte]

  1. a b De acordo com a wikipedia em inglês, disponível em: Iterated function system, http://en.wikipedia.org/w/index.php?title=Iterated_function_system&oldid=140722379 (Última visita em Jul. 11, 2007).
  2. Esta definição é na verdade um subconjunto da definição anterior, já que restringe as funções ao espaço \mathbb{R}^n e não a qualquer espaço métrico.
  3. Ver discussão do artigo.
  4. Quando se escolhe um ponto fora do atrator pode levar algumas iterações até que o ponto converja para o atrator, isso pode causar um gráfico com alguns pontos "externos" ao atrator. Ver SALOMON, David. Data Compression: The Complete Reference. 2 ed. Nova Iorque: Springer, 2000. ISBN 0-387-95045-1 para mais informações.
  5. a b SALOMON, David. Data Compression: The Complete Reference. 2 ed. Nova Iorque: Springer, 2000. ISBN 0-387-95045-1