Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... École ingénieur AlgèbreTopics traitant de algèbre [tout]Lister tous les topics de mathématiques
Niveau école ingénieur
Partager :

Transformée de Fourier discrète

Posté par
matheux14 09-09-23 à 22:14

Bonjour,

Merci d'avance.

On fixe un entier N \ge 1. Pour un vecteur de nombres complexes x = (x_0, \dots, x_{N - 1}) \in \C^N, on pose pour tout 0 \le k \le N - 1

y_k = \dfrac{1}{\sqrt{N}} \sum\limits^{N - 1}_{n = 0} x_n e^{-i \frac{2\pi}{N} nk} (où i^2 = -1)

et on définit \mathcal D(x) = (y_0, \dots, y_{N - 1}) \in \C^N la transformée de Fourier discrète de x. Pour simplifier les notations on posera \zeta = e^{-i \frac{2\pi}{N}}.

Si A \in M_n(\C) est une matrice à coefficients complexes, on note A^* = \overline{A}^{T} la transposée de la conjuguée de A. On rappelle que si \alpha = (\alpha_i)^N_{i = 1} est une suite de N nombres complexes, la matrice de Vandermonde V(\alpha) est définie par V(\alpha) = (\alpha^{j - 1}_i)_{1 \le i, j \le n} et

\det(V(\alpha)) = \prod\limits_{1 \le i \le j \le N} (\alpha_j - \alpha_i).

1) Montrer que \mathcal D est une transformation linéaire de \C^N dans lui même, et exprimer sa matrice dans la base canonique, qui sera notée U.

2) Un entier q \ge 0 étant fixé, calculer \sum\limits^{N - 1}_{n = 0} \zeta^{n q} en fonction de q.

3) Calculer U * U. En déduire que \mathcal{D} est inversible et donner l'expression de D^{-1}
dans la base canonique, qui sera notée U.

3) Calculer \mathcal D^2 puis  \mathcal D^4. En déduire que U est diagonalisable et que ses valeurs propres appartiennent à l'ensemble \{1, -1, i, -i\}.

Réponses :

1) Soit x, y \in \C^N et \alpha un scalaire.

Avec x et y d'échantillons respectifs (x_0, \dots, x_{N - 1}) et (y_0, \dots, y_{N - 1}) bien sur.

Il suffit de montrer que \mathcal{D}(x + \alpha y) = D(x) + \alpha \mathcal{D}(y).

Conformement à l'énoncé, \mathcal{D}(x) est donné par y_k = \dfrac{1}{\sqrt{N}} \sum\limits^{N - 1}_{n = 0} x_n \zeta^{nk} et \mathcal{D}(y) par z_k = \dfrac{1}{\sqrt{N}} \sum\limits^{N - 1}_{n = 0} y_n \zeta^{nk}

On considère w_k les composantes de \mathcal{D}(x + \alpha y) :

\begin{aligned} \\ w_k &= \dfrac{1}{\sqrt{N}}  \sum\limits^{N - 1}_{n = 0} (x_n + \alpha y_n) \zeta^{nk} \\\ \\ &= \dfrac{1}{\sqrt{N}} \left( \sum\limits^{N - 1}_{n = 0} x_n \zeta^{nk} + \alpha  \sum\limits^{N - 1}_{n = 0} y_n \zeta^{nk}\right) \\\ \\ &= \dfrac{1}{\sqrt{N}} \left( \sum\limits^{N - 1}_{n = 0} x_n \zeta^{nk}\right) + \dfrac{\alpha}{\sqrt{N}} \left( \sum\limits^{N - 1}_{n = 0}  y_n \zeta^{nk}\right)\\\ \\ w_k &= y_k + \alpha z_k \\ \end{aligned}

On a donc montré que \boxed{\mathcal{D}(x + \alpha y) = \mathcal D(x) + \mathcal D(\alpha y) = \mathcal D(x) + \alpha \mathcal D(y)}.

\mathcal D est donc une transformation linéaire de \C^N dans \C^N.

Expression de sa matrice dans la base canonique, qui sera notée U.


Les vecteurs de base canonique de \C^N sont représentés par U = \{e_0, e_1, \dots, e_{N - 1}\}, où e_i est le vecteur dont toutes les composantes sont nulles sauf la i-ème composante qui vaut 1.

On calculer \mathcal{D}(e_k) pour former les colonnes de la matrice de \mathcal{D} dans la base canonique.

\mathcal{D}(e_k) = \left(\dfrac{1}{\sqrt{N}} \sum\limits^{N - 1}_{n = 0} e_n \zeta^{nk}\right)^{N - 1}_{k = 0}

\mathcal{D}(e_k) = \left(\dfrac{1}{\sqrt{N}} \zeta^{0k}, \dfrac{1}{\sqrt{N}} \zeta^{1k}, \dots, \dfrac{1}{\sqrt{N}} \zeta^{(N - 1)k}\right)

\mathcal{D}(e_k) = \left(\dfrac{1}{\sqrt{N}}, \dfrac{1}{\sqrt{N}} \zeta^{k}, \dots, \dfrac{1}{\sqrt{N}} \zeta^{(N - 1)k}\right)

On a donc \mathcal{D}(e_k) est un vecteur colonne dont la première composante est \dfrac{1}{\sqrt{N}} et les composantes restantes sont obtenues en multipliant \dfrac{1}{\sqrt{N}} par les puissances de \zeta

\boxed{[\mathcal{D}]_U = (\mathcal{D}(e_0) \mathcal{D}(e_1) \dots \mathcal{D}(e_{N - 1})) = \dfrac{1}{\sqrt{N}} \begin{pmatrix} \\ 1 & 1 & 1 & \dots & 1 \\\ \\ 1 & \zeta & \zeta^2 & \dots & \zeta^{N - 1} \\\ \\ \vdots & \vdots & \vdots & \ddots & \vdots \\\ \\ 1 & \zeta^{N - 1} & \zeta^{2(N - 1)} & \dots & \zeta^{(N - 1)^2} \\ \end{pmatrix}}

Est-ce juste ?

Est-ce qu'on peut faire plus court pour cette première question ?

Posté par
GBZMre : Transformée de Fourier discrète 10-09-23 à 10:17

Bonjour,
Oui c'est juste et on attend certainement beaucoup plus court pour cette première question qui est une mise en route.
Par exemple
Les y_k sont des formes linéaires en les x_i, donc D est un endomorphisme linéaire de {\mathbb C}^n.

Par ailleurs, vu le préambule, on attend certainement que tu décrives la matrice de D en utilisant une matrice de Vandermonde.

Tu as dans on énoncé deux matrices différentes notées U. Rétablis un nénoncé correct.

Posté par
matheux14re : Transformée de Fourier discrète 10-09-23 à 20:14

Citation :
On fixe un entier N \ge 1. Pour un vecteur de nombres complexes x = (x_0, \dots, x_{N - 1}) \in \C^N, on pose pour tout 0 \le k \le N - 1

y_k = \dfrac{1}{\sqrt{N}} \sum\limits^{N - 1}_{n = 0} x_n e^{-i \frac{2\pi}{N} nk} (où i^2 = -1)

et on définit \mathcal D(x) = (y_0, \dots, y_{N - 1}) \in \C^N la transformée de Fourier discrète de x. Pour simplifier les notations on posera \zeta = e^{-i \frac{2\pi}{N}}.

Si A \in M_n(\C) est une matrice à coefficients complexes, on note A^* = \overline{A}^{T} la transposée de la conjuguée de A. On rappelle que si \alpha = (\alpha_i)^N_{i = 1} est une suite de N nombres complexes, la matrice de Vandermonde V(\alpha) est définie par V(\alpha) = (\alpha^{j - 1}_i)_{1 \le i, j \le n} et

\det(V(\alpha)) = \prod\limits_{1 \le i \le j \le N} (\alpha_j - \alpha_i).

1) Montrer que \mathcal D est une transformation linéaire de \C^N dans lui même, et exprimer sa matrice dans la base canonique, qui sera notée \mathcal{U}.

2) Un entier q \ge 0 étant fixé, calculer \sum\limits^{N - 1}_{n = 0} \zeta^{n q} en fonction de q.

3) Calculer U * U. En déduire que \mathcal{D} est inversible et donner l'expression de D^{-1}
dans la base canonique, qui sera notée \mathcal{U}'.

4) Calculer \mathcal D^2 puis  \mathcal D^4. En déduire que U est diagonalisable et que ses valeurs propres appartiennent à l'ensemble \{1, -1, i, -i\}.


Réponses :

1) \red \checkmark Plus simplement :

Citation :
Les y_k sont des formes linéaires en les x_i, donc D est un endomorphisme linéaire de {\mathbb C}^n.


Expression de sa matrice dans la base canonique, qui sera notée \mathcal U.

\mathcal{D}_{\mathcal{U}} = \dfrac{1}{\sqrt{N}} \begin{pmatrix} \\ 1 & 1 & 1 & \dots & 1 \\\ \\ 1 & \zeta & \zeta^2 & \dots & \zeta^{N - 1} \\\ \\ \vdots & \vdots & \vdots & \ddots & \vdots \\\ \\ 1 & \zeta^{N - 1} & \zeta^{2(N - 1)} & \dots & \zeta^{(N - 1)^2} \\ \end{pmatrix}

Expression  de \mathcal{D}_{\mathcal{U}} en utilisant la matrice de Vandermonde V(\alpha) :

V(\alpha) = (\alpha^{j - 1}_i)_{1 \le i, j \le N}

Plus explicitement :

V = \begin{pmatrix} \\ 1 & \alpha_1 & \alpha^2_1 & \dots & \alpha^{n - 1}_1 \\\ \\ 1 & \alpha_2 & \alpha^2_2 & \dots & \alpha^{n - 1}_2 \\\ \\ \vdots & \vdots & \vdots & \ddots & \vdots \\\ \\ 1 & \alpha_m & \alpha^2_m & \dots & \alpha^{n - 1}_m \\ \end{pmatrix}

Finalement :

\boxed{\mathcal{D}_{\mathcal{U}} = \dfrac{1}{\sqrt{N}} \mathcal{V}},

\mathcal{V} matrice de Vandermonde avec \mathcal{V}_{i, j} = \zeta^{j - 1}_{i}


2) Soit \mathcal{S} = \sum\limits^{N - 1}_{n = 0} \zeta^{n q}

On pose k = \zeta^q

\mathcal{S} = \sum\limits^{N - 1}_{n = 0} k^n =  \dfrac{1 - k^N}{1 - k}

\boxed{\mathcal{S} = \dfrac{1 - k^N}{1 - k}}

3) Disons que U \dots U, où U est la matrice de la transformation \mathcal{D} dans la base canonique \mathcal{U}' :

U \cdot U =\dfrac{1}{N} \mathcal{V}}^2 = \dfrac{1}{N} \begin{pmatrix} \\ 1 & 1 & 1 & \dots & 1 \\\ \\ 1 & \zeta & \zeta^2 & \dots & \zeta^{N - 1} \\\ \\ \vdots & \vdots & \vdots & \ddots & \vdots \\\ \\ 1 & \zeta^{N - 1} & \zeta^{2(N - 1)} & \dots & \zeta^{(N - 1)^2} \\ \end{pmatrix}\begin{pmatrix} \\ 1 & 1 & 1 & \dots & 1 \\\ \\ 1 & \zeta & \zeta^2 & \dots & \zeta^{N - 1} \\\ \\ \vdots & \vdots & \vdots & \ddots & \vdots \\\ \\ 1 & \zeta^{N - 1} & \zeta^{2(N - 1)} & \dots & \zeta^{(N - 1)^2} \\ \end{pmatrix}

En appliquant les règles de calculs du produit de deux matrices on a :

On généralise pour N, q \ge 1 avec (N, q) :

(U \cdot U)_{N, q} = \sum\limits^{N - 1}_{i = 0} \zeta^{N q} = \dfrac{1 - \zeta^{Nq}}{1 - \zeta^q}

\boxed{U \cdot U = \dfrac{1}{N} \begin{pmatrix} \\ (U \cdot U)_{1, 1} & (U \cdot U)_{1, 2} & (U \cdot U)_{1, 3} & \dots & (U \cdot U)_{1, q} \\\ \\ (U \cdot U)_{2, 1} & (U \cdot U)_{2, 2} & (U \cdot U)_{2, 3} & \dots & (U \cdot U)_{2, q} \\\ \\ \vdots & \vdots & \vdots & \ddots & \vdots \\\ \\ (U \cdot U)_{N, 1} & (U \cdot U)_{N, 2} & (U \cdot U)_{N, 3} & \dots & (U \cdot U)_{N, N} \\ \end{pmatrix}}

\mathcal{D} est inversible ?

On a

\det(U \cdot U) = \det(U) \cdot \det(U) = \dfrac{1}{N} \prod\limits_{1 \le i \le j \le N} (\zeta_j - \zeta_i) \times \prod\limits_{1 \le i \le j \le N} (\zeta_j - \zeta_i)

\det(U \cdot U) = \prod\limits_{1 \le i \le j \le N} (\zeta_j - \zeta_i)^2.

Si N \ge 2, alors \zeta_j - \zeta_i \neq 0 pour tout 1 \le i \le j \le N car les racines de l'unité complexes sont distinctes. Par conséquent,

det(U \cdot U) = \prod\limits_{1 \le i \le j \le N} (\zeta_j - \zeta_i)^2 \neq 0

Conclusion : \mathcal{D} est inversible.

Difficile de calculer l'inverse de U et donc donner l'expression de D^{-1}
dans la base canonique.

Posté par
GBZMre : Transformée de Fourier discrète 10-09-23 à 20:51

Je t'ai demandé de rétablir ton énoncé et j'ai expliqué pourquoi. J'attends.

Posté par
matheux14re : Transformée de Fourier discrète 10-09-23 à 22:08

Je ne vois pas pourquoi le U inversible de la question 3) serait différente du U de la 4).

Ou peut être au niveau de la question 3) les deux matrices sont différentes, mais là encore je ne vois pas vraiment la raison.

Posté par
matheux14re : Transformée de Fourier discrète 10-09-23 à 22:10

La seule chose que j'ai pu faire c'est de modifier alors les noms des deux bases canoniques.

Posté par
GBZMre : Transformée de Fourier discrète 10-09-23 à 22:59

J'attends toujours de savoir qui est U.

Posté par
matheux14re : Transformée de Fourier discrète 10-09-23 à 23:43

L'énoncé n'en dit pas plus, peut-être auriez vous quelque chose à proposer ?

Je peux vous envoyer le pdf ?

Posté par
GBZMre : Transformée de Fourier discrète 11-09-23 à 08:51

Tu as visiblement fait des erreurs en recopiant l'énoncé, ce qui fait qu'il est devenu incohérent.
Par exemple ton U*U de la question 3 qui est en fait U^* U (je parie). Au fait quel sens cela aurait-il si U était la base canonique, comme tu sembles le penser ?
Et dans tes réponses tu introduis d'autres notations, comme ton \mathcal D_U qui embrouillent encore plus les choses. Le choix entre police normale et police calligraphique a aussi l'air de se faire au petit bonheur.

Dans la question 1) la matrice de l'endomorphisme \mathcal D dans la base canonique est \dfrac1{\sqrt N}V(1,\zeta,\zeta^2,\ldots,\zeta^{N-1}).
Dans la question 2, tu oublies de considérer le cas où \zeta^q=1, et le fait de poser k=\zeta^q te fait passer complètement à côté du résultat attendu : tu oublies que \zeta est une racine primitive N-ème de l'unité.

Posté par
GBZMre : Transformée de Fourier discrète 13-09-23 à 14:21

Encore un sujet qui part à vau-l'eau.
Reprenons.
On note {\mathcal D} : {\mathbb C}^n\to {\mathbb c}^n la transformée de Fourier discrète définie dans le premier message.
1) C'est une application linéaire, dont la matrice dans la base canonique est U=\dfrac1{\sqrt N}V(1,\zeta,\zeta^2,\ldots,\zeta^{N-1}}.
2) La somme \sum_{n=0}^{N-1} \zeta^{nq} vaut N si N divise q, 0 sinon.
3) En utilisant le résultat de 2), on obtient que (U^* )U=I_n., ce qui montre que U est inversible d'inverse U^*=\dfrac1{\sqrt N}V(1,\zeta^{-1},\zeta^{-2},\ldots,\zeta^{1-N}).
4) Toujours en utilisant 2), on calcule U^2 ; puis on obtient facilement U^4=I_n. Donc X^4-1 est polynôme annulateur de U, ce qui montre que ses valeurs propres appartiennent à \{1,i,-1,-i\}.

Matheux14, s'il revient sur ce fil, pourra démontrer les affirmations ci-dessus.

Posté par
matheux14re : Transformée de Fourier discrète 13-09-23 à 23:06

Bonsoir GBZM

1) D'après l'énoncé, pour un vecteur de nombres complexes x = (x_0, \dots, x_{N - 1}) \in \C^N, pour tout 0 \le k \le N - 1 on a y_k = \dfrac{1}{\sqrt{N}} \sum\limits^{N - 1}_{n = 0} x_n e^{-i \frac{2\pi}{N} nk} et \mathcal D(x) = (y_0, \dots, y_{N - 1}) \in \C^N

Donc les y_k sont des formes linéaires en les x_i, donc D est un endomorphisme linéaire de {\mathbb C}^n.

Les vecteurs de base canonique de \C^N sont représentés par U = \{e_0, e_1, \dots, e_{N - 1}\}, où e_i est le vecteur dont toutes les composantes sont nulles sauf la i-ème composante qui vaut 1.

On calculer \mathcal{D}(e_k) pour former les colonnes de la matrice de \mathcal{D} dans la base canonique.

\mathcal{D}(e_k) = \left(\dfrac{1}{\sqrt{N}} \sum\limits^{N - 1}_{n = 0} e_n \zeta^{nk}\right)^{N - 1}_{k = 0}

\mathcal{D}(e_k) = \left(\dfrac{1}{\sqrt{N}} \zeta^{0k}, \dfrac{1}{\sqrt{N}} \zeta^{1k}, \dots, \dfrac{1}{\sqrt{N}} \zeta^{(N - 1)k}\right)

\mathcal{D}(e_k) = \left(\dfrac{1}{\sqrt{N}}, \dfrac{1}{\sqrt{N}} \zeta^{k}, \dots, \dfrac{1}{\sqrt{N}} \zeta^{(N - 1)k}\right)

On a donc \mathcal{D}(e_k) est un vecteur colonne dont la première composante est \dfrac{1}{\sqrt{N}} et les composantes restantes sont obtenues en multipliant \dfrac{1}{\sqrt{N}} par les puissances de \zeta

U = (\mathcal{D}(e_0) \mathcal{D}(e_1) \dots \mathcal{D}(e_{N - 1})) = \dfrac{1}{\sqrt{N}} \begin{pmatrix} \\ 1 & 1 & 1 & \dots & 1 \\\ \\ 1 & \zeta & \zeta^2 & \dots & \zeta^{N - 1} \\\ \\ \vdots & \vdots & \vdots & \ddots & \vdots \\\ \\ 1 & \zeta^{N - 1} & \zeta^{2(N - 1)} & \dots & \zeta^{(N - 1)^2} \\ \end{pmatrix}

On déduit conformement à l'énoncé la matrice dans la base canonique en utilisant une matrice de Vandermonde et on obtient :

\boxed{U =\dfrac1{\sqrt N}V\left(1,\zeta,\zeta^2,\ldots,\zeta^{N-1}\right)}}

2) \bullet Cas où N \mid q

On a N \mid q \Longrightarrow q = Nk, \forall k \in \Z

\sum\limits^{N - 1}_{n = 0} \zeta^{nq} = \sum\limits^{N - 1}_{n = 0} \zeta^{nkN} = \sum\limits^{N - 1}_{n = 0} (\zeta^N)^{kn} = \sum\limits^{N - 1}_{n = 0} \left(\left(e^{-i\frac{2\pi}{N}}\right)^N\right)^{nk} = \sum\limits^{N - 1}_{n = 0} 1 = N

\bullet Cas où N \nmid q

On a N \nmid q \Longrightarrow q = Nk + r, \forall k, r \in \Z^*

\sum\limits^{N - 1}_{n = 0} \zeta^{nq} = \sum\limits^{N - 1}_{n = 0} \zeta^{n(Nk + r)} = \sum\limits^{N - 1}_{n = 0} \zeta^{nNk} \zeta^{nr} = \sum\limits^{N - 1}_{n = 0} \zeta^{nr} = 0 car r \neq 0 \Longrightarrow les termes de \zeta^{nr} sont les racines N-ème de l'unité distinctes de 1 et leur somme vaut 0.

3) (U^* \cdot U)_{ij} = \sum\limits^{N - 1}_{k = 0} (U^*)_{ik} \cdot U_{kj}

Où U^* est la matrice conjuguée transposée de U

On a alors

\begin{aligned} \\ (U^* \cdot U)_{ij} &= \sum\limits^{N - 1}_{k = 0} (U^*)_{ik} \cdot U_{kj} \\\ \\ &= \sum\limits^{N - 1}_{k = 0} \left(\dfrac{1}{\sqrt{N}}V\left(1, \zeta^{-1}, \zeta^{-2}, \dots, \zeta^{1 - N}\right)\right)_{ik} \cdot \left(\dfrac{1}{\sqrt{N}}V\left(1, \zeta^{1}, \zeta^{2}, \dots, \zeta^{N - 1}\right)\right)_{kj} \\\ \\ &= \dfrac{1}{N} \sum\limits^{N - 1}_{k = 0}  V\left(1, \zeta^{-1}, \zeta^{-2}, \dots, \zeta^{1 - N}\right)_{ik}  \cdot V\left(1, \zeta^{1}, \zeta^{2}, \dots, \zeta^{N - 1}\right)_{kj} \\ \end{aligned}

Comme les matrices de Vandermonde sont orthogonales dans  notre cas ici (puisqu'on a une séquence de nombres \alpha_i qui est une séquence de racines N-èmes de l'unité (N \in \N)  d'après leurs propriétés d'orthogonalité spécifiques), le produit des deux matrices est une matrice diagonale :

(U^* \cdot U)_{ij} = \dfrac{1}{N} \sum\limits^{N - 1}_{k = 0} \delta_{ik} \delta_{kj} = \dfrac{1}{N} \delta_{ij}

Où \delta_{ij} est le delta de Kronecker.

Rappel : \delta_{ij} = \begin{cases} 1 \text{   si } i = j \\\ 0 \text{  si } i \neq j \end{cases}.

D'où U^* \cdot U = I_n donc U est inversible d'inverse U^*=\dfrac1{\sqrt N}V(1,\zeta^{-1},\zeta^{-2},\ldots,\zeta^{1-N}).

4) D'après les questions précédentes, U^2 = U^* \cdot U = I_n

\Longrightarrow U^4 = U^2 \cdot U^2 = I_n.

Donc X^4-1 est polynôme annulateur de U, ce qui montre que ses valeurs propres appartiennent à \{1,i,-1,-i\}.

Posté par
GBZMre : Transformée de Fourier discrète 14-09-23 à 09:02

La réponse à la question 1 est beaucoup trop longue. On a déjà remarqué que les y_k sont des formes linéaires en les x_n. Les coefficients de ces formes linéaires sont les lignes de la matrice de \mathcal D dans la base canonique, et puis c'est tout !
Question 2 : il faut reprendre le cas où N ne divise pas q en utilisant la somme des termes d'une progression géométrique de raison différente de 1. Il y a quelque chose de faux dans ce que tu écris : "les termes de \zeta^{nr} sont les racines N-ème de l'unité distinctes de 1". Prends par exemple N=4 et q=r=2.
Ça ne va pas pour la 3) : tu utilises comme argument "les matrices de Vandermonde sont orthogonales dans notre cas", juste ce qu'on te demande de montrer !  Franchement, es-tu convaincu par le simili-calcul que tu fais après ? Fais le calcul sérieusement, sans te noyer dans les notations, en utilisant la question 2. J'ai bien insisté sur l'utilisation de 2) pour les questions 3) et 4), mais tu n'en tiens pas compte..
Pour la question 4, le départ ne va pas du tout : ton égalité (U^*)U=U^2 montre que tu penses que U^*=U, ce qui est évidemment faux. Ici aussi il faut utiliser 2) et faire le calcul ! Tu aurais pu te douter que si on avait U^2=I_N, on ne se serait pas embêté à chercher un autre polynôme annulateur que X^2-1 !

Posté par
matheux14re : Transformée de Fourier discrète 15-09-23 à 22:18

Bonsoir GBZM

Effectivement, on pouvait faire mieux.

\bullet Cas où N \nmid q

N \nmid q \Longrightarrow q = Nk + r

\sum\limits^{N - 1}_{n = 0} \zeta^{nq} = \sum\limits^{N - 1}_{n = 0} \zeta^{nr}

\zeta^r \sum\limits^{N - 1}_{n = 0} \zeta^{nr} - \sum\limits^{N - 1}_{n = 0} \zeta^{nr} = \left(\zeta^{r} + \zeta^{2r} + \dots + \zeta^{Nr}\right) - \left(1 + \zeta^{r} + \zeta^{2r} + \dots + \zeta^{(N - 1)r}\right)

(\zeta^r - 1)\sum\limits^{N - 1}_{n = 0} \zeta^{nr} = \zeta^{Nr} - 1

\sum\limits^{N - 1}_{n = 0} \zeta^{nr} =  \dfrac{\zeta^{Nr} - 1}{\zeta^r - 1}

\zeta^{Nr} = 1 \Longrightarrow \sum\limits^{N - 1}_{n = 0} \zeta^{nr} = 0

On a donc montré que \sum\limits^{N - 1}_{n = 0} \zeta^{nq} = \begin{cases} 1 \text{ si } N \mid q \\\\ 0 \text{ sinon} \end{cases}

3) On a U = \dfrac{1}{\sqrt{N}} V\left(1, \zeta, \zeta^2, \dots, \zeta^{N - 1}\right) et U^* = \dfrac{1}{\sqrt{N}} V\left(1, \zeta^{-1}, \zeta^{-2}, \dots, \zeta^{1 - N}\right) avec \zeta = e^{-i\frac{2\pi}{N}}

(U^*) \cdot U = \dfrac{1}{N} V\left(1, \zeta^{-1}, \zeta^{-2}, \dots, \zeta^{1 - N}\right) \cdot V\left(1, \zeta, \zeta^2, \dots, \zeta^{N - 1}\right)

On a montré que \sum\limits^{N - 1}_{n = 0} \zeta^{nq} = \begin{cases} N \text{ si } N \mid q \\\\ 0 \text{ sinon} \end{cases}

C'est-à-dire que la multiplication des deux matrices de Vandermonde donnera une matrice diagonale avec N en diagonale. Car les termes de la matrice V\left(1, \zeta^{-1}, \zeta^{-2}, \dots, \zeta^{1 - N}\right) \cdot V\left(1, \zeta, \zeta^2, \dots, \zeta^{N - 1}\right) sont de la forme \sum\limits^{N - 1}_{n = 0} \zeta^{nq}. En d'autres termes :

(U^*) \cdot U = \dfrac{1}{N} \begin{pmatrix} \\ N & 0 & 0 & \dots & 0 \\\ \\ 0 & N & 0 & \dots & 0 \\\ \\ \vdots & \vdots & \vdots & \ddots & \vdots \\\ \\ 0 & 0 & 0 & \dots & N \\ \end{pmatrix}

Donc, (U^*)U = I_n.

D'où U est inversible d'inverse U^*=\dfrac1{\sqrt N}V(1,\zeta^{-1},\zeta^{-2},\ldots,\zeta^{1-N}).


4) On a :

U^2 = U \cdot U = \dfrac{1}{N} V\left(1, \zeta, \zeta^2, \dots, \zeta^{N - 1}\right) \cdot V\left(1, \zeta, \zeta^2, \dots, \zeta^{N - 1}\right)


Toujours en utilisant \sum\limits^{N - 1}_{n = 0} \zeta^{nq} = \begin{cases} N \text{ si } N \mid q \\\\ 0 \text{ sinon} \end{cases}, on a également :

U^2 = U \cdot U = \dfrac{1}{N} \begin{pmatrix} \\ N & 0 & 0 & \dots & 0 \\\ \\ 0 & N & 0 & \dots & 0 \\\ \\ \vdots & \vdots & \vdots & \ddots & \vdots \\\ \\ 0 & 0 & 0 & \dots & N \\ \end{pmatrix} = I_n

U^2 = I_n \Longrightarrow U^4 = U^2 \cdot U^2 = I_n

Donc U^4 = I_n \Longrightarrow X^4-1 est polynôme annulateur de U et ses valeurs propres appartiennent à \{1,i,-1,-i\}.

Posté par
GBZMre : Transformée de Fourier discrète 15-09-23 à 22:37

Le 4) est faux, et ça laisse un gros doute sur ton argument pour le 3.
Fais l'effort de calculer explicitement  le coefficient de ligne i et de colonne j du produit (U^*)U et de U^2.

Posté par
matheux14re : Transformée de Fourier discrète 16-09-23 à 13:19

Bonjour GBZM

U = \begin{pmatrix}1 & 1 & 1 & \ldots & 1 \\ \\ 1 & \zeta & \zeta^2 & \ldots & \zeta^{N-1} \\ \\ 1 & \zeta^2 & \zeta^4 & \ldots & \zeta^{2(N-1)} \\ \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \\ 1 & \zeta^{N-1} & \zeta^{2(N-1)} & \ldots & \zeta^{(N-1)^2} \\ \end{pmatrix}
  

Coefficient ij de (U^*)U

(U^*)U_{ij} = \dfrac{1}{N}\sum_{k=0}^{N-1} (\zeta^{-ki})(\zeta^{kj}) = \dfrac{1}{N}\sum_{k=0}^{N-1} \zeta^{k(j-i)} = \begin{cases} 1 \text{ si }  N \mid j-i, \\\\ 0 \text{ sinon.} \end{cases}

Donc on aura que des 1 sur la diagonale et que des 0 en dehors de la diagonale. Car (i = j) \Longrightarrow N \mid (j - i)

Coefficient ij de U^2 :

U^2_{ij} = \dfrac{1}{N}\sum_{k=0}^{N-1} \zeta^{kj}\zeta^{ki} = \dfrac{1}{N}\sum_{k=0}^{N-1} \zeta^{k(i + j)} = \begin{cases} 1 \text{ si }  N \mid i + j, \\\\ 0 \text{ sinon.} \end{cases}

U^2 est la matrice identité si et seulement si N est pair et N \le i + j.

Dans ce cas, on a U^4 = I_n et X^4 - 1  est polynôme annulateur de U et ses valeurs propres appartiennent à \{1,i,-1,-i\}.

Posté par
GBZMre : Transformée de Fourier discrète 16-09-23 à 13:39

Ok pour le 3.  Pour le 4, tu fais correctement le calcul (à condition de comprendre que les lignes et colonnes sont numérotées de 0 à N-1 et pas de 1 à N), mais par contre les conclusions que tu en tires sont aberrantes. Traites un peit exemple jusqu'au bout, par exemple pour N=3, pour avoir une idée plus exacte de ce qui se passe.

Posté par
matheux14re : Transformée de Fourier discrète 16-09-23 à 16:04

U_3 = \begin{pmatrix}1 & 1 & 1 \\ \\ 1 & \zeta & \zeta^2 \\ \\ 1 & \zeta^2 & \zeta^4 \\ \end{pmatrix} = \dfrac{1}{\sqrt{3}}\begin{pmatrix} \\ 1 & 1 & 1 \\ \\ 1 & \frac{-1 + i\sqrt{3}}{2} & \frac{-1 - i\sqrt{3}}{2} \\ \\ 1 & \frac{-1 - i\sqrt{3}}{2} & \frac{-1 + i\sqrt{3}}{2} \\ \end{pmatrix}


U^2_3 = \dfrac{1}{3}\begin{pmatrix} \\ 1 & 1 & 1 \\ \\ 1 & \frac{-1 + i\sqrt{3}}{2} & \frac{-1 - i\sqrt{3}}{2} \\ \\ 1 & \frac{-1 - i\sqrt{3}}{2} & \frac{-1 + i\sqrt{3}}{2} \\ \end{pmatrix} \cdot \begin{pmatrix} \\ 1 & 1 & 1 \\ \\ 1 & \frac{-1 + i\sqrt{3}}{2} & \frac{-1 - i\sqrt{3}}{2} \\ \\ 1 & \frac{-1 - i\sqrt{3}}{2} & \frac{-1 + i\sqrt{3}}{2} \\ \end{pmatrix}

U^2_3 = \begin{pmatrix} \\ 1 & 0 & 0 \\ \\ 0 & 0 & 1 \\ \\ 0 & 1 & 0 \\ \end{pmatrix}

U^2 est une matrice de permutation.

Et on remarque U^2_{ij} = \dfrac{1}{N}\sum_{k=0}^{N-1} \zeta^{k(i + j)} = \begin{cases} 1 \text{ si }  N \mid i + j, \\\\ 0 \text{ sinon.} \end{cases} n'est pas valable pour N \ge 3, puisque le premier élément (U^2_{11}) de U^2 est toujours 1.

Du coup je me demande comment la réponse à la question 2) peut aider ici.

Posté par
GBZMre : Transformée de Fourier discrète 16-09-23 à 16:13

Je vais commencer à m'échauffer. Si tu prenais au moins autant de soin à la cohérence au contenu mathématique de ce que tu écris qu'à la façon de l'écrire en LaTeX, tu aurais fait un grand pas !
J'ai bien précisé dans mon dernier message

Citation :
Pour le 4, tu fais correctement le calcul (à condition de comprendre que les lignes et colonnes sont numérotées de 0 à N-1 et pas de 1 à N),

Avec ta façon de calculer, le coefficient en haut à gauche de la matrice est le coefficient d'indice 0,0.

Posté par
matheux14re : Transformée de Fourier discrète 16-09-23 à 16:19

Ah oui, je vois.

C'est parfait !

Merci beaucoup.

Je vais poster la suite après..

Posté par
matheux14re : Transformée de Fourier discrète 18-09-23 à 02:38

La suite est par là

Transformée de Fourier discrète (suite 1)


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !