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

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

באלגברה הלינארית עוסקים בחקר מבנים אלגבריים המכונים מרחבים וקטוריים ולשם כך מחפשים קבוצה קטנה של אברי המרחב שבאמצעותה ניתן לתאר את המרחב כולו. קבוצה שכזו מכונה בסיס לינארי. כאשר במרחב קיימים מושגים של אורך וזווית בין וקטורים (מושגים הנובעים מהגדרת מכפלה פנימית על המרחב) קיים סוג מיוחד של בסיס, המכונה בסיס אורתונורמלי, בו כל אחד מהווקטורים ניצב (אורתוגונלי) לשאר הווקטורים בבסיס, והאורך (נורמה) של כל אחד מהווקטורים הוא 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$ . כמו כן $\ Span\left\{V_i,e_j\right\}=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'$