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

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

את התהליך אפשר להפעיל על קבוצת וקטורים בלתי תלויה ליניארית כלשהי, כל עוד היא סופית או בת מנייה, והוא מחזיר קבוצה אורתוגונלית הפורשת את אותו תת-מרחב. יתרה מזו, התהליך עובר על הווקטורים בזה אחר זה, פעם אחת בלבד, ולכל 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}$. כמו כן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \operatorname{Span}\left\{v_i,e_j\right\}=\operatorname{Span}\left\{v_i',e_j\right\}} .

מתוצאה זו ניתן לקבל כי באופן כללי, אם עד כה הפכנו את הווקטורים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left\{v_1,\dots,v_n\right\}} לקבוצה אורתונורמלית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left\{e_1,\dots,e_n\right\}} שפורשת אותו מרחב, נקבל את הווקטור הבא לקבוצה האורתונורמלית בצורה הבאה:

• נגדיר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v_{n+1}'=v_{n+1}-\sum_{k=1}^n\langle v_{n+1},e_k\rangle e_k}

בהגדרה זו הורדנו מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v_{n+1}} את כל ההטלות שלו עם אברי הבסיס האורתונורמלי שבנינו עד כה ונותרנו עם רכיב אחד שאורתוגנלי לכולם. כעת נותר לנרמל את הווקטור הזה:

• הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ e_{n+1}=\frac{v_{n+1}'}{\|v_{n+1}'\|}}

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

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

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

אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left\{v_1,v_2,\dots\right\}} היא קבוצת הווקטורים שעליה הפעלנו את התהליך, ואילו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \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}'$

כלומר, ההבדל היחיד הוא שאנו מחלקים את המכפלה הפנימית בנורמה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v_k} בריבוע. כדי לראות את הסיבה לכך נשים לב כי על פי ההגדרה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ e_k=\frac{v_k'}{\|v_k'\|}} ולכן, אם נציב משוואות אלו בנוסחה שהראינו בסעיף הקודם, נקבל:

• הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 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'}

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

אם קבוצת הווקטורים ההתחלתית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left\{v_1,v_2,\dots\right\}} תלויה ליניארית אז לעיתים נקבל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_{n+1}'=0} . במקרה כזה יש להתעלם מווקטור זה, ולהמשיך באלגוריתם.

שימושים

תהליך גרם-שמידט מוכיח כי לכל מרחב מכפלה פנימית ממד סופי (או בן מניה) יש בסיס אורתונורמלי. אפשר לנסח תוצאה זו, במונחים של מטריצות באופן הבא: כל מטריצה סימטרית חיובית לחלוטין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} חופפת למטריצת היחידה. זהו מקרה פרטי של משפט סילבסטר. יתר על כן, מהתהליך נובע שניתן לבצע חפיפה זו על ידי מטריצה משולשית. מכן אנו מקבלים את הפרוק הבא: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S=B \cdot B^t} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} היא מטריצה משולשית. פרוק זה בתורו גרר את הפרוק הבא: כל מטריצה הפיכה ניתן לפרק למכפלה של מטריצה אורתוגונלית ומטריצה משולשית. פירוק זה נקרא פירוק QR, שהוא מקרה פרטי של פרוק יווסווה.

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

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

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

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

תהליך גרם-שמידט אמנם נראה מובן אינטואיטיבית כאשר עוסקים במרחב הווקטורי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^n} המצויד במכפלה הפנימית האוקלידית הסטנדרטית, אולם הצורך בו מתחוור ביתר בהירות בתחום האנליזה הפונקציונלית, העוסקת במרחבי פונקציות מממד אינסופי, שם מציאת בסיסים אורתוגונליים למרחב פונקציות כבר אינה משימה נגישה וישירה כמו באלגברה ליניארית. המוטיבציה והרקע הרעיוני לתהליך מומחשים באופן מיטבי בתחום זה, כמו גם היתרון שבעבודה עם בסיסים אורתוגונליים (ביחס למכפלה הפנימית המוגדרת); כיוון שההיטל של שני רכיבים אורתוגונליים אחד על השני הוא וקטור האפס, ההיטלים של וקטור כללי על איברי הבסיס האורתוגונלי הם בעצמם בעלי היטל אפס אחד ביחס לשני, מה שמפשט מאוד את החישובים הנלווים ומקל על גיבוש אינטואיציה בנוגע לטיב המרחב הפונקציונלי איתו עובדים.

נביא כאן דוגמה מפורסמת וחשובה ליישום לא טריוויאלי של התהליך - מציאת בסיס אורתונורמלי ל"מרחב הפולינומים" הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}[x]} בקטע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle [-1,1]} מתוך הבסיס "הסטנדרטי" של מרחב זה, סדרת המונומים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{x^n\right\}_{n=0}^{\infty}} , כאשר המכפלה הפנימית היא הגרסה הרציפה של המכפלה הפנימית האוקלידית, דהיינו: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle <f,g> = \int_{-1}^1f(x)\cdot g(x)dx} .

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

נסמן ב- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_k(x), p_k(x)} את האיבר ה-k בבסיס האורתוגונלי שיתקבל, לפני הנרמול ולאחר הנרמול בהתאמה. לאחר נרמול האיבר הראשון בבסיס הסטנדרטי, נקבל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_0 = \frac{1}{\sqrt{2}}} . כעת נחשב את ההטלה של האיבר השני על האיבר הראשון המנורמל, ונקבל:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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$

בדומה לכך, נחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_2} :

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_2(x) = x^2 - <x^2,p_0>p_0-<x^2,p_1>p_1 = x^2 - (\int_{-1}^1x^2\frac{1}{\sqrt{2}}dx)\frac{1}{\sqrt{2}} - 0 = x^2-\frac{1}{3} } .

כאשר הנחנו ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle <x^2,p_1>p_1=0} משום שזהו אינטגרל של פונקציה אי-זוגית על פני תחום סימטרי ביחס לראשית. לאחר נרמול נקבל את האיבר השלישי:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_2(x)=\frac{q_2(x)}{|q_2|} = \frac{x^2-\frac{1}{3}}{\sqrt{\int_{-1}^1(x^2-\frac{1}{3})^2dx}} = \frac{\sqrt{5}}{2\sqrt{2}}(3x^2-1)}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_3(x) = \frac{\sqrt{7}}{2\sqrt{2}}(5x^3-3x)}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 (באנגלית)   

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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