MATH 414 Lecture 21

From Notes
Jump to navigation Jump to search

« previous | Wednesday, March 5, 2014 | next »


Sampling Theorem

Band-limited function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(t)} (this means that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{f}(\lambda) = 0} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| \lambda \right| \ge \Omega} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(t) = \frac{1}{\sqrt{2\pi}} \, \int_{-\Omega}^\Omega \hat{f}(\omega) \, \mathrm{e}^{i \, \omega \, t} \, \mathrm{d}\omega}
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega} is the angular frequency
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu_{f} = \frac{\Omega}{2\pi}} is the natural frequency (measured in Hertz)
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu_{Ny} = \frac{\Omega}{\pi} = 2\nu_f} is the Nyquist rate (or sampling rate)

Note Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{j \, \pi}{\Omega} = \frac{j}{\nu_{Ny}}}

Theorem. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(t)} is band-limited, with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{f}(\omega) = 0} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| \omega \right| \ge \Omega} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(t) = \sum_{j=-\infty}^\infty f \left( \frac{j \, \pi}{\Omega} \right) \, \frac{\sin{(\Omega \, t - j \, \pi)}}{\Omega \, t - j \, \pi}}

Definition:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(t) = \frac{1}{\sqrt{2\pi}} \, \int_{-\Omega}^\Omega \hat{f}(\omega) \, \mathrm{e}^{i \, \omega \, t} \, \mathrm{d}\omega}

Proof. Expand Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{f}(\omega)} in a Fourier Series on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[ -\Omega, \Omega \right]} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \hat{f}(\omega) &= \sum_{n=-\infty}^\infty c_n \, \mathrm{e}^{\frac{i \, \pi \, n}{\Omega} \, \omega} \\ c_n &= \frac{1}{2\Omega} \, \int_{-\Omega}^{\Omega} \hat{f}(\omega) \, \mathrm{e}^{-\frac{i \, \pi \, n \, \omega}{\Omega}} \,\mathrm{d}\omega \\ &= \frac{\sqrt{2\pi}}{2\Omega} \, \frac{1}{\sqrt{2\pi}} \, \int_{-\Omega}^{\Omega} \hat{f}(\omega) \, \mathrm{e}^{i \, \left( -\frac{n \, \pi}{\Omega} \right) \omega} \,\mathrm{d}\omega \\ &= \frac{\sqrt{2\pi}}{2\Omega} \, f \left( - \frac{n \, \pi}{\Omega} \right) \\ \end{align}}

Use this definition of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_n} in the series expansion of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{f}} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \hat{f} &= \sum_{n=-\infty}^\infty c_n \, \mathrm{e}^{\frac{i \, n \, \pi \, \omega}{\Omega}} \\ &= \sum_{j=-\infty}^\infty c_{-j} \, \mathrm{e}^{-\frac{i \, j \, \pi \, \omega}{\Omega}} \\ &= \sum_{j=-\infty}^\infty \frac{\sqrt{2\pi}}{2\Omega} \, f \left( \frac{j \, \pi}{\Omega} \right) \, \mathrm{e}^{-\frac{i\, j \, \pi \, \omega}{\Omega}} \end{align}}

Put the series back into the definition and interchange sum & integral (takes a lot of work)

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} f(t) &= \frac{1}{\sqrt{2\pi}} \, \int_{-\Omega}^{\Omega} \left( \left( \sum_{j=-\infty}^\infty \frac{\sqrt{2\pi}}{2\Omega} \, f \left( \frac{j \, \pi}{\Omega} \right) \, \mathrm{e}^{-\frac{j \, \pi \, \omega}{\Omega}} \right) \, \mathrm{e}^{i \, \omega \, t} \right) \,\mathrm{d}\omega \\ &= \sum_{j=-\infty}^\infty \frac{\sqrt{2\pi}}{2\Omega} \, f \left( \frac{j \, \pi}{\Omega} \right) \, \int_{-\Omega}^{\Omega} \mathrm{e}^{i \, \left( t - \frac{j \, \pi \, \omega}{\Omega} \right) \, \omega} \,\mathrm{d}\omega \\ &= \sum_{j=-\infty}^\infty \frac{\sqrt{2\pi}}{2\Omega} \, f \left( \frac{j \, \pi}{\Omega} \right) \, \frac{\sin{(\Omega \, t - j \, \pi)}}{\Omega \, t - j \, \pi} \end{align}}

This recovers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} from its samples at Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{j}{\nu_{Ny}}} .

quod erat demonstrandum


Discrete Fourier Transform

Way of computing an approximation to coefficients in the Fourier Series Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(t) = \sum_{n = -\infty}^\infty c_n \, \mathrm{e}^{i \, n \, t}} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_n = \frac{1}{2\pi} \, \int_{0}^{2\pi} f(t) \, \mathrm{e}^{-i \, n \, t}} , given samples at Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t = \left\{ \frac{2\pi}{n} \, j \right\}_{j=1}^n} .

We know Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_j = f\left( \frac{2\pi\,j}{n} \right)} .

We want Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_n = \frac{1}{2\pi} \, \int_0^{2\pi} f(t) \, \mathrm{e}^{-i\,n\,t} \,\mathrm{d}t} , so we need a quadrature formula to approximate

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_a^b f(t) \,\mathrm{d}t = \sum_{j=0}^n q_j \, f \left( \frac{2\pi \, j}{n} \right) = \sum_{j=0}^n q_j \, y_j}

We shall use the composite trapezoidal rule:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_a^b f(t) \,\mathrm{d}t \approx \frac{b-a}{n} \, \left( \frac{1}{2} y_0 + \frac{1}{2} y_n + \sum_{j=1}^{n-1} f \left( a + \frac{b-a}{n} \, j \right) \right)}

Suppose Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\pi} -periodic (and continuous): Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a = 0} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b = 2\pi} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(t) = f(t+2\pi)} . Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_0 = f(0)} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_n = f(2\pi)} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_0 = y_n} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_a^b f(t) \,\mathrm{d}t \approx \frac{2\pi}{n} \sum_{j=0}^{n-1} f \left( \frac{2\pi}{n} \, j \right)}


Back to the original problem, we wish to evaluate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_k = \frac{1}{2\pi} \, \int_0^{2\pi} f(t) \, \mathrm{e}^{-i\,k\,t} \,\mathrm{d}t \approx \frac{1}{2\pi} \left( \frac{2\pi}{n} \right) \, \sum_{j=0}^{n-1} f \left( \frac{2\pi}{n} \,j \right) \, \mathrm{e}^{- i \, \frac{2\pi}{n} \, j \, k} = \frac{1}{n} \, \sum_{j=0}^{n-1} y_j = \overline{\omega}^{k\,j}}

Where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \overline{\omega} = \mathrm{e}^{ - i \, \frac{2\pi}{n}}} is the complex conjugate of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega = \mathrm{e}^{i \, \frac{2\pi}{n}}} .

We get a nice inversion formula as well:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{y}_k := \sum_{j=0}^{n-1} y_j \, \overline{\omega}^{j\,k}}

and

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_k \approx \frac{\hat{y}_j}{n}}

Then

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_j = \frac{1}{n} \, \sum_{k=0}^{n-1} \hat{y}_j \, \omega^{j\,k}}

Retrieved from "https://notes.komputerwiz.net/w/index.php?title=MATH_414_Lecture_21&oldid=7487"