כפל מטריצות

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

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

המכפלה של מטריצות היא אסוציאטיבית ודיסטריביוטיבית ביחס לחיבור, אבל אינה חילופית (כלומר, בדרך כלל \ AB \neq BA).

המכפלה של מטריצה \,A במטריצה \,B מוגדרת רק כאשר מספר העמודות של \,A שווה למספר השורות של \,B, ואז מספר השורות במכפלה \,AB שווה למספר השורות של \,A, ומספר העמודות שווה למספר העמודות של \,B.

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

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

תהיינה \ A=(a_{ij}) מטריצה בגודל \ n\times m ו-\ B=(b_{ij}) מטריצה בגודל \ m\times p. לפי ההגדרה, מכפלתן היא מטריצה AB בגודל \ n\times p, שאבריה מוגדרים לפי הנוסחה \ (AB)_{ij}=\sum_{k=1}^m a_{ik}b_{kj}.

נסביר זאת: האיבר בשורה \ i ובעמודה \ j של המכפלה AB מתקבל מהכפלת השורה ה-\ i במטריצה הראשונה בעמודה ה-\ j במטריצה השנייה. נשים לב שמספר האיברים הן בשורה והן בעמודה זהה - \ m; אחרת הכפל אינו מוגדר. במלים אחרות, דרוש שמספר העמודות במטריצה הראשונה יהיה שווה למספר השורות במטריצה השנייה - מספר העמודות במטריצה הראשונה קובע כמה איברים יהיו בכל שורה שלה, ואילו מספר השורות במטריצה השנייה קובע כמה איברים יהיו בכל עמודה שלה. כאן פעולת הכפל של הווקטורים דומה למכפלה סקלרית רכיב רכיב: כופלים כל זוג איברים בעלי אותו מספר, וסוכמים את כל המכפלות.

התמונה מראה כפל של מטריצה A מסדר \ 4\times 2 במטריצה B מסדר \ 2\times 3: המטריצה המתקבלת היא מסדר \ 4\times 3. בתמונה מראים כיצד מחושב האיבר \ (AB)_{12} במטריצה: מוכפלת השורה הראשונה במטריצה \ A בעמודה השנייה במטריצה \ B.

Matrix multiplication diagram.svg

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


  \begin{pmatrix}
     1 & 0 \\ 
     -1 & 3
  \end{pmatrix}
\times 
  \begin{pmatrix} 
    3 & 1 \\ 
    2 & 1 \\ 
      \end{pmatrix}




=
\begin{pmatrix} 
   (1 \times 3+0 \times 2) & (1 \times 1+0 \times 1) \\
   (-1 \times 3+3 \times 2) & (-1 \times 1+3 \times 1) \end{pmatrix}
= 
\begin{pmatrix} 3 & 1 \\ 3 & 2 \end{pmatrix}


על-פי-רוב כפל מטריצות אינו קומוטטיבי כלומר AB אינו שווה ל BA :


\begin{pmatrix}
1 & 2 & 0 \\
4 & 3 & -1 \\
\end{pmatrix}

\begin{pmatrix}
5 & 1 \\
2 & 3 \\
3 & 4 \\
\end{pmatrix}

=

\begin{pmatrix}
9 & 7 \\
23 & 9 \\
\end{pmatrix}

          בעוד ש           

\begin{pmatrix}
5 & 1 \\
2 & 3 \\
3 & 4 \\
\end{pmatrix}

\begin{pmatrix}
1 & 2 & 0 \\
4 & 3 & -1 \\
\end{pmatrix}

=

\begin{pmatrix}
9 & 13 & -1 \\
14 & 13 & -3 \\
19 & 18 & -4 \\
\end{pmatrix}

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

לשתי מטריצות יש תפקיד מיוחד ביחס לכפל: מטריצת האפס (שכל רכיביה אפסים) היא נייטרלית ביחס לחיבור (כלומר, \ A+0=0+A=A), ותוצאת הכפל במטריצת האפס היא תמיד אפס (\ 0 \cdot A = A \cdot 0 = 0). מטריצת היחידה I, שהיא מטריצה ריבועית, שרכיבי האלכסון שלה הם 1 ושאר הרכיבים אפס, היא נייטרלית ביחס לכפל (כלומר, \ A \cdot I = I \cdot A = A).

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

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

הכפלת שתי מטריצות ריבועיות בגודל n על n על פי ההגדרה דורש סיבוכיות של סדר גודל n בשלישית פעולות.

ב-1969 הראה וולקר שטראסן כי ניתן להכפיל מטריצות באופן יעיל יותר ("אלגוריתם שטראסן") של n^{\log_2 7} (בערך 2.807). שיפורים נוספים הורידו את החזקה ל-2.376 (דון קופרסמיט ושמואל וינוגרד, 1987), ואז ל-2.373 (2010). זו הסיבוכיות הטובה ביותר הידועה, אם כי הקבועים העצומים הופכים את האלגוריתם הזה לתאורטי בלבד.

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

למרות שנראה כי הגדרתו של הכפל בלתי אינטואיטיבית, ניתן לראות במספר דוגמאות את יעילותו:

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

מכפלה טנזורית של מטריצות[עריכת קוד מקור | עריכה]

מכפלה טנזורית או "מכפלת קרונקר" ( על-שם לאופולד קרונקר ) מסומנת AB ומוגדרת למטריצה A=(a_{ij}) ומטריצה B כ:



  \begin{pmatrix} 
    a_{11}B & a_{12}B & \cdots & a_{1n}B \\ 
    \vdots & \vdots & \ddots & \vdots \\ 
    a_{m1}B & a_{m2}B & \cdots & a_{mn}B
  \end{pmatrix}


אם A היא מטריצה עם (m, n) איברים, ו B מטריצה עם (p, r) איברים, אז AB היא מטריצה עם (mp, nr) איברים. לדוגמה:



  \begin{pmatrix} 
    1 & 2 \\ 
    3 & 1 \\ 
  \end{pmatrix}
\otimes
  \begin{pmatrix} 
    0 & 3 \\ 
    2 & 1 \\ 
  \end{pmatrix}
=
  \begin{pmatrix} 
    1\times 0 & 1\times 3 & 2\times 0 & 2\times 3 \\ 
    1\times 2 & 1\times 1 & 2\times 2 & 2\times 1 \\ 
    3\times 0 & 3\times 3 & 1\times 0 & 1\times 3 \\ 
    3\times 2 & 3\times 1 & 1\times 2 & 1\times 1 \\ 
  \end{pmatrix}
=
  \begin{pmatrix} 
    0 & 3 & 0 & 6 \\ 
    2 & 1 & 4 & 2 \\
    0 & 9 & 0 & 3 \\
    6 & 3 & 2 & 1
  \end{pmatrix}
.


פעולה זו אינה קומוטטיבית.

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

מכפלה איבר איבר של מטריצות מכונה "מכפלת הדמר" (Hadamard). באופן פורמלי היא מוגדרת כך: אם \ A = (a_{ij}), \ B = (b_{ij}) הן שתי מטריצות בגודל \ n \times m, אז מכפלת הדמר שלהן מוגדרת כך: \ A\circ B = (a_{ij}\cdot b_{ij}). עבור מטריצות שאינן מאותו גודל המכפלה אינה מוגדרת.

דוגמה:


  \begin{pmatrix}
    1 & 3 & 2 \\ 
    1 & 0 & 0 \\ 
    1 & 2 & 2
  \end{pmatrix}
\cdot
  \begin{pmatrix} 
    0 & 0 & 2 \\ 
    7 & 5 & 0 \\ 
    2 & 1 & 1
  \end{pmatrix}
=
  \begin{pmatrix} 
    1 \times 0 & 3 \times 0 & 2 \times 2 \\ 
    1 \times 7 & 0 \times 5 & 0 \times 0 \\ 
    1 \times 2 & 2 \times 1 & 2 \times 1
  \end{pmatrix}
=
  \begin{pmatrix} 
    0 & 0 & 4 \\ 
    7 & 0 & 0 \\ 
    2 & 2 & 2
  \end{pmatrix}


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

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

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