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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

היסטוריה[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

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