Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Mnożenie macierzy

SPIS TREŚCI
Tematy pomocnicze

Problem

Należy znaleźć wynik mnożenia macierzy Am×n przez macierz Bn×p.

Rozwiązanie

Aby zrozumieć zasadę mnożenia dwóch macierzy, zastosujemy prosty schemat postępowania. Załóżmy, iż mamy macierze A3×4 B4×5 o następującej zawartości:

A3×4 =
 
1 2 3 4
5 6 7 8
9 8 7 6
 
   
   
B4×5 =
 
4 3 2 1 2
3 4 5 6 7
8 9 8 7 6
5 4 3 2 1
 
   
   

Wynikiem mnożenia dwóch macierzy jest nowa macierz, która posiada tyle wierszy, ile wierszy miała macierz A oraz tyle kolumn, ile kolumn miała macierz B. W naszym przypadku macierz ta będzie posiadała rozmiar 3×5, ponieważ macierz A posiada 3 wiersze, a macierz B posiada 5 kolumn. Zatem:

Am×n×Bn×p = Cn×p

Oznaczmy tę macierz jako C3×5. Po lewej stronie macierzy C umieszczamy macierz A, natomiast macierz B umieszczamy ponad macierzą C.

Obliczamy element c1, 1 jako sumę iloczynów kolejnych elementów wiersza 1 macierzy A przez elementy kolumny 1 macierzy B:

   
 
 
 
 
 
 
 
 4
 3
 2
 1
 2
 
   
 
 
 
 
 
 
 
 3
 4
 5
 6
 7
 
   
 
 
 
 
 
 
 8
 9
 8
 7
 6
   
 
 
 
 
 
 
 
 5
 4
 3
 2
 1
 
 

		

		

		

		

		

		

		

		

		

		
   
1
2
3
4
 
 
 
54
 ?
 ?
 ?
 ?
 
   
5
6
7
8
 
 
 
 ?
 ?
 ?
 ?
 ?
 
   
9
8
7
6
 
 
 
 ?
 ?
 ?
 ?
 ?
 
c1,1 = (1×4)+(2×3)+(3×8)+(4×5) = 4+6+24+20 = 54

Wynika z tego fakt, iż macierz A musi posiadać w wierszu tyle samo elementów, co macierz B ma ich w kolumnie. Zatem rozmiary tych macierzy nie mogą być dowolne, lecz muszą spełniać prosty warunek:

Am×n Bn×p

Podobnie obliczamy element c1, 2 jako sumę iloczynów kolejnych elementów wiersza 1 macierzy A przez elementy kolumny 2 macierzy B:

   
 
 
 
 
 
 
 
 4
 3
 2
 1
 2
 
   
 
 
 
 
 
 
 
 3
 4
 5
 6
 7
 
   
 
 
 
 
 
 
 8
 9
 8
 7
 6
   
 
 
 
 
 
 
 
 5
 4
 3
 2
 1
 
 

		

		

		

		

		

		

		

		

		

		
   
1
2
3
4
 
 
 
54
54
 ?
 ?
 ?
 
   
5
6
7
8
 
 
 
 ?
 ?
 ?
 ?
 ?
 
   
9
8
7
6
 
 
 
 ?
 ?
 ?
 ?
 ?
 
c1,2 = (1×3)+(2×4)+(3×9)+(4×4) = 3+8+27+16 = 54

Operację tę kontynuujemy aż do wyliczenia wszystkich elementów w wierszu 1 macierzy C:

   
 
 
 
 
 
 
 
 4
 3
 2
 1
 2
 
   
 
 
 
 
 
 
 
 3
 4
 5
 6
 7
 
   
 
 
 
 
 
 
 8
 9
 8
 7
 6
   
 
 
 
 
 
 
 
 5
 4
 3
 2
 1
 
 

		

		

		

		

		

		

		

		

		

		
   
1
2
3
4
 
 
 
54
54
48
42
38
 
   
5
6
7
8
 
 
 
 ?
 ?
 ?
 ?
 ?
 
   
9
8
7
6
 
 
 
 ?
 ?
 ?
 ?
 ?
 
c1,3 = (1×2)+(2×5)+(3×8)+(4×3) = 2+10+24+12 = 48
c1,4 = (1×1)+(2×6)+(3×7)+(4×2) = 1+12+21+ 8 = 42
c1,5 = (1×2)+(2×7)+(3×6)+(4×1) = 2+14+18+ 4 = 38

Po wyliczeniu wiersza 1 macierzy C rozpoczynamy obliczanie elementów wiersza 2. Działania wykonujemy wg tego samego schematu – sumujemy iloczyny kolejnych elementów wiersza macierzy A przez kolejne elementy kolumny macierzy B.

 
 
 
 
 
 
 
 
 
  4
  3
  2
  1
  2
 
 
 
 
 
 
 
 
 
 
  3
  4
  5
  6
  7
 
 
 
 
 
 
 
 
 
  8
  9
  8
  7
  6
 
 
 
 
 
 
 
 
 
  5
  4
  3
  2
  1
 
 

		

		

		

		

		

		

		

		

		

		
 
 
1
2
3
4
 
 
 
 54
 54
 48
 42
 38
 
 
 
5
6
7
8
 
 
 
134
134
120
106
102
 
 
 
9
8
7
6
 
 
 
  ?
  ?
  ?
  ?
  ?
 
c2,1 = (5×4)+(6×3)+(7×8)+(8×5) = 20+18+56+40 = 134
c2,2 = (5×3)+(6×4)+(7×9)+(8×4) = 15+24+63+32 = 134
c2,3 = (5×2)+(6×5)+(7×8)+(8×3) = 10+30+56+24 = 120
c2,4 = (5×1)+(6×6)+(7×7)+(8×2) =  5+36+49+16 = 106
c2,5 = (5×2)+(6×7)+(7×6)+(8×1) = 10+42+42+ 8 = 102

Na koniec wyliczamy ostatni wiersz macierzy C według tego samego schematu postępowania:

 
 
 
 
 
 
 
 
 
  4
  3
  2
  1
  2
 
 
 
 
 
 
 
 
 
 
  3
  4
  5
  6
  7
 
 
 
 
 
 
 
 
 
  8
  9
  8
  7
  6
 
 
 
 
 
 
 
 
 
  5
  4
  3
  2
  1
 
 

		

		

		

		

		

		

		

		

		

		
 
 
1
2
3
4
 
 
 
 54
 54
 48
 42
 38
 
 
 
5
6
7
8
 
 
 
134
134
120
106
102
 
 
 
9
8
7
6
 
 
 
146
146
132
118
122
 
c3,1 = (9×4)+(8×3)+(7×8)+(6×5) = 36+24+56+30 = 146
c3,2 = (9×3)+(8×4)+(7×9)+(6×4) = 27+32+63+24 = 146
c3,3 = (9×2)+(8×5)+(7×8)+(6×3) = 18+40+56+18 = 132
c3,4 = (9×1)+(8×6)+(7×7)+(6×2) =  9+48+49+12 = 118
c3,5 = (9×2)+(8×7)+(7×6)+(6×1) = 18+56+42+ 6 = 122

Rachunek skończony. Możemy zapisać:

 
 
1 2 3 4
5 6 7 8
9 8 7 6
 
 
   
 
   
×
 
4 3 2 1 2
3 4 5 6 7
8 9 8 7 6
5 4 3 2 1
 
   
   
=
 
 54  54  48  42  38
134 134 120 106 102
146 146 132 118 122
 
   
   

Algorytm mnożenia macierzy

Wejście:

m, n, p : rozmiary macierzy; m, n, p ∈ N.
A
 : macierz o rozmiarze m×n; A ∈ R.
B
 : macierz o rozmiarze n×p; B ∈ R.
C
 : macierz o rozmiarze m×p; C ∈ R.

Wyjście:

Macierz C = A×B.

Elementy pomocnicze:

i, j, k : indeksy elementów macierzy; i, j, k ∈ N. Indeksy elementów rozpoczynają się od wartości 1.
s : suma częściowa; s ∈ N.

Lista kroków:

K01: Dla i = 1, 2, …, m:
     wykonuj kroki K02…K05
K02:   Dla j = 1, 2, …, p:
       wykonuj kroki K03…K05
K03:     s ← 0 ; zerujemy sumę częściową
K04:     Dla k = 1, 2, …, n:
         wykonuj:
           ss+A[i, kB[k, j] ; obliczamy sumę iloczynów
K05:     C[i, j] ← s ; sumę umieszczamy w elemencie
                    ; macierzy wynikowej
K06: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje dane ze standardowego wejścia. Dane powinny posiadać następujący format:

Pierwsze trzy liczby określają kolejno rozmiary macierzy m, n i p.
Dalsze m×n liczb określa zawartość macierzy A. Dane są wprowadzane kolejno wierszami.
Kolejne n×p liczb określa zawartość macierzy B. Dane są wprowadzane kolejno wierszami.

Odczytane dane są umieszczane w macierzach, których iloczyn program oblicza i wyprowadza na standardowe wyjście.

Przykładowe dane (przekopiuj do schowka i wklej do okna konsoli):

3 4 5
1 2 3 4
5 6 7 8
9 8 7 6
4 3 2 1 2
3 4 5 6 7
8 9 8 7 6
5 4 3 2 1
Pascal
// Mnożenie macierzy
// Data: 26.01.2010
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program mmultiply;

type
  NInt = array of integer; // typ tablic wierszy
  MInt = array of NInt;    // typ tablicy wskaźników

var
  A, B, C : MInt;
  m, n, p, i, j, k, s : integer;

begin

  // odczytujemy wymiary macierzy
  read(m, n, p);

  // tworzymy macierze o odpowiednich rozmiarach
  SetLength(A, m);
  SetLength(B, n);
  SetLength(C, m);

  for i := 0 to m-1 do
  begin
    SetLength(A[i], n);
    SetLength(C[i], p);
  end;

  for i := 0 to n-1 do SetLength(B[i], p);

  // odczytujemy dane dla macierzy A
  for i := 0 to m-1 do
    for j := 0 to n-1 do read(A[i][j]);

  // odczytujemy dane dla macierzy B
  for i := 0 to n-1 do
    for j := 0 to p-1 do read(B[i][j]);
  writeln;

  // mnożymy macierz A przez B i wynik umieszczamy w C
  for i := 0 to m-1 do
    for j := 0 to p-1 do
    begin
      s := 0;
      for k := 0 to n-1 do s := s+A[i][k]*B[k][j];
      C[i][j] := s;
    end;

  // wyprowadzamy wynik mnożenia w C
  writeln('C = A x B:');

  for i := 0 to m-1 do
  begin
    for j := 0 to p-1 do write(C[i][j]:6);
    writeln;
  end;

  // zwalniamy pamięć zajętą przez macierze
  for i := 0 to m-1 do
  begin
    SetLength(A[i], 0);
    SetLength(C[i], 0);
  end;

  for i := 0 to n-1 do SetLength(B[i], 0);
  SetLength(A, 0);
  SetLength(B, 0);
  SetLength(C, 0);

end.
C++
// Mnożenie macierzy
// Data: 26.01.2010
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  int **A, **B, **C, m, n, p, i, j, k, s;

  // odczytujemy wymiary macierzy
  cin >> m >> n >> p;

  // tworzymy macierze o odpowiednich rozmiarach
  A = new int * [m];
  B = new int * [n];
  C = new int * [m];

  for(i = 0; i < m; i++)
  {
    A[i] = new int[n];
    C[i] = new int[p];
  }

  for(i = 0; i < n; i++)
    B[i] = new int[p];

  // odczytujemy dane dla macierzy A
  for(i = 0; i < m; i++)
    for(j = 0; j < n; j ++)
      cin >> A[i][j];

  // odczytujemy dane dla macierzy B
  for(i = 0; i < n; i++)
    for(j = 0; j < p; j++)
      cin >> B[i][j];

  cout << endl;

  // mnożymy macierz A przez B
  // i wynik umieszczamy w C
  for(i = 0; i < m; i++)
    for(j = 0; j < p; j++)
    {
      s = 0;
      for(k = 0; k < n; k++)
        s += A[i][k]*B[k][j];
      C[i][j] = s;
    }

  // wyprowadzamy wynik mnożenia w C
  cout <<  "C = A x B:\n";

  for(i = 0; i < m; i++)
  {
    for(j = 0; j < p; j++)
      cout << setw(6) << C[i][j];
    cout << endl;
  }

  // zwalniamy pamięć zajętą przez macierze
  for(i = 0; i < m; i++)
  {
    delete [] A[i];
    delete [] C[i];
  }

  for(i = 0; i < n; i++)
    delete [] B[i];
  delete [] A;
  delete [] B;
  delete [] C;

  return 0;
}
Basic
' Mnożenie macierzy
' Data: 26.01.2010
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Dim As Integer m, n, p, i, j, k, s

' odczytujemy wymiary macierzy
Open Cons For Input As #1
Input #1, m, n, p

' tworzymy macierze o odpowiednich rozmiarach
Dim As Integer A(1 To m, 1 To n), _
               B(1 To n, 1 To p), _
               C(1 To m, 1 To p)

' odczytujemy dane dla macierzy A
For i = 1 To m
  For j = 1 To n
    Input #1, A(i, j)
  Next
Next

' odczytujemy dane dla macierzy B
For i = 1 To n
  For j = 1 To p
    Input #1, B(i, j)
  Next
Next

Close #1

' mnożymy macierz A przez B i wynik umieszczamy w C
For i = 1 To m
  For j = 1 To p
    s = 0
    For k = 1 To n
      s += A(i, k)*B(k, j)
    Next
    C(i, j) = s
  Next
Next

' wyprowadzamy wynik mnożenia w C
Print "C = A x B:"

For i = 1 To m
  For j = 1 To p
    Print Using "######";C(i, j);
  Next
  Print
Next

End
Python (dodatek)
# Mnożenie macierzy
# Data: 26.01.2010
# (C)2020 mgr Jerzy Wałaszek
# ---------------------------


# wyświetla macierz
# ------------------
def mprint(t, x):
    print(t)
    for i in x:
        for j in i:
            print("%6d" % j, end="")
        print()
    print()


# odczytujemy wymiary macierzy
arr = input().split()
m = int(arr[0])
n = int(arr[1])
p = int(arr[2])
# tworzymy macierze o odpowiednich rozmiarach
a = []
b = []
c = []
for i in range(m):
    arr = []
    for j in range(p):
        arr.append(0)
    c.append(arr)
# odczytujemy dane dla macierzy A
for i in range(m):
    s = input().split()
    arr = [0.0] * len(s)
    for j in range(len(s)):
        arr[j] = int(s[j])
    a.append(arr)
# odczytujemy dane dla macierzy B
for i in range(n):
    s = input().split()
    arr = [0.0] * len(s)
    for j in range(len(s)):
        arr[j] = int(s[j])
    b.append(arr)
print()
# mnożymy macierz A przez B
# i wynik umieszczamy w C
for i in range(m):
    for j in range(p):
        s = 0
        for k in range(n):
            s += a[i][k] * b[k][j]
        c[i][j] = s
# wyprowadzamy wynik mnożenia w C
mprint("C = A x B:", c)
# zwalniamy pamięć zajętą przez macierze
a = None
b = None
c = None
arr = None
Wynik:
3 4 5
1 2 3 4
5 6 7 8
9 8 7 6
4 3 2 1 2
3 4 5 6 7
8 9 8 7 6
5 4 3 2 1

C = A x B:
    54    54    48    42    38
   134   134   120   106   102
   146   146   132   118   122

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.