Questions du sujet
1. Résoudre dans $\mathbb{C}$ l’équation $z^N = 1$. On exprimera les solutions à l’aide du nombre $\omega$.
2. Déterminer l’ensemble des entiers relatifs $j$ tels que $\omega^j = 1$.
3. Démontrer que, pour tout $k \in \mathbb{N}$, $\frac{1}{\omega^k} = \overline{\omega^k}$.
4. Soit $q$ un nombre complexe et $N$ un entier naturel supérieur ou égal à 1. Calculer $\sum_{n=0}^{N-1} q^n$. On distinguera les cas $q = 1$ et $q \neq 1$.
5. En déduire la valeur de $\sum_{n=0}^{N-1} \omega^{rn}$, dans les trois cas $r = 0$, $r \in \llbracket 1, N – 1 \rrbracket$, $r \in \llbracket -(N-1), -1 \rrbracket$.}
6. Vérifier que $\forall k \in \mathbb{Z}$, $c_k(f) = \frac{1}{2\pi}\int_0^{2\pi} f(t) e^{-ikt} dt$.
7. Question de cours : citer le théorème de Parseval pour une fonction $f \in \mathcal{C}_0^{2\pi}$.
8. Pour tout entier naturel $k$ non nul, exprimer $|c_k(f)|^2$ et $|c_{-k}(f)|^2$ en fonction de $a_k^2(f)$ et $b_k^2(f)$ et, en utilisant le théorème de Parseval, démontrer que $\lim_{k \to +\infty} c_k(f) = \lim_{k \to +\infty} c_{-k}(f) = 0$.
9. Pour tout entier naturel $k$ non nul, justifier l’existence de $a_k(f’)$ et $b_k(f’)$.
10. À l’aide d’intégrations par parties, démontrer que, pour tout entier naturel $k$ non nul,
\[
\left\{
\begin{array}{l}
a_k(f’) = k b_k(f), \\
b_k(f’) = -k a_k(f).
\end{array}\right.
\]
En déduire que, pour tout $k \in \mathbb{Z}^*$, $c_k(f’) = ik c_k(f)$.}
11. En déduire que $|c_k(f)| = \underset{k \to +\infty}{o}\left(\frac{1}{k}\right)$ et $|c_{-k}(f)| = \underset{k \to +\infty}{o}\left(\frac{1}{k}\right)$.
12. Montrer que $G_3$ est une matrice orthogonale de $\mathcal{M}_3(\mathbb{R})$. Identifier géométriquement l’isométrie canoniquement associée à la matrice $G_3$ (on précisera ses éléments caractéristiques).
13. Calculer le polynôme caractéristique de $G_3$. Montrer que la matrice $G_3$ est diagonalisable dans $\mathcal{M}_3(\mathbb{C})$. Est-elle diagonalisable dans $\mathcal{M}_3(\mathbb{R})$ ?
14. Déterminer une matrice $P_3$ inversible dans $\mathcal{M}_3(\mathbb{C})$ et une matrice $D_3 \in \mathcal{M}_3(\mathbb{C})$ diagonale telles que $G_3 = P_3 D_3 P_3^{-1}$.
15. Pour tout $(a_0, a_1, a_2) \in \mathbb{C}^3$ exprimer $C(a_0, a_1, a_2)$ à l’aide de $I_3$, $G_3$ et $G_3^2$ et en déduire que $C(a_0, a_1, a_2)$ est diagonalisable dans $\mathcal{M}_3(\mathbb{C})$.}
16. Montrer que le polynôme caractéristique de $G_N$ est $X^N – 1$.
17. $G_N$ est-elle diagonalisable dans $\mathcal{M}_N(\mathbb{C})$ ? Justifier.
18. Calculer le produit matriciel $G_N C_k$. Démontrer que $\omega^k$ est une valeur propre de $G_N$ et donner un vecteur propre associé.
19. En déduire que la famille des vecteurs colonnes $(C_1, C_2, …, C_N)$ est libre, puis que la matrice $P_N$ est inversible.
20. Calculer le produit matriciel $P_N \overline{P_N}$ et en déduire que $P_N^{-1} = \frac{1}{N} \overline{P_N}$.}
21. Pour tout $j \in \llbracket 1, N \rrbracket$, exprimer $g(e_j)$ en fonction des vecteurs $e_1, e_2, …, e_n$. On distinguera le cas $j=1$.
22. Pour tout $k \in \llbracket 1, N-1 \rrbracket$ et tout $j \in \llbracket 1, N \rrbracket$, exprimer $g^k(e_j)$ en fonction des vecteurs $e_1, …, e_n$. On distinguera les cas $j>k$ et $j \leq k$.
23. En déduire, pour tout $k \in \llbracket 0, N-1 \rrbracket$, l’expression de $G_N^k$ comme une matrice $C(a_0, …, a_{N-1})$ particulière. (On rappelle que $G_N^0 = I_N$).
24. En exprimant $C(a_0, …, a_{N-1})$ comme combinaison linéaire de $G_N^0$, $G_N^1$, …, $G_N^{N-1}$ et en utilisant les questions précédentes, justifier que $C(a_0, …, a_{N-1})$ est diagonalisable dans $\mathcal{M}_N(\mathbb{C})$. Donner sa réduite diagonale et une matrice de passage de la base canonique à une base de vecteurs propres.
25. À l’aide du résultat précédent, calculer le déterminant de la matrice $C(a_0, a_1, …, a_{N-1})$.}
26. Justifier, en explicitant le théorème utilisé, que $\lim_{N \to +\infty} a’_0(N) = a_0$, et que, pour tout $k \in \mathbb{N}^*$, $\lim_{N \to +\infty} a’_k(N) = a_k$ et $\lim_{N \to +\infty} b’_k(N) = b_k$.
27. En déduire que, pour tout entier relatif $k$, $\lim_{N \to +\infty} c’_k(N) = c_k$.
28. Combien d’opérations (additions et multiplications entre nombres complexes) sont nécessaires pour calculer les $N$ termes de la transformée de Fourier $\hat{u}$, connaissant ceux de l’échantillon $u$ et les nombres $e^{-ik2\pi n/N}$ ? Parmi les multiplications, on ne comptabilise pas celles dont l’un des facteurs est égal à 1.
29. Démontrer que $\forall k \in \llbracket 0, N-1 \rrbracket, u_k = \frac{1}{N} \sum_{n=0}^{N-1} \hat{u}_n e^{ik2\pi n/N}$.
30. Montrer que, pour tout $\ell \in \llbracket 1, N-1 \rrbracket$, $\hat{u}_\ell = \hat{u}_{N-\ell}$.}
31. Combien suffit-il d’opérations (additions, multiplications entre nombres complexes et conjugaison d’un nombre complexe) pour calculer les $N$ termes de la transformée de Fourier $\hat{u}$, connaissant ceux de l’échantillon $u$ de taille $N$ et les nombres $e^{-ik2\pi n/N}$ ?
32. Donner un équivalent de ce nombre d’opérations lorsque $N$ tend vers $+\infty$.
33. Montrer que $\hat{u}_{N/2} = \hat{y}_0 – \hat{z}_0$.
34. Montrer que,
\[
\forall k \in \llbracket 0, \frac{N}{2}-1\rrbracket,
\left\{
\begin{array}{l}
\hat{u}_k = \hat{y}_k + \overline{\omega}^k \hat{z}_k, \\
\hat{u}_{k+N/2} = \hat{y}_k – \overline{\omega}^k \hat{z}_k.
\end{array}
\right.
\]
35. Justifier que $T(2) = 3$ et démontrer que, pour tout entier $j$ supérieur ou égal à 2, $\forall r \in \llbracket 2, j \rrbracket, T(2^r) \leq 2 T(2^{r-1}) + 4 \times 2^{r-1}$.}
36. Démontrer que $T(N) \leq 2 \ln 2 N \ln N$. On pourra utiliser la suite auxiliaire $(t_k)_{1 \leq k \leq j}$, définie par $t_k = \frac{T(2^k)}{2^k}$.
37. Expliquer pourquoi cette méthode est qualifiée de transformée de Fourier « rapide ».
38. Étant donnée une suite $(u_n)_{n \in \mathbb{Z}}$ périodique de période $N$, démontrer que, pour tout entier relatif $p \in \llbracket -N + 1, 0 \rrbracket$, $\sum_{k=p}^{p+N-1} u_k = \sum_{k=0}^{N-1} u_k$.
39. Montrer que la convolée circulaire de deux suites périodiques de période $N$ est une suite périodique de période $N$.
40. On considère les suites $r$ et $s$ périodiques de période 3, dont les germes sont $r = (1, 2, 3)$ et $s = (6, 5, 4)$. Donner le germe de $r \ast s$.}
41. Combien d’opérations (additions et multiplications) sont à priori nécessaires pour calculer les $N$ termes $(u \ast v)_0, (u \ast v)_1, …, (u \ast v)_{N-1}$ à partir de la donnée de $u_0, …, u_{N-1}$ et $v_0, …, v_{N-1}$ ?
42. Pour deux suites $u$ et $v$ périodiques de période $N$, montrer que $\widehat{u \ast v} = \hat{u} \cdot \hat{v}$.
43. En utilisant à la fois la transformée de Fourier rapide, le résultat de la question 42 et la formule d’inversion, donner, lorsque $N = 2^j$, un majorant (dépendant de $N$) du nombre d’opérations (additions, multiplications entre nombres complexes, divisions d’un nombre complexe par un entier naturel) utilisées pour calculer efficacement le germe de la convolée circulaire de deux suites périodiques de période $N$.}