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

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

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

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

רקע

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

האלגוריתם

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

סרטון המדגים את תהליך גרם-שמידט במרחב

תאור אינטואיבי

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

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

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

אפשר להפעיל את אותו אלגוריתם גם ללא שלב הנרמול, ולקבל קבוצה אורתוגונלית.

תאור פורמלי

נניח כי קבוצת הווקטורים שעליה אנו רוצים להפעיל את התהליך מסומנת בתור $\ \left\{v_1,v_2,\dots\right\}$. התוצאה של התהליך תהיה הקבוצה $\ \left\{e_1,e_2,\dots\right\}$ שפורשת אותו מרחב לינארי כמו הקבוצה המקורית, ומקיימת $\ \langle e_i,e_j\rangle=\delta_{ij}$ (הדלתא של קרונקר).

בהינתן וקטור $\ v_i$ כלשהו ווקטור מנורמל $\ e_j$ , הווקטור $\ \langle v_i,e_j\rangle e_j$ (הווקטור שמתקבל מהכפלת $\ e_j$ בסקלר שהוא המכפלה הפנימית שלו ושל $\ v_i$) מכונה "ההטלה" של $\ v_i$ על $\ e_j$. זהו הרכיב של $\ v_i$ בכיוון של $\ e_j$. על כן ניתן להוכיח על ידי בדיקה מיידית כי הווקטור $\ v_i'=v_i- \langle v_i,e_j\rangle e_j$ הוא וקטור אורתוגונלי ל-$\ e_j$. כמו כן $\ Span\left\{v_i,e_j\right\}=Span\left\{v_i',e_j\right\}$.

מתוצאה זו ניתן לקבל כי באופן כללי, אם עד כה הפכנו את הווקטורים $\ \left\{v_1,\dots,v_n\right\}$ לקבוצה אורתונורמלית $\ \left\{e_1,\dots,e_n\right\}$ שפורשת אותו מרחב, נקבל את הווקטור הבא לקבוצה האורתונורמלית בצורה הבאה:

• נגדיר $\ v_{n+1}'=v_{n+1}-\sum_{k=1}^n\langle v_{n+1},e_k\rangle e_k$

בהגדרה זו הורדנו מ-$\ v_{n+1}$ את כל ההטלות שלו עם אברי הבסיס האורתונורמלי שבנינו עד כה ונותרנו עם רכיב אחד שאורתוגנלי לכולם. כעת נותר לנרמל את הווקטור הזה:

• $\ e_{n+1}=\frac{v_{n+1}'}{\|v_{n+1}'\|}$

וכך קיבלנו את האיבר הבא בסדרה.

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

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

אם $\ \left\{v_1,v_2,\dots\right\}$ היא קבוצת הווקטורים שעליה הפעלנו את התהליך, ואילו $\ \left\{v_1',v_2',\dots v_n'\right\}$ היא קבוצת הווקטורים האורתוגונליים שהתקבלה עד כה, נגדיר את האיבר הבא על ידי:

$\ v_{n+1}'=v_{n+1}-\sum_{k=1}^n\frac{\langle v_{n+1},v_k'\rangle}{\|v_k'\|^2} v_k'$

כלומר, ההבדל היחיד הוא שאנו מחלקים את המכפלה הפנימית בנורמה של $\ v_k$ בריבוע. כדי לראות את הסיבה לכך נשים לב כי על פי ההגדרה $\ e_k=\frac{v_k'}{\|v_k'\|}$ ולכן, אם נציב משוואות אלו בנוסחה שהראינו בסעיף הקודם, נקבל:

• $\ v_{n+1}'=v_{n+1}-\sum_{k=1}^n\langle v_{n+1},e_k\rangle e_k=v_{n+1}'=v_{n+1}-\sum_{k=1}^n\langle v_{n+1},\frac{v_k'}{\|v_k'\|}\rangle \frac{v_k'}{\|v_k'\|}=v_{n+1}-\sum_{k=1}^n\frac{\langle v_{n+1},v_k'\rangle}{\|v_k'\|^2} v_k'$

קבוצה תלויה לינארית

אם קבוצת הווקטורים ההתחלתית $\ \left\{v_1,v_2,\dots\right\}$ תלויה לינארית אז לעתים נקבל $v_{n+1}'=0$. בכזה מיקרה יש להיתעלם מווקטור זה, ולהמשיך באלגוריתם.

שימושים

תהליך גרם-שמידט מוכיח כי לכל מרחב מכפלה פנימית מימד סופי (או בן מניה) יש בסיס אורתונורמלי. אפשר לנסח תוצאה זו, במונחים של מטריצות באופן הבא: כל מטריצה סימטרית מוגדרת חיובית $S$ חופפת למטריצת היחידה. זהו מיקרה פרטי של משפט סילבסטר יתר על כן, מהתהליך נובעה שניתן לבצע חפיפה זו על ידי מטריצה משולשית. מכן אנו מקבלים את הפרוק הבא: $S=B \cdot B^t$ כאשר $B$ היא מטריצה משולשית. פרוק זה בתורו גרר את הפרוק הבא: כל מטריצה הפיכה ניתן לפרק למכפלה של מטריצה אורתוגונלית ומטריצה משולשית. זהו מיקרה פרטי של פרוק יווסווה^(אנ').

בנוסף התהליך מוכיח את קיומו של בסיס אורתונורמלי בכל מרחב הילברט ספרבילי. בנוסף התהליך מוכיח את קיומו של בסיס אורתונורמלי בכל מרחב הילברט ספרבילי. עובדה זו שקולה לכך שכל מרחב הילברט ספרבילי איזומורפי למרחב הסדרות $\ell_2$

היסטוריה

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

ראו גם

• בסיס אורתונורמלי
• משפט סילבסטר
• פרוק יווסווה

קישורים חיצוניים

• סרטונים המדגימים את התהליך : תהליך גרם-שמידט במישור, תהליך גרם-שמידט במרחב