שינויים
/* הרצאה 10 - משפט הדגימה של שנון, התמרת פורייה הבדידה */
*שימו לב שבפתרון הסופי מופיעה פונקצית תנאי ההתחלה, ואין צורך לחשב את ההתמרה שלה.
==הרצאה 10 - משפט הדגימה של שנון, התמרת פורייה הבדידה==
===משפט הדגימה של שנון===
*תהי פונקציה f. ברור שבהנתן הערכים של f על השלמים <math>f(0),f(\pm 1),f(\pm 2),...</math> לא ניתן להסיק כלום על ערכיה האחרים (אפילו אם היא רציפה וגזירה).
*נקבל פונקציה שאינה שייכת ל<math>G</math>, כיוון שהאינטגרל שלה לא יכול להתכנס בכל הממשיים.
*בהמשך, נראה אנלוגיה למשפט הדגימה של שנון בהתמרת פורייה הבדידה.
==הרצאה 11 - התמרת פורייה הבדידה==
===DFT - Discrete Fourier transform===
*תהי סדרת נקודות <math>a_0,...,a_{N-1} \in \mathbb{C}</math>, התמרת הפורייה הבדידה שלה היא סדרת הנקודות <math>A_0,...,A_{N-1}\in\mathbb{C}</math> המוגדרת ע"י:
:<math>A_n = \sum_{k=0}^{N-1} a_k e^{-2\pi i n\frac{k}{N}} </math>
*שימו לב שכמות הפעולות הנדרשות לחישוב ההתמרה באופן ישיר היא סדר גודל של <math>N^2</math>.
*התמרת פורייה המהירה (FFT) מבצעת את אותו חישוב בכמות פעולות בסדר גודל של <math>N\log(N)</math>.
====משמעות ההתמרה====
*תהי פונקציה f. נדגום ממנה <math>N</math> נקודות בתדר <math>t</math>, כלומר נתון לנו:
:<math>f(0),f(\frac{1}{t}),f(\frac{2}{t}),...,f(\frac{N-1}{t})</math>
*נסמן נקודות אלה ב<math>a_k=f(\frac{k}{t})</math>
*אנו רוצים לפרק אותה לסכום של גלים:
:<math>f(x)=A_0e^{2\pi i \cdot 0\cdot\frac{t}{N}x}+ A_1e^{2\pi i \cdot 1\cdot\frac{t}{N}x}+A_2e^{2\pi i \cdot 2\cdot\frac{t}{N}x}+...+A_{N-1}e^{2\pi i \cdot (N-1)\cdot\frac{t}{N}x}</math>
*כיוון שהתדר של <math>e^{isx}</math> הוא <math>\frac{|s|}{2\pi}</math> נובע כי הגלים הללו הם בתדרים <math>0,\frac{t}{N},\frac{2t}{N},...,\frac{(N-1)t}{N}</math>
*נוכיח שפירוק זה תמיד אפשרי כך שיהיה שיוויון בכל נקודות הדגימה, ושסדרת המקדמים היא אכן התמרת הפורייה של נקודות הדגימה.
