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.
Disambig grey.svg 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[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:

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[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 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. 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.
  2. Erro de citação: Tag <ref> inválida; não foi fornecido texto para as refs chamadas wen
  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 (2000). Data Compression. The Complete Reference 2 ed. Springer [S.l.] ISBN 0-387-95045-1.  para mais informações.
  5. a b SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Springer [S.l.] ISBN 0-387-95045-1.