Loading AI tools
תהליך הפעלת פעולות אלמנטריות על מטריצות מוויקיפדיה, האנציקלופדיה החופשית
דירוג מטריצות היא הפעלה של פעולות מתמטיות מסוימות על מטריצה, שאינן משנות את מרחב הפתרונות שלה. השימושים של תהליך זה הם מציאת פתרונות של מערכת משוואות ליניאריות, מציאת דרגה של מטריצה, מציאת דטרמיננטה של מטריצה ומציאת המטריצה ההופכית של מטריצות הפיכות.
השיטה שבעזרתה מדרגים מטריצות נקראת "שיטת החילוץ של גאוס" או "שיטת האלימינציה של גאוס", ולעיתים גם "אלימינציית גאוס-ז'ורדן". שיטה זו קרויה על שם המתמטיקאים קרל פרידריך גאוס הגרמני וקאמי ז'ורדן הצרפתי. שיטות דומות מופיעות כבר בפרק השמיני של תשעת הפרקים של אמנות המתמטיקה, כתב מתמטי סיני עתיק מלפני הספירה.
בכל שורה במטריצה שאיננה שורת אפסים, הרכיב הראשון השונה מאפס ייקרא האיבר המוביל של השורה.
מטריצה תקרא מטריצה מדורגת אם היא מקיימת את התנאים הבאים:
מטריצה תקרא מטריצה מדורגת קנונית אם מתקיימים התנאים הבאים:
הרעיון המנחה את האלגוריתם הוא ביצוע פעולות על שורות המטריצה, באופן שאינו משנה את מרחב הפתרונות של המערכת שהיא מייצגת. הפעולות הבאות נקראות פעולות אלמנטריות:
קל לראות באמצעות פעולות אלגבריות פשוטות, כי ביצוע הפעולות האלמנטריות הללו אינו משנה את מרחב הפתרונות.
מטריצה המתקבלת ממטריצת היחידה על ידי הפעלת פעולה אלמנטרית נקראת מטריצה אלמנטרית.
הרעיון של האלגוריתם הוא לבצע רצף של פעולות אלמנטריות כדי להביא אותה לצורה מדורגת קנונית.
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
זמן הריצה של האלגוריתם הוא . קיימות גרסאות יעילות יותר (אסימפטוטית) כגון זו של קופרסמיט-וינוגרד . נכון ל-2018 הסיבוכיות המיטבית היא .
נניח שלפנינו מערכת המשוואות הבאה:
בהצגה מטריציאלית
פעולה | נחסר את השורה הראשונה מהשורה השנייה, ונחסר 3 פעמים את השורה הראשונה מהשורה השלישית | נחבר 5 פעמים את השורה השנייה לשורה השלישית: | ננרמל את השורה השלישית (לקבלת מטריצת מדרגות משולשית) | נחסר את השורה השלישית פעם אחת מהשורה הראשונה, ופעם אחת מהשורה השנייה | נחסר את השורה השנייה פעמיים מהשורה הראשונה |
---|---|---|---|---|---|
מטריצה |
|
|
|
|
וקיבלנו את הצורה המדורגת קנונית ממנה אפשר לקרוא את הפתרון:
שיטת דירוג המטריצות, הידועה גם בשם אלימינציית גאוס-ז'ורדן, היא שיטה לפתרון מערכת משוואות ליניאריות. באלגברה ליניארית מוכיחים כי כל מטריצה ניתנת לדירוג עד להבאתה לצורתה הקנונית היחידה. לכן במסגרת שיטה זו מדרגים את המטריצה המתקבלת מהוספת וקטור המקדמים החופשיים למטריצת המקדמים, ומקבלים מטריצה מדורגת קנונית ממנה אפשר בקלות לקרוא את הפתרון. כאשר יש פתרון יחיד למערכת (המטריצה הפיכה) מגיעים לצורה
כאשר 'b הוא וקטור ובו איברים ההמתקבלים מצירופים ליניאריים של המקדמים החופשיים, ותלויים בפעולות הדירוג שנעשו על המטריצה. למשל, עבור מערכת של 2 משוואות ב-2 נעלמים מקבלים
ממנה קוראים את הפתרון .
כדי למצוא את המטריצה ההפכית של מטריצה הפיכה A, יש ליצור מטריצה חדשה המורכבת מבלוקים A ו-I (מטריצת היחידה). כעת יש לדרג את A לצורת המדרגות הקנונית, כך ש-A תהפוך ל-I, ובמקביל לבצע את אותן הפעולות על I (כלומר: כל פעולה שעושים על שורות A עושים על השורות המקבילות ב-I). המטריצה המתקבלת היא המטריצה ההפכית (אם לא ניתן לדרג את המטריצה המקורית למטריצת היחידה, היא איננה הפיכה).
כדי למצוא דרגה של מטריצה יש לדרג אותה עד לצורה מדורגת (אין צורך להגיע לקנונית דווקא), ואז מספר השורות פחות מספר שורות האפסים שווה לדרגת המטריצה.
הדרך היעילה ביותר לחשב דטרמיננטה עבור מטריצות גדולות (למשל מסדר 4 ומעלה) היא לדרג את המטריצה עד אשר מגיעים למטריצה משולשית. הדטרמיננטה של מטריצה משולשית היא מכפלת איברי האלכסון של המטריצה המשולשית. כדי לקבל את הדטרמיננטה של המטריצה המקורית, יש לעקוב אחרי פעולות הדירוג שביצענו, ולתקן את ערך הדטרמיננטה בהתאם:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.