# Fourier Analysis
## basic concept

> __fouier series:__ break down a perodic function to a collection of perodic functions whose period differ from each other.
> __fouier integral:__ break down a non-perodic function to a integral form.

the characteristic of perodic function:
1. assume the period of $f(x)$ is $T$, $kT, k\in\Bbb Z^+$ are also the period of $f(x)$
2. consider two period function, $f(x), g(x)$, whose period are both $T$. the linear combination $h(x)=k_1f(x)+k_2g(x), k_1,k_2\in\Bbb R$ has also a minimum period $T$.
3. assume the period of $f(x)$ is $T$, the period of $f(mT)$ is $T/m$
4. assume two period function $f(x),g(x)$ with period $T_f, T_g$ respectively. the linear combination $h(x)$ has a minimum period $\text{lcm}(T_f, T_g)$

the characteristic of tri-function
1. $\int^\pi_{-\pi} \sin(nx)dx = 0,n\in\Bbb N$
2. $\int^\pi_{-\pi} \cos(nx)dx = 0,n\neq0$
3. $\int^\pi_{-\pi} \sin(nx)\sin(mx) dx=\int^\pi_{-\pi}\frac12(\cos(n-m)x-\cos(n+m)x)dx=\\\begin{cases}0, &n\neq m\\\pi, &n=m\end{cases}$
4. $\int^\pi_{-\pi} \cos(nx)\cos(mx) dx=\\\begin{cases}0, &n\neq m\\\pi, &n=m\end{cases}$
5. $\int^\pi_{-\pi} \sin(nx)\cos(mx) dx=0$ (orthogonality)

__EXERCISE:__
please determine whether the following functions belong to periodic function. if yes, please find the period.
1. $8\sin(2x)+17\cos(10x)$
2. $\cos(n\pi x/l)$
3. $10\cdot e^{-x}+20\cos(5x)$
4. $\sin(x) \cos(x)$

ans:
1. $\pi$
2. $2l/n$
3. not periodic
4. $\pi$

## fourier coefficients
$f(x)=a_0+\sum^{\infty}_{n=1}(a_n\cos(nx)+b_n\sin(nx))$.

$a_0=\frac1{2\pi}\int^\pi_{-\pi}f(x)dx$
$a_n=\frac1{\pi}\int^\pi_{-\pi}f(x)\cos(nx)dx$
$b_n=\frac1{\pi}\int^\pi_{-\pi}f(x)\sin(nx)dx$

notice that the period of the tri. polynomial above is $2\pi$, since the period is $\text{lcm}(2\pi/1,2\pi/2,2\pi/3,...) = 2\pi$.
we want to know if there's a periodic function whose period is $T$. what is the coefficients of tri. polynomial?
obviously, the internal argument of $cos$ and $sin$ shall be $2\pi nx/T$, so that, the period of the polynomial is $lcm(\frac{2\pi T}{2\pi\cdot1},\frac{2\pi T}{2\pi\cdot2},\frac{2\pi T}{2\pi\cdot3},...)=T$.
so the desired function will be $f(x)=a_0+\sum_{n=1}^{\infty}(a_n\cos(2\pi nx/T)+b_n\sin(2\pi nx/T))$
use the same trick to determine the coefficients:
$a_0 = \frac1T\int_{T}f(x)dx$
$a_n = \frac2T\int_{T}f(x)\cos(2\pi nx/T)dx$
$b_n = \frac2T\int_{T}f(x)\sin(2\pi nx/T)dx$

__!! note that fourier series on the jump point $a$ are defined as $\frac12(f(a^-)+f(a^+))$__

look page 11 of this [pdf](http://faculty.olin.edu/josborne1/EmathII/FourierChapterCalculusAModernApproachDrJeffKnisley.pdf).

## half range expansion
in some condition, we can use just the half period to get the fourier coefficient, this technique is called __half range expansion__.

for example, $f(x)$ is a period function whose period is $T=2l$, and the value of $f(x),x\in[0,l]$ is known.
- if $f(x)$ is an even function:
$f(x) = a_0+\sum^\infty_{n=0}(a_n\cos(2\pi nx/T) + 0\cdot \sin(2\pi nx/T))$
$a_0 = \frac1T\int_Tf(x)dx = \frac2T\int_0^lf(x)dx$
$a_n = \frac2T\int_Tf(x)\cos(2\pi nx/T)dx =\frac4T\int_0^lf(x)\cos(2\pi nx/T)dx$
- if $f(x)$ is a odd function:
$f(x)=a_0+\sum^\infty_{n=0}(0\cdot \cos(2\pi nx/T)+b_n\sin(2\pi nx/T))$
$a_0 = 0$
$b_n = \frac2T\int_Tf(x)\sin(2\pi nx/T)dx=\frac4T\int_0^lf(x)\sin(2\pi nx/T)dx$

__EXERCISE:__
please find the fourier cosine series expansion of $sin\,x$ when $0\leq x\leq \pi$.

ans:
$f(x)=a_0+\sum^\infty_{i=1}a_n\cos(2n\pi x/T)$

$a_0=\frac1T\int_Tf(x)dx=\frac2{2\pi}\int^\pi_0\sin(x)dx=\frac2\pi$
$\begin{align}a_n&=\frac2T\int_Tf(x)\cos(2n\pi x/T)dx\\&=\frac2\pi\int^\pi_0\sin(x)\cos(nx)dx\\&=\frac1\pi\int^\pi_0[\sin(1+n)x+\sin(1-n)x]dx\\&=\begin{cases}0&,\text{n is odd}\\\frac4{\pi(1-n^2)}&,\text{otherwise}\end{cases}\end{align}$

$f(x)=\frac2\pi+\sum^\infty_{i=1}\frac{4}{\pi(1-4n^2)}\cos(2nx)$

__EXERCISE:__
please find the fourier sine series expansion of $cos\,x$ when $0\leq x\leq \pi$.

ans:
$f(x)=a_0+\sum^{\infty}_{i=1}b_n\sin(2n\pi x/T)$

$a_0=0$
$\begin{align}b_n&=\frac1\pi\int^\pi_{-\pi}f(x)\sin(nx)dx\\&=\frac1\pi\int^\pi_0[\sin(n-1)x+\sin(n+1)x]dx\\&=\begin{cases}0&,\text{n is odd}\\\frac{4n}{\pi(n^2-1)}&,\text{otherwise}\end{cases}\end{align}$

$f(x)=\sum^\infty_{i=1}\frac{8n}{\pi(4n^2-1)}\sin(2nx)$

__EXERCISE:__
please cosider a function $f(x)=\frac{3}{2}+\frac{3}{4}cos(x)+\frac25\sin(x)$.
if this function is defined only at $0\leq x \leq \pi$, please find the fourier cosine series expansion of $f(x)$.

ans:
$f(x)=a_0+\sum^\infty_{n=1}a_n\cos(nx)$

$a_0=\frac1{2\pi}\int^\pi_{-\pi}f(x)dx=\frac1\pi\int^\pi_0f(x)dx=\frac32+\frac4{5\pi}$
$\begin{align}a_n&=\frac1\pi\int^\pi_{-\pi}f(x)\cos(nx)dx\\&=\frac2\pi\int^\pi_0[\frac{3}{2}+\frac{3}{4}\cos(x)+\frac25\sin(x)]\cos(nx)dx\\&=\frac2\pi[\frac{3}{2}\int^\pi_0cos(nx)dx+\frac{3}{4}\int^\pi_0\cos(x)\cos(nx)dx+\frac25\int^\pi_0\sin(x)\cos(nx)dx]\end{align}$

$\int^\pi_0\cos(nx)dx=0$
$\int^\pi_0\cos(x)\cos(nx)dx=\begin{cases}\pi/2&,n=1\\0&,\text{otherwise}\end{cases}$
$\int^\pi_0\sin(x)\cos(nx)dx=\frac12\int^\pi_0[\sin(1+n)x+\sin(1-n)x]dx=\begin{cases}0&,\text{n is odd}\\\frac2{1-n^2}&,\text{otherwise}\end{cases}$

$a_1=\frac34$
$a_n,n\geq 2=\begin{cases}0&,\text{n is odd}\\\frac8{5\pi(1-n^2)}&,\text{otherwise}\end{cases}$

$f(x)=\frac32+\frac4{5\pi}+\frac34\cos(x)+\sum^\infty_{n=1}\frac{8}{5\pi(1-4n^2)}\cos(2nx)$

## fourier integral
$f(x)=\frac1T\int_Tf(x)dx+\frac{2}{T}\sum^{\infty}_{n=1}\int_Tf(x)\cos(\omega_nx)dx\,\cos(\omega_nx)+\int_Tf(x)\sin(\omega_nx)dx\,\sin(\omega_nx)$
where $\omega_n=\frac{2n\pi}{T}=2n\pi f$, and $\Delta\omega=\frac{2\pi}{T}=\omega_{n+1}-\omega_n$.

rewrite it, $f(x)=\frac1T\int_Tf(x)dx+\frac{1}{\pi}\frac{2\pi}{T}(\sum^{\infty}_{n=1}\int_Tf(x)\cos(\omega_nx)dx\,\cos(\omega_nx)+\int_Tf(x)\sin(\omega_nx)dx\,\sin(\omega_nx))$

let $\lim_{T\to\infty}$
$f(x)=\frac1T\int_{-\infty}^{\infty}f(x)dx+\frac{1}{\pi}\int_0^\infty(\int_{-\infty}^{\infty}f(x)\cos(\omega x)dx\,\cos(\omega x)+\int_{-\infty}^{\infty}f(x)\sin(\omega x)dx\,\sin(\omega x))d\omega$

let $\int_{-\infty}^{\infty}f(x)\cos(\omega x)dx=A(\omega)$ and $\int_{-\infty}^{\infty}f(x)\sin(\omega x)dx=B(\omega)$
and since $\lim_{T\to\infty}\frac1T\int^{\infty}_{-\infty}f(x)dx=0$

$f(x)=\frac{1}{\pi}\int_0^\infty(A(\omega)\,\cos(\omega x)+B(\omega)\,\sin(\omega x))d\omega$

__EXAMPLE:__
$f(x)=\begin{cases}1&,x\in[-1,1]\\0&,\text{else}\end{cases}$
what is its fourier integral?

ans:
$A(\omega)=\int^\infty_{-\infty}f(x)\cos(\omega x)dx=2\int^1_01\cdot \cos(\omega x)dx=\frac{2\sin(\omega)}{\omega}$
$B(\omega)=\int^\infty_{-\infty}f(x)\sin(\omega x)dx=0$

__EXAMPLE:__
$f(x)=\begin{cases}x&,|x|\leq1\\0&,|x|>1\end{cases}$
what it its fourier integral?

ans:
$A(\omega)=\int^{1}_{-1}f(x)\cos(\omega x)dx=0$
$B(\omega)=2\int^{1}_{0}f(x)\sin(\omega x)dx=2\int^{1}_{0}x\cdot \sin(\omega x)dx=\frac{2\sin(\omega)-2\omega \cos(\omega)}{\omega^2}$

__EXAMPLE:__
$f(x)=e^{-3|x|}$. find its fourier integral.

ans:
$A(\omega)=\int^\infty_{-\infty}f(x)\cos(\omega x)dx$
$B(\omega)=\int^\infty_{-\infty}f(x)\sin(\omega x)dx$

$\mathscr L[f(x)]=\int^\infty_0f(t)e^{-st}dt$
$\mathscr L[\cos(at)]=\frac{s}{s^2+a^2}$
$\mathscr L[\sin(at)]=\frac{a}{s^2+a^2}$

$A(\omega)=\frac{6}{9+\omega^2}$
$B(\omega)=0$

__EXAMPLE:__
$f(x)=e^{-a|x|},a>0$. find
1. fourier integral
2. calculate $\int^\infty_0 \cos(2x)/(x^2+4)dx$

ans:

1. $A(\omega)=\int^\infty_{-\infty}f(x)\cos(\omega x)dx=\int^\infty_{-\infty}e^{-a|x|}\cos(\omega x)dx=2\int^\infty_0e^{-ax}\cos(\omega x)dx\\=2a/(a^2+\omega^2)$
$B(\omega)=\int^\infty_{-\infty}f(x)\sin(\omega x)dx=\int^\infty_{-\infty}e^{-a|x|}\sin(\omega x)dx=0$

2. $f(x)=\frac1{\pi}\int^\infty_0A(\omega)\cos(\omega x)d\omega=\frac1{\pi}\int^\infty_0\frac{2a}{a^2+\omega^2}\cos(\omega x)d\omega$, let $a=2$, $f(x)=\frac{1}{\pi}\int^\infty_0\frac{4}{4+\omega^2}\cos(\omega x)d\omega$, and so $f(2)=\frac1\pi\int^\infty_0\frac{4}{4+\omega^2}\cos(2\omega)d\omega=e^{-2|2|}=e^{-4}$
$\int^\infty_0\frac{1}{4+\omega^2}\cos(2\omega)d\omega=\frac\pi{4}e^{-4}$

__EXAMPLE:__
if $f(x)=\begin{cases}e^{-2x}&,x>0\\0&,x<0\end{cases}$
please find the fourier integral.

ans:
$A(\omega)=\int^\infty_{-\infty}f(x)\cos(\omega x)dx=\int^\infty_0e^{-2x}\cos(\omega x)=2/(4+\omega^2)$
$B(\omega)=\int^\infty_{-\infty}f(x)\sin(\omega x)dx=\int^\infty_0e^{-2x}\sin(\omega x)=\omega/(4+\omega^2)$

__EXERCISE:__
please use fourier integral representation to show that $\int^\infty_0\frac{\cos(\pi\omega/2)\cos(\omega x)}{1-\omega^2}d\omega=\begin{cases}\frac{\pi}{2}\cos(x)&,|x|<\pi/2\\0&,|x|>\pi/2\end{cases}$

ans:
let $f(x)=\begin{cases}\frac{\pi}{2}\cos(x)&,|x|<\pi/2\\0&,|x|>\pi/2\end{cases}$

$\begin{align}A(\omega)&=\frac\pi2\int^\frac\pi2_{-\frac\pi2} \cos(x)\cos(\omega x)dx\\&=\frac\pi4\int^\frac\pi2_{-\frac\pi2}[\cos(\omega+1)x+\cos(\omega-1)x]dx\\&=\frac\pi2[\frac1{\omega +1}\sin(\omega+1)x+\frac1{\omega -1}\sin(\omega-1)x]^{\pi/2}_0\\&=\frac\pi2[\frac1{\omega +1}\sin(\omega+1)\frac\pi2+\frac1{\omega -1}\sin(\omega-1)\frac\pi2]\\&=\frac\pi2\frac{(\omega -1)\sin(\omega+1)\frac\pi2+(\omega+1)\sin(\omega-1)\frac\pi2}{\omega^2-1}\\&=\frac\pi2\frac{\omega \sin(\omega+1)\frac\pi2-\sin(\omega+1)\frac\pi2+\omega \sin(\omega-1)\frac\pi2+\sin(\omega-1)\frac\pi2}{\omega^2-1}\\&=\frac\pi2\frac{\omega(2\sin(\omega\pi/2)\cos(\pi/2))+2\sin(-\pi/2)\cos(\pi\omega/2)}{\omega^2-1}\\&=\frac{\pi \cos(\pi\omega/2)}{1-\omega^2}\end{align}$

$f(x)=\frac1\pi\int^{\infty}_{0}A(\omega)\cos(\omega x)d\omega=\int^\infty_0\frac{\cos(\pi\omega/2)}{1-\omega^2}\cos(\omega x)d\omega=\begin{cases}\frac{\pi}{2}\cos(x)&,|x|<\pi/2\\0&,|x|>\pi/2\end{cases}$

__EXERCISE:__
a function $f(x)$ is defined as $f(x)=\begin{cases}1&,0\leq x\leq 2\\0&,\rm{otherwise}\end{cases}$
1. please find the fourier integral representation
2. please use the result in 1. to find $\int ^\infty_0\frac1\omega\sin\omega d\omega$

ans:
$A(\omega)=\int^2_0cos(\omega x)dx=\frac1\omega sin(\omega x)|^2_0=\frac{sin(2\omega)}{\omega}$
$B(\omega)=\int^2_0sin(\omega x)dx=-\frac1\omega cos(\omega x)|^2_0=\frac{-cos(2\omega)-1}{\omega}$

if not on $x=0$ and $x=2$:

$\begin{align}f(x)&=\frac1\pi\int^\infty_0\frac{\sin(2\omega)}{\omega}\cos(\omega x)+\frac{-\cos(2\omega)-1}{\omega}\sin(\omega x)d\omega\\&=\frac1\pi\int^\infty_0\frac1{\omega}(\sin(2\omega -\omega x)-\sin(\omega x))d\omega\end{align}$

if on $x=0$ and $x=2$:
$f(x)=1/2$

so $f(x)=\begin{cases}1/2&,\text{x=0 or x=2}\\\frac1\pi\int^\infty_0\frac1{\omega}(\sin(2\omega -\omega x)-\sin(\omega x))d\omega&,\text{otherwise}\end{cases}$

$f(0)=\frac12=\frac1\pi\int^\infty_0\frac1{\omega}\sin(2\omega)d\omega$

let $u=2\omega$, $\frac1\pi\int^\infty_0\frac1{\omega}\sin(2\omega)d\omega=\frac1\pi\int^\infty_0\frac2{u}\sin(u)du/2=\frac1\pi\int^\infty_0\frac1{u}\sin(u)du$

$f(0)=1/2=\frac1\pi\int^\infty_0\frac1{u}\sin(u)du=\int ^\infty_0\frac1\omega\sin\omega d\omega$

__EXERCISE:__
you have one function $f(x)=x^2$ when $0\leq x\leq 1$. please determine the result of its fourier sine integral.

ans:
$B(\omega)=\int^\infty_{-\infty}f(x)\sin(\omega x)dx=\int^1_{-1}f(x)\sin(\omega x)dx=2\int^1_0x^2\sin(\omega x)\\=\frac2{\omega^3}(-\omega^2cos(\omega)+2\omega \sin(\omega)+2\cos(\omega)-2)$

$f(x)=\frac1\pi\int^\infty_0\frac2{\omega^3}(-\omega^2\cos(\omega)+2\omega \sin(\omega)+2\cos(\omega)-2)\sin(\omega x)d\omega$

## taylor and maclaurin series


__EXAMPLE:__
find the 4-th Maclaurin series of $\sqrt{x+1}$ and find its value at $\sqrt{0.9}$. afterward, show the approximation error in this case.

ans:
let $f(x)=\sqrt{x+1}$, $f^{(1)}=\frac12(x+1)^{-\frac12}$, $f^{(2)}=-\frac14(x+1)^{-\frac32}$, $f^{(3)}=\frac38(x+1)^{-\frac52}$, $f^{(4)}=-\frac{15}{16}(x+1)^{-\frac72}$

so the 4-th Maclaurin series of $f(x)$ is $F(x)=1+\frac{x}2-\frac{x^2}8+\frac{3x^3}{48}-\frac{15x^4}{384}$.
the value of $F(-0.1)=0.9487$

the approximation error is $\frac{105}{32}\frac1{5!}(-0.1)^5\approx -2.734375\times10^{-7}$

## fourier transform

$$\begin{align}f(x)&=\frac1\pi\int^{\infty}_0A(\omega) \cos(\omega x)+B(\omega)\sin(\omega x) d\omega\\&=\frac1\pi\int^{\infty}_0\frac12[A(\omega) (e^{i\omega x}+e^{-i\omega x})+B(\omega) (-i)(e^{i\omega x}-e^{-i\omega x})] d\omega\\&=\frac{1}{2\pi}\int^{\infty}_0A(\omega)e^{i\omega x}+A(\omega)e^{-i\omega x}-iB(\omega)e^{i\omega x}+iB(\omega)e^{-i\omega x}d\omega\\&=\frac{1}{2\pi}\int^{\infty}_0(A(\omega)-iB(\omega))e^{i\omega x}+(A(\omega)+iB(\omega))e^{-i\omega x}d\omega\end{align}$$

let $C(\omega)=A(\omega)-iB(\omega)$. since $A(\omega)$ is even function and $B(\omega)$ is odd function, so $f(x)$ can be rewritten as:
\\$$\begin{align}f(x)&=\frac{1}{2\pi}\int^{\infty}_0C(\omega)e^{i\omega x}+C^{*}(\omega)e^{-i\omega x}d\omega\\&=\frac{1}{2\pi}\int^{\infty}_0C(\omega)e^{i\omega x}+C(-\omega)e^{-i\omega x}d\omega\\&=\frac{1}{2\pi}\int^{\infty}_{-\infty}C(\omega)e^{i\omega x}d\omega\end{align}$$

let $F(\omega)=C(\omega)=A(\omega)-iB(\omega)\\=\int^\infty_{-\infty}f(x)\cos(\omega x)dx-i\int^\infty_{-\infty}f(x)\sin(\omega x)dx\\=\int^\infty_{-\infty}f(x)e^{-i\omega x}dx$

therefore, we can define fourier transform as:
$\mathscr F\{f(x)\} =F(\omega)=\int^{\infty}_{-\infty}f(x)e^{-i\omega x}dx$

$\mathscr F^{-1}\{F(\omega)\}=f(x)=\frac{1}{2\pi}\int^{\infty}_{-\infty}F(\omega) e^{i\omega x}d\omega$

## fourier transform for basic function
__EXAMPLE:__
find $\mathscr F\{f(x)\}$, where $f(x)=e^{-ax}u(x)=e^{-ax}H(x)$.

ans:
$F(\omega)=\frac1{a+i\omega}$

__EXAMPLE:__
find $\mathscr F\{1\}$.

ans:
$F(\omega)=2\pi\delta(\omega)$

__EXAMPLE:__
find $\mathscr F\{e^{-a|x|}\},a>0$.

ans:
$F(\omega)=\frac{2a}{a^2+\omega^2}$

__EXAMPLE:__
find $\mathscr F\{k(u(x+a)-u(x-a))\},a>0$.

ans:
$F(\omega)=\frac{2k}\omega \sin(\omega a)$

__EXAMPLE:__
find $\mathscr F\{\delta(x)\}$.

$\delta=\begin{cases}+\infty&,x=0\\0&,x\neq0\end{cases}$ and $\int^\infty_{-\infty}\delta(x)dx=1$.

![[CWqnZdJ.png]]

note that $\delta(x)$ __is not a normal function__. it's a [distribution](https://zh.wikipedia.org/wiki/%E5%88%86%E5%B8%83_(%E6%95%B0%E5%AD%A6%E5%88%86%E6%9E%90)), which can be loosely said that the properties have meanings only when it's measured by other functions, e.g. integral.

ans:
we can calculate $\mathscr F\{\delta(x)\}$ by using

![[z1aJdZz.png]]
and let $\lim_{k\to0,\,a\to0}$.

$\frac1k\int^{a+k}_{a}e^{-i\omega x}dx=\frac1k\frac1{-i\omega}(e^{-i\omega(a+k)}-e^{-i\omega a})=\frac1k\frac1{-i\omega}e^{-i\omega a}(e^{-i\omega k}-1)$

$\lim_{k\to0}\frac1k\frac1{-i\omega}e^{-i\omega a}(e^{-i\omega k}-1)=e^{-i\omega a}\lim_{k\to0}\frac{e^{-i\omega k}-1}{-i\omega k}=({\rm L.H.})e^{-i\omega a}$

and then $\lim_{a\to0}$, $\mathscr F\{\delta(x)\}=1$

__summary:__
$\mathscr F\{e^{-ax}H(x),a>0\}=\frac1{a+i\omega}$
$\mathscr F\{(e^{-a|x|, a>0)}\}=\frac{2a}{a^2+\omega^2}$
$\mathscr F\{H(x+a)-H(x-a),a>0\}=\frac{2}{\omega}sin(\omega a)$
$\mathscr F\{\delta(x)\}=1$
$\mathscr F\{\begin{cases}1-|x|&,-1\leq x\leq1\\0&\text{, otherwise}\end{cases}\}=\frac{2(1-cos\omega)}{\omega^2}$

Note: $\delta(\alpha x)=\frac{\delta(x)}{|\alpha|}$

## basic attribute of fourier transform

1. $\mathscr F\{cf(x)+dg(x)\}=c\mathscr F\{f(x)\}+d\mathscr F\{g(x)\}$
2. $\mathscr F\{f(x-a)\}=e^{-i\omega a}\mathscr F\{f(x)\}$
3. $\mathscr F\{e^{iax}f(x)\}=F(\omega-a)$
4. $\mathscr F\{\mathscr F\{f(x)\}\}=2\pi f(-\omega)$

proof:
$f(x)=\frac1{2\pi}\int^\infty_{-\infty}F(\omega)e^{i\omega x}d\omega$
swap $x$ and $\omega$,
$f(\omega)=\frac1{2\pi}\int^\infty_{-\infty}F(x)e^{i\omega x}dx$
if let $\omega$ be negative,
$f(-\omega)=\frac1{2\pi}\int^\infty_{-\infty}X(t)e^{-i\omega t}dx$
$2\pi f(-\omega)=\mathscr F\{F(x)\}=\mathscr F\{\mathscr F\{f(x)\}|_{\omega=x}\}$

__EXAMPLE:__
$\mathscr F\{1\}=2\pi \delta(\omega)$
$\mathscr F\{\cos(ax)\}=\pi(\delta(\omega-a)+\delta(\omega+a))$
$\mathscr F\{\sin(ax)\}=\frac\pi i(\delta(\omega-a)-\delta(\omega+a))$

__EXAMPLE:__
we know $\mathscr F\{\cos(bx)\}=\pi(\delta(\omega -b)+\delta(\omega +b))$, use the duality property of fourier transform, find $\mathscr F^{-1}\{\cos(b\omega)\}$.

ans:
$\mathscr F\{\pi(\delta(x -b)+\delta(x +b))\}=2\pi cos(-\omega)\iff\frac1{2\pi}\mathscr F\{\pi(\delta(x -b)+\delta(x +b))\}= cos(-b\omega)=cos(b\omega)$
so $\mathscr F^{-1}\{\cos(b\omega)\}=\frac12(\delta(x -b)+\delta(x +b))$

__EXAMPLE:__
repeat the previous example, but find $\mathscr F^{-1}\{sin(b\omega)\}$.

ans:
$\mathscr F^{-1}\{\sin(b\omega)\}=\frac{i}2(\delta(x-a)-\delta(x+a))$

5. $\lim_{x\to\infty} f^{(n)}(x)=0,\forall n\in [0,n-1],\text{ so that }\mathscr F\{f^{(n)}(x)\}=(i\omega)^n F(\omega)$

__EXAMPLE:__
$y'(x)+2y(x)=\delta(x),\lim_{x\to\infty}y(x)=0,y(x)=?$

ans:
$\mathscr F\{y'(x)+2y(x)=\delta(x)\}\Rightarrow(i\omega)Y(\omega)+2Y(\omega)=1$
$Y(\omega)=\frac1{2+i\omega},\mathscr F^{-1}\{Y(\omega)\}=y(x)=e^{-2x}H(x)$

6. $f(x)*\delta(x-a)=f(x-a)$
7. $\mathscr F\{\int^\infty_{-\infty}f^2(x)dx\}=\int^\infty_{-\infty}|F(\omega)|^2d\omega$ (parseval's theorem)

## convolution and modulation
convolution:
$f*g(x)=\int^\infty_{-\infty}f(v)g(x-v)dv$
$\mathscr F\{f*g(x)\}=F(\omega)G(\omega)$

modulation:
$\mathscr F\{f(x)g(x)\}=\frac1{2\pi}F*G(\omega)$

__EXAMPLE:__
$s(x)=e^{-2|x|},p(x)=\cos(3x)$. find $\mathscr F\{s(x)p(x)\}$.

ans:
$\mathscr F\{s(x)p(x)\}=\frac1{2\pi}\mathscr F\{s(x)\}*\mathscr F\{s(x)\}(\omega)=(\frac{4}{4+\omega^2})*(\pi(\delta(\omega-3)+\delta(\omega+3)))\\=\frac\pi{2\pi}(\frac{4}{4+(\omega-3)^2}+\frac{4}{4+(\omega+3)^2})=\frac2{4+(\omega-3)^2}+\frac2{4+(\omega+3)^2}$

## DTFT
continuous time:
$F(\omega)=\int^\infty_{-\infty}f(x)e^{-i\omega x}dx$
$f(x)=\frac1{2\pi}\int^\infty_{-\infty}F(\omega)e^{i\omega x}d\omega$

discrete time:
$X(\omega)=\sum^{\infty}_{n=-\infty}x[n]e^{-i\omega n}$
$X[n]=\frac1{2\pi}\int^{2\pi}_{0}X(\omega)e^{i\omega n}d\omega$

note:
1. $X[n]\in \Bbb R$
2. $X(\omega)\in \Bbb C$
3. $\omega\in[0,2\pi]$

## DFT

DFT: $\hat x[k] = \sum^{N-1}_{n=0}x[n]e^{-i\frac{2\pi}{N}nk}$
IDFT: $x[n]=\frac1N\sum^{N-1}_{k=0}\hat x[k]e^{i\frac{2\pi}{N}nk}$

$\vec{\hat x}=F\cdot\vec x$

$F=\begin{bmatrix}1&1&1&1&1&...\\1&W_N&W_N^2&W_N^3&W_N^4&...\\1&W_N^2&W_N^4&W_N^6&W_N^8&...\\1&W_N^3&W_N^6&W_N^9&W_N^{12}&...\\1&W_N^4&W_N^8&W_N^{12}&W_N^{16}&...\\...\end{bmatrix}$
where $W_N=e^{-i\frac{2\pi}{N}}$

## FFT

let $N=2^r,$

$$\begin{align}\hat x[k]=\sum^{N-1}_{n=0}x[n]e^{-i\frac{2\pi}{N}nk}=\sum_{n\in\text{odd}}x[n]W_N^{nk}+\sum_{n\in\text{even}}x[n]W_N^{nk}=\\\sum_{t=0}^{(N-2)/2}x[2t+1]W_N^{(2t+1)k}+\sum_{t=0}^{(N-2)/2}x[2t]W_N^{2tk}=\\W_N^k\sum_{t=0}^{N/2-1}x[2t+1]W_{N/2}^{tk}+\sum_{t=0}^{N/2-1}x[2t]W_{N/2}^{tk}\end{align}$$

it's equal to do $\text{N/2-FFT}$ on the both odd and even part.

so the complexity is $O(n\log n)$.

| | FFT | DFT |
| ------- | :------------- | -------- |
| __mul__ | $N(\log_2 N-1)$ | $N^2$ |
| __add__ | $N\log_2N$ | $N(N-1)$ |