Mnożenie macierzy


Tematy pokrewne
Macierze
Podstawowe pojęcia dotyczące macierzy
Reprezentacja macierzy w pamięci komputera
Mnożenie macierzy przez skalar
Dodawanie macierzy
Transponowanie macierzy
Mnożenie macierzy
Potęgowanie macierzy
Eliminacja Gaussa
Eliminacja Gaussa-Crouta
Wyznacznik macierzy
Rozkład LU
Rozkład LU – rozwiązywanie układu równań liniowych
Rozkład LU – macierz odwrotna
Rozkład LU – wyznacznik macierzy

Problem

Znaleźć wynik mnożenia macierzy Am × n przez macierz Bn × p.

 

 

 

Aby zrozumieć zasadę mnożenia dwóch macierzy, zastosujemy prosty schemat postępowania. Załóżmy, iż mamy macierz A3 × 4 i 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 = Cm × 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 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
s  – suma częściowa, s R
Lista kroków:
K01: Dla i = 1,2,...,m wykonuj K02...K06  
K02:     Dla j = 1,2,...,p wykonuj K03...K06  
K03:         s ← 0 ; zerujemy sumę częściową
K04:         Dla k = 1,2,...,n wykonuj K05 ; obliczamy sumę iloczynów
K05:             ss + A[i,k] × B[k,j]  
K06:         C[i,j] ← s ; sumę umieszczamy w elemencie macierzy wynikowej
K07: Zakończ  

 

Program

Ważne:

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 rozmiar 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.

Odczytane dane są umieszczane w macierzach, których iloczyn program oblicza i wyprowadza na standardowe wyjście (w języku Basic dane wyjściowe są zapisywane w pliku out.txt).

Przykładowe dane dla programu:

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

 

Lazarus
// Mnożenie macierzy
// Data: 26.01.2010
// (C)2012 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.
Code::Blocks
// Mnożenie macierzy
// Data: 26.01.2010
// (C)2012 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;
}
Free Basic
' Mnożenie macierzy
' Data: 26.01.2010
' (C)2012 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
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

 



List do administratora Serwisu Edukacyjnego I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo  , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

(C)2014 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.