MentoraLINEAR 2

שבוע 13 — מטריצות סימטריות ולכסון אורתוגונלי

המשפט הספקטרלי וקירוב בריבועים פחותים

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

רקע — על מה השבוע הזה

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

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

התמונה

לחצי Play או עברי שלב-שלב
קירוב בריבועים פחותים
נקודות מדידה שלא יושבות על אף ישר אחד.

הגדרות (1)

הניסוח המלא מהמצגת
הגדרהמטריצה אורתוגונלית
תהי O∈Mn(R)O\in M_n(\mathbb{R}).
נאמר ש-OO היא מטריצה אורתוגונלית אם עמודות OO הן בסיס אורתונורמלי ל-Rn\mathbb{R}^n.

משפטים ומסקנות (8)

ניסוחים בלבד — ההוכחות בלשונית ההרצאה
משפט 1⟨Ax⃗,y⃗⟩=⟨x⃗,Aty⃗⟩\langle A\vec x,\vec y\rangle=\langle\vec x,A^t\vec y\rangleצריך לדעת להוכיח
תהי A∈Mm×n(R)A\in M_{m\times n}(\mathbb{R}). אזי לכל x⃗∈Rn,y⃗∈Rm\vec x\in\mathbb{R}^n,\vec y\in\mathbb{R}^m מתקיים: ⟨Ax⃗,y⃗⟩=⟨x⃗,Aty⃗⟩\langle A\vec x,\vec y\rangle=\langle\vec x,A^t\vec y\rangle
מסקנה 1העברת מטריצה סימטרית בין רכיבי המכפלה
אם A∈Mn(R)A\in M_n(\mathbb{R}) היא מטריצה סימטרית אז ⟨Ax⃗,y⃗⟩=⟨x⃗,Ay⃗⟩\langle A\vec x,\vec y\rangle=\langle\vec x,A\vec y\rangle
משפט 2משוואת הריבועים הפחותים AtAx⃗0=Atb⃗A^tA\vec x_0=A^t\vec bצריך לדעת להוכיח
תהי A∈Mm×n(R)A\in M_{m\times n}(\mathbb{R}) ויהי b⃗∈Rm\vec b\in\mathbb{R}^m.
יהי x⃗0∈Rn\vec x_0\in\mathbb{R}^n הוקטור שעבורו ∥Ax⃗−b⃗∥\|A\vec x-\vec b\| מינימלי.
אזי: AtAx⃗0=Atb⃗A^tA\vec x_0=A^t\vec b
משפט 3ערכים עצמיים של מטריצה סימטריה ממשית הם ממשייםצריך לדעת להוכיח
תהי A∈Mn(R)A\in M_n(\mathbb{R}) מטריצה סימטרית. יהי λ∈C\lambda\in\mathbb{C} ערך עצמי של AA. אזי λ∈R\lambda\in\mathbb{R}.
מסקנה 2לכל מטריצה סימטרית יש ערך עצמי ממשיצריך לדעת להוכיח
לכל מטריצה סימטרית A∈Mn(R)A\in M_n(\mathbb{R}) יש ערך עצמי ממשי.
משפט 4מרחבים עצמיים של מטריצה סימטרית הם אורתוגונלייםצריך לדעת להוכיח
תהי A∈Mn(R)A\in M_n(\mathbb{R}) מטריצה סימטרית. יהיו λ1,λ2∈R\lambda_1,\lambda_2\in\mathbb{R} שני ערכים עצמיים שונים של AA.
אזי Vλ1,Vλ2V_{\lambda_1},V_{\lambda_2} הם תתי מרחבים אורתוגונליים.
משפט 5OO אורתוגונלית אם"ם OtO=InO^tO=I_nצריך לדעת להוכיח
תהי O∈Mn(R)O\in M_n(\mathbb{R}). אזי OO היא מטריצה אורתוגונלית אם ורק אם OtO=InO^tO=I_n.
משפט 6משפט הפירוק הספקטרלי - ללא הוכחה
תהי A∈Mn(R)A\in M_n(\mathbb{R}) מטריצה סימטרית.
אזי AA לכסינה.
בנוסף, קיימת מטריצה אורתוגונלית O∈Mn(R)O\in M_n(\mathbb{R}) כך ש-OtAOO^tAO היא אלכסונית.

הערות (1)

המשפט הספקטרלי
המשפט הספקטרלי

אם נתון לי… אז אני יודעת

8 מסקנות · זה מה שכותבים בשורה הראשונה של הפתרון
המערכת Ax⃗=b⃗A\vec x=\vec b אינה פתירה, ומבקשים את הפתרון "הכי טוב"
  • מחפשים x⃗0\vec x_0 שממזער את ∥Ax⃗−b⃗∥\|A\vec x-\vec b\|
  • x⃗0\vec x_0 מקיים את משוואת הריבועים הפחותים AtAx⃗0=Atb⃗A^tA\vec x_0=A^t\vec b (משפט 2)
  • לחלופין: Ax⃗0A\vec x_0 הוא ההיטל של b⃗\vec b על מרחב העמודות של AA (תרגיל 1)
  • ו-AtAA^tA תמיד סימטרית
הווקטור הקרוב Ax⃗0A\vec x_0 (ההיטל) יחיד תמיד, אבל x⃗0\vec x_0 עצמו יחיד רק כאשר AtAA^tA הפיכה. אם עמודות AA ת"ל — יש אינסוף x⃗0\vec x_0.
A∈Mm×n(R)A\in M_{m\times n}(\mathbb{R}) ומופיעה מכפלה פנימית עם Ax⃗A\vec x
  • ⟨Ax⃗,y⃗⟩=⟨x⃗,Aty⃗⟩\langle A\vec x,\vec y\rangle=\langle\vec x,A^t\vec y\rangle (משפט 1) — כך "מעבירים" מטריצה בין הרכיבים
  • ואם AA סימטרית: ⟨Ax⃗,y⃗⟩=⟨x⃗,Ay⃗⟩\langle A\vec x,\vec y\rangle=\langle\vec x,A\vec y\rangle (מסקנה 1)
  • זה הצעד הפותח כמעט בכל הוכחה על מטריצות סימטריות
המשפט מנוסח מעל R\mathbb{R} עם המכפלה הסטנדרטית. מעל C\mathbb{C} המקבילה דורשת At‾\overline{A^t} ולא AtA^t.
A∈Mn(R)A\in M_n(\mathbb{R}) סימטרית
  • כל ערך עצמי של AA הוא ממשי (משפט 3)
  • ויש לה לפחות ערך עצמי ממשי אחד (מסקנה 2)
  • מרחבים עצמיים של ע"ע שונים אורתוגונליים זה לזה (משפט 4)
  • AA לכסינה, ואף קיימת OO אורתוגונלית עם OtAOO^tAO אלכסונית (משפט 6 — הפירוק הספקטרלי)
המשפט הספקטרלי חל על מטריצות סימטריות ממשיות בלבד. מטריצה ממשית לא סימטרית עלולה לא להיות לכסינה כלל (למשל מטריצת סיבוב).
O∈Mn(R)O\in M_n(\mathbb{R}) אורתוגונלית
  • עמודותיה מהוות בסיס אורתונורמלי של Rn\mathbb{R}^n (הגדרה)
  • OtO=InO^tO=I_n (משפט 5), ולכן O−1=OtO^{-1}=O^t — היפוך בשחלוף בלבד
  • ולכן det⁡(O)2=1\det(O)^2=1, כלומר det⁡(O)=±1\det(O)=\pm1
  • ובלכסון אורתוגונלי אפשר לכתוב OtAOO^tAO במקום O−1AOO^{-1}AO
"מטריצה אורתוגונלית" דורשת עמודות אורתונורמליות, לא רק אורתוגונליות. מטריצה עם עמודות אורתוגונליות שאינן מנורמלות אינה מקיימת OtO=IO^tO=I.
מבקשים לכסון אורתוגונלי של מטריצה סימטרית
  • הלכסון מובטח לפני שמתחילים (משפט 6)
  • מוצאים ע"ע ובסיס לכל מרחב עצמי
  • מריצים גרם-שמידט בתוך כל מרחב עצמי בנפרד ומנרמלים
  • ווקטורים ממרחבים עצמיים שונים כבר אורתוגונליים אוטומטית (משפט 4) — אין צורך לטפל בהם
לא מריצים גרם-שמידט על כל הווקטורים ביחד — זה יקלקל את היותם ווקטורים עצמיים. רק בתוך כל VλV_\lambda.
נתון ש-λ1≠λ2\lambda_1\neq\lambda_2 ע"ע של מטריצה סימטרית ממשית
  • Vλ1⊥Vλ2V_{\lambda_1}\perp V_{\lambda_2}: לכל u⃗∈Vλ1\vec u\in V_{\lambda_1} ו-w⃗∈Vλ2\vec w\in V_{\lambda_2} מתקיים ⟨u⃗,w⃗⟩=0\langle\vec u,\vec w\rangle=0 (משפט 4)
  • ולכן איחוד הבסיסים האורתונורמליים שלהם הוא קבוצה אורתונורמלית
  • ובפרט הם בת"ל — בלי צורך במשפט 3 של שבוע 7
מופיע הביטוי AtAA^tA
  • (AtA)t=AtA(A^tA)^t=A^tA — היא סימטרית, ולכן חלים עליה כל משפטי השבוע
  • בפרט היא לכסינה אורתוגונלית וכל ע"ע שלה ממשיים
  • והיא הכלי לפתרון ריבועים פחותים (משפט 2)
המערכת Ax⃗=b⃗A\vec x=\vec b כן פתירה
  • כל פתרון רגיל הוא גם פתרון ריבועים פחותים — השגיאה ∥Ax⃗−b⃗∥\|A\vec x-\vec b\| מתאפסת
  • ו-b⃗\vec b כבר במרחב העמודות, ולכן ההיטל שלו הוא הוא עצמו (משפט 1, שבוע 12)
  • ומשוואת הריבועים הפחותים תיתן בדיוק את אותם פתרונות

איך מפריכים

מהבדיקה הזולה ביותר לכיוון היקרה
להפריך ש-OO מטריצה אורתוגונלית
  1. 1הזול ביותר — נורמה של עמודה אחת: אם ∥C⃗1∥≠1\|\vec C_1\|\neq1, סיימת.
  2. 2ואז זוג עמודות אחד: ⟨C⃗1,C⃗2⟩≠0\langle\vec C_1,\vec C_2\rangle\neq0 מפריך.
  3. 3בדיקת det⁡\det: אם det⁡(O)≠±1\det(O)\neq\pm1 — הופרך מיד.
  4. 4הבדיקה המלאה והיקרה: לחשב OtOO^tO ולראות שאינה InI_n (משפט 5).
להפריך שמטריצה ניתנת ללכסון אורתוגונלי
  1. 1בדקי סימטריות: אם A≠AtA\neq A^t — הכיוון של המשפט הספקטרלי לא חל, אין הבטחה.
  2. 2להפרכה ממש: הראי שיש ע"ע לא ממשי (משפט 3 בשלילה) — למשל מטריצת סיבוב עם pA(λ)=λ2+1p_A(\lambda)=\lambda^2+1.
  3. 3או הראי ששני ו"ע של ע"ע שונים אינם אורתוגונליים — סותר את משפט 4, ולכן AA אינה סימטרית ואינה לכסינה אורתוגונלית.
  4. 4או הראי שהיא בכלל לא לכסינה (GM<AMGM<AM) — ואז בוודאי לא אורתוגונלית.
להפריך שווקטור נתון הוא פתרון הריבועים הפחותים
  1. 1הציבי במשוואה AtAx⃗0=Atb⃗A^tA\vec x_0=A^t\vec b ובדקי שוויון — חישוב אחד (משפט 2).
  2. 2לחלופין חשבי ∥Ax⃗0−b⃗∥\|A\vec x_0-\vec b\| והשוו לווקטור אחר קונקרטי; אם קיים טוב יותר — הופרך.
  3. 3בדיקה מהירה: השארית b⃗−Ax⃗0\vec b-A\vec x_0 חייבת להיות אורתוגונלית לכל עמודות AA.

איך מוכיחים

המהלכים שעובדים בשבוע הזה
לפתור בעיית ריבועים פחותים
  1. 1רשמי את AA ואת b⃗\vec b מתוך המערכת ואמתי שאין פתרון רגיל.
  2. 2חשבי AtAA^tA ו-Atb⃗A^t\vec b.
  3. 3פתרי את המערכת הריבועית AtAx⃗0=Atb⃗A^tA\vec x_0=A^t\vec b (משפט 2).
  4. 4בדיקה: השארית b⃗−Ax⃗0\vec b-A\vec x_0 אורתוגונלית לעמודות AA.
  5. 5אם ביקשו את הווקטור הקרוב עצמו — זהו Ax⃗0A\vec x_0, וזה ההיטל של b⃗\vec b על מרחב העמודות.
ללכסן אורתוגונלית מטריצה סימטרית
  1. 1ודאי ש-AA סימטרית — זה מה שמפעיל את משפט 6.
  2. 2חשבי pAp_A ומצאי את הע"ע (כולם ממשיים לפי משפט 3).
  3. 3לכל ע"ע מצאי בסיס ל-Vλ=Null(λI−A)V_\lambda=Null(\lambda I-A).
  4. 4הריצי גרם-שמידט בתוך כל VλV_\lambda בנפרד ונרמלי; בין מרחבים שונים האורתוגונליות בחינם (משפט 4).
  5. 5הרכיבי את OO מהעמודות שקיבלת וכתבי OtAO=DO^tAO=D — בדיקה: OtO=InO^tO=I_n.
להוכיח טענה על מטריצה סימטרית ממשית
  1. 1התחילי מ-⟨Ax⃗,y⃗⟩=⟨x⃗,Ay⃗⟩\langle A\vec x,\vec y\rangle=\langle\vec x,A\vec y\rangle (מסקנה 1) — זה הצעד הפותח כמעט תמיד.
  2. 2הציבי ווקטורים עצמיים: אם Au⃗=λ1u⃗A\vec u=\lambda_1\vec u ו-Aw⃗=λ2w⃗A\vec w=\lambda_2\vec w, קבלי λ1⟨u⃗,w⃗⟩=λ2⟨u⃗,w⃗⟩\lambda_1\langle\vec u,\vec w\rangle=\lambda_2\langle\vec u,\vec w\rangle.
  3. 3הסיקי (λ1−λ2)⟨u⃗,w⃗⟩=0(\lambda_1-\lambda_2)\langle\vec u,\vec w\rangle=0, ומכיוון ש-λ1≠λ2\lambda_1\neq\lambda_2 — אורתוגונליות (משפט 4).
  4. 4לממשיות הע"ע — אותו טריק עם v⃗\vec v מרוכב ועם λ‾\overline{\lambda} (משפט 3).
  5. 5לקיום ע"ע — המשפט היסודי של האלגברה נותן שורש מרוכב, ומשפט 3 מוריד אותו ל-R\mathbb{R} (מסקנה 2).

מסקנות — מה לוקחים מהשבוע

  • 1O אורתוגונלית ⟺ OᵗO = I ⟺ O⁻¹ = Oᵗ ⟺ העמודות בסיס אורתונורמלי. ואז det O = ±1.
  • 2מטריצה סימטרית ממשית: כל הע"ע ממשיים, וו"ע של ע"ע שונים אורתוגונליים אוטומטית.
  • 3המשפט הספקטרלי: לכל A סימטרית קיימת O אורתוגונלית עם OᵗAO = D.
  • 4ריבועים פחותים: הפתרון המקרב פותר את המשוואות הנורמליות AᵗAx₀ = Aᵗb.
שקפי הרצאה 13
המצגת המקורית במלואה
שבוע 12:גרם–שמידט