\documentclass[11pt,a4paper]{article}
%\documentclass[11pt,a4paper]{book}
\usepackage[french]{babel}
%%%ACCENTSCIDESSOUS%%%%
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{lastpage}
\usepackage{times}

%\usepackage{A4w}
%\newcommand{\R}{{\bf R}}
\newcommand{\Bel}{\widehat{B}_{2l}}
\newcommand{\Bem}{\widehat{B}_{2m}}
\newcommand{\Bemp}{\widehat{B}_{2m+2}}
%\newcommand{\ld}{\lambda_D}
\newcommand{\La}{\lambda}
%\newcommand{\l2om}{L_{\omega}^2}
%\newcommand{\l2ab}{L^2(a,b)}
\newcommand{\ep}{\varepsilon}
\newcommand{\Om}{\Omega}
\newcommand{\om}{\omega}
\newcommand{\dd}{\Delta}
\newcommand{\bbl}{B_L}
\newcommand{\lik}{\lambda_{i}}
\newcommand{\likk}{\lambda_{i,k}}
\newcommand{\xik}{x_{i,k}}
\newcommand{\vfi}{\varphi}
\newcommand{\eps}{\varepsilon}
\newcommand{\psieps}{\psi_{\varepsilon}}
\newcommand{\grad}{\nabla}
\newcommand{\Ep}{E^{\prime}}
\newcommand{\lun}{{\ell}^1}
\newcommand{\linf}{{\ell}^{\infty}}
\newcommand{\vois}{{\cal V}(x)}
\newcommand{\Cab}{{\cal C}[a,b]}
\def\e {{é}}
\def\ee {{è}}
\def\eee {{\^e}}
\def\e {{é}}
\def\ea {{é} }
\def\ee {{è}}
\def\eee {{\^e}}
\def\a {{à} }
\def\aa {{\^a}}
\def\ii {{\^\i}}
\def\iii {{\"\i}}
\def\ccaadd{ c'est-{à}-dire }
\def\u {{\`u} }
\def\uu {{\^u}}
\def\oo {{\^o}}
\def\ooo {{\"o}}
\newtheorem{lem}{Lemma}
\newtheorem{theo}{Th\'eor\`eme}
\newtheorem{theor}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem{defi}{D\'efinition}
\newtheorem{rem}{Remarque}
\newtheorem{exo}{Exercice}
%\newtheorem{Exer}{Exercice}[chapter]  %Exercice
\newtheorem{Exer}{Exercice}  %Exercice
\def\dexer{\begin{Exer}\rm}    %sans
\def\fexer{\end{Exer}}        %italique !
\def\dexo{\begin{exo}\rm}    %sans
\def\fexo{\end{exo}}  
% ensembles Q R N Z C
\gdef\RR{\hbox{\rm I\kern-.25em\hbox{R}}}
\gdef\NN{\hbox{\rm I\kern-.25em\hbox{N}}}
\gdef\PP{\hbox{\rm I\kern-.25em\hbox{P}}}
\gdef\ZZ{{\sl Z\hskip -1ex Z} }
\gdef\CC{\rm \hbox{C\kern-.56em\raise.4ex
         \hbox{$\scriptscriptstyle |$}\kern+0.5 em }}
\gdef\QQ{\rm \hbox{Q\kern-.35em\raise.4ex
         \hbox{$\scriptscriptstyle |$}\kern+0.5 em }}
\renewcommand{\theequation}{\thesection.\arabic{equation}}

% Numerotation des pages / la derniere
\makeatletter
\renewcommand{\@evenfoot}%
        {\thepage \slash \pageref{LastPage}}
\renewcommand{\@oddfoot}{\@evenfoot}
\makeatother

% Suppression de l'indentation
\setlength{\parindent}{0pt}


\begin{document}

{\raggedright  Analyse fonctionnelle\hfill{}
 \par}

{\raggedright ENS de Cachan\hfill{} 2008-2009}


\vspace{0.5cm}

{\centering TD : TFD (Préparation au TP) \\}

\vspace{0.5cm}
Dans tout ce qui suit, on suppose que $N\geq 2$ est un entier pair. \\On note $\omega_N=\exp\left(\frac{2i\pi}{N}\right)$, racine $N$-ième de l'unité.\\
On rappelle que la TFD et la TFD inverse sont données par les formules:
\begin{eqnarray*}
\mbox{TFD}:&u=(u_l)_{0\leq l\leq N-1} \longmapsto& \tilde u=(\tilde u_n)_n \hbox{ où } \tilde u_n = \frac{1}{N}\sum_{l=0}^{N\!-\!1}u_l\omega_N^{-nl},\, n=-\frac N2, ...,\frac N2-1,\\
\mbox{TFD}^{-1}:&\tilde u=(\tilde u_n)_{-\frac N2\leq n\leq \frac N2-1}  \longmapsto& u=(u_k)_k \hbox{ où } u_k=\sum_{n=-\frac N2}^{\frac N2-1} \tilde u_n \omega_N^{kn}, \; k=0, ..., N\!-\!1.
\end{eqnarray*}
 \dexer  
\hfill
\newline\newline
Soit $u$ une fonction continue et $a$-périodique. Montrer que si $u_k=u(ka/N)$ pour $k=0,N-1$, les 
$\tilde u_n$, pour
$n=\frac{-N}{2},...,\frac{N}{2}-1$, sont des approximations des coefficients de Fourier de $u$, $$c_n(u)=\frac{1}{a} \int_0^a u(x) \exp \left( \frac{-2i\pi nx}{a}\right),$$ par la formule des trapèzes.
\fexer
 \dexer  
\hfill
\newline\newline
On suppose que les échantillons $u=(u_k)_k$ sont réels. Soit $\tilde u=(\tilde u_n)_n=\mbox{TFD}(u)$, montrer que 
 $\tilde u_0$ et $\tilde u_{-\frac N2}$ sont r{é}els, et que $\tilde u_k=\overline{\tilde u_{-k}}$ pour $k=1...\frac N2-1$.
\fexer
% \dexer  
%\hfill
%\newline\newline
%Si $u$ est maintenant un polynôme trigonométrique réel dont les fréquences sont parmi $-\frac N2, ..., \frac N2 -1$, montrer que le terme
%$\tilde u_{-\frac N2}$ est nul.
%\fexer 
 \dexer 
\hfill
\newline\newline
On consid{è}re un r{é}el $a$, une fonction $u$ de $\RR^2$ dans $\RR$, telle que $u(x+a,y+a)=u(x,y)$. On pose $u_{k,l}=u\left(\frac{ka}{N},\frac{la}{N}\right)$. On d{é}finit la TFD des
$u_{k,l}$ comme la suite des coefficients, pour $m,n \in \{-\frac N 2,...,\frac N 2 -1\}$,
$$
\tilde{u}_{m,n}=\frac{1}{N^2}\sum_{k=0}^{N\!-\!1}\sum_{l=0}^{N\!-\!1}u_{k,l}\omega_N^{-mk}\omega_N^{-nl }.
$$
Montrer que la transformation ainsi d{é}finie est ``s{é}parable'', c'est-à-dire que le passage des $u_{k,l}$ aux
$\tilde u_{m,n}$ s'effectue par deux TFDs {à} une dimension successives.
\fexer 
\newpage
 \dexer Quelques propriétés de la TFD 
\hfill
\newline\newline
Il est commode pour la manipulation des formules de considérer $u=(u_k)_k \in \CC^N$ pour ce qu'il est en fait dans la pratique ($u_k=u(ka/N)$): une suite périodique, de période $N$, que l'on peut voir comme une suite $u_k$ avec $k\in \ZZ$. La formule de la TFD donnant les $\tilde u_n$ est également périodique de période $N$. On peut donc aussi écrire $\tilde u_n$ avec $n\in \ZZ$. Enfin, dans les formules donnant la TFD et son inverse, la sommation peut être effectuée sur n'importe quel ensemble de $N$ entiers consécutifs. \\
Avec cette convention, on suppose que $u=(u_k)_k \stackrel{\mbox{TFD}}{\longrightarrow} \tilde{u}=(\tilde{u}_n)_n$. \\
1) Montrer que $(u_{-k})_k\longrightarrow (\tilde{u}_{-n})_n$, $(\overline{u_k})_k \longrightarrow (\overline{\tilde{u}_{-n}})_n$ et que $(\overline{{u}_{-k}})_k\longrightarrow (\overline{\tilde{u}_{n}})_n$.\\
2) On dira que la suite $(u_k)_k$ est paire (resp. impaire) si $\forall k \in \ZZ$, $u_{-k}=u_k$ (resp. $u_{-k}=-u_k$).\\
Montrer que $(u_k)_k$ est paire (resp. impaire) $\Leftrightarrow $ $(\tilde{u}_{n})_n$ est paire (resp. impaire).\\
3) Montrer que $(u_k)_k$ est réelle et paire $\Leftrightarrow $ $(\tilde{u}_{n})_n$ est réelle et paire.\\
4) Montrer que $(u_k)_k$ est réelle et impaire $\Leftrightarrow $ $(\tilde{u}_{n})_n$ est imaginaire pure et impaire.
5) Soient $x=(x_k)_k$ et $(y_k)_k$ deux suites périodiques de période $N$ et $(\tilde{x}_{n})_n,(\tilde{y}_{n})_n$ leur TFD. \\
On considère la suite $z=(z_k)_k$ définie par convolution circulaire :
 $$z_k= \sum_{q=0}^{N-1} x_q y_{k-q}.$$
Calculer sa TFD en fonction des TFD $(\tilde{x}_{n})_n$ et $(\tilde{y}_{n})_n$.
 \fexer 
 \dexer FFT 
\hfill
\newline\newline
On suppose que $N=2^{n}$ avec $n\geq 1$. Appelons ``calcul d'ordre $N$'' l'{é}valuation d'un polyn{\^o}me de degr{é} $N\!-\!1$ aux racines
$N$-i{è}mes de l'unit{é}. Et notons $M(n)$ le nombre d'op{é}rations (additions et multiplications) demand{é}es par ce
calcul.

On se donne un polyn{\^o}me $P(X)=\displaystyle{\sum_{k=0}^{N\!-\!1}}a_kX^k$. On pose
$Q(X)=\displaystyle{\sum_{k=0}^{\frac N2-1}}a_{2k}X^k$ et $R(X)=\displaystyle{\sum_{k=0}^{\frac N2-1}}a_{2k+1}X^k.$
Alors $$(\star)\qquad
P(\omega_N^k)=Q\left(\left(\omega_N^k\right)^2\right)+\omega_N^kR\left(\left(\omega_N^k\right )^2
\right).$$
Or, si $N$ est pair, les $\left(\omega_N^k\right)^2$ sont exactement les racines d'ordre
$\frac{N}{2}$ de l'unit{é}. Il suffit donc d'{é}valuer les deux polyn{\^o}mes $Q$ et $R$ aux racines d'ordre
$\frac{N}{2}$ de l'unit{é}. C'est donc un "calcul d'ordre $\frac{N}{2}$", nécessitant $M(n-1)$ opérations. \\ \\
Montrer que $M(n) \leq n2^{n+2}=4N\log_2N$ additions et multiplications.
%On a donc, en tenant compte des additions et
%multiplications demand{é}es par $(\star)$,
%$$T(N)=2T\left(\frac{N}{2}\right)+2N.$$
%Démontrer la relation $T(N)=\mathcal{O}(N\log(N))$.
\fexer 
\dexer Zoom 2D (voir poly page 109-110)
\hfill
\newline\newline
..."Nous pr{é}sentons une m{é}thode d'interpolation reposant sur une extension de la TFD d'un signal ou d'une image. Nous
d{é}taillons la m{é}thode, dite du ``prolongement par des zéros (``zéro-padding''), en une dimension, le principe se
g{é}n{é}ralisant sans mal pour une image. Comme pr{é}c{é}demment, consid{è}rons des échantillons $u_k$, $k$ variant de
0 {à} $N\!-\!1$, et $\tilde{u}_n = \frac{1}{N}\sum_{k=0}^{N-1}u_{k}\omega_N^{-kn}$. On suppose que N
est pair et que l'on veut zoomer d'un facteur 2, c'est {à} dire que l'on veut construire un signal de taille deux fois
plus grande (avec deux fois plus d'échantillons) que le signal de d{é}part. On d{é}finit un nouveau signal $v$, de
taille $2N$ comme {é}tant la TFD inverse de $\tilde {v}$, donn{é} par
$$ \tilde{v}_n =  \tilde u_n \; \hbox { si } -\frac N2\leq n\leq \frac N2-1,\;\; \tilde v_n=0
\hbox{
 si  } n\in[-N, -\frac N2-1]\cup  [\frac N2, N-1].
$$
Proposition 1D: On peut facilement vérifier que le signal $v$ dont la TFD est donn{é}e par la formule ci-dessus v{é}rifie  $v_{2k}=u_k$, pour $k=0, ...,N\!-\!1$.\\ \\
La m{é}thode se g{é}n{é}ralise aux cas des images. \\Consid{é}rons une image num{é}rique $(u_{k,l})_{0\leq k,l\leq N-1}$. Nous
d{é}finissons une image zoom{é}e $\left(v_{i,j}\right)_{i,j=0,\;...,\; 2N\!-\!1}$ comme {é}tant la transform{é}e de
Fourier discr{è}te inverse de $\tilde v_{i,j}$ définie pour $i,j=-N,\;...,\;N\!-\!1$ par
$$
 \tilde{v}_{m,n} = \tilde u_{m,n} \hbox{  si  } -\frac N2\leq m, n\leq \frac N2-1, \;\; \tilde
v_{m,n}=0
 \hbox {  sinon}.
$$
 Ecrire la proposition 2D correspondante et démontrer-la. 
\fexer 
\newpage
{\bf Corrigé:}  
\dexo
\hfill \newline
Rappel: Formule des trapèzes\\
Soit $[\alpha,\beta] \subset \RR$ et soit $\Delta = \{\alpha=\alpha_0<...<\alpha_{k}=\beta \}$ une sudivision de $[\alpha,\beta]$ avec $h_i=\alpha_{i+1}-\alpha_{i}$, $i=0,k-1$. La formule des trapèzes donne \\
$$\int_{\alpha}^{\beta} f dx \approx T_k(f) = \sum_{i=0}^{k-1} \frac{h_i}{2} (f(\alpha_i)
+ f(\alpha_{i+1})).$$ 
Ici, avec $h=\frac{a}{N}$, $\alpha_j=jh$, on obtient donc ($u$ est continue et $u(0)=u(a)$)
\begin{eqnarray*}
c_n(u)&=&\frac{1}{a} \int_0^a u(x) e^{( \frac{-2i\pi nx}{a})}dx,\\
      &\approx&\frac{1}{N} \left( \frac{u(0)}{2}+ u(\frac{a}{N})e^{-\frac{2i\pi n}{N}}+...+u((N-1)\frac{a}{N})e^{-\frac{2i\pi n(N-1)}{N}}+\frac{u(0)}{2}\right),\\
      &\approx& \tilde{u}_{n},
\end{eqnarray*}  
où $u_k=u(k\frac{a}{N})$ dans la formule de la TFD.    
\fexo
\dexo
\hfill \newline
Comme $u_k \in \RR$, par définition de la TFD, on a
$$\tilde{u}_0= \frac{1}{N} \sum_{k=0}^{N-1} u_k \in \RR,$$
$$\tilde{u}_{-\frac{N}{2}}= \frac{1}{N} \sum_{k=0}^{N-1} u_k\omega_N^{k\frac{N}{2}}= \frac{1}{N} \sum_{k=0}^{N-1} u_k(-1)^{k} \in \RR.$$
Enfin, pour $n=1...\frac N2-1$, on a
$$\tilde{u}_{-n}=\frac{1}{N} \sum_{k=0}^{N-1}  \omega_N^{nk}=\frac{1}{N} \sum_{k=0}^{N-1} \overline{u_k}\overline{\omega_N^{-nk} }= \overline{\tilde{u}_{n}}.$$
\fexo
\dexo
\hfill \newline
On a
\begin{eqnarray*}
\tilde{u}_{m,n}&=&\frac{1}{N^{2}} \sum_{k=0}^{N-1}\sum_{l=0}^{N-1} u_{k,l} \omega_N^{-mk}\omega_N^{-nl},\\
               &=&\frac{1}{N} \sum_{k=0}^{N-1}\omega_N^{-mk}\left[\frac{1}{N} \sum_{l=0}^{N-1}u_{k,l}\omega_N^{-nl} \right].
\end{eqnarray*}
Le terme entre crochets est une "TFD 1D d'une colonne", il reste ensuite une "TFD 1D d'une ligne". Finalement, ce cacul se fait avec $N$ TFD en colonne et $N$ TFD en ligne.
\fexo
\dexo
\hfill \newline
1) Notons $u^{1}=(u^{1}_{n})_n$ la TFD de $(u_{-n})_n$. Alors$$
%\begin{eqnarray*}
u^{1}_{n} = \frac{1}{N} \sum_{k=0}^{N-1}u_{-k} \omega_N^{-nk}=\frac{1}{N} \sum_{k=-N+1}^{0}u_k \omega_N^{nk}=\frac{1}{N} \sum_{k=0}^{N-1}u_k \omega_N^{nk}=\tilde{u}_{-n},$$
%\end{eqnarray*}
car $u_{k+N}=u_k$ pour tout $k$.
Si $u^{\ast}=(u^{\ast}_{n})_n$ est la TFD de $(\overline{u_k})_k$, alors
$$u^{\ast}_{n}=\frac{1}{N} \sum_{k=0}^{N-1} \overline{u_k} \omega_N^{-nk}=\overline{\tilde{u}_{-n}}.$$
Donc, $(\overline{u_{-k}})_k \rightarrow (\overline{\tilde{u}_{+n}})_n$.\\
2) C'est une conséquence directe de 1).\\
3) Si $(u_k)_k$ est réelle et paire, alors $(\tilde{u}_{n})_n$ est paire par 2). De plus pour tout $k$, $u_k-\overline{u_k}=0$ $\Rightarrow$ $\tilde{u}_{n}-\overline{\tilde{u}_{-n}}=0=\tilde{u}_{n}-\overline{\tilde{u}_{n}}$. Donc $(\tilde{u}_{n})_n$ est réelle. Et réciproquement.\\
4) Si $(u_k)_k$ est réelle et impaire, alors $(\tilde{u}_{n})_n$ est impaire par 2). De plus pour tout $k$, 
$u_k-\overline{u_k}=0$ $\Rightarrow$ $\tilde{u}_{n}-\overline{\tilde{u}_{-n}}=0=\tilde{u}_{n}+\overline{\tilde{u}_{n}}$. D'où, $(\tilde{u}_{n})_n$ est imaginaire pure. Et réciproquement.\\
5) On a par définition
\begin{eqnarray*}
\tilde{z}_{n} &=& \frac{1}{N} \sum_{k=0}^{N-1}z_{k} \omega_N^{-nk},\\
              &=& \frac{1}{N} \sum_{k=0}^{N-1} \sum_{q=0}^{N-1} x_q y_{k-q}\omega_N^{-nk},\\
              &=& \frac{1}{N} \sum_{q=0}^{N-1} x_q \omega_N^{-nq} \sum_{k=0}^{N-1} y_{k-q}\omega_N^{-n(k-q)},\\
              &=& \tilde{x}_{n}\times N\tilde{y}_{n}.
\end{eqnarray*}
\fexo
\dexo
\hfill \newline
On démontre que $M(n)\leq n2^{n+2}=4N\log_2N$ par récurrence sur $n$. Si $n=1$, il s'agit d'évaluer $P(1)$ et $P(\omega_2)$ avec $P$ de degré $\leq 1$. On a evidemment $M(1)=3\leq 1\times 2^{1+2}$. Supposons l'inégalité vraie en $n-1$ et démontrons-la pour $n$. 
Les calculs à l'ordre $\frac{N}{2}$ étant faits pour $Q$ et $R$ (ce qui demande $2M(n-1)$ opérations), la formule $(\star)$ permet de calculer chaque $P(\omega^{k}_{N})$ avec $2$ opérations. On en déduit que $M(n)=2M(n-1)+2N$. \\Donc $M(n)\leq 2(n-1)2^{n+1}+2.2^{n}=2^{n+1}(2n-1)\leq n2^{n+2}$.
\fexo
\dexo
\hfill \newline
Montrons que $v_{2k,2l}=u_{k,l}$ pour $k,l=0,...,N-1$. En effet,
$$v_{2k,2l}=\sum_{m=-N}^{N-1}\sum_{n=-N}^{N-1} \tilde{v}_{m,n}  \omega_{2N}^{2mk}\omega_{2N}^{2nl}=\sum_{m=-\frac{N}{2}}^{\frac{N}{2}-1}\sum_{n=-\frac{N}{2}}^{\frac{N}{2}-1} \tilde{u}_{m,n}  \omega_{N}^{mk}\omega_{N}^{nl}=u_{k,l}.$$
%car $\omega_{2N}^{2nl}=\omega_{N}^{nl}$.
\fexo
 \end{document}