\documentclass[10pt]{article}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[version=4]{mhchem}
\usepackage{stmaryrd}
\usepackage{bbold}
\usepackage{mathrsfs}
\usepackage{graphicx}
\usepackage[export]{adjustbox}
\graphicspath{ {./images/} }

\title{Conceptions : HEC Paris - ESSEC }

\author{OPTION SCIENTIFIQUE}
\date{}


\begin{document}
\maketitle


\section*{MATHÉMATIQUES}
Mercredi 28 avril 2021, de 14 h. à 18 h.

La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies.\\
Les candidats sont invités à encadrer dans la mesure du possible les résultats de leurs calculs.\\
Aucun document n'est autorisé. L'utilisation de toute calculatrice et de tout matériel électronique est interdite. Seule l'utilisation d'une règle graduée est autorisée.\\
Si au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il la signalera sur sa copie et poursuivra sa composition en expliquant les raisons des initiatives qu'il sera amené à prendre.

Ce problème étudie la transformée de Fourier discrète des vecteurs de \(\mathbb{C}^{n}\) où l'entier \(n\) est une puissance de 2. Dans la première partie, on découvre la matrice de Fourier-Vandermonde. Dans la seconde, on utilise les résultats obtenus pour les matrices circulantes et, dans la troisième partie, on s'intéresse à un algorithme d'obtention de la transformée de Fourier discrète que l'on applique ensuite au calcul d'un produit de convolution.

Dans tout le problème :

\begin{itemize}
  \item \(N\) désigne un entier supérieur ou égal à 1 et \(n=2^{N}\).
  \item On note \(\omega_{n}\) le nombre complexe \(\mathrm{e}^{\frac{2 i \pi}{n}}=\cos \left(\frac{2 \pi}{n}\right)+i \sin \left(\frac{2 \pi}{n}\right)\).
  \item Si \(z=\operatorname{Re}(z)+i \operatorname{Im}(z)\) est un nombre complexe, on note son conjugué \(\bar{z}=\operatorname{Re}(z)-i \operatorname{Im}(z)\). Ainsi, \(\overline{\omega_{n}}=\mathrm{e}^{-\frac{2 i \pi}{n}}\).
  \item \(\mathscr{B}_{n}=\left(e_{0}, e_{1}, \ldots, e_{n-1}\right)\) est la base canonique de \(\mathbb{C}^{n}\) et \(e_{\Sigma}\) est le vecteur \(e_{\Sigma}=\sum_{k=0}^{n-1} e_{k}\).
  \item Si \(x=\left(x_{0}, x_{1}, \ldots, x_{n-1}\right)=\sum_{k=0}^{n-1} x_{k} e_{k} \in \mathbb{C}^{n}\), on pourra identifier \(x\) et la matrice colonne \(X=\left(\begin{array}{c}x_{0} \\ x_{1} \\ \vdots \\ x_{n-1}\end{array}\right)\) de ses coordonnées dans la base \(\mathscr{B}_{n}\).
  \item \(\mathrm{Si} X=\left(\begin{array}{c}x_{0} \\ x_{1} \\ \vdots \\ x_{n-1}\end{array}\right)\), on note \(\bar{X}=\left(\begin{array}{c}\overline{x_{0}} \\ \overline{x_{1}} \\ \vdots \\ \overline{x_{n-1}}\end{array}\right)\).
\end{itemize}

Si \(M=\left(m_{i, j}\right)_{(i, j) \in \llbracket 0, n-1 \rrbracket^{2}} \in \mathscr{M}_{n}(\mathbb{C})\), on note \(\bar{M}\) la matrice \(\bar{M}=\left(\overline{m_{i, j}}\right)_{(i, j) \in \llbracket 0, n-1 \rrbracket^{2}} \in \mathscr{M}_{n}(\mathbb{C})\).\\
On utilisera sans démonstration la formule \(\overline{M X}=\bar{M} \bar{X}\).

\begin{itemize}
  \item Si \(x=\sum_{k=0}^{n-1} x_{k} e_{k}\), on remarquera que :
\end{itemize}

\[
\sum_{k=0}^{n-1}\left|x_{k}\right|^{2}=\left({ }^{t} \bar{X}\right) X
\]

où \({ }^{t} \bar{X}\) est la matrice ligne \(\left(\begin{array}{llll}\overline{x_{0}} & \overline{x_{1}} & \cdots & \overline{x_{n-1}}\end{array}\right)\).

\begin{itemize}
  \item Si \(\lambda\) est une valeur propre d'un endomorphisme \(g\) de \(\mathbb{C}^{n}\), on note \(E_{\lambda}(g)=\operatorname{Ker}\left(g-\lambda \operatorname{id}_{\mathbb{C}^{n}}\right)\) l'espace propre associé à la valeur propre \(\lambda\).
  \item Un sous-espace vectoriel \(G\) de \(\mathbb{C}^{n}\) est dit stable par un endomorphisme \(g\) de \(\mathbb{C}^{n}\) si, pour tout \(x \in G, g(x) \in G\).\\
On note alors \(g_{\mid G}:\left\{\begin{array}{l}G \rightarrow G \\ x \mapsto g(x)\end{array}\right.\). On utilisera sans démonstration le fait que \(g_{\mid G}\) est un endomorphisme de \(G\).\\
Cet endomorphisme \(g_{\mid G}\) est appelé endomorphisme de \(G\) induit par \(g\).\\
On s'intéresse, dans ce problème, à l'étude de l'application :
\end{itemize}

\[
F_{n}: x=\sum_{k=0}^{n-1} x_{k} e_{k} \mapsto \sum_{k=0}^{n-1}\left(\sum_{j=0}^{n-1} \omega_{n}^{k j} x_{j}\right) e_{k}
\]

On acceptera sans le démontrer que \(F_{n}\) est un endomorphisme de \(\mathbb{C}^{n}\).\\
On notera \(A_{n}\) la matrice de \(F_{n}\) dans la base \(\mathscr{B}_{n}\); on a donc \(A_{n}=\left(\omega_{n}^{k j}\right)_{(k, j) \in \llbracket 0, n-1 \rrbracket^{2}} \in \mathscr{M}_{n}(\mathbb{C})\).

\[
A_{n}=\left(\begin{array}{ccccc}
1 & 1 & 1 & \cdots & 1 \\
1 & \omega_{n} & \omega_{n}^{2} & \cdots & \omega_{n}^{n-1} \\
1 & \omega_{n}^{2} & \omega_{n}^{4} & \cdots & \omega_{n}^{2(n-1)} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & \omega_{n}^{n-1} & \omega_{n}^{2(n-1)} & \cdots & \omega_{n}^{(n-1)^{2}}
\end{array}\right)
\]

(on prendra bien garde que dans tout le problème, les indexations des coefficients de vecteurs et de matrices sont réalisées à l'aide de l'ensemble d'entiers \(\llbracket 0, n-1 \rrbracket\) )

\section*{Partie I = Premières propriétés de l'application \(F_{n}\)}
\begin{enumerate}
  \item Préliminaires :\\
(a) Que vaut \(\omega_{n}^{n}\) ? Et plus généralement, que vaut \(\left(\omega_{n}^{k}\right)^{n}\) pour \(k \in \mathbb{Z}\) ?
\end{enumerate}

Montrer que : \(\forall\left(k, k^{\prime}\right) \in \llbracket 0, n-1 \rrbracket^{2}, k \neq k^{\prime} \Longrightarrow \omega_{n}^{k} \neq \omega_{n}^{k^{\prime}}\).

Justifier alors la factorisation dans \(\mathbb{C}[X]: X^{n}-1=\prod_{k=0}^{n-1}\left(X-\omega_{n}^{k}\right)\).\\
(b) Soit \(s \in \mathbb{Z}\); montrer que \(\sum_{q=0}^{n-1} \omega_{n}^{s q}=\left\{\begin{array}{ll}n & \text { si } s \text { est un multiple de } n \\ 0 & \text { sinon }\end{array}\right.\).\\
2. Cas particulier \(n=2\) :\\
(a) Expliciter la matrice \(A_{2}\). Est-elle inversible? Si oui, calculer son inverse.\\
(b) \(A_{2}\) est-elle diagonalisable? Si oui, déterminer ses valeurs propres et une base de vecteurs propres.\\
3. Cas particulier \(n=4\) :\\
(a) Expliciter la matrice \(A_{4}\) et calculer la matrice \(A_{4} \overline{A_{4}}\). En déduire que \(A_{4}\) est inversible et donner son inverse.\\
(b) Calculer la matrice \(A_{4}^{2}\) puis \(A_{4}^{4}\). En déduire un polynôme annulateur non nul de \(A_{4}\).\\
(c) Quelles sont les valeurs propres possibles de \(A_{4}\) ?\\
(d) On note \(P=\operatorname{vect}\left(e_{0}, e_{\Sigma}\right)\); montrer que \(P\) est stable par \(F_{4}\).

Écrire la matrice \(C_{4}\) de l'endomorphisme induit \(F_{4 \mid P}\) dans la base ( \(e_{0}, e_{\Sigma}\) ) de \(P\).\\
Déterminer les valeurs propres de \(C_{4}\) ainsi qu'une base de vecteurs propres de \(C_{4}\).\\
En déduire que 2 et -2 sont valeurs propres de \(F_{4}\) et déterminer des vecteurs propres de \(F_{4}\) associés à ces deux valeurs propres.\\
(e) Calculer \(F_{4}\left(e_{0}+e_{2}\right)\) ainsi que \(F_{4}\left(e_{1}-e_{3}\right)\).

En déduire le spectre de \(F_{4}\) ainsi que ses espaces propres. \(F_{4}\) est-il diagonalisable?\\
4. Exemples de transformées de Fourier discrètes :

Soient \(x=\sum_{k=0}^{n-1} x_{k} e_{k} \in \mathbb{C}^{n}\) et \(y=F_{n}(x)=\sum_{k=0}^{n-1} y_{k} e_{k}\).\\
(a) Déterminer \(y\) dans les trois cas suivants:\\
i. \(x=e_{\Sigma}=\sum_{k=0}^{n-1} e_{k}\).\\
ii. \(x=\sum_{k=0}^{n-1} a^{k} e_{k}\) où \(a \in \mathbb{C}\) tel que \(|a| \neq 1\).\\
iii. \(x=\sum_{k=0}^{n-1}\binom{n-1}{k} e_{k}\).\\
(b) On suppose que pour tout \(k \in \llbracket 0, n-1 \rrbracket, x_{k} \in \mathbb{R}\).

Montrer que pour tout \(k \in \llbracket 1, n-1 \rrbracket, y_{k}=\overline{y_{n-k}}\).\\
5. Inversibilité de \(A_{n}\) dans le cas général et formule de Parseval :\\
(a) Calculer la matrice \(A_{n} \overline{A_{n}}\).

Justifier alors que \(A_{n}\) est inversible et préciser \(A_{n}^{-1}\).\\
(b) Justifier que \(F_{n}\) est inversible et préciser \(F_{n}^{-1}\).\\
(c) Montrer que pour tout \(X \in \mathscr{M}_{n, 1}(\mathbb{C}), \quad n\left({ }^{t} \bar{X}\right) X={ }^{t}\left(\overline{A_{n} X}\right) A_{n} X\).\\
(d) En déduire la formule de Parseval : pour tout \(x=\sum_{k=0}^{n-1} x_{k} e_{k}, \quad \sum_{k=0}^{n-1}\left|\sum_{j=0}^{n-1} \omega_{n}^{k j} x_{j}\right|^{2}=n \sum_{k=0}^{n-1}\left|x_{k}\right|^{2}\).\\
6. Valeurs propres de \(A_{n}\) :\\
(a) Soit \(\lambda \in \mathbb{C}\), une valeur propre de \(A_{n}\); montrer que \(|\lambda|=\sqrt{n}\) (on pourra utiliser la question 5. (c)).\\
(b) Montrer que la matrice \(A_{n}^{2}\) est la matrice de terme général \(b_{k, j}\) où \((k, j) \in \llbracket 0, n-1 \rrbracket^{2}\) tel que :

\[
b_{0,0}=n \quad b_{k, n-k}=n \text { pour } k \in \llbracket 1, n-1 \rrbracket \quad \text { et } \quad b_{k, j}=0 \text { sinon }
\]

Autrement dit, \(A_{n}^{2}=\left(\begin{array}{ccccc}n & 0 & \cdots & \cdots & 0 \\ 0 & \cdots & 0 & 0 & n \\ \vdots & . & . & . & 0 \\ 0 & 0 & . & . & \vdots \\ 0 & n & 0 & \cdots & 0\end{array}\right)\).\\
(c) Préciser alors \(A_{n}^{4}\).

En déduire un polynôme annulateur non nul de \(A_{n}\) et les valeurs propres possibles de \(A_{n}\).\\
7. Construction de vecteurs propres de \(F_{n}\) :\\
on suppose dans cette question que \(n \geq 8\).\\
On note \(e_{\cos }=\sum_{k=0}^{n-1} \cos \left(\frac{2 k \pi}{n}\right) e_{k}\) et \(e_{\sin }=\sum_{k=0}^{n-1} \sin \left(\frac{2 k \pi}{n}\right) e_{k}\).\\
(a) Calculer \(F_{n}\left(e_{1}+e_{n-1}\right)\) et \(F_{n}\left(e_{1}-e_{n-1}\right)\) en fonction des vecteurs \(e_{\cos }\) et \(e_{\sin }\).\\
(b) On note \(G_{n}\) l'endomorphisme canoniquement associé à \(A_{n}^{2}\).

Préciser \(G_{n}\left(e_{1}+e_{n-1}\right)\) et \(G_{n}\left(e_{1}-e_{n-1}\right)\) et en déduire que :

\[
F_{n}\left(e_{\cos }\right)=\frac{n}{2}\left(e_{1}+e_{n-1}\right) \quad \text { et } \quad F_{n}\left(e_{\sin }\right)=i \frac{n}{2}\left(e_{1}-e_{n-1}\right)
\]

(c) On note \(Q=\operatorname{vect}\left(e_{1}+e_{n-1}, e_{\cos }\right)\).

Vérifier que \(Q\) est de dimension 2 et montrer que \(Q\) est stable par \(F_{n}\).\\
Quelle est la matrice de l'endomorphisme induit \(F_{n \mid Q}\) dans la base ( \(e_{1}+e_{n-1}, e_{\cos }\) ) de \(Q\) ?\\
Déterminer les valeurs propres ainsi qu'une base de vecteurs propres de cette matrice.\\
En déduire que \(\sqrt{n}\) et \(-\sqrt{n}\) sont valeurs propres de \(F_{n}\) et déterminer des vecteurs propres de \(F_{n}\) associés à ces deux valeurs propres.\\
(d) Procéder de la même façon avec \(R=\operatorname{vect}\left(e_{1}-e_{n-1}, e_{\text {sin }}\right)\).\\
(e) En déduire les valeurs propres de \(F_{n}\).

\section*{Partie II - Lien avec les matrices circulantes}
Soit \(a=\left(a_{0}, a_{1}, \ldots, a_{n-1}\right) \in \mathbb{C}^{n}\); on appelle matrice circulante associée à \(a\) et on note \(C(a)\) la matrice :

\[
C(a)=\left(\begin{array}{ccccc}
a_{0} & a_{1} & a_{2} & \cdots & a_{n-1} \\
a_{n-1} & a_{0} & a_{1} & \cdots & a_{n-2} \\
a_{n-2} & a_{n-1} & \ddots & \ddots & \vdots \\
\vdots & \ddots & \ddots & \ddots & a_{1} \\
a_{1} & \cdots & a_{n-2} & a_{n-1} & a_{0}
\end{array}\right) \in \mathscr{M}_{n}(\mathbb{C})
\]

On note en particulier, \(J_{n}=C(0,1,0,0, \ldots, 0)=\left(\begin{array}{ccccc}0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \ddots & \vdots \\ \vdots & 0 & \ddots & \ddots & 0 \\ 0 & \vdots & \ddots & \ddots & 1 \\ 1 & 0 & \cdots & 0 & 0\end{array}\right)\)\\
(c' est-à-dire \(a_{1}=1\) et \(a_{j}=0\) si \(j \neq 1\) ).\\
On note \(\varphi_{n}\) l'endomorphisme de \(\mathbb{C}^{n}\) dont la matrice dans la base \(\mathscr{B}_{n}\) est \(J_{n}\). Enfin, on note \(\operatorname{Circ}_{n}(\mathbb{C})\) l'ensemble des matrices circulantes de \(\mathscr{M}_{n}(\mathbb{C})\).\\
8. Puissances successives de \(J_{n}\) :\\
(a) Pour tout \(j \in \llbracket 0, n-1 \rrbracket\), déterminer \(\varphi_{n}\left(e_{j}\right)\), puis \(\varphi_{n}^{2}\left(e_{j}\right)\) et en déduire la matrice \(J_{n}^{2}\).\\
(b) Soit \(k \in \llbracket 1, n-1 \rrbracket\). Montrer que :

\[
\forall j \in \llbracket k, n-1 \rrbracket \quad \varphi_{n}^{k}\left(e_{j}\right)=e_{j-k} \quad \text { et } \quad \forall j \in \llbracket 0, k-1 \rrbracket \quad \varphi_{n}^{k}\left(e_{j}\right)=e_{n-k+j}
\]

(c) Enfin, pour tout \(j \in \llbracket 0, n-1 \rrbracket\), calculer \(\varphi_{n}^{n}\left(e_{j}\right)\).

Que vaut \(\varphi_{n}^{n}\) ?\\
(d) Déduire de ce qui précède l'expression des matrices \(J_{n}^{k}\) pour \(k \in \llbracket 1, n \rrbracket\).\\
9. Réduction de \(J_{n}\) :\\
(a) Déduire de la question 8 ., les valeurs propres possibles de \(J_{n}\).\\
(b) Montrer que pour tout \(k \in \llbracket 0, n-1 \rrbracket, F_{n}\left(e_{k}\right)\) est vecteur propre de \(\varphi_{n}\) pour la valeur propre \(\omega_{n}^{k}\).\\
(c) Donner alors tous les sous-espaces propres de \(\varphi_{n}\).

En déduire que \(J_{n}\) est diagonalisable dans \(\mathscr{M}_{n}(\mathbb{C})\) et que \(J_{n}=\frac{1}{n} A_{n} D_{n} \overline{A_{n}}\) où \(D_{n}\) est la matrice diagonale de taille \(n\) dont les coefficients diagonaux sont les complexes \(\omega_{n}^{k}\) où \(k \in \llbracket 0, n-1 \rrbracket\).\\
10. Structure de \(\operatorname{Circ}_{n}(\mathbb{C})\) :\\
(a) Justifier que \(\operatorname{Circ}_{n}(\mathbb{C})\) est un sous-espace vectoriel de \(\mathscr{M}_{n}(\mathbb{C})\).

En donner une base et la dimension.\\
(b) Montrer que \(\operatorname{Circ}_{n}(\mathbb{C})\) est stable pour la multiplication.\\
11. Réduction des matrices circulantes:

Soit \(a=\left(a_{0}, a_{1}, \ldots, a_{n-1}\right) \in \mathbb{C}^{n}\) et \(C(a)\) la matrice circulante associée.\\
(a) Vérifier que \(C(a)=\sum_{k=0}^{n-1} a_{k} J_{n}^{k}\).\\
(b) Montrer alors que \(C(a)\) est diagonalisable dans \(\mathscr{M}_{n}(\mathbb{C})\) et préciser ses valeurs propres.\\
(c) Exemple : soit \(\alpha=(0,1,0,0, \ldots, 0,1) \in \mathbb{C}^{n}\), c'est-à-dire :

\[
\alpha_{1}=\alpha_{n-1}=1 \quad \text { et } \quad \alpha_{i}=0 \quad \text { si } i \neq 1 \text { et } i \neq n-1
\]

On note \(S_{n}=C(\alpha)\).\\
Quelles sont les valeurs propres de \(S_{n}\) ?\\
La matrice \(S_{n}\) est-elle inversible?\\
12. Caractérisation des matrices circulantes:

On se propose dans cette question, de montrer que \(\operatorname{Circ}_{n}(\mathbb{C})\) est l'ensemble des matrices qui commutent avec \(J_{n}\). On note \(\Omega=\left\{M \in \mathscr{M}_{n}(\mathbb{C}) \mid J_{n} M=M J_{n}\right\}\).\\
(a) Vérifier que \(\operatorname{Circ}_{n}(\mathbb{C}) \subset \Omega\).

Dans la suite de cette question, on considère une matrice \(M \in \mathscr{M}_{n}(\mathbb{C})\) vérifiant \(J_{n} M=M J_{n}\) et on note \(g\) l'endomorphisme de \(\mathbb{C}^{n}\) dont la matrice dans la base canonique de \(\mathbb{C}^{n}\) est \(M\).\\
(b) Montrer que pour tout \(k \in \llbracket 0, n-1 \rrbracket\), il existe \(\lambda_{k} \in \mathbb{C}\) tel que \(g\left(F_{n}\left(e_{k}\right)\right)=\lambda_{k} F_{n}\left(e_{k}\right)\).\\
(c) En déduire une explicitation simple de \(\frac{1}{n} \overline{A_{n}} M A_{n}\).\\
(d) Démontrer que \(\Omega\) est un sous-espace vectoriel de \(\mathscr{M}_{n}(\mathbb{C})\) de dimension \(n\), et que \(\Omega\) est égal à \(\operatorname{Circ}_{n}(\mathbb{C})\).

\section*{Partie III - Construction algorithmique}
\begin{enumerate}
  \setcounter{enumi}{12}
  \item Algorithme de calcul de \(F_{n}(x)\) :\\
algorithme de Cooley-Tukey ou algorithme «papillon».\\
On rappelle que l'entier \(n\) est égal à \(2^{N}\) avec \(N\) entier supérieur ou égal à 1.\\
On se propose dans cette question, de construire un algorithme de calcul de \(F_{n}(x)\), pour un vecteur \(x=\sum_{k=0}^{n-1} x_{k} e_{k}=\left(x_{0}, x_{1}, \ldots, x_{n-1}\right)\) de \(\mathbb{C}^{n}\).\\
Pour tout \(k \in[0, n-1]\), on note \(\left[F_{n}(x)\right]_{k}\) la composante d'indice \(k\) de \(F_{n}(x)\) dans la base \(\mathscr{B}_{n}\). À \(x\), on associe les vecteurs \(y=\left(y_{0}, y_{1}, \ldots, y_{n / 2-1}\right) \in \mathbb{C}^{n / 2}\) et \(z=\left(z_{0}, z_{1}, \ldots, z_{n / 2-1}\right) \in \mathbb{C}^{n / 2}\) tels que pour tout \(k \in \llbracket 0, \frac{n}{2}-1 \rrbracket, y_{k}=x_{2 k}\) et \(z_{k}=x_{2 k+1}\).\\
Ainsi, pour \(n=8\), pour \(x=\left(x_{0}, x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7}\right) \in \mathbb{C}^{8}\), on a \(y=\left(x_{0}, x_{2}, x_{4}, x_{6}\right) \in \mathbb{C}^{4}\) et \(z=\left(x_{1}, x_{3}, x_{5}, x_{7}\right) \in \mathbb{C}^{4}\).\\
(a) Vérifier que pour tout \(k \in \llbracket 0, \frac{n}{2}-1 \rrbracket\) :
\end{enumerate}

\[
\left[F_{n}(x)\right]_{k}=\left[F_{n / 2}(y)\right]_{k}+\omega_{n}^{k}\left[F_{n / 2}(z)\right]_{k} \quad \text { et } \quad\left[F_{n}(x)\right]_{k+n / 2}=\left[F_{n / 2}(y)\right]_{k}-\omega_{n}^{k}\left[F_{n / 2}(z)\right]_{k}
\]

(b) On suppose déjà calculés \(F_{n / 2}(y)\) et \(F_{n / 2}(z)\) et on considère l'algorithme suivant:

\begin{verbatim}
A prend la valeur 1
pour \(k\) allant de 0 à \(\frac{n}{2}-1\) faire
    \(B\) prend la valeur \(A \times\left[F_{n / 2}(z)\right]_{k}\)
    \(\alpha_{k}\) prend la valeur \(\left[F_{n / 2}(y)\right]_{k}+B\)
    \(\alpha_{k+n / 2}\) prend la valeur \(\left[F_{n / 2}(y)\right]_{k}-B\)
    \(A\) prend la valeur \(\omega_{n} \times A\)
fin
\end{verbatim}

Comparer le vecteur \(\left(\alpha_{0}, \alpha_{1}, \ldots, \alpha_{n-1}\right)\) obtenu après exécution de cet algorithme au vecteur \(F_{n}(x)\).\\
(c) On s'intéresse, dans cette question, à l'efficacité de l'algorithme précédent en terme de rapidité de calcul. Pour ceci, la procédure habituelle consiste à évaluer le nombre d'opérations arithmétiques (additions, soustractions, multiplications et divisions de deux nombres complexes) nécessaires à l'obtention du résultat final.\\
L'implémentation de ce type d'algorithmes, dits récursifs (pour calculer des images par la fonction \(F_{n}\), on commence par calculer des images par la fonction \(F_{n / 2}\) ), nécessite une gestion particulière dans la mémoire de la machine, du stockage des variables et de l'adressage des instructions exécutées, gestion dont nous ne tiendrons pas compte dans ce sujet.\\
On note \(u_{N}\) le nombre d'opérations nécessaires au calcul de \(F_{n}(x)\) avec \(n=2^{N}\).\\
Les calculs de \(F_{n / 2}(y)\) et de \(F_{n / 2}(z)\) nécessitent donc chacun \(u_{N-1}\) opérations.\\
On convient que \(u_{0}=0\).\\
Justifier alors que la suite ( \(u_{N}\) ) vérifie la relation de récurrence \(u_{N}=2 u_{N-1}+2^{N+1}\).\\
(d) En déduire pour tout \(N \in \mathbb{N}\), la valeur de \(u_{N}\) en fonction de \(N\), puis de \(n\).\\
(on pourra d'abord s'intéresser à la suite \(\left(v_{N}\right)\) définie par: \(\forall N \in \mathbb{N}, v_{N}=\frac{u_{N}}{2^{N}}\) )\\
14. Produit de convolution de deux vecteurs de \(\mathbb{C}^{n / 2}\) :

Soient \(y=\left(y_{0}, y_{1}, \ldots, y_{n / 2-1}\right) \in \mathbb{C}^{n / 2}\) et \(z=\left(z_{0}, z_{1}, \ldots, z_{n / 2-1}\right) \in \mathbb{C}^{n / 2}\); on pose, pour tout \(k \in \llbracket \frac{n}{2}, n-1 \rrbracket, y_{k}=z_{k}=0\);\\
on construit ainsi deux vecteurs notés \(\tilde{y}=\left(y_{0}, y_{1}, \ldots, y_{n-1}\right) \in \mathbb{C}^{n}\) et \(\tilde{z}=\left(z_{0}, z_{1}, \ldots, z_{n-1}\right) \in \mathbb{C}^{n}\). On pose alors \(x=y * z=\left(x_{0}, x_{1}, \ldots, x_{n-1}\right) \in \mathbb{C}^{n}\) tel que pour tout \(k \in \llbracket 0, n-1 \rrbracket\), \(x_{k}=\sum_{j=0}^{k} y_{j} z_{k-j}\).\\
Le vecteur \(x\) est appelé produit de convolution des vecteurs \(y\) et \(z\).\\
(a) Vérifier que pour tout \(k \in \llbracket 0, n-1 \rrbracket,\left[F_{n}(x)\right]_{k}=\left[F_{n}(\tilde{y})\right]_{k} \cdot\left[F_{n}(\tilde{z})\right]_{k}\).\\
(b) On calcule le produit de convolution \(x=y * z\) en calculant successivement:

\begin{itemize}
  \item les transformées de Fourier discrètes \(F_{n}(\widetilde{y})\) et \(F_{n}(\widetilde{z})\) par l'algorithme étudié dans la question 13.
  \item les produits : pour tout \(k \in \llbracket 0, n-1 \rrbracket,\left[F_{n}(x)\right]_{k}=\left[F_{n}(\widetilde{y})\right]_{k} \cdot\left[F_{n}(\widetilde{z})\right]_{k}\), donc \(F_{n}(y * z)\),
  \item la transformée de Fourier discrète inverse \(F_{n}^{-1}\left(F_{n}(y * z)\right)\).
\end{itemize}

Déterminer le nombre d'opérations nécessaires à la réalisation de chacune de ces trois étapes, et en déduire en fonction de \(n\) un équivalent du nombre d'opérations nécessaires au calcul du produit de convolution \(x=y * z\) par cette méthode.\\
(c) Comparer, du point de vue du nombre d'opérations effectuées, cette méthode à la méthode du calcul du produit \(x=y * z\) par la définition : pour tout \(k \in \llbracket 0, n-1 \rrbracket, x_{k}=\sum_{j=0}^{k} y_{j} z_{k-j}\).\\
\includegraphics[max width=\textwidth, alt={}, center]{6a9df6ca-aff3-4805-b324-dc93f7e3bef8-7_152_191_2430_927}


\end{document}