Mnożenie macierzy

wspólna nazwa różnych działań na macierzach

Mnożenie macierzy – operacja mnożenia macierzy przez skalar lub inną macierz. Artykuł zawiera opis różnorodnych sposobów przeprowadzania ich mnożenia.

Standardowe mnożenie macierzy

edytuj

Jest to najczęstszy sposób mnożenia macierzy, nazywany też mnożeniem Cauchy’ego. Działanie to zdefiniowane jest wyłącznie dla macierzy, z których pierwsza ma tyle kolumn, co druga wierszy. Jeżeli   jest macierzą   a   macierzą typu   to ich iloczyn, oznaczany   czasem też   jest macierzą o wymiarach   Jeżeli   a   oznacza element   na pozycji   to[1]:

 

dla każdej pary   dla której   oraz  

Obliczanie z definicji

edytuj

Poniżej zilustrowany został sposób obliczania elementów   oraz   macierzy wynikowej   będącej iloczynem macierzy   i  

 

Przykładowo, element   powstaje z sumy iloczynów odpowiadających sobie elementów z pierwszego wiersza macierzy   i drugiej kolumny macierzy   (elementy macierzy składowych bierzemy zgodnie z kierunkiem strzałek). Innymi słowy, aby wyznaczyć element   musimy wymnożyć pierwszy element z pierwszego wiersza macierzy   przez pierwszy element z drugiej kolumny macierzy   i do tego dodać iloczyn drugiego elementu z pierwszego wiersza macierzy   i drugiego elementu z drugiej kolumny macierzy   Opisane obliczenia poniżej:

 

Każdy element iloczynu macierzy jest iloczynem skalarnym odpowiedniego wiersza pierwszej macierzy i odpowiedniej kolumny drugiej macierzy

 

gdzie   oznacza transpozycję macierzy b.

Podobnie postępujemy z wyróżnionym na niebiesko elementem macierzy   z trzeciego wiersza i trzeciej kolumny:

 

Przykładowo:

 

Metoda współczynniki-wektory

edytuj

To mnożenie macierzy może być rozważane z nieco innego punktu widzenia: sumuje ono wektory po przemnożeniu ich uprzednio przez różne współczynniki. Jeżeli

    oraz    

to

 

Dla powyższych danych jest:

 
 

Wiersze macierzy po lewej są listą współczynników. Macierz po prawej jest listą wektorów. W przykładzie pierwszy wiersz to   czyli bierzemy 1 raz pierwszy wektor, 0 razy drugi wektor i 2 razy trzeci wektor. Równanie można jeszcze uprościć za pomocą iloczynu zewnętrznego:

 

Elementy tej sumy są macierzami tego samego kształtu, z których każda opisuje działanie jednej kolumny z   i jednego wiersza z   na wynik. Kolumny   mogą być postrzegane jako układ współrzędnych przekształcenia, np. dla danego wektora   jest   gdzie   są współrzędnymi wzdłuż „osi”   Wyrazy   są analogiczne do   z tym, że   zawiera i-tą współrzędną każdego wektora kolumnowego macierzy   z której każda jest równocześnie przekształcana niezależnie od pozostałych.

Raz jeszcze stosując dane przykładowe, mamy:

 
 

Wektory   oraz   zostały równocześnie przekształcone na   oraz   Można je również przekształcić po kolei, czyniąc te same kroki:

 

Metoda list wektorowych

edytuj

O zwykłym iloczynie macierzy można myśleć jak o iloczynie skalarnym listy kolumnowej wektorów przez listę wierszową wektorów. Jeżeli

    oraz    

gdzie:

  to wektor wierszowy wszystkich elementów postaci     to wektor wierszowy wszystkich elementów postaci   itd.,
a   jest wektorem kolumnowym wszystkich elementów postaci     wektorem kolumnowym wszystkich elementów postaci   itd.,

to wtedy

 

Własności

edytuj

Mnożenie macierzy nie jest w ogólności przemienne, tj.   Można zaobserwować to następująco: nie można spodziewać się, iż zmiana proporcji wektorów da ten sam wynik. Innym sposobem jest też zwrócenie uwagi na kolejność czynników – liczba kolumn w macierzy proporcji musi być równa liczbie wierszy w macierzy wektorów: muszą one reprezentować tę samą liczbę wektorów. Przypadkiem szczególnym jest np. mnożenie macierzy diagonalnych równego stopnia, które jest przemienne.

Choć mnożenie macierzy nie jest przemienne, to wyznaczniki   oraz   są zawsze równe (jeżeli   i   są macierzami kwadratowymi tego samego stopnia), co wyjaśnione jest w artykule o wyznaczniku.

Mnożenie Cauchy’ego jest istotne, ponieważ jeśli macierze   i   reprezentują przekształcenia liniowe (co powszechnie się czyni), to ich iloczyn   odpowiada złożeniu tych przekształceń, w którym odwzorowanie   wykonywane jest w pierwszej kolejności.

Dodatkowo wszystkie sposoby mnożenia opisane w tym artykule dzielą zestaw wspólnych własności opisanych niżej.

Algorytmy

edytuj

Naiwny algorytm standardowego mnożenia macierzy typu   przez macierz typu   wymaga   mnożeń. Dla macierzy kwadratowych daje to algorytm o złożoności  

Istnieją wydajniejsze algorytmy rozwiązywania tego zadania. Pierwszy z takich algorytmów podał w 1969 r. Volker Strassen – złożoność tego algorytmu to około   Nie jest on jednak zwykle używany w praktyce z powodu braku numerycznej stabilności. Najlepszy obecnie znany algorytm mnożenia macierzy, podany przez Dona Coppersmitha i Shmuela Winograda, ma złożoność rzędu ok.   Dolne oszacowanie złożoności mnożenia macierzy, wynikające z konieczności obliczenia   wartości, to  

Jeśli to możliwe, należy skorzystać z algorytmów wykorzystujących szczególne własności macierzy, np. istnieje prosty algorytm mnożenia macierzy diagonalnych klasy  

Potęgowanie macierzy

edytuj

Definiujemy potęgę macierzy kwadratowej   rekurencyjnie za pomocą wzorów:

  gdzie   jest wymiarem macierzy  
  dla całkowitego nieujemnego  

A zatem

 
 
 

itd.

Operacja potęgowania macierzy ma następujące własności:

  •  
  •  

Naiwny algorytm obliczenia potęgi   wymaga   mnożeń.

Za pomocą algorytmu szybkiego potęgowania potęgę   możemy obliczyć w czasie  

Możliwe jest również potęgowanie za pomocą diagonalizacji – wymaga to podniesienia macierzy diagonalnej do  -tej potęgi (zob. złożoność obliczeniowa iloczynu macierzy); jeżeli macierz   ma współczynniki całkowite, to macierz diagonalna nie musi zachować tej właściwości, co może spowodować błędy zaokrągleń, dlatego jest to metoda mniej ogólna.

Mnożenie macierzy -wskaźnikowych

edytuj

Macierz  -wskaźnikowa   zawiera   wskaźników przebiegających   wartości. Taka macierz zawiera   elementów macierzowych o wartościach zespolonych,

 

Dla macierzy   zdefiniowana jest operacja transpozycji cyklicznej,   przesuwającej wskaźniki o jeden do przodu

 

Mnożenie (iloczyn) macierzy  -wskaźnikowych, zdefiniowane jest jako  -arne działanie wewnętrzne dla dokładnie   macierzy, z których każda ma   wskaźników przebiegających   wartości. Każda macierz zawiera   wartości. Wynikiem jest również macierz  -wskaźnikowa.

Jeżeli   a   oznacza element   na pozycji   to

 

dla każdego wskaźnika   dla których   oraz  

Własności mnożenia macierzy  -wskaźnikowych

edytuj

Mnożenie macierzy  -wskaźnikowych nie jest działaniem łącznym, np. dla   istnieje macierz   taka że  

Transpozycja cykliczna iloczynu macierzy   ma postać

 

Szczególne macierze  -wskaźnikowe

edytuj

Macierze jednostkowe

Macierze jednostkowe definiuje się z pomocą macierzy pomocniczej   (numer w nawiasie oznacza położenie macierzy jednostkowych cyklicznie za macierz pomocniczą, gdy macierz pomocnicza jest w innym położeniu to przy pomocy transpozycji cyklicznej przestawić na ostatnie miejsce równania):

 

Dla macierzy binarnych (przyjmujących tylko wartości 0 i 1) równanie jest jednoznacznie rozwiązywalne.

 

gdzie   jest symbolem Kroneckera.

Podindeksy uważamy za cyklicznie równoważne gdy różnią się o wielokrotność  

Gdy przemieścimy macierz pomocniczą o   miejsc, to

 

Dla pełnego zagadnienia z dowolnym położeniem macierzy pomocniczej i z uwzględnieniem symetrii symbolu Kroneckera otrzymujemy   macierzy jednostkowych. Macierz jednostkowa w niewłaściwym położeniu nie musi być w nim macierzą jednostkową.

Macierze jednostkowe dla każdego położenia wyróżniają parę wskaźników. Dogodnie jest traktować macierz  -wskaźnikową jako zbiór   dwuwskaźnikowych warstw numerowanych przez pozostałe   wskaźniki.

Macierze diagonalne

Jeżeli każda warstwa macierzy   jest dwuwskaźnikową macierzą diagonalną to taką macierz nazywamy macierzą diagonalną.

Macierze odwrotne

Macierze odwrotne definiuje się przez rozwiązanie poniższych dwóch równań (macierze   i   są w tym samym położeniu, uzupełniające macierze jednostkowe nie zostały zaznaczone)

 
 

Macierz   jest macierzą odwrotną do  

Każda warstwa macierzy   jest macierzą odwrotną (dwuwskaźnikową) warstwy o tym samym numerze macierzy  

Zadanie jest wykonalne jeżeli iloczyn wszystkich wyznaczników warstw macierzy   jest różny od zera. Taki iloczyn nazwiemy wyznacznikiem macierzy  

Dla macierzy diagonalnej wyznacznik jest równy iloczynowi wszystkich diagonalnych elementów macierzowych wszystkich warstw.

Macierz osobliwa

Macierz nazwiemy osobliwą, gdy jej wyznacznik jest równy zero.

Zagadnienie odwrotne

edytuj

Zagadnieniem odwrotnym nazywamy wyznaczenie macierzy   z równania

 

Zagadnienie odwrotne jest rozwiązywalne gdy wspólne działanie   macierzy:   jest nieosobliwe.

Jeżeli co najwyżej jedna macierz   jest niediagonalna to działanie jest nieosobliwe gdy wszystkie macierze są nieosobliwe.

Jeżeli co najmniej dwie macierza     są niediagonalne to osobliwość działania jest nieokreślona.

Mnożenie macierzy  -wskaźnikowych jako działanie zewnętrzne

edytuj

Mnożenie

 

możemy traktować jako przekształcenie   wymiarowego wektora   przez wspólne działanie   macierzy   zapisujemy to w postaci

  gdzie   jest   macierzą.

Przekształcenie macierzy   w macierz   jest jednoznaczne, a przekształcenie odwrotne jest niejednoznaczne, a po wykonaniu przekształceń macierzy   może być nieodwracalne.

Elementy macierzowe macierzy   są następujące

 

gdzie:

 
 

Macierz   ma postać quasidiagonalną zawierającą   podmacierzy  

Jeżeli w wyrażeniu   jest tylko   macierzy niediagonalnych to przy zmianie kolejności (wskaźniki primowane) wyliczanych wskaźników (najpierw   wskaźników macierzy niediagonalnych, a następnie   macierzy diagonalnych)

 
 

macierz   przyjmie postać quasidiagonalną zawierającą   podmacierzy  

Tak wyznaczona macierz   daje formalną podstawę do wyznaczania macierzy odwrotnych, rozwiązywania zagadnienia odwrotnego, jak również do badania zagadnienia własnego wspólnego działania jednej lub więcej macierzy  

Mnożenie przez skalar

edytuj

Mnożenie macierzy   przez skalar   daje w wyniku iloczyn   będący macierzą tego samego typu co   Jej współczynniki dane są wzorem

 

Na przykład jeśli

 

to

 

Jeżeli jesteśmy zainteresowani macierzami nad pierścieniem, to powyższe mnożenie nazywa się czasem mnożeniem lewostronnym, podczas gdy mnożenie prawostronne definiowane jest jako

 

Jeżeli pierścień jest przemienny, np. ciało liczb rzeczywistych lub zespolonych, to powyższe mnożenia są tożsame. Jednakże jeśli pierścień nie jest przemienny, jak np. kwaterniony, mogą się one różnić. Przykładowo

 

Iloczyn Hadamarda

edytuj

Dla dwóch macierzy tego samego typu definiuje się iloczyn Hadamarda, znany także jako iloczyn Schura lub iloczyn po współrzędnych. Może być on uogólniony także na operatory. Iloczyn Hadamarda dwóch macierzy   typu   oznaczany przez   jest również macierzą typu   daną wzorem

 

Dla przykładu:

 

Zauważmy, że iloczyn Hadamarda jest podmacierzą iloczynu Kroneckera (zob. niżej). Iloczyn Hadamarda badany jest w teorii macierzy i pojawia się w algorytmach kompresji stratnej takiej jak JPEG, jednak właściwie nie pojawia się w algebrze liniowej[wymaga weryfikacji?]. Dyskusja na ten temat zawarta jest w Horn & Johnson, 1994, rozdz. 5.

Iloczyn Kroneckera

edytuj
Osobny artykuł: iloczyn Kroneckera.

Dla dowolnych dwóch macierzy   oraz   definiuje się iloczyn prosty lub iloczyn Kroneckera (od nazwiska Leopolda Kroneckera) jako

 

Zauważmy, że jeśli   jest macierzą typu   zaś   macierzą typu   to   jest macierzą typu   To mnożenie również nie jest przemienne.

Na przykład

 

Jeżeli   i   reprezentują przekształcenia liniowe, odpowiednio   oraz   to   reprezentuje iloczyn tensorowy dwóch odwzorowań,  

Wspólne własności

edytuj

Wszystkie rodzaje mnożenia macierzy są łączne:

 

rozdzielne względem dodawania:

 

oraz

 

i zgodne z mnożeniem przez skalar:

 
 
 

Należy wspomnieć, że w powyższe trzy wyrażenia będą sobie tożsame, jeśli mnożenie i dodawanie w ciele skalarów będzie przemienne, np. będzie ono pierścieniem przemiennym. Zobacz sekcję mnożenie przez skalar wyżej, aby zobaczyć kontrprzykład dla ciała skalarów kwaternionów.

Iloczyn wewnętrzny Frobeniusa

edytuj

Iloczyn Frobeniusa, oznaczany czasem   jest iloczynem wewnętrznym po składowych dwóch macierzy traktowanych jako wektory. Innymi słowy jest to suma elementów iloczynu Hadamarda, czyli

 

Ten iloczyn skalarny indukuje normę Frobeniusa.

Zobacz też

edytuj

Przypisy

edytuj
  1. mnożenie macierzy, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2024-09-24].

Linki zewnętrzne

edytuj