IB112 Základy matematiky Řešení soustavy lineárních rovnic, matice, vektory Jan Strejček Obsah ■ Soustava lineárních rovnic m Vektor a matice ■ násobení matic ■ maticový zápis soustavy lineárních rovnic schodovitý tvar ■ Řešení soustavy lineárních rovnic ■ Gaussova eliminace ■ Zpětná substituce ■ Geometrický význam lineárních rovnic m s dvěma neznýmými ■ s třemi neznámými IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 2/53 Soustava lineárních rovnic IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 3/53 Lineární rovnice Definice (Lineární rovnice) Lineární rovnicí o n neznámých x-\, x2,..., xn rozumíme rovnici tvaru a-, x-, + a2x2 + ... + anxn = b, kde a-\,a2,...,an jsou koeficienty a b je absolutní člen. Příklad ■ x + 3 = 2y-4 —> x-2y = -7 ■ lze chápat i jako rovnici nad 3 neznámými: x - 2y + Oz = -7 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 4/53 Soustava lineárních rovnic Definice (Soustava lineárních rovnic) Je-li dáno m rovnic o n neznámých x-|, x2,..., xn, hovoříme o soustavě lineárních rovnic nebo systému lineárních rovnic. aii*i + a12x2 + ... + a^nxn = 321*1 + 322X2 + ... + a2nXn = b2 3m1 *1 + 3m2X2 + ... + amnXn = bm Řešením soustavy rozumíme n-tici čísel (u-\, ív2, ..., un), po jejichž dosazení za proměnné (x-|, x2,..., xn) se levá strana každé rovnice vyhodnotí na odpovídající pravou stranu. IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 5/53 Motivační příklad 1 Příklad 2x -3y = 7 x +2z = 1 3x +3y +2z = 14 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 6/53 Motivační příklad 1 Příklad 2x -3y = 7 x +2z = 1 3x +3y +2z = 14 Řešení ■ Soustava má jediné řešení (5,1, -2). ■ Jinak zapsáno: x = 5, y = 1, z = -2 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 7/53 Motivační příklad 2 Příklad 2x -3y = 7 x +2z = 1 3x -3y +2z = 8 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 8/53 Motivační příklad 2 Příklad 2x -3y = 7 x +2z = 1 3x -3y +2z = 8 Řešení ■ Soustava má řešení (5,1, -2). ■ Existují další řešení: (-1, -3,1), (2, -1, -\), (11,5, -5), ... IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 9/53 Motivační příklad 2 Příklad 2x -3y = 7 x +2z = 1 3x -3y +2z = 8 Řešení ■ Soustava má řešení (5,1, -2). ■ Existují další řešení: (-1, -3,1), (2, -1, -\), (11,5, -5), ... ■ Řešením je každá trojice (ř, kde ř je libovolné. ■ Řešení je tedy nekonečně mnoho. ■ Tato situace obvykle nastává, je-li rovnic méně než proměnných (v tomto příkladu třetí rovnice nepřidává žádnou informaci, je pouze součtem prvních dvou rovnic). IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 10/53 Motivační příklad 3 Příklad 2x -3y = 7 x +2z = 1 3x -3y +2z = 9 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 11/53 Motivační příklad 3 Příklad 2x -3y = 7 x +2z = 1 3x -3y +2z = 9 Řešení ■ Neexistuje žádné řešení: součtem prvních dvou rovnic dostáváme 3x-3y + 2z = 8, což odporuje třetí rovnici. IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 12/53 Vyřešení a ekvivalence soustavy rovnic ■ Vyřešením soustavy rovnic rozumíme nalezení všech řešení. ■ Obvyklým postupem je převod soustavy na jednodušší soustavu se stejnou množinou řešení. Definice (Ekvivalence soustav lineárních rovnic) Soustavy lineárních rovnic se nazývají ekvivalentní, mají-li stejnou množinu řešení. IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 13/53 Úpravy soustavy Následujícími úpravami získáme vždy ekvivalentní soustavu lineárních rovnic: □ výměna libovolných dvou rovnic soustavy B vynásobení obou stran libovolné rovnice nenulovým číslem c B přičtení c-násobku /-té rovnice k y-té rovnici (/' ^ j) Každá z uvedených úprav je vratná. Původní soustavu dostaneme □ opakováním výměny rovnic. B vynásobením stejné rovnice číslem ±. B k y-té rovnici přičteme (-c)-násobek /-té rovnice. IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 14/53 Poznámky k úpravám soustavy Obecně nelze kombinovat více úprav v jednom kroku (mohlo by to vést k neekvivalentní soustavě rovnic): 2x -3y = 7 x +2z = 1 3x +3y +2z = 14 Současným přičtením 2. rovnice k 3. a 3. rovnice k 2. dostaneme 2x -3y = 7 4x +3y +4z = 15 4x +3y +4z = 15 Tato soustava není ekvivalentní: původní soustava má jedno řešení, upravená soustava jich ma nekonečně mnoho. IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 15/53 Vektory a matice IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory Vektory Vektor je uspořádaná n-tice prvků. Vektor se zapisuje do řádku či do sloupce jedním z následujících způsobů (vpravo jsou sloupcové vektory): (-3,2,8) (-3 2 8) /"3N (*i,x2,x3) {x^ x2 x3) y q Vektory stejného typu lze sčítat po složkách: (-3,2,8)+ (5,-5,0) = (2,-3,8) Násobení vektoru číslem: 5 • (-3,2,8) = (-15,10,40) IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 17/53 Matice Definice (Matice) Maticí typu m/n rozumíme obdélníkové schéma í au a-12 • • • a-\n\ A = 321 ^22 • • • &2n \3mA &m2 ■ ■ ■ 3mn/ ■ Zápis A = (a,y) znamená, že prvky matice A označujeme jmény tvaru a,, dle uvedeného schématu. IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 18/53 Součin matic Součinem matic A = (a,y) typu m/n a B = (b^) typu n/o je matice C = (Cjk) typu m/o splňující n Cik = ^2 3jj ■ bjk-7=1 Příklad 2 0 1 0 4-1 í° 1 o\ -2 -2 -2 1 0 0 \2 0 -3/ IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 19/53 Součin matic Součinem matic A = (a,y) typu m/n a B = (b^) typu n/o je matice C = (Cjk) typu m/o splňující n Cik = ^2 3jj ■ bjk-7=1 Příklad 2 0 0 4 -1 -1 í° 1 o\ -2 -2 -2 1 0 0 \2 0 -3/ 7 -11 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 20/53 Maticový zápis soustavy lineárních rovnic Soustavu lineárních rovnic a2i*i + a12x2 + + a22x2 + + a1nxn = + a2nXn = b2 3m1 x1 + 3m2x2 + lze zapsat pomocí matic následovně: /a-n a-i2 • • • ain\ a2i a22 ... a2n 3m2 *2 b2 amnj \XnJ \bm J Označíme-li matici a vektory poradě A, x, b, dostáváme rovnici A ■ x = b. IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 21/53 Maticový zápis soustavy lineárních rovnic Soustavu lineárních rovnic lze ještě úsporněji reprezentovat tzv. rozšířenou maticí soustavy: (A\b) ( a-12 • 321 ^22 • \ 3/771 3/772 • ^2/7 kí \ bm J Příklad 2x -3y = 7 x +2z = 1 3x +3y +2z = 14 2 -3 0 7 1 0 2 1 3 3 2 14 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 22/53 Schodovitý tvar matice Definice (Schodový tvar matice) Vedoucí prvek i-tého řádku matice je nejvější nenulový prvek na i-tém řádku (nulový řádek nemá vedoucí prvek). Matice je v (řádkově) schodovitém tvaru, jestliže D za nulovým řádkem následují už jen nulové řádky a B vedoucí prvek v každém nenulovém řádku je v pravějším sloupci než vedoucí prvky všech předcházejících řádků. Příklad /o 3 0 3\ 0 0 17 0 0 0 1 0 \0 0 0 0 0/ (2 -3 0 3\ 0 17 1 4 0 0 0 3 \0 0 0 1/ (2 -3 0 3\ 0 17 1 4 0 0 0 0 \0 0 0 3/ ■ Vedoucí prvky jsou červené. ■ Pouze matice vlevo je ve schodovitém tvaru. IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 23/53 Řešení soustavy lineárních rovnic IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory Elementární řádkové transformace matic Dříve zmíněné úpravy soustavy lineárních rovnic, které zachovávají ekvivalenci, přesně odpovídají následujícím elementárním řádkovým transformacím provedeným na rozšířené matici soustavy. Definice (Elementární řádkové transformace) Elementární řádkové transformace matic jsou O výměna dvou řádků matice, El vynásobení jednoho řádku nenulovým číslem, B přičtení násobku některého řádku k jinému řádku. IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 25/53 Gaussova eliminace Věta (Gaussova eliminace) Každou matici lze pomocí konečně mnoha elementárních řádkových úprav převést na řádkově schodovitý tvar. Důkaz Převod do schodovitého tvaru lze provést následujícím algoritmem. D Nechť y-tý sloupec je nejlevější nenulový sloupec matice. Vyměníme řádky tak, aby na prvním řádku byl v y-tém sloupci nenulový prvek a1y. B K ostatním řádkům, které mají v tomto sloupci nenulový prvek a,y přičteme (-|jL)-násobek prvního řádku. Tím vynulujeme celý y-tý sloupec až na a1y. Q Tím jsme dostali první řádek do požadovaného tvaru. Opakovanou aplikací kroků 1 a 2 na zbylé řádky převedeme matici do požadovaného tvaru. □ IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 26/53 Řešení soustavy lineárních rovnic Postupujeme následovně: □ Zapíšeme soustavu pomocí rozšířené matice soustavy (A \ b). Q Rozšířenou matici převedeme Gaussovou eliminací na matici (A' | b') ve schodovitém tvaru. Jelikož eliminace používá pouze elementární úpravy, reprezentuje výsledná rozšířená matice ekvivalentní soustavu lineárních rovnic. B Z rozšířené matice (A' \ b1) vyčteme kolik řešení má soustava rovnic. Rozlišujeme tři situace: ■ Matice {A' | b') obsahuje řádek tvaru (0 0 ... 0 | k), kde k je nenulové číslo. Tento řádek odpovídá rovnici 0 = k a soustava proto nemá řešení. V opačných případě soustava má řešení a nastává jeden z následujících případů. ■ Matice A' má v každém sloupci nějaký vedoucí prvek. Pak má soustava právě jedno řešení. ■ V matice A' existuje sloupec, ve kterém není vedoucí prvek. Pak má soustava nekonečně mnoho řešení. □ Řešení spočítáme pomocí tzv. zpětné substituce. IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 27/53 Zpětná substituce ■ Nechť (A | b') je matice ve schodovitém tvaru neobsahující řádek tvaru (0 0 ... 0 | k) s nenulovým k. m Proměnné odpovídající sloupcům matice A' bez vedoucího prvku nahradíme parametrem. Tyto proměnné mohou nabývat libovolné hodnoty. Hodnoty ostatních proměnných jsou v každém řešení závislé na konkrétních hodnotách parametrů. ■ Každý neprázdný řádek (00 ... Oflí-a;-^) ... ájn\b'j) převedeme na rovnici Xj = — • (b'i — aý(y+1)Xy+1 ... - ájnxn) ij tyto rovnice postupně odspodu řešíme dosazením níže spočítaných hodnot a parametrů. IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 28/53 Příklady Příklad 1 2x-| -3x2 =7 x^ +2x3 = 1 3xt -3x2 +2x3 = 9 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 29/53 Příklady Příklad 1 2x-| -3x2 =7 x^ +2x3 = 1 3xt -3x2 +2x3 = 9 2 -3 0 7 1 0 2 1 3 -3 2 9 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 30/53 Příklady Příklad 1 2x, -3x2 = 7 / 2 -3 0 7 +2x3 = 1 —> 1 0 2 1 -3x2 +2x3 = 9 V 3 -3 2 9 / 1 0 2 1 \ > 0 -3 -4 5 0 0 6 i ■ Uvedená soustava lineárních rovnic nemá řešení. IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory Příklady Příklad 2 2x-| -3x2 =7 x^ +2x3 = 1 3xt -3x2 +2x3 = 8 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 32/53 Příklady Příklad 2 2x-| -3x2 =7 x^ +2x3 = 1 3xt -3x2 +2x3 = 8 2 -3 0 7 1 0 2 1 3 -3 2 8 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 33/53 Příklady Příklad 2 2xt -3x2 3xí -3x? +2x3 +2x3 1 O 2 O -3 -4 OOO 7 1 8 2 -3 0 7 1 0 2 1 3 -3 2 8 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 34/53 Příklad 2 2xt -3x2 3xí -3x? +2x3 +2x3 1 O 2 O -3 -4 OOO 7 1 8 2 -3 0 7 1 0 2 1 3 -3 2 8 *1 *2 1 -2x3 ^(5 + 4x3) IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory Příklad 2 2x, 3xí -3x2 = 7 +2x3 = 1 -3x2 +2x3 = 8 x^ X3 2 -3 0 7 1 0 2 1 3 -3 2 8 x2 1 -2t Jg(5 + 4ř) ř 1 -2x3 ^(5 + 4x3) ■ Řešením je tedy každá trojice (1 - 2t, ^3(5 + 4ř), ř) kde ř je libovolné. ■ To je totéž jako (ř, ^f1, ^). IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory Příklady Příklad 3 2x-| -3x2 =7 Xt +2x3 = 1 3xt +3x2 +2x3 = 14 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 37/53 Efektivita Gaussovy eliminace ■ Gaussova eliminační metoda je velmi efektivní při ručním řešení malých soustav rovnic i pro počítačové řešení větších soustav (stovky až tisíce rovnic). ■ Pro rozsáhlejší soustavy existují efektivnější algoritmy. IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 38/53 Geometrický význam lineárních rovnic IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory Lineární rovnice o dvou neznámých ■ Lineární rovnice o dvou neznámých má nekonečně m řešení, které tvoří přímku v dvojrozměrném prostoru. ■ Řešením x + 2y = 8 je každá dvojice tvaru (ř, 4 - |). 6 5 4 3 2 1 0 0 12 3 4 5 6 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory Soustava lineárních rovnice o dvou neznámých Soustava lineárních rovnice o dvou neznámých Soustava lineárních rovnice o dvou neznámých Soustava lineárních rovnice o dvou neznámých Soustava lineárních rovnice o dvou neznámých Soustava lineárních rovnice o dvou neznámých Lineární rovnice o třech neznámých ■ Lineární rovnice o třech neznámých má nekonečně mnoho řešení, které tvoří rovinu v trojrozměrném prostoru. ■ Řešením 2x - 3y + Oz = 7 je každá trojice tvaru (ř, r). IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 47/53 Soustava lineárních rovnic o třech neznámých ■ Řešením soustavy lineárních rovnic o třech neznámých je průnik odpovídajících rovin. IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 48/53 Soustava lineárních rovnic o třech neznámých ■ Řešením soustavy lineárních rovnic o třech neznámých je průnik odpovídajících rovin. ■ 2x-3y =7 x +2z = 1 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 49/53 Soustava lineárních rovnic o třech neznámých ■ Řešením soustavy lineárních rovnic o třech neznámých je průnik odpovídajících rovin. ■ 2x-3y =7 x +2z = 1 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 50/53 Soustava lineárních rovnic o třech neznámých ■ Řešením soustavy lineárních rovnic o třech neznámých je průnik odpovídajících rovin. ■ 2x-3y =7 x +2z = 1 ■ 3x+3y+2z=14 IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 51/53 Soustava lineárních rovnic o třech neznámých ■ Řešením soustavy lineárních rovnic o třech neznámých je průnik odpovídajících rovin. IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 52/53 Soustava lineárních rovnic o třech neznámých ■ Všechna řešení soustavy lineárních rovnic o třech neznámých mohou tvořit: ■ rovinu (typicky pokud máme jednu rovnici) ■ přímku (typicky pokud máme dvě rovnice) ■ bod (typicky pokud máme tři rovnice) ■ Soustava také nemusí mít žádné řešení (typicky pokud máme více jak tři rovnice nebo pokud nějaké dvě rovnice odpovídají rovnoběžným rovinám). IB112 Základy matematiky: Řešení soustavy lineárních rovnic, matice, vektory 53/53