Sistemas de funções iterativas

De GirinoWiki

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 IFS é 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.

Tabela de conteúdo

1 Definição
2 Cálculo dos fractais
- 2.1 Jogo do Caos
3 Exemplos
4 Ver também
5 Links
6 Notas e referências

[editar] 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 \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\,$

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

[editar] Cálculo dos fractais

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

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. Predefinição:Carece de fontes^[3]

[editar] 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^[4].

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

[editar] Exemplos

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.

Imagem:Sierpinski1.png

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.

Imagem:Menger sponge (IFS).jpg

Um exemplo de IFS 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.

[editar] Ver também

[editar] Links

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.

[editar] Notas e referências

↑ ^1,0 ^1,1 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).
↑ 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.
↑ Ver discussão do artigo.
↑ ^4,0 ^4,1 SALOMON, David. Data Compression: The Complete Reference. 2.ed. Nova Iorque: Springer, 2000. ISBN 0-387-95045-1