szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 18 mar 2014, o 02:16 
Użytkownik
Avatar użytkownika

Posty: 1446
Lokalizacja: Trójmiasto
Metoda Chió


1. Chió kontra Laplace
2. Definicja
3. Przykład
4. Podsumowanie

\hline





Najbardziej rozpowszechnioną metodą liczenia wyznacznika macierzy większych niż 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 2 \times 2 gdyż to obliczenie stanowi w niej rolę operacji elementarnej.
Przy rozwinięciu Laplace'a dla macierzy rozmiaru n musimy wyznaczyć n macierzy rozmiaru n-1, następnie z każdej z nich wyznaczyć n-1 macierzy rozmiaru 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 n robimy jedną macierz rozmiaru n-1 i wejściowa macierz nie jest nam już potrzebna, następnie z tak powstałej tworzymy jeszcze mniejszą 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.

\hline





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

\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 a_{1,1} na żadnym etapie nie może być równy 0. Jeśłi tak się stanie należy zamienić miejscami pierwszy wiersz z innym, w którym w pierwszej kolumnie nie występuje 0.

\hline





\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

\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ć.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna
PostNapisane: 19 mar 2014, o 17:42 
Użytkownik

Posty: 939
Lokalizacja: Mazowsze
Zdaje się że to ma nawet złożoność rzędu O(n^{3}), przy czym Laplace ma znacznie gorszą O(n!) liczoną względem potrzebnych obliczeń wyznaczników 2 \times 2
Góra
Mężczyzna
PostNapisane: 20 mar 2014, o 00:26 
Użytkownik
Avatar użytkownika

Posty: 1446
Lokalizacja: Trójmiasto
jarek4700, no mniej więcej, bo samych wyznaczników 2 \times 2 będzie n^2, potem (n-1)^2 itd. a tych kroków nadrzędnych (zmniejszeń macierzy) jest n czyli wychodzi około n^3
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Rozkład LU macierzy  mariuszm  1
 Rząd macierzy z parametrem - zadanie 10  zushichi  1
 Rozwiąż metodą Newtona i metodą cięciw  Stary  0
 całka nieoznaczona - metoda podstawiania  mpk  2
 Układy równań - metodą Kroneckera-Capellego i Gaussa - zadanie 2  edycia17211  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl