משפחות של מטריצות

מטריצות טופוליץ

הגדרה 1 (מטריצת טופוליץ)

מטריצה $T$ בגודל $n\times m$ נקראת מטריצת טופליץ אם איבריה מקיימים $t_{i,j}=t_{i+1,j+1}$ .

הערה

לפעמים רושמים $t_{i,j}=t_{j-i}$ וזה פשוט אומר שכל האיברים בהם ההפרש $j-i$ זהה, זהים.

T=\begin{pmatrix} t_{0} & t_{1} & t_{2} & \dots & t_{m-1} \\ t_{-1} & t_{0} & t_{1} & & \vdots \\ t_{-2} & t_{-1} & t_{0} & & \vdots \\ \vdots & & & \ddots & \vdots \\ t_{1-n} & t_{2-n} & t_{3-n} & \dots & t_{m-n} \end{pmatrix}

ישנן שתי תכונות מעניינות למטריצות טופוליץ:

חיבור של שתי מטריצות טופליץ היא גם מטריצת טופוליץ.
כפל בסקלר של מטריצת טופוליץ היא גם מטריצת טופוליץ

הגדרה 2 (מטריצה צרה)

מטריצה $T$ נקראת צרה אם ערכיה השונים מאפס מרוכזים ברצועה צרה סביב האלכסון הראשי.

מה קורה אם אנו מקבלים תרגיל לפתור מערכת משוואות $A\underline{x}=\underline{b}$ כאשר $A$ טופוליץ? האם נוכל לנצל את זה ⟸ כן! אבל בקורס זה לא נדבר על זה.
מה אם נרצה ללכסן מטריצה בעלת מבנה זה ולמצוא את הע"ע שלה? בקורס זה אנו לא נתעסק ישירות עם זה אבל נסתכל על משהו דומה אשר יוביל אותנו להתמרת פורייה.

המקור המרכזי לעיסוק במטריצות האלו היא פעולה בשם קונבולוציה!

הגדרה 3 (קונבולוציה)

יהיו שני וקטורים $\underline{h}\in \mathbb{R}^n,\;\underline{x}\in \mathbb{R}^m$ .
פעולת הקונבולוציה ביניהם תסומן $\underline{z}=\underline{x}\otimes \underline{h}$ ופועלת בצורה הבאה:

z_{k}=\sum_{j=-\infty}^{\infty} x_{k-j}h_{j}=\sum_{j=0}^{n-1}x_{k-j}h_{j}

הערה

אם אנו יוצאים מגבולות $\underline{x}$ או $\underline{z}$ אזי פשוט נקבל בסכימה אפסים באיברים הללו.

באיזה אורך $\underline{z}$ ? זהו בתכלס וקטור באורך אינסופי אבל אין לנו עניין בערכי $k$ שיביאו לאפסים ב- $\underline{z}$ ולכן $0\leq k\leq m+n-2$ כאשר אורך $\underline{z}$ הוא $k$ .

מה אם כעת נקח את הוקטור $\underline{x}$ ונסדר אותו במטריצה בתצורה של מטריצת טופוליץ כך:

\begin{pmatrix} z_{0} \\ z_{1} \\ \vdots \\ z_{m+m-2} \end{pmatrix}=\begin{pmatrix} x_{0} \\ x_{1} & x_{0} \\ x_{2} & x_{1} & x_{0} \\ \vdots & \vdots & \vdots & \ddots \\ x_{m-1} & & & & x_{0} \\ & x_{m-1} & & & x_{1} \\ & & x_{m-1} & & x_{2}\\ & & & \ddots & \vdots \\ & & & & x_{m-1} \end{pmatrix}\begin{pmatrix} h_{0} \\ h_{1} \\ h_{2} \\ \vdots \\ h_{n-1} \end{pmatrix}=X\underline{h}

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

משפט

פעולת הקונבולוציה סימטרית:

\underline{z}=\underline{x}\otimes \underline{h}=\underline{h}\otimes \underline{x}

הוכחה: ישירות מההגדרה.

מסקנה

\underline{z}=X\underline{h}=H\underline{x}

כאשר $H,X$ הן מטריצות טופוליץ הבנויות מהוקטורים $\underline{h},\underline{x}$ בהתאמה.
נשים לב כי קיבלנו מטריצות טופוליץ צרות.

Proposition (דרך אחרת לחשוב על פעולת הקונבולוציה)

הנח את הוקטור $\underline{x}$ בתצורה אופקית.
הצב מולו את הוקטור $\underline{h}$ כשמיקום האיבר הראשון( $x_{0},h_{0}$ ) מותאם בין שניהם.
שקף את $\underline{h}$ סביב נקודת ה- $0$ .
חשב את המכפלה בין איברי $\underline{x}$ ואיברי $\underline{h}$ לפי מיקום התואם וסכם כל מכפלות אלה - זה יהיה ערך $z_{0}$ .
הסע את הוקטור $\underline{h}$ ימינה , כשבכל מיקום $k$ שהוא מוצב, הוא מבצע סכום מכפלות כמקודם ויוצר את $z_{k}$ .

מטריצות סיבוביות

הגדרה 4 (מטריצה סיבובית)

מטריצה $C$ בגודל $n\times n$ נקראת סיבובית אם איבריה מקיימים $t_{i,j}=t_{(j-i)(mod\; n)}$

הערה (תזכורת מאלגברה אמ)

(j-i)(mod\; n)=\begin{cases} n+j-i & j-i<0 \\ j-i & 0\leq j-i<n \end{cases}

הערה

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

הגדרה 5 (קונבולוציה סיבובית)

קונבולוציה סיבובית (ציקלית) בין שני וקטורים $\underline{h}\in \mathbb{R}^n,\underline{x}\in \mathbb{R}^m$ מסומנת $\underline{z}=\underline{x}\underset{c}{\otimes}\underline{h}$ ומייצרת את $\underline{z}$ לפי:

z_{k}=\sum_{j=0}^{n-1} x_{(k-j)(mod\; n)}h_{j}

טענה

וקטור התוצאה בקונבולוציה סיבובית מחזורי ב- $n$ . כלומר, $z_{k+Jn}=z_{k}$ לכל $J \in \mathbb{Z}$ .

הוכחה:

z_{k+Jn}=\sum_{j=0}^{n-1}x_{(k+Jn-j)(mod\; n)}h_{j}=\sum_{j=0}^{n-1}x_{(k-j)(mod\; n)}h_{j}=z_{k}

∎

לכסון מטריצות סיבוביות

נרצה כעת למצוא את הו"ע של המטריצות הסיבוביות מסיבות שנראה בהמשך.

משפט

יהיו $A,B$ מטריצות לכסינות במשותף.
אזי, מכפלתן קומוטטיבית

הוכחה:
אם הן לכסינות במשותף אז קיימת $S$ הפיכה כך שמתקיים:

A=S\Lambda _{A}S^{-1} \qquad \land \qquad B=S\Lambda_{B}S^{-1}

לכן:

AB=S\Lambda_{A}S^{-1}\cdot S\Lambda_{B}S^{-1}=S\Lambda_{A}\Lambda_{B}S^{-1}

לפי משפט, הכפלה של מטריצות אלכסוניות קומוטטיבית ולכן:

AB=S\Lambda_{B}\Lambda_{A}S^{-1}=S\Lambda_{B}S^{-1}S\Lambda_{A}S^{-1}=BA

∎

משפט

כל המטריצות הסיבוביות בגודל $n\times n$ הינן לכסינות אורתונורמלית ובמשותף.
כלומר, כל המטריצות הסיבוביות חולקות את אותם ו"ע, אשר מהווים בסיס אורתונורמלי.

מסקנה

מכפלת מטריצות סיבוביות היא קומוטטיבית.

בקונבולוציה סיבובית נשים לב כי מתקיים:

F(X\underline{h})=X(F\underline{h})=X(H\underline{f})=\cdots

בואו נוכיח את המשפט הנ"ל בדרך ארוכה ומסובכת ולא פורמלית בעליל:
כעת, נגש ללכסון מטריצות סיבוביות. המשימה שלנו פה היא מציאת הו"ע והע"ע שיקיימו את המשוואה הבאה $C\underline{v}=\lambda \underline{v}$ .
על מנת למצוא את הו"ע הללו, נתחיל עם מקרה פשוט של מטריצה סיבובית מאוד בסיסית שתקרא $C_{1}$ אשר נראית כך:

C_{1}\underline{v}=\begin{pmatrix} 0 & 1 & 0 & 0 & \dots & 0 \\ 0 & 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \dots & 1 \\ 1 & 0 & 0 & 0 & \dots & 0 \end{pmatrix}\begin{pmatrix} v_{0} \\ v_{1} \\ v_{2} \\ v_{3} \\ \vdots \\ v_{n-1} \end{pmatrix}=\alpha \begin{pmatrix} v_{0} \\ v_{1} \\ v_{2} \\ v_{3} \\ \vdots \\ v_{n-1} \end{pmatrix}

קיבלנו פה מערכת מעניינת של משוואות:

\begin{cases} v_{1}=\alpha v_{0} \\ v_{2}=\alpha v_{1} \\ v_{3}=\alpha v_{2} \\ \vdots \\ v_{n-1}=\alpha v_{n-2} \\ v_{0}=\alpha v_{n-1} \end{cases}

אז מספיק שנקבע $v_{0}=1$ (זוהי קביעה שרירותית) אזי נקבל כי:

v_{1}=\alpha,v_{2}=\alpha^2,v_{3}=\alpha^3,\dots,v_{n-1}=\alpha^{n-1},v_{0}=\alpha^n=1

קיבלנו פה אילוץ עבור $\alpha$ וכל $\alpha \in \mathbb{R}$ שיפתור משוואה זו יהיה כביל :)

נסתכל על המשוואה שקיבלנו שהיא $\alpha^n=1$ ונשים לב שזהו פולינום אשר לו $n$ שורשים. נשתמש במעגל היחידה ובנוסחת אויילר אשר אומרת:

\alpha_{\ell}=\exp \left\{ -\frac{2\pi i}{n}\ell \right\}=e^{-\frac{2\pi \;\!i}{n}\ell} \quad \quad 0\leq\ell\leq n-1

הערה

ניתן להגדיר זאת גם בדרך אחרת כאשר נאמר כי:

\forall 0\leq \ell\leq n-1:\;\; \alpha_{\ell}=w_{n}^{-\ell},\;\;\; w_{n}=e^{\frac{2\pi}{n}i}

נשים לב כי קיבלנו $n$ ע"ע אפשריים למטריצה $C_{1}$ וקיבלנו את $n$ הו"ע המתייחסים אליהם:

\underline{v}_{\ell}=\begin{pmatrix} 1 \\ \alpha_{\ell} \\ \alpha_{\ell}^2 \\ \alpha_{\ell}^3 \\ \vdots \\ \alpha_{\ell}^{n-1} \end{pmatrix}

המקרה הכללי

ראינו עד כה מקרה מאוד מאוד פרטי של חישוב ע"ע וו"ע עבור מטריצה סיבובית. כעת, נוכל להשתמש בזה כדי למצוא את הע"ע והו"ע של כל מטריצה סיבובית.
נמשיך ונסתכל על המטריצה $C_{1}$ רק שכעת בריבוע:

C_{1}^2=\begin{pmatrix} 0 & 1 & 0 & 0 & \dots & 0 \\ 0 & 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \dots & 1 \\ 1 & 0 & 0 & 0 & \dots & 0 \end{pmatrix}^2=\begin{pmatrix} 0 & 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 0 & 1 & \dots & 0 \\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \dots & 1 \\ 1 & 0 & 0 & 0 & \dots & 0 \\ 0 & 1 & 0 & 0 & \dots & 0 \end{pmatrix}=C_{2}

אנו יודעים כי מתקיים:

A\underline{v}=\lambda \underline{v}\implies A^2\underline{v}=AA\underline{v}=\lambda A\underline{v}=\lambda^2\underline{v}

ולכן ל- $C_{2}$ אותם ע"ע וו"ע של $C_{1}$ .
נמשיך ל- $C_{3}=C_{1}^3$ אשר ממשיך להזיז את האלכסון למעלה. נשים לב כי $C_{1}^n$ היא מטריצת היחידה כאשר $C_{1} \in \mathbb{R}^{n\times n}$ .

נקח כעת מטריצה סיבובית כללית ונפרק אותה למטריצות $C_{i}$ -ים כך:

C=\begin{pmatrix} c_{0} & c_{1} & c_{2} & c_{3} & \dots & c_{n-1} \\ c_{n-1} & c_{0} & c_{1} & c_{2} & \dots & c_{n-2} \\ c_{n-2} & c_{n-1} & c_{0} & c_{1} & \dots & c_{n-3} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ c_{1} & c_{2} & c_{3} & c_{4} & \dots & c_{0} \end{pmatrix}=c_{1}C_{1}+c_{2}C_{1}^2+c_{3}C_{1}^3+\dots+c_{n-1}C_{1}^{n-1}+c_{0}C_{1}^n

מתוך כך נקבל כי:

C=c_{0}I+c_{1}C_{1}+c_{2}C_{1}^2+c_{3}C_{1}^3+\dots+c_{n-1}C_{1}^{n-1}=\sum_{k=0}^{n-1} c_{k}C_{1}^k

זהו פולינום מדרגה $n-1$ הפועל על המטריצה $C_{1}$ ומקדמיו הם איברי השורה הראשונה במטריצה $C$ .

נזכר במשפט מאלגברה אמ:

משפט

נניח כי $\lambda \in \mathbb{C}$ הוא ע"ע של המטריצה $A$ עם ו"ע תואם $\underline{v}$ המקיימים $A\underline{v}=\lambda \underline{v}$ .
יהי פולינום כללי $p_{n}(x)\in \mathbb{F}_{n}[x]$ .
אזי $p_{n}(\lambda)$ הינו ע"ע של המטריצה $p_{n}(A)$ עם אותו ו"ע $\underline{v}$ .

A\underline{v}=\lambda \underline{v}\implies p_{n}(A)\underline{v}=p_{n}(\lambda)\underline{v}

לפי משפט זה נוכל להגיד כי עבור מטריצה סיבובית כללית $C$ הו"ע שלה הינם זהים לו"ע של $C_{1}$ והע"ע הינם $p_{n}(\lambda)$ לכל $\lambda$ ע"ע של $C_{1}$ .

מסקנה

תהי $C$ מטריצה סיבובית כללית. אזי, קיימים סקלרים $c_{0},\dots ,c_{n-1}\in \mathbb{F}$ כך ש:

C=\sum_{k=0}^{n-1}c_{k}C_{1}^k

ומתקיים כי הו"ע של $C$ זהים לו"ע של $C_{1}$ עם הע"ע:

\lambda_{\ell}=\sum_{k=0}^{n-1}c_{k}\alpha_{\ell}^k=\sum_{k=0}^{n-1} c_{k}w_{n}^{-k\ell}\quad \forall 0\leq \ell \leq n-1

כעת, על מנת לסיים להוכיח את המשפט מלמעלה, נרצה רק להראות כי הו"ע מהווים סט אורתונורמלי.

הערה

בפרק זה, נשנה קצת את ההגדרה של הנורמה על מנת לתמוך במספרים מרוכבים:

\left\lVert \underline{u} \right\rVert _{2}^2=\underline{u}^H\underline{u}

כאשר $H$ מבצע טרנספוז ואז עושה צמוד מרוכב לכל איבר.

נסתכל על המכפלה הפנימית בין שני ו"ע שונים שמצאנו:

\underline{v}_{k}^H\underline{v}_{j}=\sum_{m=0}^{n-1} w_{n}^{mk}w_{n}^{-mj}=\sum_{m=0}^{n-1}w_{n}^{m(k-j)}=\sum_{m=0}^{n-1}(w_{n}^{k-j})^m

נשים לב כי זה סכום הנדסי ולכן מתקיים:

\underline{v}_{k}^H\underline{v}_{j}=\frac{1-w_{n}^{n(k-j)}}{1-w_{n}^{k-j}}=\frac{1-e^{2\pi(k-j)i}}{1-e^{\frac{2\pi(k-i)}{n}i}}

עבור $k=j$ מתקיים כי $\underline{v}_{k}^H\underline{v}_{j}=n$ ועבור $k\neq j$ מתקיים כי $\underline{v}_{k}^H\underline{v}_{j}=0$ ולכן הוקטורים אורתוגונליים.
ננרמל אותם ע"י חלוקה ב- $\sqrt{ n }$ ואז הם גם יהיו אורתונורמליים.

בכך, סיימנו את הוכחת המשפט :O

מסקנה

בהינתן מטריצה סיבובית כלשהי $C$ , המטריצה האורתונורמלית הבאה $W$ מלכסנת אותה:

W=\frac{1}{\sqrt{ n }}\begin{pmatrix} 1 & 1 & 1 & 1 & \dots & 1 \\ 1 & w_{n}^{-1} & w_{n}^{-2} & w_{n}^{-3} & \dots & w_{n}^{-(n-1)} \\ 1 & w_{n}^{-2} & w_{n}^{-4} & w_{n}^{-6} & \dots & w_{n}^{-2(n-1)} \\ 1 & w_{n}^{-3} & w_{n}^{-6} & w_{n}^{-9} & \dots & w_{n}^{-3(n-1)} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & w_{n}^{-(n-1)} & w_{n}^{-2(n-1)} & w_{n}^{-3(n-1)} & \dots & w_{n}^{-(n-1)^2} \end{pmatrix}

A=W^HCW

הערה

המטריצה $W$ סימטרית ולכן, $W^H$ היא בעצם לקיחת את הצמוד הקומפלקסי לכל איבר.

נשים לב לעוד דבר, והוא במציאת הע"ע.

\begin{pmatrix} \lambda_{0} \\ \lambda_{1} \\ \lambda_{2} \\ \lambda_{3} \\ \lambda_{4} \\ \vdots \\ \lambda_{n-1} \end{pmatrix}=\begin{pmatrix} 1 & 1 & 1 & 1 & \dots & 1 \\ 1 & w_{n}^{-1} & w_{n}^{-2} & w_{n}^{-3} & \dots & w_{n}^{-(n-1)} \\ 1 & w_{n}^{-2} & w_{n}^{-4} & w_{n}^{-6} & \dots & w_{n}^{-2(n-1)} \\ 1 & w_{n}^{-3} & w_{n}^{-6} & w_{n}^{-9} & \dots & w_{n}^{-3(n-1)} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & w_{n}^{-(n-1)} & w_{n}^{-2(n-1)} & w_{n}^{-3(n-1)} & \dots & w_{n}^{-(n-1)^2} \end{pmatrix}\begin{pmatrix} c_{0} \\ c_{1} \\ c_{2} \\ c_{3} \\ c_{4} \\ \vdots \\ c_{n-1} \end{pmatrix}=\sqrt{ n }W\underline{c}

כלומר, אותה מטריצה ששימשה ללכסון היא גם זו שאיתה נוכל לחשב את הע"ע מתוך השורה הראשונה של $C$ .

למטריצה $W$ זו יש שימוש מאוד מעניין ונראה אותו עכשיו:

התמרת הפורייה הדיסקרטית

הגדרה 6 (מטריצת פורייה)

המטריצה $W$ שראינו נקראת מטריצת פורייה והכפלתה בווקטור $\underline{c}$ נקראת התמרת הפורייה הדיסקרטית המניבה ווקטור תוצאה $\underline{d}$ בעל אותו אורך $n$ .

מסקנה

פעולת ה- $DFT$ נתונה ע"ע $\underline{d}=W\underline{c}$ או בצורה מפורשת יותר:

\left\{ d_{\ell}=\frac{1}{\sqrt{ n }}\sum_{k=0}^{n-1}c_{k}w_{n}^{-\ell k} \right\}_{\ell=0}^{n-1}

משמעות הדבר היא שחישוב ע"ע של מטריצה סיבובית $C$ (עד כדי קבוע) אינו אלא חישוב התמרת הפורייה הדיסקרטית על איברי שורתה הראשונה.

להתמרת הפורייה הדיסקרטית מגוון תכונות מעניינות. אנחנו נראה שתיים מתוכן שיותר רלוונטיות לנו.

משפט (תכונה

\mathrm{I}

)

בהינתן שני וקטורים $\underline{a},\underline{b} \in \mathbb{F}^n$ מתקיים כי:

\text{DFT}\left\{ \underline{a} \right\}\cdot \text{DFT}\left\{ \underline{b} \right\}=\text{DFT}\left\{ \underline{a}\underset{c}{\otimes} \underline{b} \right\}

מסקנה

\underline{a} \underset{c}{\otimes}\underline{b}=\text{DFT}^{-1}\left\{ \text{DFT}\left\{ \underline{a} \right\}\cdot\text{DFT}\left\{ \underline{b} \right\} \right\}

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

הוכחה של המשפט:
קונבולוציה סיבובית בין $\underline{a}$ ל- $\underline{b}$ ניתנת גם לכתיבה בעזרת בניית המטריצה הסיבובית $B$ מהוקטור $\underline{b}$ והכפלתה ב- $\underline{a}$ :

\underline{a} \underset{c}{\otimes}\underline{b}=B^t\underline{a}

נבצע את התמרת פורייה הדיסקרטית על שני החלקים של המשוואה:

\text{DFT}\left\{ \underline{a}\underset{c}{\otimes}\underline{b} \right\}=WB^t \underline{a}=WB^t \underbrace{W^HW}_{I}\underline{a}=WB^tW^H\cdot \text{DFT}\left\{ \underline{a} \right\}

שכן $W\underline{a}=\text{DFT}\left\{ \underline{a} \right\}$ .

(WB^tW^H)^t=(W^H)^tBW^t \underset{\begin{matrix} \downarrow \\ W=W^t \\ (W^H)^t=W^H \end{matrix}}{=}W^HBW

מכיוון שהביטוי שהתקבל שווה לפעולת הכלסון שהינה מטריצה אלכסונית, מתקיים השוויון $WB^tW^H=W^HBW$ ולכן:

\text{DFT}\left\{ \underline{a}\underset{c}{\otimes}\underline{b} \right\}=diag( \text{DFT}\left\{ \underline{b} \right\})\cdot\text{DFT}\left\{ \underline{a} \right\}

∎

נשים לב כי כעת, ביצוע של התמרת פורייה דיסקרטית דורשת $\Theta(n^2)$ פעולות. זה לא טוב ולכן נרצה לייעל זאת. פה מגיע המשפט הבא:

טענה

ניתן להכפיל במטריצה $W$ ביעילות $\Theta (n\log n)$ ע"י אלגוריתם בשם התמרת פורייה מהירה( $FFT$ ).

הוכחה:
נניח כי $n$ הוא חזקה של $2$ ונפצל את הסכימה בהגדרת התמרת הפורייה הדיסקרטית לזוגיים ואי זוגיים.

d_{\ell}=\sum_{k=0}^{n-1} c_{k}w_{n}^{-\ell k}=\left( \sum_{k=0,2,4,\dots}^{n-1} c_{k}w_{n}^{-\ell k}+\sum_{k=1,3,5,\dots}^{n-1}c_{k}w_{n}^{-\ell k} \right) \!\!\!\!\!\underset{\begin{matrix} \uparrow \\ j=\frac{k}{2} \lor j=\frac{k-1}{2} \end{matrix}}{=}\!\!\!\!\!\left( \sum_{j=0}^{\frac{n}{2}-1}c_{2j}w_{n}^{-j\ell}+\sum_{j=0}^{\frac{n}{2}-1}c_{2j+1}w_{n}^{-(2j+1)e^{ ll }} \right)

נשים לב כי מתקיים:

w_{n}^{-2j\ell}=\exp \left\{ -\frac{2\pi i}{n}\cdot2j\ell \right\}=\exp \left\{ -\frac{2\pi i}{\frac{n}{2}}\cdot j\ell \right\}=w_{\frac{n}{2}}^{-j\ell}

ולכן:

d_{\ell}=\left( \sum_{j=0}^{\frac{n}{2}-1} c_{2j}w_{\frac{n}{2}}^{-j\ell}+w_{n}^{-\ell}\sum_{j=0}^{\frac{n}{2}-1} c_{2j+1}w_{\frac{n}{2}}^{-j\ell} \right)={\Large(}\text{DFT}\left\{ \underline{c}_{even} \right\}+w_{n}^{-\ell}\text{DFT}\left\{ \underline{c}_{odd} \right\}{\Large)}

קיבלנו כי את ה- $DFT$ ה- $n$ מימדי ניתן לקבל ע"י שתי פעולות $DFT$ במימד $\frac{n}{2}$ ובינהם אוסף של $n$ פעולות "מיזוג".
ניתן לנצל קשר זה ולהמשיך רקורסיבית בפיצול כל וקטור לשני חלקים באופן דומה.
∎

הערה

כשנציב $\frac{n}{2}\leq \ell\leq n$ בשתי הסכימות הללו, נקבל פשוט מחזוריות. כלומר, איברי הסדרות שיתקבלו ישמשו פעמיים.

בואו נחשב את סיבוכיות האלגוריתם הרקורסיבי $T(n)$ של $DFT$ ב- $n$ מימדים.

T(n)=2T\left( \frac{n}{2} \right)+n \implies T(n)=n\log_{2} n

אין ספק שזה הרבה יותר טוב מ- $n^2$ פעולות :)

הערה

שימושים של התמרת הפורייה רואים בתרגול (לא הסמסטר)

6 - התמרת פורייה

אלגוריתמים נומריים

התמרת פורייה

6 - התמרת פורייה

אלגוריתמים נומריים

התמרת פורייה

משפחות של מטריצות

מטריצות טופוליץ

מטריצות סיבוביות

לכסון מטריצות סיבוביות

המקרה הכללי

התמרת הפורייה הדיסקרטית