Wyznacznik macierzy - metoda Chió

Zbiór wzorów, definicji i najczęściej poruszanych problemów z Algebry.
Awatar użytkownika
Gouranga
Użytkownik
Użytkownik
Posty: 1446
Rejestracja: 16 maja 2013, o 17:56
Płeć: Mężczyzna
Lokalizacja: Trójmiasto
Podziękował: 11 razy
Pomógł: 217 razy

Wyznacznik macierzy - metoda Chió

Post autor: Gouranga » 18 mar 2014, o 01:16

Metoda Chió


1. Chió kontra Laplace
2. Definicja
3. Przykład
4. Podsumowanie
\(\displaystyle{ \hline}\)

Najbardziej rozpowszechnioną metodą liczenia wyznacznika macierzy większych niż \(\displaystyle{ 3 \times 3}\) jest chyba rozwinięcie Laplace'a i to z nim należałoby wstępnie porównać prezentowana tu metodę Chió.
Obie te metody działają rekurencyjnie, co oznacza, że stopniowo będziemy schodzić do coraz mniejszych macierzy. Rozwinięcie Laplace'a może posłużyć do liczenia wyznacznika dowolnie dużej macierzy, metoda Chió posiada jedno zasadnicze ograniczenie - nie można nią liczyć wyznaczników macierzy \(\displaystyle{ 2 \times 2}\) gdyż to obliczenie stanowi w niej rolę operacji elementarnej.
Przy rozwinięciu Laplace'a dla macierzy rozmiaru \(\displaystyle{ n}\) musimy wyznaczyć \(\displaystyle{ n}\) macierzy rozmiaru \(\displaystyle{ n-1}\), następnie z każdej z nich wyznaczyć \(\displaystyle{ n-1}\) macierzy rozmiaru \(\displaystyle{ n-2}\) i tak dalej co wiąże się z koniecznością przechowywania jednocześnie coraz większej ilości liczb co jest kłopotliwe zarówno w komputerze jak i na kartce. W metodzie Chió natomiast najpierw z macierzy rozmiaru \(\displaystyle{ n}\) robimy jedną macierz rozmiaru \(\displaystyle{ n-1}\) i wejściowa macierz nie jest nam już potrzebna, następnie z tak powstałej tworzymy jeszcze mniejszą \(\displaystyle{ n-2 \times n-2}\) i możemy zapomnieć o poprzedniej co jest zdecydowanie wygodniejsze gdy liczymy na papierze i daje większe możliwości na komputerze ponieważ nie wymaga tyle pamięci co rozwinięcie Laplace'a.
\(\displaystyle{ \hline}\)

Macierz \(\displaystyle{ n \times n}\) będziemy redukować do macierzy \(\displaystyle{ n-1 \times n-1}\) a każdy element nowej macierzy będziemy obliczać jako wyznacznik \(\displaystyle{ 2 \times 2}\). Obliczanie takiego wyznacznika stanowi tu rolę operacji elementarnej, można do tego użyć np. metody Sarrusa (liczenia "na krzyż").

\(\displaystyle{ \begin{vmatrix} a_{1,1} & \ldots & a_{1,n}\\ \vdots & \ddots & \vdots \\ a_{n,1} & \ldots & a_{n,n} \end{vmatrix} = \frac{1}{a_{1,1}^{n-2}} \begin{vmatrix} \begin{vmatrix} a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \end{vmatrix} & \ldots & \begin{vmatrix} a_{1,1} & a_{1,n} \\ a_{2,1} & a_{2,n} \end{vmatrix} \\ \vdots & \begin{vmatrix} a_{1,1} & a_{1,j} \\ a_{i,1} & a_{i,j} \end{vmatrix} & \vdots \\ \begin{vmatrix} a_{1,1} & a_{1,2} \\ a_{n,1} & a_{n,2} \end{vmatrix} & \ldots & \begin{vmatrix} a_{1,1} & a_{1,n} \\ a_{n,1} & a_{n,n} \end{vmatrix} \end{vmatrix}}\)

Jak widać element \(\displaystyle{ a_{1,1}}\) na żadnym etapie nie może być równy \(\displaystyle{ 0}\). Jeśłi tak się stanie należy zamienić miejscami pierwszy wiersz z innym, w którym w pierwszej kolumnie nie występuje \(\displaystyle{ 0}\).
\(\displaystyle{ \hline}\)

\(\displaystyle{ \begin{vmatrix} 5 & 1 & 1 & 2 & 3\\ 4 & 2 & 1 & 7 & 3\\ 2 & 1 & 2 & 4 & 7\\ 9 & 1 & 0 & 7 & 0\\ 1 & 4 & 7 & 2 & 2 \end{vmatrix} = \frac{1}{5^{5-2}} \begin{vmatrix} \begin{vmatrix} 5 & 1\\ 4 & 2 \end{vmatrix} & \begin{vmatrix} 5 & 1\\ 4 & 1 \end{vmatrix} & \begin{vmatrix} 5 & 2\\ 4 & 7 \end{vmatrix} & \begin{vmatrix} 5 & 3\\ 4 & 3 \end{vmatrix} \\ \\ \begin{vmatrix} 5 & 1\\ 2 & 1 \end{vmatrix} & \begin{vmatrix} 5 & 1\\ 2 & 2 \end{vmatrix} & \begin{vmatrix} 5 & 2\\ 2 & 4 \end{vmatrix} & \begin{vmatrix} 5 & 3\\ 2 & 7 \end{vmatrix} \\ \\ \begin{vmatrix} 5 & 1\\ 9 & 1 \end{vmatrix} & \begin{vmatrix} 5 & 1\\ 9 & 0 \end{vmatrix} & \begin{vmatrix} 5 & 2\\ 9 & 7 \end{vmatrix} & \begin{vmatrix} 5 & 3\\ 9 & 0 \end{vmatrix} \\ \\ \begin{vmatrix} 5 & 1\\ 1 & 4 \end{vmatrix} & \begin{vmatrix} 5 & 1\\ 1 & 7 \end{vmatrix} & \begin{vmatrix} 5 & 2\\ 1 & 2 \end{vmatrix} & \begin{vmatrix} 5 & 3\\ 1 & 2 \end{vmatrix} \end{vmatrix} = \frac{1}{5^3} \begin{vmatrix} 6 & 1 & 27 & 3 \\ 3 & 8 & 16 & 29 \\ -4 & -9 & 17 & -27 \\ 19 & 34 & 8 &7 \end{vmatrix} = \frac{1}{5^3} \cdot \frac{1}{6^{4-2}} \begin{vmatrix} \begin{vmatrix} 6 & 1\\ 3 & 8 \end{vmatrix} & \begin{vmatrix} 6 & 27\\ 3 & 16 \end{vmatrix} & \begin{vmatrix} 6 & 3\\ 3 & 29 \end{vmatrix} \\ \\ \begin{vmatrix} 6 & 1\\ -4 & -9 \end{vmatrix} & \begin{vmatrix} 6 & 27\\ -4 & 17 \end{vmatrix} & \begin{vmatrix} 6 & 3\\ -4 & -27 \end{vmatrix} \\ \\ \begin{vmatrix} 6 & 1\\ 19 & 34 \end{vmatrix} & \begin{vmatrix} 6 & 27\\ 19 & 8 \end{vmatrix} & \begin{vmatrix} 6 & 3\\ 19 & 7 \end{vmatrix} \end{vmatrix} = \frac{1}{5^3 \cdot 6^2} \begin{vmatrix} 45 & 15 & 165\\ -50 & 210 & -150\\ 185 & -465 & -15 \end{vmatrix} = \frac{1}{5^3 \cdot 6^2 \cdot 45} \begin{vmatrix} \begin{vmatrix} 45 & 15\\ -50 & 210 \end{vmatrix} & \begin{vmatrix} 45 & 165\\ -50 & -150 \end{vmatrix} \\ \\ \begin{vmatrix} 45 & 15\\ 185 & -465 \end{vmatrix} & \begin{vmatrix} 45 & 165\\ 185 & -15 \end{vmatrix} \end{vmatrix} = \frac{1}{125 \cdot 36 \cdot 45} \begin{vmatrix} 10200 & 1500 \\ -23700 & -31200 \end{vmatrix} = \frac{10200 \cdot (-31200) - 1500 \cdot (-23700)}{125 \cdot 36 \cdot 45} = \frac{-318240000 + 35550000}{202500} = \frac{-282690000}{202500} = -1396}\)
\(\displaystyle{ \hline}\)

Jak widać na przykładzie, na końcu dochodzimy do działań na dużych liczbach jednak ręczne liczenie wyznacznika tą metodą to kwestia wprawy. Przykład jest sprawdzony na każdym etapie z programem liczącym wyznaczniki i nie ma w nim błędów. Jeśli kogoś urządza ograniczenie ilości rzeczy, jakie trzeba na raz zapisywać kosztem działań na dużych liczbach to myślę, że ta metoda powinna mu się spodobać.
Ostatnio zmieniony 19 mar 2014, o 23:15 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.

jarek4700
Użytkownik
Użytkownik
Posty: 939
Rejestracja: 26 gru 2009, o 17:38
Płeć: Mężczyzna
Lokalizacja: Mazowsze
Podziękował: 5 razy
Pomógł: 228 razy

Wyznacznik macierzy - metoda Chió

Post autor: jarek4700 » 19 mar 2014, o 16:42

Zdaje się że to ma nawet złożoność rzędu \(\displaystyle{ O(n^{3})}\), przy czym Laplace ma znacznie gorszą \(\displaystyle{ O(n!)}\) liczoną względem potrzebnych obliczeń wyznaczników \(\displaystyle{ 2 \times 2}\)

Awatar użytkownika
Gouranga
Użytkownik
Użytkownik
Posty: 1446
Rejestracja: 16 maja 2013, o 17:56
Płeć: Mężczyzna
Lokalizacja: Trójmiasto
Podziękował: 11 razy
Pomógł: 217 razy

Wyznacznik macierzy - metoda Chió

Post autor: Gouranga » 19 mar 2014, o 23:26

jarek4700, no mniej więcej, bo samych wyznaczników \(\displaystyle{ 2 \times 2}\) będzie \(\displaystyle{ n^2}\), potem \(\displaystyle{ (n-1)^2}\) itd. a tych kroków nadrzędnych (zmniejszeń macierzy) jest \(\displaystyle{ n}\) czyli wychodzi około \(\displaystyle{ n^3}\)

ODPOWIEDZ