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

תהליך גרם-שמידט (Gram–Schmidt process) הוא תהליך המקבל בסיס סדור של מרחב מכפלה פנימית ומחזיר בסיס אורתונורמלי (אפשר לבצע את התהליך באופן חלקי לקבלת בסיס אורתוגונלי).

את התהליך אפשר להפעיל על קבוצת וקטורים בלתי תלויה ליניארית כלשהי, כל עוד היא מעוצמה סופית או אלף אפס, והוא מחזיר קבוצה אורתוגונלית הפורשת את אותו תת-מרחב. יתרה מזו, התהליך עובר על הווקטורים בזה אחר זה, פעם אחת בלבד, ולכל 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}$. כמו כן $\ \operatorname {Span} \left\{v_{i},e_{j}\right\}=\operatorname {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$ היא מטריצה משולשית. פירוק זה בתורו גרר את הפירוק הבא: כל מטריצה הפיכה ניתן לפרק למכפלה של מטריצה אורתוגונלית ומטריצה משולשית. פירוק זה נקרא פירוק QR, שהוא מקרה פרטי של פירוק איווסווה.

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

אלגברה ליניארית

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

באנליזה פונקציונלית

תהליך גרם-שמידט אמנם נראה מובן אינטואיטיבית כאשר עוסקים במרחב הווקטורי $\mathbb {R} ^{n}$ המצויד במכפלה הפנימית האוקלידית הסטנדרטית, אולם הצורך בו מתחוור ביתר בהירות בתחום האנליזה הפונקציונלית, העוסקת במרחבי פונקציות מממד אינסופי, שם מציאת בסיסים אורתוגונליים למרחב פונקציות כבר אינה משימה נגישה וישירה כמו באלגברה ליניארית. המוטיבציה והרקע הרעיוני לתהליך מומחשים באופן מיטבי בתחום זה, כמו גם היתרון שבעבודה עם בסיסים אורתוגונליים (ביחס למכפלה הפנימית המוגדרת); כיוון שההיטל של שני רכיבים אורתוגונליים אחד על השני הוא וקטור האפס, ההיטלים של וקטור כללי על איברי הבסיס האורתוגונלי הם בעצמם בעלי היטל אפס אחד ביחס לשני, מה שמפשט מאוד את החישובים הנלווים ומקל על גיבוש אינטואיציה בנוגע לטיב המרחב הפונקציונלי איתו עובדים.

נביא כאן דוגמה מפורסמת וחשובה ליישום לא טריוויאלי של התהליך – מציאת בסיס אורתונורמלי ל"מרחב הפולינומים" $\mathbb {R} [x]$ בקטע $[-1,1]$ מתוך הבסיס "הסטנדרטי" של מרחב זה, סדרת המונומים $\left\{x^{n}\right\}_{n=0}^{\infty }$, כאשר המכפלה הפנימית היא הגרסה הרציפה של המכפלה הפנימית האוקלידית, דהיינו: $<f,g>=\int _{-1}^{1}f(x)\cdot g(x)dx$.

בניית פולינומי לז'נדר

נסמן ב- $q_{k}(x),p_{k}(x)$ את האיבר ה-k בבסיס האורתוגונלי שיתקבל, לפני הנרמול ולאחר הנרמול בהתאמה. לאחר נרמול האיבר הראשון בבסיס הסטנדרטי, נקבל $p_{0}={\frac {1}{\sqrt {2}}}$. כעת נחשב את ההטלה של האיבר השני על האיבר הראשון המנורמל, ונקבל:

$q_{1}(x)=x-<x,p_{0}>p_{0}=x-(\int _{-1}^{1}x{\frac {1}{\sqrt {2}}}dx){\frac {1}{\sqrt {2}}}=x$

ולאחר נרמול נקבל את האיבר השני:

$p_{1}(x)={\frac {q_{1}(x)}{|q_{1}|}}={\frac {x}{\sqrt {\int _{-1}^{1}x^{2}dx}}}={\sqrt {\frac {3}{2}}}x$

בדומה לכך, נחשב את $q_{2}$:

$q_{2}(x)=x^{2}-<x^{2},p_{0}>p_{0}-<x^{2},p_{1}>p_{1}=x^{2}-(\int _{-1}^{1}x^{2}{\frac {1}{\sqrt {2}}}dx){\frac {1}{\sqrt {2}}}-0=x^{2}-{\frac {1}{3}}$.

כאשר הנחנו ש-$<x^{2},p_{1}>p_{1}=0$ משום שזהו אינטגרל של פונקציה אי-זוגית על פני תחום סימטרי ביחס לראשית. לאחר נרמול נקבל את האיבר השלישי:

$p_{2}(x)={\frac {q_{2}(x)}{|q_{2}|}}={\frac {x^{2}-{\frac {1}{3}}}{\sqrt {\int _{-1}^{1}(x^{2}-{\frac {1}{3}})^{2}dx}}}={\frac {\sqrt {5}}{2{\sqrt {2}}}}(3x^{2}-1)$

ניתן להמשיך את התהליך ולקבל גם:

$p_{3}(x)={\frac {\sqrt {7}}{2{\sqrt {2}}}}(5x^{3}-3x)$

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

$L_{0}(x)=1,L_{1}(x)=x,L_{2}(x)={\frac {1}{2}}(3x^{2}-1),L_{3}(x)={\frac {1}{2}}(5x^{3}-3x),...$

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

היסטוריה

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

ראו גם

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

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

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