Aby zrozumieć zasadę mnożenia dwóch macierzy, zastosujemy prosty schemat
postępowania. Załóżmy, iż mamy macierze A3×4
i B4×5 o
następującej zawartości:
A3×4 =
|
|
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:
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:
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ć:
|
×
|
|
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.
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:
s ← s+A[i, k]×B[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
|