MentoraLINEAR 2

שבוע 11 — היטל, בסל ופרסבל

בסיס אורתונורמלי, ההיטל הניצב ותכונותיו

בסיס אורתונורמליהיטל ניצבאי-שוויון בסלשוויון פרסבל

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

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

בסיס אורתונורמליהיטל ניצבאי-שוויון בסלשוויון פרסבל

התמונה

לחצי Play או עברי שלב-שלב
בסיס אורתונורמלי ופרסבל
u₁u₂
בסיס אורתונורמלי: שני וקטורים ניצבים באורך 1.

הגדרות (1)

הניסוח המלא מהמצגת
הגדרהההיטל האורתוגונלי
יהי VV מרחב מכפלה פנימית ויהי WW תת-מרחב של VV. יהיו u1,…,uku_1,\dots,u_k בסיס אורתונורמלי של WW. יהי v∈Vv\in V.
ההיטל האורתוגונלי של vv על WW (או על u1,…,uku_1,\dots,u_k) הוא:
v~=projW(v)=proju1,…,uk(v)=∑i=1k⟨v,ui⟩ui\tilde v=proj_W(v)=proj_{u_1,\dots,u_k}(v)=\sum_{i=1}^{k}\langle v,u_i\rangle u_i

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

ניסוחים בלבד — ההוכחות בלשונית ההרצאה
מסקנה 1נרמול קבוצה אורתוגונלית
אם הוקטורים u1,…,uk≠0Vu_1,\dots,u_k\neq 0_V אורתוגונליים אזי: הוקטורים u1∥u1∥,…,uk∥uk∥\dfrac{u_1}{\|u_1\|},\dots,\dfrac{u_k}{\|u_k\|} הם אורתונורמליים.
משפט 2הכללת משפט פיתגורסצריך לדעת להוכיח
יהי VV ממ"פ ותהי {u1,…,uk}⊆V\{u_1,\dots,u_k\}\subseteq V קבוצה אורתוגונלית. אזי מתקיים:
∥u1+⋯+uk∥2=∥u1∥2+⋯+∥uk∥2\|u_1+\cdots+u_k\|^2=\|u_1\|^2+\cdots+\|u_k\|^2
משפט 3קבוצה אורתוגונלית ללא 0V0_V היא בת"לצריך לדעת להוכיח
יהי VV מרחב מכפלה פנימית. יהיו 0V≠u1,…,uk∈V0_V\neq u_1,\dots,u_k\in V.
נניח ש-u1,…,uku_1,\dots,u_k אורתוגונליים.
אזי u1,…,uku_1,\dots,u_k הם בת"ל.
מסקנה 2קבוצה אורתונורמלית היא בת"לצריך לדעת להוכיח
יהי VV ממ"פ נ"ס ויהיו u1,…,uk∈Vu_1,\dots,u_k\in V. נניח ש-u1,…,uku_1,\dots,u_k הם אורתונורמליים.
אזי u1,…,uku_1,\dots,u_k בת"ל.
משפט 4נוסחת המקדמים בבסיס אורתוגונליצריך לדעת להוכיח
יהי VV מרחב מכפלה פנימית ויהיו 0V≠u1,…,uk∈V0_V\neq u_1,\dots,u_k\in V.
נניח ש-u1,…,uku_1,\dots,u_k אורתוגונליים.
יהי v∈span{u1,…,uk}v\in span\{u_1,\dots,u_k\}.
אזי מתקיים: v=∑i=1k⟨v,ui⟩∥ui∥2uiv=\sum_{i=1}^{k}\dfrac{\langle v,u_i\rangle}{\|u_i\|^2}u_i
מסקנה 3נוסחת המקדמים בבסיס אורתונורמליצריך לדעת להוכיח
יהי VV ממ"פ נ"ס ויהיו u1,…,unu_1,\dots,u_n בסיס אורתונורמלי של VV. יהי v∈Vv\in V. אזי מתקיים:
v=∑i=1n⟨v,ui⟩uiv=\sum_{i=1}^{n}\langle v,u_i\rangle u_i
משפט 5תכונות ההיטלצריך לדעת להוכיח
יהי VV ממ"פ. יהיו u1,…,uk∈Vu_1,\dots,u_k\in V וקטורים אורתונורמלים.
יהי v∈Vv\in V. יהי v~\tilde v ההיטל האורתוגונלי של vv על u1,…,uku_1,\dots,u_k. אזי:
1. ∥v~∥2=∑i=1k∣⟨v,ui⟩∣2\|\tilde v\|^2=\sum_{i=1}^{k}|\langle v,u_i\rangle|^2
2. לכל 1≤j≤k1\le j\le k מתקיים: ⟨v−v~,uj⟩=0\langle v-\tilde v,u_j\rangle=0 (האנך v−v~v-\tilde v מאונך לכל וקטור שפורש את המישור)
3. לכל u∈span{u1,…,uk}u\in span\{u_1,\dots,u_k\} מתקיים: ⟨v−v~,u⟩=0\langle v-\tilde v,u\rangle=0 (האנך v−v~v-\tilde v מאונך לכל וקטור במישור)
4. לכל w∈Ww\in W מתקיים ∥v−v~∥≤∥v−w∥\|v-\tilde v\|\le\|v-w\|. בנוסף, שוויון מתקיים אם ורק אם w=v~w=\tilde v. (זה הוקטור הקצר ביותר מקצה vv אל WW)
משפט 6אי שוויון בסלצריך לדעת להוכיח
יהי VV ממ"פ נ"ס ויהי WW תמ"ו של VV.
אזי לכל v∈Vv\in V מתקיים: ∥v∥≥∥v~∥\|v\|\ge\|\tilde v\|
בנוסף, שוויון מתקיים אם ורק אם v=v~v=\tilde v.
מסקנה 4שוויון פרסבלצריך לדעת להוכיח
יהי VV ממ"פ נ"ס ויהיו u1,…,unu_1,\dots,u_n בסיס אורתונורמלי של VV. יהי v∈Vv\in V. אזי מתקיים:
∥v∥2=∑i=1n∣⟨v,ui⟩∣2\|v\|^2=\sum_{i=1}^{n}|\langle v,u_i\rangle|^2
מסקנה 5ההיטל אינו תלוי בבחירת הבסיס האורתונורמליצריך לדעת להוכיח
יהי VV ממ"פ נ"ס ויהי WW תמ"ו של VV.
יהיו u1,…,uku_1,\dots,u_k ו-u~1,…,u~k\tilde u_1,\dots,\tilde u_k שני בסיסים אורתונורמליים של WW.
יהי v∈Vv\in V. אזי מתקיים: proju1,…,un(v)=proju~1,…,u~n(v)proj_{u_1,\dots,u_n}(v)=proj_{\tilde u_1,\dots,\tilde u_n}(v)

הערות (1)

הערה 1 — האינטואיציה להיטל מ-R2\mathbb{R}^2
יהיו x⃗,y⃗∈R2\vec x,\vec y\in\mathbb{R}^2, x⃗,y⃗≠0⃗\vec x,\vec y\neq\vec 0. נניח ש-y⃗\vec y הוא וקטור יחידה.
ידוע ש-⟨x⃗,y⃗⟩=∥x⃗∥⋅∥y⃗∥⋅cos⁡θ\langle\vec x,\vec y\rangle=\|\vec x\|\cdot\|\vec y\|\cdot\cos\theta
נציב ∥y⃗∥=1\|\vec y\|=1 ונקבל: ⟨x⃗,y⃗⟩=∥x⃗∥⋅cos⁡θ\langle\vec x,\vec y\rangle=\|\vec x\|\cdot\cos\theta
נתבונן בוקטור ⟨x⃗,y⃗⟩⋅y⃗\langle\vec x,\vec y\rangle\cdot\vec y, נסמנו w⃗\vec w:
ניתן לראות מההגדרה ש-w⃗∈span{y⃗}\vec w\in span\{\vec y\} וכמו כן:
∥w⃗∥=∥⟨x⃗,y⃗⟩⋅y⃗∥=∣⟨x⃗,y⃗⟩∣⋅∥y⃗∥=∣⟨x⃗,y⃗⟩∣=∥x⃗∥⋅∣cos⁡θ∣\|\vec w\|=\|\langle\vec x,\vec y\rangle\cdot\vec y\|=|\langle\vec x,\vec y\rangle|\cdot\|\vec y\|=|\langle\vec x,\vec y\rangle|=\|\vec x\|\cdot|\cos\theta|
לכן w⃗\vec w הוא וקטור שכיוונו ככיוון y⃗\vec y או −y⃗-\vec y והנורמה שלו שווה לניצב של משולש ישר זווית.
וקטור זה מכונה גם ההיטל של x⃗\vec x על y⃗\vec y! נרצה כעת להכליל את מושג ההיטל!

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

8 מסקנות · זה מה שכותבים בשורה הראשונה של הפתרון
נתונה קבוצה אורתוגונלית u1,…,uku_1,\dots,u_k שאף אחד מאיבריה אינו 0V0_V
  • הם בת"ל (משפט 3)
  • ואם k=dim⁡Vk=\dim V — הם בסיס של VV, בלי לבדוק פרישה
  • ואפשר לנרמל אותם לבסיס אורתונורמלי (מסקנה 1)
התנאי "אף אחד אינו 0V0_V" הכרחי: קבוצה שמכילה את 0V0_V עדיין אורתוגונלית לפי ההגדרה, אבל בוודאי ת"ל.
נתון בסיס אורתוגונלי u1,…,uku_1,\dots,u_k ו-v∈span{u1,…,uk}v\in span\{u_1,\dots,u_k\}
  • v=∑i=1k⟨v,ui⟩∥ui∥2uiv=\sum_{i=1}^{k}\dfrac{\langle v,u_i\rangle}{\|u_i\|^2}u_i (משפט 4)
  • ולכן אין צורך לפתור מערכת משוואות כדי למצוא קואורדינטות
  • כל מקדם מחושב בנפרד — לא תלוי באחרים
החלוקה ב-∥ui∥2\|u_i\|^2 היא בדיוק מה ששוכחים. היא נעלמת רק אם הבסיס אורתונורמלי.
נתון בסיס אורתונורמלי u1,…,unu_1,\dots,u_n של VV
  • v=∑i=1n⟨v,ui⟩uiv=\sum_{i=1}^{n}\langle v,u_i\rangle u_i (מסקנה 3)
  • ולכן [v]A[v]_{\mathcal{A}} הוא בדיוק וקטור המכפלות ⟨v,ui⟩\langle v,u_i\rangle
  • שוויון פרסבל: ∥v∥2=∑i=1n∣⟨v,ui⟩∣2\|v\|^2=\sum_{i=1}^{n}|\langle v,u_i\rangle|^2 (מסקנה 4)
נתון תמ"ו WW עם בסיס אורתונורמלי u1,…,uku_1,\dots,u_k ווקטור v∈Vv\in V
  • v~=projW(v)=∑i=1k⟨v,ui⟩ui\tilde v=proj_W(v)=\sum_{i=1}^{k}\langle v,u_i\rangle u_i — נוסחה ישירה, בלי מערכת משוואות
  • v−v~v-\tilde v אורתוגונלי לכל u∈Wu\in W (משפט 5, סעיפים 2-3)
  • ∥v~∥2=∑i=1k∣⟨v,ui⟩∣2\|\tilde v\|^2=\sum_{i=1}^{k}|\langle v,u_i\rangle|^2
  • ההיטל אינו תלוי בבחירת הבסיס האורתונורמלי של WW (מסקנה 5)
נוסחת ההיטל דורשת בסיס אורתונורמלי של WW. אם הבסיס רק אורתוגונלי — חלקי ב-∥ui∥2\|u_i\|^2; ואם הוא לא אורתוגונלי כלל — חייבים גרם-שמידט קודם.
השאלה מבקשת את האיבר הקרוב ביותר ל-vv מתוך WW
  • זהו ההיטל v~\tilde v: לכל w∈Ww\in W מתקיים ∥v−v~∥≤∥v−w∥\|v-\tilde v\|\le\|v-w\| (משפט 5, סעיף 4)
  • ושוויון מתקיים אם"ם w=v~w=\tilde v — כלומר המינימום יחיד
  • והמרחק המינימלי הוא ∥v−v~∥\|v-\tilde v\|
נתון היטל v~\tilde v של vv על תמ"ו WW
  • אי-שוויון בסל: ∥v~∥≤∥v∥\|\tilde v\|\le\|v\| (משפט 6)
  • ושוויון מתקיים אם"ם v=v~v=\tilde v, כלומר אם"ם v∈Wv\in W
  • ולכן ∑i=1k∣⟨v,ui⟩∣2≤∥v∥2\sum_{i=1}^{k}|\langle v,u_i\rangle|^2\le\|v\|^2
בסל הוא אי-שוויון כשהקבוצה האורתונורמלית אינה בסיס של כל VV. כשהיא כן בסיס — האי-שוויון הופך לשוויון פרסבל.
צריך לפרק vv ל"חלק ב-WW" ו"חלק מאונך"
  • כתבי v=v~+(v−v~)v=\tilde v+(v-\tilde v)
  • v~∈W\tilde v\in W ו-(v−v~)(v-\tilde v) אורתוגונלי לכל WW (משפט 5)
  • ולכן לפי פיתגורס ∥v∥2=∥v~∥2+∥v−v~∥2\|v\|^2=\|\tilde v\|^2+\|v-\tilde v\|^2
נתונה קבוצה אורתוגונלית (לא מנורמלת) ורוצים להשליך עליה
  • הנוסחה היא ∑i⟨v,ui⟩⟨ui,ui⟩ui\sum_i\dfrac{\langle v,u_i\rangle}{\langle u_i,u_i\rangle}u_i
  • והווקטור w=v−∑i⟨v,ui⟩⟨ui,ui⟩uiw=v-\sum_i\dfrac{\langle v,u_i\rangle}{\langle u_i,u_i\rangle}u_i אורתוגונלי ל-span{u1,…,uk}span\{u_1,\dots,u_k\} (תרגיל מבחן 2017)
  • זהו בדיוק הצעד האינדוקטיבי של גרם-שמידט

איך מפריכים

מהבדיקה הזולה ביותר לכיוון היקרה
להפריך שווקטור נתון הוא ההיטל של vv על WW
  1. 1הזול ביותר: בדקי אם המועמד בכלל שייך ל-WW. אם לא — סיימת.
  2. 2ואז — אורתוגונליות השארית: חשבי ⟨v−v~,u1⟩\langle v-\tilde v,u_1\rangle עבור וקטור בסיס אחד של WW. אם ≠0\neq0 — הופרך (משפט 5).
  3. 3בדיקת בסל: אם ∥v~∥>∥v∥\|\tilde v\|>\|v\| — בוודאי לא היטל (משפט 6).
  4. 4בדיקת מרחק: מצאי w∈Ww\in W קונקרטי עם ∥v−w∥<∥v−v~∥\|v-w\|<\|v-\tilde v\| — סותר את סעיף 4.
להפריך שקבוצה נתונה היא בסיס אורתוגונלי של WW
  1. 1ספרי איברים: אם מספרם ≠dim⁡W\neq\dim W — סיימת.
  2. 2בדקי שאין 0V0_V בקבוצה — עם 0V0_V היא ת"ל ולכן אינה בסיס.
  3. 3בדקי זוג אחד: ⟨u1,u2⟩≠0\langle u_1,u_2\rangle\neq0 מפריך.
  4. 4בדקי שייכות: אם אחד הווקטורים אינו ב-WW — הופרך.

איך מוכיחים

המהלכים שעובדים בשבוע הזה
לחשב היטל אורתוגונלי
  1. 1ודאי שהבסיס של WW אורתונורמלי. אם הוא רק אורתוגונלי — או שתנרמלי, או שתשתמשי בגרסה עם ∥ui∥2\|u_i\|^2 במכנה.
  2. 2חשבי ⟨v,ui⟩\langle v,u_i\rangle לכל ii בנפרד.
  3. 3הרכיבי: v~=∑⟨v,ui⟩ui\tilde v=\sum\langle v,u_i\rangle u_i.
  4. 4בדיקה: ⟨v−v~,ui⟩=0\langle v-\tilde v,u_i\rangle=0 לכל ii — אם לא מתאפס, יש טעות אריתמטית.
  5. 5אם ביקשו מרחק — חשבי ∥v−v~∥\|v-\tilde v\|.
להוכיח בת"ל בעזרת אורתוגונליות
  1. 1הראי שהקבוצה אורתוגונלית ושאין בה 0V0_V — ואז משפט 3 סוגר מיד, בלי מערכת משוואות.
  2. 2אם צריך את ההוכחה עצמה: הניחי ∑αiui=0V\sum\alpha_iu_i=0_V והכפילי פנימית ב-uju_j.
  3. 3כל האיברים מתאפסים חוץ מ-αj∥uj∥2\alpha_j\|u_j\|^2, ולכן αj=0\alpha_j=0 (כאן משתמשים ב-uj≠0Vu_j\neq0_V).
  4. 4ואם מספר הווקטורים שווה למימד — הסיקי שזה בסיס.
להוכיח אי-שוויון בעזרת בסל או פרסבל
  1. 1זהי את הסכום ∑∣⟨v,ui⟩∣2\sum|\langle v,u_i\rangle|^2 באגף אחד — זו הנורמה בריבוע של ההיטל.
  2. 2אם ה-uiu_i אורתונורמליים אך לא בסיס של VV — הפעילי בסל: הסכום ≤∥v∥2\le\|v\|^2.
  3. 3אם הם בסיס אורתונורמלי מלא — יש שוויון (פרסבל).
  4. 4למספר תתי-מרחבים אורתוגונליים — האיחוד של הבסיסים עדיין אורתונורמלי, ואז בסל נותן את הסכום (תרגיל 4 בהרצאה 13).

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

  • 1בבסיס אורתונורמלי המקדמים הם פשוט מכפלות פנימיות — בלי לפתור מערכת.
  • 2Proj_W(v) = Σ⟨v,u_i⟩u_i נכון רק לבסיס אורתונורמלי. אחרת מחלקים ב-‖u_i‖².
  • 3v − Proj_W(v) ⟂ W, וזו התכונה שמאפיינת את ההיטל באופן יחיד.
  • 4בסל: ‖Proj_W(v)‖ ≤ ‖v‖. פרסבל הוא מקרה השוויון, כשהבסיס פורש את כל המרחב.
מטלה 12
לתרגל את החומר של השבוע
שקפי הרצאה 11
המצגת המקורית במלואה
שבוע 10:אורתוגונליותגרם–שמידט:שבוע 12