Présentation de la transformée de Fourier discrète

Question

J'ai une petite question concernant les transformées de Fourier discrètes. Si je comprends bien, alors ce que nous faisons est de convertir un polynôme en sa représentation de valeur de point, avec n points pour un polynôme qui monte à la puissance de n-1. Mais pourquoi devons-nous l'évaluer aux racines nième de l'unité? Est-ce que d'autres n points n'identifieraient pas de façon unique ce polynôme ET seraient beaucoup plus simples?

Answer 1

Aucun autre point n n'identifierait-il de manière unique ce polynôme ET serait beaucoup plus simple?

Non aux deux. 1) Il n'y a aucune garantie que n points arbitraires fonctionneraient et 2) ce ne serait pas plus simple. Retournez la question: pourquoi vous opposez-vous aux racines de l'unité?

Answer 2

Les principaux raisons applicatives

• vagues deviennent monômes.
• Le produit sur l'espace-temps est la convolution sur l'espace des phases et vice-versa (vous pouvez donc multiplier deux polynômes de degré n dans O (n log n)).
• Dérivée sur l'espace de temps est produit par x sur l'espace de phase et vice versa.

Vous n'en auriez aucun avec des points aléatoires - intuitivement parlant, parce qu'ils ne forment pas un groupe. Il y a beaucoup plus de raisons théoriques (et aussi quelques raisons plus applicatives)

Answer 3

Non, pas vraiment. Cela n'a rien à voir avec les polynômes. Il s'agit de décomposer un vecteur (la séquence initiale de nombres) en une base différente. C'est juste que cette base a une série de propriétés très utiles:

(1) Il est orthogonal - les vecteurs ne se mélangent pas, et déterminer la transformation à la base d'origine est extrêmement simple.

(2) Les vecteurs de base de Fourier sont des vecteurs propres de l'opération de décalage (ou circulaire, pour le cas discret) - une fonction de base de Fourier , après avoir décalé les indices vectoriels, est toujours la même fonction). C'est ce qui rend les circonvolutions et la solution d'une grande classe d'équations différentielles très simples dans l'espace de Fourier.

(3) Et enfin, les entrées sont des racines de l'unité - ceci donne le F FT, l'un des algorithmes les plus élégants jamais découverts, réduisant les opérations N^2 nécessaires pour un changement de base à N log N.

Answer 4

Voici deux explications «intuitives» de la transformée de Fourier discrète. Ils ne sautent pas dans les équations directement, mais à pied vous à travers un souhait, quelqu'un-dit-me-ce-avant ainsi

1. http://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/

2. http://www.altdevblogaday.com/2011/05/17/understanding-the-fourier-transform/