Gaussova eliminační metoda – Pascal – Fórum – Programujte.com

Zdravím, potřeboval bych porozumět gaussově eliminační metodě - zejména pak jejím zápisu v pascalu. Přídávám zápis, který jsem našel. Mohl by mi prosím na něm někdo vysvětlit jednotlivé kroky, které zde jsou ? Nejsem v programování příliš zběhlý, tak pokud možno tak prosím o "zjednodušený" návod.

program Gauss;

uses crt;

var a:array[1..6,1..6] of real;
    b:array[1..6] of real;
    k,d,i,j,n:integer;
    po,mul,pom:real;
   
begin clrscr;
write('n=');read(n);
for i:=1 to n do begin
for j:= 1 to n do begin
write('a[',i,j,']=');read(a[i,j]);
                 end;
write('b[',i,']=');read(b[i]);
                  end;
                     
for k:=1to n-1 do begin
begin
d:=1;
while ((a[k,k]=0)and((k+d)<=n)) do begin for j:=1 to n do begin pom:=a[k,j];
                                                                a[k,j]:=a[k+d,j];
                                                                a[k+d,j]:=pom;
                                                          end;
po:=b[k];        
b[k]:=b[k+d];
b[k+d]:=po;
d:=d+1;
end;
                  end;
if(a[k,k]<>0) then begin for i:=k+1 to n do begin mul:=a[i,k]/a[k,k];
                                                  for j:=1 to n do
                                                  a[i,j]:=a[i,j]-(a[k,j]*mul);
                                                  b[i]:= b[i]-(b[k]*mul);
                                            end;
                   end;

end;

for i:=1 to n do begin
for j:=1 to n do begin
write (a[i,j]:6:2); end;    
write(':');
writeln (b[i]:6:2);end;

repeat until keypressed;
end.

Ten program nemůže fungovat, protože na začátku do matic nenačte žádné hodnoty a rovnou je začne vypisovat a přepočítávat. Zbytku na první pohled nerozumím a nemám zrovna náladu na luštění a zkoušení, takže radši přejdu rovnou k té eliminační metodě.

Začátek: máš soustavu lineárních rovnic, třeba:

2x+3y+5z=10
4x-1y+z=-3
10x+16y+0z=1

Neboli v maticovém tvaru:

 (2, 3,5    (x    (10
  4,-1,1  *  y  =  -3
 10,16,0)    z)     1)

Neboli A*X=B.

Předpokládám, že víš, jak se násobí a sčítají vektory a matice. Jestli ne, doporučuji prostudovat základy lineární algebry, protože bez toho se neobejdeme.

První krok: vezmeme matici na levé straně a zprava k ní připojíme matici pravé strany (A|B):

 (2, 3,5,10
  4,-1,1,-3
 10,16,0, 1)

Druhý krok: pomocí řádkových ekvivalentních úprav tuhle rozšířenou matici převedeme na trojúhelníkovou s jednotkovou diagonálou, tj. aby na hlavní diagonále byly samé jedničky a pod ní samé nuly. Dostaneme něco jako tohle:

(1,-4,23,10     (čísla jsou vycucaná z prstu, 0, 1,-6,-3      nechtělo se mi to počítat,
 0, 0, 1, 7)     takže to neber jako směrodatný výsledek!)

Kdyby při úpravách některý řádek nebo sloupec matice A (to je ten čtverec 3x3 nalevo) vyšel úplně nulový, znamená to, že tato matice byla singulární a soustava rovnic tedy nemá jednoznačné řešení.

Ekvivalentními úpravami myslím vynásobení všech prvků řádku konstantou, prohození řádků a přičtení lineární kombinace některých řádků k jinému. Předpokládám, že to znáš.

Poslední krok: zase to rozpojíme na matice A' a B' a představíme si to v původním rovnicovém tvaru:

x -4y +23z = 10
    y  -6z = -3
         z = 7

A dál už je to triviální: hodnotu z vidíme rovnou, po dosazení do druhého řádku dostaneme y, po dosazení do prvního x a jsme hotovi.

Jestli chceš hotový, plně funkční zdroják, koukni sem: http://mircosoft.mzf.cz/…d/MATYKA.PAS a najdi si v tom proceduru TrojuhM. Je sice trochu složitější, protože zároveň počítá determinant a navíc používá matice obecných rozměrů, které se musí indexovat jako jednorozměrná pole (i*šířka+j), ale postup Gaussovy eliminace by z ní měl být vidět. Kdyby ne, ptej se.

princip je v tom, vypocitat v diagonale jednotky a v poslednim sloupci pak jsou presne vysledky x, y, z ....  (vesmes je to neco na bazi dosazovani)  Tj. neskonci se nulama pod diagonalou, ale pokracuje se aby byly nuly i nad, a pak uz jen vydelit tak, aby vznikly jednotky.

tj neco jako:

[ 1  0  0  4 ]  =>  x= 4
[ 0  1  0 -2 ]  =>  y= -2
[ 0  0  1  3 ]  =>  z= 3

ok díky, tu metodu už zhruba chápu, neměl by někdo co nejjednodušší zdroják (třeba i popsat nějaké kroky), s těma determinantama bych tomu moc nerozuměl ...

Našel jsem něco zde - http://www.trsek.com/…r/ales/gauss, ale pro mně je to celkem komplikované.. nevěděl by někdo, jak to trochu zjednodušit 

Celý zdroják nedostaneš, to bys to měl moc jednoduché :-). Škola je od toho, aby ses to naučil napsat sám.

Zkusím to vysvětlit víc algoritmicky (Kiive, díky za opravu).

1) Máš matici levé strany A a matici pravé strany B, spojené do jedné velké matice soustavy, označíme si ji AB. První index bude představovat číslo řádku a druhý číslo sloupce.

2) Vezmeme to postupně zleva. Cyklus pro každý sloupec matice A, číslo sloupce budeme mít v proměnné j:

2a) Prvky hlavní diagonály se poznají tak, že mají stejné číslo řádku a sloupce. V našem značení to budou prvky AB[ j , j]. Chceme, aby prvky AB[j,j] měly hodnotu 1:

2a1) Jestli už ji mají, není co řešit, pokračujeme bodem 2b.

2a2) Jestli mají nějakou jinou nenulovou hodnotu, vydělíme všechny prvky j-tého řádku matice AB hodnotou prvku AB[j,j]. Jakékoli nenulové číslo dělené samo sebou se změní na jedničku, nuly nalevo vzniklé při předchozích iteracích cyklu zůstanou pořád nulami, což je přesně to, co chceme.

2a3) Jestli mají nulovou hodnotu, musíme projít zbylé prvky v j-tém sloupci pod hlavní diagonálou a najít mezi nimi nenulový prvek (dejme tomu, že na hledání použijeme pomocný index i od j+1 do n, kde n je počet řádků, a na nalezeném prvku se zastavíme). Pokud ho najdeme, prohodíme celý i-tý řádek matice AB s j-tým a dál pokračujeme podle bodu 2a2 (hotové sloupce nalevo nám výměna neovlivní, tam už jsou jenom samé nuly a ty můžeme navzájem přehazovat jak chceme). Pokud už žádný nenulový prvek nenajdeme, znamená to, že matice A je singulární a soustava nemá jednoznačné řešení - není co řešit, končíme. Nad diagonálou nemá cenu hledat - i kdyby tam něco nenulového bylo, na singularitě matice to nic nemění.

2b) Hlavní diagonálu máme jednotkovou, ještě musíme vynulovat všechny ostatní prvky tohoto sloupce. To znamená, že od všech řádků kromě j-tého (toho jednotkového) odečteme x-násobek j-tého řádku, kde x je hodnota prvku, který chceme vynulovat (protože x-1*x=0). Hotové sloupce vlevo od j-tého už si tím neovlivníme, protože v j-tém řádku tam jsou jenom nuly a x-0*cokoli=x.

2c) Zpátky na začátek cyklu, dokud není celá matice A jednotková.

A to je celé. Praktické provedení bude o vhodném použití cyklů typu for a while, řídicí proměnné ti budou stačit dvě (i a j), dále budeš potřebovat proměnnou n na uložení počtu proměnných (A má rozměry n×n, B n×1, AB pak n×n+1). V případě dalších dotazů nezapomeň přiložit svůj zdroják ;-).

Díky moc... zkusim se tim nějak prokousat    Mám to právě k maturitě