Rozwinięcie według dopełnień (rozwinięcie Laplace’a): praktyczny przewodnik

Obliczanie wyznacznika macierzy 3×3 — lub większej — nie jest tak proste, jak w przypadku 2×2.

Nie wystarczy po prostu pomnożyć na krzyż dwóch przekątnych. Im większa macierz, tym bardziej kłopotliwe stają się rachunki. Bez uporządkowanej metody łatwo stracić orientację. Właśnie taki problem rozwiązuje rozwinięcie według dopełnień — nazywane też rozwinięciem Laplace’a.

Rozwinięcie według dopełnień to metoda obliczania wyznacznika dowolnej macierzy kwadratowej poprzez rozwinięcie wzdłuż wybranego wiersza lub kolumny. Rozbija problem rekursywnie na mniejsze wyznaczniki, które już umiemy obliczać.

W tym artykule omówię definicję rozwinięcia według dopełnień, stojący za nią wzór, przykłady krok po kroku dla macierzy 2×2 i 3×3, kluczowe własności oraz praktyczne zastosowania.

Czym jest rozwinięcie według dopełnień?

Rozwinięcie według dopełnień to rekursywna metoda obliczania wyznacznika dowolnej macierzy kwadratowej.

W tym sensie „rekursywna” oznacza, że zamiast liczyć wyznacznik dużej macierzy od razu, rozbijamy go na mniejsze wyznaczniki. Te mniejsze rozbijają się dalej na jeszcze mniejsze. Kontynuujemy, aż zostaną wyznaczniki 2×2, które są trywialne do obliczenia.

To działa dla każdej macierzy kwadratowej — 2×2, 3×3, 4×4 i większych. Najbardziej przydaje się jednak przy macierzach 3×3 i większych, gdzie nie można już po prostu pomnożyć dwóch przekątnych na krzyż.

Rdzeń pomysłu jest prosty. Wybieramy jeden wiersz lub jedną kolumnę w macierzy i rozwijamy wzdłuż niej. Każdy element w tym wierszu lub kolumnie wnosi mniejszy podproblem. Rozwiązujemy każdy z nich, łączymy wyniki i otrzymujemy wyznacznik. Tyle.

Minor i dopełnienie algebraiczne: kluczowe definicje

Zanim rozwinie się wyznacznik, trzeba zrozumieć dwa elementy składowe: minory i dopełnienia.

Minor

Minor M_ij to wyznacznik mniejszej macierzy powstałej po usunięciu z macierzy wyjściowej wiersza i i kolumny j.

Załóżmy, że mamy macierz 3×3 A i chcemy minor M_12. Usuwamy wiersz 1 i kolumnę 2. Zostaje macierz 2×2. Liczymy jej wyznacznik — to nasz minor.

Dopełnienie algebraiczne

Dopełnienie algebraiczne C_ij idzie o krok dalej. Nakłada czynnik znaku zależny od położenia (i, j):

Dopełnienie algebraiczne

Czynnik (-1)^(i+j) zachowuje znak minora lub go odwraca — zależnie od położenia w macierzy.

Gdy i + j jest parzyste, (-1)^(i+j) = +1, więc dopełnienie równa się minorowi. Gdy i + j jest nieparzyste, (-1)^(i+j) = -1, więc dopełnienie odwraca znak minora.

Wzór szachownicy

To naprzemienne znakowanie tworzy w macierzy wzór szachownicy:

Wzór szachownicy

Lewy górny róg zawsze zaczyna się od +. Dalej znaki zmieniają się naprzemiennie w każdym kierunku. Ten wzór od razu podpowiada, czy dane dopełnienie będzie dodawać do wyznacznika, czy go odejmować.

Wzór na rozwinięcie według dopełnień

Oto wzór, na który Pan/Pani czeka.

Dla rozwinięcia wzdłuż wiersza i:

Rozwinięcie wzdłuż wiersza i

Dla rozwinięcia wzdłuż kolumny j:

Rozwinięcie wzdłuż kolumny j

Mówiąc prosto: mnożymy każdy element w wybranym wierszu lub kolumnie przez jego dopełnienie algebraiczne, a następnie sumujemy wszystko.

Wyrażenia a_ij to po prostu poszczególne elementy macierzy. Wyrażenia C_ij to dopełnienia obliczone dla każdej pozycji. Mnożymy je, sumujemy wyniki i mamy wyznacznik.

Nie ma znaczenia, który wiersz lub którą kolumnę wybierzemy. Rozwinięcie wzdłuż wiersza 1 da ten sam wynik, co wzdłuż wiersza 3 lub kolumny 2. Wyznacznik jest stałą własnością macierzy — ścieżka rozwinięcia to tylko nasz wybór.

Ten wybór wpływa jednak na ilość pracy. Wiersz lub kolumna z większą liczbą zer oznacza mniej dopełnień do policzenia. Jeśli w wierszu są dwa zera i trzy elementy niezerowe, trzeba policzyć dopełnienia tylko dla tych trzech — zera nic nie wnoszą do sumy. Zawsze proszę przeskanować macierz w poszukiwaniu zer, zanim Pan/Pani wybierze wiersz lub kolumnę do rozwinięcia.

Krok po kroku: jak działa rozwinięcie według dopełnień

Rozwinięcie według dopełnień zawsze przebiega w 3 tych samych krokach.

Krok 1: Wybierz wiersz lub kolumnę. Przeskanuj macierz i wybierz wiersz lub kolumnę z największą liczbą zer. Mniej elementów niezerowych to mniej dopełnień do policzenia.

Krok 2: Dla każdego niezerowego elementu w tym wierszu lub kolumnie:

• Policz minor M_ij — usuń wiersz i i kolumnę j, a następnie weź wyznacznik tego, co zostało.

• Zastosuj czynnik znaku (-1)^(i+j), korzystając ze wzoru szachownicy, aby otrzymać dopełnienie C_ij.

• Pomnóż element a_ij przez jego dopełnienie C_ij.

Krok 3: Zsumuj wszystkie iloczyny.

Wyznacznik

To jest Pana/Pani wyznacznik.

Jeśli któreś z podmacierzy są większe niż 2×2, proszę powtórzyć ten sam proces na nich, aż zostaną wyznaczniki 2×2 — które można obliczyć bezpośrednio wzorem ad - bc.

Przykład 1: rozwinięcie według dopełnień dla macierzy 2×2

Połączmy wszystko w najprostszym możliwym przypadku.

Weźmy tę macierz 2×2:

Przykładowa macierz 2x2

Rozwińmy wzdłuż wiersza 1. Dwa elementy to a_11 = 3 i a_12 = 1.

• Dla a_11 = 3: usuń wiersz 1 i kolumnę 1. Zostaje po prostu (4). Czynnik znaku to (-1)^(1+1) = +1. Zatem C_11 = +4.

• Dla a_12 = 1: usuń wiersz 1 i kolumnę 2. Zostaje po prostu (2). Czynnik znaku to (-1)^(1+2) = -1. Zatem C_12 = -2.

Teraz zsumujmy iloczyny:

Obliczenie wyznacznika

Zauważmy, że to zgadza się ze standardowym wzorem 2×2 ad - bc = (3)(4) - (1)(2) = 10. Rozwinięcie według dopełnień i skrót „mnożenie na krzyż” to dwie drogi do tego samego wyniku.

Przykład 2: rozwinięcie według dopełnień dla macierzy 3×3

Przejdźmy teraz przez pełny przykład 3×3.

Rozważmy tę macierz:

Przykładowa macierz 3x3

W wierszu 1 mamy zero w pozycji (1,2), więc rozwińmy wzdłuż wiersza 1. To zero pozwala całkowicie pominąć jedno dopełnienie.

Krok 1: Przygotuj rozwinięcie

Ustawienie rozwinięcia (1)

Ponieważ a_12 = 0, wyraz środkowy znika:

Ustawienie rozwinięcia (2)

Musimy policzyć tylko dwa dopełnienia. To nagroda za dobór właściwego wiersza.

Krok 2: Oblicz C_11

Teraz usuńmy wiersz 1 i kolumnę 1. Oto co zostaje:

Pierwsze obliczenie

Znak w pozycji (1,1) to (-1)^(1+1) = +1, więc C_11 = +2.

Krok 3: Oblicz C_13

Kolejny krok to usunięcie wiersza 1 i kolumny 3. Zostaje:

Drugie obliczenie

Znak w pozycji (1,3) to (-1)^(1+3) = +1, więc C_13 = +11.

Krok 4: Zsumuj iloczyny

Obliczenie wyznacznika

To jest Pana/Pani wyznacznik. Wybierając na początku wiersz z zerem, zamieniono problem trzech dopełnień na dwa. Zawsze warto pracować sprytniej.

Wybór najlepszego wiersza lub kolumny

Wybór wiersza lub kolumny nie zmienia wyniku, ale zmienia liczbę wykonywanych działań.

Zawsze najpierw proszę szukać zer. Każde zero w wybranym wierszu lub kolumnie to jedno dopełnienie mniej do obliczenia. W powyższym przykładzie 3×3 jedno zero zmniejszyło pracę z trzech dopełnień do dwóch. W większych macierzach wiersz z wieloma zerami może oszczędzić liczenie kilku podwyznaczników.

Oto kilka rzeczy wartych zapamiętania

• Jedno zero w wierszu lub kolumnie oznacza o jedno dopełnienie mniej do policzenia
• Dwa zera oznaczają dwa dopełnienia mniej
• Same zera poza jednym elementem oznaczają, że liczymy tylko jedno dopełnienie

To ma coraz większe znaczenie wraz ze wzrostem rozmiaru macierzy. Naiwne rozwinięcie według dopełnień dla macierzy n×n działa w czasie silniowym — tzn. dla 4×4 trzeba policzyć wyznaczniki czterech macierzy 3×3, z których każda rozwija się do trzech macierzy 2×2. To 24 osobne obliczenia, zanim zaczniemy sumować. Dla 5×5 — 120.

Dla dużych macierzy rozwinięcie według dopełnień nie jest właściwym narzędziem. Redukcja wierszy i rozkład LU radzą sobie z dużymi macierzami znacznie szybciej. Rozwinięcie według dopełnień najlepiej zostawić dla przypadków 2×2 i 3×3 lub pracy teoretycznej, gdzie trzeba symbolicznie wyrazić wyznacznik.

Przy obliczeniach ręcznych warto poświęcić kilka sekund na znalezienie wiersza lub kolumny z największą liczbą zer, zanim zaczniemy. To najprostszy sposób na ograniczenie błędów rachunkowych.

Rozwinięcie według dopełnień i struktura rekursywna

Rozwinięcie według dopełnień ma wbudowaną strukturę rekursywną.

Aby znaleźć wyznacznik macierzy n×n, rozwijamy wzdłuż wiersza lub kolumny i liczymy wyznaczniki macierzy (n-1)×(n-1) . Każda z nich rozwija się do macierzy (n-2)×(n-2). Kontynuujemy redukcję aż do macierzy 2×2, które liczymy bezpośrednio.

Ta własność rekursji definiuje algebraicznie wyznacznik. Określa, czym jest wyznacznik dla każdej wielkości macierzy, a nie tylko jak go obliczać.

Rekursja ma jednak swoją cenę.

Każdy poziom rozwinięcia mnoży liczbę podproblemów i dla dużych macierzy obliczenia rosną bardzo szybko. Dlatego biblioteki numeryczne nie używają rozwinięcia według dopełnień „pod maską”. Redukcja wierszy i metody faktoryzacji skalują się znacznie lepiej.

Dla małych macierzy i w pracy teoretycznej struktura rekursywna jest dokładnie tym, czego potrzebujemy. Dla większych lepiej poszukać innego podejścia.

Związek z macierzą dołączoną

Dopełnienia są elementem budulcowym odwracania macierzy. Nie służą wyłącznie do obliczania wyznaczników.

Jeśli obliczymy dopełnienie C_ij dla każdego elementu macierzy A, otrzymamy macierz dopełnień C. Jej transpozycja — zamiana wierszy z kolumnami — daje macierz dołączoną:

Macierz dołączona

Stąd już bezpośrednio wynika wzór na macierz odwrotną:

Macierz odwrotna

Mówiąc prościej: trzeba policzyć wszystkie dopełnienia, ułożyć je w macierz, przetransponować, a następnie podzielić przez wyznacznik. To daje macierz odwrotną.

Warto zapamiętać dwie rzeczy:

1. To działa tylko wtedy, gdy det(A) ≠ 0 — zerowy wyznacznik oznacza, że macierz nie ma odwrotności
2. Wzór jest dokładny, dzięki czemu przydaje się w pracy teoretycznej i algebrze symbolicznej. Do obliczeń numerycznych na dużych macierzach szybsze są inne metody.

Jeśli zastanawia Pana/Panią związek z rozwinięciem według dopełnień, proszę pamiętać, że każdy element macierzy dołączonej pochodzi z dopełnienia liczonego podczas rozwinięcia. Ten sam proces, który daje wyznacznik, dostarcza też wszystkiego, co potrzebne do odwrócenia macierzy.

Własności rozwinięcia według dopełnień

Rozwinięciu według dopełnień towarzyszy kilka własności wartych poznania. Pozwolą uniknąć wątpliwości i pomogą dostrzec skróty rachunkowe.

Oto cztery własności do zapamiętania:

• Rozwinięcie wzdłuż dowolnego wiersza lub kolumny daje ten sam wynik. Można rozwijać wzdłuż wiersza 2 lub kolumny 3 — wyznacznik się nie zmienia. Wybierzmy ten z największą liczbą zer
• Wyznacznik jest liniowy w każdym wierszu. Jeśli przemnożymy wiersz przez stałą k, wyznacznik także mnoży się przez k. Wynika to bezpośrednio z faktu, że dopełnienia mnożą się przez poszczególne elementy
• Zamiana dwóch wierszy odwraca znak wyznacznika. Jedna zamiana neguje wyznacznik. Dwie — przywracają go. Dlatego należy uważnie śledzić operacje na wierszach
• Jeśli dwa wiersze są liniowo zależne, wyznacznik jest równy zero. Zależność liniowa oznacza, że jeden wiersz jest wielokrotnością drugiego — lub ogólniej, że wiersze nie rozpinają całej przestrzeni. Macierz jest osobliwa i nie ma odwrotności

Te własności pozwalają upraszczać macierze przed rozwinięciem — redukować wiersze, dostrzegać zależności i unikać niepotrzebnych obliczeń.

Częste błędy

Rozwinięcie według dopełnień ma kilka typowych punktów potknięć. Oto na co zwracać uwagę.

• Pomijanie znaku (-1)^(i+j). To najczęstszy błąd. Minor jest policzony poprawnie, element przemnożony, a wynik zły, bo pominięto czynnik znaku. Zawsze proszę sprawdzić wzór szachownicy przed zapisaniem dopełnienia
• Usuwanie niewłaściwego wiersza lub kolumny przy minorze. Przy obliczaniu M_ij usuwa się wiersz i i kolumnę j — czyli wiersz i kolumnę elementu, względem którego rozwijamy. Częstym potknięciem jest usunięcie niewłaściwego, zwłaszcza w 3×3, gdzie powstałe macierze mogą wyglądać podobnie
• Zbyt wczesne przerwanie rekursji. Gdy podmacierz ma wciąż rozmiar 3×3 lub większy, należy rozwijać dalej. Niektórzy traktują minor 3×3 jak 2×2 i bezpośrednio stosują ad - bc.
• Błędy rachunkowe w krokach rekursji. Im głębsza rekursja, tym więcej mnożeń i zmian znaków trzeba śledzić. Jeden błąd rachunkowy we wczesnym podwyznaczniku przenosi się na wszystkie kolejne kroki. Warto dokładnie policzyć każdy wyznacznik 2×2 przed łączeniem wyników

Jeśli końcowy wynik wydaje się niepoprawny, w pierwszej kolejności proszę sprawdzić wzór znaków i to, które wiersze/kolumny usuwano przy minorach.

Kiedy używać rozwinięcia według dopełnień

Rozwinięcie według dopełnień jest właściwym narzędziem w kilku konkretnych sytuacjach.

Dla małych macierzy to najprostsze podejście. 2×2 jest trywialna, a 3×3 da się policzyć ręcznie w parę minut. Od 4×4 w górę liczba kroków rekursji rośnie na tyle szybko, że inne metody są szybsze i mniej podatne na błędy.

To także metoda pierwszego wyboru w pracy teoretycznej i symbolicznej. Jeśli pracujemy nad dowodem, wyprowadzamy wzór lub liczymy wyznacznik z elementami symbolicznymi zamiast liczb, rozwinięcie według dopełnień daje dokładne wyrażenie symboliczne. Redukcja wierszy świetnie sprawdza się przy liczbach, ale z symbolami bywa kłopotliwa.

Krótko, kiedy po nią sięgać:

• Pracuje Pan/Pani z macierzą 2×2 lub 3×3
• Potrzebny jest dokładny wynik symboliczny, a nie przybliżenie numeryczne
• Realizuje Pan/Pani dowód wymagający jawnego rozwinięcia wyznacznika
• Buduje Pan/Pani intuicję, czym właściwie jest wyznacznik

Dla dużych macierzy numerycznych lepiej to pominąć. Redukcja wierszy i rozkład LU radzą sobie z takimi przypadkami znacznie szybciej i z dużo mniejszym ryzykiem kumulowania błędów rachunkowych. Większość bibliotek numerycznych używa tych metod właśnie z tego powodu.

Rozwinięcie według dopełnień najlepiej traktować jako narzędzie do obliczeń ręcznych i pracy teoretycznej, a nie algorytm ogólnego przeznaczenia.

Zakończenie

Rozwinięcie według dopełnień daje systematyczny, rekursywny sposób obliczania wyznacznika dowolnej macierzy kwadratowej.

Dwa elementy składowe — minory i wzór znaków (-1)^(i+j) — napędzają cały proces. Jeśli są poprawne, reszta jest prosta. Proszę wybierać wiersz lub kolumnę z zerami, aby ograniczyć pracę, redukować do wyznaczników 2×2 i sumować wyniki.

Poza wyznacznikami metoda łączy się z macierzą dołączoną i wzorem na macierz odwrotną. Dopełnienia liczone podczas rozwinięcia to te same, które budują adj(A) — dzięki czemu rozwinięcie według dopełnień stanowi podstawę zrozumienia algebraicznego odwracania macierzy.

Dla małych macierzy i pracy teoretycznej to najbardziej przejrzysta metoda. Dla dużych macierzy numerycznych lepiej wybrać redukcję wierszy lub bibliotekę numeryczną.

Jeśli chce Pan/Pani zobaczyć rozwinięcie według dopełnień w praktyce, proszę zapisać się na nasz kurs Algebra liniowa dla Data Science w R.