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

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Mnożenie macierzy

SPIS TREŚCI
Tematy pomocnicze

Problem

Należy znaleźć wynik mnożenia macierzy A m × n przez macierz B n × p.

Rozwiązanie

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

A 3 × 4 =
  1 2 3 4  
  5 6 7 8  
  9 8 7 6  
  B 4 × 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:

A m × n × B n × p = C m × p

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

Obliczamy element c 1, 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       ? ? ? ? ?  
c 1, 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:

A m × n, B n × p

Podobnie obliczamy element c 1, 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       ? ? ? ? ?  
c 1, 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       ? ? ? ? ?  
c 1, 3 = ( 1 × 2 ) + ( 2 × 5 ) + ( 3 × 8 ) + ( 4 × 3 ) = 2 + 10 + 24 + 12 = 48
c 1, 4 = ( 1 × 1 ) + ( 2 × 6 ) + ( 3 × 7 ) + ( 4 × 2 ) = 1 + 12 + 21 +   8 = 42
c 1, 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       ? ? ? ? ?  
c 2, 1 = ( 5 × 4 ) + ( 6 × 3 ) + ( 7 × 8 ) + ( 8 × 5 ) = 20 + 18 + 56 + 40 = 134
c 2, 2 = ( 5 × 3 ) + ( 6 × 4 ) + ( 7 × 9 ) + ( 8 × 4 ) = 15 + 24 + 63 + 32 = 134
c 2, 3 = ( 5 × 2 ) + ( 6 × 5 ) + ( 7 × 8 ) + ( 8 × 3 ) = 10 + 30 + 56 + 24 = 120
c 2, 4 = ( 5 × 1 ) + ( 6 × 6 ) + ( 7 × 7 ) + ( 8 × 2 ) =   5 + 36 + 49 + 16 = 106
c 2, 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  
c 3, 1 = ( 9 × 4 ) + ( 8 × 3 ) + ( 7 × 8 ) + ( 6 × 5 ) = 36 + 24 + 56 + 30 = 146
c 3, 2 = ( 9 × 3 ) + ( 8 × 4 ) + ( 7 × 9 ) + ( 6 × 4 ) = 27 + 32 + 63 + 24 = 146
c 3, 3 = ( 9 × 2 ) + ( 8 × 5 ) + ( 7 × 8 ) + ( 6 × 3 ) = 18 + 40 + 56 + 18 = 132
c 3, 4 = ( 9 × 1 ) + ( 8 × 6 ) + ( 7 × 7 ) + ( 6 × 2 ) =   9 + 48 + 49 + 12 = 118
c 3, 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

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

Dane przykładowe ( 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
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
©2020 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.