# Sistemas de funções iterativas

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

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

### 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

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.