Mnożenie macierzy
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
edytujJest 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
edytujPoniż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
edytujTo 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
edytujO 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
edytujMnoż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
edytujNaiwny 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
edytujDefiniujemy 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
edytujMacierz -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
edytujMnoż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
edytujMacierze 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
edytujZagadnieniem 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
edytujMnoż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
edytujMnoż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
edytujDla 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
edytujDla 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
edytujWszystkie 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
edytujIloczyn 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ż
edytujPrzypisy
edytuj- ↑ mnożenie macierzy, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2024-09-24] .
Linki zewnętrzne
edytuj- Przemysław Kiciak , Schemat Falka, „Delta”, luty 2014, ISSN 0137-3005 [dostęp 2022-07-19] .
- Piotr Stachura, nagrania dla Khan Academy na YouTube [dostęp 2024-06-22]:
- Wprowadzenie do mnożenia macierzy, 19 września 2017.
- Przykład mnożenia macierzy, 19 września 2017.
- Czy mnożenie macierzy jest przemienne?, 21 września 2017.
- Czy mnożenie macierzy jest łączne?, 21 września 2017.
- Macierze zerowe i mnożenie macierzy, 10 października 2017.
- Transpozycja iloczynu macierzy, 30 kwietnia 2021.
- How AI Discovered a Faster Matrix Multiplication Algorithm, kanał Quanta Magazine na YouTube, 22 maja 2023 [dostęp 2024-08-24].