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

מתוך המכלול, האנציקלופדיה היהודית
(הופנה מהדף תהליך גרם שמידט)
קפיצה לניווט קפיצה לחיפוש

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

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

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

רקע

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

האלגוריתם

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

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

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

התהליך פועל כך: מנרמלים את הווקטור הראשון. אז מפרקים את הווקטור השני לרכיבים, כאשר הרכיב הראשון הוא בכיוון הווקטור הראשון, והרכיב השני בכיוון הניצב לו. מחליפים את הווקטור השני ברכיב הניצב לווקטור הראשון, ומנרמלים את התוצאה. התקבל וקטור שניצב לווקטור הראשון, אורכו הוא 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\{e_1,e_2,\dots\right\}} שפורשת אותו מרחב ליניארי כמו הקבוצה המקורית, ומקיימת (הדלתא של קרונקר).

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

כלומר, ההבדל היחיד הוא שאנו מחלקים את המכפלה הפנימית בנורמה של הפענוח נכשל (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, שהוא מקרה פרטי של פרוק יווסווה(אנ').

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

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

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

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

תהליך גרם-שמידט אמנם נראה מובן אינטואיטיבית כאשר עוסקים במרחב הווקטורי הפענוח נכשל (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}

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

בדומה לכך, נחשב את הפענוח נכשל (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),...}

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

היסטוריה

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

ראו גם

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

הערות שוליים

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


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

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