דירוג מטריצות

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

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

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

[עריכה] הגדרות בסיסיות

[עריכה] איבר מוביל

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

[עריכה] מטריצה מדורגת

מטריצה תקרא מטריצה מדורגת אם היא מקיימת את התנאים הבאים:

1. שורות האפסים מופיעות אחרי השורות שאינן אפסים.
2. האיבר המוביל נמצא משמאל לאיבר המוביל בשורה שמתחתיו.

[עריכה] מטריצה מדורגת קנונית

מטריצה תקרא מטריצה מדורגת קנונית אם מתקיימים התנאים הבאים:

1. האיבר המוביל נמצא משמאל לאיבר המוביל בשורה שמתחתיו.
2. שורות האפסים מופיעות אחרי השורות שאינן אפסים.
3. בכל שורה שאיננה שורת אפסים, האיבר המוביל שווה ל-1 וכל יתר האיברים בעמודתו הם אפסים.

[עריכה] פעולות מותרות על שורות

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

1. החלפה בין שתי שורות.
2. הכפלה של שורה בסקלר מעליה השונה מאפס ששייך לשדה שהמטריצה מעליה.
3. חיסור או חיבור של מכפלה בסקלר של שורה אחת בשורה אחרת.

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

[עריכה] האלגוריתם

[עריכה] אלגוריתם בעברית

1. הצג את הבעיה כמטריצה. אם יש m משוואות ב-n נעלמים, אזי המטריצה שתוצג תהיה בעלת m שורות ו-n+1 עמודות, כאשר העמודה האחרונה היא עמודת המקדמים החופשיים.

   

   

       :

       :

   

   שקול ל

   

2. i=1.
3. עבור העמודות j=1 עד j=n, בצע:
   1. אם המקדם הפותח (המקדם הראשון בשורה) בשורה ה-i הוא 0, בצע החלפת שורות עם השורה הראשונה שבה המקדם הפותח שונה מאפס. אם אין מקדם כזה (כל העמודה היא עמודת אפסים) עבור לעמודה הבאה, j=j+1.
   2. נרמל את השורה על ידי כפל בקבוע, כך שהמקדם הפותח יהיה שווה ל-1.
   3. עבור כל שורה i מתחתיה: חסר את השורה הראשונה כפול המקדם הפותח של השורה ה-i ממנה כך שהמקדם הפותח החדש שיתקבל יהיה שווה לאפס.
   4. בסוף התהליך עליך לקבל עמודה שבראשה 1 ומתחתיה אפסים.
   5. עבור לעמודה הבאה, j=j+1.
4. בסוף שלב זה עליך לקבל מטריצת מדרגות משולשית, שבה המקדמים הפותחים הם 1 או 0.
5. עבור j=n עד j=1 בצע:
   1. חסר את השורה ה-i מהשורות שמעליה, על ידי הכפלת השורה ה-i במקדם שמופיע באותה עמודה בשורה שמעליה, כך שהחיסור ייתן 0 בעמודה זו.
   2. i=i+1.
   3. בסוף שלב זה כל האיברים שמעל האיבר הפותח בשורה ה-j יהיו שווים ל-0.
6. בסוף שלב זה מתקבלת מטריצת מדרגות קנונית שממנה אפשר לקרוא ישירות את הפתרון למערכת.

[עריכה] פסאודו-קוד

i := 1
j := 1
while (i ≤ m and j ≤ n) do
  Find pivot in column j, starting in row i:
  maxi := i
  for k := i+1 to m do
    if abs(A[k,j]) > abs(A[maxi,j]) then
      maxi := k
    end if
  end for
  if A[maxi,j] ≠ 0 then
    swap rows i and maxi, but do not change the value of i
    Now A[i,j] will contain the old value of A[maxi,j].
    divide each entry in row i by A[i,j]
    Now A[i,j] will have the value 1.
    for u := i+1 to m do
      subtract A[u,j] * row i from row u
      Now A[u,j] will be 0, 
       since A[u,j] - A[i,j] * A[u,j] = A[u,j] - 1 * A[u,j] = 0.
    end for
    i := i + 1
  end if
  j := j + 1
end while

[עריכה] הצורה הכללית

הצורה הכללית אליה אנו שואפים להגיע במטריצה m על n היא

 :

שנקראת מטריצת מדרגות קנונית או מטריצה מדורגת קנונית. ה-* מסמלות ערכים שרירותיים של מספרים.

[עריכה] סיבוכיות

זמן הריצה האלגוריתם היא O(n³). קיימות גרסאות יעילות יותר (אסימפטוטית) כגון זו של קופרסימט-וינוגרד O(n^2.376).

[עריכה] דוגמה

נניח שלפנינו מערכת המשוואות הבאה:

בהצגה מטריציאלית

נחסר את השורה הראשונה מהשורה השנייה, ונחסר 3 פעמים את השורה הראשונה מהשורה השלישית.

נחבר 5 פעמים את השורה השנייה לשורה השלישית.

ננרמל את השורה השלישית:

ומה שקיבלנו זו מטריצת מדרגות משולשית.

נחסר את השורה השלישית פעם אחת מהשורה הראשונה, ופעם אחת מהשורה השנייה:

נחסר את השורה השנייה פעמיים מהשורה הראשונה:

וקיבלנו את הצורה המדורגת קנונית ממנה אפשר לקרוא את הפתרון:

[עריכה] מציאת ההפכי של מטריצה

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