Umíte pascalsky - 29.lekce ...

Umíte pascalsky?
29.lekce
 Vytisknout  
Řešení soustavy lineárních rovnice - Jordanova metoda

Soustavu lineárních rovnic zkráceně zapisujeme pomocí matice soustavy, která obsahuje pouze koeficienty levých a pravých stran rovnic.

Například soustavu rovnic
        2y + z = 1   
2x +   y  - z = 0
3x + 5y + z = 4
zapíšeme pomocí matice soustavy takto  
Pro řešení soustavy lineárních rovnic budeme používat Jordanovu metodu. Její základní myšlenkou je upravit matici levých stran soustavy na matici jednotkovou (na hlavní diagonále pouze jedničky). Pokud se to podaří, pak je řešením soustavy vektor pravých stran. Takováto matice soustavy se nazývá regulární a soustava má jediné řešení.

V našem příkladě si za chvíli ukážeme, že lze původní matici soustavy upravit na tuto matici:
Ta by odpovídala soustavě:

(hlavní diagonála zeleně)		   x                =  2   
        y          =  -1
                 z  =  3
Tedy pravé strany udávají kořeny soustavy: x =2 , y = -1 , z = 3

Pokud se nepodaří získat jednotkovou matici z levých stran soustavy, nazýváme takovouto matici soustavy singulární, a soustava v tomto případě buď nemá řešení nebo má nekonečně mnoho řešení.

Převod původní matice na matici jednotkovou provádíme pomocí tzv. ekvivalentních úprav (nemění se při nich množina kořenů):

- výměna dvou libovolných řádků
- násobení řádku nenulovou konstantou
- přičtení násobku některého řádku k jinému řádku
 (1)
(2)
(3)



A) Řešení regulární soustavy lineárních rovnic

Nyní si na našem příkladě ukážeme postup při převodu matice soustavy na matici jednotkovou:

V matici soustavy potřebujeme na hlavní diagonále v prvním řádku dostat místo čísla 0 číslo 1 pomocí ekvivalentních úprav (1-3).

Vyměníme nejprve druhý a první řádek - úprava (1) - abychom na diagonálu získali nenulový prvek (příprava řádku).

Teď jedničku získáme vynásobením prvního řádku jednou polovinou, tedy vydělíme dvěma - úprava (2) - (získej jedničku)

Pod jedničkou v prvním sloupci musíme získat samé nuly (nulování sloupce). Je třeba se tedy zbavit čísla 3 v třetím řádku. Toho dosáhneme tím, že první řádek vynásobíme mínus třemi a přičteme k třetímu řádku - úprava (3)

A stejně pokračujeme druhým řákem, kde na hlavní diagonále chceme získat jedničku.Je zde nenulový prvek, nemusíme tedy přehazovat řádky (příprava řádku). Stačí řádek vydělit dvěma (získej jedničku).

Nad a pod jedničkou v druhém sloupci musíme získat samé nuly. Jedné poloviny v prvním řádku se zbavíme tak, že druhý řádek vynásobíme minus jednou polovinou a přičteme k prvnímu řádku - úprava (3) - (nulování sloupce).

Sedm polovin pod jedničkou vynulujeme vynásobením druhého řádku mínus sedmi polovinami a přičtením k třetímu řádku - úprava (3)

Třetí řádek nejprve násobíme čtyřmi třetinami, abychom získali jedničku.

Potom nulujeme třetí sloupec. Třetí řádek násobíme třemi čtvrtinami a přičteme k prvnímu - tím vznikne nula v prvním řádku.

Nakonec třetí řádek vynásobíme mínus jednou polovinou a přičteme k druhému řádku - tím vznikne nula v druhém řádku.

Tím jsme získali z matice levých stran jednotkovou matici, soustava je regulární a má jediné řešení:
x = 2
y = -1
z = 3


Z příkladu je zřejmé, že se při řešení soustavy Jordanovou metodou opakují dílčí kroky, které jsme nazvali:

- příprava řádku
- získej jedničku
- nuluj sloupec

V případě, kdy je matice regulární, se tyto operace provádí tak dlouho, dokud nezískáme na hlavní diagonále samé jedničky.

Myšlenka (hrubý algoritmus):
<zadej matici soustavy>
<začni prvním řádkem>
dokud <neprojdeš všechny řádky matice> opakuj
  <připrav řádek>
  <získej jedničku>
  <nuluj sloupec>
  <přejdi na další řádek>
<řešením je vektor pravých straan>

Celý program budeme tvořit postupně v dílčích krocích odpovídajících popsanému postupu.
Sestavíme a odladíme postupně tedy následující procedury:

1. Nacti - načtení koeficientů soustavy jako matice soustavy. Zadáváme počet rovnic a počet neznámých
2. Tisk - vytiskne aktuální matici soustavy
3. Priprav(ktery_rad) - připravuje aktuální řádek - zajistí, aby v aktálním řádku na hlavní diagonále byl nenulový prvek a šlo tedy v dalším kroku z něho opatřit jedničku. Připrava řádku se dosáhne výměnou s některým z následujících řádků.
4. Jednicka(ktery_rad) - v aktuálním řádku na hlavní diagonále zajistí jedničku tím, že se celý řádek vydělí číslem na hlavní diagonále.
5. Nuluj(ktery_sloup) - vynuluje sloupec s aktuální jedničkou na hlavní diagonále. Nahradí tedy všechna čísla v tomto sloupci nulami, kromě jedničky na hlavní diagonále. Toho dosáhne vynásobením řádku s jedničkou opačným koeficientem ke koeficientu nulovaného řádku a přičtením.


Až budou všechny tyto procedury odladěny, sestavíme proceduru Regular_reseni pro opakované provádění těchto operaci podle výše uvedeného hrubého algoritmu.


B) Řešení singulární soustavy lineárních rovnic

Při řešení singulární soustavy lineárních rovnicse nám nepodaří získat jednotkovou matici z levých stran soustavy, protože se v jednom nebo více řádcích na levé straně objeví samé nuly. Potom závisí na pravé straně tohoto řádku.

Ukážeme si to opět (zkráceně) na příkladě:


        2y + z = 1   
2x +   y  - z = 0
2x + 3y       = 1

Řešením této soustavy dostáváme:

Použitím přípravy řádku na 1.řádek , získej jedničku a nuluj sloupec dostaneme:

Pokud použijeme tentýž postup na druhý řádek, obdržíme matici:

V třetím řádku jedničku na hlavní diagonále už získat nelze - třetí rovnice zmizela (samé nuly). Matice odpovídá soustavě:
  x     - 3z/4 = -1/2   
      y + z/2  =  1/2
             0z   =   0

Tato soustava má nekonečně mnoho řešení s volitelnou neznámou z (počet rovnic je o jednu menší než počet neznámých).
x = -1/2 + 3z/4
y = 1/2 - z/2
z je libovolné číslo

Pokud tedy při opakování operací připrav řádek, získej jedničku, nuluj sloupec skončíme u operace připrav řádek v situaci, že již nelze připravit řádek (jsou na levé straně samé nuly) a na pravé straně je také nula, pak má soustava nekonečně řešení. Za ty neznámé. které převyšují počet rovnic zvolíme a zbývající dopočítáme.

Poslední variantu řešení ukazuje příklad soustavy:


        2y + z = 1   
2x +   y  - z = 0
2x + 3y       = 3

Řešením této soustavy dostáváme:

Použitím přípravy řádku na 1.řádek , získej jedničku a nuluj sloupec dostaneme:

Pokud použijeme tentýž postup na druhý řádek, obdržíme matici:

V třetím řádku jedničku na hlavní diagonále už získat nelze. Matice odpovídá soustavě:
  x     - 3z/4 = -1/2   
      y + z/2  =  1/2
             0z   =   3

Tato soustava nemá řešení
(z neexistuje).

Pokud tedy při opakování operací připrav řádek, získej jedničku, nuluj sloupec skončime u operace připrav řádek v situaci, že již nelze připravit řádek (jsou na levé straně samé nuly) a na pravé straně je nenulové číslo, pak nemá soustava řešení..

Můžeme se pokusit zformulovat hrubý algoritmus, který by zahrnoval i tyto varianty:

Myšlenka (hrubý algoritmus):
<zadej matici soustavy>
<začni prvním řádkem>
dokud <byl připraven předchozí řádek a neprošli jsme všechny řádky matice> opakuj
  <připrav řádek>
  když <je připraven řádek> pak
    <získej jedničku>
    <nuluj sloupec>
    <přejdi na další řádek>
   jinak
    <soustava je singulární>

Program doplníme o následující procedury a postupně odladíme :

8. Reseni_parcial - určí kořeny regulární soustavy a pozná singulární soustavu (a napíše o tom zprávu)
9. Reseni - vyřeší soustavu jak regulárí, tak i singulární soustavu a vytiskne řešení. V případě singulární soustavy rozliší případ, kdy nemá řešení a kdy má nekonečmš řešení.


Až budou všechny tyto procedury odladěny, můžeme předchozí pomocné procedury Regularni_reseni a Reseni_parcial odstranit a hlavní program zredukovat na volby: Zadání, Řešení a Konec.


Program Jordan může zatím vypadat takto:


program Jordan;

  const Max = 50;
  type TRadek = array[1..Max] of real;
          TMatice = array[1..Max] of TRadek;
  var   Soustava,Zadani: TMatice;
          radky,sloupce,volba,cislo :integer;
          jdeto:boolean;
{typ pole pro řádek matice}
{typ dvojrozměrného pole pro matici}
{globální proměnné}
{počet rovnic,neznámých,volba řádku,metody}
 
procedure Nacti;
  var ktery_rad,ktery_sl : integer;
  begin
     for ktery_rad:=1 to radky do
       for ktery_sl:=1 to sloupce do
         begin
           writeln('Zadejte koeficienty soustavy:');
           readln(Soustava[ktery_rad,ktery_sl]);
         end;
     Zadani:=Soustava;
 {opakování po řádcích}
{opakování v jednom řádku po sloupcích}

{postupné načítání prvků matice}

{uložení původní matice soustavy}
  end;
procedure Tisk;
  var ktery_rad,ktery_sl : integer;
  begin
     for ktery_rad:=1 to radky do
       begin
         for ktery_sl:=1 to sloupce do
           write(Soustava[ktery_rad,ktery_sl],' ');
           writeln;
         end;
 {opakování po řádcích}
{opakování v jednom řádku po sloupcích}

{tisk prvků matice}
  end;
procedure Priprav(cislo_rad:integer;var jak:boolean);
  var ktery_rad,ktery_sl : integer;
        radek:TRadek;
  begin
     ktery_rad:=cislo_rad;
     while (Soustava[ktery_rad,cislo_rad] = 0) and (ktery_rad<radky) do
       ktery_rad:=ktery_rad+1;
     if Soustava[ktery_rad,cislo_rad] = 0 then
         jak := false
       else
         begin
           radek:=Soustava[cislo_rad];
           Soustava[cislo_rad]:=Soustava[ktery_rad];
           Soustava[ktery_rad]:=radek;
           jak := true;
         end;
 {začneme od připravovaného řádku}
{dokud je prvek na hlavní diagonále 0}
{a nejsme v posledním řádku}
{přejdeme na další řádek}
{když je na hlavní diagonále nula}
{připravit řádek už nelze}

{uložíme původní připravovaný řádek}
{vložíme do připravovaného nalezený řádek}
{vložíme do nalezeného uložený}
{řádek připraven}
  end;
procedure Jednicka(cislo_rad:integer);
  var ktery_rad,ktery_sl : integer;
        koeficient:real;
  begin
     koeficient:=Soustava[cislo_rad,cislo_rad];
     for ktery_sl:=1 to sloupce do
       Soustava[cislo_rad,ktery_sl]:= Soustava[cislo_rad,ktery_sl]/koeficient;
 {koeficientem je prvek na hl.diagonále}
{všechny prvky v daném řádku}
{dělíme koeficientem}
  end;
procedure Nuluj_sloupec(cislo_sloupce:integer);
  var ktery_rad,ktery_sl : integer;
        koeficient:real;
  begin
     for ktery_rad:=1 to radky do
       begin
         if ktery_rad <> cislo_sloupce then
           begin
             koeficient:=(-1)*Soustava[ktery_rad,cislo_sloupce];
             for ktery_sl:=1 to sloupce do
               Soustava[ktery_rad,ktery_sl]:= Soustava[cislo_sloupce,ktery_sl]*koeficient+ Soustava[ktery_rad,ktery_sl];
           end;
       end;
 {pro všechny řádky matice}

{není-li to řádek s připravenou jedničkou}
{koeficient, kterým násobíme je}
{opačné číslo k prvku na hl.diagonále}
{všechny prvky jedničkového řádku}
{násobíme a přičítáme k nulovanému}
  end;
procedure Regularni_reseni;
  var ktery_rad,ktery_sl : integer;
  begin
     ktery_rad:=1;
     while ktery_rad<radky+1 do
       begin
         Priprav(ktery_rad,jdeto);
         Jednicka(ktery_rad);
         Nuluj_sloupec(ktery_rad);
         ktery_rad:=ktery_rad+1;
       end;
 {od prvního řádku}
{dokud neprojdeme všechny řádky}

{připrav řádek s nenulovým prvkem}
{opatři jedničku na hl.diagonále}
{vynuluj ostatní prvky sloupce s jedničkou}
{přejdi na další řádek}
  end;
procedure Reseni_parcial;
  var ktery_rad,ktery_sl : integer;
  begin
     ktery_rad:=1;
     jdeto:=true;
     while (ktery_rad<radky+1) and jdeto do
       begin
         Priprav(ktery_rad,jdeto);
         if jdeto then
           begin
             Jednicka(ktery_rad);
             Nuluj_sloupec(ktery_rad);
             ktery_rad:=ktery_rad+1;
           end
         else
           begin
             writeln('Soustava je singularni');
             writeln('(nema reseni nebo ma nekonecne reseni)');
           end
       end;
 {od prvního řádku}
{byl připraven předchozí řádek}
{dokud neprojdeme všechny řádky}
{a předchozí řádek byl připraven}
{připrav další řádek s nenulovým prvkem}
{je-li připraven}

{opatři jedničku na hl.diagonále}
{vynuluj ostatní prvky sloupce s jedničkou}
{přejdi na další řádek}



{napíše zprávu o singulárnosti soustavy}
  end;

Begin
   writeln('Program Jordan umoznuje:');
   repeat
     writeln('1 ... Nacist matici soustavy');
     writeln('2 ... Tisk matice soustavy');
     writeln('3 ... Pripravit radek');
     writeln('4 ... Opatrit jednicku na radku');
     writeln('5 ... Opatrit nuly ve sloupci');
     writeln('6 ... Tisk reseni');
     writeln('7 ... Reseni-pro regularnii');
     writeln('8 ... Reseni-castecne');
     writeln('9 ... Reseni');
     writeln('0 ... Ukoncit');
     writeln('Zadejte svoji volbu:');
     readln(volba);
     case volba of
       1: begin
             write('Zadejte pocet rovnic:');readln(radky);
             write('Zadejte pocet neznamych:');readln(sloupce);
             sloupce:=sloupce+1;
             Nacti;
           end;
       2: Tisk;
       3: begin
             write('Zadejte cislo radku:');readln(cislo);
             Priprav(cislo,jdeto);
             writeln('Vysledna matice soustavy je:');
             Tisk;
           end;
       4: begin
             write('Zadejte cislo radku:');readln(cislo);
             Jednicka(cislo);
             writeln('Vysledna matice soustavy je:');
             Tisk;
           end;
       5: begin
             write('Zadejte cislo sloupce:');readln(cislo);
             Nuluj_sloupec(cislo);
             writeln('Vysledna matice soustavy je:');
             Tisk;
           end;
       6: ;
       7: begin
             Regularni_reseni;
             writeln('Vysledna matice soustavy je:');
             Tisk;
           end;
       8: begin
             Reseni_parcial;
             writeln('Vysledna matice soustavy je:');
             Tisk;
           end;
       9: ;
       0: ;
     end;
   until volba=0;
 {nabidka cinnosti}












{zadani volby}






{realizace volby}

































End.


Domácí úkol:

    Doplňte program Jordan o procedury Tisk_reseni na tisk kořenů soustavy a Reseni na úplné řešení soustavy rovnic. U singulární soustavy napíše zprávu, že nemá řešení. Pokud má nekonečně řešení, nabídne možnost volby neznámé (popř. neznámých) a vypočítá zbývající neznámé.

On-line účast na řešení úkolu

Řešit úkol Prohlídka hodnocení úkolu Dotazy,připomínky

Pomocí volby Řešit můžete (po přihlášení) odeslat vaše řešení domácího úkolu (každý úkol smíte řešit jen jednou). Volbou Hodnocení si přečtete hodnocení a komentář od vyučujícího. Dotaz nebo připomínku můžete opakovaně zasílat pomocí tlačítka Dotazy, Komunikace (na levém okraji) zobrazuje příklad možné komunikace s vyučujícím.