MATH529: L16 Finite Fourier transform, FFT

Overview

• Finite Fourier transform

• Fast Fourier transform

Finite Fourier transform

• Finite Fourier transforms arise for functions defined on a finite domain

  ${\displaystyle \begin{array}{cc}\mathrm{Infinite}\mathrm{domain}& \mathrm{Finite}\mathrm{domain}\\ f:ℝ\to ℝ& f:[0,p]\to ℝ\\ F_c\left(\alpha \right)={ℱ}_c\left\{f\right\}=\underset{0}{\overset{\infty }{\int }}f\left(x\right)\cos \alpha xdx,& F_c\left(n\right)=\underset{0}{\overset{p}{\int }}f\left(x\right)\cos \frac{n\pi }{p}xdx\\ f\left(x\right)={ℱ}_c^{-1}\left\{F_c\right\}=\frac{2}{\pi }\underset{0}{\overset{\infty }{\int }}{F}_c\left(\alpha \right)\cos \alpha xd\alpha & f\left(x\right)={ℱ}_c^{-1}\left\{F_c\right\}=\\ & \frac{2}{p}[\frac{1}{2}F\left(0\right)+\sum _{n=1}^{\infty }F\left(n\right)\cos \frac{n\pi }{p}x]\\ F_s\left(\alpha \right)={ℱ}_c\left\{f\right\}=\underset{0}{\overset{\infty }{\int }}f\left(x\right)\sin \alpha xdx,& F_s\left(n\right)=\underset{0}{\overset{p}{\int }}f\left(x\right)\sin \frac{n\pi }{p}xdx\\ f\left(x\right)={ℱ}_s^{-1}\left\{F_s\right\}=\frac{2}{\pi }\underset{0}{\overset{\infty }{\int }}{F}_s\left(\alpha \right)\sin \alpha xd\alpha & f\left(x\right)={ℱ}_s^{-1}\left\{F_s\right\}=\\ & \frac{2}{p}\sum _{n=1}^{\infty }F\left(n\right)\sin \frac{n\pi }{p}x\end{array}}$

Comparison to trigonometric series

• Recall $f:ℝ\to ℝ$, $f$ periodic $f(t+T)=f\left(t\right)$

  ${\displaystyle f\left(t\right)=\frac{1}{2}{A}_0+\sum _{n=1}^{\infty }{A}_n\cos 2\pi n\frac{t}{T}+B_n\sin 2\pi n\frac{t}{T}}$ ${\displaystyle A_n=(f,\cos 2\pi n\frac{t}{T}),B_n=(f,\sin 2\pi n\frac{t}{T})}$

• $f$ was defined with a finite number of points of discontinuity $\forall t$

  ${\displaystyle {lim}_{N\to \infty }{T}_n\left(t\right)={lim}_{N\to \infty }\frac{1}{2}{A}_0+\sum _{n=1}^N{A}_n\cos 2\pi n\frac{t}{T}+B_n\sin 2\pi n\frac{t}{T}=f\left(t\right)}$

• What happens at a discontinuity, $t_{\ast }$?

  ${\displaystyle T_n\left(t_{\ast }\right)=\frac{1}{2}(f\left(t_{\ast }^{-}\right)+f\left(t_{\ast }^{+}\right))}$

Finite transforms of derivatives

• Having defined

  ${\displaystyle F_c\left(n\right)=\underset{0}{\overset{p}{\int }}f\left(x\right)\cos \frac{n\pi }{p}xdx}$

• Compute transform of second derivative

  ${\displaystyle {ℱ}_{\mathrm{cn}}\left(f^{\text{'}\text{'}}\right)=f^{\text{'}}\left(p\right){(-1)}^n-f^{\text{'}}\left(0\right)-{\left(\frac{n\pi }{p}\right)}^2{F}_c\left(n\right)}$

• Compare to inifinite-domain Fourier transform

  ${\displaystyle F\left(\alpha \right)=ℱ\left\{f\right\}=\underset{-\infty }{\overset{\infty }{\int }}f\left(x\right)e^{i\alpha x}dx,ℱ\left\{f^{\text{'}\text{'}}\right\}=-{\alpha }^{2}F\left(\alpha \right)}$