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

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

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

הגדרות בסיסיות

איבר מוביל

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

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

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

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

מטריצה מדורגת קנונית

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

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

פעולות מותרות על שורות

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

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

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

מטריצה המתקבלת ממטריצת היחידה על ידי הפעלת פעולה אלמנטרית נקראת מטריצה אלמנטרית.

האלגוריתם

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

אלגוריתם בעברית

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

   $\ \alpha _{11}x_{1}+\alpha _{12}x_{2}+...+\alpha _{1n}x_{n}=b_{1}$

   $\ \alpha _{21}x_{1}+\alpha _{22}x_{2}+...+\alpha _{2n}x_{n}=b_{2}$

       :

       :

   $\ \alpha _{m1}x_{1}+\alpha _{m2}x_{2}+...+\alpha _{mn}x_{n}=b_{m}$

   שקול ל

   ${\begin{bmatrix}\alpha _{11}&\cdots &\alpha _{1n}\\\vdots &\ddots &\vdots \\\alpha _{m1}&\cdots &\alpha _{mn}\end{bmatrix}}{\begin{pmatrix}x_{1}\\\vdots \\x_{n}\end{pmatrix}}={\begin{pmatrix}b_{1}\\\vdots \\b_{m}\end{pmatrix}}$

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 היא

:${\begin{bmatrix}1&*&0&0&*&*&0&*&0\\0&0&1&0&*&*&0&*&0\\0&0&0&1&*&*&0&*&0\\0&0&0&0&0&0&1&*&0\\0&0&0&0&0&0&0&0&1\\0&0&0&0&0&0&0&0&0\end{bmatrix}}$

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

סיבוכיות

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

דוגמה

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

$x+2y+z=1\quad (L_{1})$

$x+3y+2z=2\quad (L_{2})$

$3x+y+z=0\quad (L_{3})$

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

$\left[{\begin{array}{ccc|c}1&2&1&1\\1&3&2&2\\3&1&1&0\end{array}}\right]$

פעולה	נחסר את השורה הראשונה מהשורה השנייה, ונחסר 3 פעמים את השורה הראשונה מהשורה השלישית	נחבר 5 פעמים את השורה השנייה לשורה השלישית:	ננרמל את השורה השלישית (לקבלת מטריצת מדרגות משולשית)	נחסר את השורה השלישית פעם אחת מהשורה הראשונה, ופעם אחת מהשורה השנייה	נחסר את השורה השנייה פעמיים מהשורה הראשונה
מטריצה	$\left[{\begin{array}{ccc|c}1&2&1&1\\0&1&1&1\\0&-5&-2&-3\end{array}}\right]$	$\left[{\begin{array}{ccc|c}1&2&1&1\\0&1&1&1\\0&0&3&2\end{array}}\right]$	$\left[{\begin{array}{ccc|c}1&2&1&1\\0&1&1&1\\0&0&1&2/3\end{array}}\right]$	$\left[{\begin{array}{ccc|c}1&2&0&1/3\\0&1&0&1/3\\0&0&1&2/3\end{array}}\right]$	$\left[{\begin{array}{ccc|c}1&0&0&-1/3\\0&1&0&1/3\\0&0&1&2/3\end{array}}\right]$

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

$\ x=-{\frac {1}{3}}\ ,\quad y={\frac {1}{3}}\ ,\quad z={\frac {2}{3}}$

שימושים

פתרון מערכת משוואות לינאריות

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

$(I|{\vec {b'}})$

כאשר 'b הוא וקטור ובו איברים ההמתקבלים מצירופים לינאריים של המקדמים החופשיים, ותלויים בפעולות הדירוג שנעשו על המטריצה. למשל, עבור מערכת של 2 משוואות ב-2 נעלמים מקבלים

$\ \left[{\begin{array}{cc|c}1&0&b'_{1}\ \\0&1&b'_{2}\ \end{array}}\right]$

ממנה קוראים את הפתרון $\ x_{1}=b'_{1}\ ,\ x_{2}=b'_{2}$.

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

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

מציאת דרגה של מטריצה

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

חישוב דטרמיננטה

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

• פעולה של החלפת שורות היא ביצוע של חילוף אחד נוסף ולכן הסימן משתנה, ולכן יש לכפול את הדטרמיננטה במינוס אחד, $|A_{\mathrm {new} }|=(-1)\cdot |A_{\mathrm {old} }|$.
• מהעובדה שהדטרמינטה היא מולטי-לינארית, נובע כי על פעולה של הכפלת שורה או עמודה בסקלר $\lambda$, הדטרמיננטה מוכפלת באותו סקלר, $|A_{\mathrm {new} }|=\lambda \cdot |A_{\mathrm {old} }|$
• על פעולה של הוספת שורה מוכפלת בסקלר, לשורה אחרת, ערך הדטרמיננטה לא משתנה, $|A_{\mathrm {new} }|=|A_{\mathrm {old} }|$