שינויים
/* תקציר ההרצאות */
[[קטגוריה:מערכי לימוד]]
=מבחנים לדוגמא=
*[[מדיה:20ForierTestA.pdf|מועד א' תש"ף]]
**[[מדיה:20ForierTestASol.pdf|פתרונות סופיים למועד א' תש"ף]]
*[[מדיה:20ForierTestB.pdf|מועד ב' תש"ף]]
*[[מדיה:19ForierExmplTest.pdf|מבחן לדוגמא תשע"ט]]
**[[מדיה:19ForierExmplTestSol.pdf|פתרון מבחן לדוגמא תשע"ט]]
*[[מדיה:19ForierTestA.pdf|מועד א' תשע"ט]]
**[[מדיה:19ForierTestASol.pdf|פתרון חלקי מאד מועד א' תשע"ט]]
*[[מדיה:19ForierTestB.pdf|מועד ב' תשע"ט]]
**[[מדיה:19ForierTestBSol.pdf|פתרון מועד ב' תשע"ט]]
=תקציר ההרצאות=
*ההרצאות מבוססות בחלקן על הספר המצויין [httphttps://www2.mathsamyzaf.com/technion.ac.il/~yoramyfourier/heb-psfourier.html pdf 'טורי פוריה' של זעפרני ופינקוס]. עוד ספרים מתמטיים בסגנון ניתן למצוא [https://samyzaf.com/ באתר של סמי זערפני].
==הרצאה 1 - הקדמה ומקדמי פוריה==
===הקדמה - גלים===
**<math>\frac{1}{\pi}\int_{-\pi}^{\pi}\cos(0)\cos(0)dx=\frac{1}{\pi}\int_{-\pi}^{\pi}1dx=2</math>
*שימו לב שכאשר מציבים 0 בsin מקבלים אפס, ולכן אין צורך בבדיקה הזו.
*כמו כן קל לחשב <math>\int_{-\pi}^{\pi} \sin(x)dx = \int_{-\pi}^{\pi} \cos(x)dx=0</math>
**נגדיר את שתי הפונקציות <math>h_s(t)=\begin{cases}g(t)\sin(\frac{t}{2}) & 0\leq t\leq \pi \\ 0 & -\pi\leq t <0\end{cases}</math> ו <math>h_c(t)=\begin{cases}g(t)\cos(\frac{t}{2}) & 0\leq t\leq \pi \\ 0 & -\pi\leq t <0\end{cases}</math>
**קל לראות כי שתי הפונקציות רציפות למקוטעין. לכן פרט לשינוי במספר סופי של נקודות שלא משפיע על האינטגרל, ניתן להניח כי <math>h_c,h_s\in E</math>.
**ביחד נקבל כי <math>\int_{0}^\pi g(t)\sin\left(\left(n+\frac{1}{2}\right)t\right)dt = \int_{-\pi}^\pi h_c(t)\sin(nt)dt + \int_{-\pi}^\pi h_s(t)sin\cos(nt)dt \to 0</math>
===גרעין דיריכלה===
*כעת נחשב את המקדמים של הסינוסים:
:<math>b_n=\langle f,sin(nx)\rangle = \frac{1}{\pi}\int_{-\pi}^\pi x\sin(nx)dx =\frac{2}{\pi}\int_{0}^\pi x\sin(nx)dx= \frac{2}{n\pi}\left[-x\cos(nx)\right]_{0}^\pi + \frac{2}{n\pi}\int_{0}^{\pi}\cos(nx)dx =
-\frac{2\pi\cos(\pi n)}{\pi n} = \frac{2(-1)^{n+1}}{n}</math>
*לכן, בכל נקודת רציפות של f, כלומר בכל נקודה <math>x\neq \pi +2\pi k</math>, מתקיים כי:
:<math>\frac{\pi}{2}=\sum_{n=1}^\infty\frac{2}{2n-1}\sin(n\pi-\frac{\pi}{2}) =\sum_{n=1}^\infty\frac{-2}{2n-1}\cos(n\pi) = \sum_{n=1}^\infty\frac{2(-1)^{n+1}}{2n-1} </math>
*שימו לב שהפעם לא קיבלנו טור חדש בזכות פורייה, כיוון שנקבל בדיוק את אותו הטור אם נציב 1 בטור הטיילור של <math>arctan(x)</math>.
=====דוגמא 2=====
*כלומר, בתנאים הנתונים, אם טור הפוריה של f הינו:
:<math>f(x)=\sim\frac{a_0}{2}+\sum_{n=1}^\infty a_n\cos(nx)+b_n\sin(nx)</math>
*אזי טור הפורייה של הנגזרת הינו:
:<math>f'(x)=\sim\frac{\alpha_0}{2}+\sum_{n=1}^\infty \left((-1)^n\alpha_0+nb_n\right)\cos(nx)-n\cdot a_n\sin(nx)</math>
*במקרה המיוחד בו <math>f(-\pi)=f(\pi)</math> מתקיים כי <math>\alpha_0=0</math> ולכן נקבל את טור הפורייה הפשוט:
:<math>f'(x)=\sim\sum_{n=1}^\infty nb_n\cos(nx)-na_n\sin(nx)</math>
====דוגמאות====
*נחלץ את המקדמים ונקבל כי טור הפורייה של <math>\frac{x^3}{3}</math> הוא:
:<math>\frac{x^3}{3} = \sim \sum_{n=1}^\infty \frac{2(-1)^n}{n^3}\left(2-\frac{\pi^2 n^2}{3}\right)\sin(nx)</math>
=====דוגמא 2=====
:<math>F(s)=\frac{1}{2\pi}\int_{-\infty}^\infty f(x)e^{-isx}dx = \frac{1}{2\pi}\int_{-\pi}^\pi |x|e^{-isx}dx = </math>
:<math>\frac{1}{2\pi}\int_{-\pi}^\pi |x|\cos(sx)dx - \frac{i}{2\pi}\int_{-\pi}^\pi |x|\sin(sx)dx = \frac{1}{\pi}\int_{0}^\pi x\cos(sx)dx = \frac{\sin(s\pi)}{s} + \frac{\cos(s\pi)-1}{s^2\pi}</math>
*שימו לב: חישוב האינטגרל שגוי עבור <math>s=0</math>, ניתן להציבו בנוסחא המקורית של האינטגרל או להשתמש ברציפות ההתמרה, שנלמד בהמשך.
==הרצאה 7 - תכונות של התמרות פורייה==
*התמרת הנגזרת:
*נניח <math>f,f'\in G</math> ונניח כי <math>f'</math> רציפה ומתקיים כי <math>\lim_{x\to \pm\infty}f(x)=0</math>, אזי:
*<math>\mathcal{F}[f'](s)=is\mathcal{F}[f](s)</math>
**הוכחה:
*כיוון ש<math>e^{-x^2}</math> רציפה וגזירה, וכיוון ש <math>e^{-\frac{s^2}{4}}\in G</math> לפי משפט ההתמרה ההפוכה נקבל כי:
**<math>\mathcal{F}^{-1}[Ce^{-\frac{s^2}{4}}](x) = e^{-x^2}</math>
*כלומר <math>e^{-x^2}=\int_{-\infty}^\infty Ce^{-\frac{s^2}{4}}e^{-isx}ds </math>
*נציב <math>t=\frac{s}{2}</math> ונקבל:
**<math>e^{-x^2} = 2C\int_{-\infty}^\infty e^{-t^2}e^{-i(-2x)t}dt = 2C\cdot 2\pi Ce^{-\frac{(-2x)^2}{4}}</math>
*נזכור בנוסף שראינו כי <math>2\pi C = \int_{-\infty}^\infty e^{-x^2}dx</math>.
*לכן נובע כי <math>\int_{-\infty}^\infty e^{-x^2}dx = \sqrt{\pi}</math>
===דוגמא===
*נביט ב<math>f(x)=\begin{cases}1 & |x|<1 \\ 0 & |x|>1\end{cases}</math>
*<math>\mathcal{F}[f](s) = \frac{sin(s)}{\pi s}</math>
*<math>\lim \int_{-(n+\frac{1}{2})}^{n+\frac{1}{2}} \frac{sin(s)}{\pi s}e^{is}ds = \frac{1}{2}</math> (הצבנו x=1, הנקודה בה f אינה רציפה).
===הקדמה לקראת הוכחת משפט ההתמרה ההפוכה===
**<math>\int_{-(n+\frac{1}{2})}^{n+\frac{1}{2}}\int_{-\infty}^\infty f(y)e^{is(x-y)}dyds = \lim_{k\to\infty} \int_{-k}^k \int_{-(n+\frac{1}{2})}^{n+\frac{1}{2}}f(y)e^{is(x-y)}dsdy = \int_{-\infty}^\infty \int_{-(n+\frac{1}{2})}^{n+\frac{1}{2}}f(y)e^{is(x-y)}dsdy</math>
**שימו לב שהאינטגרל הלא אמיתי אכן מתכנס (כפי שהוכחנו לעיל) ולכן שווה לגבול.
==הרצאה 9 - קונבולוציה, משוואת החום על מוט אינסופי==
*שימו לב: בנושא זה נבצע החלפת סדר אינטגרציה מספר פעמים, אך לא נצדיק החלפות אלו החלפה זו כיוון שהן דורשות שהיא דורשת העמקה רבה.
*ניתן להעמיק ע"י קריאה בספר Fourier Analysis של T.W.Korner
*(נניח כי הפתרון מקיים את התנאים שמאפשרים להחליף את סדר הגזירה והאינטגרציה, לא נרחיב על כך בהמשך)
*כיוון ש<math>u_t-ku_{xx}=0</math> נקבל כי:
:<math>U_t(s,t) = \frac{k}{2\pi}\int_{-\infty}^{\infty} u_{xx}(x,t)e^{-isx}dx</math>
*נזכר בנוסחאת התמרת הנגזרת <math>\mathcal{F}[f']=is\mathcal{F}[f]</math>
*ולכן נקבל כי:
*שימו לב שבפתרון הסופי מופיעה פונקצית תנאי ההתחלה, ואין צורך לחשב את ההתמרה שלה.
==הרצאה 10 - משפט הדגימה של שנון==
===משפט הדגימה של שנון===
*תהי פונקציה f. ברור שבהנתן הערכים של f על השלמים <math>f(0),f(\pm 1),f(\pm 2),...</math> לא ניתן להסיק כלום על ערכיה האחרים (אפילו אם היא רציפה וגזירה).
*בפרט אם נדגום באופן דומה את הפונקציה <math>sin(x)</math> בנקודות <math>2\pi n</math> אנחנו עשויים לחשוד שהיא קבועה לחלוטין.
*מה יקרה אם נדגום גל בקצב מהיר יותר מהתדר שלו?
*במילים פשוטות, משפט הדגימה של שנון אומר שבהנתן פונקציה שהתדרים שלה חסומים, אם נדגום אותה בקצב מהיר פי 2 מהתדר המקסימלי שלה, נוכל לשחזר אותה לחלוטין.
*כעת ננסח את המשפט במדויק, יחד עם ניסוח התנאים הנחוצים על הפונקציות.
*עד כה דיברנו על תדר כמדד לקצב בו הפונקציה חוזרת על עצמה, כעת נגדיר אותו במדויק:
*בהנתן פונקציה עם מחזור <math>t</math> נגדיר את התדר של המחזור להיות <math>\frac{1}{t}</math>.
*דוגמאות:
**התדר של <math>\sin(x)</math> הוא <math>\frac{1}{2\pi}</math>
**התדר של <math>\sin(\pi x)</math> הוא <math>\frac{1}{2}</math>
**באופן כללי, התדר של <math>sin(\pi t x)</math> הוא <math>\frac{t}{2}</math> כיוון ש <math>\sin(\pi t(x+\frac{2}{t})) = \sin(\pi t x)</math>
**התדר של <math>e^{isx}</math> הוא <math>\frac{|s|}{2\pi}</math> כיוון ש <math>e^{is(x+\frac{2\pi}{|s|})} = e^{isx\pm i2\pi} =e^{isx}</math>
*משפט הדגימה של שנון:
*תהי <math>f\in G</math> רציפה ובעלת נגזרת חד צדדיות הקיימות בכל נקודה, שתדריה חסומים על ידי <math>t</math>, אזי בהנתן דגימה שלה בתדר <math>2t</math> ניתן לשחזר אותה בכל הממשיים (כלומר היא נקבעת באופן יחיד על ידי הדגימות).
*שימו לב: הכוונה בכך שתדריה של הפונקציה חסומים, היא למעשה ש<math>\mathcal{F}[f](s)=0</math> לכל <math>\frac{|s|}{2\pi}>t</math>.
====הוכחת משפט הדגימה====
*כיוון שהתמרת הפורייה מתאפסת מחוץ לקטע <math>[-2\pi t,2\pi t]</math>, ניתן לקבוע כי
:<math>\int_{-\infty}^\infty \mathcal{F}[f](s)e^{isx}ds = \int_{-2\pi t}^{2\pi t}\mathcal{F}[f](s)e^{isx}ds</math>
*ובפרט האינטגרל מתכנס.
*לפי משפט ההתמרה ההפוכה, נובע כי <math>f(x)= \int_{-2\pi t}^{2\pi t}\mathcal{F}[f](s)e^{isx}ds</math>
*כעת, נתונה לנו סדרת הדגימות בתדר <math>2t</math>:
:<math>c_n = f\left(\frac{n}{2t}\right), n\in\mathbb{Z}</math>
*נציב אותן בנוסחא שמצאנו לעיל:
:<math>c_n = \int_{-2\pi t}^{2\pi t}\mathcal{F}[f](s)e^{is\left(\frac{n}{2t}\right)}ds</math>
*נבצע הצבה <math>\frac{s}{2t}=-x</math> ונקבל:
:<math>c_n = \int_{-\pi}^\pi \mathcal{F}[f](-2tx)e^{-inx}dx</math>
*אבל אלה בדיוק מקדמי פוריה (פרט לקבוע <math>\frac{1}{2\pi}</math>) של הפונקציה <math>\mathcal{F}[f](-2tx)</math>.
*כיוון שההתמרה חסומה בתדר, עבור <math>|x|\geq \pi</math> מתקיים כי <math>\mathcal{F}[f](-2tx)=0</math> (זכרו כי ההתמרה רציפה, ולכן מתאפסת גם בקצוות).
*לכן <math>\mathcal{F}[f](-2tx)</math> נקבעת על ידי ערכיה בקטע <math>(-\pi,\pi)</math>, והם נקבעים באופן יחיד על ידי מקדמי הפורייה (מסקנה מפרסבל).
*לבסוף, כפי שראינו לעיל, הפונקציה f נקבעת באופן יחיד על ידי ההתמרה (בזכות משפט ההתמרה ההפוכה).
====הערות====
*שימו לב שלא ניתן באופן פרקטי לדגום אות אנלוגי באינסוף נקודות.
*מה יקרה אם נדגום במספר סופי של נקודות ונניח כי הפונקציה ממשיכה באופן מחזורי?
*נקבל פונקציה שאינה שייכת ל<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)=B_0e^{2\pi i \cdot 0\cdot\frac{t}{N}x}+ B_1e^{2\pi i \cdot 1\cdot\frac{t}{N}x}+B_2e^{2\pi i \cdot 2\cdot\frac{t}{N}x}+...+B_{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>
*שימו לב - ככל שנדגום יותר נקודות נקבל יותר מגוון של תדרים. מצד שני, נביט בחלון זמן יותר ארוך ונפספס שינויי תדרים מהירים יותר.
*נוכיח שפירוק זה תמיד אפשרי כך שיהיה שיוויון בכל נקודות הדגימה, ונקשר בין סדרת המקדמים להתמרת הפורייה של נקודות הדגימה.
*נביט בפונקצית הגל <math>u_n(x)=e^{2\pi i n\frac{t}{N}x}</math>.
*נציב בה את נקודות הדגימה ונקבל את הוקטור המרוכב:
:<math>v_n= \left(u_n(0),u_n(\frac{1}{t}),...,u_n(\frac{N-1}{t})\right) = \left( 1,e^{2\pi i n \frac{1}{N}},e^{2\pi i n \frac{2}{N}},...,e^{2\pi i n \frac{N-1}{N}} \right)</math>
*נציב בפונקציה הנתונה f את נקודות הדגימה ונקבל את הוקטור המרוכב:
:<math>v=\left(f(0),f(\frac{1}{t}),f(\frac{2}{t}),...,f(\frac{N-1}{t})\right) = (a_0,...,a_{N-1})</math>
*לכן אנו מעוניינים בפתרון למשוואה:
:<math>v=B_0v_0+...+B_{N-1}v_{N-1}</math>
*זה בדיוק אומר שהפירוק של הפונקציה לגלים מתקיים בכל נקודות הדגימה:
:<math>f(\frac{k}{t}) = B_0u_0(\frac{k}{t})+...+B_{N-1}u_{N-1}(\frac{k}{t})</math>
*נבחן את הקבוצה <math>\{v_0,...,v_{N-1}\}</math>.
:<math>\langle v_n,v_n\rangle = v_n^t \overline{v_n} = \sum_{k=0}^{N-1} e^{2\pi i n \frac{k}{N}}\cdot e^{-2\pi i n \frac{k}{N}}= 1+1+...+1= N</math>
*עבור <math>n\neq m</math>:
:<math>\langle v_n,v_m\rangle = \sum_{k=0}^{N-1} e^{2\pi i n \frac{k}{N}}\cdot e^{-2\pi i m \frac{k}{N}} = \sum_{k=0}^{N-1} e^{2\pi i (n-m) \frac{k}{N}}</math>
*אבל זה בדיוק סכום סדרה הנדסית <math>1+q+...+q^{N-1}</math> עבור <math>q=e^{2\pi i (n-m)\frac{1}{N}}</math>
*שימו לב ש<math>\frac{|n-m|}{N}<1</math> ולכן <math>q\neq 1</math>.
*כמו כן, שימו לב ש<math>q^N = e^{2\pi i (n-m)}=1</math>
*לכן לפי הנוסחא לסכום סדרה הנדסית נקבל כי:
:<math>\langle v_n,v_m\rangle = \frac{1-q^N}{1-q}=0</math>
*כלומר גילינו כי <math>\{v_0,...,v_{N-1}\}</math> קבוצה אורתוגונלית (לא אורתונורמלית) ומהווה בסיס.
*לכן ניתן בקלות לחשב את המקדמים <math>B_n = \frac{\langle v,v_n\rangle}{N}</math>
*לבסוף, נשים לב כי:
:<math>\langle v,v_n\rangle = \sum_{k=0}^{N-1} a_k e^{-2\pi i n \frac{k}{N}} = A_n</math>
*כלומר <math>B_n = \frac{A_n}{N}</math>
====התמרת פורייה הבדידה ההפוכה====
*מכאן גם ניתן להסיק ישירות את התמרת פורייה ההפוכה, שמחזירה את סדרת המקדמים <math>A_n</math> לסדרת הדגימות <math>a_n</math>.
:<math>v=\frac{1}{N}(A_0v_0+...+A_{N-1}v_{N-1})</math>
*ולכן:
:<math>a_n = \frac{1}{N}\sum_{k=0}^{N-1} A_k e^{2\pi i k \frac{n}{N}}</math>
====מסקנות לגבי גלים ממשיים====
*פירקנו את הפונקציה לסכום של גלים מרוכבים בנקודות הדגימה, האם ניתן להשתמש בהתמרה על מנת לקבל פירוק לגלים ממשיים?
*ראשית, נשים לב לתופעה הבאה:
:<math>v_{N-n} = (1,e^{2\pi i (N-n) \frac{1}{N}},...,e^{2\pi i (N-n) \frac{N-1}{N}}) = (1,e^{2\pi i (N-n) \frac{1}{N} - 2\pi i },...,e^{2\pi i (N-n) \frac{N-1}{N} - 2\pi i (N-1)})</math>
*(השיוויון נכון בזכות המחזוריות)
*ולכן נקבל:
:<math>v_{N-n} = (1, e^{2\pi i (\frac{(N-n)}{N} - 1)},...,e^{2\pi i (N-1)(\frac{(N-n)}{N} - 1)}) = v_{-n}</math>
*כלומר פירוק הפונקציה לגלים <math>u_0,u_1,...,u_{N-1}</math> נותן את אותם המקדמים כמו פירוק הפונקציה לגלים <math>u_0,u_1,u_{-1},...</math>.
*כאשר המקדם של <math>u_{-n}</math> שווה למקדם של <math>u_{N-n}</math>.
*שימו לב שזה לא פירוק של הפונקציה לסכום הגלים בכל הממשיים, אלא רק בנקודות הדגימה.
*לדוגמא:
*נניח שיש לנו 5 דגימות של f.
*אם נפרק את f לגלים <math>u_0,u_1,...,u_5</math> נקבל <math>v=B_0v_0+...+B_4v_4</math>
*אם נפרק את f לגלים <math>u_{-2},u_{-1},u_0,u_1,u_2</math> נקבל <math>v=B_3v_{-2},B_4v_{-1}+B_0v_0+B_1v_1+B_2v_2</math>
*במצב זה, אם דגמנו בתדר <math>t</math> נקבל את התדרים <math>0,\frac{t}{5},\frac{2t}{5}</math> שזה מתאים למשפט הדגימה של שנון (טווח התדרים של הפונקציה הוא עד חצי מתדר הדגימה).
*עבור n ספציפי מתקיים כי:
:<math>B_ne^{2\pi i n \frac{t}{N}x} + B_{N-n}e^{-2\pi i n \frac{t}{N}x} = (B_n+B_{N-n}) \cos (2\pi n \frac{t}{N}x) + i(B_n-B_{N-n})sin(2\pi n \frac{t}{N}x)</math>
*מהצבה ישירה של הנוסחאות שמצאנו ניתן לראות שאם f ממשית אזי <math>B_n+B_{N-n}</math> וגם <math>i(B_n-B_{N-n})</math> הם ממשיים.
*כלומר הצלחנו לפרק את f לסכום של גלים ממשיים עם מקדמים ממשיים.
*הערה: אם N זוגי, אז הגל <math>u_{\frac{N}{2}}</math> נותר בודד.
*לדוגמא עבור <math>N=4</math> נקבל במקום הגלים <math>u_0,u_1,u_2,u_3</math> את <math>u_{-1},u_0,u_1,u_2</math>
*נשים לב כי במקרה זה <math>v_{\frac{N}{2}}</math> הוא וקטור ממשי (ולכן גם המקדם שלו ממשי) כיוון שהsin מתאפס בכל נקודות הדגימה.
