שבוע 12 — גרם–שמידט

התהליך, קיום בסיס אורתוגונלי והמשלים הניצב

גרם–שמידטבסיס אורתוגונלימשלים ניצב

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

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

גרם–שמידטבסיס אורתוגונלימשלים ניצב

התמונה

לחצי Play או עברי שלב-שלב

ההיטל הניצב

תת‑המרחב W הוא הישר הזה, ו‑v הוא וקטור שלא נמצא עליו.

הגדרות (1)

הניסוח המלא מהמצגת

הגדרהגרם שמידט - הרחבה: תהליך גרם שמידט לאורתונורמליזציה

בעזרת תהליך גרם שמידט עם שינויים קלים ניתן לבנות בסיס אורתונורמלי (במקום אורתוגונלי).

הכוונה היא שבכל שלב בבניה האינדוקטיבית כל הוקטורים מנורמלים.

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

תהליך גרם שמידט לאורתונורמליזציה:

יהי

V

ממ"פ. יהיו

v_1,\dots,v_n\in V

בסיס של

V

נגדיר וקטורים

u_1,\dots,u_n\in V

בצורה הבאה באופן אינדוקטיבי:

1. נגדיר את הוקטור הראשון בבסיס באופן הבא:

u_1=\dfrac{v_1}{\|v_1\|}

2. לכל

2\le k<n

נגדיר:

u_{k+1}^{*}=v_{k+1}-\sum_{i=1}^{k}\langle v_{k+1},u_i\rangle u_i

וממנו נגדיר את

u_{k+1}=\dfrac{u_{k+1}^{*}}{\|u_{k+1}^{*}\|}

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

ניסוחים בלבד — ההוכחות בלשונית ההרצאה

משפט 1ההיטל של וקטור שנמצא בתת-המרחב הוא הוא עצמוצריך לדעת להוכיח

יהי

V

ממ"פ נ"ס. יהיו

u_1,\dots,u_k\in V

וקטורים אורתונורמלים.

יהי

v\in span\{u_1,\dots,u_k\}

. אזי

proj_{u_1,\dots,u_k}(v)=v

משפט 1תהליך האורתוגונליזציה של גרם-שמידטצריך לדעת להוכיח

יהי

V

ממ"פ נ"ס. יהיו

v_1,\dots,v_n\in V

בסיס של

V

נגדיר וקטורים

u_1,\dots,u_n\in V

בצורה הבאה באופן אינדוקטיבי:

1. נגדיר את הוקטור הראשון בבסיס:

u_1=v_1

2. לכל

2\le k\le n

נגדיר:

u_k=v_k-\sum_{i=1}^{k-1}\dfrac{\langle v_k,u_i\rangle}{\|u_i\|^2}u_i

ואז מתקיים:

u_1,\dots,u_n

מהווים בסיס אורתוגונלי של

V

לכל

1\le k\le n

מתקיים:

span\{u_1,\dots,u_k\}=span\{v_1,\dots,v_k\}

מסקנה 1קיום בסיס אורתוגונלי

לכל מרחב מכפלה פנימית נוצר סופית יש בסיס אורתוגונלי.

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

אם

v_1,\dots,v_n

אורתוגונליים, אז

v_k=u_k

לכל

1\le k\le n

מסקנה 3קיום בסיס אורתונורמלי

לכל מרחב מכפלה פנימית נוצר סופית יש בסיס אורתונורמלי.

הערות (2)

אינטואיציה להמשך

יהי

V

ממ"פ נ"ס. יהיו

u_1,\dots,u_k\in V

וקטורים אורתונורמליים.

נסמן

W=span\{u_1,\dots,u_k\}

ממשפט שהוכחנו,

proj_{u_1,\dots,u_k}(v)

אינו תלוי בבחירת הבסיס האורתונורמלי.

נשאלת השאלה האם לכל תמ"ו

W

של

V

בכלל קיים בסיס אורתונורמלי?

אם כן, הרי שההיטל מוגדר היטב על כל תמ"ו!

תהליך גרם שמידט - הדגמה ב-

\mathbb{R}^2

תהליך גרם שמידט - הדגמה ב-

\mathbb{R}^2

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

7 מסקנות · זה מה שכותבים בשורה הראשונה של הפתרון

נתון בסיס כלשהו

v_1,\dots,v_n

של ממ"פ

V

(או של תמ"ו

W

)

גרם-שמידט מייצר ממנו בסיס אורתוגונלי $u_1,\dots,u_n$ (משפט 1)
$u_1=v_1$ ו- $u_k=v_k-\sum_{i=1}^{k-1}\dfrac{\langle v_k,u_i\rangle}{\|u_i\|^2}u_i$
ולכל $k$ מתקיים $span\{u_1,\dots,u_k\}=span\{v_1,\dots,v_k\}$
ולכן לכל ממ"פ נ"ס יש בסיס אורתוגונלי, ואחרי נרמול גם אורתונורמלי (מסקנות 1,3)

הסכום הוא על ה-

u_i

שכבר חושבו, לא על ה-

v_i

המקוריים. וההחסרה היא של ההיטל על מה שנבנה עד כה — לא של

v_i

עצמם.

לכל תמ"ו של ממ"פ נוצר סופית יש בסיס אורתונורמלי

ההיטל $proj_W(v)$ מוגדר היטב לכל תמ"ו $W$ — לא רק לכאלה שניתן להם בסיס אורתונורמלי מראש
ובצירוף מסקנה 5 משבוע 11, הוא גם אינו תלוי בבחירת הבסיס
ולכן כל שאלת "הקרוב ביותר" פתירה תמיד

הבסיס הנתון כבר אורתוגונלי

גרם-שמידט לא ישנה אותו: $u_k=v_k$ לכל $k$ (מסקנה 2)
ולכן אין טעם להריץ את התהליך — רק לנרמל אם צריך אורתונורמלי
בדיקה של זוג אחד לפני שמתחילים חוסכת דף שלם של חישוב

נתון

v\in W

(הווקטור כבר בתת-המרחב)

$proj_W(v)=v$ (משפט 1)
ולכן המרחק ל- $W$ הוא $0$
ובכיוון ההפוך: אם $proj_W(v)=v$ אז $v\in W$ — זה גם מקרה השוויון בבסל

תת-המרחב נתון על ידי משוואה (למשל מישור

x-y+2z=0

)

קודם פותרים את המערכת ההומוגנית ומוצאים בסיס למרחב הפתרונות
ואז מריצים גרם-שמידט על הבסיס הזה
ולבסוף מנרמלים (תרגיל 2)

הווקטור המאונך למישור (

\vec n

ממקדמי המשוואה) אינו שייך למישור — הוא משלים אותו, ולא יכול להיות חלק מהבסיס האורתוגונלי של

W

מבקשים להשלים בסיס אורתוגונלי של

W

לבסיס אורתוגונלי של כל

\mathbb{R}^n

קחי $v\notin W$ כלשהו והחסירי ממנו את ההיטל על $u_1,\dots,u_k$ — זהו בדיוק צעד גרם-שמידט נוסף
לחלופין פתרי את מערכת המשוואות $\langle\vec x,u_i\rangle=0$ לכל $i$
שתי הדרכים נותנות וקטור אורתוגונלי לכל הקודמים ולכן בת"ל בהם (משפט 3, שבוע 11)

מבקשים את האיבר הקרוב ביותר ל-

q

מתוך תת-מרחב

W

(למשל הפולינום הקרוב ביותר)

מצאי בסיס ל- $W$ ← גרם-שמידט ← נרמול ← היטל של $q$
התשובה היא $proj_W(q)$ והמרחק המינימלי הוא $\|q-proj_W(q)\|$ (משפט 5, שבוע 11)
המכפלה הפנימית היא זו שהשאלה הגדירה, לא בהכרח הסטנדרטית (תרגיל 3)

איך מפריכים

מהבדיקה הזולה ביותר לכיוון היקרה

להפריך שקבוצה נתונה היא תוצאת גרם-שמידט של הבסיס הנתון

1בדקי את הווקטור הראשון: בגרסה האורתוגונלית חייב $u_1=v_1$ (או $u_1=\frac{v_1}{\|v_1\|}$ בגרסה האורתונורמלית).
2בדקי את הפרישה: $span\{u_1,u_2\}$ חייב להיות שווה ל- $span\{v_1,v_2\}$ (משפט 1).
3בדקי אורתוגונליות של זוג אחד — אם $\langle u_1,u_2\rangle\neq0$ , התהליך לא בוצע נכון.
4אם הבסיס המקורי כבר היה אורתוגונלי — התוצאה חייבת להיות זהה לו (מסקנה 2); כל שינוי מפריך.

להפריך שאין ל-

W

בסיס אורתונורמלי

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

איך מוכיחים

המהלכים שעובדים בשבוע הזה

לבצע גרם-שמידט ולקבל בסיס אורתונורמלי

1בדקי קודם אם הבסיס כבר אורתוגונלי — אם כן, דלגי ישר לנרמול (מסקנה 2).
2סדרי את הווקטורים כך שהראשון יהיה הפשוט ביותר — הסדר חופשי והוא משפיע רק על נוחות החישוב.
3 $u_1=v_1$ ; ואז לכל $k$ : $u_k=v_k-\sum_{i<k}\frac{\langle v_k,u_i\rangle}{\|u_i\|^2}u_i$ .
4אחרי כל שלב — בדקי $\langle u_k,u_i\rangle=0$ לכל $i<k$ לפני שממשיכים; טעות מוקדמת מתגלגלת.
5מותר להכפיל כל $u_k$ בסקלר חיובי כדי להיפטר משברים — האורתוגונליות נשמרת.
6לבסוף נרמלי: $\frac{u_k}{\|u_k\|}$ לכל $k$ .

להוכיח קיום של בסיס אורתוגונלי/אורתונורמלי

1צטטי שקיים בסיס כלשהו ( $V$ נוצר סופית).
2הפעילי עליו את גרם-שמידט (משפט 1) — התוצאה אורתוגונלית ופורשת את אותו מרחב.
3נרמלי (מסקנה 1, שבוע 11) וקבלי אורתונורמלי.
4זו מסקנה 1 ומסקנה 3 של ההרצאה — מותר לצטט אותן ישירות.

למצוא את המרחק המינימלי מווקטור לתת-מרחב

1מצאי בסיס ל- $W$ (אם $W$ נתון במשוואה — פתרי אותה).
2הריצי גרם-שמידט ונרמלי.
3חשבי $\tilde v=\sum\langle v,u_i\rangle u_i$ .
4המרחק הוא $\|v-\tilde v\|$ , וזה המינימום היחיד (משפט 5.4, שבוע 11).

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

1u_k = v_k − Σ_{i<k} (⟨v_k,u_i⟩/‖u_i‖²)·u_i — שימי לב לריבוע במכנה.
2התהליך שומר על ה-span בכל שלב: span{v₁..v_k} = span{u₁..u_k}.
3לכל מרחב מכפלה פנימית נ"ס יש בסיס אורתונורמלי — תוצאה מיידית של התהליך.
4V = W ⊕ W^⊥ — כל וקטור מתפרק יחידית להיטל ולמשלים הניצב שלו.

שקפי הרצאה 12

המצגת המקורית במלואה

שבוע 11:היטל, בסל ופרסבל מטריצות סימטריות ולכסון אורתוגונלי:שבוע 13