בלב הסיפור שלנו עומד עוד פעם פירוק. הפירוק הפעם הוא אחד מהחשובים ביותר באלגברה ליניארית והוא פירוק ה- $SVD$ .

A=U\Sigma V^t

זה לא לכסון אך זה כן דומה ללכסון.

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

ערכים עצמיים

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

הגדרה 1 (ערך עצמי ווקטור עצמי)

בהינתן מטריצה ריבועית וממשית בגודל $n \times n$ , הסקלר $\lambda$ נקרא ערך עצמי אם קיים ווקטור $\underline{v} \neq 0$ אשר יקרא וקטור עצמי המקיים:

A\underline{v}=\lambda \underline{v}

נשים לב שאם נמצא וקטור עצמי שאינו טריוויאלי $\underline{v}$ אזי הכפלתו בסקלר מותירה אותו פתרון ראוי למערכת $A\underline{v}=\lambda \underline{v}$ .
לכן מקובל לדרוש שהו"ע יהיו מנורמלים $\left\lVert \underline{v} \right\rVert_{2}=1$ .

כדי למצוא את הע"ע נעשה דבר מאוד פשוט:

A\underline{v}=\lambda \underline{v} \implies A\underline{v}=\lambda I\underline{v} \implies (A-\lambda I)\underline{v}=0

לכן, על הע"ע להיות כאלה שיגרמו למטריצה $A-\lambda I$ להיות לא הפיכה. כלומר, עלינו לדרוש:

\left| A-\lambda I \right|=\left| \lambda I-A \right|=0

ביטוי זה מוביל לפולינום ב- $\lambda$ מדרגה $n$ . זהו הפולינום האופייני.

משפט

$\lambda=a+ib$ ע"ע של $A$ אם ורק אם $\lambda=a-ib$ הינו גם ע"ע של $A$ .

הגדרה 2 (ריבוי אלגברי)

כשערך עצמי מופיע $k$ פעמים כשורש של הפולינום האופייני נאמר כי לערך עצמי זה ריבוי אלגברי $r_{a}=k$ .

הגדרה 3 (ריבוי גיאומטרי)

לערך עצמי בריבוי אלגברי $r_{a}=k$ יש ת"מ של ו"ע ממימד $1\leq r_{g}\leq r_{a}=k$ הקרוי ריבוי גיאומטרי.

דוגמה

ישנה מטריצה שנקראת מטריצת ג'ורדן והיא נראית כך:

A=\begin{pmatrix} \lambda_{0} & 1 & 0 & 0 & \dots & 0 \\ 0 & \lambda_{0} & 1 & 0 & \dots & 0 \\ 0 & 0 & \lambda_{0} & 1 & \dots & 0 \\ 0 & 0 & 0 & \lambda_{0} & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \dots & \lambda_{0} \end{pmatrix}

למטריצה משולשת הדרטרמיננטה היא מכפלת איברי האלכסון ולכן $p(\lambda)=(\lambda-\lambda_{0})^n$ .
כאשר אנו נחפש את הו"ע ונחסיר את $\lambda_{0}$ מהמטריצה נקבל:

(A-\lambda_{0}I)\underline{v}=\begin{pmatrix} 0 & 1 & 0 & \dots & 0 & 0 \\ 0 & 0 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & 1 & 0 \\ 0 & 0 & 0 & \dots & 0 & 1 \end{pmatrix}

הפתרון למערכת זו הוא הוקטור $\underline{v}^t=\begin{pmatrix}1 & 0 & 0 & 0 & \dots & 0\end{pmatrix}$ .
במקרה הזה לע"ע ר"א של $n$ ור"ג של $1$ .

משפט

יהיו $\lambda_{1},\dots,\lambda_{n} \in \mathbb{R}$ ע"ע של המטריצה $A$ . אזי:

|A|=\lambda_{1}\cdot\lambda_{2}\cdots\lambda_{n}

הוכחה: באלגברה אמ.

משפט

יהיו $\lambda_{1},\dots,\lambda_{n} \in \mathbb{R}$ ע"ע של המטריצה $A$ . אזי:

\lambda_{1}+\lambda_{2}+\dots+\lambda_{n}=\operatorname{trace}(A)

הוכחה: באותו המשפט של ההוכחה הקודמת.

משפט

בהינתן מטריצה $A$ עם שני ע"ע בר"א=ר"ג=1 ושונים זה מזה $\lambda_{1} \neq \lambda_{2}$ הו"ע המיוחסים לע"ע הללו $\underline{v}_{1},\underline{v}_{2}$ הינם בהכרח בת"ל.

הוכחה: גם כן באלגברה אמ'.

משפט

בהינתן מטריצה $A$ עם ע"ע שונים זה מזה, הו"ע התואמים להם הינם בהכרח בת"ל ולכן מהווים בסיס למרחב ה- $n$ מימדי.

הגדרה 4 (מטריצה לכסינה)

מטריצה ריבועית $A$ נקראת לכסינה אם קיימת מטריצה הפיכה $S$ ומטריצה אלכסונית $D$ כך שמתקיים:

S^{-1}AS=D

משפט

בהנתן מטריצה ריבועית $A$ כלשהי ומטריצה הפיכה $G$ באותו גודל, המטריצה $G^{-1}AG$ תהיה בעלת אותם ע"ע כשל $A$ .

הוכחה:
נניח כי $\lambda$ ע"ע של $A$ . אזי, קיים ו"ע $\underline{v}$ כך ש- $A\underline{v}=\lambda \underline{v}$ .
נכפול מערכת זו משמאל ב- $G^{-1}$ ונקבל: $G^{-1}A\underline{v}=\lambda G^{-1}\underline{v}$ .
נגדיר $\underline{z}=G^{-1}\underline{v}$ ונקבל כי $G\underline{z}=\underline{v}$ ולכן $G^{-1}AG\underline{z}=\lambda \underline{z}$ .
לכן, $\lambda$ ע"ע של $G^{-1}AG$ עם ו"ע אשר לא מובטח להיות זהה.
∎

פירוק שור( $Schur$ )

משפט

בהינתן מטריצה ריבועית $A$ לכסינה, ניתן למצוא מטריצה אורתונורמלית $Q$ ומטריצה משולשת עליונה $T$ ממשיות כך שיתקיים:

Q^tAQ=T

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

הוכחה:
כיוון שהמטריצה לכסינה, קיימים $S$ ו- $D$ עבורם $S^{-1}AS$ .
נקח את המטריצה $S$ ונפעיל עליה פירוק $QR$ . נקבל $S=QR$ . בשל היות $S$ הפיכה $R$ הפיכה גם כן.
נציב את הפירוק למשוואת הלכסון ונקבל:

S^{-1}AS=(QR)^{-1}A(QR)=R^{-1}Q^tAQR=D

נעביר את ההכפלות של $R$ והיפוכו לאגף השני ונקבל

Q^tAQ=RDR^{-1}=T

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

מטריצות סימטריות וחיוביות מוגדרות

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

כעת, נצמצם את הדיון למטריצות סימטריות בלבד.

משפט

אם המטריצה $A$ ריבועית ממשית וסימטרית אזי:

המטריצה בהכרח לכסינה
כל הע"ע והו"ע שלה ממשיים
הו"ע שלה מהווים סט אורתונורמלי ולכן היא ניתנת ללכסון אורתונורמלי ע"י $Q^tAQ=D$ .

הערה

הפירוק $A=QDQ^t$ נקרא הפירוק הספקטרלי וכלל הערכים העצמיים של מטריצה נקראים הספקטרום שלה.
אין שום קשר בין הפירוק הנ"ל לפירוק $LDL^t$ .

דוגמה

נסתכל על המטריצה הסימטרית הבאה:

A=\begin{pmatrix} 5 & -4 & 2 \\ -4 & 5 & 2 \\ 2 & 2 & -1 \end{pmatrix}

הע"ע והו"ע נתונים ע"י:

\lambda_{1}=9,\underline{v}_{1}=\begin{pmatrix} 1 \\ -1 \\ 0 \end{pmatrix} \qquad \lambda_{2}=3,\underline{v}_{2}=\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} \qquad \lambda_{3}=-3,\underline{v}_{3}=\begin{pmatrix} 1 \\ 1 \\ -2 \end{pmatrix}

ניכר שהווקטורים אנכיים זה לזה.
פירוק שור יראה כך:

A=\begin{pmatrix} \frac{1}{\sqrt{ 2 }} & \frac{1}{\sqrt{ 3 }} & \frac{1}{\sqrt{ 6 }} \\ -\frac{1}{\sqrt{ 2 }} & \frac{1}{\sqrt{ 3 }} & \frac{1}{\sqrt{ 6 }} \\ 0 & \frac{1}{\sqrt{ 3 }} & -\frac{2}{\sqrt{ 6 }} \end{pmatrix}\begin{pmatrix} 9 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & -3 \end{pmatrix}\begin{pmatrix} \frac{1}{\sqrt{ 2 }} & \frac{1}{\sqrt{ 3 }} & \frac{1}{\sqrt{ 6 }} \\ -\frac{1}{\sqrt{ 2 }} & \frac{1}{\sqrt{ 3 }} & \frac{1}{\sqrt{ 6 }} \\ 0 & \frac{1}{\sqrt{ 3 }} & -\frac{2}{\sqrt{ 6 }} \end{pmatrix}

לפירוק הספקטרלי $A=QDQ^t$ יש פרשנות מעניינת:

A\underline{x}=QDQ^t\underline{x}

למה זה מעניין? כי ככה מיקי אלעד החליט.

עוד דבר מעניין שניתן לראות הוא:

{\Large A}=QDQ^t=\begin{pmatrix} \vert & & \vert \\ \underline{v}_{1} & \dots & \underline{v}_{n} \\ \vert & & \vert \end{pmatrix}\begin{pmatrix} \lambda_{1} \\ & \ddots \\ & & \lambda_{n} \end{pmatrix}\begin{pmatrix} - & \underline{v}_{1}^t & - \\ & \vdots \\ - & \underline{v}_{n}^t & - \end{pmatrix}=\Large \sum_{k=1}^n \lambda_{k}\underline{v}_{k}\underline{v}_{k}^t

מטריצה סימטרית היא תמיד סכום של מטריצות סימטריות מדרגה $1$ והן המטריצות שנוצרות מהו"ע וכל אחת מושקלת מהע"ע המותאם לה.
זוהי דרך אחרת לראות מהי המטריצה $A$ .

עכשיו גם חיובית מוגדרת

כיוון ש- $K$ סימטרית קיים לה פירוק פקטרלי. נשתמש בו בהגדרת החיוביות מוגדרת ונקבל:

\begin{align*} \forall \underline{x} \neq0:\; & \underline{x}^tK\underline{x}=\underline{x}^tQDQ^t\underline{x}=(Q^t\underline{x})^tD(Q^t\underline{x})>0 \\ & \underline{z}:=Q^t\underline{x} \\ \forall \underline{z} \neq 0:\; & \underline{x}^tK\underline{x}=\underline{z}^tD\underline{z}=\sum_{k=1}^n \lambda_{k}z_{k}^2 >0 \end{align*}

מה זה דורש על $D$ ? נדרש שכל איברי אלכסון $D$ יהיו חיוביים.
כלומר, כל הע"ע חיוביים.

משפט

אם $K$ סימטרית וחיובית מוגדרת, כל הע"ע שלה חיוביים.
אם היא חיובית חצי מוגדרת, כל ערכיה העצמיים אי-שליליים.

תכונת רילי-ריץ: ע"ע כפתרון לבעיית אופטימיזציה

ראינו ב2 - ריבועים פחותים כיצד אנו לוקחים בעיית שוויון $A\underline{x}=\underline{b}$ והופכים אותה לבעיית אופטימיזציה $\underset{\underline{x}}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert_{2}^2$ .
בפרק זה נראה שגם את המשוואה $A\underline{v}=\lambda \underline{v}$ ניתן לקחת ולהפוך לבעיית אופטימיזציה. לזה קוראים תכונת ריילי-ריץ ואותה נראה כעת.

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

D=\begin{pmatrix} d_{1} & 0 & \dots & 0 \\ 0 & d_{2} & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & d_{n} \end{pmatrix} \qquad \qquad d_{1}\geq d_{2} \geq d_{3}\geq \dots \geq d_{n}\geq 0

נניח כי ברצוננו להביא למקסימום את התבנית הבאה:

\underset{\underline{z}}{\max}q(\underline{z})=\underset{\underline{z}}{\max }\underline{z}^tD\underline{z}=\underset{\underline{z}}{\max} \sum_{k=1}^n d_{k}z_{k}^2

נשים לב כי הביטוי הזה אינו חסום.
נרצה לקבל משהו חסום ולשם כך נוכל לקבוע אילוץ על הוקטור $\underline{z}$ להימצא על כדור היחידה. כלומר, $\underline{z}^t\underline{z}=1$ .
הבעיה שנקבל חסומה שכן $d_{1}$ הוא הגדול באיברי האלכסון של $D$ ואז הפונקציה מקבלת את החסם מלמעלה הבא:

\sum_{k=1}^n d_{k}z^2_{k}\leq \sum_{k=1}^n d_{1}z_{k}^2=d_{1}\sum_{k=1}^n z_{k}^2=d_{1}

הפונקציה חסומה ובנוסף, ניתן למצוא את הוקטור $\underline{z}$ שיביא אותנו לסופרמום ובכך הוא יהיה מקסימום:

\underline{z}^t=\begin{pmatrix} 1 & 0 & 0 & 0 & \dots & 0 \end{pmatrix}

נשים לב כי זהו הו"ע שמתייחס לע"ע $d_{1}$ במטריצה $D$ .

כעת, אם נחליף את בעיית המקסימיזציה שלנו לבעיית מנימיזציה כאשר במקום $d_{1}$ נקח את $d_{n}$ כך:

\forall \underline{z}^t\underline{z}=1:\;\;\; \underset{\underline{z}}{\min}\underline{z}^tD\underline{z}\leq d_{n}

האם דבר זה נכון גם למטריצות חיוביות מוגדרות שהן לאו דווקא אלכסוניות?
תהי $A$ מטריצה סימטרית וחיובית חצי מוגדרת. אזי קיים לה פירוק ספקטרלי $A=QDQ^t$ .
נתבונן בבעיה $\arg \underset{\left\lVert \underline{x} \right\rVert_{2}=1}{\max} \underline{x}^tA\underline{x}$ . נוכל לפרק זאת עם הפירוק:

\arg \underset{\left\lVert \underline{x} \right\rVert_{2}=1}{\max} \underline{x}^tA\underline{x}=arg \underset{\left\lVert \underline{x} \right\rVert_{2}=1 }{\max} (Q^t\underline{x})^tD(Q^t\underline{x})=arg \underset{\left\lVert \underline{z} \right\rVert_{2}=1 }{\max} \underline{z}^tD\underline{z}

ברור שהמקסימום של הבעיה שהתקבלה הוא $\lambda_{1}$ שהוא הע"ע הגדול ביותר של $A$ (וגם איבר האלכסון הגדול ביותר של $D$ )

משפט

למטריצה חיובית חצי מוגדרת $A$ בגודל $n$ על $n$ בעלת ע"ע $\lambda_{1}\geq \lambda_{2}\geq \dots\geq \lambda_{n}\geq 0$ וו"ע תואמים להם $\underline{v}_{1},\dots,\underline{v}_{n}$ מתקבל כי:

\begin{matrix} \underset{\left\lVert \underline{x} \right\rVert_{2}=1 }{\max}\underline{x}^tA\underline{x}=\lambda_{1} & arg \!\!\underset{\left\lVert \underline{x} \right\rVert_{2}=1 }{\max} \underline{x}^tA\underline{x}=\underline{v}_{1} \\ \underset{\left\lVert \underline{x} \right\rVert_{2}=1 }{\min}\underline{x}^tA\underline{x}=\lambda_{n} & arg \!\!\underset{\left\lVert \underline{x} \right\rVert_{2}=1 }{\min} \underline{x}^tA\underline{x}=\underline{v}_{n} \end{matrix}

ניתן לנסח את הבעיית האופטימיזציה בדרך אחרת:

\begin{align*} \underline{x}^*&=arg\underset{\left\lVert \underline{x} \right\rVert_{2}=1 }{ \max}\underline{x}^tA\underline{x}=arg\underset{\underline{x}\neq0}{\max} \left( \frac{\underline{x}}{\left\lVert \underline{x} \right\rVert_{2} } \right)^tA\left( \frac{\underline{x}}{\left\lVert \underline{x} \right\rVert_{2} } \right)=arg\underset{\underline{x}\neq0}{\max} \frac{\underline{x}^tA\underline{x}}{\left\lVert \underline{x} \right\rVert_{2} }=arg\underset{\underline{x}\neq0}{\max} \frac{\underline{x}^tA\underline{x}}{\underline{x}^t\underline{x}} \end{align*}

לדבר הזה קוראים מנת ריילי ובתרגול נראה שימוש שלה.

דרך הסתכלות נוספת

נשכח את כל מה שעשינו עד כה ונתבונן בביטוי הבא:

f(\underline{x})=\frac{\underline{x}^tA\underline{x}}{\underline{x}^t\underline{x}}

נגזור כפי שראינו בריבועים הפחותים ונקבל:

\nabla_{\underline{x}}f(\underline{x})=2 \frac{A\underline{x}(\underline{x}^t\underline{x})-\underline{x}(\underline{x}^tA\underline{x})}{(\underline{x}^t\underline{x})^2}=0

A\underline{x}=\frac{\underline{x}^tA\underline{x}}{\underline{x}^t\underline{x}}\underline{x}

נשים לב כי הגענו לאותה המסקנה בדרך מאוד שונה.

מוצאים את כל הע"ע

ראינו עד כה כלי למציאת הע"ע הקיצוניים - הגדול ביותר והקטן ביותר. נרצה כעת למצוא את שאר הע"ע.
נניח כי מצאנו את $k$ הע"ע הגדולים ביותר ואת הו"ע שלהם ורצוננו בע"ע הבא ובו"ע שלו.
נאסוף את $k$ הו"ע הללו כעמודותיה של המטריצה $U$ ונגדיר בעיה חדשה:

\underset{\underline{x}\neq0,\;\; U^t\underline{x}=0}{\arg \min} \frac{\underline{x}^tA\underline{x}}{\underline{x}^t\underline{x}}

כיוון שהו"ע למטריצות חיוביות חצי מוגדרות מהווים בסיס אורתונורמלי, האילוץ יכווץ את הבעיה לו"ע הבא המתייחס ל- $\lambda_{k+1}$ .

ערכים ע"ע מוכללים

כעת, נכליל את בעיית האופטימיזציה ע"י שינוי הביטוי במכנה כך:

\underline{x}^*=\underset{\underline{x} \neq 0}{\arg \max} \frac{\underline{x}^tA\underline{x}}{\underline{x}^tB\underline{x}}

כאשר $B$ חיובית מוגדרת על מנת להבטיח שהמכנה לא מתאפס.

נפתור בעיה זו ע"י גזירה והשוואה לאפס כך:

\nabla f(\underline{x})=\nabla \frac{\underline{x}^tA\underline{x}}{\underline{x}^tB\underline{x}}=2 \frac{(A\underline{x})(\underline{x}^tB\underline{x})-(B\underline{x})(\underline{x}^tA\underline{x})}{(\underline{x}^tB\underline{x})^2}=0

אזי נקבל:

A\underline{x}=\frac{\underline{x}^tA\underline{x}}{\underline{x}^tB\underline{x}}B\underline{x} \implies A\underline{x}=\lambda B\underline{x}

זוהי בעיית ערכים עצמיים מוכללת או בעיית עפרון.
הבעיה מציגה לנו מצב בו הפעלה של $A$ על $\underline{x}$ זהה להפעלה של $B$ על $\underline{x}$ ואז כפולה בסקלר.
השוני העיקרי בבעיה זו ממה שראינו הוא שהאילוץ שלנו על $\underline{x}$ שונה. מקודם $\underline{x}^t\underline{x}$ נבע מעובדה שדרשנו $\langle \underline{x},\underline{x}\rangle =1$ אך כעת, האילוץ יהיה $\underline{x}^tB\underline{x}=1$ שזוהי סוג של מכפלה פנימית אחרת המוגדרת על $\mathbb{R}^n$ . הפיתוח של זה יראה זהה לפיתוח שראינו ממקודם רק עם $\underline{x}^tB\underline{x}$ במקום $\left\lVert \underline{x} \right\rVert_{2}$ .
האילוץ הזה יוצר סוג של אליפסואיד של ע"ע מתאימים.

הערה

מכיוון ש- $B$ חיובית מוגדרת, אזי, לפי משפט, היא הפיכה ולכן נוכל להמיר את הבעיה הזו לבעיית ע"ע רגילה:

A\underline{x}=\lambda B\underline{x} \implies B^{-1}A\underline{x}=\lambda \underline{x}

פירוק SVD

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

ערכים סינגולריים

תהי $\underset{m\times n}{A}$ . נניח כי $m\geq n$ ודרגת המטריצה מלאה.
נבנה את מטריצת הגרם $A^tA$ שגודלה $n\times n$ והיא חיובית מוגדרת.
למטריצה זו קיימים ע"ע וו"ע המקיימים:

A^tA\underline{v}_{k}=\lambda_{k}\underline{v}_{k}

קבוצת כל הו"ע של $A^tA$ מהווים בסיס אורתונורמלי למרחב ה- $n$ מימדי. כמו כן, גם לכל ע"ע $\lambda$ מתקיים בהכרח $\lambda>0$ .

נתסכל על תמונה של אחד הו"ע של $A^tA$ כאשר אנו מפעילים עליו רק את $A$ . אזי מתקבל וקטור ארוך יותר כך:
4 - ערכים עצמיים וסינגולריים 2026-06-15 11.45.25.excalidraw.svg
כעת, נקח שני וקטורים שונים ונבצע עליהם את הנ"ל ונמצא את המכפלה הפנימית שלהם:

\langle A\underline{v}_{j},A\underline{v}_{k}\rangle= (A\underline{v}_{j})^t(A\underline{v}_{k})=\underline{v}_{j}^t \underbrace{A^tA\underline{v}_{k}}_{\lambda_{k}\underline{v}_{k}}=\lambda_{k}\underline{v}_{j}^t\underline{v}_{k}

ראינו ממקודם כי הע"ע של $A^tA$ הינם אורתונורמליים ולכן:

\langle A\underline{v}_{j},A\underline{v}_{k}\rangle=\begin{cases} \lambda_{k} & k=j \\ 0 & k\neq j \end{cases}

תוצאה זו בעצם מגלה לנו כי אנו יוצרים קבוצה של וקטורים אורתוגונליים במימד $m$ .
נרצה כעת כמובן לנרמל אותם כדי לקבל וקטורים אורתונורמליים. את הערך הדורש לנרמול נסמן ב- $\sigma_{k}^2$ ונקרא לא ערך סינגורלי.

הגדרה 5 (ערך סינגולרי)

תהי מטריצה $A \in \mathbb{R}^{m\times n}$ .
יהי $\lambda_{i}$ ע"ע של המטריצה $A^tA$ . אזי, הערך הסינגולרי $\sigma_{i}$ מוגדר להיות השורש הריבועי החיובי של $\lambda_{i}$ .

\sigma_{i}=\sqrt{ \lambda_{i} }

הערה

נשים לב כי $A^tA$ חיובית מוגדרת ולכן, לפי משפט, הע"ע שלה חיוביים ולכן, לא תהיה לנו בעיה עם השורש.

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

\underline{u}_{k}=\frac{A\underline{v}_{k}}{\left\lVert A\underline{v}_{k} \right\rVert_{2} }=\frac{A\underline{v}_{k}}{\sigma_{k}}

נסתכל על זה ויזואלית כדי להבין יותר טוב:
4 - ערכים עצמיים וסינגולריים 2026-06-15 11.58.46.excalidraw.svg

\LARGE \forall 1\leq k\leq n:\;\;\;\; A\underline{v}_{k}=\sigma_{k}\underline{u}_{k}

הקשר שקיבלנו פה הוא דומה מאוד לקשר בין ע"ע למטריצה( $A\underline{v}=\lambda \underline{v}$ ) אך יש הבדלים מהותיים ביניהם:

המטריצה $A$ יכולה להיות בכל צורה
ערך סינגולרי הוא תמיד אי שלילי
הוקטורים בשני האגפים מהווים בסיס אורתונורמלי אך למרחבים שונים

מפרקים מטריצות

הצעד הטבעי הבא יהיה לאחד את כל המשוואות לאחת:

\left\{ \begin{matrix} A\underline{v}_{1}=\sigma_{1}\underline{u}_{1} \\ A\underline{v}_{2}=\sigma_{2}\underline{u}_{2} \\ \vdots \\ A\underline{v}_{n}=\sigma_{n}\underline{u}_{n} \end{matrix} \right\}

נסתכל על אגף שמאל ונשים אותו בעמודות מטריצה כך:

\begin{pmatrix} \vert & \vert & & \vert \\ A\underline{v}_{1} & A\underline{v}_{2} & \dots & A\underline{v}_{n} \\ \vert & \vert & & \vert \end{pmatrix}={\color{orange} A}{\color{red}\begin{pmatrix} \vert & \vert & & \vert \\ \underline{v}_{1} & \underline{v}_{2} & \dots & \underline{v}_{n} \\ \vert & \vert & \dots & \vert \end{pmatrix}}={\color{orange} A}{\color{red}V}

נשים לב כי המטריצה $A$ מלבנית והמטריצה $V$ החדשה הזו היא מטריצה אורתונורמלית וריבועית בגודל $n\times n$ .

נעבוד באותה דרך עבור אגף ימין כך:

\begin{pmatrix} \vert & \vert & & \vert \\ \sigma_{1}\underline{u}_{1} & \sigma_{2}\underline{u}_{2} & \dots & \sigma_{n}\underline{u}_{n} \\ \vert & \vert & & \vert \end{pmatrix}={\color{blue}\begin{pmatrix} \\ \vert & \vert & & \vert \\ \underline{u}_{1} & \underline{u}_{2} & \dots & \underline{u}_{n} \\ \vert & \vert & & \vert \\ \\ \end{pmatrix}}{\color{purple}\begin{pmatrix} \sigma_{1} & 0 & \dots & 0 \\ 0 & \sigma_{2} & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & \sigma_{n} \end{pmatrix}}={\color{blue}U}{\color{purple}\Sigma}

המטריצות שקיבלנו הינן מעניינות מאוד:

$U$ היא מטריצה גבוהה מאוד בגודל $m\times n$ אשר עמודותיה אורתונורמלית(אך היא לא מטריצה אורתונורמלית שכן היא לא ריבועית)
$\Sigma$ היא מטריצה אלכסונית בגודל $n\times n$ .

מה קיבלנו?
עבור מטריצה $A$ בגודל $m\times n$ כאשר $m\geq n$ מדרגה מלאה מתקבל:

\LARGE AV=U\Sigma \implies {\color{orange}A}={\color{blue}U}{\color{purple}\Sigma} {\color{red}V^t}

(הטרנספוז הוא כי $V$ אורתונורמלית)
4 - ערכים עצמיים וסינגולריים 2026-06-15 12.14.13.excalidraw.svg

אנחנו לא אוהבים מטריצות שהם לא אורתונורמליות ולכן, נבצע השלמה למטריצה אורתונורמלית עם המשך רנדומלי לתהליך גרם שמידט.
4 - ערכים עצמיים וסינגולריים 2026-06-15 12.19.30.excalidraw.svg
זהו פירוק ה- $SVD$ והדבר היחיד שבגללו נבוא אליו בטענות הוא שהוא מוגבל.
מיד אנו נראה כי הוא תקף לכל מטריצה שהיא.

סיכום בניית ה-SVD

חישוב המטריצה $A^tA$
ביצוע פירוק ספקטרלי וקבלת $\left\{ \lambda_{k},\underline{v}_{k} \right\}_{k=1}^n$
איסוף כל הו"ע הנ"ל כשורותיה של מטריצה וזוהי $V^t$
הוצאת שורש לע"ע ואלה יאכלסו את אלכסונה של $\Sigma$
חישוב $\underline{u}_{k}=A\underline{v}_{k}$ ונירמולם עבור $k=1,\dots,n$ ואלה יהיו עמודותיה של $U$ .
השלמת $U$ עם וקטורים אורתונורמליים נוספים מתאימים על פי האלגוריתם שלמדנו לפירוק $QR$ .

עבור מטריצות ללא דרגה מלאה

עד כה הנחנו כי המטריצה $A$ בעלת דרגה מלאה, אך זה לא עוד המצב. כעת נגיד כי $r(A)=r<n$ .
במקרה זה יתקים כי בפירוק הספקטרלי של $A^tA$ נקבל $A^tA\underline{v}_{k}=\lambda_{k}\underline{v}_{k}$ אבל $\lambda_{r+1}=\dots=\lambda_{n}=0$ שכן יש לנו $n$ וקטורים ב- $null\;A$ .
נזכר כי $\underline{u}_{k}=\frac{A\underline{v}_{k}}{\sqrt{ \lambda_{k} }}$ אך פה אנו מחלקים ב- $0$ - זוהי בעיה רצינית. כדי לתקן אותה נחלק את הקבוצה שלנו ל-2:

\left\{ \begin{matrix} A\underline{v}_{1}=\sigma_{1}\underline{u}_{1} \\ \vdots \\ A\underline{v}_{r}=\sigma_{r}\underline{u}_{r} \\ -------- \\ A\underline{v}_{r+1}=\sigma_{r+1}\underline{u}_{r+1} \\ \vdots \\ A\underline{v}_{n}=\sigma_{n}\underline{u}_{n} \end{matrix} \right\}

עבור הקבוצה העליונה נטפל כרגיל ועבור הקבוצה התחתונה נקבע $\sigma_{k}=0$ . (לכל $k \in[r+1,n]$ )
זה נותן לנו להשלים את $\underline{u}_{k}$ במה שאנחנו רוצים כי הם בכל מקרה מוכפלים ל- $0$ ולכן, נבצע את אותו המשך לגרם-שמידט כמו ממקודם.
4 - ערכים עצמיים וסינגולריים 2026-06-15 12.35.23.excalidraw.svg

עכשיו גם מטריצות רחבות

כעת יש לנו $A$ בגודל $m\times n$ כאשר $m<n$ .
אם נשחלף את המטריצה נוכל לקבל את אותו הפירוק. הפעם נקרא למטריצות בשמות הפוכים:

A^t=V\Sigma^tU^t

ואז:

A=U\Sigma V^t

כאשר המטריצות כעת מעט שונות:
4 - ערכים עצמיים וסינגולריים 2026-06-15 12.40.52.excalidraw.svg
המטריצות שקיבלנו פה בעצם הפוכות בסדר שלהם עם טרנספוז בנוסף, אך עדיין נקרא להם בשמות שיתאימו לנו עבור הפירוק.

הפירוק באופן כללי

משפט

תהי $A \in \mathbb{R}^{m\times n}$ כאשר $m,n \in \mathbb{R}$ .
אזי, $A$ ניתנת לפירוק $SV\!D$ מהצורה:

A=U\Sigma V^t

כאשר:

$U$ מטריצה אורתונורמלית בגודל $m\times m$
$V$ מטריצה אורתונורמלית בגודל $n\times n$
$\Sigma$ מטריצה אלכסונית בגודל $m$ על $n$ כאשר איברי אלכסונה אי-שליליים ובמגמת ירידה הנקראים ערכים סינגולריים.

מסקנה

כל מטריצה $A$ מדרגה $r$ תהיה בעלת $r$ ערכים סינגולריים שונים מאפס בדיוק.
כך נוכל למצוא את דרגת המטריצה באמצעות הפירוק.

ניתן לפרק מכפלה של וקטור במטריצה $A$ באמצעות הפירוק $A\underline{x}=U\Sigma V^t\underline{x}$ כך:

תחילה אנו מבצעים סיבוב של הוקטור ע"י $V^t$
לאחר מכן, אנו מותחים אותו בכל ציר ואף יכולים לשנות את מימדו ע"י ההכפלה ב- $\Sigma$
לבסוף, אנו מסובבים אותו שוב פעם, הפעם במימד אחר ע"י $U$ .

מסקנה

כל מטריצה $A$ מדרגה $r$ ניתנת לכתיבה כסכום משוקלל של מטריצות מדרגה אחת לפי:

A=U\Sigma V^t=\sum_{k=1}^r \sigma_{k}\underline{u}_{k}\underline{v}_{k}^t

הערה

אנו לא נתעסק בשיטה הנומרית לבניית הפירוק. (כלומר, באיך באמת עושים את זה במחשב)
בנוסף, גם לא נתעסק בסיבוכיות התהליך שהינה $n^3$ מכפלות.

פירוק SVD אל מול פירוק ספקטרלי

נניח כי נתונה לנו מטריצה $A$ ריבועית, סימטרית וחיובית חצי מוגדרת. נוכל לחשב עבורה פירוק ספקטרלי או פירוק $SV\!D$ .

QDQ^t=A=U\Sigma V^t

נרצה למצוא מהו הקשר בין השניים.
נוכל לגרום להתלכדות בין שני הפירוקים אם מתקיים $U=V=Q,\;\Sigma=D$ . ⟸ במקרה זה הערכים הסינגולריים זהים לע"ע של $A$ וגם הו"ע מתלכדים.

אם נתונה לנו מטריצה ריבועית וסימטרית שאינה חיובית חצי מוגדרת. נוכל לחשב עבורה פירוק ספקטרלי ופירוק $SVD$ .
לא נוכל כעת להגיד כי $\Sigma=D$ כי יכול להיות שב- $D$ ערכים שליליים.
נניח ונקח $\lambda \in \mathbb{R}$ ע"ע ממשי שקיים בהכרח מכיוון שהמטריצה סימטרית, אזי:

A\underline{x}=\lambda \underline{x}\implies A^tA\underline{x}=\lambda A^t\underline{x}=\lambda A\underline{x}=\lambda^2\underline{x}

נשים לב כי הע"ע של $A^tA$ הינם הע"ע בריבוע ⟸ הערכים הסינגולריים יהיו $\sigma=\sqrt{ \lambda^2 }=|\lambda|$ ולכן הם יהיו הע"ע בערך מוחלט.
על מנת להשוות בין שני הפירוקים במצב זה, נקח שתי מטריצות יחידה, ובכל שורה בה במטריצה $D$ הע"ע קטן מאפס, נהפוך את ה- $1$ ל- $-1$ .
נקבל את המטריצות הבאות:

A=QDI^*I^*Q^t \underset{\begin{matrix} \downarrow \\ Q=U \\ DI^*=\Sigma \\ I^*Q^t=V^t \end{matrix}}{=}U\Sigma V^t

כך הגענו מהפירוק הספקטרלי ל- $SV\!D$ .

שימושי הפירוק

פתרון מערכת משווואות

תהי מערכת משוואות $A\underline{x}=\underline{b}$ . נוכל להשתמש בפירוק $SV\!D$ על מנת לפתור אותה. נסתכל על שלושה מקרים:

$A$ ריבועית והפיכה
$A$ מלבנית עם יותר שורות מעמודות
$A$ מלבנית עם יותר עמודות משורות

נניח כי בכל אחד מהמקרים קיים פתרון וננסה לנסח אותו במונחים של $SV\!D$ .

מטריצה ריבועית והפיכה

נתחיל בפירוק $SV\!D$ ל- $A$ כך:

A\underline{x}=\underline{b}=U\Sigma V^t\underline{x}

המטריצות $U$ ו- $V$ אורתונורמליות ולכן נוכל להכפיל ב- $U^t$ ו- $V^t$ בהתאמה. בנוסף, המטריצה $\Sigma$ היא אלכסונית אז להפוך אותה זו לא בעיה ולכן:

\underline{x}=V\Sigma^{-1}U^t\underline{b}

נשים לב כי הפירוק שקיבלנו כעת $V\Sigma^{-1}U^t$ הוא הפירוק עבור $A^{-1}$ . כלומר, גם ל- $A^{-1}$ יש פירוק $SV\!D$ .
ישנו פגם אחד בפירוק הזה הוא שב- $\Sigma^{-1}$ הע"ע אינם בסדר יורד כפי שאנו רוצים.
(מיקי אלעד: "בתי הכלא מלאים באנשים שהפכו מטריצות. קיבלנו מערכת משוואות הפכו מטריצות. הם אנשים רשעים והם משלמים מחיר")

יותר שורות מעמודות

פה המטריצה גבוהה ולכן, יש יותר משוואות מאשר פתרונות. נבצע פירוק $SV\!D$ גם כן:

A\underline{x}=\underline{b}=U\Sigma V^t\underline{x}

נכפיל את $\underline{b}$ ב- $U^t$ ונקבל וקטור $\underline{\hat{b}}$ שמקיים:

\underline{\hat{b}}=U^t\underline{b}=\Sigma V^t\underline{x}

בחלק התחתון של $\Sigma$ יש אפסים כפי שראינו ממקודם ולכן בהכרח השורות התחתונות של $\underline{\hat{b}}$ חייבות להיות אפסים על מנת שיהיה פתרון.
נניח כרגע כי יש אפסים בחלק התחתון של $\underline{\hat{b}}$ . ממקודם הכפלנו ב- $\Sigma^{-1}$ אבל פה לא נוכל לעשות זאת שכן הגודל לא מתאים. נתקן את $\Sigma^{-1}$ ע"י הוספת עמודות אפסים אליה. נקרא למטריצה החדשה $\text{"}\Sigma^{-1}\text{"}$ ואז:

\underline{x}=V\;\text{"}\Sigma^{-1}\text{"}\;U^t\underline{b}

[להוסיף ציור אם יש לי זמן]

יותר עמודות משורות

במצב זה בהכרח יש לנו $\infty$ פתרונות שכן יש דרגות חופש.

\underline{b}=A\underline{x}=U\Sigma V^t\underline{x}

נגדיר $\underline{z}=V^t\underline{x}$ ואז:

U^t\underline{b}=\underline{\hat{b}}=\Sigma \underline{z}

פה פשוא אפשר למצוא את $\underline{\hat{b}}$ ואז למצוא את $\underline{z}$ ובכך למצוא את $\underline{x}$ .

מכל האפשרויות לבחירת $\underline{z}$ נרצה להסתכל על $\underline{z}$ הקצר ביותר ב- $L_{2}$ . כלומר, זה שתחתיתו אפסים.
נשים לב כי הפתרון הקצר ביותר עבור $\underline{z}$ מוביל לפתרון $\underline{x}$ הקצר ביותר כי הקשר בין שניהם הוא $\underline{x}=V\underline{z}$ כאשר $V$ אותרתונורמלית.
נרצה למצוא נוסחה קומפקטית ל- $\underline{z}$ הקטן ביותר:

נתחיל בלהכפיל את $\underline{b}$ ב- $U^t$ ואז להכפיל ב- $\Sigma^{-1}$ עם הוספת שורות אפסים ללמטה של $\Sigma^{-1}$ ואז: $\underline{x}=V\;\text{"}\Sigma^{-1}\text{"}\;U^{t}\underline{b}$

נשים לב כי אנו הגענו בדיוק לאותה נוסחה כל פעם, למעט שינויים קטנים ל- $\Sigma^{-1}$ .

מקסנה

נזכר כי הסיבוכיות של פתרון מערכת משוואות בעזרת פירוק LU הוא $\frac{n^3}{6}$ ולכן, לפתרון מערכת משוואות הוא עדיף על ה- $SV\!D$ .
אך במה הפירוק החדש כן עדיף? תכף נראה בריבועים פחותים איך נוכל להשתמש בו ביעילות.

פתרון בעיית ריבועים פחותים

נתונה לנו $\underset{\underline{x}}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert_{2}^2$ ונניח כי היא בעלת פתרון יחיד.
אזי, הפתרון למשוואה נתון ע"י המשוואה הנורמלית: $\underline{x}=A^{\dagger}\underline{b}=(A^tA)^{-1}A^t\underline{b}$ .
כעת, נבנה את ההפיכוך המוכלל של $A$ באמצעות פירוק ה- $SV\!D$ כך:

A^{\dagger}=(A^tA)^{-1}A^t=(V\Sigma^tU^tU\Sigma V^t)^{-1}V\Sigma^tU^t=(V\Sigma^t\Sigma V^t)^{-1}V\Sigma^{t}U^t

המטריצות $V,V^t$ ו- $\Sigma^t\Sigma$ הינן ריבועיות והפיכות ולכן:

A^{\dagger}=V(\Sigma^{-1}\Sigma)^{-1}V^tV\Sigma^tU^t=V(\Sigma^t\Sigma)^{-1}\Sigma^tU^t

נשים לב כי נוצר לנו ביטוי באמצע שהוא מעניין $(\Sigma^t\Sigma)^{-1}\Sigma^t$ . נשים לב כי בעצם $\Sigma ^{\dagger}=(\Sigma^t\Sigma)^{-1}\Sigma^t$ ולכן:

A^{\dagger}=V\Sigma ^{\dagger}U^t

קיבלנו בעצם כי:

\underline{x}=A^{\dagger}\underline{b}=V\Sigma ^{\dagger}U^t\underline{b}

מסקנה

היפוך מוכלל של $A$ אינו אלא היפוך הערכים הסינגולריים ושינוי סדר המכפלה וקל מאוד לקבלו מפירוק ה- $SV\!D$ של $A$ .

כעת, בבעית הריבועים הפחותים שלנו יש $\infty$ פתרונות (כלומר, $A$ בעלת דרגה $r<n$ )
כל הפתרונות נדרשים לקיים את המשוואה הנורמלית: $A^tA\underline{x}=A^t\underline{b}$ . נשתמש בפירוק ונראה לאן אנו מגיעים:

V\Sigma^tU^tU\Sigma V^t\underline{x}=V\Sigma ^tU^t\underline{b}

V\Sigma^t\Sigma V^t\underline{x}=V\Sigma^tU^t\underline{b}

נכפיל ב- $V^t$ משני הצדדים ונזכור שהיא אורתונורמלית ואז:

\Sigma^t\Sigma V^t\underline{x}=\Sigma^tU^t\underline{b}

נסמן $\underline{z}=V^t\underline{x}$ ובנוסף $\underline{\hat{b}}=U^t\underline{b}$ ואז:

\Sigma^t\Sigma \underline{z}=\Sigma^tU^t\underline{b}=\Sigma^t \underline{\hat{b}}

\begin{pmatrix} \sigma_{1}^2 \\ & \ddots \\ & & \sigma^2_{r} \\ & & & 0 \\ & & & & \ddots \\ & & & & & 0 \end{pmatrix}\begin{pmatrix} z_{1} \\ \vdots \\ z_{r} \\ z_{r+1} \\ \vdots \\ z_{n} \end{pmatrix}=\left(\begin{array}{c:c} \begin{matrix} \sigma_{1} \\ & \ddots \\ & & \sigma_{r} \\ & & & 0 \\ & & & & \ddots \\ & & & & & 0 \end{matrix} & \LARGE \quad 0 \quad \end{array}\right)\begin{pmatrix} \hat{b}_{1} \\ \hat{b}_{2} \\ \hat{b}_{3} \\ \\ \\ \vdots \\ \\ \\ \hat{b}_{m} \end{pmatrix}

האם ניתן לומר מהו $z_{1}$ ? נוכל לקבל אותו לפי משוואה פשוטה $z_{1}=\frac{\hat{b}_{1}}{\sigma_{1}}$ . משוואה זו מתקיימת עבור $r$ הרכיבים הראשונים:

\sigma^2z_{r}=\sigma _r\hat{b}_{r}\implies z_{r}=\frac{\hat{b}_{r}}{\sigma_{r}}

עבור $z_{r+1},\dots,z_{n}$ הם נפגשים עם אפסים ולכן הם יכולים להיות מה שאנחנו רוצים. לכן, נבחר $0$ כדי שיהיה לנו את הוקטור הקצר ביותר.

הערה

למה ברור כי למערכת $A^tA\underline{x}=A^t\underline{b}$ יש פתרון?

ל- $r$ המשוואות הראשונות תמיד יהיה פתרון שכן לא יכול להיות מצב בו $\sigma_{k}=0$ לפי הגדרת הערכים הסינגולריים.
שאר המשוואות הן פשוט פסוקי אמת $0=0$ ולכן הן לא משנות לנו דבר

בואו נרכיב את הפתרון במונחים של $SV\!D$ :

\underline{x}=V\left(\begin{array}{c:c} \begin{matrix} \sigma_{1}^{-1} \\ & \ddots \\ & & \sigma_{r}^{-1} \\ & & & 0 \\ & & & & \ddots \\ & & & & & 0 \end{matrix} & \LARGE \quad 0 \quad \end{array}\right)U^t\underline{b}

פה נראה שיש לנו יצור מעניין וכדי לתת לו שם נגדיר הכללה להיפוך המוכלל

הגדרה 6 (הרחבה להיפוך מוכלל למטריצות אלכסוניות)

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

ואז נקבל:

\underline{x}=A^{\dagger}\underline{b}=V\Sigma ^{\dagger}U^t\underline{b}

והיא תהיה המשוואה המתאימה לכל המצבים.

הערה

ראינו בעבר את בעיית הרגולריזציה וראינו שהיא נותנת את הפתרון הקצר ביותר אך הוא לאו דווקא בתוך אוסף הפתרונות של המשוואה הנורמלית המקורית.
עם פירוק ה- $SV\!D$ אנו מקבלים תמיד את הוקטור הקצר ביותר אשר פותר את המשוואה הנורמלית המקורית ופה נמצא הייתרון של פירוק זה על פני המשוואה הנורמלית המקורית או ה- $QR$ שראינו ממקודם.

קירוב מטריצות עם אילוץ דרגה

נזכר כי כל מטריצה ניתנת לפירוק לקבוצה של מטריצות מדרגה אחת:

A=U\Sigma V^t=\sum_{k=1}^r \sigma_{k}\underline{u}_{k}\underline{v}_{k}^t

אנו נרצה למצוא מטריצה $B$ באותו גודל של $A$ כך שתהיה הקרובה ביותר ל- $A$ כאשר דרגתה מוגבלת להיות $k_{0}<r$ .
כלומר, אנו מבקשים פתרון לבעיה: $\underset{B}{\min}dist(A,B)\;\; s.t.\;\; rank(B)=k_{0}\leq r$ .
הדבר הראשון שאנו צריכים לעשות זה להגדיר מרחק בין מטריצות והוא:

הגדרה 7 (נורמת פורביניוס)

תהי מטריצה $A$ .

\left\lVert A \right\rVert_{F}^{2}=\sum_{k=1}^m \sum_{j=1}^n a_{kj}^2=trace(A^tA)=trace(AA^t)

הגדרה 8 (מרחק בין מטריצות)

יהיו מטריצות $A,B$ . אזי:

dist(A,B)=\left\lVert A-B \right\rVert _{F}^{2}=\sum_{k=1}^m \sum_{j=1}^n (a_{kj}-b_{kj})^2

נוכל עכשיו למצוא פתרון לבעיה.

משפט

עבור מטריצה $A$ בעל פירוק $SV\!D$ מהצורה $A=U\Sigma V^t=\displaystyle \sum_{k=1}^r \sigma_{k}\underline{u}_{k}\underline{v}_{k}^t$ עם ערכים סינגולריים בסדר יורד $\sigma_{1}\geq\sigma_{2}\geq\sigma_{3}\geq\dots\geq \sigma_{r}>0$ .
פתרון הבעיה $\underset{B}{\min}dist(A,B)\;\; s.t.\;\; rank(B)=k_{0}\leq r$ הינו:

B=\sum_{k=1}^{k_{0}} \sigma_{k}\underline{u}_{k}\underline{v}_{k}^t

הוכחה: בתרגול

מהי השגיאה שמתקבלת?

\begin{align*} \left\lVert A-B \right\rVert _{F}^{2}=\left\lVert \sum_{k=k_{0}+1}^r \sigma_{k}\underline{u}_{k}\underline{v}_{k}^t \right\rVert _{F}^2&=trace\left\{ \left( \sum_{j=k_{0}+1}^r \sigma_{j}\underline{v}_{j}\underline{u}_{j}^t \right) \left( \sum_{k=k_{0}+1}^r\sigma_{k}\underline{u}_{k}\underline{v}_{k}^t \right)\right\} \\ &=trace \left\{ \sum_{j=k_{0}+1}^r \sum_{k=k_{0}+1}^r \sigma_{j}\sigma_{k}\underline{v}_{j}\underline{v}_{k}\underline{u}_{j}^t\underline{u}_{k}\underline{v}_{k}^t \right\} \\ &=\sum_{j=k_{0}+1}^r \sum_{k=k_{0}+1}^r \sigma_{j}\sigma_{k}trace \left\{ \underline{v}_{j}\underline{u}_{j}^t\underline{u}_{k}\underline{v}_{k}^t \right\} \end{align*}

נזכר כי לאור $\underline{u}$ -ים אורתונורמליים מתקיים כי $\underline{u}_{j}^t\underline{u}_{j}=1$ וכנ"ל עם $\underline{v}_{k}\underline{v}_{k}^t$ לאור העובדה ש- $\mathrm{Tr}(E^tE)=\mathrm{Tr}(EE^t)$ ולכן:

\left\lVert A-B \right\rVert _{F}^2=\sum_{k=k_{0}+1}^r \sigma_{k}^2

הגדרה 9 (מספר מצב)

תהי $A$ מטריצה ריבועית בגודל $n\times n$ . אזי, מספר המצב שלה הינו:

\kappa \left\{ A \right\}=\frac{\sigma_{1}}{\sigma_{n}}

הערה

המושג הזה הומצא ע"י אלן טיורינג.

מספר המצב מספר כמה המטריצה נוטה להיות לא הפיכה.
⟸ נשים לב כי זה מספר גדול או שווה ל- $1$ . כשהוא $1$ מדובר במטריצה אורתונורמלית עד כדי קבוע וכשהוא נוטה ל- $\infty$ מדובר במטריצה לא הפיכה.

4 - ערכים עצמיים וסינגולריים

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

ערכים עצמיים וסינגולריים

4 - ערכים עצמיים וסינגולריים

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

ערכים עצמיים וסינגולריים

ערכים עצמיים

פירוק שור( $Schur$ )

מטריצות סימטריות וחיוביות מוגדרות

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

עכשיו גם חיובית מוגדרת

תכונת רילי-ריץ: ע"ע כפתרון לבעיית אופטימיזציה

דרך הסתכלות נוספת

מוצאים את כל הע"ע

ערכים ע"ע מוכללים

פירוק SVD

ערכים סינגולריים

מפרקים מטריצות

סיכום בניית ה-SVD

עבור מטריצות ללא דרגה מלאה

עכשיו גם מטריצות רחבות

הפירוק באופן כללי

פירוק SVD אל מול פירוק ספקטרלי

שימושי הפירוק

פתרון מערכת משווואות

מטריצה ריבועית והפיכה

יותר שורות מעמודות

יותר עמודות משורות

מקסנה

פתרון בעיית ריבועים פחותים

קירוב מטריצות עם אילוץ דרגה

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

ערכים עצמיים וסינגולריים

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

ערכים עצמיים וסינגולריים

ערכים עצמיים

פירוק שור(SchurSchurSchur)

מטריצות סימטריות וחיוביות מוגדרות

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

עכשיו גם חיובית מוגדרת

תכונת רילי-ריץ: ע"ע כפתרון לבעיית אופטימיזציה

דרך הסתכלות נוספת

מוצאים את כל הע"ע

ערכים ע"ע מוכללים

פירוק SVD

ערכים סינגולריים

מפרקים מטריצות

סיכום בניית ה-SVD

עבור מטריצות ללא דרגה מלאה

עכשיו גם מטריצות רחבות

הפירוק באופן כללי

פירוק SVD אל מול פירוק ספקטרלי

שימושי הפירוק

פתרון מערכת משווואות

מטריצה ריבועית והפיכה

יותר שורות מעמודות

יותר עמודות משורות

מקסנה

פתרון בעיית ריבועים פחותים

קירוב מטריצות עם אילוץ דרגה

פירוק שור( $Schur$ )