🚀 go-pugleaf

On Fri, 02 Jan 1998 15:41:11 +0100, Paweł Borowiec
<borowiec@ci-1.ci.pwr.wroc.pl> wrote:

>Poszukuje algorytmu (programu) obliczajacego wyznacznik macierzy
>kwadratowej o wymiarze n.
>(niby latwe, ale nie za bardzo wiem jak sie do tego zabrac...)
>
>Najlepszy bylby kod (C, C++, inne...), ale moze byc rowniez opis.
>
Podsyłam dwa programiki liczące wyznaczniki dowolnie wielkiej macierzy
(zależy od ilości wolnej pamięci). Jeden oblicz wyznacznik metodą
Laplace'a drugi Gaussa. Są trochę pamięciożerne (chodziło mi o
zaimplementowanie samego algorytmu) i chyba niezbyt optymalne, ale
myślę, że sobie z tym poradzisz.

Metoda Laplece'a poleg na tym, że z wyjściowej macierzy wybieramy
sobie dowolną kolumnę. Wyznacznik macierzy jest rowny sumie elementu z
danej kolumny pomnożonego przez (-1)^(numer_kolumny+numer_wiersza) i
to jeszcze razy wysznacznik macierzy powstałej poprzez wykreślenie
danej kolumny i wiersza. Do wyznacznika mniejszej macierzy stosujemy
ponownie tą regułę aż otrzymamy macierz np. 2x2 lub 1x1. Metoda ta
daje bardzo dobre rezultaty jeśli w macierzy jest dużo zer.

Metoda Gaussa jest o ile mnie dobrze poinformowano najszybszą znaną
metodą obliczania wyznacznika. Najpierw należy wprowadzić pojęcie
operacji elementarnych Gaussa:
1. pomnożenie dowolnego wiersza macierzy przez dowloną stałą
niezerową,
2. zamiana dwóch wierszy miejscami,
3. dodanie do danego wiersza innego pomnożonego przez stałą.

Przy pomocy tych trzech przekształceń należy doprowadzić macierz do
postaci:
1...
0...
0...
.
.
0...
Natępnie wykreślamy pierwszą kolumnę oraz wiersz i bawimy się od nowa.
Na końcu otrzymamy coś takiego:
1....
01...
001..
0001.
00001

Aby obliczyć wycznacznik przyjmujemy, że przed rozpoczęciem
przekształceń jest on równy 1 (D=1). Każda zamiana dwóch wierszy
miejscami zmienia znak liczby D. Pomnożenie wiersza przez stałą
powoduje pomnożenie D przez odwrotność tej stałej. Dodanie wiersza
pomnożonego przez stałą nie zmienia D. Jeśli w którymkolwiek momencie
pojawi się wiersz lub koluma zerowa, to wyznacznik jest równy 0.
Wydaje się to skomplikowane, ale jest bardzo proste.

Uff. Dawno się tyle nie napisałem. Mam nadzieję, że uda Ci się coś z
tego zrozumieć. Naprawdę się starałem.

Acha dane do programu: pierwsza liczba do rozmiar boku macierzy, a
dalej kolejne elementy (wszystkie liczby oddzielone spacjami lub nowym
wierszem).

-- 
_/_/_/_/_/ _/ _/_/_/_/_/   _/_/_/
   _/     _/     _/     _/      _/
  _/     _/     _/     _/      _/                     Sebastian Graca
 _/     _/     _/     _/      _/        Silesian Technical Univeristy
_/     _/     _/       _/_/_/     mailto:titmus@zeus.polsl.gliwice.pl

One man's fun is another's hell

begin 644 Laplace.cpp
M+R\@;V)L:6-Z86YI92!W>7IN86-Z;FEK82!M86-I97)Z>2!M971O9*4@3&%P
M;&%C92=A#0H-"B\O('=E:IAC:64Z#0HO+R!N("T@<F]Z;6EA<B!M86-I97)Z
M>2`H;&EC>F)A(&-AB&MO=VET82D-"B\O(&X@=VEE<G-Z>2!P;R!N(&QI8WIB
M#0H-"B\O('=Y:IAC:64@+2!W>7IN86-Z;FEK(&UA8VEE<GIY#0H-"B-I;F-L
M=61E(#QI;W-T<F5A;2YH/@T*(VEN8VQU9&4@/'-T9&QI8BYH/@T*#0IE;G5M
M(%IN86L@>R!M:6YU<RP@<&QU<R!].PT*#0IT>7!E9&5F(&1O=6)L92`J5VEE
M<G-Z36%C:65R>GD[#0IT>7!E9&5F(%=I97)S>DUA8VEE<GIY("I-86-I97)Z
M.PT*#0H-"G9O:60@='=O<GI?;6%C:65R>BA-86-I97)Z('=E:G-C:6]W82P@
M36%C:65R>B`F=WEJ<V-I;W=A+`T*("`@("`@("`@("`@("`@("`@(&EN="!R
M;WIM:6%R+"!I;G0@=VEE<G-Z*0T*+RH@='=O<GIY('H@;6%C:65R>GD@=V5J
M<V-I;W=A(&\@<F]Z;6EA<GIE(')O>FUI87(@;6%C:65R>B!W>6IS8VEO=V$-
M"B`@(&\@<F]Z;6EA<GIE(')O>FUI87(M,2!P;W!R>F5Z('5S;FFI8VEE('=I
M97)S>F$@;R!N=6UE<GIE('=I97)S>B`J+PT*>PT*("!F;W(H:6YT(&D@/2`P
M+"!J(#T@,#L@:2`\(')O>FUI87([(&DK*RP@:BLK*0T*("`@(&EF*"!I("$]
M('=I97)S>B`I#0H@("`@("!W>6IS8VEO=V%;:ET@/2!W96IS8VEO=V%;:5T[
M#0H@("`@96QS90T*("`@("`@:BTM.PT*?2`O+R!T=V]R>E]M86-I97)Z#0H-
M"@T*9&]U8FQE('=Y>FYA8WIN:6LH36%C:65R>B!M86-I97)Z+"!I;G0@<F]Z
M;6EA<BD-"GL-"B`@36%C:65R>B!N;W=A7VUA8VEE<GH[("\J(&UA8VEE<GHL
M(&MTHG)A('!O=W-T88AA('!R>F5Z('=Y:W)EF&QE;FEE#0H@("`@("`@("`@
M("`@("`@("`@("`@("`@("!O9'!O=VEE9&YI96=O('=I97)S>F$@:2!K;VQU
M;6YY("HO#0H@(%IN86L@>FYA:SL@("`@("`@("`@("`O+R!Z;F%K('H@:F%K
M:6T@>F]S=&%N:64@=WIIJ71Y(&MO;&5J;GD@96QE;65N=`T*#0H@(&1O=6)L
M92!?=WEZ;F%C>FYI:R`](#`[#0H-"B`@:68H(')O>FUI87(M+2`]/2`Q("D-
M"B`@("!R971U<FX@;6%C:65R>ELP75LP73L-"@T*("!I9B@@*&YO=V%?;6%C
M:65R>B`](&YE=R!7:65R<WI-86-I97)Z>5MR;WIM:6%R72D@/3T@,"`I('L-
M"B`@("!C97)R(#P\("):82!M88AO('!A;6FI8VDB(#P\(&5N9&P[#0H@("`@
M97AI="@Q*3L-"B`@?0T*#0H@("\O(&QI8WH@=WEZ;F%C>FYI:PT*("!F;W(H
M:6YT('=I97)S>B`](#`[('=I97)S>B`\/2!R;WIM:6%R.R!W:65R<WHK*RD@
M>PT*("`@('IN86L@/2`H=VEE<G-Z("4@,BD@/R!M:6YU<R`Z('!L=7,[#0H@
M("`@='=O<GI?;6%C:65R>BAM86-I97)Z+"!N;W=A7VUA8VEE<GHL(')O>FUI
M87(K,2P@=VEE<G-Z*3L-"B`@("!I9B`H('IN86L@/3T@<&QU<R`I#0H@("`@
M("!?=WEZ;F%C>FYI:R`K/2!M86-I97)Z6W=I97)S>EU;<F]Z;6EA<ETJ=WEZ
M;F%C>FYI:RAN;W=A7VUA8VEE<GHL(')O>FUI87(I.PT*("`@(&5L<V4-"B`@
M("`@(%]W>7IN86-Z;FEK("T](&UA8VEE<GI;=VEE<G-Z75MR;WIM:6%R72IW
M>7IN86-Z;FEK*&YO=V%?;6%C:65R>BP@<F]Z;6EA<BD[#0H@('T-"B`@9&5L
M971E6UT@;F]W85]M86-I97)Z.PT*("!R971U<FX@7W=Y>FYA8WIN:6L[#0I]
M("\O('=Y>FYA8WIN:6L-"@T*#0H-"FEN="!M86EN*'9O:60I#0I[#0H@(&EN
M="!R;WIM:6%R.R`@("`@("\O(')O>FUI87(@;6%C:65R>GD-"B`@36%C:65R
M>B!M86-I97)Z.R`@+R\@;F%S>F$@;6%C:65R>@T*#0H@("\O('=C>GET86YI
M92!D86YY8V@-"B`@8VEN(#X^(')O>FUI87([#0H@(&EF("AR;WIM:6%R(#P@
M,2D@>PT*("`@(&-E<G(@/#P@(DYI97!O<')A=VYY(')O>FUI87(@;6%C:65R
M>GDB(#P\(&5N9&P[#0H@("`@<F5T=7)N(#$[#0H@('T-"@T*("!I9B@@*&UA
M8VEE<GH@/2!N97<@5VEE<G-Z36%C:65R>GE;<F]Z;6EA<ETI(#T](#`@*2![
M#0H@("`@8V5R<B`\/"`B6F$@;6&(;R!P86UIJ6-I(B`\/"!E;F1L.PT*("`@
M(')E='5R;B`Q.PT*("!]#0H@(&9O<BAI;G0@=VEE<G-Z(#T@,#L@=VEE<G-Z
M(#P@<F]Z;6EA<CL@=VEE<G-Z*RLI#0H@("`@:68H("AM86-I97)Z6W=I97)S
M>ET@/2!N97<@9&]U8FQE6W)O>FUI87)=*2`]/2`P("D@>PT*("`@("`@8V5R
M<B`\/"`B6F$@;6&(;R!P86UIJ6-I(B`\/"!E;F1L.PT*("`@("`@<F5T=7)N
M(#$[#0H@("`@?0T*#0H@(&9O<BAW:65R<WH@/2`P.R!W:65R<WH@/"!R;WIM
M:6%R.R!W:65R<WHK*RD-"B`@("!F;W(H:6YT(&MO;'5M;F$@/2!R;WIM:6%R
M+3$[(&MO;'5M;F$@/CT@,#L@:V]L=6UN82TM*0T*("`@("`@8VEN(#X^(&UA
M8VEE<GI;=VEE<G-Z75MK;VQU;6YA73L@+R\@=R!W:65R<WIU(&5L96UE;G1Y
M('IA<&ES>7=A;F4@;V0@:V_D8V$-"@T*("!C;W5T(#P\(&5N9&P@/#P@=WEZ
M;F%C>FYI:RAM86-I97)Z+"!R;WIM:6%R*2`\/"!E;F1L.PT*#0H@(&9O<BAW
M:65R<WH@/2`P.R!W:65R<WH@/"!R;WIM:6%R.R!W:65R<WHK*RD-"B`@("!D
M96QE=&5;72!M86-I97)Z6W=I97)S>ET[#0H@(&1E;&5T95M=(&UA8VEE<GH[
0#0H@(')E='5R;B`P.PT*?7=I
`
end

begin 644 Gauss.cpp
M+R\@;V)L:6-Z86YI92!W>7IN86-Z;FEK82!M86-I97)Z>2!M971O9*4@1V%U
M<W,G80T*#0HO+R!W96J88VEE.@T*+R\@;B`M(')O>FUI87(@;6%C:65R>GD@
M*&QI8WIB82!C88AK;W=I=&$I#0HO+R!N('=I97)S>GD@<&\@;B!L:6-Z8@T*
M#0HO+R!W>6J88VEE("T@=WEZ;F%C>FYI:R!M86-I97)Z>0T*#0HC:6YC;'5D
M92`\:6]S=')E86TN:#X-"B-I;F-L=61E(#QS=&1L:6(N:#X-"@T*='EP961E
M9B!D;W5B;&4@*E=I97)S>DUA8VEE<GIY.PT*='EP961E9B!7:65R<WI-86-I
M97)Z>2`J36%C:65R>CL-"@T*#0II;FQI;F4@=F]I9"!Z86UI96Y?=VEE<G-Z
M92A7:65R<WI-86-I97)Z>2`F=VEE<G-Z,2P@5VEE<G-Z36%C:65R>GD@)G=I
M97)S>C(I#0I[#0H@(%=I97)S>DUA8VEE<GIY('1E;7`@/2!W:65R<WHQ.PT*
M("!W:65R<WHQ(#T@=VEE<G-Z,CL-"B`@=VEE<G-Z,2`]('1E;7`[#0I]("\O
M('IA;6EE;E]W:65R<WIE#0H-"@T*9&]U8FQE('=Y>FYA8WIN:6LH36%C:65R
M>B!M86-I97)Z+"!I;G0@<F]Z;6EA<BD-"GL-"B`@:68H(')O>FUI87(M+2`]
M/2`Q("D-"B`@("!R971U<FX@;6%C:65R>ELP75LP73L-"@T*("!I;G0@=VEE
M<G-Z.PT*("!D;W5B;&4@7W=Y>FYA8WIN:6L@/2`Q.PT*("!D;W5B;&4@)G!I
M97)W<WIY(#T@;6%C:65R>ELP75MR;WIM:6%R73L-"@T*("`O+R!S>G5K86YI
M92!N:65Z97)O=V5G;R!E;&5M96YT=0T*("!I9B@@(7!I97)W<WIY("D-"B`@
M("!F;W(@*'=I97)S>B`](#$[('=I97)S>B`\/2!R;WIM:6%R.R!W:65R<WHK
M*RD-"B`@("`@(&EF*"!M86-I97)Z6W=I97)S>EU;<F]Z;6EA<ET@*2![#0H@
M("`@("`@('IA;6EE;E]W:65R<WIE*&UA8VEE<GI;,%TL(&UA8VEE<GI;=VEE
M<G-Z72D[#0H@("`@("`@(%]W>7IN86-Z;FEK("H]("TQ.PT*("`@("`@("!B
M<F5A:SL-"B`@("`@('T-"@T*("!I9B@@(7!I97)W<WIY("D@+R\@:V]L=6UN
M82!Z97)O=V$-"B`@("!R971U<FX@,#L-"@T*("`O+R!P:65R=W-Z>6T@96QE
M;65N=&5M(&UA(&)YAB`Q#0H@(%]W>7IN86-Z;FEK("H]('!I97)W<WIY.PT*
M("!F;W(H:6YT(&MO;'5M;F$@/2`P.R!K;VQU;6YA(#P@<F]Z;6EA<CL@:V]L
M=6UN82LK*0T*("`@(&UA8VEE<GI;,%U;:V]L=6UN85T@+ST@<&EE<G=S>GD[
M#0H@('!I97)W<WIY(#T@,3L-"@T*("`O+R!Z97)U:B!P;WIO<W1AB&4@96QE
M;65N='D@=R!K;VQU;6YI90T*("!F;W(H=VEE<G-Z(#T@,3L@=VEE<G-Z(#P]
M(')O>FUI87([('=I97)S>BLK*2![#0H@("`@9&]U8FQE(&EL;W)A>B`](&UA
M8VEE<GI;=VEE<G-Z75MR;WIM:6%R73L-"B`@("!F;W(H:V]L=6UN82`](#`[
M(&MO;'5M;F$@/"!R;WIM:6%R.R!K;VQU;6YA*RLI#0H@("`@("!M86-I97)Z
M6W=I97)S>EU;:V]L=6UN85T@+3T@;6%C:65R>ELP75MK;VQU;6YA72II;&]R
M87H[#0H@("`@;6%C:65R>EMW:65R<WI=6W)O>FUI87)=(#T@,#L-"B`@?0T*
M#0H@(')E='5R;B!?=WEZ;F%C>FYI:RIW>7IN86-Z;FEK*"9M86-I97)Z6S%=
M+"!R;WIM:6%R*3L-"GT@+R\@=WEZ;F%C>FYI:PT*#0H-"FEN="!M86EN*'9O
M:60I#0I[#0H@(&EN="!R;WIM:6%R.R`@("`@("\O(')O>FUI87(@;6%C:65R
M>GD-"B`@36%C:65R>B!M86-I97)Z.R`@+R\@;F%S>F$@;6%C:65R>@T*#0H@
M("\O('=C>GET86YI92!D86YY8V@-"B`@8VEN(#X^(')O>FUI87([#0H@(&EF
M("AR;WIM:6%R(#P@,2D@>PT*("`@(&-E<G(@/#P@(DYI97!O<')A=VYY(')O
M>FUI87(@;6%C:65R>GDB(#P\(&5N9&P[#0H@("`@<F5T=7)N(#$[#0H@('T-
M"@T*("!I9B@@*&UA8VEE<GH@/2!N97<@5VEE<G-Z36%C:65R>GE;<F]Z;6EA
M<ETI(#T](#`@*2![#0H@("`@8V5R<B`\/"`B6F$@;6&(;R!P86UIJ6-I(B`\
M/"!E;F1L.PT*("`@(')E='5R;B`Q.PT*("!]#0H@(&9O<BAI;G0@=VEE<G-Z
M(#T@,#L@=VEE<G-Z(#P@<F]Z;6EA<CL@=VEE<G-Z*RLI#0H@("`@:68H("AM
M86-I97)Z6W=I97)S>ET@/2!N97<@9&]U8FQE6W)O>FUI87)=*2`]/2`P("D@
M>PT*("`@("`@8V5R<B`\/"`B6F$@;6&(;R!P86UIJ6-I(B`\/"!E;F1L.PT*
M("`@("`@<F5T=7)N(#$[#0H@("`@?0T*#0H@(&9O<BAW:65R<WH@/2`P.R!W
M:65R<WH@/"!R;WIM:6%R.R!W:65R<WHK*RD-"B`@("!F;W(H:6YT(&MO;'5M
M;F$@/2!R;WIM:6%R+3$[(&MO;'5M;F$@/CT@,#L@:V]L=6UN82TM*0T*("`@
M("`@8VEN(#X^(&UA8VEE<GI;=VEE<G-Z75MK;VQU;6YA73L@+R\@=R!W:65R
M<WIU(&5L96UE;G1Y('IA<&ES>7=A;F4@;V0@:V_D8V$-"@T*("!C;W5T(#P\
M(&5N9&P@/#P@=WEZ;F%C>FYI:RAM86-I97)Z+"!R;WIM:6%R*2`\/"!E;F1L
M.PT*#0H@(&9O<BAW:65R<WH@/2`P.R!W:65R<WH@/"!R;WIM:6%R.R!W:65R
M<WHK*RD-"B`@("!D96QE=&5;72!M86-I97)Z6W=I97)S>ET[#0H@(&1E;&5T
<95M=(&UA8VEE<GH[#0H@(')E='5R;B`P.PT*?7=I
`
end