התמרת פורייה הבדידה - מה זה בכלל?

עד עכשיו ראינו שני סוגים של התמרות פורייה: אחת עבור פונקציות מחזוריות מעל הממשיים, כלומר פונקציות שמוגדרות מעל הקטע \( \left[-\pi,\pi\right] \) ואנחנו יכולים “להרחיב” אותן לכל \( \mathbb{R} \) באופן מחזורי; ופונקציות שהוגדרו מראש על כל \( \mathbb{R} \). להתמרה במקרה הראשון קראנו “טורי פורייה” כי התוצאה המתקבלת היא פירוק של הפונקציה לסכום - טור - של פונקציות בסיס. במקרה השני קיבלנו התמרה שהיא בעצמה פונקציה ממשית. ההבדל בין המקרה הראשון והשני הוא שבמקרה הראשון ההתמרה יוצאת לנו פונקציה שמוגדרת על מרחב בדיד בזמן שבמקרה השני יוצאת לנו פונקציה על מרחב רציף.

מה זה בדיוק מרחב רציף ומה זה בדיוק מרחב בדיד קשה לומר בלי הגדרות נוספות וזה לא קריטי לנו כרגע, אבל אינטואיציה לא רעה לעומק ההבדל היא שמרחב בדיד הוא בן מניה - יש לו מספר “קטן יחסית” של איברים, בזמן ש-\( \mathbb{R} \) היא קבוצה לא בת מניה - יש בה “המון” איברים. ההבדל הזה גורם להבדלים טכניים ברורים - מעל מרחב בדיד יש משמעות לדיבור על טורים, מעל מרחב רציף התורה של טורים כבר לא עובדת וצריך לדבר על אינטגרלים במקום זה. גם בהסתברות יש לנו את התופעה הזו ואפשר לראות הבדל מובהק בין הסתברות על מרחב בדיד - שהיא פשוטה ונחמדה ואינטואיטיבית יחסית - ובין הסתברות על מרחב רציף שהיא מהומה שלמה. וכמובן, ייצוגים של פונקציות במחשב הם לרוב ייצוגים בדידים. אמנם, אפשר לאכסן במחשב במדויק פונקציה כמו \( f\left(x\right)=x^{2} \) גם אם היא מוגדרת מעל הממשיים, אבל עבור פונקציות כלליות, שנתונות לנו בעיקר בתור אוסף זוגות קלט-פלט, זה כבר לא אפשרי.

כל המבוא הזה בא לומר שהצעד המתבקש הבא אחרי מה שכבר ראינו הוא לדבר על התמרת פורייה עבור פונקציות שמוגדרות לא מעל \( \mathbb{R} \) אלא מעל \( \mathbb{Z} \). כמקודם, אני רוצה לדבר על שני מקרים שונים - זה של פונקציות מחזוריות וזה של פונקציות לא מחזוריות. הראשונות יהיו מעניינות במיוחד כי הן ניתנות לתיאור על ידי סדרה סופית של מספרים - כלומר, כולן ניתנות לייצוג מדויק לחלוטין במחשב. לשתי ההתמרות הללו אקרא “התמרת פורייה הבדידה”, למרות שלרוב מי שמשתמש בביטוי הזה מתכוון רק למקרה של פונקציות מחזוריות, והמקרה השני מכונה לעתים “התמרת פורייה בזמן בדיד” כדי להבדיל ביניהם.

נתחיל, כרגיל, מהתיאוריה הבסיסית; אבל אחר כך אעבור סוף סוף להמחשה של שימוש בסיסי כלשהו לכל העסק הזה, על ידי הכנסת מושג מורכב יותר שנקרא קונבולוציה. הייתי יכול להראות קונבולוציות כבר קודם, אבל אני חושב שההקשר שבו הכי קל לעכל אותם הוא ההקשר הבדיד ולכן התאפקתי עד כה.

בשלב הזה אנחנו כבר למודי קרבות עם התמרות פורייה ויודעים מה מצפה לנו - מה שקראתי לו משוואות סינתזה ואנליזה. משוואת אנליזה לוקחת פונקציה ו”מפרקת” אותה לרכיבים - כלומר, נותנת לנו את ההתמרה של הפונקציה. משוואת סינתזה לוקחת את הרכיבים ו”בונה מחדש” את הפונקציה - כלומר, נותנת לנו את ההתמרה ההפוכה של הפונקציה. ה”רכיבים” שלנו בהקשר של פורייה הן פונקציות טריגונומטריות - בפוסט הקודם עברתי להשתמש באקספוננט מרוכב במקום לכתוב במפורש סינוסים וקוסינוסים.

לצורך תזכורת, הנה משוואות האנליזה והסינתזה של פונקציות \( f:\mathbb{R}\to\mathbb{C} \) ו-\( g:\left[-\pi,\pi\right]\to\mathbb{C} \):

אנליזה:

\( \hat{f}\left(\omega\right)=\int_{-\infty}^{\infty}f\left(t\right)e^{-2\pi i\omega t}dt \)

\( \hat{g}\left(n\right)=\frac{1}{2\pi}\int_{-\pi}^{\pi}g\left(x\right)e^{-inx}dx \)

סינתזה:

\( f\left(t\right)=\int_{-\infty}^{\infty}\hat{f}\left(\omega\right)e^{2\pi i\omega t}d\omega \)

\( g\left(x\right)=\sum_{n=-\infty}^{\infty}\hat{g}\left(n\right)e^{inx} \)

עכשיו בואו נעבור לדבר על פונקציות בדידות. ניקח פונקציה \( f:\mathbb{Z}\to\mathbb{C} \) ופונקציה \( g:\mathbb{Z}_{N}\to\mathbb{C} \) כאשר \( N \) הוא מספר טבעי חיובי כלשהו. \( \mathbb{Z}_{N}=\left\{ 0,1,2,\dots,N-1\right\} \) למי שתוהה מה פשר הסימון הזה ולא מכיר אותו.

בואו נתחיל מ-\( f \). איך משוואת האנליזה שלה תיראה? האם הגיוני לכתוב \( \hat{f}\left(\omega\right)=\int_{-\infty}^{\infty}f\left(t\right)e^{-2\pi i\omega t}dt \) גם במקרה הזה? התשובה היא כמובן “לא”, כי \( f\left(t\right) \) לא מוגדרת כמעט עבור אף ערך של \( t \). אנחנו הולכים להצטמצם רק לערכים שבהם \( f \) מוגדרת, ולכן נעבור מאינטגרל לסכום:

\( \hat{f}\left(\omega\right)=\sum_{n=-\infty}^{\infty}f\left(n\right)e^{-2\pi i\omega n} \)

\( \hat{f} \) היא פונקציה ממשית - לכל מספר ממשי שנציב בה, יש הגיון מאחורי הערך שנקבל. אבל די קל לראות שזו תהיה פונקציה מחזורית: באופן כללי, \( e^{2\pi ik}=1 \) לכל \( k \) שלם (זה מייצג \( k \) סיבובים נגד כיוון השעון על מעגל ברדיוס 1 כשנקודת ההתחלה שלנו היא הנקודה \( \left(1,0\right) \)), ולכן \( e^{-2\pi i\left(\omega+k\right)n}=e^{-2\pi i\omega n}\cdot e^{-2\pi ikn}=e^{-2\pi i\omega n}\cdot\left(e^{2\pi ik}\right)^{-n}=e^{-2\pi i\omega n} \). זה כמובן לא מפתיע בכלל - ראינו שפונקציה מחזורית על \( \mathbb{R} \) עוברת לפונקציה על \( \mathbb{Z} \) על ידי התמרת פורייה, ושיש התמרה בכיוון ההפוך שמחזירה את הפונקציה על \( \mathbb{Z} \) להיות פונקציה מחזורית על \( \mathbb{R} \); מה שאנחנו עושים כרגע הוא פשוט להתחיל מהפונקציה על \( \mathbb{Z} \), אבל מה ההבדל?

התשובה היא שאין ממש הבדל - משוואות האנליזה והסינתזה יכולות להילקח מהמשוואות המתאימות עבור טורי פורייה, עם היפוך סימנים ותו לא:

אנליזה:

\( \hat{f}\left(x\right)=\sum_{n=-\infty}^{\infty}f\left(n\right)e^{-inx} \)

סינתזה:

\( f\left(n\right)=\frac{1}{2\pi}\int_{-\pi}^{\pi}\hat{f}\left(x\right)e^{inx}dx \)

בשל כך, אני רוצה לקפוץ אל החלק היותר מעניין של הפוסט - המקרה שבו יש לנו פונקציה מחזורית על הטבעיים, \( g:\mathbb{Z}_{N}\to\mathbb{C} \). במקרה הזה, אפשר לזהות את הפונקציה עם סדרת הערכים שהיא מחזירה - סדרה שאסמן \( a_{0},a_{1},a_{2},\dots,a_{N-1} \) (כלומר - \( a_{k}=g\left(k\right) \)). התמרת פורייה לוקחת את סדרת הערכים הזו ומחזירה, כרגיל, את המקדמים בפירוק שלה לרכיבים. וממי יורכבו הרכיבים הללו? הבה וניזכר מה קרה בטורי פורייה המקוריים - התחלנו מפונקציה מחזורית, ומצאנו פונקציות מחזוריות “קנוניות” שבעזרתן נבנה אותה. גם כאן אנו מתחילים מפונקציה \( N \)-מחזורית, ולכן רוצים פונקציות אקספוננט שהן \( N \)-מחזוריות (על קלטים שהם מספרים שלמים). לא קשה במיוחד לראות שאלו חייבות להיות פונקציות מהצורה \( t\left(n\right)=e^{\frac{2\pi ik}{N}n} \) כאשר \( 0\le k<N \). למה? כי בואו נניח ש-\( t\left(n\right)=e^{isn} \) היא פונקצית אקספוננט \( N \)-מחזורית, כלומר \( e^{isn}=e^{is\left(n+N\right)} \), אז נקבל \( e^{isN}=1 \). עכשיו, למשוואה הזו יש פתרון רק אם \( 2\pi|sN \), כלומר רק אם קיים \( k \) כך ש-\( 2\pi k=sN \), כלומר \( s=\frac{2\pi k}{N} \), כנדרש.

עכשיו, התרגלנו לחשוב על האקספוננטים שלנו בתור סינוסים וקוסינוסים, אבל בהקשר הנוכחי שלנו יש לפונקציות \( t\left(n\right)=e^{\frac{2\pi ik}{N}n} \) משמעות נוספת - אלו הם שורשי היחידה מסדר \( N \). תזכורת: מספר מרוכב \( x \) הוא שורש יחידה מסדר \( N \) אם \( x^{N}=1 \) (במספרים הממשיים יש רק שני מספרים שחזקה שלהם יכולה לתת 1 - רק 1 עצמו ומינוס 1, ולכן זה מעניין רק בהקשר של מספרים מרוכבים). שורשי היחידה מסדר \( N \) הם חבורה כפלית - אם כופלים שניים מהם מקבלים שוב פעם שורש יחידה מסדר \( N \). כמו כן, אם נסמן \( \omega=e^{\frac{2\pi i}{N}} \) (אין קשר בין הסימן \( \omega \) כאן לסימן שהשתמשנו בו קודם בשביל לתאר את המשתנה של “מרחב התדר” - זה פשוט אותו סימן שמשמש בהקשרים שונים) נקבל שורש יחידה מסדר \( N \) שחזקות שלו נותנות את כל יתר שורשי היחידה - כל שורשי היחידה מסדר \( N \) הם \( \omega^{0},\omega^{1},\omega^{2},\omega^{3},\dots\omega^{N-1} \). לצורך פשטות נהוג לסמן \( \omega_{k}=\omega^{k} \) (למה? כי לעתים קרובות מעלים בחזקה כלשהי את ה-\( \omega_{k} \) ולא רוצים שהחזקה ה-\( k \)-ית “תתנגש” עם החזקה הנוספת).

אז אם לסכם - נתונה לנו סדרת מספרים מרוכבים \( a_{0},a_{1},\dots,a_{N-1} \). אני רוצה לייצג אותה איכשהו בתור צירוף לינארי של הפונקציות \( t_{k}\left(n\right)=\omega_{k}^{n} \). כלומר, אני רוצה למצוא מקדמים מרוכבים \( b_{0},b_{1},\dots,b_{N-1} \) כך שמתקיים:

\( a_{n}=\sum_{k=0}^{N-1}b_{k}\omega_{k}^{n} \)

זו משוואת הסינתזה שלנו - אחר כך אכתוב אותה בצורה הסטנדרטית של פונקציות, אבל לעת עתה בואו ננסה להבין מה משוואת האנליזה תהיה - כלומר, איך מוצאים את ה-\( b \)-ים. יש כמה דרכים לעשות זאת, כמובן, והחביבה עלי הולכת ישירות דרך אלגברה לינארית - אחרי ככלות הכל, מה שיש לנו פה הוא את המרחב הוקטור \( \mathbb{C}^{N} \) שהוא סוף-ממדי ולכן האלגברה הלינארית שלנו תהיה נחמדה וקלה. יחסית.

אם אסמן ב-\( \overline{a} \) את הוקטור \( \overline{a}=\left(a_{0},a_{1},\dots,a_{N-1}\right) \) ובדומה אסמן גם את הוקטור \( \overline{b} \), אז נשים לב שמשוואות הסינתזה הן דרך לכתוב \( \overline{a}=W\cdot\overline{b} \) כאשר \( W \) היא מטריצה שמקודדת בתוכה את כל חזקות שורשי היחידה מסדר \( N \), בצורה הבאה: \( W_{nk}=\omega_{k}^{n} \). קונקרטית, הנה איך שהיא נראית:

\( W=\left[\begin{array}{ccccc}1 & 1 & 1 & \cdots & 1\\1 & \omega & \omega_{2} & \cdots & \omega_{N-1}\\1 & \omega^{2} & \omega_{2}^{2} & \dots & \omega_{N-1}^{2}\\\vdots & \vdots & \vdots & & \vdots\\1 & \omega^{N-1} & \omega_{2}^{N-1} & \cdots & \omega_{N-1}^{N-1}\end{array}\right] \)

מה קורה כאן? כל עמודה מכילה את כל החזקות של אחד משורשי היחידה מסדר \( N \), החל מ-1 הטריוויאלי, עבור ב-\( \omega \) וכלה בכל החזקות של \( \omega \) עד \( \omega_{N-1} \). מטריצות כאלו הן מספיק מעניינות כדי לזכות לשם מיוחד משל עצמן - מטריצות ונדרמונדה, אם כי לרוב השם הזה מיועד למטריצות שבהן החזקות של האיברים הם בשורות ולא בעמודות. המבנה הכללי של מטריצת ונדרמונדה מסדר \( N\times N \) על האיברים \( \alpha_{1},\dots,\alpha_{N} \) הוא זה:

\( V\left(\alpha_{1},\dots,\alpha_{N}\right)=\left[\begin{array}{cccc}\alpha_{1}^{0} & \alpha_{1}^{1} & \cdots & \alpha_{1}^{N-1}\\\alpha_{2}^{0} & \alpha_{2}^{1} & \dots & \alpha_{2}^{N-1}\\\vdots & \vdots & & \vdots\\\alpha_{N-1}^{0} & \alpha_{N-1}^{1} & \cdots & \alpha_{N-1}^{N-1}\end{array}\right] \)

אם נחשוב על זה לרגע נשים לב לכך ש-\( W \) היא סימטרית, ולכן היא גם מטריצת ונדרמונדה במובן הרגיל של ההגדרה, אבל זה לא יהיה חשוב לנו כל כך כרגע.

מה שאנחנו רוצים לעשות הוא למצוא את ההופכית של \( W \), כדי לפתור את המשוואה \( \overline{a}=W\cdot\overline{b} \) - נוכל להסיק ש-\( \overline{b}=W^{-1}\cdot\overline{a} \), והנה קיבלנו דרך מעשית לחשב את התמרת פורייה הבדידה. להפוך את \( W \) זה סיפור מעניין - אמנם, יש נוסחה כללית להופכית של מטריצת ונדרמונדה אבל היא לא טריוויאלית, וכך גם להשתמש בשיטות הסטנדרטיות למציאת הופכית של מטריצה. הכי טוב אם פשוט אצליח לנחש את ההגדרה של \( W^{-1} \) מהשמיים ואוכיח שהיא עובדת. מה הניחוש הכי טוב שלנו? ובכן, אנחנו מחפשים מטריצה שמקודדת משוואת אנליזה - משוואה שנותנת את \( b_{n} \) בתור סכום כלשהו של \( a_{n} \). אפשר להתפלל שהמשוואה הזו תהיה דומה באופיה למשוואות של המקרה הרציף, לנסות, ולראות מה קורה.

אם משוואת הסינתזה של התמרת פורייה הבדידה היא זו:

\( g\left(n\right)=\sum_{k=0}^{N-1}\hat{g}\left(k\right)e^{\frac{2\pi ikn}{N}} \)

אז אפשר לנחש שמשוואת האנליזה תהיה זו:

\( \hat{g}\left(n\right)=\sum_{k=0}^{N-1}g\left(k\right)e^{-\frac{2\pi ikn}{N}} \)

זה רק ניחוש, ותכף נראה שהוא לא מדויק (צריך גם לכפול בקבוע כלשהו, כמו ה-\( \frac{1}{2\pi} \) של המשוואה עבור טורי פורייה) אבל הוא למעשה לא רע בכלל. כדי לפשט עניינים נחזור לסמן \( \omega_{k}^{n}=e^{\frac{i\pi kn}{N}} \), והמינוס הזה מטופל על ידי מעבר לצמוד המרוכב: \( e^{-\frac{i\pi kn}{N}}=\overline{\omega_{k}^{n}} \). אם כן, המועמד שלנו להיות ההופכי של \( W \) היא המטריצה \( W^{*} \) - המטריצה הצמודה של \( W \), שמתקבלת על ידי שחלוף (שלא משנה כלום) והצמדה. עכשיו, כדי לפשט נוסחאות עם הצמוד, בואו נחשוב שניה על דרך יותר פשוטה לסמן אותו: \( \omega\cdot\overline{\omega}=\left|\omega\right|^{2}=1 \) ולכן \( \overline{\omega}=\omega^{-1} \) (למעשה, אפשר לראות את זה מיידית מההגדרה). לכן באופן כללי \( \overline{\omega_{k}^{n}}=\omega_{k}^{-n} \).

כעת, הבה ונתבונן ב-\( \left(WW^{*}\right)_{nk} \):

\( \left(WW^{*}\right)_{nk}=\sum_{i=0}^{N-1}W_{ni}W_{ik}^{*}=\sum_{i=0}^{N-1}\omega_{i}^{n}\overline{\omega_{i}^{k}}=\sum_{i=0}^{N-1}\omega_{i}^{n-k} \)

כאשר \( n=k \) נקבל \( \omega_{i}^{n-k}=1 \) ולכן \( \sum_{i=0}^{N-1}\omega_{i}^{n-k}=N \). לעומת זאת, המקרה שבו \( n\ne k \) מעניין יותר. אם לשאוב אינטואיציה ממה שקרה בטורי פורייה, אנחנו מצפים שהסכום יצא 0 במקרה הזה - אבל למה? ובכן, שימו לב לכך ש-\( \sum_{i=0}^{N-1}\omega_{i}^{n-k}=\sum_{i=0}^{N-1}\omega_{n-k}^{i} \), כלומר אפשר לחשוב על הסכום הזה בתור טור גאומטרי - סכום חזקות של שורש יחידה כלשהו מסדר \( N \). לטור גאומטרי יש באופן כללי נוסחה פשוטה: \( \sum_{i=0}^{t}a^{i}=\frac{a^{t+1}-1}{a-1} \), ולכן במקרה שלנו נקבל \( \sum_{i=0}^{N-1}\omega_{n-k}^{i}=\frac{\omega_{n-k}^{N}-1}{\omega_{n-k}-1}=0 \) - האיבר במונה מתאפס כי \( \omega_{n-k}^{N}=1 \) (זו המשמעות של להיות שורש יחידה מסדר \( N \)).

לסיכום, \( WW^{*}=NI \), כלומר זו מטריצה סקלרית שיש בה \( N \) באלכסון הראשי ו-0 בכל מקום אחר. זה אומר שאפשר להפוך את \( W \) למטריצה אוניטרית על ידי נרמול - חלוקה ב-\( \sqrt{N} \) - אבל לא נזדקק לזה. די לנו במסקנה: \( W^{-1}=\frac{1}{N}W^{*} \). זה נותן לנו את משוואת האנלזיה שחיפשנו:

\( b_{n}=\frac{1}{N}\sum_{k=0}^{N-1}a_{k}\omega_{k}^{-n} \)

המשוואות הללו נותנות לנו אלגוריתם פרקטי לגמרי לחישוב התמרת פורייה הבדידה, גם במחשב, אבל זה לא סוף הסיפור. אם רוצים להשתמש בהתמרה בשביל דברים כמו זה שאראה עוד מעט, רצוי שתהיה דרך מהירה עוד יותר לחשב אותה - ומה שיפה הוא שדרך כזו קיימת, פחות או יותר עוד מזמנו של גאוס, לפני פורייה בכלל. שיטות חישוב מהירות של התמרת פורייה הבדידה נקראות, באופן הולם למדי, “התמרת פורייה מהירה” (Fast Fourier Transform, או FFT בקיצור) ואני אראה את השיטה הידועה ביותר בפוסט נפרד.

בפוסט הקודם הראיתי שיש קשר בין התמרת פורייה של פונקציות ממשיות כלליות ובין התמרת פורייה של פונקציות ממשיות מחזוריות (“טורי פורייה”), שבא לידי ביטוי בדיאגרמה קומוטטיבית:

\( \begin{array}{ccc}f & \leftrightarrow & \hat{f}\\\downarrow & & \downarrow\\g & \leftrightarrow & \hat{g}\end{array} \)

כאשר המעבר מ-\( f \) אל \( g \) התבצע על ידי פעולה של סכימה (שלקחה פונקציה כללית והפכה אותה למחזורית) והמעבר מ-\( \hat{f} \) אל \( \hat{g} \) התבצע על ידי דגימה (שלקחה פונקציה על מרחב רציף והפכה אותה לפונקציה על מרחב בדיד). בצורה לא מפתיעה במיוחד, אותה דיאגרמה (עם אותן פעולות, עד כדי הפרמטרים שלהן שעשויים להיות שונים) מתאימה גם להתמרות שראינו הפעם - התמרה של פונקציה “כללית” על \( \mathbb{Z} \) והתמרה של פונקציה מחזורית על \( \mathbb{Z} \). אז יש לנו עוד עותק של הדיאגרמה

\( \begin{array}{ccc}u & \leftrightarrow & \hat{u}\\\downarrow & & \downarrow\\v & \leftrightarrow & \hat{v}\end{array} \)

עכשיו, די בבירור יש לנו מעברים מהפונקציות \( f \) אל \( u \) ומ-\( g \) אל \( v \) על ידי דגימה (הסבירו לעצמכם למה!) ומ-\( \hat{f} \) אל \( \hat{u} \) ומ-\( \hat{g} \) אל \( \hat{v} \) על ידי סכימה (עם פרמטרים ספציפיים שונים לכל סכימה). אז אנחנו מקבלים דיאגרמה קומוטטיבית דמויית קוביה, שהדיאגרמה הראשונה שהראיתי היא הפאה העליונה שלה, והדיאגרמה השניה היא הפאה התחתונה שלה. נסו לצייר אותן!

כעת, בואו נעבור להדגמה הפשוטה ביותר שאני יכול לחשוב עליה על שימוש יעיל להתמרת פורייה הבדידה (ולהתמרות פורייה באופן כללי). בשביל זה אני צריך את מושג הקונבולוציה שלדעתי הכי קל להסביר דרך המושג של כפל פולינומים.

בואו נסתכל לרגע על המכפלה הבאה של שני פולינומים ממעלה שנייה: \( \left(a_{2}x^{2}+a_{1}x+a_{0}\right)\left(b_{2}x^{2}+b_{1}x+b_{0}\right) \). אני הולך לפתוח את המכפלה ולכתוב את כל האיברים לא כי בא לי לעשות חשבון אלא כי זה יהיה סופר-חשוב להמשך לראות מה קורה כאן. תנסו לעקוב אחרי מה שעשיתי ולבצע את החישוב בראש בעצמכם (הכי טוב אם תעשו את זה על נייר - אבל נו טוב, אני לא מצפה שמישהו יתחיל לכתוב באמצע קריאת פוסט). מה שאני מקבל הוא זה:

\( a_{2}b_{2}x^{4}+\left(a_{1}b_{2}+a_{2}b_{1}\right)x^{3}+\left(a_{0}b_{2}+a_{1}b_{1}+a_{2}b_{0}\right)x^{2}+\left(a_{0}b_{1}+a_{1}b_{0}\right)x+a_{0}b_{0} \)

לפתוח את הכל ידנית זה סיפור לא כיפי, ולכן מה שעושה המתמטיקאי אחרי שהוא מקבל את הנוסחה הזו הוא להביט בה ולנסות להבין מה התבנית שיש כאן - מה ההגיון הכללי מאחורי הנוסחה. אני מקבל סכום של חזקות של \( x \) עם מקדמים שנבנים איכשהו מהמקדמים של הפולינומים שהכפלתי, אבל על פי איזו חוקיות? בואו נסתכל לרגע על המקדם הכי מסובך, זה של \( x^{2} \). כשאנחנו כופלים את הביטוי \( \left(a_{2}x^{2}+a_{1}x+a_{0}\right)\left(b_{2}x^{2}+b_{1}x+b_{0}\right) \) אנחנו בעצם בוחרים איבר מהסוגריים השמאליים ואיבר מהסוגריים הימניים, כופלים אותם, וסוכמים את כל המכפלות שמתקבלות כך. כל מכפלה כזו ש-\( x^{2} \) מופיע בה עם מקדם קבוע כלשהו תתרום את המקדם הזה למקדם של \( x^{2} \) בתוצאה הסופית. כך שנשאלת השאלה - באילו דרכים אפשר לבחור איבר מהסוגריים השמאליים ואיבר מהסוגריים הימניים ולכפול אותם כדי לקבל משהו קבוע כפול \( x^{2} \)?

ובכן, זה פשוט מאוד: צריך לבחור מהסוגריים איברים שסכום חזקות ה-\( x \) שלהם שווה ל-2. כלומר, \( a_{2}x^{2}\cdot b_{0}x^{0} \) (כי \( 2+0=2 \)) ו-\( a_{1}x^{1}\cdot b_{1}x^{1} \) ו-\( a_{0}x^{0}\cdot b_{2}x^{2} \). זה נותן לנו בדיוק את המקדם של \( x^{2} \) שראינו כאן.

ומה קורה באופן הכי כללי שרק אפשר? בואו ניקח שני פולינומים \( \sum_{k=0}^{t}a_{k}x^{k} \) ו-\( \sum_{k=0}^{t}b_{k}x^{k} \) (חלק מהמקדמים עלולים להיות 0 ואין עם זה בעיה) ונכפול אותם: נקבל פולינום \( \sum_{k=0}^{r}c_{k}x^{k} \) שמקיים באופן כללי:

\( c_{n}=\sum_{k=0}^{n}a_{k}b_{n-k} \)

כלומר - \( c_{n} \) הוא סכום שבו מכפילים את כל ה-\( a_{k} \)-ים עד \( a_{n} \) ב-\( b \)-ים, אבל ב-\( b \)-ים שבאים בסדר הפוך - מתחילים ב-\( b_{n} \) ומגיעים עד ל-\( b_{0} \). שימו לב שהמשכי שתי הסדרות (האיברים שאחרי האיברים במקום ה-\( n \)) בכלל לא רלוונטיים.

סדרת ה-\( c_{n} \)-ים הזו היא בדיוק מה שנקרא קונבולוציה של הסדרות \( a_{n},b_{n} \). בואו נגדיר את זה פורמלית: אם \( a_{0},a_{1},a_{2},\dots \) ו-\( b_{0},b_{1},b_{2},\dots \) הן סדרות (שיכולות להיות אינסופיות, אין עם זה בעיה) אז הקונבולוציה שלהן היא סדרה \( c_{0},c_{1},c_{2},\dots \) שמוגדרת על ידי הנוסחה שכבר נתתי: \( c_{n}=\sum_{k=0}^{n}a_{k}b_{n-k} \).

אני מאוד אוהב להציג את העניין הזה בצורה ציורית. בואו נכתוב את אברי הסדרה \( a_{n} \), ומעליהם נכתוב את אברי הסדרה \( b_{n} \) אבל בסדר הפוך, כך שנקודת ה”חיבור” היחידה שלהם היא באיברים עם אינדקס 0:

\( \begin{array}{ccccccc}\cdots & b_{2} & b_{1} & b_{0}\\ & & & a_{0} & a_{1} & a_{2} & \cdots\end{array} \)

חשבו על המקומות שנותרו ריקים בתור 0-ים.

עכשיו נכפול כל איבר בשורה העליונה באיבר שבדיוק מתחתיו בשורה התחתונה, ונסכום הכל. די ברור שכל הכפולות פרט למספר סופי יהיו 0 כך שהסכום הוא בעצם סופי, ולכן מוגדר היטב, וגם קל לראות שהוא פשוט יהיה \( a_{0}b_{0} \). עד כאן, כתיבה מסובכת לדבר פשוט, אבל הנה האופן שבו אני מקבל את האיבר הבא בסכום: אקח את סדרת ה-\( b \)-ים שבשורה העליונה ואזיז אותה צעד אחד ימינה:

\( \begin{array}{ccccccc}\cdots & b_{3} & b_{2} & b_{1} & b_{0}\\ & & & a_{0} & a_{1} & a_{2} & \cdots\end{array} \)

כעת הכפלה של כל זוג איברים וסכום של כולם תניב לי את \( a_{0}b_{1}+a_{1}b_{0} \), וכן הלאה וכן הלאה. \( c_{n} \) יתקבל אחרי שאזיז את ה-\( b \)-ים למעלה \( n \) צעדים ימינה, אכפול ואסכום. התיאור הציורי הזה נותן לי אישית אינטואיציה טובה לגבי “מה הולך כאן בכלל”.

כמובן שההגדרה של קונבולוציה היא יותר כללית מאשר “רק” עבור סדרות. הנה הגדרה דומה עבור פונקציות \( f:\mathbb{R}\to\mathbb{C} \), כאשר אני משתמש בסימן \( * \) כדי לסמן קונבולוציה: \( \left(f*g\right)\left(t\right)=\int_{-\infty}^{\infty}f\left(x\right)g\left(t-x\right)dx \). אפשר גם לתת הגדרה כללית יותר שמתאימה לכל הקשר שבו אפשר לדבר על התמרת פורייה, אבל לא אכנס לכך כרגע.

כפי שכבר הבנו מהמקרה של פולינומים, קונבולוציה היא לא פעולה טריוויאלית לחישוב. מצד שני, כפי שכבר הבנו מהמקרה של פולינומים, קונבולוציה היא משהו שצץ באופן טבעי במתמטיקה, בין אם אנחנו מדברים על התמרת פורייה ובין אם לאו. ולכן הקשר של התמרת פורייה לקונבולוציות הוא לא טריוויאלי ומעניין. ומה הקשר הזה? פשוט מאוד: ההתמרה של קונבולוציה היא מכפלת ההתמרות. בנוסחה, אם \( f,g \) הן פונקציות ואם אני מסמן ב-\( \mathcal{F}\left[f\right],\mathcal{F}\left[g\right] \) את התמרות הפורייה שלהן (וזו יכולה להיות כל אחת משלושת סוגי ההתמרות שכבר ראינו, וזה עובד גם להתמרות פורייה בהקשרים אחרים שלא ראינו), אז \( \mathcal{F}\left[f*g\right]=\mathcal{F}\left[f\right]\cdot\mathcal{F}\left[g\right] \).

בפרט, אם אנחנו יודעים גם לחשב את ההתמרה ההפוכה, \( \mathcal{F}^{-1} \), זה נותן לנו שיטה פשוטה לחשב קונבולוציות: \( f*g=\mathcal{F}^{-1}\left[\mathcal{F}\left[f\right]\cdot\mathcal{F}\left[g\right]\right] \). עוברים ל”מישור התדר”, מבצעים את הכפל שם, ואז חוזרים למשתנה המקורי. נראה מוכר? באלגברה לינארית עושים את זה כל הזמן - אם יש לנו פעולה מסובכת בבסיס הנוכחי שלנו (למשל, העלאה בחזקה גבוהה של איזה אופרטור) אז עוברים לבסיס אחר, נוח יותר, מבצעים את החישוב שם, ואז חוזרים לבסיס המקורי. במובן מסויים זו בדיוק המהות של התמרות פורייה - מעבר לבסיס נוח יותר לצרכים מסויימים.

לא סתם התחלתי מדוגמת הפולינומים. התעלול הזה של ההתמרות נותן לנו אלגוריתם יעיל לכפל פולינומים - יותר יעיל מאשר פשוט לבצע חישוב. זה לא קריטי לפולינומים קטנים, אבל תחשבו על פולינומים עם אלפי מקדמים (או יותר!). כמובן, זה דורש שההתמרות יתבצעו בעזרת FFT, כך שהאלגוריתם שמבצע את הכפל המהיר הזה הוא לא טריוויאלי - אבל עושים את זה בפועל כי זה עובד טוב (למעשה, משתמשים בהתמרת פורייה מהירה גם כדי לחשב כפל של מספרים רגילים עם כמות גדולה של ספרות - עשרות אלפים).

היישום הזה של התמרות פורייה הוא חימום. הוא רק קצה הקרחון. הסיבה העיקרית שאני כותב את הפוסטים הללו היא כדי שאוכל בעתיד להציג שימושים בלי לדאוג לכך שלא הצגתי את הרקע. אבל מה כדאי להראות? שאלה מצויינת, ואתם מוזמנים להשאיר הצעות בתגובות.