Ekvivalentní systémy rovnic Metody řešení systému lineárních rovnic užitím rozkladu matice soustavy, qr­rozklad Řešení systému lineárních rovnic metodou nejmenších čtverc ů Vlastní čísla matice Normy matic Iterační metody řešení systému lineárních rovnic Základní poznatky z kapitoly 6 a úlohy k procvičení Metody řešení systému lineárních algebraických rovnic 6 6. Metody řešení systému lineárních algebraických rovnic Cíl kapitoly Cílem této části je zvládnout problematiku řešitelnosti systému lineárních algebraických rovnic naučit se řešit systém lineárních rovnic jeho převedením na systém ekvivalentní s horní schodovitou maticí soustavy seznámit se s Gaussovou a s Jordanovou eliminační metodou seznámit se s metodou qr­rozkladu matice soustavy seznámit se s pojmem norma matice seznámit se s iteračními metodami řešení systému lineárních rovnic seznámit se s řešením systému lineárních rovnic metodou nejmenších čtverců Časová zátěž 20 hodin 6.1 Ekvivalentní systémy rovnic Několik úvodních slov. Dříve než přikročíte ke studiu této kapitoly je nutné, abyste měli dokonale zvládnuté základní pojmy z lineárních rovnic uvedené v kapitole 3. V této kapitole se budeme zabývat především problematikou existence a jednoznačnosti řešení systému m lineárních rovnic o n neznámých a popisu některých metod na jejich řešení. Seznámili jsme se již s Cramerovým pravidlem (věta 5.23) na řešení systému lineárních rovnic Ax = b, které lze použít v případě, že jeho matice soustavy A je regulární čtvercová matice. V tomto případě má systém právě jedno řešení. Určí se pomocí determinantů. Tato metoda se však nehodí k řešení systému lineárních rovnic pro větší počet neznámých, neboť k jeho řešení je nutno provést velký počet aritmetických operací. Dále jsme se seznámili s řešením systému lineárních rovnic Ax = b s regulární čtvercovou maticí soustavy užitím inverzní matice A-1 . Výpočet inverzní matice je na počet operací náročnější, než je řešení jednoho systému rovnic. Používáme ji jenom tehdy, jestliže inverzní matici známe, nebo ji potřebujeme i k jiným účelům. Popíšeme především metodu, založenou na pojmu ekvivalentnosti dvou systémů lineárních rovnic. Tato metoda se dá použít i v případě, že matice soustavy A není regulární čtvercovou maticí. Uvedená metoda nám pomůže též vyslovit větu o řešitelnosti a jednoznačnosti řešení systému lineárních rovnic. 252 Dva systémy lineárních rovnic A x = b, C x = d nazveme ekvivalentními, jestliže každý vektor, který je řešením systému rovnic A x = b, je i řešením systému C x = d a naopak, každé řešení systému rovnic C x = d je i řešením systému rovnic A x = b. Při řešení systému rovnic Ax = b půjde o nalezení takového ekvivalentního systému rovnic, který je možno snadno posoudit. To znamená určit, zda tento ekvivalentní systém má nebo nemá řešení a v případě, že má řešení, toto řešení nalézt. Takovým vhodným ekvivalentním systémem je systém, jehož matice soustavy je horní schodovitá matice. 6.1.1 Převod systému lineárních rovnic na systém lineárních rovnic s horní schodovitou maticí soustavy Uvažujme systém lineárních rovnic A x = b (6.1) Ukažme si platnost následujících pravidel P1, P2, P3, P4. P1. Nechť je libovolné reálné číslo = 0. Uvažujme libovolně zvolenou i­tou rovnici systému (6.1) ai,1 x1 + . . . + ai,n xn = bi. (6.2) Je evidentní, že vektor x vyhovuje rovnici (6.2), když a jenom když vyhovuje rovnici (ai,1 x1 + . . . ai,n xn) = bi, = 0. (6.3) Nahradíme-li tedy v systému (6.1) některou rovnici jejím násobkem číslem , = 0, je vzniklý systém ekvivalentní s daným systémem. P2. Nechť ai,1 x1 + . . . + ai,n xn = bi, (6.4) aj,1 x1 + . . . + aj,n xn = bj, (6.5) jsou dvě libovolné rovnice systému rovnic (6.1). Je opět evidenetní, že každý vektor x vyhovuje oběma těmto rovnicím, když a jenom když vyhovuje rov- nicím ai,1 x1 + . . . + ai,n xn = bi, (6.6) (aj,1 + ai,1) x1 + . . . + (aj,n + ai,n) xn = bj + bi, (6.7) kde je libovolné reálné číslo. 253 6. Metody řešení systému lineárních algebraických rovnic Přičteme-li tedy k některé rovnici systému (6.1) -násobek jiné rovnice, R, vznikne systém ekvivalentní se systémem (6.1). P3. Vypustíme-li ze systému rovnic (6.1) rovnici tvaru 0 x1 + 0 x2 + . . . + 0 xn = 0, obdržíme systém rovnic, který je ekvivalentní se systémem rovnic (6.1), neboť každý vektor x Vn této rovnici vyhovuje. Tato rovnice tedy nedává žádné omezení pro řešení systému rovnic (6.1). P4. Jestliže v systému rovnic (6.1) je některá rovnice tvaru 0 x1 + 0 x2 + . . . + 0 xn = c, c = 0, nemá uvažovaný systém žádné řešení, neboť této rovnici nevyhovuje žádný vektor. Tyto úvahy můžeme shrnout následovně. Věta 6.1. Nechť jsou dány dva systémy lineárních rovnic A x = b, C x = d o neznámých x1, x2, . . . , xn. Nechť systém C x = d vznikl ze systému A x = b těmito úkony: H1. Libovolnou rovnici systému jsme násobili číslem různým od nuly. H2. K libovolné rovnici jsme přičetli jinou rovnici systému. H3. Vyměnili jsme navzájem dvě rovnice systému. H4. K nenulovému násobku jedné rovnice jsme připočetli libovolný násobek jiné rovnice. Potom systémy A x = b, C x = d jsou navzájem ekviva- lentní. Poznámka. 1. Jestliže v systému rovnic Ax = b vypustíme rovnice tvaru 0 x1 + + 0 xn = 0, obdržíme systém rovnic s ním ekvivalentní. 254 2. Systém rovnic, v němž je rovnice tvaru 0 x1 + + 0 xn = konst, kde konst = 0, nemá řešení. Abychom si usnadnili zápis při operacích s rovnicemi, budeme pracovat jenom s koeficienty rovnic a s jejich pravými stranami. Abychom to precizovali, zaveďme si zobrazení T , jímž se ke každému systému lineárních rovnic A x = b přiřadí rozšířená matice tohoto systému rovnic (A|b), to jest T (A x = b) = (A|b). Lineární rovnici daného systému ai,1 x1 + . . . + ai,n xn = bi odpovídá v tomto zobrazení i-tý řádek rozšířené matice (A|b), to jest vektor (ai,1, . . . , ai,n|bi). Lehce nahlédneme, že zobrazení T je prosté zobrazení množiny systémů m lineárních rovnic Ax = b o neznámých x1, . . . , xn na prostor matic (A|b). Existuje tedy k němu inverzní zobrazení T -1 . Ukážme dále, že zobrazení T zachovává jak sečítání dvou rovnic, tak i násobení rovnice číslem. Uvažujme dvě rovnice ai,1 x1 + . . . + ai,n xn = bi, aj,1 x1 + . . . + aj,n xn = bj, a reálné číslo = 0. Potom podle definice v zobrazení T odpovídá rovnici ai,1 x1 + . . . + ai,n xn = bi (6.8) vektor (ai,1, . . . , ai,n|bi) (6.9) a rovnici aj,1 x1 + . . . + aj,n xn = bj (6.10) odpovídá vektor (aj,1, . . . , aj,n | bj). (6.11) Sečtením uvažovaných rovnic dostáváme rovnici (ai,1 + aj,1)x1 + + (ai,n + aj,n)xn = bi + bj. (6.12) Podle definice zobrazení T odpovídá této rovnici vektor ((ai,1 + aj,1), . . . , (ai,n + aj,n)|(bi + bj)). (6.13) 255 6. Metody řešení systému lineárních algebraických rovnic Je zřejmé, že v inverzním zobrazeni T -1 odpovídá vektoru (6.13) rovnice (6.12). Dále rovnici (ai,1 x1 + . . . + ai,n xn) = bi, = 0 (6.14) odpovídá v zobrazení T vektor ( ai,1, . . . , ai,n | bi). (6.15) Je zřejmé, že v inverzním zobrazeni T -1 odpovídá vektoru (6.15) rovnice (6.14). Předpokládejme, že jsme k systému lineárních rovnic Ax = b v zobrazení T přiřadili rozšířenou matici soustavy tohoto systému rovnic (A|b). Potom úkonům H1, H2, H3, H4 s rovnicemi systému Ax = b, uvedených ve větě 6.1, odpovídají elementární transformace H1(i, ), H2(i, j), H3(i, j), H4(i, , j, ) aplikované na matici (A|b). Větu 6.1 můžeme tedy přeformulovat takto. Věta 6.2. Nechť matice (A|b) (6.16) je rozšířenou maticí soustavy lineárních rovnic Ax = b. (6.17) Nechť matice (C|d) vznikla z matice (6.16) elementárními transformacemi. Potom systém lineárních rovnic Cx = d je ekvivalentní k systému rovnic (6.17). 256 Vhodnými elementárními transformacemi lze z matice (A|b) dospět ke schodovité matici (C|d), která odpovídá systému Cx = d, ekvivalentnímu k systému lineárních rovnic Ax = b. V kapitole 4 jsme uvedli postup převodu matice na schodovitý tvar užitím elementárních transformací. Řešení systému lineárních rovnic Ax = b lze tímto způsobem převést na řešení systému lineárních rovnic se schodovitou maticí soustavy. Postup řešení systému lineárních rovnic Jak řešit systém Ax = b Nechť je dán systém lineárních rovnic Ax = b (6.18) o n neznámých x1, . . . , xn. Tento systém lineárních rovnic můžeme řešit v těchto krocích 1. K daném systému rovnic přiřadíme matici rozšířenou (A|b). 2. Užitím vhodných elementárních transformací H1(i, ), = 0, H2(i, j), H3(i, j), H4(i, , j, ), = 0 postupně aplikovaných na matici (A|b), vytvoříme horní schodovitou matici (F |g). 3. Vypustíme nulové řádky matice (F |g). Takto vzniklou matici označme (C|d). Této matici odpovídá systém rovnic Cx = d. (6.19) 4. Nechť systém (6.19) má tvar c1,s1 xs1 + . . . + c1,s2 xs2 + . . . + c1,sh-1 xsh-1 + . . . + c1,nxn = d1 c2,s2 xs2 + . . . + c2,sh-1 xsh-1 + . . . + c2,nxn = d2 ... (6.20) ch-1,sh-1 xsh-1 + . . . + ch-1,nxn = dh-1 0 xn = dh, v němž čísla c1,s1 , c2,s2 , . . . , ch-1,sh-1 , dh jsou různá od 0, nebo tvar 257 6. Metody řešení systému lineárních algebraických rovnic c1,s1 xs1 + . . . + c1,s2 xs2 + . . . + c1,sh xsh + . . . + c1,nxn = b1 c2,s2 xs2 + . . . + c2,sh xsh + . . . + c2,nxn = d2 ... (6.21) ch,sh xsh + . . . + ch,nxn = dh v němž c1,s1 , c2,s2 , . . . , ch,sh jsou různá od 0. Systém (6.20) nemá řešení, neboť jeho poslední rovnice je tvaru 0 x1 + . . . + 0 xn = konst, kde konst = 0. (6.22) Této rovnici nevyhovuje žádný vektor x. Systém rovnic (6.20) obsahuje rovnici tvaru (6.22), když a jenom když matice soustavy C a matice rozšířená (C | d) mají různé hodnosti. Poněvadž jsme k systému rovnic Cx = d dospěli elementárními transformacemi ze systému Ax = b, můžeme vyslovit tento prozatímní závěr. Jestliže hodnost matice soustavy A je menší než hodnost matice rozšířené (A|b), nemá systém rovnic Ax = b řešení. Matice soustavy systému rovnic (6.21) je horní schodovitou maticí. O jeho řešení pojednáme později (str. 260). Trojúhelníková matice soustavy Řešení systému lineárních rovnic s regulární horní trojúhelníkovou maticí soustavy Řešme systém rovnic Cx = d, (6.23) kde C je horní regulární trojúhelníková matice řádu n, d je n­rozměrný sloupcový vektor a x je n­rozměrný sloupcový vektor neznámých. Rozepsáním tohoto systému dostáváme c1,1 c1,2 . . . c1,n-1 c1,n 0 c2,2 . . . c2,n-1 c2,n ... ... . . . ... ... 0 0 0 cn-1,n-1 cn-1,n 0 0 0 0 cn,n x1 x2 ... xn-1 xn = d1 d2 ... dn-1 dn (6.24) 258 Zpětná substituce Poněvadž dle předpokladu je matice C regulární, jsou její prvky na hlavní diagonále různé od nuly. Tento systém rovnic lze řešit metodou, zvanou metoda zpětné substituce. Z poslední rovnice vypočítáme xn. Dostáváme xn = dn/cn,n. (6.25) Dosadíme-li do předposlední rovnice za xn vypočítanou hodnotu (6.25), do- stáváme cn-1,n-1 xn-1 + cn-1,n dn/cn,n = dn-1. (6.26) Odtud xn-1 = 1/cn-1,n-1 (dn-1 - cn-1,n dn/cn,n). (6.27) Když jsme již vypočítali xn, xn-1, dosadíme tyto hodnoty do (n - 2)­té rovnice a vypočítáme xn-2. Tímto způsobem dále pokračujeme. Když jsme již vypočítali xn, xn-1, . . . , x2, dosadíme tyto hodnoty do první rovnice a vypočítáme zbývající hodnotu x1. Příklad 6.1. Nalezněte řešení systému lineárních rovnic (jehož matice soustavy je horní trojúhelníková matice). 2x1 + 3x2 + x3 = 11 x2 + 2x3 = 9 2x3 = 8. (6.28) Z poslední rovnice vypočítáme x3. Dostáváme x3 = 4. Dosazením této hodnoty do druhé rovnice dostáváme x2 + 8 = 9. Odtud dostáváme x2 = 1. Dosaďme za x2, x3 tyto vypočítáné hodnoty do první rovnice systému. Dostáváme 2x1 + 3 + 4 = 11. Odtud dostáváme x1 = 2. Řešením zadaného systému rovnic (6.28) jsme tedy obdrželi x1 = 2, x2 = 1, x3 = 4. Řešení systému lineárních rovnic s regulární diagonální matici sou- stavy. Řešme systém rovnic Cx = d, kde matice C je regulární diagonální matice. 259 6. Metody řešení systému lineárních algebraických rovnic Rozepsáním lze tento systém zapsat takto c1,1x1 = d1 c2,2x2 = d2 ... cn-1,n-1xn-1 = dn-1 cn,nxn = dn. (6.29) Řešením tohoto systému rovnic je zřejmě vektor x = C-1 d, to jest xi = di/ci,i, i = 1, 2, . . . , n. Příklad 6.2. Nalezněte řešení systému rovnic s diagonální matici soustavy 2x1 = 6, 3 x2 = 1, -2 x3 = 5. Řešení. Z první rovnice vypočítáme x1. Dostáváme x1 = 3. Z druhé rovnice vypočítáme x2. Dostáváme x2 = 1/3. Z třetí rovnice vypočítáme x3. Dostáváme x3 = -5/2. Řešení systému lineárních rovnic s horní schodovitou maticí soustavy (6.30) typu (h, n), s hodností h n. Tento systém lze rozepsat takto c1,s1 xs1 + . . . + c1,s2 xs2 + . . . + c1,sh xsh + . . . + c1,nxn = d1 c2,s2 xs2 + . . . + c2,sh xsh + . . . + c2,nxn = d2 ... ... ... (6.30) ch,sh xsh + . . . + ch,nxn = dh. V něm jsou prvky c1,s1 , c2,s2 , . . . , ch,sh různé od nuly. Při jeho řešení postupujeme takto. Všechny členy tohoto systému rovnic, které obsahují neznámé xj, kde j {{1, 2, . . . , n} -{s1, s2, . . . , sh}}, převedeme na pravou stranu systému rovnic. V dalším je budeme považovat za parametry; je jich celkem d = n-h. Obdržíme tak systém h rovnic o h neznámých xs1 , xs2 , . . . , xsh s horní regulární trojúhelníkovou maticí soustavy, jehož pravá strana závisí na d parametrech. Jeho řešením zpětnou substitucí dostaneme h složek řešení závislých na uvedených d parametrech. (Způsob řešení systému lineárních rovnic s trojúhelníkovou maticí soustavy; byla nahoře popsaná.) Řešení daného systému rovnic je pak vektor x, jehož složky jsou zavedené parametry v počtu d a vypočítané složky xs1 , xs2 , . . . , xsh . 260 Příklad 6.3. Nalezněte řešení systému lineárních rovnic x1 + 2x2 + x3 + 4x4 + x5 + 2x6 + 7x7 = 40 - 2x3 + x5 - x7 = -8 x6 - 3x7 = -15 (6.31) o neznámých xi, i = 1, 2, 3, 4, 5, 6, 7. Řešení. Maticí soustavy je horní schodovitá matice A = 1 2 1 4 1 2 7 0 0 -2 0 1 0 -1 0 0 0 0 0 1 -3 . Označme b vektor pravých stran a x vektor neznámých. Potom je b = 40 -8 -15 , x = x1 x2 x3 x4 x5 x6 x7 Zadaný systém (6.31) rovnic lze pak zapsat v maticové notaci jako A x = b. Matice soustavy i matice rozšířená mají stejnou hodnost h = 3. Má tedy systém řešení. Zadaný systém rovnic přepíšeme tak, že na pravou stranu převedeme všechny členy rovnic obsahující neznámé x2, x4, x5, x7. Dostáváme tak systém rovnic x1 + x3 + 2x6 = 40 - 2x2 - 4x4 - x5 - 7x7 - 2x3 = -8 - x5 + x7 x6 = -15 + 3x7 (6.32) Dosadíme-li za neznámé x2, x4, x5, x7 do (6.32) jakákoliv čísla, je pravou stranou takto vzniklého systému konstantní vektor a systém přechází na systém 3 rovnic o třech neznámých x1, x3, x6. Matice soustavy tohoto systému je regulární horní trojúhelníková matice řádu 3. Jeho vyřešením dostáváme hodnoty neznámých x1, x3, x6, které spolu se zvolenými hodnotami x2, x4, x5, x7 dávají řešení zadaného systému lineárních rovnic. 261 6. Metody řešení systému lineárních algebraických rovnic Na neznámé x2, x4, x5, x7 se budeme tedy dívat jako na parametry. Kvůli zvýšení přehlednosti zavedeme toto označení parametrů: x2 = c1, x4 = c2, x5 = c3, x7 = c4. (6.33) Dosazením těchto parametrů do (6.32), dostáváme x1 + x3 + 2x6 = 40 - 2c1 - 4c2 - c3 - c4 - 2x3 = -8 - c3 + c4 x6 = -15 + 3c4 (6.34) Z poslední rovnice vypočítáme x6. Dostáváme x6 = -15 + 3c4. Do druhé rovnice dosadíme vypočítanou hodnotu x6 a vypočítáme x3. (Dosazení za x6 se neprojeví, neboť koeficient u x6 je v této rovnici roven 0.) Dostáváme x3 = 4 + 1/2c3 - 1/2c4. Dosadíme tyto vypočítané hodnoty za x3, x6 do první rovnice systému (6.34) a vypočítáme x1. Dostáváme x1 = 66 - 2c1 + 4c2 + 1/2c3 - 25/2c4. Všechna řešení zadaného systému rovnic (6.32) lze zapsat takto x = 66 - 2c1 + 4c2 + 1/2c3 - 25/2c4 c1 4 + 1/2c3 - 1/2c4 c2 c3 -15 + 3c4 c4 , kde c1, c2, c3, c4 R jsou parametry. Toto řešení lze zapsat takto x = 66 0 4 0 0 -15 0 Partikulární řešení systému Ax = b + c1 -2 1 0 0 0 0 0 + c2 4 0 0 1 0 0 0 + c3 1/2 0 1/2 0 1 0 0 + c4 -25/2 0 -1/2 0 0 3 1 Obecné řešení homogenního systému Ax = 0 . 262 Poznámka 1. Množinu všech řešení systému lineárních rovnic A x = b nazýváme obecným řešením. Lze ukázat, že toto obecné řešení je součtem obecného řešení příslušného homogenního systému rovnic A x = 0 a partikulárního, to jest libovolně zvoleného jednoho řešení systému rovnic A x = b, b = 0. Poznámka 2. V našem případě obdržené obecné řešení závisí na 4 parametrech. Znamená to, že každou volbou parametrů dostáváme řešení uvedeného systému lineárních rovnic a naopak, každé řešení daného systému rovnic dostaneme speciální volbou parametrů. V tomto obecném řešení je vektor x = 66 0 4 0 0 -15 0 jedním z řešení daného systému rovnic. Nazýváme je partikulárním řešením. Množina řešení c1 -2 1 0 0 0 0 0 + c2 4 0 0 1 0 0 0 + c3 1/2 0 1/2 0 1 0 0 + c4 -25/2 0 -1/2 0 0 3 1 , kde c1, c2, c3, c4 R jsou parametry, je obecným řešením systému A x = 0, který se nazývá homogenním systémem rovnic, příslušným k danému systému rovnic A x = b. Poznámka 3. Vyjádření obecného řešení systému rovnic není jednoznačné (každé vyjádření ovšem obsahuje tatáž řešení), dá se vyjádřit v různých tva- rech. Dosavadní úvahy shrneme v následující větě. 263 6. Metody řešení systému lineárních algebraických rovnic Věta 6.3. (Frobeniova věta.) Nechť A x = b (6.35) je systém m lineárních rovnic o n neznámých. Potom platí: Jestliže matice soustavy A má menší hodnost než matice rozšířená (A|b), potom systém rovnic (6.35) nemá řešení. Jestliže matice soustavy A má stejnou hodnost jako matice rozšířená (A|b), potom systém rovnic (6.35) má řešení. Jestliže tato společná hodnost je rovna počtu neznámých n, potom má právě jedno řešení. Jestliže tato společná hodnost je h < n, potom má nekonečně mnoho řešení, závislých na n - h parametrech. Uveďme ukázky řešení několika úloh, v nichž matice soustavy není schodo- vitá. Příklad 6.4. Řešte systém lineárních rovnic x1 + 2x2 - 3x3 + x4 = 1, 2x1 - x2 + x3 - x4 = 1, 4x1 + 3x2 - 5x3 + x4 = 3. (6.36) Řešení. K danému systému rovnic napíšeme odpovídající rozšířenou matici soustavy (A|b) = 1 2 -3 1 1 2 -1 1 -1 1 4 3 -5 1 3 . (6.37) Tuto matici transformujeme elementárními transformacemi na horní schodovitou matici. První řádek násobíme číslem (-2) a přičteme ke druhému řádku. Dostaneme (A|b) 1 2 -3 1 1 0 -5 7 -3 -1 4 3 -5 1 3 . První řádek násobíme (-4) a připočteme ke čtvrtému řádku. Dostaneme (A|b) 1 2 -3 1 1 0 -5 7 -3 -1 0 -5 7 -3 -1 . Druhý řádek násobíme číslem (-1) a připočteme ke třetímu řádku. Dostaneme horní schodovitou matici (A|b) 1 2 -3 1 1 0 -5 7 -3 -1 0 0 0 0 0 . 264 V této matici vypustíme řádek obsahující samé 0. Dostáváme tak matici, označme ji (B|c), která odpovídá systému (6.38) Bx = c, který je ekvivalentní s daným systémem rovnic (6.36). x1 + 2x2 - 3x3 + x4 = 1 - 5x2 + 7x3 - 3x4 = -1 (6.38) Členy těchto rovnic obsahující neznámé x3, x4 převedeme na pravou stranu systému. Budeme je považovat za parametry. Zároveň položíme c1 = x3, c2 = x4. Dostáváme x1 + 2x2 = 1 + 3c1 - c2, - 5x2 = -1 - 7c1 + 3c2. Z poslední rovnice vypočítáme x2. Dostaneme x2 = 1/5 (1 + 7c1 - 3c2). Dosadíme tuto vypočítanou hodnotu x2 do první rovnice a vypočítáme z takto vzniklé rovnice x1. Dostaneme x1 = 1/5 (3 + c1 + c2). Obecným řešením zadaného systému lineárních rovnic (6.36) je tedy vektor x = (1/5 (3 + c1 + c2) 1/5 (1 + 7c1 - 3c2) c1 c2 , kde c1, c2 R. Toto obecné řešení lze zapsat ve tvaru x = 3/5 1/5 0 0 + c1 1/5 7/5 1 0 + c2 1/5 -3/5 0 1 , kde c1, c2 R. Příklad 6.5. Nalezněte řešení systému lineárních rovnic x1 + 2x2 - 3x3 + x4 = 1 2x1 - x2 + x3 - x4 = 1 4x1 + 3x2 - 5x3 + x4 = 4 (6.39) Řešení. K danému systému rovnic napíšeme odpovídající rozšířenou matici soustavy. (A|b) = 1 2 -3 +1 1 2 -1 1 -1 1 4 3 -5 1 4 . 265 6. Metody řešení systému lineárních algebraických rovnic Tuto matici soustavy transformujme elementárními transformacemi na horní schodovitou matici. První řádek násobíme číslem (-2) a přičteme ke druhému řádku. Dostaneme (A|b) 1 2 -3 1 1 0 -5 7 -3 -1 4 3 -5 1 4 . První řádek násobíme (-4) a připočteme k třetímu řádku. Dostaneme (A|b) 1 2 -3 1 1 0 -5 7 -3 -1 0 -5 7 -3 0 . Druhý řádek násobíme číslem (-1) a připočteme ke třetímu řádku. Dostaneme horní schodovitou matici (A|b) 1 2 -3 1 1 0 -5 7 -3 -1 0 0 0 0 1 . První čtyři sloupce představují matici, kterou jsme obdrželi elementárními transformacemi matice soustavy daného systému rovnic. Tato matice má hodnost 2. Celá matice představuje matici, která vznikla elementárními transformacemi rozšířené matice soustavy daného systému rovnic. Má hodnost 3. To znamená, že matice soustavy daného systému rovnic má hodnost 2 a matice rozšířená daného systému rovnic má hodnost 3, tedy odlišnou od hodnosti matice soustavy. Daný systém rovnic tedy nemá řešení. Neexistence řešení daného systému rovnic vyplývá i z této úvahy. Tato výsledná matice reprezentuje systém lineárních rovnic x1 + 2x2 - 3x3 + x4 = 1, - 5x2 + 7x3 - 3x4 = -1, 0 x1 + 0 x2 + 0 x3 + 0 x4 = 1. (6.40) Vzhledem k poslední rovnici je patrno, že systém nemá řešení. Gaussova eleminační metoda. V následujícím výkladu nejde o nic nového. Jde o zavedení názvu pro metodu, o které jsme již obecněji pojednali. Speciální případ uvádíme proto, že se s tímto názvem můžete setkat. Nechť A je regulární čtvercová matice řádu n, b je n­rozměrný sloupcový vektor a x je neznámý n­rozměrný sloupcový vektor. Uvažujme systém n lineárních rovnic Ax = b. (6.41) Tento systém rovnic (6.41) řešme takto: 266 1. Matici (A|b) transformujeme elementárními transformacemi na matici (T |c), (6.42) kde T je horní trojúhelníková matice. (Je to schodovitá matice.) 2. Řešíme obdržený systém rovnic T x = c s horní trojúhelníkovou maticí metodou zpětné substituce. Tento způsob výpočtu se nazývá Gaussova eleminační metoda. Tato metoda má mnoho variant, spočívajících jak ve výběru hlavních řádků (při transformaci rozšířené matice soustavy na horní schodovitou matici), tak i při provádění jednotlivých kroků v elementárních transformacích, jimiž se systém rovnic (6.41) převádí na systém rovnic (6.42). Příklad 6.6. Gaussovou eliminační metodou řešte systém lineárních rovnic Ax = b, kde A = 1 -3 2 0 5 -2 -2 4 1 , b = 1 4 9 . K systému rovnic přiřadíme rozšířenou matici soustavy (A|b) = 1 -3 2 1 0 5 -2 4 -2 4 1 9 . Tuto matici převedeme elementárními transformacemi na matici (B|c), kde matice B je horní trojúhelníková matice. Postupně dostáváme (A|b) = 1 -3 2 1 0 5 -2 4 -2 4 1 9 1 -3 2 1 0 5 -2 4 0 -2 5 11 1 -3 2 1 0 5 -2 4 0 0 21 63 . Poslední matici odpovídá systém lineárních rovnic x1 -3x2 +2x3 = 1, 5x2 -2x3 = 4, 21x3 = 63. Tento systém řešíme metodou zpětné substituce. Z poslední rovnice vypočítáme x3. Dostáváme x3 = 3. Dosadíme-li tuto hodnotu do druhé rovnice a vypočítáme x2, dostáváme x2 = 2. Dosadíme-li nyní do první rovnice 267 6. Metody řešení systému lineárních algebraických rovnic vypočítané hodnoty x3, x2, dostáváme z ní x1 = 1. Je tedy hledaným řešením vektor x = 1 2 3 . Jordanova eliminační metoda. V následujícím výkladu pojednáme o metodě založené na speciálně cílenou elementární tranformaci rozšířené matice soustavy. (Popis algoritmu je na str. 270.) Nechť A je regulární čtvercová matice řádu n, b je n­rozměrný sloupcový vektor a x je neznámý n­rozměrný sloupcový vektor. Uvažujme systém lineárních rovnic Ax = b. (6.43) Systém rovnic (6.43) řešme takto: 1. Matici (A|b) transformujeme elementárními trasformacemi na matici (C|d), kde C je regulární diagonální matice řádu n. 2. Řešíme systém rovnic s diagonální maticí Cx = d. (6.44) Tento způsob výpočtu se nazývá Jordanova eleminační metoda. Tato metoda má mnoho variant, spočívajících jak ve výběru hlavních řádků tak i při provádění jednotlivých kroků v elementárních transformacích, jimiž se systém rovnic (6.41) převádí na systém rovnic (6.44). Příklad 6.7. Jordanovou eliminační metodou řešte systém lineárních rovnic Ax = b, kde A = 1 -3 2 0 5 -2 -2 4 1 , b = 1 4 9 . K systému rovnic přiřadíme rozšířenou matici soustavy (A|b) = 1 -3 2 1 0 5 -2 4 -2 4 1 9 . Tuto matici převedeme elementárními transformacemi na matici (C|d), 268 kde matice C je diagonální matice, (to lze, jestliže matice A je regulární). Postupně dostáváme (A|b) = 1 -3 2 1 0 5 -2 4 -2 4 1 9 1 -3 2 1 0 5 -2 4 0 -2 5 11 1 -3 2 1 0 5 -2 4 0 0 21 63 5 0 4 17 0 5 -2 4 0 0 21 63 105 0 0 105 0 105 0 210 0 0 21 63 . Poslední matici odpovídá systém rovnic 105x1 = 105, 105x2 = 210, 21x3 = 63. Jeho řešením dostáváme hledaný vektor x = 1 2 3 . Jordanova metoda na řešení maticové rovnice A X = B Uvažujme systém rovnic A X = B, (6.45) kde A je daná regulární matice řádu n, B je daná matice typu (n, m) a X je neznámá matice typu (n, m). Každý sloupec X(:, j), j = 1, . . . , m, matice X je řešením systému rovnic AX(:, j) = B(:, j), j = 1, . . . , m. (6.46) Máme tedy řešit m systémů rovnic (6.46) se stejnou maticí soustavy A. Tyto systémy můžeme řešit najednou. K systému rovnic (6.45) přiřaďme matici rozšířenou F = (A | B). (6.47) Užitím elementárních transformací převedeme matici F na tvar F = (D | C), (6.48) kde D je diagonální matice. Položme G := D-1 F . Matice G má tedy tvar G = (E | R). 269 6. Metody řešení systému lineárních algebraických rovnic Tato matice odpovídá systému rovnic E X = R, (6.49) který je ekvivalentní se systémem (6.45). Poněvadž E . X = X, dostáváme ze systému (6.49) X = R, (6.50) takže matice R je řešením systému (6.45). Výpočet inverzní matice k regulární matici řádu n V podkapitole 5.4 jsme ukázali, že v případě, že matice A je regulární, potom inverzní matici, označme ji X, nalezneme řešením systému rovnic A X = E. Jde tedy o řešení systému, který je speciálním případem systému rovnic (6.45). Převod matice F elementárními transformacemi na matici G. Algoritmus. Předpokládejme, že proměnné F je přiřazena matice (A | B) a proměnné n je přiřazen řád matice A a proměnné m je přiřazen počet sloupců matice B. Začátek B1 Začneme s úpravou prvního sloupce matice F . Položíme j := 1. B2 Zvolme p {j, j + 1, . . . , n}, pro něž je fp,j = 0. (Takové p existuje vzhledem k regulárnosti matice A.) Touto volbou zvolíme p-tý řádek matice F jako hlavní pro následné eliminace. Jestliže p = j, je j-tý řádek hlavní a jdeme k B3. Jestliže p = j, vyměníme navzájem p-tý a j-tý řádek matice F a jdeme k B3. B3 Pro i = 1, . . . , n, i = j, provedeme tyto úkony b1 Položme i := 1, jdeme k b2. b2 Jestliže i = j jdeme k b4, jinak k b3. b3 Je-li fi,j = 0, jdeme k b4, jinak položíme F = H4(j, -fi,j/fj,j, i, 1)F . (Po této transformací bude fi,j = 0.) Jdeme k b4. b4 položme i := i + 1. Je-li i n jdeme k bodu b2, jinak jdeme k bodu B4. 270 B4 Položme j := j + 1. Jestliže j n, jdeme k B2. Jinak jdeme k bodu B5. B5 Původní matice F se transformovala na matici F = (D | C) kde matice D je diagonální. Potom hledaná matice G je G := D-1 F = (E|R). Příklad 6.8. Nalezněte inverzní matici k matici A = 1 2 4 -2 1 2 4 3 5 . (6.51) Řešení. Označme X matici inverzní k matici A. Předpokládáme-li, že matice A je regulární, je hledaná matice X řešením systému lineárních rovnic A X = E. Této rovnici odpovídá matice F = (A|E), to jest matice F = 1 2 4 1 0 0 -2 1 2 0 1 0 4 3 5 0 0 1 . (6.52) Na matici F budeme postupně aplikovat elementární tranasformace podle nahoře popsaného algoritmu. Položme j := 1. Začneme s úpravami prvního sloupce matice F . Za hlavní řádek zvolíme řádek 1.(Prvek f1,1 = 0.) Elementárními transformacemi typu H4 dosáhneme toho, aby ve vzniklé matici byly prvky f2,1, f3,1 rovny nule. Provedením transformace F := H4(1, -f2,1/f1,1, 2, 1)F , to jest transformací F := H4(1, 2, 2, 1)F dostáváme F = 1 2 4 1 0 0 0 5 10 2 1 0 4 3 5 0 0 1 . Provedením transformace F := H4(1, -f3,1/f1,1, 3, 1)F to jest provedením transformace F := H4(1, -4, 3, 1)F dostáváme F := 1 2 4 1 0 0 0 5 10 2 1 0 0 -5 -11 -4 0 1 . Položme j := 2. Začneme s úpravami druhého sloupce matice F . 271 6. Metody řešení systému lineárních algebraických rovnic Za hlavní řádek zvolíme řádek 2.(Prvek f2,2 = 0.) Elementárními transformacemi typu H4 dosáhneme toho, aby ve vzniklé matici byly prvky f1,2, f3,2 rovny nule. Provedením transformace F := H4(2, -f1,2/f2,2, 1, 1)F , to jest provedením transformace F := H4(2, -2/5, 1, 1)F dostáváme F := 1 0 0 1/5 -2/5 0 0 5 10 2 1 0 0 -5 -11 -4 0 1 Provedením transformace F := H4(2, -f3,2/f2,2, 3, 1)F , to jest provedením transformace F := H4(2, 5/5, 3, 1)F , dostáváme 1 0 0 1/5 -2/5 0 0 5 10 2 1 0 0 0 -1 -2 1 1 Položme j := 3. Začneme s úpravami třetího sloupce matice F . Za hlavní řádek zvolíme řádek 3.(Prvek f3,3 = 0.) Poněvadž f1,3 = 0, provedeme jenom takovou elementární transformaci typu H4, aby ve vzniklé matici byl prvek f2,3 roven nule. Provedením transformace F := H4(3, -f2,3/f3,3, 2, 1)F , to jest transformací F := H4(3, 10, 2, 1)F dostáváme F := 1 0 0 1/5 -2/5 0 0 5 0 -18 11 10 0 0 -1 -2 1 1 . Označme obdrženou matici F jako F = (D | C). Je tedy D = 1 0 0 0 5 0 0 0 -1 . K ní inverzní maticí je matice D-1 = 1 0 0 0 1/5 0 0 0 -1 . Položme G := D-1 F . Dostáváme G = 1 0 0 1/5 -2/5 0 0 1 0 -18 5 11 5 2 0 0 1 2 -1 -1 . 272 Matici G lze zapsat jako G = (E | R). Této maticí odpovídá systém rovnic E X = R ekvivalentní s daným systémem rovnic A X = E. Je tedy hledanou inverzní maticí matice X = R = 1/5 -2/5 0 -18 5 11 5 2 2 -1 -1 . Studovat informativně6.2 Metody řešení systému lineárních rovnic užitím rozkladu matice soustavy, qr­rozklad Zabývejme se opět řešením systému m lineárních rovnic o n neznámých Ax = b, (6.53) kde A je matice soustavy typu (m, n), b je vektor pravých stran typu (m, 1) a x je vektor neznámých typu (n, 1). Předpokládejme, že matice A se dá napsat jako součin dvou matic U, V , to jest, že A = U V . Potom vyšetřovaný systém rovnic se dá napsat ve tvaru (UV )x = b, (6.54) nebo po úpravě U(V x) = b. Zaveďme si pomocný vektor u vztahem u = V x. Z (6.54) vyplývá, že pro něj platí vztah Uu = b. (6.55) Jestliže u je řešením tohoto systému, potom hledaný vektor x je řešením systému rovnic V x = u. (6.56) Řešení systému rovnic (6.53) je tak převedeno na řešení dvou systémů rovnic (6.55), (6.56). Tento způsob je vhodný jen v tom případě, že oba systémy rovnic (6.55), (6.56) lze snadno řešit, resp. že tento rozklad má nějaké další výhody. Je známá celá řada užitečných rozkladů matic. Zavedeme si nyní pojem ortogonální matice a ukážeme si některé její vlastnosti. Dále si uvedeme tak zvaný qr­rozklad matice A, v němž jednou maticí je matice ortogonální. Definice 6.1. Čtvercovou matici Q řádu n nazýváme ortogonální, jestliže QT Q = E. (6.57) Poznámka 1. Z definice inverzní matice a ze vztahu (6.57) vyplývá, že matice QT je inverzní k matici Q. 273 6. Metody řešení systému lineárních algebraických rovnic Poznámka 2. Nechť U, V jsou ortogonální matice téhož řádu. Potom i U V je ortogonální matice. Skutečně, (U V )T (U V ) = (V T UT ) (U V ) = V T E V = V T V = E. Odvození qr­rozkladu matice. Ukažme si nyní podstatu qr­rozkladu matice A. Uvažujme matici A typu (m, n), m n. Nechť i, j jsou takové indexy, že 1 i m, 1 j n, i < j. Označme nyní i,j Q čtvercovou matici řádu m, která se od jednotkové matice liší jen v prvcích qii, qij, qji, qjj, které jsou definovány vztahy qi,i = cos(), qj,j = cos(), qi,j = sin(), qj,i = - sin() Je tedy i,j Q() = 1 . . . 0 ...i-týsloupec 0 0 . . . 0 ...j-týsloupec 0 0 . . . 0 ... ... ... ... ... ... ... ... ... 0 1 0 0 . . . 0 0 0 0 0 . . . 0 cos() 0 0 sin() 0 . . . 0 i-tý řádek 0 . . . 0 0 1 0 0 0 . . . 0 ... ... ... ... ... ... ... ... ... 0 0 0 0 1 0 0 . . . 0 0 . . . 0 - sin() 0 0 cos() 0 . . . 0 j-tý řádek 0 . . . 0 0 0 0 0 1 . . . 0 ... ... ... ... ... ... ... ... ... 0 . . . 0 0 0 0 0 0 . . . 1 . (6.58) Výpočtem zjistíme, že i,j QT i,j Q = E, takže matice i,j Q je ortogonální. Jednotková matice E řádu m je jejím zvláštním případem pro = 0. Uvažujme nyní m­rozměrný sloupcový vektor c. Nechť cj = 0. Označme d = i,j Qc. Potom di = cos()ci + sin()cj, (6.59) dj = - sin()ci + cos()cj, (6.60) dk = ck, k = 1, 2, . . . , m, k = i, k = j. (6.61) Určeme nyní úhel tak, aby dj = 0. Řešme proto systém rovnic - sin()ci + cos()cj = 0, sin2 () + cos2 () = 1. Úhel nepotřebujeme znát explicitně, stačí znát sin(), cos(). Výpočtem dostáváme cos() = ci , sin() = cj , kde = c2 i + c2 j . Je-li cj = 0, položme i,j Q := E. Označme d = i,j Q c. Potom dj = cj pro všechna j = 1, 2, . . . , m. Zejména dj = 0. Je tedy v obou případech j­tá složka vektoru i,j Q c rovna nule. Vektor i,j Q c se liší od vektoru c nejvýše v i­té a v j­té složce. Uvažujme nyní matici A typu (m, n). Pro každé dva indexy, i = 1, 2, . . . , n, j = i+1, . . . , m definujme matici i,j Q(), takto: Je-li aj,i = 0, položme i,j Q() = E. Je-li aj,i = 0, položme i,j Q() rovno matici určené vztahem (6.58), kde cos() = ai,i , sin() = aj,i , = a2 i,i + a2 j,i. 274 Potom v matici A := i,j Q()A bude aj,i = 0. V matici A se změnily pouze prvky v jejím i­tém a v j­tém řádku. Položme nyní A := 1,2 Q A. V prvním sloupci nově vzniklé matice A je a21 = 0. Položme nyní A := 1,3 Q A. V prvním sloupci nově vzniklé matice A je a3,1 = 0 a prvek a2,1 se nezmění, to jest je a2,1 = 0. Položme nyní A := 1,4 Q A. V prvním sloupci nově vzniklé matice A je a4,1 = 0 a prvky a2,1, a3,1 se nezmění, to jest je a2,1 = 0, a3,1 = 0. Tímto způsobem dále pokračujeme, až položíme A := 1,m Q A. V takto vzniklé matice A jsou všechny prvky v prvním sloupci, počínaje druhým prvkem, rovny 0. Prvek a1,1 = 0 v případě, že první sloupec původní matice A byl nenulový. (Viz poznámka 3.) Matici A dále analogicky postupně násobme maticemi 2,3 Q, . . . , 2,m Q, . . . , n,n+1 Q, . . . , n,m Q. (6.62) Vznikne tak matice T O kde T je horní trojúhelníková matice typu (n, n) a O je nulová matice typu (m - n, n). Položme QT = 1,2 Q 1,3 Q . . . 1,m Q 2,3 Q . . . 2,m Q . . . n,n+1 Q . . . n,m Q. Potom matici A lze psát ve tvaru A = Q T O . Poněvadž součin dvou ortogonálních matic je opět matice ortogonální, je matice Q ortogonální, takže lze na základě nahoře uvedeného výpočtového postupu vyslovit následující větu. Věta 6.4. Nechť A je matice typu (m, n), kde m n. Potom existuje taková ortogonální matice Q řádu m, že A = Q T O , (6.63) kde T je horní trojúhelníková matice řádu n a O je nulová matice typu (m-n, n). Budeme říkat, že (6.63) je qr­rozkladem matice A. Poznámka 3. Některé prvky na diagonále matice T mohou být nulové. Jestliže matice A je typu (m, n), kde m > n a hodnost matice A je rovna n, potom matice T je regulární. Ukážeme použití qr­rozkladu matice A ve dvou případech. Úloha. Užitím qr­rozkladu matice A popište postup při řešení následujícího systému m lineárních rovnic o n neznámých. Ax = b, (6.64) kde A je matice typu (m, n), b je m­rozměrný sloupcový vektor a x je neznámý nrozměrný vektor. 275 6. Metody řešení systému lineárních algebraických rovnic Postup výpočtu. Aplikujeme-li na matici A větu 6.4 o qr­rozkladu, lze systém rovnic (6.64) zapsat ve tvaru Q T O x = b, (6.65) kde T je horní trojúhelníková matice řádu n. Násobíme-li rovnici (6.65) maticí QT zleva, dostáváme s ohledem na vztah QT Q = E systém rovnic T O x = QT b, (6.66) Položíme-li b = QT b, lze systém (6.66) zapsat takto T O x = b. (6.67) což je systém lineárních rovnic ekvivalentní se zadaným systémem rovnic. (Násobení maticí QT zleva představuje provedení elementární transformace.) U vzniklého systému rovnic lze lehce stanovit, zda má řešení nebo ne. Je-li např. matice A regulární čtvercová matice řádu n, je systém (6.66) tvaru T x = QT b (6.68) s regulární horní trojúhelníkovou maticí T , jehož řešení (zpětnou substitucí) jsme již dříve popsali. Jako příklad si uveďme následující úlohu, v níž předpokládáme, že rozklad matice A jsme získali na počítači. Příklad 6.9. Nalezněte řešení systému lineárních rovnic Ax = b, (6.69) kde A = 4 1 2 2 5 1 2 3 6 , b = 12 15 26 . (6.70) Řešení. Na počítači jsme získali qr­rozklad matice A. Dostali jsme A = QT , kde Q = -0,8164965809 0,5449492609 -0,1906925178 -0,4082482904 -0,7784989441 -0,4767312946 -0,4082482904 -0,3113995776 0,8581163303 , T = -4,8989794855 -4,0824829046 -4,4907311951 0,0000000000 -4,2817441928 -1,5569978883 0,0000000000 0,0000000000 4,2905816516 . Položíme-li v (6.69) A = QR a vynásobíme-li takto vzniklou rovnici maticí QT zleva, dostáváme systém rovnic T x = c, (6.71) kde c = QT b. Výpočtem dostáváme -4,8989794855 -4,0824829046 -4,4907311951 0,0000000000 -4,2817441928 -1,5569978883 0,0000000000 0, 4,2905816516 x1 x2 x3 = = -26,5361388801510928 -13,2344820507458874 12,8717449548154974 . (6.72) 276 Jeho řešením obdržíme x1 = 1, x2 = 2, x3 = 3. 6.3 Řešení systému lineárních rovnic metodou nejmenších čtverců Aproxinace funkce. Často se setkáváme s potřebou nalezení, resp. verifikací, vzájemných vztahů mezi různými veličinami. Je tomu jak v ekonomii, tak i v řadě jiných disciplín. Ke konkrétním studiím jsou k tomu využívaná většinou reálná data. Při tom se setkáváme s důležitým pojmem modelu. Model je zjednodušeným zobrazením skutečnosti. Objektivní realitu, kterou zobrazujeme, nazýváme předmětem modelování. Modelem bývají zachyceny většinou jenom určité vlastnosti. Je tomu tak buď proto, že jiné vlastnosti nejsou předmětem zkoumání, anebo že je neznáme. V modelu musí být zobrazeny všechny vlastnosti jevu důležité z hlediska účelu modelu. V této části výkladu se budeme zabývat modelováním nějaké závislosti. Předpokládejme, že tato závislost je tvaru y = f(x), pro x a, b , (6.73) kde funkci f(x) sice neznáme, ale nějakým rozumným způsobem jsme zjistili přibližně několik, řekněme m bodů, této funkce [xi, yi], i = 1, 2, . . . , m. Budeme předpokládat, že hodnoty xi jsou přesné a yi jsou přibližné hodnoty této funkce v bodech xi. Předpokládá se, že chyba f(xi)-yi, i = 1, . . . , n, má nějaké předpokládané pravděpodobnostní rozložení1 . Zde si ukážeme jednu metodu, jak lze neznámou funkci f(x) aproximovat (přibližně nahradit) za jistých předpokladů funkcí, označme ji f(x), ze třídy F funkcí ve tvaru g(x, p1, . . . , pn) = p1 1(x) + p2 2(x) + . . . + pn n(x), (6.74) kde 1(x), . . . , n(x) jsou známé funkce a p1, . . . , pn jsou neznámé parame- try. Samozřejmě je nutno prověřit, zda použití aproximace hledané závislosti funkcí ze zvolené třídy F je v řešené úloze oprávněno. K tomu slouží aparát statistiky. Budeme se tedy snažit určit takové parametry p1, . . . , pn, aby pro funkci g(xi, p1, p2, ..., pn) F s těmito parametry platilo (alespoň přibližně) g(xi, p1, p2, ..., pn) = yi, i = 1, 2, . . . , n. (6.75) Vztah (6.75) představuje m rovnic o n neznámých. Tento vztah lze přepsat na tvar 1(x1)p1 + 2(x1)p2 + + n(x1) = y1 1(x2)p1 + 2(x2)p2 + + n(x2) = y2 ... ... ... 1(xm)p1 + 2(xm)p2 + + n(xm) = ym (6.76) 1 Tento pojem Vám bude zaveden ve statistice. 277 6. Metody řešení systému lineárních algebraických rovnic Označme A matici A = 1(x1) 2(x1) n(x1) 1(x2) 2(x2) n(x2) ... ... 1(xm) 2(xm) n(xm) . (6.77) Dále označme y vektor pravých stran (to jest y-ových souřadnic daných bodů) a p vektor parametrů (které chceme určit). Tedy y = y1 y2 ... ym, , p = p1 p2 ... pn . (6.78) Systém rovnic (6.76) lze v maticové notaci zapsat takto A p = y. (6.79) Matice A závisí na volbě třídy F. Je typu (m, n). V praktických úlohách bývá m > n. To znamená, že podmínek pro parametry je více než je počet parametrů. Z předcházejícího výkladu je známo, že tento systém má řešení, když a jenom když matice soustavy A a matice rozšířená (A|y) mají stejnou hodnost. Kdyby tento systém měl řešení, to jest, kdyby existoval vektor, označme jej ^p, který by vyhovoval systému rovnic (6.79), procházela by funkce y = ^p1 1(x) + . . . + ^pn n(x) (z prostoru F) uvažovanými body [xi, yi]. (O takto vytvořené funkci se říká, že dané body interpoluje.) Tuto funkci bychom mohli považovat za aproximaci hledané funkce. Avšak většinou v praktických úlohách nemá systém rovnic (6.79) pro m > n řešení. V tomto případě je na místě hledat takovou funkci z prostoru funkcí F, která sice danými body neprochází, ale je od nich " málo" vzdálená. Slovo " málo" je nutno precizovat. Na obr. 6.1 je znázorněn graf jedné zvolené funkce y = g(x, p1, p2, ..., pn) z prostoru F a dva zadané body, označené [xi, yi], [xj, yj]. Požadavek, že tato funkce je pro nějaké parametry " málo" vzdálená od těchto bodů [xi, yi], [xj, yj] budeme chápat tak, že absolutní hodnoty čísel ri = g(xi, p1, p2, ..., pn) - yi, rj = g(xj, p1, p2, ..., pn) - yj jsou malé. Veličinu rk pro nějaké k lze chápat tak, že její absolutní hodnota |rk| je vzdálenost bodu [xk, yk] od funkce g ve směru osy y. Je-li tento bod pod grafem funkce, je rk < 0, je-li tento bod nad grafem funkce, je rk > 0. 278 Na obr. 6.1 je patrný význam čísel ri, rj. K posouzení blízkosti všech bodů [xi, yi], i = 1, 2, . . . , m, k funkci g pro nějaké parametry p použijeme např. hodnotu S(p1, . . . , pn) = m i=1 (g(xi, p1, p2, ..., pn) - yi )2 , (6.80) to jest hodnotu S(p1, . . . , pn) = m i=1 r2 i . (6.81) Pravá strana rovnice (6.81) je kvadrát euklidovské normy vektoru r, to jest ||r||2 2. Místo této normy bychom mohli použít jinou vektorovou normu. O x y ri rj yi yj xi xj g(x, p1, . . . , pn) Obrázek 6.1: Výklad k metodě nejmenších čtverců. Poznamenejme, že kdybychom ve vzorci (6.80) použili místo r2 i = (g(xi, p1, p2, ..., pn) - yi )2 pouze ri = (g(xi, p1, p2, ..., pn) - yi ), mohl by být součet reziduí ri malý, dokonce i nulový, i když by absolutní hodnoty čísel ri byly velké. Některé z těchto hodnot mohou být totiž kladné a jiné záporné. K aproximaci funkce f použijeme tu funkci g(x, p1, . . . , pn) z třídy funkcí F, jejíž parametry p1, . . . , pn minimalizují S(p1, . . . , pn), dané vztahem (6.80). Naši úlohu můžeme přeformulovat takto. Zaveďme si vektor r r = r1 r2 ... rn (6.82) vztahem (6.82) v závislosti na vektoru p. Nazýváme jej vektorem reziduí. Místo řešení systému (6.79) hledejme takový vektor p, pro nějž je některá norma vektoru r A p - y = r (6.83) 279 6. Metody řešení systému lineárních algebraických rovnic minimální. Zde se zmíníme pouze o hledání p, pro nějž je euklidovská norma vektoru r minimální, tedy o takovém vektoru p, pro něž je S = r2 1 + r2 2 + . . . + r2 n (6.84) minimální. Takto určený vektor p můžeme nazvat zobecněným řešením systému lineárních rovnic (6.79), to jest systému Ap = y. Budeme říkat, že vektor p je řešením systému (6.79) metodou nejmenších čtverců. 6.3.1 Řešení systému Ap = y metodou nejmenších čtverců ­ užitím systému normálních rovnic Vztah (6.84) upravme. Zřejmě rT r = r2 1 + r2 2 + . . . + r2 n. Dosadíme-li sem za r vztah (6.83), to jest r = A p - y, dostáváme rT r = (A p - y)T (A p - y). Úpravou dostáváme rT r = pT AT Ap - 2pT AT y + yT y. Hledáme tedy p, pro nějž je pT AT Ap - 2pT AT y + yT y (6.85) minimální. Poněvadž yT y je konstanta, lze ji ve vztahu (6.85) pro hledání minima vynechat. Hledáme tedy p pro nějž je S(p) = pT AT Ap - 2pT AT y (6.86) minimální. Uveďme bez důkazu větu uvádějící jeden způsob nalezení p, který minimalizuje funkci S(p). 280 Věta 6.5. Nechť A je matice typu (m, n), kde m > n, hodnosti n. Nechť y je známý vektor délky m a p je neznámý vektor délky n. Položme r = A p - y. (6.87) Potom existuje právě jeden vektor x, pro nějž je rT r minimální. Tento vektor x je řešením systému lineárních rovnic, zvaného systémem normálních rovnic, (jeho matice soustavy AT A je regulární) AT A p = AT y. (6.88) Poznámka. Regulárnost matice AT A se dá odvodit z předpokladů, uvedených ve větě, že A je typu (m, n), m > n a že hodnost matice A je rovna n. Řešení (6.88) lze pak vyjádřit ve tvaru p = (AT A)-1 AT y. Praktický výpočet podle tohoto vztahu je však nevhodný pro rozsáhlejší problémy. Jak již bylo řečeno, výpočet inverzní matice je sám o sobě velice náročný. Kromě toho se ukazuje, že řešení problému nalezení řešení systému lineárních rovnic Ap = y metodou nejmenších čtverců užitím normálního systému lineárních rovnic bývá nestabilní. Existují jiné metody na řešení, které vycházejí přímo ze systému rovnic Ap = y. Je to např. metoda založená na qr­rozkladu matice A. V některých aplikacích není splněna podmínka, že hodnost matice A je rovna n. V takovémto případě má úloha vícero řešení. Tímto případem se zde nebudeme zabývat. Příklad 6.10. Metodou nejmenších čtverců nalezněte polynom prvního stupně, to jest polynom ve tvaru y = p1x + p2, pro body zadané v následující tabulce. V jejím prvním sloupci jsou uvedeny x­ové souřadnice a ve druhém sloupci jsou uvedeny jejich y­ové souřadnice. 281 6. Metody řešení systému lineárních algebraických rovnic xi yi 1,0 3,2421 2,0 3,7471 3,0 4,0860 4,0 5,6901 5,0 6,3611 6,0 7,0972 7,0 7,9012 8,0 8,2962 9,0 9,4278 10,0 10,3011 Řešení. Poněvadž se má aproximovat neznámá funkce f polynomem prvního stupně, hledáme aproximaci neznámé funkce f funkcí ^f(x) ze třídy funkcí F tvaru p11(x) + p22(x), kde 1(x) = x, 2(x) = 1 a p1, p2 R jsou parametry, to jest tvaru p1x + p2. Podmínkou pro to, aby funkce p1x + p2 procházela zadanými body [xi, yi], je splnění systému rovnic p1xi + p2 = yi, kde i = 1, . . . , 10. Označme A matici soustavy tohoto systému rovnic, p vektor neznámých parametrů a y vektor y­ových souřadnic zadaných bodů. Potom tento systém rovnic lze zapsat ve tvaru Ap = y, (6.89) kde A = 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 , p = p1 p2 , y = 3,2421 3,7471 4,0860 5,6901 6,3611 7,0972 7,9012 8,2962 9,4278 10,3011 . (6.90) Hodnost matice A soustavy tohoto systému rovnic je rovna 2 a hodnost matice rozšířené (A|y) je rovna 3. Tento systém rovnic nemá tedy řešení. Místo něho budeme hledat takové parametry p, pro něž (Ap - y)T (Ap - y) nabývá svého minima. Jak vyplývá z věty 6.5, je hledaný vektor p řešením normálního systému lineárních rovnic AT Ap = AT y. Označme B = AT A, z = AT y. 282 Výpočtem dostáváme B = 385,0 55,0 55,0 10,0 , z = 429,6850 66,1507 . Vektor p je tedy řešením systému dvou rovnic o dvou neznámých Bp = z. Řešením dostáváme p = 0,7983 2,2247 . Hledaným polynomem je tedy funkce ^f(x) = 0,7983 x + 2,2247. Na obr. 6.2 jsou hvězdičkami znázorněny zadané body [xi, yi], i = 1, . . . , 10 a plnou čárou graf nalezeného polynomu prvního stupně, to jest odhad neznámé funkce. 1 2 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 11 Obrázek 6.2: Metoda nejmenších čtverců, příklad Studovat informativně 6.3.2 qr­metoda na řešení systému lineárních rovnic metodou nejmenších čtverců Nechť A je matice typu (m, n), kde m > n, a nechť její hodnost je h = n. Nechť b je vektor typu (m, 1) a x je neznámý vektor. Metodou nejmenších čtverců řešme systém lineárních rovnic Ax = b. (6.91) Zaveďme si vektor reziduí r vztahem Ax - b = r. (6.92) 283 6. Metody řešení systému lineárních algebraických rovnic Hledejme vektor x pro nějž je ||r||2 v (6.92) minimální, to znamená, pro něž je r2 1 + r2 2 + . . . + r2 m (6.93) minimální. Rovnici 6.92 použitím rokladu matice A podle věty (6.4) lze přepsat na tvar Q T O x - b = r. (6.94) Vynásobením této rovnice zleva maticí QT dostáváme QT Q T O x - QT b = QT r. (6.95) Označme b = QT b, r = QT r. (6.96) Poněvadž QT Q = E, lze (6.95) přepsat s ohledem na (6.96) na rovnici T O x - b = r. (6.97) Poněvadž matice Q je ortogonální matice řádu m, platí pro m­rozměrný sloupcový vektor r vztah ||r||2 = ||r||2. (6.98) Skutečně, ||r||2 = ||QT r||2 = (QT r, QT r) = (QT r)T (QT r) = = (rT Q) (QT r) = rT (QQT )r = rT r = ||r||2. Poněvadž matice Q je regulární a platí (6.98), každý vektor x, který v (6.92) minimalizuje ||r||2, minimalizuje v (6.97) ||r||2 a naopak, každý vektor x, který v (6.97) minimalizuje ||r||2, minimalizuje ||r||2 v (6.98). Hledejme tedy takový vektor x, který minimalizuje ||r||2. Rovnici (6.97) lze rozepsat takto t1 1x1 + t1 2x2 + . . . + t1 nxn - b1 = r1, t2 2x2 + . . . + t2 nxn - b2 = r2, ... tn nxn - bn = rn, - bn+1 = rn+1, ... - bm = rm. (6.99) Z tohoto systému je patrno, že hodnoty rn+1, . . . , rm nelze změnit. Součet r2 1 + . . . + r2 n + r2 n+1 + . . . + r2 m bude minimální, jestliže v (6.99) položíme r1 = 0, . . . , rn = 0. Dostáváme t1 1x1 + t1 2x2 + . . . + t1 nxn - b1 = 0, t2 2x2 + . . . + t2 nxn - b2 = 0, ... tn nxn - bn = 0. (6.100) 284 Je to systém s regulární horní trojúhelníkovou maticí. Lze jej řešit dříve popsanou metodou zpětné substituce. Poznámka. Kdyby hodnost matice A byla menší než n, trojúhelníková matice T by nebyla regulární, takže systém (6.100) by měl více řešení. Norma vektoru reziduí by byla pro všechna řešení stejná. Jako příklad budeme řešit stejnou úlohu, jako jsme již řešili pomocí systému normálních rovnic. Příklad 6.11. Metodou nejmenších čtverců nalezněte polynom prvního stupně, to jest polynom ve tvaru y = p1x + p2, pro body zadané v následující tabulce. V jejím prvním sloupci jsou uvedeny x­ové souřadnice a ve druhém sloupci jsou uvedeny jejich y­ové souřadnice. xi yi 1,0 3,2421 2,0 3,7471 3,0 4,0860 4,0 5,6901 5,0 6,3611 6,0 7,0972 7,0 7,9012 8,0 8,2962 9,0 9,4278 10,0 10,3011 Řešení. Poněvadž se má aproximovat neznámá funkce f polynomem prvního stupně, hledáme aproximaci neznámé funkce f funkcí f(x) ze třídy funkcí F tvaru p11(x) + p22(x), kde 1(x) = x, 2(x) = 1 a p1, p2 R jsou parametry, to jest funkcí tvaru p1x + p2. Podmínkou pro to, aby funkce p1x + p2 procházela zadanými body [xi, yi], je splnění systému rovnic p1xi + p2 = yi, kde i = 1, . . . , 10. Označme A matici soustavy tohoto systému rovnic, p vektor neznámých parametrů a y vektor y­ových souřadnic zadaných bodů. Potom tento systém rovnic lze zapsat ve tvaru Ap = y, (6.101) kde A = 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 , p = p1 p2 , y = 3,2421 3,7471 4,0860 5,6901 6,3611 7,0972 7,9012 8,2962 9,4278 10,3011 . (6.102) Hodnost matice soustavy tohoto systému rovnic je rovna 2, tedy počtu neznámých koeficientů a hodnost matice rozšířené (A|y) je rovna 3. Tento systém rovnic nemá tedy řešení v klasickém slova smyslu. Budeme jej řešit metodou nejmenších čtverců. Zaveďme si vektor reziduí r vztahem Ap - y = r. (6.103) 285 6. Metody řešení systému lineárních algebraických rovnic Hledejme vektor p pro nějž je ||r||2 v (6.103) minimální, to znamená, pro nějž je r2 1 + r2 2 + . . . + r2 m (6.104) minimální. Rovnici (6.103) použitím rokladu matice A podle věty 6.4 lze přepsat na tvar Q T O p - y = r. (6.105) Vynásobíme tuto rovnice zleva maticí QT . Označme r = QT r. (6.106) Výpočtem na počítači dostáváme -19,6214 -2,8031 0 -1,4639 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 p1 p2 - -21,8987 -3,2563 -0,5449 0,2419 0,0956 0,0144 0,0011 -0,4212 -0,1069 -0,0509 = r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 (6.107) V tomto systému rovnic určíme ri, i = 1, 2, . . . , 10 tak, aby součet jejich kvadrátů byl minimální. Hodnoty ri, i = 3, 4, . . . , 10 nemůžeme nijak ovlivnit, jejich hodnoty jsou jednoznačně určeny rovnicemi 3--10 systému rovnic (6.107). Můžeme však zvolit r1 = 0, r2 = 0. Při této volbě bude ||r||2 minimální. První dvě rovnice tohoto systému jsou pak -19,6214 -2,8031 0 -1,4639 p1 p2 - -21,8987 -3,2563 = 0 0 . Řešením pak dostaneme p1 = 0,7983, p2 = 2,2244. Hledaným polynomem je tedy funkce f(x) = 0,7983x + 2,2247. Vidíme, že výsledky obdržené oběma metodami se od sebe liší velice málo. Vyžaduje se orientační znalost 6.4 Vlastní čísla matice Při řešení řady úloh lineární algebry se pracuje s pojmem vlastního čísla a s pojmem vlastního vektoru čtvercové matice. I když mají tyto pojmy základní význam v lineární algebře, my se zde s ním nebudeme zabývat do hloubky. Cílem tohoto odstavce je pouze seznámit se s nimi tak, abychom je mohli použít v souvislosti s normou matice. Uvažujme čtvercovou matici A řádu n. Nechť Mn je množina všech sloupcových vektorů typu (n, 1). Jestliže ke každému x Mn přiřadíme vektor y = A x Mn , 286 je toto přiřazení zobrazením množiny Mn do sebe. Zabývejme se otázkou, zda existuje takové a k němu nenulový vektor x Mn , že A x = x. (6.108) Číslo vyhovující této podmínce se nazývá vlastním číslem matice A a vektor x, pro nějž platí A x = x, vlastním vektorem, příslušným k vlastnímu číslu . Uveďme si tento příklad. Nechť A = 1 2 2 4 , a = 1 2 . Potom Aa = 1 2 2 4 1 2 = 5 10 . Je tedy Aa = 5a. Číslo = 5 je tedy vlastním číslem matice A a vektor a = 1 2 je vlastním vektorem matice A příslušným k vlastnímu číslu = 5. Uveďme si větu pro určení vlastních čísel a vlastních vektorů matice. Věta 6.6. Nechť A je čtvercová matice řádu n. Potom rovnice det(A - E) = 0, (6.109) v níž je obecně komplexní proměnná, se nazývá charakteristickou rovnicí matice A. Číslo je vlastním číslem matice A, když a jenom když je kořenem charakteristické rovnice matice A. Každý vektor x vyhovující systému lineárních rovnic (A - E) x = 0 je pak vlastním vektorem, příslušným k vlatnímu číslu . Důkaz: Nechť A je čtvercová matice řádu n. Rovnici (6.108) lze přepsat na tvar (A - E) x = 0. (6.110) Jde o systém n lineárních rovnic o n neznámých a jednom parametru . Poněvadž vektor na pravé straně tohoto systému rovnic je nulový, má tento 287 6. Metody řešení systému lineárních algebraických rovnic systém nenulové řešení jenom tehdy, je-li determinant soustavy roven 0, to jest, je-li det(A - E) = 0. To znamená, že podmínkou existence nenulového řešení x systému (6.110) je, že číslo je kořenem charakteristické rovnice (6.109), neboli, že je vlastním číslem matice A. Ke každému charakteristickému číslu jsou odpovídající vlastní vektory řešením systému rovnic (6.110) s hodnotou rovnou tomuto vlastnímu číslu. Příklad 6.12. Nalezněte vlastní čísla a vlastní vektory matice A = 1 2 3 1 2 3 1 5 6 . Řešení. Napišme charakteristickou rovnici det(A - E) = 0. Dosasazením za A a E dostáváme det 1 - 2 3 1 2 - 3 1 5 6 - = 0. Po vyčíslení dostáváme 92 - 3 = 0. Tato charakteristická rovnice má kořeny 0, 0, 9. Tedy má dvojnásobné vlastní číslo 0 a jednoduché vlastní číslo 9. Hledejme nyní vlastní vektory. a) Pro vlastní číslo = 0 dostáváme ze vztahu (6.110) systém lineárních rovnic x1 + 2x2 +3x3 = 0, x1 + 2x2 +3x3 = 0, x1 + 5x2 +6x3 = 0. (6.111) Jeho řešením dostáváme množinu všech vlastních vektorů matice A příslušných k vlastnímu číslu = 0. Jsou to vektory c1 -1 -1 1 závislé na jednom parametrru c1. b) Pro vlastní číslo = 9 dostáváme ze vztahu (6.110) systém lineárních rovnic -8x1 + 2x2 +3x3 = 0, x1 - 7x2 +3x3 = 0, x1 + 5x2 -3x3 = 0. (6.112) 288 Jeho řešením dostáváme množinu všech vlastních vektorů příslušných k vlastnímu číslu = 9. Jsou to vektory c2 1 1 2 závislé na pametru c2. Spektrum matice Množinu všech vlastních čísel matice A budeme nazývat spektrem matice a značit (A). Zavedeme si ještě pojem spektrálního poloměru (A) čtvercové matice A jako (A) = max{|| : (A)}. Poznámka. Určení spektra matice A je pro matice vyšších řádů velice náročné. Pro výpočet vlastních čísel matic jsou vyvinuty metody, které nejsou založeny na řešení charakteristického polynomu. Spektrum hraje významnou roli v řadě aplikačních úloh. Např. pomocí spektrálního poloměru se stanoví nutné a postačující podmínky konvergence dále popsané iterační metody na řešení systému lineárních rovnic. Na základě této věty se podaří pak stanovit postačující podmímky konvergence, jejichž splnění se dá snadno ověřit. Při vyšetřování iteračních metod na řešení systému lineárních rovnic budeme potřebovat ještě pojem normy matice. 6.5 Normy matic Označme M(m,n) množinu všech matic typu (m, n), kde m, n N. Tato množina společně s dříve zavedenou operací " +" sečítání dvou matic a s ope- rací " " násobení matice číslem, tvoří lineární prostor. Budeme jej značit M(m,n) . Je tedy definicí 4.14 normy v lineárním prostoru zavedena též norma matic na prostoru M(m,n) . Uveďme si ještě jednou pojem normy speciálně pro matice. Definice 6.2. (Norma matice) Nechť M(m,n) je lineární prostor matic typu (m, n). Jestliže ke každé matici A M(m,n) přiřadíme takové nezáporné číslo, označme je ||A||, že pro A, B M(m,n) , R platí ||A|| = 0 A = 0, (6.113) ||A + B|| ||A|| + ||B|| , (6.114) 289 6. Metody řešení systému lineárních algebraických rovnic || A|| = || ||A|| pro libovolné číslo , (6.115) potom ||A|| nazýváme normou matice A v prostoru M(m,n) . V dalším si uveďme několik často používaných maticových norem. Věta 6.7. (Speciální normy matic) Ke každé matici A M(n,n) přiřaďme čísla A 1, A 2, A 3, A F takto A 1 = max k i |aik|, (6.116) A 2 = (AT A), (6.117) A F = n i=1 n k=1 |aik|2, (6.118) A 3 = max i k |aik|. (6.119) Potom A 1, A 2, A 3, A F jsou maticové normy na Mn,n . Mají tyto speciální názvy: A 1 se nazývá oktaedrickou normou, A 2 se nazývá euklidovskou normou, A 3 se nazývá max-normou, A F se nazývá Frobeniovou normou. Jestliže x Vn, potom platí tyto vztahy: Ax 1 A 1 x 1, (6.120) Ax 2 A 2 x 2, (6.121) Ax 2 A F x 2, (6.122) Ax 3 A 3 x 3. (6.123) (6.124) Mezi normami 2, F platí vztah A 2 A F . (6.125) Důkaz: Provedeme jenom částečný důkaz. 290 1. Dokažme, že 1 splňuje požadavky (6.113)­(6.115). a) Dokažme, že 1 splňuje (6.113). Nechť A Mn je taková matice, že A 1 = 0. To znamená, že max k ( i |aik|) = 0. To je možno jenom tehdy, jsou-li všechna čísla aik = 0, to jest, je-li A = 0. Platí tedy (6.113). b) Dokažme, že 1 splňuje (6.114). Nechť A, B Mn . Potom platí A + B = max k ( i |aik + bik|) max k ( i (|aik| + |bik|) max k ( i |aik|) + max k ( i |bik|) = A 1 + B 1. Platí tedy (6.114). c) Dokažme, že 1 splňuje (6.115). Nechť A Mn a nechť je reálné číslo. Potom platí A 1 = max k ( i (|aik|) || max k ( i |aik|) = || A 1. 2. Nechť x Vn, A Mn . Dokažme, že Ax 1 A 1 x 1. Platí Ax 1 = max k ( i |aikxi|) max k ( i |aik| max i |xi| = A 1 x 1. Příklad 6.13. Nechť A je matice A = 2 1 3 1 3 2 3 2 1 . Abychom určili ||A||1, vypočítejme součet absolutních hodnot prvků matice v jednotlivých jejich sloupcích. Dostáváme postupně tato čísla 6, 6, 6. Největší z nich je číslo 6, takže ||A||1 = 6. Podobně, abychom vypočítali ||A||3, vypočítáme součty absolutních hodnot prvků v jednotlivých řádcích. Dostáváme postupně čísla 6, 6, 6 Největším z nich je číslo 6, takže ||A||3 = 6. Abychom určili ||A||2, vypočítáme matici B = AT A = 14 11 11 11 14 11 11 11 14 . Charakteristická rovnice této matice det(B - E) = 0 má kořeny (jak se můžete výpočtem přesvědčit) rovny číslům 36, 3, 3. Největším z nich je číslo 36. Je tedy ||A||2 = 36 = 6. 291 6. Metody řešení systému lineárních algebraických rovnic Prostudovat informativně 6.6 Iterační metody řešení systému lineárních rovnic Předpokládejme, že A je regulární čtvercová matice řádu n a b je vektor typu (n, 1). Za uvedených předpokladů má systém Ax = b (6.126) rovnic právě jedno řešení, označme je x . Uveďme si podstatu iteračních metod k jeho přibližnému určení. Nechť x = Bx + c (6.127) je systém lineárních rovnic ekvivalentní se systémem (6.126). Poznamenejme, že vytvoření ekvivalentního systému uvedeného tvaru není jednoznačné. Zvolme libovolný sloupcový vektor 1x Vn jako počáteční aproximaci vektoru x a vytvořme posloupnost vektorů k+1 x = Bk x + c, pro k = 0, 1, 2, . . . (6.128) Ukážeme, že za jistých předpokladů o matici B tato posloupnost vektorů konverguje po složkách k vektoru x. Dříve než přikročíme k vyslovení podmínek, za nichž tato posloupnost konverguje k řešení zadaného systému rovnic, uveďme si tento příklad. Příklad 6.14. Uvažujme systém lineárních rovnic Ax = b, (6.129) kde A = 4 1 2 2 5 1 2 3 6 , b = 12 15 26 . (6.130) Lehce se přesvědčíme dosazením, že vektor x = 1 2 3 (6.131) je jeho řešením. K zadanému systému rovnic vytvořme systém rovnic k němu ekvivalentní a to tak, že z první rovnice vypočítáme x1, z druhé rovnice vypočítáme x2 a ze třetí rovnice vypočítáme x3. Dostaneme tak systém rovnic x = Bx + c, (6.132) kde B = - 0 1/4 1/2 2/5 0 1/5 1/3 1/2 0 , c = 3 3 13/3 . (6.133) Zvolme výchozí vektor 0 x = 0 0 0 292 a utvořme posloupnost vektorů k x podle rovnice k+1 x = B k x + c, pro k = 0, 1, 2, . . . . Výpočtem dostáváme posloupnost vektorů k x pro k = 0, 1, 2, . . .. Uveďme tyto z nich 9 x = 1,116568519 2,097918519 3,120979115 , 10 x = 0,9150308128 1,929176770 2,912184568 , (6.134) 19 x = 1,004765753 2,003982929 3,004930063 , 20 x = 0,9965392364 1,997107686 2,996419951 . (6.135) Tento výpočet byl proveden na počítači. Samotný výpočet se dá velice snadno naprogramovat. V iteračních metodách jsou však tyto problémy: 1. Zjistit konvergenci iteračního procesu. 2. Kolik členů posloupnosti je nutno spočítat, abychom obdrželi výsledek s potřebnou přesností. Uveďme si následující větu, která uvádí podmínky pro konvergenci iterační metody a odhad odchylky vektoru k x z iteračního výpočtu a přesného řešení. Věta 6.8. Nechť je dána soustava lineárních rovnic x = Bx + c, (6.136) kde B je čtvercová matice řádu n a c je sloupcový vektor z prostoru Vn. Označme (B) spektrální poloměr matice B a nechť (B) < 1. (6.137) Nechť 0 x je libovolný sloupcový vektor z prostoru Vn. Položme k+1 x = Bk x + c pro k = 0, 1, 2, . . . (6.138) Potom posloupnost vektorů {k x} konverguje a její limitou je přesné řešení systému (6.136), označme je x . Postačující podmínkou pro splnění (6.137) je, aby některé z čísel ||B||1, ||B||3, ||B||F bylo menší než 1. V následujících odhadech značí || ||m zvolenou maticovou normu z norem || ||1, || ||2, || ||3, || ||F splňujících podmínku ||B||m < 1 a ||||v značí tu vektorovou normu, která vzhledem ke zvolené maticové normě || ||m splňuje podmínku ||A x||v ||A||m ||x||v. Platí tyto odhady ||x - k x||v ||B||k m||0 x||v + ||B||k m (1 - ||B||m)-1 ||c||v (6.139) ||x - k x||v ||B||m(1 - ||B||m)-1 ||k x - k-1 x||v. (6.140) Důkaz: Bez důkazu. Vraťme se k řešení nahoře uvedeného příkladu iterační metodou. Poněvadž ||B||1 = 5 6 < 1, je podmínka (6.137) splněna. Tedy posloupnost vektorů {k x} k=0 konverguje k přesnému 293 6. Metody řešení systému lineárních algebraických rovnic řešení daného systému rovnic. Proveďme odhad např. vektorů 10 x, 20 x od přesného řešení x . (Jak víme, přesným řešením systému je vektor x = (1, 2, 3)T .) K odhadu použijeme oba vzorce vzorce (6.139), (6.140). K výpočtu potřebujeme znát tyto hodnoty. ||B||1 = 5 6 , ||0 x||1 = 0, ||c||1 = 13 3 , ||10 x -9 x||1 = 0,2087945473, ||20 x -19 x||1 = 0,008510111636. Dosazením do vzorců (6.139), (6.140) dostáváme následující odhady pro aproximaci ||k x - x ||1 k podle (6.139) podle (6.140) 10 4,199145155 0,6781853859 20 1,043972736 0,042550558 Vidíme, že tyto odhady jsou značně hrubé. K dosažení větší přesnosti by bylo zapotřebí provést větší počet iterací. Provedťe si tyto odhady pro jiné normy a výsledky porovnejte. 6.7 Základní poznatky z kapitoly 6 a úlohy k procvičení Vysvětlit pojem ekvivalentnosti dvou systémů lineárních rovnic. Převod systému lineárních rovnic na systém rovnic s horní schodovitou maticí. Věta Frobeniova o řešitelnosti systému lineárních rovnic a o jednoznačnosti řešení. Řešení systému lineárních rovnic převodem na systém s horní schodovitou maticí. Metoda Gaussova a metoda Jordanova. Praktické řešení. Normy matic, zaměřte se na normy || ||1, || ||F , || ||3. Popis metody nejmenších čtverců na řešení systému rovnic. Systém normálních rovnic. Orientačně se seznámit s iteračními metodami na řešení systému lineárních rovnic. V textu je pojednáno o metodě řešení systému lineárních rovnic založené na qr-rozkladu matice soustavy. Tato metoda je vysoce stabilní. Její stručný výklad v tomto textu je jen pro orientaci. Je součástí lepších programových systémů. Její znalost se při zkoušce nevyžaduje. Úlohy 1. Gaussovou a Jordanovou metodou řešte systém lineárních rovnic A x = b, kde A = 1,0 2,0 5,0 -3,0 3,0 0,0 2,0 -2 2 1 3 5 5 9 3 -1 , b = 8 1 33 28 . 294 [x = 1 2 3 4 .] 2. Napište řešení systému lineárních rovnic A x = b, kde A = 1 3 -2 0 0 -2 3 1 2 4 -1 1 , b = 14 -10 18 , kde c1, c2 R. [x = -1 - 5/2c1 - 3/2c2 5 + 3/2c1 + 1/2c2 c1 c2 .] 3. Nalezněte vlastní čísla matice A a k nim odpovídající vlastní vektory, je-li A = 1 2 2 3 . [Vlastní číslo 2 + 5, k němu přísluší vlastní vektor c1 1 1/2 + 1/2 5 , vlastní číslo 2- 5, k němu přísluší vlastní vektor c2 1 -1/2 - 1/2 5 , c1, c2 jsou parametry.] 295 6. Metody řešení systému lineárních algebraických rovnic 296