2. Úpravy a řešení soustav lineárních rovnic 2. Úpravy a řešení soustav lineárních rovnic ­ p. 1/27 Úpravy a řešení soustav lineárních rovnic 1. Soustava lineárních rovnic 2. Ekvivalentní úpravy 3. Maticový zápis 4. Úprava na schodový tvar 5. Zpětná substituce 6. Gaussova eliminace 7. Gauss-Jordanova metoda 8. Pracnost řešení 2. Úpravy a řešení soustav lineárních rovnic ­ p. 2/27 2.1 Soustava lineárních rovnic DEFINICE 1 Soustavou m lineárních rovnic o n neznámých x1, . . . , xn nazýváme množinu rovnic ve tvaru: a11x1 + . . . + a1nxn = b1 ... ... ... am1x1 + . . . + amnxn = bm (S) Čísla aij, i = 1, . . . , m, j = 1, . . . , n nazýváme koeficienty soustavy a bi, i = 1, . . . , m nazýváme pravé strany. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 3/27 2.1 Soustava lineárních rovnic P ŘÍKLAD 1 Soustava z úvodního příkladu II: 2u1 -u2 = 0.2683 -u1 +2u2 -u3 = 0.2683 -u2 +2u3 -u4 = 0.2683 -u3 +2u4 -u5 = 0.2683 -u4 +2u5 = 0.2683 Jedná se o soustavu 5 rovnic o 5 neznámých u1, . . . , u5, kde a11 = 2, a12 = -1, a13 = 0, a14 = 0, a15 = 0, a21 = -1, a22 = 2, a23 = -1, a24 = 0, a25 = 0, a31 = 0, a32 = -1, a33 = 2, a34 = -1, a35 = 0, a41 = 0, a42 = 0, a43 = -1, a44 = 2, a45 = -1, a51 = 0, a52 = 0, a53 = 0, a54 = -1, a55 = 2, b1 = 0.2683 b2 = 0.2683 b3 = 0.2683 b4 = 0.2683 b5 = 0.2683 2. Úpravy a řešení soustav lineárních rovnic ­ p. 4/27 2.2 Ekvivalentní úpravy Základní myšlenka řešení soustavy lineárních rovnic spočívá v nahrazení dané soustavy jinou soustavou, která má stejné řešení a je jednodušší. DEFINICE 2 Ekvivalentními úpravami soustavy lineárních rovnic nazýváme následující úpravy: E1 Vzájemná výměna libovolných dvou rovnic soustavy, E2 Násobení obou stran některé rovnice soustavy nenulovým číslem, E3 Přičtení násobku některé rovnice soustavy k jiné rovnici. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 5/27 2.2 Ekvivalentní úpravy Ekvivalentní úpravy mají tu vlastnost, že jejich pomocí můžeme z upravené soustavy získat zpět původní soustavu. Jestliže soustava S vznikla ze soustavy S vzájemnou výměnou i-té a j-té rovnice podle pravidla E1, pak tatáž úprava použitá na S nás přivede zpět k S. Jestliže soustava S vznikla ze soustavy S násobením i-tého řádku nenulovým číslem podle pravidla E2, pak násobením téhož řádku soustavy S číslem 1 obdržíme zpátky soustavu S. Jestliže soustava S vznikla ze soustavy S přičtením -násobku i-té rovnice k j-té rovnici (i = j), pak přičtení (-)-násobku i-té rovnice soustavy S k j-té rovnici soustavy S vede opět k S. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 6/27 2.2 Ekvivalentní úpravy Dvě soustavy lineárních rovnic nazýváme ekvivalentní soustavy, jestliže jednu z nich lze získat z druhé ekvivalentními úpravami. V ĚTA 1 Jsou-li dvě soustavy lineárních rovnic ekvivalentní, potom mají stejné řešení. P ŘÍKLAD 2 - 2x1 + x2 = 0 (1) x1 - 3x2 = -10 (2) Vhodná úprava soustavy je například vynásobení (2) dvěma, podle pravidla E2, a přičtení (1) k upravené (2), v souladu s pravidlem E3. Upravená soustava bude mít tvar - 2x1 + x2 = 0 (3) -5x2 = -20 (4) Z rovnice (4) vypočteme x2 = 4 a po dosazení do rovnice (3) dostaneme -2x1 + 4 = 0 odkud x1 = 2. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 7/27 2.3 Maticový zápis Soustavu (S) bude úsporně zapisovat do tabulky a11 . . . a1n b1 ... ... ... ... am1 . . . amn bm , kterou nazýváme rozšířená matice soustavy (S). Matici A a vektor b A = a11 . . . a1n ... ... ... am1 . . . amn , b = b1 ... bm , nazýváme maticí soustavy (S) a pravou stranou soustavy (S) . Pokud vektor x má za složky neznámé x1, . . . , xn můžeme soustavu zapsat v maticové podobě Ax = b. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 8/27 2.3 Maticový zápis Ekvivalentním úpravám soustavy rovnic odpovídají operace s řádky rozšířené matice soustavy, které nazýváme elementární (řádkové) operace: (e1) Vzájemná výměna libovolných dvou řádků. (e2) Násobení některého řádku nenulovým číslem. (e3) Přičtení násobku některého řádku k jinému řádku. Máme-li dvě matice, z nichž jedna vznikla z druhé pomocí elementárních řádkových operací, říkáme, že matice jsou řádkově ekvivalentní. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 9/27 2.3 Maticový zápis V ĚTA 2 Mají-li dvě soustavy lineárních rovnic řádkově ekvivalentní rozšířené matice, potom mají stejné řešení. P ŘÍKLAD 3 Úpravu soustavy (1),(2) na (3),(4) můžeme zapsat pomocí elementárních operací ve tvaru -2 1 0 1 -3 -10 2 -2 1 0 2 -6 -20 +r1 -2 1 0 0 -5 -20 2. Úpravy a řešení soustav lineárních rovnic ­ p. 10/27 2.4 Úprava na schodový tvar DEFINICE 3 Budeme říkat, že matice je ve schodovém tvaru, jestliže má první nenulové prvky řádků zvané vedoucí prvky uspořádány jako schody klesající zleva doprava. Požaduje se přitom, aby vedoucí prvky nebyly nad sebou a aby všechny případné nulové řádky byly dole. P ŘÍKLAD 3 A = 2 0 2 0 0 2 , B = 0 2 2 0 0 2 0 0 0 , C = 0 3 2 0 0 0 0 0 0 2. Úpravy a řešení soustav lineárních rovnic ­ p. 11/27 2.4 Úprava na schodový tvar Pomocí elementárních řádkových operací můžeme převést lib. matici na schodový tvar. Je-li v matici soustavy [A|b] prvek aij nenulový, pak vynásobíme-li i-tý řádek této matice číslem -akj/aij a přičteme-li ho ke k-tému řádku, bude mít upravená matice v k-tém řádku a j-tém sloupci prvek akj + (-akj/aij) aij = 0. Pokud je prvek a11 nenulový, lze takto transformovat matici [A|b] na tvar a11 a12 . . . a1n b1 0 a1 22 . . . a1 2n b1 2 ... ... ... ... ... 0 a1 m2 . . . a1 mn b1 m 2. Úpravy a řešení soustav lineárních rovnic ­ p. 12/27 2.4 Úprava na schodový tvar Pokud bude také prvek a1 22 nenulový, můžeme obdobně dosáhnout pomocí elementárních řádkových operací, aby i pod ním byly v upravené matici nuly. Bude-li pokaždé ai-1 ii = 0, dostaneme nakonec matici ve schodovém tvaru (nebo též v tzv. trojúhelníkovém tvaru) s nenulovými prvky a11, a1 22, . . . , ak-1 kk . a11 a12 . . . a1k . . . a1n b1 0 a1 22 . . . a1 2k . . . a1 2n b1 2 ... ... ... ... ... 0 0 ak-1 kk . . . ak-1 kn bk-1 k 0 0 . . . 0 . . . 0 bk k+1 0 0 . . . 0 . . . 0 0 ... ... ... ... ... 0 0 . . . 0 . . . 0 0 Pokud ai-1 ii = 0 a je možno nalézt prvek ai-1 ji = 0, j > i, stačí vzájemně vyměnit před úpravou i-tý a j-tý řádek. V opačném případě dostaneme obecnější schodový tvar. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 13/27 2.4 Úprava na schodový tvar POZOR! Neprovádíme-li postupné úpravy na upravené matici, můžeme se dopustit chyby. Například úpravami 1 1 1 1 2 1 1 0 2 0 1 1 -r3 -r2 1 1 1 1 0 1 0 -1 0 -1 0 1 +r2 1 1 1 1 0 1 0 -1 0 0 0 0 nedostaneme rozšířenou matici soustavy ekvivalentní s původní matici soustavy. Této chybě se můžeme vyhnout tak, že zvolíme jeden řádek, který neupravujeme, ale použijeme ho k úpravě ostatních. Například úpravy následující úpravy jsou již ekvivalentní. 1 1 1 1 2 1 1 0 2 0 1 1 -2r1 -2r1 1 1 1 1 0 -1 -1 -2 0 -2 -1 -1 -2r2 1 1 1 1 0 -1 -1 2 0 0 1 3 2. Úpravy a řešení soustav lineárních rovnic ­ p. 14/27 2.5 Zpětná substituce Uvažujme, že rozšířená matice soustavy je ve schodovém tvaru a11 a12 . . . a1k . . . a1n b1 0 a1 22 . . . a1 2k . . . a1 2n b1 2 ... ... ... ... ... 0 0 ak-1 kk . . . ak-1 kn bk-1 k 0 0 . . . 0 . . . 0 bk k+1 0 0 . . . 0 . . . 0 0 ... ... ... ... ... 0 0 . . . 0 . . . 0 0 1. Jestliže poslední nenulový řádek rozšířené matice soustavy má nenulový pouze poslední prvek bk k+1, pak tomuto řádku odpovídá rovnice 0 = bk k+1, která nemá pro bk k+1 = 0 řešení. V tomto případě tedy daná soustava nemá řešení. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 15/27 2.5 Zpětná substituce P ŘÍKLAD 4 Soustava nemá řešení Rozšířená matice soustavy byla elementárními řádkovými operacemi převedena na schodový tvar: 1 2 -1 1 0 1 -1 2 0 0 0 -3 Tato rozšířená matice soustavy odpovídá soustavě: x1 + 2x2 - x3 = 1 x2 - x3 = 2 0 = -3 Poslední rovnici 0 = -3 nelze splnit pro žádnou volbu x1, x2, x3 a soustava tudíž nemá řešení. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 16/27 2.5 Zpětná substituce Uvažujme, že rozšířená matice soustavy je ve schodovém tvaru a11 a12 . . . a1k . . . a1n b1 0 a1 22 . . . a1 2k . . . a1 2n b1 2 ... ... ... ... ... 0 0 ak-1 kk . . . ak-1 kn bk-1 k 0 0 . . . 0 . . . 0 bk k+1 0 0 . . . 0 . . . 0 0 ... ... ... ... ... 0 0 . . . 0 . . . 0 0 a11 a12 . . . a1n b1 0 a1 22 . . . a1 2n b1 2 ... ... ... ... ... 0 0 . . . an-1 nn bn-1 n 2. Jestliže k = n, bn n+1 = 0 a ai-1 ii = 0, i = 1, . . . , n, pak n-tá rovnice má tvar an-1 nn xn = bn-1 n , ze které snadno vypočteme xn. Po dosazení do předchozích rovnic zbude v (n - 1)-ní rovnici opět jediná neznámá. Budeme-li takto postupovat dále, určíme jediné řešení soustavy. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 17/27 2.5 Zpětná substituce P ŘÍKLAD 5 Soustava má jediné řešení Rozšířená matice soustavy byla elementárními řádkovými operacemi převedena na schodový tvar: 1 2 -1 1 0 1 -1 2 0 0 1 -3 Tato rozšířená matice soustavy odpovídá soustavě: x1 +2x2 -x3 = 1 x2 -x3 = 2 x3 = -3 x1 +2x2 -(-3) = 1 x2 -(-3) = 2 x1 +2x2 = -2 x2 = -1 x1 + 2(-1) = -2 x1 = 0 Soustava má jediné řešení x1 = 0, x2 = -1, x3 = -3. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 18/27 2.5 Zpětná substituce a11 a12 . . . a1k . . . a1n b1 0 a1 22 . . . a1 2k . . . a1 2n b1 2 ... ... ... ... ... 0 0 ak-1 kk . . . ak-1 kn bk-1 k 0 0 . . . 0 . . . 0 0 0 0 . . . 0 . . . 0 0 ... ... ... ... ... 0 0 . . . 0 . . . 0 0 3. Jestliže rozšířená matice má obecný schodový tvar, pak z každé rovnice soustavy vyjádříme neznámou, která odpovídá vedoucímu prvku. Postupným dosazováním od posledního řádku dostaneme vzorce pro neznámé odpovídající vedoucím prvkům vyjádřené pomocí neznámých na pravé straně. V tomto případě má soustava nekonečně mnoho řešení. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 19/27 2.5 Zpětná substituce P ŘÍKLAD 6 Soustava má nekonečně mnoho řešení Rozšířená matice soustavy byla elementárními řádkovými operacemi převedena na schodový tvar: 1 1 -1 1 1 0 0 1 -1 2 0 0 0 0 0 Tato rozšířená matice soustavy odpovídá soustavě: x1 +x2 -x3 +x4 = 1 x3 -x4 = 2 0 = 0 x1 = 1 - x2 + x3 - x4 x3 = 2 + x4 x1 = 1 - x2 + (2 + x4) - x4 = 3 - x2 Soustava má nekonečně mnoho řešení x1 = 3 - x2, x3 = 2 + x4 přižemž x2, x4 volíme libovolně. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 20/27 2.6 Gaussova eliminace Gaussova eliminační metoda: 1. dopředná redukce, tj. redukce na schodový tvar 2. zpětná substituce, tj. řešení soustavy se schodovou maticí P ŘÍKLAD 7 Soustava, která nemá řešení. Řešme soustavu 2x1 + x2 = 2 x1 + 2x2 - x3 = 1 4x1 + 5x2 - 2x3 = -1 Ekvivalentními řádkovými úpravami dostaneme postupně 2 1 0 2 1 2 -1 1 4 5 -2 -1 2 - r1 -2r1 2 1 0 2 0 3 -2 0 0 3 -2 -5 -r2 2 1 0 2 0 3 -2 0 0 0 0 -5 Poslední rovnici 0x1 + 0x2 + 0x3 = -5 nelze splnit žádnou volbou x1, x2, x3. Soustava proto nemá řešení. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 21/27 2.6 Gaussova eliminace P ŘÍKLAD 8 Soustava s jediným řešením. Řešme soustavu 2x2 + 3x3 = 2 x2 + x3 = 0 x1 + x3 = 4 Ekvivalentními řádkovými úpravami dostaneme postupně 0 2 3 2 0 1 1 0 1 0 1 4 r3 r1 1 0 1 4 0 1 1 0 0 2 3 2 -2r2 1 0 1 4 0 1 1 0 0 0 1 2 Řešením rovnic dostaneme postupně x3 = 2 x2 = -x3 = -2 x1 = 4 - x3 = 2 což je jediné řešení naší soustavy. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 22/27 2.6 Gaussova eliminace P ŘÍKLAD 9 Soustava, která má nekonečně mnoho řešení. Řešme soustavu x1 + x2 + x3 = 1 x1 - x3 = 1 x2 + 2x3 = 0 Ekvivalentními řádkovými úpravami dostaneme postupně 1 1 1 1 1 0 -1 1 0 1 2 0 -r1 1 1 1 1 0 -1 -2 0 0 1 2 0 +r2 1 1 1 1 0 -1 -2 0 0 0 0 0 Poslední matice je rozšířenou maticí soustavy x1 + x2 + x3 = 1 -x2 - 2x3 = 0 0 = 0 2. Úpravy a řešení soustav lineárních rovnic ­ p. 23/27 2.6 Gaussova eliminace P ŘÍKLAD 9 Pokračování x1 + x2 + x3 = 1 (1) -x2 - 2x3 = 0 (2) 0 = 0 (3) Z rovnice (2) vypočteme x2 pomocí x3, tj. x2 = -2x3. Po dosazení za x2 do rovnice (1) dostaneme x1 = 1 + x3. Soustava má tedy nekonečně mnoho řešení ve tvaru x3 libovolné, x2 = -2x3, x1 = 1 + x3. Můžeme je zapsat také pomocí libovolného parametru p ve tvaru x3 = p, x2 = -2p, x1 = 1 + p. Poznámka: Má-li soustava nekonečně mnoho řešení, je množina řešení určena jednoznačně, nikoliv však její parametrizace. Například x2 = p, x3 = -1 2 p a x1 = -1 2 p + 1 je jiný tvar téhož řešení. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 24/27 2.7 Gauss-Jordanova metoda DEFINICE 4 Budeme říkat, že matice je v normovaném schodovém tvaru, jestliže je v takovém schodovém tvaru, že všechny prvky nad vedoucími prvky jsou nulové a navíc vedoucí prvky jsou rovny jedné. Gauss­Jordanova metoda: 1. dopředná redukce, tj. redukce na schodový tvar 2. úprava na normovaný schodový tvar (a) dělení řádků matice vedoucími prvky (b) nulování prvků nad vedoucími prvky pomocí elementárních řádkových operací (e1),(e2) a (e3) 2. Úpravy a řešení soustav lineárních rovnic ­ p. 25/27 2.7 Gauss-Jordanova metoda P ŘÍKLAD 10 Například dodatečnou úpravou rozšířené matice soustavy z příkladu 8 dostaneme 1 0 1 4 0 1 1 0 0 0 1 2 -r3 -r3 1 0 0 2 0 1 0 -2 0 0 1 2 Řešení soustavy se nachází v posledním sloupci matice vpravo, neboť rovnice, které odpovídají rozšířené matici soustavy napravo, jsou x1 = 2, x2 = -2 a x3 = 2 2. Úpravy a řešení soustav lineárních rovnic ­ p. 26/27 2.8 Pracnost řešení Gaussova eliminace je velmi efektivní pro ruční řešení malých soustav a pro počítačové řešení soustav stovek až tisíců rovnic. Metoda je velmi efektivní i pro počítačové řešení větších soustav se speciální strukturou rozložení nenulových prvků. Pro rozsáhlejší soustavy existují efektivnější metody, které se rozvíjejí i v současné době. Gaussova eliminace není vhodná pro paralelní počítačovou implementaci. Pracnost řešení soustavy metodou Gaussovy eliminace (m = n): 1. Dopředná redukce: 1 6 (2n + 1)(n + 1)n násobení, tj. cca 1 3 n3 pro velká n 2. Zpětná substituce: 1 2 n(n - 1) násobení, tj. cca 1 2 n2 pro velká n. 2. Úpravy a řešení soustav lineárních rovnic ­ p. 27/27