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

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

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

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

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

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

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

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

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

תיאור אינטואיבי[עריכת קוד מקור | עריכה]

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

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

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

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

תיאור פורמלי[עריכת קוד מקור | עריכה]

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

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

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

  • נגדיר

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

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

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

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

אם היא קבוצת הווקטורים שעליה הפעלנו את התהליך, ואילו היא קבוצת הווקטורים האורתוגונליים שהתקבלה עד כה, נגדיר את האיבר הבא על ידי:

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

קבוצה תלויה לינארית[עריכת קוד מקור | עריכה]

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

סיבוכיות ויציבות נומרית[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

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

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

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