Lineární modely - 5. přednáška Systémy lineárních rovnic a determinanty matic Ondřej Klíma 21. 3. 2013 4. přednáška Systémy a determinanty Osnova přednášky • Soustavy lineárních rovnic • Gausova eliminace • Inverzní matice Determinanty matic • Parita permutace (možná, není nezbytné) 4. přednáška Systémy a determinanty Motivační příklad Příklad " Vyřešte soustavu lineárních rovnic (v oboru Z,Q,M,C) 2x + 3y + 5z = 0 x + 2y - z = 4 y + 2z = - -1 • Řešení [x,y,z] = [1,1,-1]. • Maticový zápis soustavy 2 3 5 0 1 2 -1 4 0 1 2 -1 V následujícím se omezíme na pole skalárů (např. Q,R,C). I když některé idee lze bez potíží aplikovat v oborech integrity. 4. přednáška Systémy a determinanty Maticový zápis systémů lineárních rovnic • Soustava au*! + a12x2 + a13x3 = jbi 321*1 + a22x2 + a23x3 = b2 a^xA + a32x2 + a33x3 = b3 • Zápis pomocí násobení matic: au a12 a13 \ / Xt \ / ^ \ a21 a22 a23 • x2 = \ b2 a3i a32 a33 / \ x3 / \ b3 J • Stručně píšeme A- x = b, kde xg K3, beK3 (sloupce). • Obecně xeť.íiÉPa tedy A g Mařm,n(K). Přesněji x g Mařnj1 (K) a b g Mařmj1 (K). • /A matice soustavy, (A \ b) rozšířená matice soustavy. 4. přednáška Systémy a determinanty Postup - elementární řádkové úpravy • Dvě soustavy (rozšířené matice) jsou ekvivalentní, pokud mají stejná řešení. • Postup - převod soustavy na ekvivalentní jednodušší soustavu. • Realizace - pomocí elementárních řádkových úprav. Elementární řádkové transformace: • záměna dvou řádků; • vynásobení vybraného řádku nenulovým skalárem (POLE); • přičtení řádku k jinému řádku. Systematicky můžeme použít elementární řádkové úpravy k postupné eliminaci proměnných. Postup je algoritmický a většinou se mu říká Gausova eliminace proměnných. 4. přednáška Systémy a determinanty Schodovitý tvar matice Věta Nenulovou matici nad libovolným polem skalárů K lze konečně mnoha elementárními řádkovými transformacemi převést na tzv. (řádkově) schodovitý tvar: 9 Je-li a,-| = • • • = a,y = 0, potom a^ = 0 pro všechna k > /'. • Je-li aj--\j první nenulový prvek na (/' - 1 )-tém řádku, tzv. pivot, pak a-,j = 0. Matice v řádkově schodovitém tvaru vypadá takto /0...0 a-ij a-|j+i ... a-i^ ......... ai,m\ 0...0 0 0 ... 0 a2,k ......... a2,m 0...0 0 0 ... 0 0 ... a/iP ... a3,m { \ \ \ ) a matice může, ale nemusí, končit několika nulovými řádky. 4. přednáška Systémy a determinanty Příklad Příklad Vyřešte soustavu lineárních rovnic. / 2 4 1 5 -1 1 ^ 12 0 2 0 0 12 0 3 1 2 ^ 2 4 2 5 -3 o) Řešení [-4,0, -1,2,0] + ř(-2,1,0,0,0) + s(2,0,2, -1,1). Množina řešení soustavy (nad nekonečným polem K) je: jednoprvková, prázdná nebo nekonečná. Pro homogenní soustavy (pravé strany nulové) je množina řešení jednoprvková nebo nekonečná. 4. přednáška Systémy a determinanty Algoritmus - Gausova eliminace Algoritmus pro řešení systémů lineárních rovnic: O Záměnou řádků docílíme, že v prvním řádku bude v prvním nenulovém sloupci nenulový prvek, nechť je to y-tý sloupec. O Pro i = 2,..., vynásobením prvního řádku prvkem a,y, Mého řádku prvkem a1y a odečtením vynulujeme prvek a,y na /-tém řádku. O Opakovanou aplikací bodů (1) a (2), vždy pro zbytek řádků a sloupců v získané matici dospějeme po konečném počtu kroků k požadovanému tvaru. Algoritmus lze dále dokončit i tak, že matici vyeliminujeme do tzv. redukovaného schodovitého tvaru, kde pivot je jediný nenulový prvek v příslušném sloupci. (Mluvíme o zpětné eliminaci.) 4. přednáška Systémy a determinanty Inverzní matice Definice Říkáme, že B je matice inverzní k čtvercové matici A, když A ■ B = B ■ A = E. Píšeme pak B = A~1, přičemž matice B je čtvercová stejného rozměru n. Matici, k níž existuje matice inverzní, říkáme invertibilní matice. Pokud řešíme soustavu A ■ x = b s invertibilní maticí A, pak x = A 1 • b. Postup výpočtu: snažme se určit matici X splňující A ■ X = E postupně po sloupcích. První sloupec je řešením následujícího systému: 2 3 1 2 0 1 /1 0 0 5 \ 9 1 0 1 0 "i Vo 0 1 i) 4. přednáška Systémy a determinanty Inverzní matice - algoritmus Algoritmus pro nalezení inverzní matice O Vedie sebe napíšeme původní matici A a jednotkovou matici E. O Matici A upravujeme řádkovými elementárními úpravami nejprve na schodovitý tvar. O Následně zpětnou eliminací na diagonální matici. O V té násobíme řádky inverzními prvky z K, abychom dostali jednotkovou matici E. O Tytéž úpravy souběžně prováděné s vedle napsanou maticí E vedou k hledané inverzi A~1. Q Pokud tento algoritmus narazí na vynulování celého řádku v původní matici, znamená to, že matice inverzní neexistuje. 4. přednáška Systémy a determinanty Determinant - očekávání, plán • Motivace - objem. • Obecná (korektní) definice \A\ (pro čtvercovou matici A), m Determinant a elementární řádkové úpravy. • existuje právě tehdy když \A\ ^ 0. • Použití pro přímý výpočet řešení soustavy. • Výpočet determinantu. • Determinant a součin matic - \A ■ B\ = \A\ ■ \B\. 4. přednáška Systémy a determinanty Determinant - matice typu 2 x 2, 3 x 3 A a-i2 321 ^22 \A\ — au 322 - 312^21 3-11 312 313 i4 = | 321 ^22 ^23 ^31 a32 ^33 \A\ = 3n 322^33 + 3l2a23a31 + 3l3a21a32 — 3i 3 322 ^31 ~~ 3l 2 321^33 ~~ 3ll323a32 Pozor, pro větší rozměr nelze počítat takto „úhlopříčně". 4. přednáška Systémy a determinanty Determinant - definice Definice Buď A = (a,y) čtvercová matice řádu n nad polem K. Determinant matice \A\ je prvek z K definovaný předpisem: 1^1 = ^ s9n(°")' aMi)" a2CT(2)an(J(n). aeSn Zde Sn je množina všech permutací množiny {1,2,...,/?}. A sgn(o-) je parita permutace a (přičemž sgn(o-) = ±1). Pozn.: Formální definice parity - viz dodatek na konci slajdů. Výpočet \A\ z definice není efektivní. Naučíme se jinak. 4. přednáška Systémy a determinanty Determinant - základní poznatky • Pro jednotkovou matice máme \ E\ = 1. • Speciální vzorce n = 2, n = 3. • Pokud A obsahuje nulový řádek, pak \A\ = 0. • Horní trojúhelníková matice - součin prvků na diagonále. • Pro transponovanou matici AT platí |/A|=|/AT|. Definice Pro každou matici A = (a,y) typu m/n definujeme AT = (a^) s prvky ájj = ap typu n/m. Čtvercová matice A s vlastností A = AT se nazývá symetrická. Jestliže platí A = -AT, pak se A nazývá antisymetrická. 4. přednáška Systémy a determinanty Determinant a elementární řádkové úpravy 9 Vznikne-li matice B přehozením dvou řádků čtvercové matice A, pak|fí| = -\A\. • Jsou-li dva řádky čtvercové matice A stejné, pak \A\ = 0. • Vznikne-li matice B vynásobením některého řádku čtvercové matice A konstantou c, pak |fí| = c • \ A\. • Nechť matice A = (a,y), B = (b-,j) a C = (c,y) jsou tři čtvercové matice řádu n, které se od sebe liší pouze prvky /c-tého řádku, přičemž k-lý řádek matice A je součtem k-lý řádků matic Ba C, tj. = by + % pro j g {1,2,..., n}. Potom \A\ = \B\ + \C\. m Vznikne-li matice B z čtvercové matice A přičtením násobku některého řádku k jinému řádku, pak |fí| = \A\. Metoda výpočtu determinantu pomocí Gaussovy eliminace. Pozor: obecně neplatí \B+ C\ = \B\ + \C\. 4. přednáška Systémy a determinanty Determinant - příklad výpočtu Příklad Určete determinant matice / 2 3 5\ 1 2 -1 \ 0 1 2/ Eliminace: \A\ = 9. Nebo z definice: \A\ = 8 + 5 - (-2) -6 = 9. Příklad ^ Určete determinant matice ( 1 0 0 2 ^ B = 0 3 4 0 0 5 6 0 l 7 0 0 8 ) Výsledek = 12. 4. přednáška Systémy a determinanty Výpočet determinantu - Laplaceův rozvoj Buď A = (a,y) čtvercová matice řádu n > 1. Pro zvolené indexy i, j označme Ay čtvercovou matici řádu n - 1, která vznikne z A vynecháním /-tého řádku a y'-tého sloupce. Pak prvek A/ = (-l)/+y-|A/l nazýváme algebraický doplněk prvku a,y v matici A. Věta (Laplaceův rozvoj) Buď A = (a,y) čtvercová matice řádu n > 1. Pak pro libovolný index i platí \A\ = ahÁiA + a/2A2 + • • • + a^ n = ^2 SijAij. 7=1 Hovoříme o rozvoji podle /-tého řádku. 4. přednáška Systémy a determinanty Laplaceův rozvoj - příklad Příklad Určete determinant matice ( 1 0 0 2 ^ B = 0 3 4 0 0 5 6 0 ^ 7 0 0 8 ) lfll = 1.(-1) 1+1 3 4 0 5 6 0 0 0 8 + 2-(-1) 1+4 8 • 3 4 5 6 Všiměme si, že 2-7 3 4 5 6 (8-14). 3 4 5 6 0 3 4 0 5 6 7 0 0 (_6).(-2) = 12 3 4 5 6 4. přednáška Systémy a determinanty Inverze pomocí adjungované matice • Laplaceův rozvoj pomocí sloupce — důkaz transponováním. • Definujeme A = (Ay) matici řádu n složenou z algebraických doplňků. K ní transponovanou matici A* = AT nazýváme adjungovanou maticí k matici A. Věta Buď A čtvercová matice řádu n > 1 taková, že \ A\ ^ 0. Pak A-A = \A\-A - A*. • Důsledek: existuje právě tehdy, když \A\ ^ 0. • Praktické použití je diskutabilní. Pro výpočet determinantů |Ajj\ je zapotřebí stejně eliminovat. 4. přednáška Systémy a determinanty Cramerovo pravidlo Řešíme rovnici Ax = b, kde A je čtvercová matice taková, že \A\ ^ 0. Tudíž řešení je x = Ar1/?. Věta Buď A čtvercová matice řádu n > 1 taková, že \ A\ ^ 0. Pak soustava Ax = b má jediné řešení x = (x-i, x2,..., xn)T, kde Xi = W přičemž As je matice vzniklá z matice A nahrazením jejího j-tého sloupce sloupcem b. 4. přednáška Systémy a determinanty Cramerovo pravidlo - příklad Příklad (Motivační příklad) ^ Vyřešte soustavu lineárních rovnic 2x + 3y + 5z = 0 x + 2y - z = 4 y + 2z = -1 0 3 5 4 2-1 -1 1 2 2 3 1 2 0 1 5 -1 2 9 9 1, X2)*3 - sami. 4. přednáška Systémy a determinanty Cauchyova věta Věta Pro libovolné dvě čtvercové matice AaB stejného řádu platí \A-B\ = \A\ ■ \B\. Důsledek: = \A\~\ Důkaz: ukázka matematické rafinovanosti. Bloky v matici (submatice): jsou-li A a C čtvercové matice (ne nutně stejného rozměru) potom Důkaz: idea stejná jako u trojúhelníkové matice. 4. přednáška Systémy a determinanty Cauchyova věta - důkaz \A\ ■ \B\ . Pro matice A a B stejného řádu uvažujeme matici F dvojnásobného řádu: A 0 -E B Tento determinant lze spočítat obvyklým způsobem 1. Prohazování řádků mezi horní a dolní polovinou: -E B (-1)" A 0 2. násobení -1 v horní polovině: E -B A 0 3. Eliminace matice A v levém dolním rohu: E -B 0 AB \AB\ 4. přednáška Systémy a determinanty Požadavky • Vyřešit zadaný systém lineárních rovnic. • Spočítat inverzní matici (dle algoritmu). » Spočítat determinant matic (i matic s parametrem). Ovládat obě metody a umět je kombinovat • Znát základní vlastnosti determinantů (Cauchyova věta). • Znalost adjungované matice a Cramerovo pravidlo se nezkouší. 4. přednáška Systémy a determinanty Dodatek - parita permutace (slajdy prof.Slováka) Říkáme, že dvojice prvků a,beX = {1,...,n} tvoří inverzi v permutaci a, je-li a < b a a (a) > 1, je právě \n\ sudých a \n\ lichých permutací. Jestliže složíme dvě permutace za sebou, znamená to provést napřed všechny transpozice tvořící první a pak druhou. Proto pro libovolné permutace a, r\ -. X X platí sgn(o- o v) = sgn(o-) • sgnfa), sgn(o-~1) = sgn(o-). 4. přednáška Systémy a determinanty