Grupo - Modelo Sznajd

2018-01-25T05:38:34Z

Csdionatan: /* Aplicações */

== Introdução ==
O Modelo de Sznajd ou '''United we stand, divided we fall (USDF)''' é um modelo recente, proposto em 2000 para entender a dinâmica de opiniões através da física estatística. No ponto de vista de um físico, o comportamento de indivíduos a as interações entre eles constituem um nível microscópico de um sistema social. O modelo introduz o fenômeno chamado validação social:

'''Validação Social:''' Se duas pessoas compartilham da mesma opinião, os seus vizinhos começarão a concordar com elas.

'''Discordância Destrutiva:''' Se as pessoas discordam, os vizinhos começarão a argumentar com elas.

== O método e Formulação Matemática ==
Opinião social é vinda de opiniões individuais, representadas neste modelo por spins de Ising de forma ''"yes"'' e ''"no"''. A dinâmica segue a relação da validação social:

# A cada timestep um par de sping <math> S_{i}, S_{i+1}</math> são escolhidos para tentar mudar os seus vizinhos mais próximos
# Se <math> S_{i} = S_{i+1}</math>, então <math> S_{i-1} = S_{i}</math> e <math> S_{i+2} = S_{i}</math> (''validação social'')
# Se <math> S_{i} = -S_{i+1}</math>, então <math> S_{i-1} = S_{i+1}</math> e <math> S_{i+2} = S_{i}</math>

No modelo, dois tipos de estados estacionários são alcançáveis: consenso completo(ferromagnético) e impasse(antiferromagnético). A principal diferença para o Ising é que a informação flui para fora. O modelo de Sznajd ou USDF tem sido modificado e utilizado em marketing, política e finanças.

== Modificações ==
Fala-se que o estado antes mencionado, o antiferromagnetismo, pode ser considerado não realístico para representar o comportamento de indivíduos em uma sociedade. Para tentar evitar este caso, propõe-se o seguinte:

# A cada timestep um par de sping <math> S_{i}, S_{i+1}</math> são escolhidos para tentar mudar os seus vizinhos mais próximos igual anteriomente
# Se <math> S_{i} = S_{i+1}</math>, então <math> S_{i-1} = S_{i}</math> e <math> S_{i+2} = S_{i}</math> (''validação social'')
# Se <math> S_{i} = -S_{i+1}</math>, então <math> S_{i-1} = S_{i}</math> e <math> S_{i+2} = S_{i}</math>

Estas regras ficaram conhecidas como algo do tipo: "Se você não sabe o que fazer, ou faz nada ou faz qualquer coisa." É um tanto quanto óbvio que o modelo unidimensional não representa bem um sistema social e que modelos bidimensionais são bem mais realistas. Algo interessante mencionar é a atualização simultânea para sistemas de duas dimensões: uma atualização simultânea leva a uma muito maior dificuldade de atingir o estado de consenso total. Isso foi mostrado por Stauffer<ref>D. Stauffer D, J Math Sociol 28 25 (2004)</ref> e a rezão para isso é que alguns recebem simultaneamente distintas informações de diferentes vizinhos, o que leva a não aceitar a opinião.

Regras para rede quadrada <math>LxL</math>:

# Se conjunto 2x2 de 4 vizinhos não tiverem todos os seus spins paralelos, deixam os seus oito vizinhos sem modificações
# Um par de vizinhos convence seus seis vizinhos a seguirem a sua orientação se o par de spins for paralelo.

A regra de atualização para duas dimensões pode ser obtida pela regra em uma dimensão: A regra e 1D é aplicada para cada uma das 4 cadeias de spins, como mostra a próxima figura:
[[Arquivo:1.jpg]]

Isto foi mostrado por Gallam<ref>S. Galam, J. Stat. Phys. 61, 943 (1990)</ref>

== Generalização ==
Para a generalização desse método para a rede quadrada <math>L</math>x<math>L</math> onde cada spin pode estar para cima ou para baixo e utiliza-se condições periódicas de contorno. As regras <ref>D. Stauffer,A.O. Sousa,M. De Oliveira, Int. J. Mod. Phys. C 11 1239</ref> esquematizadas:
[[Arquivo:2.jpg]]

<math>I.</math> Um conjunto 2x2 de quatro vizinhos é escolhido e se todos não forem paralelos, deixa os seus oito vizinhos sem mudanças. Se não, seguem duas regras:
#<math>I_a</math> Os vizinhos seguem a orientação do conjunto.
#<math>I_b</math> Os vizinhos seguem a orientação oposta ao conjunto.

<math>II.</math> Um par vizinho tenta convencer seus seis vizinhos a seguir a orientação do par apenas se o par tiver spins paralelos. Caso contrário, seguem três regras horizontais mas com regras verticais completamente análogas:
#<math>II_a</math> Os vizinhos não mudam
#<math>II_b</math> Os três vizinhos da esquerda seguem a orientação do spin da esquerda do par e os três da direita seguem o spin da direita
#<math>II_c</math> Os três vizinhos da esquerda seguem a orientação do spin da direita do par e os três da direita seguem o spin da esquerda (oposto a anterior)

<math>III.</math> A regra de 1D é aplicada para cada uma das quatro linhas de quatro spins cada.

Regra <math>I_a:</math> pontos fixos com spins todos para cima ou para baixo

Regra <math>I_b:</math> sem pontos fixos

Regra <math>II_a</math> e <math>II_b:</math> pontos fixos com spins todos para cima ou para baixo

Regra <math>II_c:</math> Para L par ten-se ou tudo para cima ou para baixo. Para L ímpar também a o ponto antiferromagnético

Regra <math>III:</math> pontos fixos com spins todos para cima ou para baixo com L ímpar

== Aplicações ==
O modelo de Sznajd pode ser utilizado em política, marketing e finanças. Um caso especial está em <ref>A. T. BERNARDES et al, Int. J. Mod. Phys. C 12, 159 (2001)</ref>

Reproduzimos o modelo mostrado no paper, usando uma rede quadrada <math>NxN</math> com <math>N = 1000</math>. Ao invés de usar um modelo de spin (-1 ou 1), o modelo simula eleições brasileiras, usando um numero de políticos escolhido como <math>N_p = 600</math>. Usando a condição de seleção <math>IIa</math>, cada vez que dois vizinhos tem a mesma opinião, todos os seus 6 vizinhos adquirem a mesma opinião.

Nossa condição inicial é montada selecionando todos os eleitores aleatoriamente, dando-os uma probabilidade <math>P = \frac{n^2}{N^2}</math> de escolher um candidato <math>n</math>. Ao escolher um candidado, ele tem uma mesma probabilidade <math>P</math> de tentar convencer seus vizinhos (<math>P</math> nesse caso age como o poder de convencimento de um candidato). Na imagem podemos ver a distribuição de votos por politico, que segue uma lei de potências.

[[Arquivo:init.png|x300px]]

Em seguida, realizamos passos de Monte Carlo, selecionando aleatóriamente <math>N^2</math> eleitores (que podem se repetir) e os fazemos tentar convencer um de seus 4 vizinhos, seguindo a mesma regra.

Nosso modelo tenta estudar a fase de transição do modelo (passos de Monte Carlo <math>1 << t << 10^5</math>), dado que num processo eleitoral os votos não atingem um equilíbrio. A imagem mostra a distribuição desses votos.

[[Arquivo:anferparty.png|x300px]]

Após essa distribuição, podemos estudar como se dividem os votos. A imagem mostra a distribuição acumulada dos votos, em azul logo após a distribuição inicial (lei de potência com inclinação -1/2), e após os passos de Monte Carlo (com inclinação -1). Vemos que muitos poucos candidatos recebem a maioria dos votos, fato que concorda com o caso real. <ref>R. N. Costa-Filho, M. P. Almeida, J. S. Andrade Jr., and J. E. Moreira, Phys. Rev. E 60, 1067 (1999)</ref> [[Arquivo:final.png|x300px]]

Uma maneira de visualizar o processo é vendo o que acontece em uma rede quadrada 50x50 com 6 candidatos. O sistema converge para um candidato dominando devido ao tamanho da rede. Para uma rede maior, há uma competição entre vários candidatos dentro do limite de transição.

[[Arquivo:foobar.gif|x300px]]

==Bibliografia==
<references/>

Grupo - Modelo Sznajd

2018-01-25T05:34:56Z

2018-01-25T05:29:44Z

Csdionatan: /* Aplicações */

== Introdução ==
O Modelo de Sznajd ou '''United we stand, divided we fall (USDF)''' é um modelo recente, proposto em 2000 para entender a dinâmica de opiniões através da física estatística. No ponto de vista de um físico, o comportamento de indivíduos a as interações entre eles constituem um nível microscópico de um sistema social. O modelo introduz o fenômeno chamado validação social:

'''Validação Social:''' Se duas pessoas compartilham da mesma opinião, os seus vizinhos começarão a concordar com elas.

'''Discordância Destrutiva:''' Se as pessoas discordam, os vizinhos começarão a argumentar com elas.

== O método e Formulação Matemática ==
Opinião social é vinda de opiniões individuais, representadas neste modelo por spins de Ising de forma ''"yes"'' e ''"no"''. A dinâmica segue a relação da validação social:

# A cada timestep um par de sping <math> S_{i}, S_{i+1}</math> são escolhidos para tentar mudar os seus vizinhos mais próximos
# Se <math> S_{i} = S_{i+1}</math>, então <math> S_{i-1} = S_{i}</math> e <math> S_{i+2} = S_{i}</math> (''validação social'')
# Se <math> S_{i} = -S_{i+1}</math>, então <math> S_{i-1} = S_{i+1}</math> e <math> S_{i+2} = S_{i}</math>

No modelo, dois tipos de estados estacionários são alcançáveis: consenso completo(ferromagnético) e impasse(antiferromagnético). A principal diferença para o Ising é que a informação flui para fora. O modelo de Sznajd ou USDF tem sido modificado e utilizado em marketing, política e finanças.

== Modificações ==
Fala-se que o estado antes mencionado, o antiferromagnetismo, pode ser considerado não realístico para representar o comportamento de indivíduos em uma sociedade. Para tentar evitar este caso, propõe-se o seguinte:

# A cada timestep um par de sping <math> S_{i}, S_{i+1}</math> são escolhidos para tentar mudar os seus vizinhos mais próximos igual anteriomente
# Se <math> S_{i} = S_{i+1}</math>, então <math> S_{i-1} = S_{i}</math> e <math> S_{i+2} = S_{i}</math> (''validação social'')
# Se <math> S_{i} = -S_{i+1}</math>, então <math> S_{i-1} = S_{i}</math> e <math> S_{i+2} = S_{i}</math>

Estas regras ficaram conhecidas como algo do tipo: "Se você não sabe o que fazer, ou faz nada ou faz qualquer coisa." É um tanto quanto óbvio que o modelo unidimensional não representa bem um sistema social e que modelos bidimensionais são bem mais realistas. Algo interessante mencionar é a atualização simultânea para sistemas de duas dimensões: uma atualização simultânea leva a uma muito maior dificuldade de atingir o estado de consenso total. Isso foi mostrado por Stauffer<ref>D. Stauffer D, J Math Sociol 28 25 (2004)</ref> e a rezão para isso é que alguns recebem simultaneamente distintas informações de diferentes vizinhos, o que leva a não aceitar a opinião.

Regras para rede quadrada <math>LxL</math>:

# Se conjunto 2x2 de 4 vizinhos não tiverem todos os seus spins paralelos, deixam os seus oito vizinhos sem modificações
# Um par de vizinhos convence seus seis vizinhos a seguirem a sua orientação se o par de spins for paralelo.

A regra de atualização para duas dimensões pode ser obtida pela regra em uma dimensão: A regra e 1D é aplicada para cada uma das 4 cadeias de spins, como mostra a próxima figura:
[[Arquivo:1.jpg]]

Isto foi mostrado por Gallam<ref>S. Galam, J. Stat. Phys. 61, 943 (1990)</ref>

== Generalização ==
Para a generalização desse método para a rede quadrada <math>L</math>x<math>L</math> onde cada spin pode estar para cima ou para baixo e utiliza-se condições periódicas de contorno. As regras <ref>D. Stauffer,A.O. Sousa,M. De Oliveira, Int. J. Mod. Phys. C 11 1239</ref> esquematizadas:
[[Arquivo:2.jpg]]

<math>I.</math> Um conjunto 2x2 de quatro vizinhos é escolhido e se todos não forem paralelos, deixa os seus oito vizinhos sem mudanças. Se não, seguem duas regras:
#<math>I_a</math> Os vizinhos seguem a orientação do conjunto.
#<math>I_b</math> Os vizinhos seguem a orientação oposta ao conjunto.

<math>II.</math> Um par vizinho tenta convencer seus seis vizinhos a seguir a orientação do par apenas se o par tiver spins paralelos. Caso contrário, seguem três regras horizontais mas com regras verticais completamente análogas:
#<math>II_a</math> Os vizinhos não mudam
#<math>II_b</math> Os três vizinhos da esquerda seguem a orientação do spin da esquerda do par e os três da direita seguem o spin da direita
#<math>II_c</math> Os três vizinhos da esquerda seguem a orientação do spin da direita do par e os três da direita seguem o spin da esquerda (oposto a anterior)

<math>III.</math> A regra de 1D é aplicada para cada uma das quatro linhas de quatro spins cada.

Regra <math>I_a:</math> pontos fixos com spins todos para cima ou para baixo

Regra <math>I_b:</math> sem pontos fixos

Regra <math>II_a</math> e <math>II_b:</math> pontos fixos com spins todos para cima ou para baixo

Regra <math>II_c:</math> Para L par ten-se ou tudo para cima ou para baixo. Para L ímpar também a o ponto antiferromagnético

Regra <math>III:</math> pontos fixos com spins todos para cima ou para baixo com L ímpar

== Aplicações ==
O modelo de Sznajd pode ser utilizado em política, marketing e finanças. Um caso especial está em <ref>A. T. BERNARDES et al, Int. J. Mod. Phys. C 12, 159 (2001)</ref>

Reproduzimos o modelo mostrado no paper, usando uma rede quadrada <math>NxN</math> com <math>N = 1000</math>. Ao invés de usar um modelo de spin (-1 ou 1), o modelo simula eleições brasileiras, usando um numero de políticos escolhido como <math>N_p = 600</math>. Usando a condição de seleção <math>IIa</math>, cada vez que dois vizinhos tem a mesma opinião, todos os seus 6 vizinhos adquirem a mesma opinião.

Nossa condição inicial é montada selecionando todos os eleitores aleatoriamente, dando-os uma probabilidade <math>P = \frac{n^2}{N^2}</math> de escolher um candidato <math>n</math>. Ao escolher um candidado, ele tem uma mesma probabilidade <math>P</math> de tentar convencer seus vizinhos (<math>P</math> nesse caso age como o poder de convencimento de um candidato). Na imagem podemos ver [[Arquivo:init.png]] a distribuição de votos por politico, que segue uma lei de potências.

Em seguida, realizamos passos de Monte Carlo, selecionando aleatóriamente <math>N^2</math> eleitores (que podem se repetir) e os fazemos tentar convencer um de seus 4 vizinhos, seguindo a mesma regra.

Nosso modelo tenta estudar a fase de transição do modelo (passos de Monte Carlo <math>1 << t << 10^5</math>), dado que num processo eleitoral os votos não atingem um equilíbrio. A imagem mostra a distribuição desses votos [[Arquivo:anferparty.png]]

Após essa distribuição, podemos estudar como se dividem os votos. A imagem mostra [[Arquivo:final.png]] a distribuição acumulada dos votos, em azul logo após a distribuição inicial (lei de potência com inclinação -1/2), e após os passos de Monte Carlo (com inclinação -1). Vemos que muitos poucos candidatos recebem a maioria dos votos, fato que concorda com o caso real <ref>R. N. Costa-Filho, M. P. Almeida, J. S. Andrade Jr., and J. E. Moreira, Phys. Rev. E 60, 1067 (1999)</ref>

==Bibliografia==
<references/>

Grupo - Modelo Sznajd

== Introdução ==
O Modelo de Sznajd ou '''United we stand, divided we fall (USDF)''' é um modelo recente, proposto em 2000 para entender a dinâmica de opiniões através da física estatística. O modelo introduz o fenômeno chamado validação social:

'''Validação Social:''' Se duas pessoas compartilham da mesma opinião, os seus vizinhos começarão a concordar com elas.

'''Discordância Destrutiva:''' Se as pessoas discordam, os vizinhos começarão a argumentar com elas.

== O método e Formulação Matemática ==
Opinião social é vinda de opiniões individuais, representadas neste modelo por spins de Ising de forma ''"yes"'' e ''"no"''. A dinâmica segue a relação da validação social:

# A cada timestep um par de sping <math> S_{i}, S_{i+1}</math> são escolhidos para tentar mudar os seus vizinhos mais próximos
# Se <math> S_{i} = S_{i+1}</math>, então <math> S_{i-1} = S_{i}</math> e <math> S_{i+2} = S_{i}</math> (''validação social'')
#Se <math> S_{i} = -S_{i+1}</math>, então <math> S_{i-1} = S_{i+1}</math> e <math> S_{i+2} = S_{i}</math>

No modelo, dois tipos de estados estacionários são alcançáveis: consenso completo(ferromagnético) e impasse(antiferromagnético). A principal diferença para o Ising é que a informação flui para fora.

Grupo - Modelo Sznajd

2018-01-23T16:06:20Z

Csdionatan: /* O método */

== Introdução ==
O Modelo de Sznajd ou '''United we stand, divided we fall (USDF)''' é um modelo recente, proposto em 2000 para entender a dinâmica de opiniões através da física estatística. O modelo introduz o fenômeno chamado validação social:

'''Validação Social:''' Se duas pessoas compartilham da mesma opinião, os seus vizinhos começarão a concordar com elas.

'''Discordância Destrutiva:''' Se as pessoas discordam, os vizinhos começarão a argumentar com elas.

== O método e Formulação Matemática ==
Opinião social é vinda de opiniões individuais, representadas neste modelo por spins de Ising de forma ''"yes"'' e ''"no"''. A dinâmica segue a relação da validação social:

# A cada timestep um par de sping <math> S_{i}, S_{i+1}</math> são escolhidos para tentar mudar os seus vizinhos mais próximos
# Se <math> S_{i} = S_{i+1}</math>, então <math> S_{i-1} = S_{i}</math> e <math> S_{i+2} = S_{i}</math> (''validação social'')
#Se <math> S_{i} = -S_{i+1}</math>, então <math> S_{i-1} = S_{i+1}</math> e <math> S_{i+2} = S_{i}</math>

Grupo - Modelo Sznajd

2018-01-23T15:57:32Z

Csdionatan: Criou página com '== Introdução == O Modelo de Sznajd ou '''United we stand, divided we fall (USDF)''' é um modelo recente, proposto em 2000 para entender a dinâmica de opiniões através d...'

== Introdução ==
O Modelo de Sznajd ou '''United we stand, divided we fall (USDF)''' é um modelo recente, proposto em 2000 para entender a dinâmica de opiniões através da física estatística. O modelo introduz o fenômeno chamado validação social:

'''Validação Social:''' Se duas pessoas compartilham da mesma opinião, os seus vizinhos começarão a concordar com elas.

'''Discordância Destrutiva:''' Se as pessoas discordam, os vizinhos começarão a argumentar com elas.

== O método ==
Opinião social é vinda de opiniões individuais, representadas neste modelo por spins de Ising de forma ''"yes"'' e ''"no"''.

Métodos computacionais

2018-01-23T13:58:17Z

Csdionatan: /* Modelo Sznajd */

Física computacional é uma abordagem da '''física teórica''' com o auxílio do computador essencialmente
quando a complexidade do problema impossibilita o avanço pela via analítica e/ou porque os cálculos
numéricos são longos demais para serem feitos sem automação.
Alguns consideram a '''física computacional''' um terceiro (e mais recente) vértice do triângulo da maneira de se fazer física, onde os outros dois vértices são a '''física teórica''' e a '''física experimental'''.

'''Métodos computacionais''' é a disciplina onde estudamos ferramentas, métodos e algoritmos numéricos para a resolução de problemas de física onde uma abordagem analítica é extremamente complexa ou impossível.

Alguns exemplos de aplicação são: a solução numérica de equações diferenciais ordinárias, integração numérica via métodos de aproximação ou estatísticos como método de Monte Carlo, equações diferencias parciais como as equações de Maxwell e de Schroedinger, métodos matriciais para a solução de problemas de autovalor e autovetor como os encontrados na Mecânica Quântica.

==Breve Historia da Computação==

De Conrad Zuse (1941) ao IBM Blue/Gene (2006)

==Arquitectura==

[http://en.wikipedia.org/wiki/Image:Personal_computer%2C_exploded_5.svg Diagrama de PC]

== Ferramentas ==
===== [[Comandos Unix/Linux]] =====
===== [[Gnuplot]] e [[xmgrace]] =====
===== [[LaTex]] =====
===== [[FORTRAN]] =====
===== [[C]] =====

== Métodos Computacionais A ==
===== [[Derivada Numérica]] =====
===== [[Integração Numérica]] =====
===== [[Interpolação e extrapolação]] =====
====== [[Fórmula de Lagrange]]======
====== [[Spline cúbico]]======

===== [[Zeros de Funções]]=====
===== [[Mínimos Quadrados]] =====
===== [[Listas de exercícios]] =====
====== [[Área 1]] ======
====== [[Área 2]] ======
====== [[Área 3]] ======

== Métodos Computacionais B ==

===== [[Integração numérica de equações diferenciais ordinárias]] =====

===== [[Métodos multipassos]]=====

===== [[Métodos de passo variável]]=====

===== [[Aplicações (Mapas)]]=====

===== [[Números Aleatórios]]=====

===== [[Histogramas e Densidade de Probabilidade ]] =====

===== [[Método de Monte Carlo (integração numérica)]]=====

== Métodos Computacionais C ==

===== [[Equações Diferenciais Parciais]] =====

=====[[Grupo1 - Dif em 2D]] =====

=====[[Grupo2 - Ondas1]]=====

=====[[Grupo3 - Ondas2]]=====

=====[[Grupo4 - FFT]]=====

=====[[Grupo5 - Eq. Schroedinger]]=====

=====[[Grupo - Ising 2D]]=====

===== [[Monte Carlo]] =====

=====[[Grupo - Lennard Jones]]=====

=====[[Grupo - BOIDS]]=====

=====[[Grupo - Tráfego]]=====

===== [[Teste_conv]] =====

===== [[Teste2]] =====

===== [[Grupo - Dilema Do Prisioneiro]] =====

===== [[Grupo - Modelo Sznajd]] =====

Métodos computacionais

2018-01-23T01:22:42Z

Csdionatan: /* Métodos Computacionais C */

Grupo4 - FFT

2017-10-24T00:21:51Z

Csdionatan:

A Transformada rápida de Fourier (em inglês '''Fast Fourier Transform''', ou '''FFT''') é um algoritmo que torna o cálculo da Transformada Discreta de Fourier (DFT) viável para a maior parte das aplicações.

== Transformada Discreta de Fourier ==

Em muitas aplicações se tem informação sobre um conjunto de dados, ao invés de uma função contínua. A '''Transformada Discreta de Fourier''' transforma esse conjunto de dados em um conjunto de tamanho igual com informação sobre as frequências da função que satisfaz o conjunto de dados.

Para um conjunto de dados igualmente espaçados, pode-se, ao considerar os dados como um período de uma função periódica, cujo período normalmente é considerado entre <math>[-\pi, \pi]</math> para facilitar o cálculo (e que pode sempre ser transformada em uma função nesse interválo), mostrar que a transformada discreta de Fourier pode ser dada pela equação:

<math>F_k = \sum_{n=0}^{N-1} f_n e^{-i2\pi nk/N}</math>

A sua inversa é, em paralelo ao caso da transformada contínua,

<math>f_n = \frac{1}{N} \sum_{n=0}^{N-1} F_k e^{i2\pi nk/N}</math>

A transformada também pode ser expressa em forma vetorial, como

<math>\vec{A} = \mathbf{W^{nk}} \vec{a}</math> onde <math>\mathbf{W^{nk}}</math> é definido como

<math>\mathbf{W^{nk}} = \begin{bmatrix}
e^{-2\pi i 0\cdot0/N} & e^{-2\pi i 0\cdot1/N} & \cdots & e^{-2\pi i 0\cdot k/N}\\
e^{-2\pi i 1\cdot0/N} & e^{-2\pi i 1\cdot1/N} & \cdots & e^{-2\pi i 1\cdot k/N}\\
\vdots & \vdots & \ddots & \vdots\\
e^{-2\pi i n\cdot0/N} & e^{-2\pi i n\cdot1/N} & \cdots & e^{-2\pi i n\cdot k/N}
\end{bmatrix}</math>

O cálculo dessa expressão leva em torno de <math>N^2</math> passos para o resultado. Uma amostra com 3,000 pontos precisa de 9,000,000 operações para a transformada ser obtida, tornando a DFT inviável para aplicações rápidas.

== Transformada Rápida de Fourier ==

É possível calcular a transformada com <math>N \log_{2} N</math> passos. Para isso se dispõe de um algoritmo chamado '''Transformada Rápida de Fourier'''.
Considera-se um conjunto de pontos <math>N = 2^p</math> (com <math>p</math> inteiro, então, da definição da DFT

<math>
F_k =\sum_{n=0}^{N-1} f_n \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot n}
</math>

podemos dividir o somatório em 2:

<math>
F_k =\color{red}\sum_{n=0}^{N/2-1} f_{2n} \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot 2n} \color{black}+ \color{blue}\sum_{n=0}^{N/2-1} f_{2n+1} \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot (2n+1)}
</math>

<math>
\color{black}F_k =\color{red}\sum_{n=0}^{N/2-1} f_{2n} \cdot e^{-i \frac{2 \pi}{N/2}\cdot k\cdot n} \color{black}+ \color{blue}e^{-i\frac{2\pi}{N}k} \sum_{n=0}^{N/2-1} f_{2n+1} \cdot e^{-i \frac{2 \pi}{N/2}\cdot k\cdot n}
</math>

<math>
\color{black}F_k =\color{red}\sum_{n=0}^{N/2-1} f_{2n} \cdot e^{-i \frac{2 \pi}{N/2}\cdot k\cdot n} \color{black}+ \color{blue}~ C(k) ~ \sum_{n=0}^{N/2-1} f_{2n+1} \cdot e^{-i \frac{2 \pi}{N/2}\cdot k\cdot n}
</math>

onde a soma em vermelho é a parte '''par''' e a soma em azul é a parte '''ímpar''' da transformada. As duas somas tem o mesmo expoente, que agora é dividido por <math>N/2</math>.
Desse expoente, é evidente a relação entre o ponto <math>k</math> e o ponto <math>k + N/2</math>

<math>e^{-i \frac{2 \pi}{N/2}\cdot k\cdot n} = e^{-i \frac{2 \pi}{N/2}\cdot (k+N/2)\cdot n} = e^{-i \frac{2 \pi}{N/2}\cdot k\cdot n} \cdot e^{-i \frac{2 \pi}{N/2}\cdot N/2\cdot n} = e^{-i \frac{2 \pi}{N/2}\cdot k\cdot n} \cdot 1</math>

Com essa relação, podemos ver que <math>F_k</math> e <math>F_{k+N/2}</math> tem o mesmo expoente e podem ser calculadas ao mesmo tempo. Mais que isso, a nova forma da transformada pode ser sucessivamente dividida, cada vez produzindo somas com limites menores.

=== Exemplo ===

Suponha que temos a função sinusoidal <math>a(t) = sin(2\pi \cdot 1Hz \cdot t)</math> e fazemos quatro medidas no intervalo de 1 segundo, resultando em

<math>a_0 = 0.00</math>
<math>a_1 = 1.00</math>
<math>a_2 = 0.00</math>
<math>a_3 = -1.00</math>

Com essas 4 medidas, podemos dividir a soma 2 vezes:

<math>A_k = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}</math>

<math>A_k = \sum_{t_1=0}^1 a_{2t_1} \cdot e^{-i \frac{2\pi}{2}\cdot k \cdot t_1} + C_k^1\sum_{t_1=0}^1 a_{2t_1+1} \cdot e^{-i \frac{2\pi}{2}\cdot k \cdot t_1}</math>

<math>A_k = \sum_{t_2=0}^0 a_{4t_2} \cdot e^{-i \frac{2\pi}{1}\cdot k \cdot t_2} + C_k^2\sum_{t_2=0}^0 a_{4t_2+2} \cdot e^{-i \frac{2\pi}{1}\cdot k \cdot t_2} + C_k^1\sum_{t_2=0}^0 a_{4t_2+1} \cdot e^{-i \frac{2\pi}{1}\cdot k \cdot t_2} + C_k^3\sum_{t_2=0}^0 a_{4t_2+3} \cdot e^{-i \frac{2\pi}{1}\cdot k \cdot t_2}</math>

e como temos <math>C_k^j = (e^{-i\frac{2\pi}{N}k})^j</math> podemos calcular

<math>A_0 = 1.00 \cdot C_0^1 - 1.00 \cdot C_0^3 = 0.00 + i0.00</math>

<math>A_1 = 1.00 \cdot C_1^1 - 1.00 \cdot C_1^3 = 0.00 - i2.00</math>

<math>A_2 = 1.00 \cdot C_2^1 - 1.00 \cdot C_2^3 = 0.00 + i0.00</math>

<math>A_3 = 1.00 \cdot C_3^1 - 1.00 \cdot C_3^3 = 0.00 + i2.00</math>

=== FFT para N diferente de uma potência de 2 ===

Mesmo com a FFT sendo um algoritmo extremamente eficiente para <math>N = 2^p</math>, esse dificilmente é o caso que encotramos. Ainda assim, para <math>N</math> altamente composto (<math>N = r_1\cdot r_2 \cdot ... \cdot r_m</math>) o algoritmo ainda resulta em uma boa queda no tempo de cálculo.

Para o caso mais simples <math>N = r_1 \cdot r_2</math> a transformada pode ser escrita como

<math>F(k_1,k_0) = \sum_{n_0=0}^{r_2-1}\left [ \sum_{n_1=0}^{r_1-1} x(n_1,n_0) e^{-i2\pi\cdot k \cdot n_1 \cdot r_2} \right ] e^{-i2\pi \cdot k \cdot n_0}</math>

onde
<math>k = k_1 \cdot r_1 + k_0</math> , <math>k_0 = 0,1,...,r_1-1</math> e <math>k_1 = 0,1,...,r_2-1</math>

<math>n = n_1 \cdot r_2 + n_0</math> , <math>n_0 = 0,1,...,r_2-1</math> e <math>n_1 = 0,1,...,r_1-1</math>

assim a transformada que antes necessitava de N calculos, agora pode ser vista como <math>r_1 + r_2</math> calculos

Grupo4 - FFT

2017-10-23T14:29:00Z

Csdionatan:

A Transformada rápida de Fourier (em inglês '''Fast Fourier Transform''', ou '''FFT''') é um algoritmo que torna o cálculo da Transformada Discreta de Fourier (DFT) viável para a maior parte das aplicações.

== Transformada Discreta de Fourier ==

Em muitas aplicações se tem informação sobre um conjunto de dados, ao invés de uma função contínua. A '''Transformada Discreta de Fourier''' transforma esse conjunto de dados em um conjunto de tamanho igual com informação sobre as frequências da função que satisfaz o conjunto de dados.

Para um conjunto de dados igualmente espaçados, pode-se, ao considerar os dados como um período de uma função periódica, cujo período normalmente é considerado entre <math>[-\pi, \pi]</math> para facilitar o cálculo (e que pode sempre ser transformada em uma função nesse interválo), mostrar que a transformada discreta de Fourier pode ser dada pela equação:

<math>F_k = \sum_{n=0}^{N-1} f_n e^{-i2\pi nk/N}</math>

A sua inversa é, em paralelo ao caso da transformada contínua,

<math>f_n = \frac{1}{N} \sum_{n=0}^{N-1} F_k e^{i2\pi nk/N}</math>

A transformada também pode ser expressa em forma vetorial, como

<math>\vec{F} = \mathbf{W^{nk}} \vec{f}</math> onde <math>\mathbf{W^{nk}}</math> é definido como

<math>\mathbf{W^{nk}} = \begin{bmatrix}
e^{-2\pi i 0\cdot0/N} & e^{-2\pi i 0\cdot1/N} & \cdots & e^{-2\pi i 0\cdot k/N}\\
e^{-2\pi i 1\cdot0/N} & e^{-2\pi i 1\cdot1/N} & \cdots & e^{-2\pi i 1\cdot k/N}\\
\vdots & \vdots & \ddots & \vdots\\
e^{-2\pi i n\cdot0/N} & e^{-2\pi i n\cdot1/N} & \cdots & e^{-2\pi i n\cdot k/N}
\end{bmatrix}</math>

O cálculo dessa expressão leva em torno de <math>N^2</math> passos para o resultado. Uma amostra com 3,000 pontos precisa de 9,000,000 operações para a transformada ser obtida, tornando a DFT inviável para aplicações rápidas.

== Transformada Rápida de Fourier ==

É possível calcular a transformada com <math>N \log_{2} N</math> passos. Para isso se dispõe de um algoritmo chamado '''Transformada Rápida de Fourier'''.
Considera-se um conjunto de pontos <math>N = 2^p</math> (com <math>p</math> inteiro, então, da definição da DFT

<math>
F_k =\sum_{n=0}^{N-1} f_n \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot n}
</math>

podemos dividir o somatório em 2:

<math>
F_k =\color{red}\sum_{n=0}^{N/2-1} f_{2n} \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot 2n} \color{black}+ \color{blue}\sum_{n=0}^{N/2-1} f_{2n+1} \cdot e^{-i \frac{2 \pi}{N}\cdot k\cdot (2n+1)}
</math>

<math>
\color{black}F_k =\color{red}\sum_{n=0}^{N/2-1} f_{2n} \cdot e^{-i \frac{2 \pi}{N/2}\cdot k\cdot n} \color{black}+ \color{blue}e^{-i\frac{2\pi}{N}k} \sum_{n=0}^{N/2-1} f_{2n+1} \cdot e^{-i \frac{2 \pi}{N/2}\cdot k\cdot n}
</math>

<math>
\color{black}F_k =\color{red}\sum_{n=0}^{N/2-1} f_{2n} \cdot e^{-i \frac{2 \pi}{N/2}\cdot k\cdot n} \color{black}+ \color{blue}~ C(k) ~ \sum_{n=0}^{N/2-1} f_{2n+1} \cdot e^{-i \frac{2 \pi}{N/2}\cdot k\cdot n}
</math>

onde a soma em vermelho é a parte '''par''' e a soma em azul é a parte '''ímpar''' da transformada. As duas somas tem o mesmo expoente, que agora é dividido por <math>N/2</math>.
Desse expoente, é evidente a relação entre o ponto <math>k</math> e o ponto <math>k + N/2</math>

<math>e^{-i \frac{2 \pi}{N/2}\cdot k\cdot n} = e^{-i \frac{2 \pi}{N/2}\cdot (k+N/2)\cdot n} = e^{-i \frac{2 \pi}{N/2}\cdot k\cdot n} \cdot e^{-i \frac{2 \pi}{N/2}\cdot N/2\cdot n} = e^{-i \frac{2 \pi}{N/2}\cdot k\cdot n} \cdot 1</math>

Com essa relação, podemos ver que <math>F_k</math> e <math>F_{k+N/2}</math> tem o mesmo expoente e podem ser calculadas ao mesmo tempo. Mais que isso, a nova forma da transformada pode ser sucessivamente dividida, cada vez produzindo somas com limites menores.

=== Exemplo ===

Suponha que temos a função sinusoidal <math>a(t) = sin(2\pi \cdot 1Hz \cdot t)</math> e fazemos quatro medidas no intervalo de 1 segundo, resultando em

<math>a_0 = 0.00</math>
<math>a_1 = 1.00</math>
<math>a_2 = 0.00</math>
<math>a_3 = -1.00</math>

Com essas 4 medidas, podemos dividir a soma 2 vezes:

<math>\tilde{a_k} = \sum_{t=0}^3 a_t \cdot e^{-i \frac{2\pi}{4}\cdot k \cdot t}</math>

<math>\tilde{a_k} = \sum_{t_1=0}^1 a_{2t_1} \cdot e^{-i \frac{2\pi}{2}\cdot k \cdot t_1} + C_k^1\sum_{t_1=0}^1 a_{2t_1+1} \cdot e^{-i \frac{2\pi}{2}\cdot k \cdot t_1}</math>

<math>\tilde{a_k} = \sum_{t_2=0}^0 a_{4t_2} \cdot e^{-i \frac{2\pi}{1}\cdot k \cdot t_2} + C_k^2\sum_{t_2=0}^0 a_{4t_2+2} \cdot e^{-i \frac{2\pi}{1}\cdot k \cdot t_2} + C_k^1\sum_{t_2=0}^0 a_{4t_2+1} \cdot e^{-i \frac{2\pi}{1}\cdot k \cdot t_2} + C_k^3\sum_{t_2=0}^0 a_{4t_2+3} \cdot e^{-i \frac{2\pi}{1}\cdot k \cdot t_2}</math>

e como temos <math>C_k^j = (e^{-i\frac{2\pi}{N}k})^j</math> podemos calcular

<math>\tilde{a_0} = 1.00 \cdot C_0^1 - 1.00 \cdot C_0^3 = 0.00 + i0.00</math>

<math>\tilde{a_1} = 1.00 \cdot C_1^1 - 1.00 \cdot C_1^3 = 0.00 - i2.00</math>

<math>\tilde{a_2} = 1.00 \cdot C_2^1 - 1.00 \cdot C_2^3 = 0.00 + i0.00</math>

<math>\tilde{a_3} = 1.00 \cdot C_3^1 - 1.00 \cdot C_3^3 = 0.00 + i2.00</math>

=== FFT para <math>N \neq 2^p</math> ====

Mesmo com a FFT sendo um algoritmo extremamente eficiente para <math>N = 2^p</math>, esse dificilmente é o caso que encotramos. Ainda assim, para <math>N</math> altamente composto (<math>N = r_1\cdot r_2 \cdot ... \cdot r_m</math>) o algoritmo ainda resulta em uma boa queda no tempo de cálculo.