FFT

[geni1]

FFT

שלום לכולם! אני מחפשת דוגמא מפורטת לFFT. מה שלא ברור לי הוא המעבר ממטריצה מרוכבת למקדמים לא מרוכבים. תודה!

 

[IsraeliSecretToilets]

מאד מוזר ../images/Emo12.gif

אני דוקא מכיר את FFT בתור המרה של פולינום מהצגה של n+1 מקדמים להצגה באמצעות n+1 נקודות (חזקות של שורש יחידה מסדר n+1). בחירת שורש יחידה מסדר n+1 מאפשר ל-FFT לרדת מתחת לסיבוכיות (O(n² ולהגיע ל-(O(nlogn. אני זוכר שהיתה חלוקה של פולינום לשני פולינומים, אחד עם מקדמים זוגיים, והשני עם מקדמים אי זוגיים, ועליהם מפעילים ברקורסיה את חישוב ערכי הפולינום בנקודה. ואני לא זוכר שהיה שם מעבר כלשהו ממטריצה מרוכבת למשהו לא מרוכב. יכול להיות שבמקרה התוצאות ייצאו לא מרוכבות (את יודעת, יכול להיות שאחרי שמחברים/מחסרים/מחלקים/כופלים כמה מספרים מרוכבים נקבל דוקא מספר ממשי) אבל זה לא משהו וודאי.

 

[geni1]

אתה צודק,אבל אנחנו למדנו

את החישוב בעזרת מטריצת ונדר מונדה. כלומר,בעזרת שורשי יחידה מרוכבים.

 

[IsraeliSecretToilets]

מטריצת ונדר מונדה..

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

 

[IsraeliSecretToilets]

"ואני גם לא רואה..." ../images/Emo122.gif

 

[geni1]

במבחן המרצה נותן מטריצה

עם מקדמים מרוכבים ומבקש למצוא את הפולינום שהיא מייצגת. אני צריכה דוגמא כדי להבין איך זה עובד! תודה!

 

[IsraeliSecretToilets]

אז תגידי חיובי ../images/Emo8.gif

אפשר לעשות את זה בכמה דרכים. נניח והמטריצה שלך היא A, אז אפשר לפתור את המערכת:

Ay = b​

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

 

[geni1]

תודה רבה! ../images/Emo140.gif

 

[IsraeliSecretToilets]

רגע..

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

 

[geni1]

מאוד בכלליות

אם יש לך הסבר מפורט יותר אני אשמח לקרוא

 

[IsraeliSecretToilets]

אין הרבה מה לפרט פה ../images/Emo3.gif

 

[מKה אפורה]

כעת סינית נראית לי שפה פשוטה..

 

[IsraeliSecretToilets]

../images/Emo6.gif

 

[אנקנואון]

../images/Emo124.gif ../images/Emo99.gif

 

[IsraeliSecretToilets]

מה אתה עושה את עצמך..

כאילו אתה מבין מה אני כתבתי שם. אפילו אני לא מבין מה כתבתי שם

 

[OעדיR]

יו מזל, חשבתי זאת רק אני שלא../images/Emo110.gif

 

[אנקנואון]

../images/Emo124.gif אני באמת לא מבין, אבל

זה נראה יפה

.

 

[IsraeliSecretToilets]

אני מכיר כמה..

סטודנטים למדמ"ח שירצו לתת לך מכות

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

 

[אנקנואון]

../images/Emo124.gif אבל זה מתימטיקה...

מתימיטקה זה יפה...

 

[מKה אפורה]

ממש. P: