Předmluva Lineární algebra se v poslední době stále šířeji uplatňuje v nejrůznějších technických, technologických i ekonomických odvětvích. Předkládané skriptum se snaží o přehledný výklad nejpodstatnějších partií lineární algebry včetně některých geometrických i ekonomických aplikací. Prezentovaný učební text je určen jako učební pomůcka pro posluchače obou zlínských fakult VUT, tj. technologické i managementu a ekonomiky. Text je však vhodný i pro studenty jiných technických nebo i univerzitních specializací. Je určen pro začátečníky, proto je doplněn řadou řešených příkladů. Lineární algebra spolu s matematickou analýzou tvoří tradiční náplň úvodních semestrů technicky nebo ekonomicky zaměřeného vysokoškolského studia. Matematika vychází ve svých úvahách z pojmů přesně zavedených, v nichž logickými prostředky dokazuje tvrzení, jímž se říká matematické věty. Souhrn matematických vět, které se týkají téhož matematického pojmu, tvoří matematickou teorii tohoto pojmu. Ústředním pojmem algebry je pojem algebraické struktury, takže algebraické věty jsou tvrzení týkající se algebraických struktur. Aby tyto věty mohly vypovídat o algebraických strukturách, zavádějí se další pojmy, které umožňují popisovat vlastnosti těchto struktur, např. pojem podstruktury. Základní matematickou strukturou lineární algebry je vektorový prostor. Hlavními pomocnými pojmy, které umožňují popisovat jeho vlastnosti, jsou soustavy lineárních rovnic, matice a determinanty. V úvodních dvou kapitolách jsou shrnuty některé pojmy z teorie množin a logiky. Usnadňují přesné vyjadřování a umožňují zavádění základních pojmů. I když je skriptum určeno studentům technického zaměření, je většina vět uvedena i s důkazy. Jsem toho názoru, že vysokoškolsky vzdělaný odborník má umět přesně formulovat problémy a rozumět tomu co říká a co používá. Proto je nutné, aby se pocvičil v přesném matematickém deduktivním 1
myšlení. Porozumí-li student určitým partiím matematiky, získá schopnost i zájem později samostatně nastudovat další její partie. Bude také umět své poznatky v praxi aplikovat ve svém speciálním technologickém nebo ekonomickém oboru. Předkládané druhé vydání skripta je rozšířeno o cvičení a o poslední jedenáctou kapitolu. Látku k ní jsem čerpal především z knihy [?]. Je zde uvedena ukázka toho, jak je možno využít právě získaných znalostí z lineární algebry při řešení některých ekonomických problémů pomocí lineárního programování. Upřímně děkuji za ochotnou pomoc při přípravě skripta svým bývalým žákům, a to mladému Mgr. Lukáši Rachůnkovi, z našeho ústavu matematiky, i zkušenému prof. Josefu Mikešovi, DrSc., z katedry algebry a geometrie Přírodovědecké fakulty UP v Olomouci.
Zlín, listopad 1999.
autor
2
Kapitola 1 Logika Každá vědecká teorie je systém vět, které přijímáme jako pravdivé a které můžeme nazývat zákony, tvrzení nebo výroky. V matematice, jakožto vědě deduktivní tato tvrzení vyplývají jedno z druhého v určitém pořadí podle jistých principů. Jsou zpravidla doprovázeny úvahami, které mají zajistit jejich platnost. O úvahách tohoto druhu mluvíme jako o důkazech, a tvrzení jejichž platnost zajišťují, nazýváme teorémy, česky věty. Mezi termíny a symboly vyskytujícími se ve větách a důkazech rozlišujeme konstanty a proměnné . V aritmetice se například setkáváme s konstantami jako „čísloÿ, „nulaÿ („0ÿ), „jednaÿ („1ÿ), „součetÿ („+ÿ) a mnoho jiných. Každý z těchto termínů má přesně vymezený význam, který v průběhu úvah zůstává neměnný. Jako proměnných užíváme zpravidla jednotlivých písmen, například v aritmetice malých písmen „aÿ, „bÿ, „cÿ,. . . , „xÿ, „yÿ, „zÿ. Na rozdíl od konstant nemají proměnné samy o sobě nějaký význam. Tak na otázku: má nula takovou a takovou vlastnost? například je nula celé číslo? lze odpovědět kladně či záporně. Odpověď může být pravdivá či nepravdivá, ale v každém případě má smysl. Naproti tomu na otázku týkající se x, například na otázku: 3
je x celé číslo? nelze dát smysluplnou odpověď. Uvedené příklady nás přivádějí ke dvěma základním pojmům matematické logiky, o které hovoříme také jako o logice formální nebo také symbolické . Slovo logika je odvozeno z řeckého slova logos, což znamená slovo nebo smysluplná řeč. Logika vznikla jako samostatná disciplína velice dávno, dokonce dříve než aritmetika a geometrie. Na druhé straně teprve „nedávnoÿ, v minulém století, po dlouhém období stagnace, se znovu začal tento vědní obor rozvíjet. Bylo to způsobeno užitím moderních algebraických metod v logice, což mělo za následek vznik matematické logiky. Budoucí vysokoškolsky vzdělaný odborník, jako je například ekonom, technolog, matematik nebo právník se musí umět přesně, tedy jednoznačně, vyjadřovat. Musí tedy ovládat základy logiky. Matematickou logiku dělíme na dvě části, a to na výrokový a predikátový počet neboli kalkul . Základním pojmem výrokového počtu je výrok. Vymezíme jej pomocí obvyklé filosofické definice: Výrokem rozumíme každé sdělení, o kterém má smysl říci, že je pravdivé nebo nepravdivé, přitom platí jediná možnost. Výroky budeme označovat malými písmeny, nejčastěji p, q, r, . . .. Uvedeme nyní příklady výroků: p: nula je celé číslo q: Zlín je město r: 0 > 2 První dva výroky jsou zřejmě pravdivé , takovým výrokům přiřazujeme pravdivostní hodnotu 1, třetí výrok r je nepravdivý a takovému přiřadíme hodnotu 0. Sdělení, jako například: „brrÿ, „achÿ nebo „x je celé čísloÿ nejsou výroky. Základním pojmem predikátového počtu je predikát neboli výroková forma či formule. Výrokovou formou rozumíme každé sdělení, které obsahuje proměnné a dosadíme-li za ně, za všechny, nějaké konstanty, dostaneme výrok. Predikát s volnou proměnnou x budeme označovat V (x). Uvedeme nyní příklady výrokových forem: V1 (x) : x2 > x2 + 1 V2 (a, b) : (a + b)2 = a2 + 2ab + b2
4
Z výrokové formy lze dvojím způsobem dostat výrok, a to dosazením konstant za všechny proměnné nebo vázáním všech proměnných tzv. kvantifikátory, tj. buď sděleními tvaru: „pro každé xÿ, „pro všechna xÿ, „pro libovolné xÿ a podobně, která se nazývají velký nebo obecný kvantifikátor , značí se ∀. Symbol vznikl převrácením prvního písmene anglického slova „allÿ. Nebo také sděleními tvaru: „existuje xÿ, „pro vhodné xÿ nebo „pro některé xÿ a podobně, která se nazývají malý nebo existenční kvantifikátor , značí se ∃. Symbol vznikl převrácením prvního písmene anglického slova „existÿ. Vážeme-li všechny proměnné v predikátu pouze velkými kvantifikátory, dostáváme obecný výrok . Takovými jsou například výroky: ∀x (reálné číslo): x2 > x2 + 1 ∀a, b (reálná čísla): (a + b)2 = a2 + 2ab + b2 Poznamenejme, že ve formulaci obecných výroků bývá obrat „pro jakékoli věci nebo čísla x, y,ÿ často vypuštěn a musíme si jej myšlenkově doplnit; tak například komutativní zákon může být napsán pouze takto x+y =y+x Všimněme si dále výrokové funkce x>y+1 Tato formule není splněna každou dvojicí čísel. Jestliže například položíme x = 3 a y = 4, dostaneme nepravdivý výrok 3>4+1 Řekneme-li proto ∀x, y : x > y + 1 vyslovíme zřejmě výrok, a to nepravdivý. Na druhé straně však existují dvojice čísel, které splňují danou výrokovou funkci; jestliže například položíme x = 4, y = 2, dojdeme k pravdivému výroku 4>2+1 Takovou situaci vyjádříme stručně takto: 5
∃x, y : x > y + 1 Právě uvedené sdělení je pravdivým výrokem a je příkladem existenčního výroku nebo výroku existenčního charakteru, konstatující existenci věcí (např. čísel), jež mají určitou vlastnost. Popsané metody nám umožňují dostat výrok z jakékoli dané výrokové formule; záleží však na obsahu výrokové funkce zda dospějeme k pravdivému nebo nepravdivému výroku. Jako ilustraci uveďme příklad: Formule x=x+1 není splněna žádným číslem; proto ať předešleme slova „pro jakékoli číslo xÿ nebo „existuje číslo x takové, žeÿ vyslovený výrok bude nepravdivý. Obsahuje-li forma více proměnných, můžeme jejich vázání kvantifikátory různě kombinovat. Časté jsou tzv. podmíněně existenční výroky, jako je například: ∀x, y ∃z : x = y + z Jestliže některou proměnnou nevážeme kvantifikátorem, pak říkáme, že zůstala volnou proměnnou a daná forma se nestala výrokem. Například sdělení ∀x, y : x = y + z zůstává výrokovou formou s jednou volnou proměnnou z a se dvěma vázanými proměnnými x, y. Skutečnost, že kvantifikátory váží proměnné, tj. že ve výrokové funkci, jež po nich následuje, mění volné proměnné ve vázané proměnné, je velmi podstatnou vlastností kvantifikátorů. Je známo několik jiných výrazů majících obdobnou vlastnost, například integrační znak. Termín operátor je obecný název, jehož užíváme k označení všech výrazů majících tuto vlastnost. Mimo výrokových funkcí si zaslouží naší pozornosti některé další výrazy obsahující proměnné, totiž tzv. označovací neboli deskriptivní funkce. Jsou to výrazy, které se po nahrazení proměnných konstantami přemění v označení neboli popis věcí. Například výraz 6
2x + 1 je označovací funkcí, protože nahradíme-li v něm proměnnou „xÿ libovolnou číselnou konstantou, například 2, dostaneme označení určitého čísla, v našem případě 5. Mezi označovací funkce vyskytující se v aritmetice patří konkrétně všechny tzv. algebraické výrazy, jež se skládají z proměnných, numerických konstant a symbolů čtyř základních aritmetických operací, jako např. x − y,
x+1 , y+2
2(x + y − z)
Naproti tomu algebraické rovnice, tj. formule skládající se ze dvou algebraických výrazů spojených symbolem „=ÿ, jsou výrokové funkce. Pokud jde o rovnice, ustálila se v matematice speciální terminologie; o proměnných vyskytujících se v rovnici mluvíme jako o neznámých a čísla splňující rovnici nazýváme kořeny rovnice. Tak např. v rovnici x2 − 5x + 6 = 0 je proměnná „xÿ neznámá, zatímco čísla 2 a 3 jsou kořeny rovnice. O proměnných „xÿ, „yÿ, . . . použitých v aritmetice říkáme, že zastupují označení čísel, nebo, že čísla jsou hodnotami těchto proměnných. Tím se míní přibližně toto: výroková funkce obsahující symboly „xÿ, „yÿ, . . . se stane výrokem, nahradíme-li tyto symboly takovými konstantami, jež označují čísla (a nikoliv výrazy, jež označují například operace s čísly, vztahy mezi čísly nebo dokonce věci z mimoaritmetických oblastí jako jsou geometrické útvary, živočichové, rostliny atd.). Podobně proměnné v geometrii zastupují označení bodů a geometrických útvarů. O označovacích funkcích vyskytujících se v aritmetice můžeme rovněž říci, že zastupují označení čísel. Někdy prostě říkáme, že symboly „xÿ, „yÿ, . . . samy, právě tak jako označovací funkce z nich vytvořené, označují čísla nebo jsou označením čísel, ale pak jde o zkratkovitou terminologii. Výroky i výrokové formy lze spojovat neboli provádět s nimi operace a tím vytvářet složené výroky. Máme pět základních operací. Jedna je unární neboli jednočlenná, nazýváme ji negace výroku, používáme pro ni symbolu ¬, který čteme „není pravda, žeÿ. Pro daný výrok p jeho negaci zapíšeme tedy takto: ¬p, a čteme: „není pravda, že pÿ nebo „p není pravdivéÿ nebo „p neplatíÿ. Negaci výroku definujeme pomocí následující tabulky 7
p ¬p 0 1 1 0 Zbývající čtyři operace jsou binární neboli dvojčlenné, neboť se jimi spojují vždy dva výroky. Pomocí spojky „aÿ, symbol ∧, vytvoříme konjunkci výroků p, q, takže sdělení p ∧ q čteme „p a qÿ nebo „p a současně qÿ. Dále, pomocí spojky „neboÿ, symbol ∨, vytvoříme disjunkci výroků, takže sdělení p ∨ q čteme „p nebo qÿ. Dále, spojíme-li dva výroky slovy „jestliže . . . , pak . . . ÿ, dostaneme složený výrok, který označujeme jako implikaci nebo podmíněný výrok. Vedlejší větu následující za slovem „jestližeÿ, nazýváme antecedent neboli předpoklad, nebo mluvíme o postačující podmínce, hlavní větu uvedenou za slovem „pakÿ, nazýváme konsekvent neboli tvrzení, nebo také říkáme podmínka nutná. Pro implikaci používáme symbolu ⇒, takže sdělení p ⇒ q čteme „p implikuje qÿ, „p je postačující podmínka pro qÿ, resp. „q je nutná podmínka pro pÿ. Konečně, budeme se zabývat posledním pátým výrazem z výrokového kalkulu. Jde o výraz, s nímž se v běžném jazyce setkáváme poměrně zřídkakdy, totiž o výraz „když a jen kdyžÿ nebo synonymně „právě (tehdy) kdyžÿ, resp. „tehdy a jen tehdy, kdyžÿ, symbol ⇔. Jsou-li dva výroky p, q spojeny tímto výrazem, vzniká složený výrok p ⇔ q, který se nazývá ekvivalence výroků p, q. Říkáme také, že vztah důsledku platí mezi těmito dvěma výroky nebo konečně že každý s obou výroků je nutnou a dostatečnou podmínkou druhého. Není ani tak důležité jak se jednotlivá binární spojení výroků značí či čtou, ale daleko důležitější je, jak se definují. Jak pravdivostní hodnota složených výroků závisí na pravdivostních hodnotách obou složek. Proto si dobře zapamatujte následující tabulku, ve které uvedeme společně všechny čtyři definice: p 0 0 1 1
q p∧q 0 0 1 0 0 0 1 1
p∨q 0 1 1 1
p⇒q 1 1 0 1
p⇔q 1 0 0 1
Tabulka je tak důležitá, že pro její porozumění a následné zapamatování připojíme ještě další komentář. V prvních dvou sloupcích tabulky jsou tzv. 8
lexikograficky, tj. jako slova ve slovníku, uspořádány všechny dvojice pravdivostních hodnot pro výroky p, q. Dále, všimneme-li si třetího sloupce tabulky, můžeme říci, že konjunkce dvou výroků je pravdivá právě tehdy, když oba její členy jsou pravdivé. Velmi pozorně si prohlédněte čtvrtý sloupec. Zjistíte, že disjunkce je pravdivá právě tehdy, když aspoň jeden z obou spojovaných výroků je pravdivý. Tak například disjunkce výroků číslo 4 je menší nebo rovno číslu 5 je pravdivým výrokem. V logice a matematice používáme tedy spojky „neboÿ pouze v tzv. nevylučovacím smyslu, zatímco v běžném jazyce má ještě slovo „neboÿ význam vylučovací. Řekneme-li například, že odpoledne půjdeme na plovárnu nebo do knihovny užili jsme zřejmě spojky „neboÿ ve vylučovacím slova smyslu. Také v matematice je někdy potřebný vylučovací smysl slova „neboÿ, pak obvykle dodáváme, že „z uvedených případů platí právě jedenÿ. Tak například zákon trichotomie pro uspořádání čísel zní: pro každá dvě čísla x, y platí právě jedna z možností: x < y ∨ x > y ∨ x = y Zvláště pozorně si prohlédněte pátý sloupec horní tabulky. Zjistíte, že tvrdíme-li implikaci, tvrdíme tím, že se nestane, aby antecedent byl pravdivý a konsekvent nepravdivý. Implikace je tedy pravdivá v kterémkoli z těchto tří případů: (1) jak antecedent, tak konsekvent jsou pravdivé, (2) antecedent je nepravdivý a konsekvent je pravdivý (3) jak antecedent, tak konsekvent jsou nepravdivé. Teprve v posledním možném případě (v tabulce třetí řádek), kdy antecedent je pravdivý a konsekvent je nepravdivý, je celá implikace nepravdivá. Z toho vyplývá, že ten, kdo přijímá implikaci jako pravdivou a zároveň přijímá jako pravdivý její antecedent, nemůže než přijmout i její konsekvent; a ten, kdo přijímá implikaci jako pravdivou a zamítá jako nepravdivý její konsekvent, musí rovněž zamítnout její antecedent. V posledním sloupci snadno zjistíte proč se ekvivalence nazývá ekvivalencí. Je totiž pravdivá právě když oba spojované výroky mají tutéž pravdivostní hodnotu. Logikové, s náležitým pochopením pro potřeby vědeckých jazyků, rozhodli se zjednodušit a vyjasnit význam výrazu „jestliže, . . . , pak . . . ÿ a zbavit jej psychologických faktorů, stejně jako v případě slova „neboÿ, resp. „aÿ. 9
Za tím účelem rozšířili oblast použití tohoto výrazu, pokládajíce implikaci za smysluplný výrok i tehdy, když neexistuje žádná spojitost mezi jejími oběma členy, a učinili pravdivost či nepravdivost implikace závislou výlučně na pravdivosti či nepravdivosti antecedentu a konsekventu. Abychom tuto situaci stručně charakterizovali, říkáme, že soudobá logika používá implikací v materiálním smyslu nebo jednoduše materiálních implikací. Proti tomu stojí použití implikace ve formálním smyslu nebo formální implikace, kdy přítomnost určité formální souvislosti mezi antecedentem a konsekventem je nezbytnou podmínkou smysluplnosti a pravdivosti implikace. Pro ilustraci těchto poznámek uveďme čtyři příklady materiálních implikací, které nejsou formálními: jestliže 2 · 2 = 4, pak Zlín je město jestliže 2 · 2 = 5, pak Zlín je město jestliže 2 · 2 = 4, pak Zlín není město jestliže 2 · 2 = 5, pak Zlín není město V běžném jazyce bychom tyto výroky stěží pokládali za smysluplné, tím méně pak za pravdivé. Z hlediska matematické logiky jsou však všechny smysluplné, přičemž třetí výrok je nepravdivý a ostatní tři jsou pravdivé. Tím ovšem netvrdíme, že výroky tohoto druhu jsou zvlášť významné z jakéhokoli hlediska. Bylo by mylné domnívat se, že zde vysvětlený rozdíl mezi běžným jazykem a jazykem logiky má absolutní charakter a že uvedená pravidla používání slov „jestliže . . . , pak . . . ÿ v běžném jazyce nepřipouštějí výjimky. Ve skutečnosti používání těchto slov více či méně kolísá, a porozhlédneme-li se můžeme najít případy, v nichž toto užívání nevyhovuje našim pravidlům. Uvedeme jeden známý příklad. Představme si, že náš přítel stojí před řešením obtížného integrálu a že nevěříme, že jej vyřeší. Můžeme pak svoji nevíru vyjádřit žertovnou poznámkou a říci: jestliže vyřešíš tento integrál, pak já sním svůj klobouk Záměr tohoto vyjádření je zcela jasný. Tvrdíme zde implikaci, jejíž konsekvent je určitě nepravdivý; protože tvrdíme pravdivost celé implikace, tvrdíme tím zároveň nepravdivost antecedentu; tj. vyjadřujeme své přesvědčení, že náš přítel nedokáže vyřešit integrál, jímž se zabývá. Je však rovněž zcela jasné, 10
že antecedent a konsekvent naší implikace spolu vůbec nesouvisí, takže zde máme typický případ materiální a přitom nikoli formální implikace. Uvedeme zde ještě příklady materiálních a nikoli formálních výroků pro předchozí spojení: 2 · 2 = 5 nebo Zlín je město 2 · 2 = 4 a ve Zlíně nyní prší První výrok je zřejmě pravdivý a pravdivost druhého závisí doslova na počasí. Zákonem neboli tautologií výrokového počtu nazýváme výrokovou formu, která obsahuje pouze výrokové proměnné a dosadíme-li za ně (za všechny) konkrétní výroky, pak dostaneme vždy pravdivý výrok. Uvedeme nyní nejdůležitější a nejužívanější tautologie. Věta 1 (o tautologiích): Nechť p, q, r jsou libovolné výroky. Potom platí 1. ¬(p ∧ ¬p) (zákon sporu) 2. p ∨ ¬p (zákon vyloučení třetí možnosti) 3. (p ∧ q) ⇔ (q ∧ p) (p ∨ q) ⇔ (q ∨ p) 4. (p ∧ p) ⇔ p (p ∨ p) ⇔ p
)
(zákony komutativní)
)
(zákony idempotence)
5. (p ∧ (q ∧ r)) ⇔ ((p ∧ q) ∧ r) (p ∨ (q ∨ r)) ⇔ ((p ∨ q) ∨ r)
)
(zákony asociativní)
6. (p ∧ (q ∨ r)) ⇔ ((p ∧ q) ∨ (p ∧ r)) (p ∨ (q ∧ r)) ⇔ ((p ∨ q) ∧ (p ∨ r)) 7. ¬(p ∧ q) ⇔ (¬p ∨ ¬q) ¬(p ∨ q) ⇔ (¬p ∧ ¬q)
)
(zákony distributivní)
)
(zákony de Morganovy)
8. (p ⇒ q) ⇔ (¬q ⇒ ¬p) (zákon kontrapozice neboli obměny) 9. ((p ⇒ q) ∧ (q ⇒ r)) ⇒ (p ⇒ r) (zákon hypotetického sylogismu) 10. ((p ⇒ q) ∧ (q ⇒ p)) ⇔ (p ⇔ q) 11
11. ¬(p ⇒ q) ⇔ (p ∧ ¬q) Z de Morganových zákonů plynou ještě dvě důležitá pravidla pro negování obecných a existenčních výroků: ¬∀x : V (x) ⇔ ∃x : ¬V (x) ¬∃x : V (x) ⇔ ∀x : ¬V (x) Důkazy tautologií se provádějí tabulkovou metodou. Na ukázku uvedeme pouze důkaz tvrzení 8, tedy zákona kontrapozice. Důkazy zbývajících tvrzení přenecháme laskavému čtenáři jako cvičení. p 0 0 1 1
q ¬p 0 1 1 1 0 0 1 0
¬q 1 0 1 0
p⇒q 1 1 0 1
¬q ⇒ ¬p 1 1 0 1
(p ⇒ q) ⇔ (¬q ⇒ ¬p) 1 1 1 1
Na závěr kapitoly uvedeme několik poznámek k logické výstavbě matematiky, jakožto deduktivní vědy. Významným rozdílem oproti jiným vědním disciplínám je používání důkazů v matematice. Například fyzik také odvozuje některé fyzikální zákony z jiných zákonů, avšak na závěrečné potvrzení obvykle zkoumá souhlas tohoto zákona s experimentem. I matematik může někdy používat pozorování a také jej často, zejména při hledání nových tvrzení, používá. Avšak nový objev uzná za novou matematickou větu pouze tehdy, jestliže ji umí dokázat, tedy vyvodit z jiných obecnějších vět. Hned nás napadne, že ne všechny matematické věty mohou být dokázány. Ty nejobecnější, ležící v samotných základech příslušné matematické teorie, se nazývají axiomy nebo postuláty. Nedokazují se a slouží jako základ dané teorie. Rozlišujeme axiomy společné pro více matematických disciplín, např. logické a axiomy speciální, určené pro jistou matematickou disciplínu, například geometrii. Známým geometrickým axiomem je například tvrzení: „Libovolnými dvěma různými body prochází jediná přímka.ÿ Podobný proces probíhá s matematickými pojmy. Nové speciálnější pojmy se vymezují definicemi pomocí již zavedených obecnějších pojmů. Zase tedy musejí existovat nejobecnější pojmy, které nelze definovat pomocí jiných pojmů příslušné teorie. V geometrii jsou to např. pojmy „bodÿ, „přímkaÿ, „procházíÿ a podobně. Takové pojmy se nedefinují a zavádějí se také pomocí 12
axiomů. Z hlediska logické výstavby je tedy axiom jednoduchou matematickou větou, ve které se zavádějí axiomatické pojmy a axiomatické vztahy mezi nimi. V souvislosti s vyslovováním definic vysvětlíme jednu všeobecně používanou úmluvu. Výrazu „když a jen kdyžÿ by se mělo důsledně používat při zavádění definic, neboť z logického hlediska má definice vždy tvar ekvivalence. V geometrii bychom měli například říci, že „dvě přímky se nazývají různoběžné, právě když mají jediný společný bodÿ. Avšak kvůli jednoduššímu vyjadřování bývá zvykem definice vyslovovat ve tvaru implikace a řekneme tedy, že „dvě přímky nazýváme různoběžné, jestliže mají jediný společný bodÿ.
13
Kapitola 2 Množiny Nejprve si vybudujeme příslušný pojmový aparát, jehož se běžně užívá v algebře, a jehož budeme užívat i v dalších úvahách skripta. Začneme u nejobecnějšího pojmu, pojmu množiny. Množinou rozumíme souhrn nějakých věcí, kterým říkáme prvky množiny. Skutečnost, že věc x je prvkem množiny M , zapisujeme formulí x ∈ M ; jinak píšeme x 6∈ M . Mezi množiny počítáme i množinu prázdnou, která nemá žádných prvků; značíme ji symbolem ∅. Má-li množina prvky a,b,c,. . . ,z (v konečném počtu), zapisujeme ji jako {a, b, c, . . . , z}; zejména je {a} jednoprvková množina, jejímž jediným prvkem je a. Je-li M množina a P nějaká vlastnost, kterou každý prvek množiny M má nebo nemá, pak {x ∈ M ; P (x)} značí množinu všech prvků z množiny M , z nichž každý má vlastnost P . Je-li množina M ze souvislosti jasná, píšeme stručně jen {x; P (x)} místo {x ∈ M ; P (x)}. Jsou-li A, B množiny, pak říkáme, že A je částí (nebo podmnožinou) množiny B, a píšeme A ⊆ B nebo B ⊇ A, jestliže každý prvek množiny A je zároveň prvkem množiny B. O množinách A, B říkáme, že jsou si rovny, a píšeme A = B, když platí A ⊆ B a zároveň B ⊆ A. Jinak říkáme, že množiny jsou různé a píšeme A 6= B Podle definice tedy důkaz rovnosti množin A, B provedeme tak, že ukážeme, že každý prvek množiny A je v B a zároveň každý prvek množiny B je v A. Dále, jestliže je A ⊆ B a současně A 6= B, pak říkáme, že A je pravá nebo vlastní podmnožina B. Je-li A množina, pak množinu všech podmnožin v A nazýváme booleán množiny A a značíme B(A) nebo 2A . Je-li A konečná množina a označíme-li n 14
počet prvků v A, pak sečtením kombinačních čísel (ni ) , i = 0, 1, . . . , n neboli počtu i-prvkových podmnožin (n0 ) + (n1 ) + . . . + (nn ) = (1 + 1)n = 2n snadno pomocí binomické věty dostaneme, že booleán má 2n prvků; odtud plyne druhý způsob jeho označování jako 2A . Množinu {{x}, {x, y}} nazýváme uspořádanou dvojicí utvořenou z prvků x, y v tomto pořadí; značíme ji symbolem (x, y); x se nazývá první člen a y druhý člen uspořádané dvojice. Uspořádaná dvojice se tedy zadává množinou složenou z obou členů a vyznačením prvního členu. Věta 2 Buďte (x, y), (z, u) uspořádané dvojice. Pak platí (x, y) = (z, u), právě když x = z, y = u. Důkaz. Je-li x = z, y = u, pak x a z značí týž objekt a y a u zase týž objekt. Proto (x, y) = (z, u). Je-li (x, y) = (z, u), je {{x}, {x, y}} = {{z}, {z, u}}. Pak tedy ze vztahu {x} ∈ {{x}, {x, y}} plyne {x} ∈ {{z}, {z, u}}. Máme dvě možnosti: (a) {x} = {z}, a tedy x = z. Proto {x, y} = {z, u} = {x, u}, a odtud y = u. (b) {x} = {z, u}. Odtud je z = x = u a {x, y} = {z}, takže y = z = x. Odtud je zejména x = z, y = x = u. S množinami lze provádět jisté operace, které si nyní popíšeme. Buďte A, B množiny. Pak jejich sjednocením rozumíme množinu všech prvků, které leží aspoň v jedné z těchto množin; sjednocení množin A, B označíme symbolem A ∪ B. Průnikem množin A, B se rozumí množina všech prvků, které leží v množině A i v množině B; průnik množin A, B označujeme symbolem A ∩ B. Rozdíl množin A, B je definován jako množina všech prvků, které jsou v množině A a nejsou v množině B; tento rozdíl označujeme symbolem A − B. Konečně kartézským součinem množin A, B rozumíme množinu všech uspořádaných dvojic (a, b) takových, že a ∈ A, b ∈ B; tento kartézský součin označujeme symbolem A × B. Množiny A, B se nazývají disjunktní, je-li A ∩ B = ∅, tj. nemají-li společných prvků. Jinak jsou incidentní. Buďte A, B množiny; libovolná podmnožina ρ jejich kartézského součinu A×B se nazývá korespondence, nebo též binární relace z množiny A do množiny B. Je-li ρ korespondence z množiny A do B, pak {(y, x) ∈ B×A; (x, y) ∈ 15
ρ} je korespondence z množiny B do množiny A; nazývá se korespondence inverzní ke korespondenci ρ a značí se ρ−1 . Je-li ρ korespondence z množiny A do množiny B a σ korespondence z množiny B do množiny C , utvoříme množinu {(x, z) ∈ A × C; existuje y ∈ B tak, že (x, y) ∈ ρ, (y, z) ∈ σ} Pak tato množina je zřejmě korespondence z množiny A do množiny C , které se říká korespondence složená z korespondencí ρ a σ, nebo též součin korespondencí ρ a σ a značí se symbolem ρσ. Z definic snadno plyne, že (ρσ)−1 = σ −1 ρ−1 a že pro skládání korespondencí platí zákon asociativní, tj. (ρσ)τ = ρ(στ ) pro libovolné korespondence ρ z množiny A do množiny B , σ z B do množiny C a τ z C do množiny D. Korespondenci z množiny A do množiny A, která obsahuje právě všechny dvojice tvaru (a,a) pro libovolné a ∈ A, nazýváme identita na množině A a značíme ji idA . Příklad. Mějme množiny A = {a, b, c}, B = {u, v}, C = {1, 2, 3} a korespondence ρ = {(a, u), (a, v), (b, v), (c, v)}, σ = {(v, 1)}. Pak ρσ = {(a, 1), (b, 1), (c, 1)} ρ−1 = {(u, a), (v, a), (v, b), (v, c)},
σ −1 = {(1, v)}
σ −1 ρ−1 = {(1, a), (1, b), (1, c)} Je-li ρ korespondence z množiny A do množiny B a C ⊆ A, pak klademe ρ[C] = {b ∈ B; existuje a ∈ C tak, že (a, b) ∈ ρ}. Buďte A, B množiny, ρ korespondence z množiny A do množiny B . Řekneme, že tato korespondence je částečné zobrazení množiny A do množiny B , je-li splněna tato podmínka: (i) Jsou-li a ∈ A, b ∈ B, b0 ∈ B takové prvky, že (a, b) ∈ ρ, (a, b0 ) ∈ ρ, pak b = b0 . nebo jak se snadno ukáže, ekvivalentní podmínka (i’) ρ−1 ρ ⊆ idB
16
Místo (a, b) ∈ ρ pak píšeme obvykle b = ρ(a), nebo též ρ : a 7→ b. Místo ρ(a) se někdy píše aρ . Prvek b nazýváme obrazem prvku a při částečném zobrazení ρ, prvek a vzorem prvku b při tomto částečném zobrazení. Definiční podmínka (i) tedy říká, že při částečném zobrazení nemůže mít týž prvek dva různé obrazy. Dále klademe dom ρ = {a ∈ A; existuje b ∈ B tak, že (a, b) ∈ ρ} Tato množina se nazývá oborem (anglicky domain) částečného zobrazení ρ. Množina ρ[A] se nazývá obor hodnot částečného zobrazení ρ a značí se ran ρ nebo také im ρ; označení jsou zkratkami anglických slov range, resp. image. Částečné zobrazení ρ z množiny A do množiny B se nazývá zobrazení množiny A do množiny B , je-li splněna tato podmínka: (ii) dom ρ = A nebo ekvivalentně (ii’) idA ⊆ ρρ−1 Píšeme ρ : A → B : a 7→ b, je-li a ∈ A, b ∈ B, ρ(a) = b. Systém všech zobrazení množiny A do množiny B značíme B A . Je-li ρ zobrazení množiny A do množiny B a C ⊆ A, pak ρ ∩ (C × B) je zřejmě zobrazení množiny C do množiny B; nazývá se restrikce zobrazení ρ na množinu C. Je-li zobrazení σ restrikcí zobrazení ρ, říkáme také, že zobrazení ρ je rozšířením zobrazení σ, nebo, že vzniklo rozšířením zobrazení σ. Příklad. Buďte ρ, σ korespondence z předchozího příkladu. Je zřejmé: Korespondence ρ z A do B , korespondence ρ−1 z B do A a korespondence σ −1 ρ−1 z C do A nejsou částečná zobrazení (například v korespondenci ρ by měl prvek a dva různé obrazy u,v ). Dále korespondence σ, σ −1 jsou částečná zobrazení z množiny B do množiny C , respektive z množiny C do množiny B . Konečně, korespondence ρσ je zobrazení množiny A do množiny C . Místo slova „zobrazeníÿ užíváme často slova funkce a funkci nejčastěji značíme symbolem f . Název funkce užíváme zejména pro zobrazení číselných množin. U funkcí bývá zvykem místo slova „oborÿ užívat názvu definiční obor a užívat označení Df nebo D(f ); podobně obor hodnot označujeme u funkcí Hf nebo H(f ). Protože jsou zobrazení definována jako množiny, máme definovánu také rovnost dvou zobrazení. Platí: 17
Věta 3 Jsou-li f , g zobrazení, pak f = g, právě když dom f = dom g a f (x) = g(x) pro každé x ∈ dom f . Důkaz. Je-li f = g, je jistě dom f = dom g a f (x) = g(x) pro každé x ∈ dom f podle věty ??. Nechť nyní obráceně dom f = dom g a f (x) = g(x) pro každé x ∈ dom f . Buď (x, y) ∈ f. Pak x ∈ dom f = dom g a y = f (x) = g(x), takže (x, y) ∈ g. Máme f ⊆ g a podobně se dokáže g ⊆ f . Zobrazení množiny A do množiny B také označujeme symbolem (f (a))a∈A ; místo f (a) se někdy píše fa , takže symbol pro zobrazení je (fa )a∈A . Při tomto způsobu označení toto zobrazení nazýváme indexovaným systémem prvků. Vedle tohoto označení se často s výhodou užívá symbolu {f (a); a ∈ A} pro ran f . Je-li zejména A = N množina všech přirozených čísel, pak (fn )n∈N se nazývá posloupnost prvků fn . Je-li I množina a (Ai )i∈I indexovaný systém prvků takový, že Ai je množina, mluvíme o indexovaném systému množin. Na indexované systémy množin rozšíříme definici sjednocení a průniku. Buď I 6= ∅ a (Ai )i∈I nechť je indexovaný systém množin. Definujeme pak sjednocení systému všech Ai jako množinu všech prvků, z nichž každý náleží aspoň do jedné množiny Ai . Toto sjednocení označujeme symbolem ∪i∈I Ai . Podobně průnik systému (Ai )i∈I je množina všech prvků, z nichž každý náleží do všech množin Ai ; označujeme ji symbolem ∩i∈I Ai . Speciální případ této situace nastane, je-li I množina množin a Ai = i pro každé i ∈ I. Obdržíme pak ∪i∈I i a ∩i∈I i. Ze stylistických důvodů mluvíme pak raději o systému množin než o množině množin. Jeli {1, 2, 3, . . . , n}, pak místo ∪i∈I Ai , ∩i∈I Ai píšeme také po řadě A1 ∪ A2 ∪ . . . ∪ An , A 1 ∩ A 2 ∩ . . . ∩ An . Protože zobrazení je zvláštní případ korespondence, lze k zobrazení utvořit korespondenci inverzní, a ke dvěma zobrazením utvořit korespondenci složenou. Inverzní korespondence k zobrazení nemusí být ani částečné zobrazení; viz například (σρ)−1 ve výše uvedeném druhém příkladu. Je-li f zobrazení množiny A do množiny B a je-li, C ⊆ A, D ⊆ B, pak platí f [C] = {f (a); a ∈ C}, f −1 [D] = {a ∈ A; f (a) ∈ D} Je-li dále g zobrazení množiny B do množiny E, snadno se dokáže, že f g je zobrazení množiny A do E takové, že (f g)(x) = g(f (x)) pro každé x ∈ A. Zobrazení f množiny A do množiny B se nazývá surjektivní, je-li splněna tato podmínka 18
(iii) Ke každému b ∈ B existuje a ∈ A tak, že f (a) = b nebo ekvivalentně (iii’) idB ⊆ f −1 f Místo surjektivní zobrazení říkáme surjekce nebo též zobrazení množiny A na množinu B. Zobrazení f množiny A do množiny B se nazývá injektivní, je-li splněna tato podmínka (iv) Pro libovolná a ∈ A, a0 ∈ A, a 6= a0 platí f (a) 6= f (a0 ); nebo ekvivalentně (iv’) f f −1 ⊆ idA nemůže mít tedy týž prvek dva různé vzory. Místo injektivní zobrazení říkáme injekce nebo též prosté zobrazení množiny A do množiny B. Zobrazení f množiny A do B se nazývá bijektivní, je-li surjektivní a injektivní současně, tj. platí-li f f −1 = idA a f −1 f = idB . Místo bijektivní zobrazení říkáme také bijekce nebo též jednoznačné zobrazení množiny A na množinu B . U bijekcí často píšeme A ↔ B : a ↔ b, místo A → B : a 7→ b. Příklad. Buď A = {a, b, c}, B = {1, 2}, α : a 7→ 1, b 7→ 2, c 7→ 2 a konečně β : 1 7→ a, 2 7→ b. Pak α je zobrazení množiny A na množinu B neboli surjekce (každý prvek z B je obrazem), zatím co β je zobrazení množiny B do množiny A, které není surjektivní (existuje prvek, a to c v A, který není obrazem). Zobrazení α není injekce (různé prvky b, c ∈ A mají týž obraz), zatím co zobrazení β je injekce. Zobrazení množiny A do sebe se nazývá transformace množiny A. Bijektivní transformace se nazývá permutace. Transformaci ρ, zejména je-li permutací, zapisujeme často tak, že sdružené prvky píšeme pod sebe, tj. místo ρ : a 7→ b, c 7→ d, . . . píšeme ρ=
a c ... b d ...
!
Množinu všech permutací konečné množiny o n prvcích značíme Sn . Má n! prvků zvaných permutace stupně n. 19
Buďte A, B množiny. Říkáme, že jsou ekvipotentní nebo že mají stejný počet prvků, a píšeme A ∼ B, jestliže existuje aspoň jedna bijekce množiny A na B. Zřejmě je A ∼ A, dále A ∼ B implikuje B ∼ A a konečně A ∼ B, B ∼ C implikují A ∼ C při libovolných množinách A, B, C. Buď A množina, označme N0 množinu všech celých nezáporných čísel a nechť n ∈ N0 . Říkáme, že počet prvků množiny A je roven n nebo také, že množina A má n prvků, je-li A ekvipotentní s množinou {i ∈ N0 ; 1 ≤ i ≤ n} nebo, což je totéž, s množinou {i ∈ N0 ; 0 ≤ i < n}. O množině A říkáme, že je konečná, existuje-li n ∈ N0 tak, že A má n prvků. Množina, která není konečná, se nazývá nekonečná. Příklad. ∅ je konečná a počet jejích prvků je 0. {x} je konečná a má 1 prvek. Množiny N, N0 jsou nekonečné. Příklad. Buďte A = {a, b, c, d}, B = {p, q, r, s}, (i) α1 : a ↔ p, b ↔ q, c ↔ r, d ↔ s (ii) α2 : a ↔ r, b ↔ p, c ↔ q, d ↔ s, pak α1 , α2 jsou příklady bijekcí A na B a množiny A, B mají stejný počet prvků. Dále A ∼ {1, 2, 3, 4}. Obě množiny A, B jsou tedy konečné a mají po čtyřech prvcích. Příklad. Buď α permutace množiny N definovaná takto: α=
1 2 3 ... 3 5 7 ...
přesněji pro n ∈ N α=
n 2n + 1
!
!
Neboli při funkčním zápisu α(1) = 3, α(2) = 5, α(3) = 7, α(4) = 9, . . . přesněji α(n) = 2n + 1, n ∈ N Je tedy dom α = N, ran α = {x ∈ N; x = 2n+1, n ∈ N} = {x ∈ N; x je liché } je pravá podmnožina N a α je bijekce N na množinu ran α, tedy množina N je ekvipotentní se svou pravou částí. Z definic je zřejmé, že takovou vlastnost má právě každá nekonečná množina. 20
Věta 4 Buď f zobrazení množiny A do množiny B, g zobrazení množiny B do množiny A takové, že f g = idA , gf = idB . Pak f , g jsou bijekce a platí g −1 = f . Důkaz. Je-li x, y ∈ A, x 6= y a f (x) = f (y), pak x = idA (x) = (f g)(x) = g(f (x)) = g(f (y)) = (f g)(y) = idA (y) = y, a to není možné. Tedy z podmínky x 6= y plyne f (x) 6= f (y) a f je injekce. Buď z ∈ B libovolné. Pak z = idB (z) = (gf )(z) = f (g(z)), takže g(z) ∈ A je prvek s vlastností f (g(z)) = z; tedy f je surjekce. Dokázali jsme, že f je bijekce, podobně se důkaz provede pro g. Je-li (y, z) ∈ g, pak z = g(y), a tedy f (z) = f (g(y)) = (gf )(y) = idB (y) = y, takže (z, y) ∈ f . Dokázali jsme, že g −1 ⊆ f ; podobně se dokáže f −1 ⊆ g. Je-li (x, y) ∈ f , je (y, x) ∈ f −1 , a tedy (y, x) ∈ g, a tudíž (x, y) ∈ g −1 , takže f ⊆ g −1 . Odtud je f = g −1 . Buď n ≥ 1 celé, A množina. Uspořádanou n-ticí prvků množiny A neboli řetězem délky n nebo také konečnou posloupností o n prvcích rozumíme zobrazení a množiny {1, . . . , n} do množiny A. Místo a(i ) obvykle píšeme ai pro každé i ∈ {1, . . . , n}. Taková n-tice je dána, je-li dán obraz ai každého i ∈ {1, 2, . . . , n}; zapisujeme ji ve tvaru (ai )ni=1 nebo (a1 , a2 , . . . , an ) nebo také a1 a2 . . . an . Množina {1, 2, . . . , n}, která se zde objevuje, se dá vyjádřit jako {i ∈ N; 1 ≤ i ≤ n}. Připustíme-li také n = 0, bude roli této množiny hrát {i ∈ N; 1 ≤ i ≤ 0} = ∅. Uspořádaná 0-tice prvků množiny A bude tedy zobrazení množiny ∅ do množiny A. Připomeňme, že zobrazení množiny ∅ do množiny A je zvláštní případ korespondence z ∅ do A, tedy podmnožina množiny ∅×A = ∅. Proto tedy zobrazení množiny ∅ do množiny A je prázdná množina. Z tohoto důvodu existuje jediná nultice prvků množiny A, kterou je prázdná množina. Tuto nultici obvykle označujeme symbolem Λ. Je to proto, abychom z označení vytušili, jak se na prázdnou množinu díváme. Lze se na ni dívat různě: Před chvílí jsme se na ni dívali jako na množinu {i ∈ N; 1 ≤ i ≤ 0}. Symbol Λ připomíná, že prázdnou množinu nyní chápeme jako (jedinou) nultici prvků nějaké množiny A. Množinu všech uspořádaných n-tic (n ∈ N0 ) množiny A nazýváme ntou kartézskou mocninou množiny A a označujeme ji symbolem An nebo též A × . . . × A. Buď n ∈ N a A1 , . . . , An množiny. Položíme A = A1 ∪. . .∪ An a definujeme množinu A1 × . . . × An jako {(a1 , . . . , an ) ∈ An ; a1 ∈ A1 , . . . , an ∈ An }. Tuto množinu nazýváme kartézským součinem množin A1 , . . . , An . 21
Vrátíme se nyní ke studiu kartézské mocniny An . Zejména tedy je A0 = {Λ}. Pro n = 1 je An = A1 množina všech zobrazení množiny {1} do A, čili množina všech uspořádaných dvojic (1, a), kde a ∈ A. Položíme-li f (a) = (1, a), je f bijekce množiny A na množinu A1 . Je zvykem nerozlišovat v této souvislosti dvojici (1, a) od prvku a a klást A1 = A. Pro n = 2 dochází k situaci, kdy máme dvě definice uspořádané dvojice (a, b). Jednak je to {{a}, {a, b}}, jednak je to zobrazení množiny {1, 2} do A s hodnotami a, b, tedy množina {(1, a), (2, b)} = {{{1}, {1, a}}, {{2}, {2, b}}}. Je vidět, že poslední množina je různá od množiny {{a}, {a, b}}. Podobně jako jsme nahoře ztotožnili prvek a s uspořádanou dvojicí (1, a), tak také ztotožníme uspořádanou dvojici (a, b) s množinou {(1, a), (2, b)} při libovolném a, b ∈ A. Vyjde nám tedy, že A2 = A × A.
22
Kapitola 3 Řešení soustav lineárních rovnic Gaussovou eliminací 3.1
Ekvivalence soustav
Za největšího matematika první poloviny 19. století bývá považován německý matematik Gauss (Carl Fridrich, 1777–1855). Prakticky po celý život (1807– 1855) pracoval jako ředitel astronomické observatoře v Göttingenu a jako profesor tamnější univerzity. Jeho disertační práce z roku 1799 obsahuje první přesný důkaz tzv. základní věty algebry. K jednomu ze tří svých důkazů použil celých komplexní čísel, která se dodnes nazývají Gaussovými. Pracoval v teorii čísel (kongruence celých čísel včetně symboliky) a znal už v roce 1799, tedy dříve než Bolayai (1823) myšlenku neeukleidovské geometrie. Spolu s Weberem sestrojili první skutečně fungující telegraf. Jsou-li m, n přirozená, aij , bi reálná čísla pro každé i = 1, 2, . . . , m, j = 1, 2, . . . , n, pak úloha najít všechny uspořádané n-tice reálných čísel (x1 , x2 , . . . , xn ) tak, aby platilo současně a11 x1 + a12 x2 + · · · + a1n xn = b1 a21 x1 + a22 x2 + · · · + a2n xn = b2 .. .. .. . . . am1 x1 + am2 x2 + · · · + amn xn = bm se nazývá soustava m reálných lineárních rovnic o n neznámých x1 , x2 , . . . , xn . 23
Je-li (c1 , c2 , . . . , cn ) jedna z hledaných n-tic, pak ji nazýváme řešením dané soustavy o složkách cj , j = 1, 2, . . . , n. Naši soustavu můžeme zapsat kratším způsobem, a to pomocí jen jedné, obecně i-té, rovnice ai1 x1 + ai2 x2 + . . . + ain xn = bi , i = 1, 2, . . . , m Dalšího podstatného zkrácení zápisu dosáhneme pomocí sumačního znaménka n X
aij xj = bi , i = 1, 2, . . . , m
j=1
Čísla aij se nazývají koeficienty a čísla bi se nazývají pravé strany soustavy. Opíšeme-li ze soustavy pouze koeficienty a vše ostatní vynecháme, dostaneme obdélník o rozměru mn napsaný z prvků aij , který se nazývá matice soustavy kaij k. Připíšeme-li k ní ještě pravé strany dostaneme tzv. matici rozšířenou kaij |bi k. O prvcích a11 , a22 , . . . akk , kde k = min {m, n} říkáme, že tvoří hlavní diagonálu. O maticích bude následovat speciální kapitola, nyní je budeme pouze používat ke stručnému a přehlednějšímu zápisu při řešení soustav lineárních rovnic. Na levých stranách soustavy lineárních rovnic jsou polynomy, ve kterých jsou všechny členy stejného stupně, a to stupně jedna. Takové mnohočleny se nazývají homogenní nebo formy, a to lineární. Podle počtu proměnných se nazývají n-ární. Na levých stranách máme tedy n-ární lineární formy. Jsou-li v soustavě na pravých stranách samé nuly, pak mluvíme o soustavě homogenních lineárních rovnic nebo krátce o soustavě homogenní nebo také názorně o soustavě bez pravých stran. O dvou soustavách lineárních rovnic řekneme, že jsou ekvivalentní, jestliže mají tytéž množiny řešení. Dostaneme-li pomocí jisté úpravy z jedné soustavy soustavu s ní ekvivalentní, pak mluvíme o ekvivalentních úpravách soustavy. Věta 5 Ekvivalentní úpravy soustavy lineárních rovnic jsou: (1) Výměna pořadí rovnic. (2) Násobení jedné rovnice nenulovým reálným číslem. (3) Přičtení libovolného reálného k-násobku jedné rovnice k jiné rovnici. (4) Vynechání rovnice tvaru 0 = 0. 24
Důkaz . Platnost tvrzení (1) a (4) je zřejmá. Dokážeme platnost tvrzení (2): Nechť je dána soustava n X
aij xj = bi , i = 1, 2, . . . , m
j=1
Vynásobme první rovnici, vzhledem k (1) na pořadí nezáleží, nenulovým reálným číslem k a dostaneme tak pomocí úpravy (2) novou soustavu (
P k · n a x = k · b1 Pn j=1 1j j j=1
aij xj = bi , i = 2, 3, . . . , m
Nechť (c1 , c2 , . . . , cn ) je řešení dané soustavy. Pak n X
aij cj = bi , i = 1, 2, . . . , m
j=1
Pak také k·
n X
a1j cj = k · b1
j=1
a tedy (c1 , c2 , . . . , cn ) je také řešením nové soustavy. Obráceně, násobíme-li první rovnici nové soustavy číslem k1 , Pak dostaneme, pomocí úpravy (2), danou soustavu. Podle předchozí úvahy je každé řešení nové soustavy také řešením dané soustavy. Celkem máme dokázáno, že obě soustavy jsou ekvivalentní. Podobně se dokáže tvrzení (3).
3.2
Gaussova eliminace
Algoritmus a jeho zdůvodnění pomocí věty ??: Řešme obecnou soustavu m reálných lineárních rovnic o n neznámých a11 x1 + a12 x2 + · · · + a1n xn = b1 a21 x1 + a22 x2 + · · · + a2n xn = b2 .. .. .. . . . am1 x1 + am2 x2 + · · · + amn xn = bm 25
Její rozšířená matice je
a11 a21 .. .
a12 a22 .. .
... ... .. .
a1n a2n .. .
b1 b2 .. .
am1 am2 . . . amn
bm
Je zřejmé, že přiřazení soustav a jejich rozšířených matic je vzájemně jednoznačné. V dalším výkladu budeme tedy nadále mluvit o soustavách rovnic, avšak psát budeme pouze jejich rozšířené matice. Lze předpokládat, že ai1 6= 0 pro vhodné i , jinak by soustava neobsahovala neznámou x1 . Lze předpokládat, že a11 6= 0, jinak vyměníme pořadí rovnic, i1 což je ekvivalentní úprava. Pro i = 2, 3, . . . , m přičteme −a -násobek první a11 rovnice k i -té a vynecháme rovnice tvaru 0 = 0. Dostaneme tak ekvivalentní soustavu s maticí b1 a11 a12 . . . a1n a022 . . . a02n b02 0 . .. .. . . . .. . . . . . a0s2 . . . a0sn
0
b0s
kde s ≤ m a kde v prvním sloupci jsou pod diagonálou samé nuly a na diagonále prvek a11 6= 0. Jsou-li všechny koeficienty a0ij = 0 pro i = 2, 3, . . . , s; j = 2, 3, . . . , n, pak, vzhledem k tomu, že všechna b0i 6= 0, neboť rovnice tvaru 0 = 0 byly vynechány, soustava nemá řešení, což je jeden ze tří možných druhů výsledku. Je-li naopak některý koeficient a0ij 6= 0, lze předpokládat, že a0i2 6= 0 pro vhodné i = 2, 3, . . . , s, jinak přečíslujeme neznámé. Poslední úprava je sice neekvivalentní, avšak kompenzuje se tím, že se nakonec vrátíme k původnímu očíslování. Ostatně tuto úpravu si při praktickém řešení pouze pomyslně představíme. Lze předpokládat, že a022 6= 0, jinak vyměníme pořadí rovnic. Nyní podobně jako předtím najdeme ekvivalentní soustavu s maticí
a11 0 0 .. .
a12 a022 0 .. .
a13 a023 a0033 .. .
a1n a02n a003n .. .
b1 b02 b003 .. .
0
0
a00t3 . . . a00tn
b00t
... ... ... .. .
kde je t ≤ s ≤ m a kde jsou v prvních dvou sloupcích pod diagonálou samé nuly a na ní nenulové prvky. Pokračujeme-li v těchto úpravách pokud to 26
jde, pak po konečném počtu kroků, menším než je minimum z čísel m,n, dostaneme tzv. redukovaný tvar dané soustavy
d11 0 .. . 0
d12 . . . d22 . . . .. ... . 0 ...
d1n d2n .. .
g1 g2 .. .
dhn
gh
kde pod diagonálou jsou samé nuly a na diagonále vesměs nenulové prvky d11 , d22 , . . . , dhh . Mohou nastat dva případy: Buď je h = n nebo h < n. Nastane-li první případ, tedy h = n, pak má soustava jediné řešení a jeho složky vypočteme pozpátku xn =
gn gn−1 gn · dn−1,n ; xn−1 = − ;... dnn dn−1,n−1 dn−1,n−1 · dnn
Nastane-li druhá možnost, tedy h < n, pak má soustava nekonečně mnoho řešení závislých na volbě n − h parametrů uh+1 = xh+1 , . . . , un = xn a tzv. obecné řešení vypočteme pomocí nich opět pozpátku xh =
gh − dh,h+1 · uh+1 − · · · − dhn · un ; xh+1 = . . . ; . . . dhh
Je zřejmé, že všechny popsané úpravy jsou proveditelné v oboru reálných čísel. Odvodili jsme Věta 6 Každá soustava m lineárních reálných rovnic o n neznámých má buď jediné reálné řešení, je-li n = h; nebo nekonečně mnoho řešení, je-li n > h; nebo žádné řešení. Kde h je počet rovnic v redukované soustavě a ze tří uvedených možností nastane vždy právě jedna. Poznamenejme, že v případě nekonečně mnoha řešení mohou složkami řešení být i čísla komplexní nereálná, tedy imaginární, volíme-li taková čísla za parametry. Volbou konkrétních parametrů se dostane z tzv. obecného řešení tzv. partikulární neboli částečné řešení. 27
Pro ekvivalentní úpravy soustav lineárních rovnic zavedeme následující symboly: Označíme Rij , Ri (k), resp. Rij (k) výměnu i-té a j-té rovnice, vynásobení i-té rovnice číslem k 6= 0, resp. přičtení k-násobku j-té rovnice k rovnici i-té. Formálně budeme tyto úpravy používat na řádky matic (soustav). V této souvislosti se pak nazývají řádkové elementární transformace matice. Příklad. Řešte soustavu x1 + 2x2 + x3 3x1 + x2 − 2x3 4x1 − 3x2 − x3 2x1 + 4x2 + 2x3
=2 =1 =3 =4
Její rozšířená matice je
1 2 1 3 1 −2 4 −3 −1 2 4 2
2 1 3 4
po úpravách R21 (−3), R31 (−4), R41 (−2) dostaneme
1 2 1 0 −5 −5 0 −11 −5 0 0 0
2 −5 −5 0
dělíme-li druhý řádek číslem −5 a vynecháme-li nulový řádek, máme
1 2 1 1 1 0 0 −11 −5
2 1 −5
a konečně po úpravách R32 (11), R3 ( 61 ) dostaneme redukovaný tvar
1 2 1 0 1 1 0 0 1 28
2 1 1
a odtud buď vypočteme podle věty ?? jediné řešení o složkách x3 = 1, x2 = 0, x1 = 1 nebo ještě úpravami R23 (−1), R13 (−1), R12 (−2) dostaneme
1 0 0 0 1 0 0 0 1
1 0 1
odkud si složky řešení rovnou přečteme, neboť ekvivalentní soustava je x1 = 1, x2 = 0, x3 = 1. Jediným řešením je tedy vektor (x1 , x2 , x3 ) = (1, 0, 1). Příklad. Řešte soustavu x1 + 2x2 − 3x3 − 4x4 = 6 x1 + 3x2 + x3 − 2x4 = 4 2x1 + 5x2 − 2x3 − 5x4 = 10 Provedeme-li hned úpravy R21 (−1) a R31 (−2), máme
1 2 −3 −4 4 2 0 1 0 1 4 3
6 −2 −2
po úpravě R32 (−1) máme
1 2 −3 −4 4 2 0 1 0 0 0 1
6 −2 0
Protože počet rovnic v redukované soustavě je h = 3 a počet neznámých je n = 4 dostáváme nekonečně mnoho řešení závislých na n − h = 1, tj. na jednom parametru. Složky řešení jsou x4 = 0, x3 = u, x2 = −2−4u, x1 = 10+11u a obecné řešení je čtveřice (10 + 11u, −2 − 4u, u, 0). Volíme-li za parametr u konkrétní číslo, např. u = 1, dostaneme určité partikulární řešení, v našem případě (21, −6, 1, 0). Příklad. Řešte soustavu x1 + x2 + 2x3 + x4 = 5 2x1 + 3x2 − x3 − 2x4 = 2 4x1 + 5x2 + 3x3 = 7 29
Řešení. Provedeme-li hned úpravy R21 (−2) a R31 (−4), máme
1 1 2 1 0 1 −5 −4 0 1 −5 −4
5 −8 −13
a po úpravě R32 (−1) dostaneme soustavu, která má neřešitelnou poslední rovnici 0 · x1 + 0 · x2 + 0 · x3 + 0 · x4 = −5 a tedy daná soustava nemá řešení.
3.3
Cvičení
Gaussovou eliminací řešte soustavy rovnic: 3x1
2x 1. 1 x1 x1
−2x2 −5x3 + x4 −3x2 + x3 +5x4 +2x2 −4x4 − x2 −4x3 +9x4
= 3 = −3 = −3 = 22 (−1, 3, −2, 2)
2.
x1 2x1
3x
1 2x 1
x1
+2x2 +3x3 +4x4 +5x5 +3x2 +7x3 +10x4 +13x5 +5x2 +11x3 +16x4 +21x5 −7x2 +7x3 +7x4 +2x5 +4x2 +5x3 +3x4 +10x5
= 2 = 12 = 17 = 57 = 7
(3, −5, 4, −2, 1)
3.
5x1 +2x2 −7x3 +14x4 5x1 − x2 +8x3 −13x4 +3x5 10x1 + x2 −2x3 +7x4 − x5 15x1 +3x2 +15x3 +9x4 +7x5 2x1 − x2 −4x3 +5x4 −7x5
= 21 = 12 = 29 = 130 = −13
(2, −3/2, 4, 3, 5/2) 30
2x1
4.
+7x2 +3x2 +5x2 +18x2
x1 x1 5x1
+3x3 + x4 +5x3 −2x4 −9x3 +8x4 +4x3 +5x4
= 5 = 3 = 1 = 12
−3x2 +2x3 − x4 −2x2 + x3 −3x4 − x2 −5x4 −3x2 + x3 −8x4
4x1
3x1 2x 1 5x1
5.
(6 − 26u + 17v, −1 + 7u − 5v, u, v)
6.
2x1
4x1 2x1 x1
+5x2 +3x2 +3x2 +8x2
−8x3 −9x3 −5x3 −7x3
= 8 = 9 = 7 = 12
8.
6x1 4x1
u, v,
10.
9x
1 2x 1
7x1
+2x2 +3x2 + x2 +2x2 + x2
+2x3 +2x3 +4x3 +3x3 +6x3
x1 + x2 2x1 +2x2 11. 3x1 +3x2 2x1 +2x2
12.
2x1
6x1
6x1
4x1
Nemá
3x1
−2x2 +5x3 +4x4 = 2 6x1 −4x2 +4x3 +3x4 = 3 9x1 −6x2 +3x3 +2x4 = 4
− x2 +3x3 −7x4 = 5 −3x2 + x3 −4x4 = 7 −2x2 +14x3 −31x4 = 18
34u − 17v − 29 16u − 8v, −16 , 5 5
3x1 2x1
8 7 6 1
(u, v, 6 − 15u + 10v, −7 + 18u − 12v)
(3, 2, 1) 2x1
7.
= = = =
+2x4 +5x4 −5x4 +4x4 − x4
= = = = =
9.
9x1
−3x2 +5x3 +6x4 = 4 6x1 −2x2 +3x3 + x4 = 5 3x1 − x2 +3x3 +14x4 = −8
u, v, 2 −
9 3 1 27 u + v, −1 + u − v 13 13 13 13
2 3 1 5 7
−6 + 8u 1 − 13u 15 − 6u , , ,u 7 7 7
+3x3 −2x4 +4x3 − x4 +5x3 −2x4 +8x3 −3x4
− x2 + x3 +2x4 −3x2 +2x3 +4x4 −3x2 +4x3 +8x4 −2x2 + x3 + x4
+3x5 +3x5 +3x5 +9x5
= = = =
1 2 1 2
Nemá +3x5 = +5x5 = 13x5 = +2x5 =
2 3 9 1
(u, v, −1 − 8u + 4v, 0, 1 + 2u − v) 31
13.
6x1
3x1
3x1
9x1
+4x2 +5x3 +2x4 +3x5 +2x2 +4x3 + x4 +2x5 +2x2 −2x3 + x4 +6x2 + x3 +3x4 +2x5
= 1 = 3 = −7 = 2
(u, v, 13, 19 − 3u − 2v, −34)
x1 3x1 14. x1 2x1
+2x2 +6x2 +2x2 +4x2
6x1
4x 15. 1 4x 1 2x1
+3x3 +5x3 +7x3 +2x3
−2x4 + x5 −4x4 +3x5 −4x4 + x5 −3x4 +3x5
= 4 = 5 = 11 = 6
25 15 9 u, v, − − u − 2v, − − 2u − 4v, − − 2u − 4v 2 2 2
+3x2 +2x3 +2x2 + x3 +2x2 +3x3 + x2 +7x3
+3x4 +4x5 +2x4 +3x5 +2x4 + x5 +3x4 +2x5
= = = =
5 4 0 1
4 2 14 7 4 2 u, v, u + v, − u − v − 1, u + v + 2 3 3 3 3 3 3
32
Kapitola 4 Matice (I. část) 4.1
Okruh matic
Buďte m, n přirozená čísla. Pak libovolné zobrazení A množiny všech uspořádaných dvojic (i, j) přirozených čísel takových, že 1 ≤ i ≤ m, 1 ≤ j ≤ n do množiny reálných čísel se nazývá reálná matice o m řádcích a n sloupcích neboli matice typu m × n. Hodnota přiřazená maticí A k uspořádané dvojici (i, j) se značí aij a říká se jí prvek matice A ležící v i-tém řádku a j-tém sloupci. Matici A zapisujeme ve tvaru obdélníku
A =
a11 a21 .. .
a12 a22 .. .
... ... ...
a1n a2n .. .
am1 am2 . . . amn
nebo symbolicky pouze pomocí jednoho prvku A= kaij k. Pro matice užíváme také závorek kulatých. Matice ze samých nul se nazývá nulová a značí se 0. Matici typu m × 1 nazýváme sloupcový aritmetický vektor o m složkách; matici typu 1 × n nazýváme řádkový aritmetický vektor o n složkách. Matice typu n × n se nazývá čtvercová řádu n. Ve čtvercové matici prvky a11 , a22 , . . . , ann tvoří hlavní diagonálu a prvky a1n , a2,n−1 , . . . , an1 tvoří vedlejší diagonálu. Má-li čtvercová matice mimo hlavní diagonálu samé nuly, nazývá se diagonální. Má-li diagonální matice na diagonále týž prvek, nazývá se skalární a je-li ten prvek roven 1, pak je to jednotková matice, značí se E. Z rovnosti zobrazení plyne definice rovnosti dvou matic. Klademe A = B, 33
jsou-li obě matice téhož typu, např. m × n, to znamená, že mají týž definiční obor a dále platí aij = bij pro každé i, j. Pro libovolné matice typu m × n definujeme operaci sčítání matic A + B = kaij + bij k Například
1 2
3 4
5 6
+
7 8
6
8
=
10 12
Věta 7 Sčítání matic je operace komutativní, asociativní, má neutrální prvek, a to 0 a pro každou matici existuje matice opačná. To znamená, že pro všechny matice A, B, C typu m × n platí (a) A + B = B + A (b) (A + B) + C = A + (B + C) (c) A + 0 = A (d) Existuje matice −A taková, že A + (−A) = 0 Důkaz. Pro libovolné matice A, B, C platí A + B = kaij + bij k = kbij + aij k = B + A neboť sčítání reálných čísel je komutativní. Podobně (A + B) + C = k(aij + bij ) + cij k = kaij + (bij + cij )k = A + (B + C) neboť sčítání reálných čísel je asociativní. Konečně, zřejmě A + 0 = A a pro −A = k − aij k je A + (−A) = 0. Sčítání neboli adice matic je s hlediska tzv. obecné algebry tzv. binární operací. Podle věty ?? je adice matic na množině všech obdélníkových matic téhož typu asociativní, má nulu a ke každému prvku existuje prvek opačný. V obecné algebře se množina s jednou binární operací takových vlastností nazývá grupa. Vzhledem k tomu, že naše operace je ještě komutativní, mluvíme o komutativní nebo abelovské grupě. Poslední větu lze tedy stručně shrnout takto: Matice téhož typu tvoří aditivní abelovskou grupu. Poznamenejme, že
34
teorie grup patří k nejrozvinutějším partiím moderní algebry. Za její zakladatele jsou považováni Francouz Galois (Evariste, 1811–1832) a Nor Abel (Niels Henrik, 1802–1829). Pro matici A = kaij k definujeme násobení reálným číslem — skalárem takto: k · A = kk · aij k. Výpočtem, podobně jako v důkazu věty ??, snadno ověříme následující tvrzení: Věta 8 Násobení matice skalárem má na aditivní grupě matic vlastnosti: (1) k · (A + B) = k · A + k · B (2) (k + l) · A = k · A + l · A (3) k · (l · A) = (kl) · A (4) 1 · A = A pro všechny matice A, B téhož typu a libovolná reálná čísla k, l. O dvou maticích řekneme, že jsou násobitelné , jestliže jejich typy na sebe „navazujíÿ, tzn., že například matice A je typu m × n a matice B je typu n × p. Pro dvě násobitelné matice definujeme součin takto: A·B=k
n X
aij bjk k = kai1 b1k + ai2 b2k + · · · + ain bnk k
j=1
Slovy říkáme stručně, že násobíme i-tý řádek matice A k-tým sloupcem matice B. Například
a
11
a21
a31
a12 a22 a32
b
11
·
b21
b12 b22
a b +a b 12 21
11 11
= a21 b11 + a22 b21
a31 b11 + a32 b21
a11 b12 + a12 b22 a21 b12 + a22 b22 a31 b12 + a32 b22
Při násobení matic je třeba dbát na pořadí činitelů. V opačném pořadí nemusí být matice násobitelné a pokud jsou, pak mohou být oba součiny různé. Například
1 2
A·B =
3 4
0 0
·
1 1
2 2
=
4 4
6=
0 0
4 6
0 0
=
1 1
1 2
·
3 4
= B·A
V obecné algebře, vynecháme-li u aditivní grupy požadavek existence opačného prvku, mluvíme pak o monoidu. Vynecháme-li u monoidu požadavek existence nuly, pak mluvíme o pologrupě . U operace násobení neboli multiplikace mluvíme místo o nule o jedničce a místo o opačném prvku o prvku inverzním. 35
Věta 9 Množina všech reálných čtvercových matic téhož řádu je neabelovský monoid, kde jedničkou je matice jednotková E. Důkaz. Z vlastností reálných čísel plyne: (AB)C = |
X
aij bjk k · C = k
X X
j
=k
(
j
k
XX j
aij bjk )ckr k = k
aij (bjk cjr )k = k
k
X
aij
j
k
XX
X
(aij bjk )ckr k =
j
bjk ckr k = A(BC).
k
Zřejmě AE = EA = A pro každou matici A. Nekomutativnost násobení již byla dokázána nahoře pomocí příkladu. Zase pomocí výpočtu lze snadno dokázat: Věta 10 Pro sčítání a násobení matic platí zákony distributivní: (a) A(B + C) = AB + AC (b) (A + B)C = AC + BC jsou-li matice takových typů, aby byly příslušné operace proveditelné. Při násobení matic může nastat taková situace, se kterou jsme se na střední škole, kde se počítá pouze s čísly, nesetkali. Následující příklad bude zajímavý tím, že v něm budeme násobit dvě nenulové matice a přesto bude součinem matice nulová:
1 0
0 0
0 0
·
0 1
=0
V obecné algebře takovým maticím říkáme netriviální, česky nesamozřejmí dělitelé nuly. Je-li nějaká množina současně nosičem abelovské aditivní grupy i multiplikativní pologrupy a jsou-li obě operace vázány zákony distributivními, které jsou uvedeny nahoře, pak říkáme, že je to okruh. Okruh může, ale nemusí mít (nesamozřejmé) dělitele nuly nebo jedničku. Má-li okruh komutativní násobení, mluvíme o abelovském okruhu. Abelovský okruh s jedničkou, a bez (netriviálních) dělitelů nuly, se nazývá obor integrity . Obor celých čísel je typickým příkladem oboru integrity. Důsledkem našich vět je tedy: Věta 11 Reálné čtvercové matice téhož řádu tvoří okruh s jedničkou, který není oborem integrity. 36
Pamatujme si tedy, že pro matice platí některé jiné početní zákony, než pro čísla. Pro úplnost uvedeme ještě jeden pojem z obecné algebry. Okruh, jehož multiplikativní pologrupa nenulových prvků tvoří grupu, se nazývá těleso. Komutativní těleso se nazývá pole nebo komutativní těleso. Obory čísel racionálních, reálných nebo komplexních jsou příklady polí. Dá se ukázat, že tělesa nemají netriviální dělitele nuly. Pole jsou tedy obory integrity. Záměna řádků matice za stejnolehlé sloupce, neboli překlopení matice kolem hlavní diagonály, se nazývá transponování matice. Matici transponovanou k matici A = kaij k označme A0 = kaji k. Platí-li pro čtvercovou matici A0 = A, řekneme, že je symetrická. Snadno se zase výpočtem dokáže: Věta 12 Pro transponování matic platí: (1) (A + B)0 = A0 + B0 (2) (AB)0 = B0 A0 (3) (kA)0 = kA0 Vraťme se nyní k soustavě lineárních rovnic a11 x1 + a12 x2 + · · · + a1n xn = b1 a21 x1 + a22 x2 + · · · + a2n xn = b2 .. .. .. . . . am1 x1 + am2 x2 + · · · + amn xn = bm a ukažme si jak ji lze zapsat velice jednoduchým způsobem pomocí maticového počtu. Označme: A = kaij k matici soustavy, x = (x1 , . . . , xn )0 sloupec neznámých a b = (b1 , . . . , bm )0 sloupec pravých stran, pak soustavu zapíšeme maticově takto: Ax = b
4.2
Cvičení
Násobte matice: 1.
3 −2 5 −4
!
·
3 4 2 5
!
2.
a b c d
!
37
·
e f g h
!
−3 2 2 5 6 5 8 −4 3 2 5 −4 1 · 1 2 5 4. 6 9 −5 · 4 −1 3 3. −5 3 1 3 2 4 7 −3 9 6 5 7 8 6 9 −1 3 −4 −2 4 −3 5 7 4 5 · 5. −3 −2 1 3 4 5 6 2 1 1 2 −3 −1 2 1 2 3 4 7 −3 −4 6 −4 −5 2 3 4 5 · 6. 4 −3 −2 1 3 5 7 2 4 6 8 5 −6 −1 2 2 2 2 5 2 −2 3 ! ! 11 6 4 −3 5 −1 −5 3 2 −3 9 −6 · 7. · 8. 16 24 8 −8 9 2 −3 4 4 −6 6 −4 8 16 0 −16 7 6 −4 7 ! ! ! 4 3 −28 93 7 3 9. · · 7 5 38 −126 2 1 0 2 −1 70 34 −107 27 −18 10 2 −68 31 −17 10. −2 −1 · 52 26 · −46 3 −2 −1 101 50 −140 3 2 1 1 1 1 −1 7 −2 3 4 −5 −3 −4 4 0 3 4 11 11. · 5 1 4 −3 5 4 3 0 −16 −11 −15 14 22 2 9 8 !3 !5 !n !n 1 −2 4 −1 2 −1 a 1 12. 13. 14. 15. 3 −4 5 −2 3 −2 0 a 1 3 2 2 3 5 3 5 7 6 8
Najděte matice, které jsou komutativní s maticemi: 16.
1 2 3 4
!
17.
7 −3 5 −2
!
3 1 0 18. 0 3 1 0 0 3
19. Najděte hodnotu mnohočlenu f (x) = 3x2 − 2x + 5 pro matici:
1 −2 3 A = 2 −4 1 3 −5 2 38
20. Najděte hodnotu mnohočlenu f (x) = x3 − 7x2 + 13x − 5 pro matici:
5 2 −3 A = 1 3 −1 2 2 −1 Řešte rovnice: !
25.
26. 27. 29.
!
!
!
2 3 5 3 −2 −1 2 ·X= 22. X · = 4 5 9 5 −4 −5 6 ! ! ! −1 5 6 14 16 ·X· = −2 7 8 9 10 2 −3 1 −3 0 2 −4 2 7 · X = 10 −1 0 10 7 8 −8 3 0 5 3 1 X · 1 −3 −2 = −5 9 0 −2 15 0 −5 2 1 2 0 −2 9 7 6 2 −3 1 9 4 −5 2 X · 1 1 2 = 18 12 23 15 !11 1 1! 1 5 −7 !3 ! 2 −3 2 3 3 6 2 4 ·X= 28. X · = 4 −6 4 6 4 8 9 18 ! ! 4 6 1 1 ·X= 6 9 1 1
1 21. 3 3 23. 5 1 24. 3 2
Výsledky: 5 2 7 0
1.
5.
9.
!
2.
ae + bg af + bh ce + dg cf + dh
10 17 19 23 17 23 27 35 16 12 9 20 7 1 3 10
!
3.
6 4 0 −5 6. 7 7 9 8 1 ! 1 0 0 0 2 0 10. 0 2 0 11. 0 0 3 0 0 5 0
8 5 7 10
39
1 3 2 2 −10 7 7 0 0 2 0 0 3 0 0
5 −5 11 −22 10 0 4. 9 −27 9 −7 13 −17 0 0 ! 0 0 0 0 7. 8. 0 0 0 0 0 0 0 ! 0 13 −14 12. 0 21 −22 4
29 32 26 0 0 0 0
0 0 0 0
!
13. 15.
18.
21.
24.
27.
304 −61 14. 305 −62 ! an nan−1 16. 0 an a b c 0 a b 19. 0 0 a ! −1 −1 22. 2 3 6 4 5 2 1 2 25. 3 3 3 ! 2+3u 2
3+3v 2
u
v
!
!
1 0 2 −1 pro n sudé, pro n liché. 0 1 3 −2 ! ! u 2v u 3v 17. 3v u + 3v −5v u + 9v 21 −23 15 0 0 0 −13 34 10 20. 0 0 0 −9 !22 25 0 0 0 ! 3 −2 1 2 23. 5 −4 3 4 1 2 3 1 1 1 4 5 6 26. 1 2 3 7 8 9 2 3 1 ! 2−3u u 4 28. 29. Řešení neexistuje. v 9−3v 4
40
Kapitola 5 Vektorové prostory (I. část) 5.1
Definice a základní pojmy
Axiomatická definice vektorového prostoru. Abelovská aditivní grupa V se nazývá (reálný) vektorový prostor , její prvky se nazývají vektory a označíme je a, b, c,. . . , nulu označíme o, jestliže je dáno zobrazení, které každé uspořádané dvojici (k, a), kde k je reálné číslo (v této souvislosti nazývané skalár ) a a je vektor z V, přiřazuje vektor ka z V tak, že jsou splněny axiomy (i) k(a + b) = ka + kb (ii) (k + l)a = ka + la (iii) k(la) = (kl)a (iv) 1 · a = a Toto zobrazení se nazývá násobení vektoru reálným číslem nebo skalárem, vektor ka se nazývá reálný nebo skalární k-násobek vektoru a. Například z vět ?? a ?? plyne, že matice téhož typu tvoří vektorový prostor. Speciálně řádkové nebo sloupcové matice tvoří tzv. aritmetické vektorové prostory. Poznamenejme, že axiomatické definice jsou sice dosti abstraktní, avšak v tom spočívá jejich smysl. Axiomatické pojmy lze totiž modelovat mnoha rozmanitými způsoby. Tak například vektor lze interpretovat jako matici, speciálně jako řádkový nebo sloupcový aritmetický vektor, orientovanou úsečku, 41
n-ární lineární formu, polynom, případně jinou funkci apod. Všechny tyto pojmy pak lze podrobit společnému abstraktnímu studiu. Nyní uvedeme ukázku takového postupu. Z definičních vlastností — axiomů vektorového prostoru uvedeme nejprve jednoduché vlastnosti jeho aditivní abelovské grupy: (1) Má jedinou nulu o, neboť kdyby nulou byl ještě například prvek o0 , pak by platilo: o = o + o0 = o0 . (2) Ke každému vektoru je v ní jediný opačný vektor, neboť kdyby prvek a měl například dva opačné prvky −a, a0 , pak by platilo: −a = −a + o = −a + (a + a0 ) = (−a + a) + a0 = o + a0 = a0 . (3) −(−a) = a, slovy: opačný vektor k −a je vektor a, neboť −a + a = o. (4) −(a + b) = −a + (−b), neboť (a + b) + (−a + (−b)) = a + b + (−b) + (−a) = a + o + (−a) = a + (−a) = o. Místo a + (−b) píšeme a − b a mluvíme o rozdílu vektorů a,b. Věta 13 Ve vektorovém prostoru má násobení vektorů skalárem vlastnosti: Pro libovolná reálná čísla k, l a každé a, b ∈ V platí: (1) k = l implikuje ka = la (2) a = b implikuje ka = kb (3) 0a = ko = o (4) −(ka) = (−k)a = k(−a) (5) ka = o implikuje k = 0 nebo a = o (6) ka = kb, k 6= 0 implikuje a = b (7) ka = la, a 6= o implikuje k = l Důkaz. První dvě vlastnosti plynou z definice k -násobku, jakožto zobrazení R×V → V. Dále, pro každé reálné k a každé a ∈ V platí ka+0a = (k+0)a = k a, tedy 0a = o. Podobně ka + ko = k(a + o) = k a, tedy ko = o. Dále, jestliže ka = o, pak je buď k = 0 nebo k 6= 0, odtud pak plyne existence 42
reálného k −1 a platí o = k −1 o = k −1 (ka) = (k −1 k)a = 1a = a. Dále, jeli ka = kb, k 6= 0, pak k(a − b) = o, k 6= 0, odtud podle předchozího je a − b = o, tedy a = b. Analogicky se dokáže poslední vlastnost. Mějme vektory a, a1 , . . . , ar ∈ V a nechť existují skaláry ki takové, že a =
r X
ki ai
i=1
Potom řekneme, že vektor a je lineární kombinací vektorů ai s koeficienty ki . Jsou-li všechny koeficienty ki = 0, pak mluvíme o triviální lineární kombinaci. Zřejmě je vektor nulový triviální lineární kombinací libovolných vektorů. Jestliže je však nulový vektor netriviální lineární kombinací (aspoň jeden koeficient 6= 0) nějakých vektorů, pak o nich řekneme, že jsou lineárně závislé. Speciálně pro aritmetické vektory, řekněme sloupcové, při označení a1 = (aj1 ), a2 = (aj2 ), . . . , ar = (ajr ) pro j = 1, 2, . . . , n to znamená, že soustava lineárních homogenních rovnic, psána vektorově a1 x1 + a2 x2 + . . . + ar xr = o nebo podrobněji a11 x1 + a12 x2 + · · · + a1r xr = 0 a21 x1 + a22 x2 + · · · + a2r xr = 0 .. .. .. . . . an1 x1 + an2 x2 + · · · + anr xr = 0 má netriviální řešení. Jinak řekneme, že dané vektory jsou lineárně nezávislé. Poznamenejme, že v geometrickém vektorovém prostoru bývá zvykem dva (tři) lineárně závislé vektory nazývat kolineární (komplanární). Příklad. Vyjádřete vektor a = (4, −1, 3) jako lineární kombinaci vektorů b = (1, 0, 2), c = (−2, 1, 1). Hledáme tedy skaláry k ,l takové, aby kb+lc = a, tedy k(1, 0, 2) + l(−2, 1, 1) = (4, −1, 3). Řešíme tedy soustavu s maticí
1 −2 0 1 2 1
4 1 −2 0 1 −1 → 3 0 5
Odtud l = −1, k = 2 a tedy a = 2b − c. 43
4 −1 → −5
1 −2 0 1
4 −1
!
Věta 14 Vektory jsou lineárně závislé, právě když je mezi nimi podmnožina lineárně závislých vektorů. Obměněně: Vektory jsou lineárně nezávislé, právě když mezi nimi není podmnožina lineárně závislých vektorů. Důkaz . Buďte a1 , . . . , ar ∈ V, s ≤ r, a1 , . . . as lineárně závislé. Pak o=
s X
ki ai
i=1
kde aspoň jedno ki , i = 1, . . . , s je nenulové. Odtud o=
s X
ki ai + 0as+1 + · · · + 0ar
i=1
kde aspoň jedno ki , i = 1, . . . , s je nenulové. Jsou tedy všechny dané vektory lineárně závislé. Obrácené tvrzení je zřejmé. Věta 15 Nutnou a postačující podmínkou pro lineární závislost aspoň dvou vektorů je, aby mezi nimi byl aspoň jeden, který je lineární kombinací ostatních. Důkaz. Nechť i = 1, . . . , r a nechť vektory ai ∈ V jsou lineárně závislé. Pak o=
r X
ki ai
i=1
kde aspoň jedno ki , kupříkladu k1 , je nenulové. Pak a1 =
r X ki i=2
Obráceně, je-li a1 =
−k1
r X
ai
li ai
i=2
pak o = (−1)a1 +
r X i=2
44
li ai
Věta 16 Jsou-li aspoň dva nenulové vektory lineárně závislé, pak lze jeden z nich napsat jako lineární kombinaci předchozích. Důkaz. Buďte a1 , . . . , ar ∈ V nenulové a lineárně závislé. Pak o=
r X
ki ai
i=1
Označme m maximální index s vlastností km 6= 0. Z nenulovosti vektorů plyne m > 1, jinak o = k1 a1 , k1 6= 0, a1 6= o, spor. Platí am =
m−1 X i=1
ki ai −km
Poznámky: Vektor nulový je sám o sobě zřejmě lineárně závislý. Dále, pomocí ?? a ?? se někdy na první pohled pozná lineární závislost vektorů. Nejnápadnější je, když je mezi nimi o, dva stejné, dva opačné nebo vektor a jeho násobek.
5.2
Vektorový podprostor, báze, dimenze
Neprázdnou podmnožinu W reálného vektorového prostoru V nazveme podprostorem prostoru V , jestliže W je vektorovým prostorem vzhledem k operacím sčítání vektorů a násobení vektoru skalárem definovanými na V . Následující věta je jednoduchým kritériem pro určování podprostoru. Věta 17 Neprázdná podmnožina W reálného vektorového prostoru V je podprostorem ve V , právě když pro každé dva vektory a, b ∈ W a každé reálné číslo k je a + b ∈ W a ka ∈ W . Poznámky: O neprázdnotě množiny W se nejčastěji přesvědčíme tak, že ukážeme, že nulový vektor z V patří do W . Podmínky z předchozí věty vyjadřujeme slovy tak, že mluvíme o uzavřenosti podmnožiny W na nulový vektor a o uzavřenosti při sčítání vektorů a při násobení vektoru skalárem. Stručně řečeno, mluvíme o uzavřenosti podmnožiny W při všech operacích z V . Pro podprostor můžeme podmínku uzavřenosti při všech operacích upravit tak, že je uzavřen při libovolné lineární kombinaci dvou vektorů. To znamená, je-li V vektorový prostor, pak ∅ = 6 W ⊆ V je jeho podprostor, jestliže a, b ∈ W, k, l ∈ R ⇒ k a + l b ∈ W 45
Opravdu, při k = l = 0 je o ∈ W , při k = l = 1 je a + b ∈ W a při l = 0 je ka ∈ W . Každý prostor V má dva triviální podprostory, a to {o} a V . Dále, například skalární matice tvoří podprostor v prostoru diagonálních matic, ty zase tvoří podprostor v prostoru symetrických matic a ty zase tvoří podprostor v prostoru všech čtvercových matic téhož řádu. Věta 18 Průnik libovolného neprázdného systému podprostorů vektorového prostoru V je zase podprostorem ve V . Důkaz. Nechť I je neprázdná množina indexů, nechť Wi je podprostor ve T V pro každé i ∈ I a označme W = i∈I Wi . Protože nulový vektor patří do všech podprostorů, patří tedy také do W , je proto W 6= ∅. Libovolné vektory a, b ∈ W patří do všech podprostorů Wi , i ∈ I a proto pro libovolná reálná čísla k, l patří také vektor ka + lb do všech Wi , i ∈ I, tedy také vektor ka + lb patří do W , a W je tedy podprostor ve V . Buď M podmnožina vektorového prostoru V . Pak nejmenší podprostor (neboli průnik všech podprostorů) obsahující množinu M nazýváme podprostorem generovaným množinou M a značíme [M ]. Zřejmě [∅] = {o}. Je-li množina M konečná, M = {a1 , . . . , ar }, pak místo [{a1 , . . . , ar }] budeme psát krátce [a1 , . . . , ar ]. Věta 19 Množina všech lineárních kombinací neprázdné podmnožiny vektorů je podprostor daného vektorového prostoru, a to podprostor jimi generovaný. Důkaz. Nechť M je neprázdná podmnožina nosiče vektorového prostoru V , nechť W je množina všech lineárních kombinací vektorů z M , pak W je vektorový podprostor, neboť pro libovolné x, y ∈ W existují reálná čísla xi , yi a vektory ai ∈ M tak, že x=
r X
xi ai ,
y=
i=1
r X
yi ai
i=1
pro vhodné přirozené číslo r a nechť ještě k, l jsou libovolná reálná čísla, pak kx + ly = k
r X i=1
xi ai + l
r X
yi ai =
i=1
46
r X i=1
(kxi + lyi )ai ∈ W
Zřejmě a ∈ W , neboť pro každé a ∈ M je a = 1 · a ∈ W , tedy M ⊆ W. Zřejmě každý podprostor obsahující M musí obsahovat aspoň všechny lineární kombinace libovolných vektorů z M . Je tedy W minimální podprostor s vlastností M ⊆ W, proto W = [M ]. Platí tedy [a1 , . . . , ar ] = {a ∈ V ; ∃ki ∈ R : a =
r X
ki ai }
i=1
Poznamenejme, že podprostor [M ] se také nazývá lineární obal množiny M , neboť je nejmenším podprostorem, který obsahuje všechny lineární kombinace vektorů z M . Dále poznamenejme, že [S] = S, právě když S je podprostor. Pro podprostory S, W vektorového prostoru V klademe S + W = {x + y; x ∈ S, y ∈ W } a řekneme, že je to součet podprostorů S, W . Je-li S +W = V a S ∩W = {o}, řekneme, že V je direktním neboli přímým součtem podprostorů S, W . Věta 20 Součet podprostorů je zase podprostor daného vektorového prostoru a rovná se podprostoru, který je generován sjednocením daných podprostorů. Důkaz. Buďte S ,W libovolné podprostory vektorového prostoru V. Nejprve ukážeme, že S + W je podprostor. Pro libovolné x, y ∈ S + W existují a, b ∈ S, c, d ∈ W tak, že x = a + c, y = b + d a dále pro libovolné skaláry k, l platí kx + ly = k(a + c) + l(b + d) = (ka + lb) + (kb + ld) ∈ S + W, neboť S ,W jsou podprostory, a tedy ka + lb ∈ S, kb + ld ∈ W. Dále ukážeme, že S + W je podprostor v [S ∪ W ]. Pro každý vektor x ∈ S + W existují a ∈ S, b ∈ W tak, že x = a + b ∈ [S ∪ W ], neboť [S ∪ W ] obsahuje všechny lineární kombinace vektorů z S ∪W. Tedy S +W ⊆ [S ∪W ]. Obráceně S = S + {o} ⊆ S + W , W = {o} + W ⊆ S + W , odtud S ∪ W ⊆ S + W , tedy [S ∪ W ] ⊆ [S + W ] = S + W, neboť S + W je podprostor. Celkem S + W = [S ∪ W ]. Obsahuje-li vektorový prostor V konečnou (úplně uspořádanou) podmnožinu M takovou, že M generuje V , tj. [M ] = V, pak řekneme, že V má konečnou dimenzi. Jsou-li navíc všechny vektory z M lineárně nezávislé, pak řekneme, je to báze ve V . Počet prvků libovolné konečné báze nazýváme
47
dimenze nebo rozměr vektorového prostoru V , píšeme dim V . Budeme studovat pouze prostory konečné dimenze. Existují však i prostory s dimenzí nekonečnou nebo i takové, že nemají bázi. Je-li a1 , . . . , an báze ve V , pak, pro každé x ∈ V existují skaláry xi ∈ R takové, že x=
n X
xi ai
i=1
neboť báze generuje V . Kdyby ještě existovaly skaláry yi tak, že x = ni=1 yi ai , P P P pak x = ni=1 xi ai = ni=1 yi ai , tedy ni=1 (xi −yi )ai = o, odtud xi −yi = 0, tj. xi = yi pro každé i = 1, 2, . . . , n, neboť bázi tvoří lineárně nezávislé vektory. Klademe sa (x) = (x1 , . . . , xn ) a řekneme, že xi je i-tá souřadnice, sa (x) je souřadnicový vektor vektoru x a sa je souřadnicová funkce vzhledem k bázi a1 , . . . , an , stručně a-bázi. Odvodili jsme P
Věta 21 Bází jsou souřadnice vektoru určeny jednoznačně. Mějme dva reálné vektorové prostory V, W a nechť f je zobrazení V do W s vlastnostmi f (x + y) = f (x) + f (y),
f (kx) = kf (x)
pro všechny vektory x, y z V a pro každé reálné číslo k, pak řekneme, že f zachovává operace z V a že je to tzv. homomorfismus V do W . Protože homomorfismus vektorových prostorů vlastně zachovává lineární kombinace vektorů, říká se mu častěji lineární zobrazení. Bijektivní homomorfismus se nazývá izomorfismus. Existuje-li izomorfismus jednoho vektorového prostoru na druhý vektorový prostor, pak řekneme, že jsou izomorfní. Izomorfní vektorové prostory považujeme ze zobecňujícího algebraického hlediska za stejné. Věta 22 Každý vektorový prostor (konečné dimenze) je izomorfní s aritmetickým vektorovým prostorem. Důkaz. Buď V vektorový prostor s bází a1 , . . . , an . Ukážeme, že souřadnicová funkce sa je izomorfismus V na n-rozměrný aritmetický vektorový prostor. Podle ?? je sa zobrazení. Jeho injektivnost i surjektivnost, tedy bijektivnost je zřejmá. Ukažme, že zachovává všechny operace vektorového prostoru, tedy, že zachovává lineární kombinace. Nechť x, y ∈ V, k, l ∈ R a označme sa (x) = (x1 , . . . , xn ), sa (y) = (y1 , . . . , yn ) 48
Pak x = x1 ai + · · · + xn an , y = y1 a1 + · · · + yn an a odtud kx + ly = (kx1 + ly1 )a1 + . . . + (kxn + lyn )an tedy sa (kx + ly) = (kx1 + ly1 , . . . , kxn + lyn ) = k · sa (x) + l · sa (y) Proto je sa izomorfismus. Poznámka: Věta ?? má zvláštní důležitost. Říká, že až na izomorfismus nejsou jiné vektorové prostory konečné dimenze než aritmetické. Věta 23 Z každé množiny generátorů vektorového prostoru V 6= {o} lze vybrat bázi. Důkaz. Nechť [a1 , a2 , . . . , an ] = V. Není-li to báze, pak vektory a1 , a2 , . . . , an jsou lineárně závislé a podle ?? je mezi nimi jeden, například a1 , který je lineární kombinací ostatních. Proto [a2 , . . . , an ] = [a1 , a2 , . . . , an ] = V. Protože V 6= {o}, po konečném počtu kroků dostaneme lineárně nezávislé vektory, tedy bázi. Bázi lze tedy také definovat jako maximální množinu lineárně nezávislých vektorů. Zvláštní důležitost pro vektorové prostory konečné dimenze má tzv. věta Steinitzova. Věta 24 (Steinitz) Buď V reálný vektorový prostor, nechť nenulové vektory a1 , . . . , an ∈ V a nechť lineárně nezávislé vektory x1 , . . . , xr ∈ [a1 , . . . , an ]. Pak je n ≥ r a r generátorů podprostoru [a1 , . . . , an ] lze zaměnit za vektory x1 , . . . , xr , tj. při vhodném označení indexů je [x1 , . . . , xr , a1 , a2 , . . . , an−r ] = [a1 ., , , an ] Důkaz. Označme W = [a1 , . . . , an ]. Pn 1. krok: Protože o 6= x1 ∈ W, je x1 = i=1 ki ai pro vhodná reálná čísla ki , tedy W = [x1 , a1 , . . . , an ] a vektory x1 , a1 , . . . , an jsou nenulové a lineárně závislé. Podle ?? lze mezi nimi vybrat vektor, při vhodném označení indexů an , který je lineární kombinací předchozích. Odtud W = [x1 , a1 , . . . , an−1 ]. P 2. krok: Protože o 6= x2 ∈ W, je x2 = l1 x1 + ni=2 li ai pro vhodná reálná čísla li . Proto W = [x1 , x2 , a1 , . . . , an−2 ] a vektory x1 , x2 , a1 , . . . , an−2 jsou nenulové a lineárně závislé. Zase podle ?? existuje mezi nimi vektor, který 49
je lineární kombinací předchozích. Nemůže to být x2 , neboť x1 , . . . , xr jsou lineárně nezávislé. Je to tedy jeden z a1 , . . . , an−2 , při vhodném označení indexů an−2 . Pak W = [x1 , x2, , a1 . . . , an−3 ]. Po konečném počtu r kroků máme W = [x1 , . . . , xr , a1 , . . . , an−r ], tedy r ≤ n. Důsledky Steinitzovy věty: Věta 25 Každé dvě báze vektorového prostoru s konečným rozměrem mají týž počet vektorů. (Tím se také dodatečně zdůvodňuje, že dimenze vektorového prostoru je korektně definována.) Důkaz. Báze mají obě vlastnosti z ??, záměnou a-vektorů za x-vektory dostaneme rovnost r = n. Věta 26 Každý podprostor vektorového prostoru o stejné dimenzi se rovná celému prostoru. Věta 27 V n-rozměrném prostoru je každá (n + 1)-tice vektorů lineárně závislá a žádná (n − 1)-tice vektorů negeneruje celý prostor. Věta 28 Každá lineárně nezávislá množina vektorů se dá doplnit na bázi vektorového prostoru. Věta 29 K tomu, aby n vektorů v prostoru o dimenzi n tvořilo bázi, je nutné a stačí, aby buď byly lineárně nezávislé, nebo aby generovaly daný prostor. Všimněme si nyní nejednodušších, tzv. jednotkových bází, v některých konkrétních prostorech. Například jednotkovou bázi v prostoru Mmn matic typu m × n tvoří matice Eik , které definujeme tak, že mají samé 0 až na místo (i ,k ), kde je 1. Zřejmě XX i
aik Eik = kaik k = 0 ⇔ aik = 0 pro každé i, k
k
Tedy dim Mmn = mn. Speciálně, jednotkovou bázi v aritmetickém vektorovém prostoru Rn tvoří vektory e1 = (1, 0, 0, . . . , 0) e2 = (0, 1, 0, . . . , 0) 50
................ en = (0, 0, 0, . . . , 1) Souřadnicemi aritmetického vektoru v jednotkové bázi jsou tedy přímo jeho složky, neboť souřadnicovou funkcí při jednotkové bázi je identita. Dále určete například jednotkovou bázi a dimenzi prostoru symetrických matic, jeho podprostoru diagonálních matic a opět jeho podprostoru skalárních matic. Podobně určete dimenzi prostoru polynomů jedné proměnné stupně ≤ n; n-árních lineárních forem. Věta 30 (Grassmannův vzorec) Pro podprostory S, W konečné dimenze vektorového prostoru V platí dim (S + W ) = dim S + dim W − dim (S ∩ W ) Důkaz. Označme dim S = k, dim W = l, dim S ∩ W = m. Je-li S podprostor W nebo naopak, není co dokazovat. Jinak označíme u1 , u2 , . . . , uk bázi v S v1 , v2 , . . . , vl bázi ve W w1 , w2 , . . . , wm bázi v S ∩ W Podle Steinitze, záměnou vektorů dostaneme nové báze, které se mohou při vhodném označení vektorů napsat takto w1 , w2 , . . . , wm , um+1 , . . . , uk v S w1 , w2 , . . . , wm , vm+1 , . . . , vl ve W Označíme-li M = [w1 , w2 , . . . , wm , um+1 , . . . , uk , vm+1 , . . . , vl ], pak [M ] = [S ∪ W ] = S + W. Stačí tedy dokázat, že vektory z M jsou lineárně nezávislé, aby tvořily bázi v S + W. Odtud pak už vzorec plyne triviálně dosazením dimenzí m + (k − m) + (l − m) = k + l − m. Nezávislost M se dokáže takto. Položme m X i=1
ci wi +
k X
dj uj +
l X s=m+1
j=m+1
51
bs vs = o
Odtud
m X
k X
ci wi +
i=1
l X
dj uj =
(−bs )vs ∈ S ∩ W
s=m+1
j=m+1
neboť levá strana patří do S a pravá do W . Proto existují skaláry a1 , . . . , am tak, že l X
(−bs )vs =
s=m+1
m X
ai wi
i=1
Odtud z lineární nezávislosti vektorů báze ve W plyne bm+1 = . . . = bl = a1 = . . . = am = 0 Tedy z původní rovnosti zbyde m X
k X
ci wi +
dj uj = o
j=m+1
i=1
Odtud opět z lineární nezávislosti vektorů báze v S plyne c1 = c2 = . . . = cm = dm+1 = . . . = dk = 0 Takže vektory z M jsou lineárně nezávislé. Příklad. Najděte nějakou bázi podprostoru generovaného vektory a1 = (1, 0, 0, −1), a2 = (2, 1, 1, 0), a3 = (1, 1, 1, 1, ), a4 = (1, 2, 3, 4), a5 = (0, 1, 2, 3) a určete souřadnice ostatních vektorů v této bázi. Řešení: Položíme k1 a1 + k2 a2 + k3 a3 + k4 a4 + k5 a5 = o a řešíme tedy soustavu lineárních homogenních rovnic s maticí
1 0 0 −1
2 1 1 0
1 1 1 1
1 2 3 4
0 1 2 3
→
1 0 0 0
2 1 1 2
1 1 1 2
1 2 3 5
0 1 2 3
1 2 1 1 0 → 0 1 1 2 1
0 0 0 1 1
soustava má tedy nekonečně mnoho řešení závislých na dvou parametrech. Z redukované matice je vidět, že bázi podprostoru generovaného všemi danými vektory tvoří například vektory a1 , a2 , a5 . Zvolíme-li za parametry třetí a čtvrtou složku, tedy k3 = u, k4 = v, pak obecné řešení je tvaru 52
(u + v, −u − v, u, v, −v) Při volbě parametrů u = −1, v = 0 dostaneme partikulární řešení (−1, 1, −1, 0, 0) odtud a3 = −a1 + a2 a při volbě parametrů u = 0, v = −1 máme partikulární řešení (−1, 1, 0, −1, 1) odtud a4 = −a1 + a2 + a5 Je tedy vidět, že ve zvolené bázi a1 , a2 , a5 má vektor a3 souřadnice −1, 1, 0 a vektor a4 má souřadnice −1, 1, 1.
5.3
Cvičení
1. Najděte lineární kombinaci 3a1 + 5a2 − a3 vektorů: a1 = (4, 1, 3, −2) a2 = (1, 2, −3, 2) a3 = (16, 9, 1, −3) 2. Vypočtěte vektor x z rovnice: a1 + 2a2 + 3a3 + 4x = o kde
a1 = (5, −8, −1, 2) a2 = (2, −1, 4, −3) a3 = (−3, 2, −5, 4)
53
3. Vypočtěte vektor x z rovnice: 3(a1 − x) + 2(a2 + x) = 5(a3 + x) kde a1 = (2, 5, 1, 3) a2 = (10, 1, 5, 10) a3 = (4, 1, −1, 1) Rozhodněte, zda následující množiny vektorů jsou lineárně závislé: (
4.
a1 = (1, 2, 3) a2 = (3, 6, 7)
(
5.
a1 = (5, 4, 3)
7. a2 = (3, 3, 2) a3 = (8, 1, 3)
a1 = (4, −2, 6) a2 = (6, −3, 9)
6.
a1 = (4, −5, 2, 6)
a = (2, −2, 1, 3) 8. 2 a3 = (6, −3, 3, 9) a4 = (4, −1, 5, 6)
a1 = (2, −3, 1)
a2 = (3, −1, 5) a3 = (1, −4, 3) a1 = (1, 0, 0, 2, 5) a = (0, 1, 0, 3, 4) 9. 2 a3 = (0, 0, 1, 4, 7) a4 = (2, −3, 4, 11, 12)
Najděte všechny hodnoty k, pro které je vektor b lineární kombinací vektorů a1 , . . . , as :
10.
13.
a1 = (2, 3, 5)
a2 = (3, 7, 8)
a3 = (1, −6, 1) b = (7, −2, k) a1 = (3, 2, 5)
a2 = (2, 4, 7)
a3 = (5, 6, k)
b = (1, 3, 5)
11.
14.
a1 = (4, 4, 3)
a2 = (7, 2, 1)
a3 = (4, 1, 6) b = (5, 9, k) a1 = (3, 2, 6)
12.
a1 = (3, 4, 2)
a2 = (6, 8, 7) b = (9, 12, k)
a2 = (7, 3, 9)
a3 = (5, 1, 3)
b = (k, 2, 5)
Najděte všechny báze podprostorů generovaných vektory:
15.
a1 = (1, 2, 0, 0)
a2 = (1, 2, 3, 4) a3 = (3, 6, 0, 0)
16.
a1 = (1, 2, 3, 4)
a2 = (2, 3, 4, 5)
a3 = (3, 4, 5, 6)
a4 = (4, 5, 6, 7)
54
17.
a1 = (2, 1, −3, 1)
a2 = (4, 2, −6, 2) a3 = (6, 3, −9, 3) a4 = (1, 1, 1, 1)
18.
a1 = (1, 2, 3) a2 = (2, 3, 4)
a = (3, 2, 3)
3 a 4 = (4, 3, 4)
a5 = (1, 1, 1)
Ukažte, že vektory a1 , · · · , ar tvoří bázi a vypočtěte souřadnice vektoru x v této bázi:
19.
a1 = (1, 1, 1)
a2 = (1, 1, 2)
a3 = (1, 2, 3)
20.
x = (6, 9, 14)
a1 = (2, 1, −3)
a2 = (3, 2, −5)
a3 = (1, −1, 1)
21.
x = (6, 2, −7)
a1 = (1, 2, −1, −2) a2 = (2, 3, 0, −1)
a = (1, 2, 1, 4)
3 a 4 = (1, 3, −1, 0)
x = (7, 14, −1, 2)
Najděte nějakou bázi podprostoru generovaného danými vektory a určete souřadnice ostatních vektorů v této bázi:
22.
a1 = (5, 2, −3, 1)
a2 = (4, 1, −2, 3)
a3 = (1, 1, −1, −2)
a4 = (3, 4, −1, 2)
a1 = (2, −1, 3, 5) a2 = (4, −3, 1, 3)
a1 = (1, 2, 3, −4) a2 = (2, 3, −4, 1)
24. a3 = (2, −5, 8, −3) 23. a3 = (3, −2, 3, 4) a4 = (5, 26, −9, −12) a = (4, −1, 15, 17) 4 a = (3, −4, 1, 2) a = (7, −6, −7, 0) 5 5
Výsledky: 1. (1,4,-7,7). 2. (0,1,2,-2). 3. (1,2,3,4). 4 Nezávislé. 5. Závislé. 6. Nezávislé. 7. Závislé. 8. Závislé. 9. Nezávislé. 10. k = 15. 11. k libovolné. 12. k libovolné. 13. k 6= 12. 14. k neexistuje. 15. a1 , a2 nebo a2 , a3 . 16. Libovolné dva. 17. Čtvrtý s prvním, druhým nebo třetím. 18. Libovolná trojice kromě a1 , a2 , a5 nebo a3 , a4 , a5 . 19. (1,2,3). 20. (1,1,1). 21. (0,2,1,2). 22. Například při bázi: a1 , a2 , a4 je a3 = a1 − a2 . 23. Při bázi: a1 , a2 , a3 je a4 = 2a1 − 3a2 + 4a3 , a5 = a1 + 5a2 − 5a3 . 24. Při bázi: a1 , a2 , a5 je a3 = a1 − a2 + a5 , a4 = 3a1 + 4a2 − 2a5 .
55
Kapitola 6 Determinanty 6.1
Pořadí a permutace
Nyní budeme pracovat s konečnými množinami. Vždy vezmeme množinu {1, 2, . . . , n} pro vhodné přirozené n. Pořadím z prvků 1, 2, . . . , n nazveme libovolnou uspořádanou n-tici (k1 , . . . , kn ), ve které se každý z prvků vyskytuje právě jednou. Pořadí (1, 2, . . . , n) nazýváme základní. Dvojice čísel tvoří inverzi v pořadí, stojí-li větší číslo před menším. Počet inverzí v pořadí (k1 , . . . , kn ) označíme [k1 , . . . , kn ]. Řekneme, že pořadí je sudé, má-li sudý počet inverzí a přiřadíme mu znaménko = signum = sgn = +1, jinak je pořadí liché a má znaménko −1. Počet inverzí v pořadí určujeme tak, že sečteme počty inverzí s čísly 1, 2, . . . , n − 1, nebo si napíšeme pod základní pořadí dané pořadí, spojíme stejná čísla a spočítáme průsečíky spojnic. Například [3, 4, 2, 1, 5] = 3 + 2 + 0 + 0 = 5, tedy sgn (3, 4, 2, 1, 5) = −1. Už víme, že bijekce množiny na sebe se nazývá permutace. Dvojřádkový zápis permutace vypadá formálně tak, že se napíší dvě pořadí pod sebe. V prvním řádku jsou vzory, obvykle v základním pořadí, a pod nimi jejich obrazy ! ! ! 1 2 3 ... n i i ϕ= = = k1 k2 k3 . . . kn ki ϕ(i) 56
kde ϕ(i) = ki . Permutace je sudá a má znaménko +1, mají-li oba řádky tutéž paritu, jinak je lichá a má znaménko −1. Prvek nazýváme samodružný, jestliže je v nějakém zobrazení sám svým obrazem. Permutace, která má všechny prvky samodružné až na dva i,k se nazývá transpozice (výměna) prvků i ,k , značí se (i k ). Prvky i ,k tvoří tzv. vratnou neboli involutorní dvojici, neboť si vzájemně slouží jako vzor a obraz. Permutace, která má všechny prvky buď samodružné nebo patřící k nějaké vratné dvojici se nazývá involuce. Například osová souměrnost v rovině je involuce. Je zřejmé, že involuce jsou sami k sobě inverzní zobrazení. Věta 31 Transpozice mění znaménko pořadí. Důkaz. Pro sousedy: Provedeme-li v pořadí (k1 , ..., ki−1 , ki , ki+1 , ki+2 , . . . , kn ) transpozici (ki ki+1 ), tedy sousedů, dostaneme pořadí (k1 , . . . , ki−1 , ki+1 , ki , ki+2 , . . . , kn ) Počet inverzí prvků ki , ki+1 vzhledem ostatním prvkům se nezměnil. Záleží tedy pouze na tom, zda prvky ki , ki+1 tvořily inverzi, pak ovšem po výměně prvky ki+1 , ki inverzi netvoří a naopak. V každém případě se však změní znaménko pořadí. Pro nesousedy: Provedeme-li v pořadí (k1 , . . . , ks−1 , ks , ks+1 , . . . , ki−1 , ki , ki+1 , . . . , kn ) transpozici (ks ki ), s < i, tedy nesousedů, dostaneme pořadí (k1 , . . . , ks−1 , ki , ks+1 , . . . , ki−1 , ks , ki+1 , . . . , kn ) Tutéž transpozici však lze provést postupnou výměnou sousedů prvku ks s prvky stojícími mezi prvky ks , ki , pak vyměníme opět sousedy ks , ki a pak postupnou výměnou sousedů prvku ki se stejnými prvky, se kterými jsme měnili prvek ks . Celkový počet výměn sousedů je tedy lichý, proto se i nyní, podle první části důkazu, změní znaménko pořadí. Věta 32 Z n prvků lze napsat n! pořadí a lze je sřetězit tak, že každé následující dostaneme z předchozího pořadí jedinou transpozicí. Přitom lze začít libovolným pořadím. 57
Důkaz. Důkaz povedeme matematickou indukcí. Pro n = 1 : (1); n! = 1 n = 2 : (1, 2) 7→(12) (2, 1);
n! = 2
Předpokládejme, že pro některé přirozené číslo n věta platí. Vezměme prvky 0, 1, 2, . . . , n v počtu n + 1. Podle indukčního předpokladu lze z těchto n + 1 prvků napsat n! pořadí tvaru (0, k01 , ..., k0n ), která jsou sřetězena tak, že každé následující dostaneme z předchozího pořadí jedinou transpozicí. Přitom lze začít libovolným pořadím, které má na 0-tém místě číslo 0. V posledním z těchto pořadí zaměníme prvek 0 s následovníkem a zase podle indukčního předpokladu dostaneme řetěz délky n! napsaný z pořadí tvaru (k11 , 0, k12 , . . . , k1n ). Po n + 1 takových krocích dostaneme celkem (n + 1)n! = (n + 1)! pořadí z n + 1 prvků sřetězených tak jak bylo požadováno. Podle principu matematické indukce platí tedy tato věta pro každé přirozené číslo n. Z vět ?? a ?? plynou dva důsledky: Věta 33 Z n > 1 je polovina, tj. n!/2 pořadí (a také permutací) sudých a polovina lichých. Věta 34 Parita (třída) permutace se rovná paritě (třídě) počtu transpozic, na které lze danou permutaci rozložit.
6.2
Definice a vlastnosti determinantu
Název determinant zavedl francouzský matematik Cauchy (Augustin Luis, 1789–1857), který byl zakládajícím členem světoznámé školy Ecole polytechnique v Paříži. Idea determinantů má však počátek již v r. 1693 u Leibnitze (Gottfried Wilhelm, 1646–1716, narozen v Lipsku), dále v r. 1750 u Cramera (Gabriel, 1704–1752, Švýcar), Lagrange (Joseph Luis, 1736–1813, nar. v Turině a měl italsko-francouzský původ) a u Laplace (Piere Simon, 1749–1827, původem z Normandie, žil v Paříži). Japonec Seki Kova snad používal ideu determinantu už před rokem 1683 a maticová metoda v Číně se používala již za dynastie Sung.
58
DEFINICE: Buď Mn množina všech reálných čtvercových matic řádu n. Potom determinantem stupně n nazýváme zobrazení Mn → R : A = kaij k 7→ |A| = |aij | =
X
sgn ϕ
ϕ
n Y
aiϕ(i)
i=1
kde ϕ je libovolná permutace z prvků 1, 2, . . . , n. Součin n Y
aiϕ(i) = a1ϕ(1) a2ϕ(2) · · · anϕ(n)
i=1
který má n činitelů a každý z nich zastupuje právě jeden řádek a právě jeden sloupec matice A, se nazývá člen determinantu |A|; sgn ϕ, tj. znaménko permutace tvořené indexy činitelů členu, se nazývá znaménko členu. Determinant stupně n je pak součtem všech n! svých členů i s jejich znaménky. Značíme také |A| = det A = A. O matici A determinantu |A| často mluvíme také jako o determinantu, nedojde-li k nedorozumění. Například mluvíme o řádcích nebo o sloupcích, společně pak o řadách, determinantu |A|. Příklady: Determinant stupně n = 2 se vypočte podle definice tak, že od součinu prvků ležících na hlavní diagonále odečteme součin prvků ležících na vedlejší diagonále, tedy a 11 a21
a12 a22
= a11 a22 − a12 a21
Pro usnadnění výpočtu determinantu stupně n = 3 se používá tzv. Sarrusovo pravidlo: Buď sepíšeme první dva řádky pod determinant nebo napíšeme první dva sloupce za determinant a pak násobíme trojice prvků ve směru hlavní diagonály a dostaneme tři členy determinantu se znaménky +1 a pak násobením trojic prvků ležících ve směru vedlejší diagonály dostaneme zbývající tři členy se znaménky −1, tedy je-li |A| =
a11 a12 a13 a21 a22 a23 a31 a32 a33
pak napíšeme a11 a12 a13 a21 a22 a23 a31 a32 a33 59
a11 a12 a21 a22 a31 a32
a máme |A| = a11 a22 a33 + a12 a23 a31 + a13 a21 a32 − a13 a22 a31 − a11 a23 a32 − a12 a21 a33 Poznámky: 1. Determinanty stupně > 3 se počítají pomocí Laplaceova rozvoje. O tom budou pojednávat speciální odstavce. 2. Místo pojmu permutace lze k definici determinantu použít pojmu pořadí X |A| = (−1)[j1 ,...,jn ] a1j1 . . . anjn (j1 ,...,jn )
3. Z ?? plyne, že determinant stupně n > 1 má polovinu členů se znaménkem +1 a druhou polovinu se znaménkem −1. 4. Považujeme-li všechny prvky determinantu za proměnné, pak determinant stupně n je n2 -ární forma stupně n. 5. Považujeme-li pouze prvky jednoho sloupce za proměnné, pak determinant stupně n je lineární n-ární forma. 6. Má-li determinant pod nebo nad hlavní diagonálou samé nuly, rovná se svému hlavnímu členu, tj. a11 a22 . . . ann . Následující věty budou obsahovat vlastnosti determinantů. Věta 35 Transponováním (matice) se determinant nemění. Důkaz. Označíme |A| = |aij |, |A0 | = |aji | = |bij | = |B|. Platí |B| =
X ϕ
sgn ϕ
n Y i=1
biϕ(i) =
X ϕ
sgn ϕ
n Y i=1
aϕ(i)i =
X ϕ−1
sgn ϕ
−1
n Y
aiϕ−1 (i) = |A|
i=1
neboť sgn ϕ−1 = sgn ϕ a proběhne-li ϕ všechny permutace stupně n, pak ϕ−1 je proběhne také. Tato věta má důležitý důsledek: Platí-li nějaká vlastnost pro sloupce platí i pro řádky determinantu a naopak. V následujících větách bude tedy řeč
60
pouze o sloupcích, s tím, že je můžeme kdykoliv použít také na řádky. Sloupce budeme symbolicky značit jako vektory aj = (a1j , a2j , . . . , anj )0 ,
j = 1, 2, . . . , n
Z poznámky 5 plynou tři následující tvrzení. Věta 36 Determinant se rovná nule, má-li v jednom sloupci samé nuly. Tj. |o, a2 , . . . , an | = 0. Důkaz. Každá nula z toho nulového sloupce se dostane právě do jednoho členu. Podobně odvodíme následující dvě věty. Věta 37 Determinant násobíme skalárem tak, že tímto skalárem násobíme jeden jeho sloupec. k|a1 , . . . , an | = |ka1 , a2 , . . . , an | Věta 38 Jestliže má determinant v jednom sloupci mnohočleny o m členech, pak se rovná součtu m determinantů, které mají v tomto sloupci právě jeden člen onoho mnohočlenu (ostatní sloupce se opisují). Například |a1 + b, a2 , . . . , an | = |a1 , a2 , . . . , an | + |b, a2 , . . . , an | Věta 39 Determinant změní znaménko, vyměníme-li v něm dva sloupce. Důkaz. Označíme |A| = |aij | původní determinant, vyměníme v něm r -tý a s-tý sloupec a nový determinant označíme|B| = |bij | . Platí tedy |bij | = |aiα(j) |, kde α je transpozice (rs). Platí |B| =
X ϕ
sgn ϕ
n Y
biϕ(i) =
X
sgn ϕ
ϕ
i=1
=−
X ϕ
sgn ϕα
n Y i=1 n Y
aiα(ϕ(i)) =
X
−sgn ϕα
ϕ
n Y
ai(ϕα)(i) =
i=1
ai(ϕα)(i) = −|A|
i=1
neboť sgn ϕ = −sgn ϕα, podle ?? a proběhne-li ϕ všechny permutace stupně n, pak ϕα je proběhne také. 61
Věta 40 Determinant se rovná nule, má-li dva sloupce stejné. Důkaz. Zaměníme-li ty stejné sloupce, pak se jednak determinant zřejmě nezmění a jednak podle ?? změní znaménko. Takovou vlastnost má jediné reálné číslo, a to nula. Věta 41 Determinant se nezmění, přičteme-li k jednomu sloupci lineární kombinaci ostatních. Důkaz. Plyne to z vět ??, ?? a ?? takto |a1 , a2 , . . . , an−1 , an +
n−1 X
ki ai | = |A| +
i=1
= |A| +
n−1 X
n−1 X
|a1 , a2 , . . . , an−1 , ki ai | =
i=1
ki |a1 , a2 , . . . , an−1 , ai | = |A| + 0 = |A|
i=1
Věta 42 Postačující i nutná podmínka k tomu, aby se determinant rovnal nule je, aby měl sloupce lineárně závislé. Důkaz. Zatím dokážeme pouze to, že daná podmínka stačí k tomu, aby se determinant rovnal nule. Její nutnost dokážeme později, až pomocí hodnosti matice. Nechť tedy má determinant lineárně závislé sloupce, pak existuje jeden, například poslední, který je lineární kombinací ostatních. Pro vhodná ki tedy platí |A| = |a1 , . . . , an | = |a1 , . . . , an−1 ,
n−1 X i=1
6.3
ki ai | =
n−1 X
ki |a1 , . . . , an−1 , ai | = 0
i=1
Laplaceův rozvoj
Mějme determinant |A| stupně n > 1. Vybereme-škrtneme r < n řádků, například s indexy i1 < i2 < . . . < ir a r sloupců, například s indexy j1 < j2 . . . < jr . Prvky které stojí právě v těchto vybraných řadách, jsou tedy dvakrát škrtnuté, tvoří čtvercovou matici stupně r . Její determinant označíme ! M i1 . . . ir j1 . . . jr 62
(je-li r = 1, pak je to pouze prvek ai1 j1 = aij ) a řekneme, že je to subdeterminant nebo minor stupně r determinantu |A|. Prvky stojící v řadách, které jsme nevybrali, nejsou tedy vůbec škrtnuté, tvoří matici stupně n − r a je-li r > 1 její determinant značíme M∗
i1 . . . ir j1 . . . jr
!
a nazveme přidruženým minorem k původnímu minoru. Je-li r = 1, přidružený minor k prvku aij označíme Mij . Konečně klademe, je-li r > 1 A
i1 . . . ir j1 . . . jr
Pr ! = (−1) s=1 is +js M∗
i1 . . . ir j1 . . . jr
!
a řekneme, že je to algebraický doplněk v |A| k původnímu subdeterminantu. Při r = 1 klademe Aij = (−1)i+j Mij a řekneme, že je to algebraický doplněk k prvku aij . Věta 43 (Laplaceův rozvoj dle jednoho řádku) Determinant stupně n > 1 se rovná součtu součinů prvků vybraných z jednoho řádku s jejich algebraickými doplňky, tj. |A| = ai1 Ai1 + ai2 Ai2 + · · · + ain Ain Důkaz. (a) Nechť |A| má tvar
a11 a21 .. . an1
0 ... 0 a22 . . . a2n .. . . .. . . . an2 . . . ann = a11
X
=
X
(−1)[k1 ,...,kn ] a11 a2k2 · · · ankn =
(k1 ,...,kn )
(−1)[1,k2 ...,kn ] a2k2 · · · ankn = a11 A11
(1,k2 ...,kn )
63
(b) Nechť |A| má tvar
a11 .. .
a12 . . . .. .. . . 0 ... .. ... .
0 .. . an1 an2 . . .
i−1 = (−1)
0 a11 .. . an1
(i−1)+(j−1) = (−1)
a1,j−1 .. .
a1j .. .
0 .. . an,j−1
aij .. . anj an,j+1 . . .
0 ... a12 . . . .. ... . an2 . . . aij a1j .. . anj
0 a1,j−1 .. .
a1,j+1 . . . .. .. . . 0 ... .. ... .
aij a1j .. .
an,j−1 anj
0 ... a11 . . . .. ... . an1 . . .
0 a1n .. . ann
a1n .. . 0 .. . ann
0 ... a1,j+1 . . . .. ... . an,j+1 . . .
=
0 a1n .. . ann
=
= (−1)i+j aij Mij = aij Aij
dle (a). (c) Obecný determinant |A| si představíme jako součet n determinantů typu (b), které mají v i -tém řádku n-členy typu aij = 0 + 0 + . . . 0 + aij + 0 + . . . + 0 pro j = 1, 2, . . . , n Podle (b) a věty ?? pak platí (c). Důsledkem poslední věty je Věta 44 Součet součinů prvků vybraných z jednoho řádku determinantu s algebraickými doplňky prvků jiného řádku je roven nule, tj. n X
aij Akj = 0 pro i 6= k
j=1
Důkaz: Jakoby měl determinant stejný i-tý a k -tý řádek.
64
Věta 45 (Obecný Laplaceův rozvoj), dle řádků i1 , . . . , ir , bez důkazu: |A| =
X
M
i1 . . . ir j1 . . . jr
!A
i1 . . . ir j1 . . . jr
!
kde se sčítá přes všechny kombinace (j1 , . . . , jr ) r -té třídy z n čísel 1, 2, . . . , n. n Víme, že je jich r . Slovy: Determinant stupně n > 1 se rovná součtu součinů minorů vybraných všemi možnými způsoby z pevně zvolených r < n řádků s jejich algebraickými doplňky. Odtud plyne zase analogický důsledek: Věta 46 Jestliže r řádků determinantu |A| stupně n > r > 0 obsahuje ve více než n − r sloupcích samé nuly, pak je |A| = 0.
6.4
Praktický výpočet determinantů
Zásady: Determinanty více než 3-řadé počítáme pomocí Laplaceova rozvoje. Nejprve si však determinant upravíme tak, aby měl v některé řadě v absolutní hodnotě co nejmenší prvky (přičtením vhodné lineární kombinace rovnoběžných řad) nejlépe 0 a podle této řady jej pak rozvineme. Příklad. 2 3 −2 4 2 + 2(3) 3 + 2(−2) −2 + 2(1) 4 + 2(2) 3 −2 1 2 3 −2 1 2 = 3 2 3 4 3 − 3(3) 2 − 3(−2) 3 − 3(1) 4 − 3(2) −2 4 0 5 −2 4 0 5 8 −1 0 8 8 −1 8 3 −2 1 2 8 −2 = = = (−1)2+3 −6 −6 8 0 −2 −2 4 5 −2 4 0 5 8 + 8(−1) −1 8 + 8(−1) 8 −2 + 8(8) = − −6 + 8(8) −2 + 8(4) 4 5 + 8(4)
65
0 −1 0 8 62 = = − 58 30 4 37
=
58 62 = −(−1)1+2 (−1) 30 37
Příklad.
=
x y y .. .
1 y 0 x−y 0 0 .. .. . . 0 0
= ... x
y y x .. .
... ... ... .. .
y y y
y y y .. .
1 y y ... y 1 x y ... y = [x + (n − 1)y] 1 y x . . . y = . . . . .. .. .. . . ... 1 y y ... x x y ... y y ... 0 x − y ... 0 = [x + (n − 1)y](x − y)n−1 .. .. ... . . 0 ... x − y
x + (n − 1)y y y . . . x + (n − 1)y x y . . . x + (n − 1)y y x . . . .. .. .. . . . . . . x + (n − 1)y y y . . .
= [x + (n − 1)y]
y x y .. .
= −286
y y y .. .
Příklad. Vandermondův determinant: Vn (a1 , a2 , . . . , an ) = =
1 1 .. .
a21 . . . a22 . . . .. ... . a2n . . .
a1 a2 .. .
1 an
1 0 0 1 a2 − a1 a2 (a2 − a1 ) .. .. .. . . . 1 an − a1 an (an − a1 )
an−1 n
=
= n−2 an (an − a1 )
... 0 . . . an−2 (a 2 − a1 ) 2 .. .. . . ...
= (a2 − a1 )(a3 − a1 ) . . . (an − a1 )
66
an−1 1 an−1 2 .. .
1 1 .. .
a2 a3 .. .
1 an
a22 . . . a23 . . . .. .. . . a2n . . .
an−1 2 an−1 3 .. . an−1 n
=
= (a2 − a1 )(a3 − a1 ) . . . (an − a1 )Vn−1 (a2 , a3 , . . . an ) =
n Y
(ak − ai ) =
k>i=1
= [(a2 − a1 )(a3 − a1 ) . . . (an − a1 )][(a3 − a2 ) . . . (an − a2 )] . . . [(an − an−1 )] Poznamenejme, že první úprava spočívá v tom, že (n−1)-ní sloupec násobíme (−a1 ) a přičteme k n-tému, (n − 2)-hý sloupec násobíme (−a1 ) a přičteme k (n − 1)-nímu, atd., 1-ní sloupec násobíme (−a1 ) a přičteme k 2-hému. Pak determinant rozvineme podle prvního řádku a nakonec použijeme indukce.
6.5
Násobení determinantů
Věta 47 (O násobení determinantů) Pro každé dvě čtvercové matice téhož řádu je determinant jejich součinu roven součinu determinantů jednotlivých matic, tj. |AB| = |A| · |B|. Důkaz. Podle Laplaceova rozvoje podle prvních n řádků je a 11 . . . a |A| · |B| = n1 −1 . . . 0
. . . a1n 0 . .. .. . .. . . . . ann 0 . . . 0 b11 . .. .. . .. . . . . −1 b1n
. . . 0 . .. . .. . . . 0 A N A AB = = = N . . . b1n −E B −E . .. . .. . . . bnn 2
= (−1)(n+1)+···+2n+(1+2+···+n) | − E| · |AB| = (−1)n (−1)n |AB| = 2 −n
= (−1)n
|AB| = (−1)n(n−1) |AB| = |AB|
Nejprve jsme si matici rozdělili na čtvercové bloky o rozměrech n×n, pak jsme v tomto blokovém schématu násobili zprava první sloupec maticí B a přičetli ke druhému sloupci. Poslední matici jsme si znovu představili napsanou po prvcích a rozvinuli jsme ji podle posledních n řádků. Poznamenejme, že matice násobíme pouze „řádky × sloupceÿ, kdežto determinanty můžeme násobit ještě dalšími třemi způsoby, což plyne z toho, že determinant se transponováním nemění.
67
6.6
Cramerovo pravidlo
Věta 48 (Cramerovo pravidlo) Soustava n lineárních rovnic o n neznámých a11 x1 + a12 x2 + · · · + a1k xk + · · · + a1n xn = b1 a21 x1 + a22 x2 + · · · + a2k xk + · · · + a2n xn = b2 .. .. .. . . . an1 x1 + an2 x2 + · · · + ank xk + · · · + ann xn = bn s determinantem soustavy |A| = |aik | = 6 0 má jediné řešení o složkách xk =
|Ak | , kde k = 1, 2, . . . , n |A|
a kde |Ak | je determinant, který dostaneme z |A| záměnou k -tého sloupce za pravé strany rovnic. Tj. |Ak | = |a1 , . . . , ak−1 , b, ak+1 , . . . , an |, při označení aj = (a1j , a2j , . . . , anj )0 , b = (b1 , b2 , . . . , bn )0 . Důkaz. Každé řešení dané soustavy je i řešením libovolné lineární kombinace jejích rovnic. Opak platit nemusí, viz například triviální lineární kombinace. Utvořme, pro každé k , lineární kombinaci rovnic dané soustavy s koeficienty A1k , A2k , . . . , Ank , což jsou algebraické doplňky k prvkům z k-tého sloupce. Podle Laplaceova rozvoje a jeho důsledku bude |A|xk = |Ak | kde k = 1, 2, . . . , n. Odtud xk =
|Ak | |A|
kde k = 1, 2, . . . , n. Ověřme, že jsou to složky jediného řešení dané soustavy tím, že provedeme zkoušku dosazením do i -té rovnice ai1
|A1 | |A2 | |An | + ai2 + · · · + ain = |A| |A| |A|
68
1 vytkneme |A| a determinanty |Ak | pro k = 1, 2, . . . , n rozvineme podle k -tého sloupce, tam jsou ty pravé strany
|A1 | = b1 A11 + b2 A21 + · · · + bn An1 |A2 | = b1 A12 + b2 A22 + · · · + bn An2 .. .. .. . . . |An | = b1 A1n + b2 A2n + · · · + bn Ann a máme dále =
n n X X 1 (ai1 bj Aj1 + · · · + ain bj Ajn ) = |A| j=1 j=1
přerovnáme dle bs (viz soustavu rovností nahoře) =
n n n X X X 1 (b1 aij A1j + · · · + bi aij Aij + · · · + bn aij Anj ) = |A| j=1 j=1 j=1
odtud podle Laplaceova rozvoje a jeho důsledku zbyde pouze =
n 1 1 X aij Aij = bi bi |A| = bi |A| j=1 |A|
Příklad. Pomocí Cramerova pravidla řešte soustavu: 2x − 3y = 4 4x − 5y = 10 Řešení: Vypočteme nejprve determinant soustavy 2 −3 |A| = 4 −5
= −10 + 12 = 2
Dále vypočteme oba pomocné determinanty: 4 −3 |Ax | = = −20 + 30 = 10 10 −5
69
2 4 |Ay | = 4 10
= 20 − 16 = 4
Odtud x=
|Ax | 10 |Ay | 4 = = 5, y = = =2 |A| 2 |A| 2
Soustava má tedy jediné řešení (x, y) = (5, 2).
6.7
Cvičení
Určete počet inverzí v pořadích: 1. 2, 3, 5, 4, 1. 2. 6, 3, 1, 2, 5, 4. 3. 1, 9, 6, 3, 2, 5, 4, 7, 8. 4. 7, 5, 6, 4, 1, 3, 2. 5. 1, 3, 5, 7, . . . , 2n − 1, 2, 4, 6, 8, . . . , 2n. 6. 2, 4, 6, . . . , 2n, 1, 3, 5, . . . , 2n − 1. Následující permutace rozložte v součin nezávislých cyklů a v součin transpozic: 7. 9.
1 4 1 8
2 1 2 1
3 5 3 3
4 2 4 6
!
!
5 1 2 3 4 5 6 8. 3 6 5 1 4 2 3 ! ! 5 6 7 8 1 2 3 4 5 6 7 8 9 10. 5 7 4 2 5 8 9 2 1 4 3 6 7
Následující permutace rozložené na cykly napište dvouřádkově: 11. (1 5)(2 3 4) 12. (1 3)(2 5)(4) 13. (7 5 3 1)(2 4 6)(8)(9) Rozhodněte který z následujících součinů může být členem determinantu a určete jeho znaménko: 14. a43 a21 a35 a12 a54
15. a61 a23 a45 a36 a12 a54
16. a27 a36 a51 a74 a25 a43 a62
17. Vyberte hodnoty i, k tak, aby součin a62 ai,5 a33 ak,4 a46 a21 mohl být členem determinantu 6-tého stupně se znaménkem mínus. 18. Vyberte hodnoty i, k tak, aby součin a47 a63 a1,i a55 a7,k a24 a31 mohl být členem determinantu 7-tého stupně se znaménkem plus.
70
Vypočtěte determinanty:
19.
22.
25.
28.
31.
2 −5 0 1 1 1 1 2 1 1 1 1 7 −1 4 1 −1 1 1 −3 1 0 1 1 21. 20. 5 −9 1 1 0 1 2 7 1 1 −1 1 4 −6 1 1 1 0 1 2 1 1 1 −1 2 −5 3 −3 −5 −3 9 3 6 4 3 8 3 −4 7 5 2 4 −6 −5 8 2 7 −3 24. 23. 4 −9 2 −5 −7 8 5 5 4 −5 −3 −2 −3 2 −5 3 −4 3 5 −6 7 −8 −4 −5 3 −5 3 −5 −2 2 2 −4 3 −3 −2 −5 −3 −4 4 −5 3 7 4 4 2 5 4 6 27. 26. −5 4 −9 −3 7 7 −7 5 5 5 8 7 8 −8 2 −6 −3 2 5 −6 4 4 5 6 7 6 3 7 6 −5 3 2 2 2 8 4 9 −8 5 10 7 5 2 3 5 7 2 9 29. 30. 5 4 3 5 7 5 −8 5 8 5 3 7 5 6 5 4 −4 6 −5 4 7 8 −8 −3 7 3 2 6 8 −9 4 9 7 −2 7 3 5 −3 3 4
Pomocí Cramerova pravidla řešte soustavu: 2x + 3y + 5z
32. 34.
36.
= 3x + 7y + 4z = x + 2y + 2z = 4x − 3y + 2z = 6x − 2y + 3z = 5x − 3y + 2z = ax + y + z = 1 x + ay + z = 1 x + y + az = 1
10 3 3 −4 −1 −3
5x − 6y + 4z
33. 3x − 3y + 2z 4x − 5y + 2z 5x + 2y + 3z 2x − 2y + 5z 35. 3x + 4y + 2z (1 + a)x + y + z x + (1 + a)y + z 37. x + y + (1 + a)z
= = = = = = = = =
3 2 1 −2 0 −10 1 a a2
Výsledky: 1. 5. 2. 8. 3. 13. 4. 18. 5. n(n−1) 6. n(n+1) 7. (142)(35) 2 2 8. (163)(25)(4) 9. (182)(3)(467)(5) 10. (15)(2864)(397) 71
!
!
1 2 3 4 5 1 2 3 4 5 11. 12. 5 3 4 2 1 3 5 1 4 2 ! 1 2 3 4 5 6 7 8 9 13. 14. Může, se znaménkem mínus. 15. Může, 7 4 1 6 3 2 5 8 9 se znaménkem plus. 16. Nemůže. 17. i = 5, k = 1. 18. i = 6, k = 2. 19. -8. 20. -3. 21. -9. 22. 18. 23. 18. 24. 4. 25. 90. 26. 27. 27. 17. 28. -6. 29. -10. 30 100. 31. 150. 32. (3,-2,2). 33. (1,1,1). 34. (1,2,-1). 35. (2,-3,-2). 1 1 1 , a+2 , a+2 ). Pro a = 1 je 36. Pro a 6= 1, −2 má soustava jediné řešení: ( a+2 nekonečně mnoho řešení tvaru: (1 − u − v, u, v). Pro a = −2 není řešení. 2a−1 a3 +2a2 −a−1 2−a2 , a(a+3) , a(a+3) ). Pro a = 0, −3 37. Pro a 6= 0, −3 je jediné řešení ( a(a+3) není řešení.
72
Kapitola 7 Obecné řešení soustav lineárních rovnic 7.1
Hodnost matice
Hodnost nenulové matice se nazývá maximální stupeň nenulového subdeterminantu dané matice; dále definujeme, že nulová matice má hodnost nula. Máme-li matici A typu m×n a označíme-li její hodnost h(A), pak je h(A) ≤ min (m, n). Poznamenejme, že stačí zjistit, že všechny minory stupně h(A)+1 jsou rovny 0; že jsou pak rovny nule i minory vyšších stupňů, to už plyne z Laplaceova rozvoje. Věta 49 Hodnost matice se nemění transponováním matice a (ekvivalentními) úpravami (1)–(4) (soustavy rovnic) z věty ?? provedenými na řádky nebo na sloupce matice. Důkaz. (1), (2) a transponování: Výměnou řádků nebo násobením řádku nenulovým prvkem nebo transponováním se nemění nulovost nebo nenulovost subdeterminantů, a nemění se tedy ani hodnost matice. (3): V dané matici A přičtěme k i -tému řádku c-násobek k -tého řádku a dostaneme novou matici B. Označme h(A), h(B) hodnosti matic. Ukážeme, že všechny subdeterminanty v B stupně h(A) + 1 jsou rovny nule. Ty, které neobsahují i -tý řádek jsou rovny nule proto, že jsou to subdeterminanty stupně h(A) + 1 z A. Ty, které obsahují i -tý a s ním také k -tý řádek jsou rovny nule proto, že je lze napsat jako součet subdeterminantu matice A 73
stupně h(A) + 1, tedy nuly a násobku determinantu, který má jeden řádek násobkem jiného řádku, a je tedy také nula. Ty, které obsahují i-tý řádek a neobsahují k -tý lze napsat jako součet subdeterminantu matice A stupně h(A) + 1, tedy nuly a násobku determinantu stupně h(A) + 1, který se liší od subdeterminantu matice A pouze pořadím řádků, a je tedy také nula. Proto je h(B) ≤ h(A). Přičtením (−c)-násobku k -tého řádku k i -tému řádku v matici B dostaneme jako novou matici A. Odtud podobně jako před tím plyne h(A) ≤ h(B). Celkem je h(A) = h(B). (4): Vynecháním nulového řádku se nezmění hodnost triviálně. Věta 50 Podprostor generovaný řádky (sloupci) matice má dimenzi rovnu hodnosti matice. Jeho bázi lze vybrat z těch řádků (sloupců) kde leží nenulový subdeterminant jehož stupeň se rovná hodnosti. Důkaz. Mějme matici
A =
a11 .. .
. . . a1h . Ah ..
ah1 .. .
. . . ahh . . . .. . . . . amh . . .
am1
... .. . ... ...
a1n .. . ahn .. . amn
a předpokládejme, že má hodnost h. Pak všechny její subdeterminanty stupně h + 1 jsou rovny nule a aspoň jeden minor stupně h je nenulový. Bez újmy na obecnosti lze předpokládat, že je to minor, označíme jej Ah , z levého horního rohu. Podle jedné věty o determinantech jsou řádky determinantu Ah lineárně nezávislé, lze tedy v prvních h řádcích matice A získat samé nuly na prvních h místech pouze pomocí triviální lineární kombinace, a jsou tedy také tyto řádky v A lineárně nezávislé. K tomu, aby tvořily bázi prostoru vytvořeného všemi řádky stačí ukázat, že v případě h < m jsou ostatní řádky v A jejich lineárními kombinacemi. Rozlišíme několik případů: a) Pro h = n < m má soustava lineárních rovnic
x1 . Ah .. = xh
ai1 .. . aih
podle Cramera jediné řešení, neboť má determinant nenulový. Složky tohoto řešení jsou koeficienty hledané kombinace. 74
b) Pro h < n, h < m determinant Ah „ovroubímeÿ i -tým řádkem a s-tým sloupcem pro i = h + 1, . . . , m a s = h + 1, . . . , n. Máme
0 =
a11 . . . .. . Ah ah1 . . . ai1 . . .
a1h .. .
a1s .. .
ahh ahs aih ais
Označme c1 , . . . , ch složky řešení z bodu (a) a přičtěme v posledním determinantu lineární kombinaci prvních h řádků s koeficienty −c1 , . . . , −ch k poslednímu řádku. Pak
0 =
a11 . . . .. . Ah ah1 . . . 0 ...
a1h .. .
a1s .. .
ahh ahs 0 b
kde b = −(c1 a1s + · · · + ch ahs ). Rozvineme-li poslední determinant podle posledního řádku, máme Ah b = 0, kde Ah 6= 0, tedy b = 0. Odtud ais = c1 a1s + · · · + ch ahs Je tedy dimenze prostoru vytvořeného řádky matice A rovna její hodnosti. Poznamenejme, že nyní máme větu ?? o determinantech dokázánu v plném znění, tj.: Determinant rovná se nule, právě když má sloupce lineárně závislé. Dále poznamenejme, že hodnost matice můžeme nyní definovat také jako dimenzi prostoru vytvořeného jejími řádky nebo sloupci. Konečně poznamenejme, že podle důkazu poslední věty, části (b), lze hodnost matice počítat tzv. „vroubenímÿ. Poslední věta dává druhou možnost jak lze definovat hodnost matice: DEFINICE: Hodnost matice se rovná maximálnímu počtu lineárně nezávislých řádků nebo sloupců matice.
7.2
Kritérium řešitelnosti
Z Gaussovy eliminace a z posledního odstavce snadno plyne kritérium řešitelnosti soustav lineárních rovnic: 75
Věta 51 (Frobeniova) Soustava m lineárních reálných rovnic o n neznámých s hodností matice soustavy h a s hodností matice rozšířené h0 má řešení, právě když h = h0 . Je-li h = h0 = n, pak má soustava jediné řešení. Je-li h = h0 < n, pak má soustava nekonečně mnoho řešení závislých na n − h parametrech. Odtud ihned plyne Věta 52 Má-li soustava n lineárních rovnic o n neznámých nulový determinant soustavy a nenulový některý z determinantů které vzniknou z determinantu soustavy nahrazením některého sloupce pravými stranami, pak soustava nemá řešení. Neboť h < h0 = n.
7.3
Vlastnosti řešení soustav lineárních rovnic
Soustavu m lineárních rovnic o n neznámých zapíšeme nyní stručně Ax = b, kde A je matice soustavy, typu m × n, x je neznámý aritmetický sloupcový vektor o n složkách a pravá strana b je aritmetický sloupcový vektor o m složkách a řekneme, že Ax = o je k ní přiřazená homogenní soustava. Věta 53 Množina všech řešení dané soustavy homogenních rovnic tvoří vektorový prostor. Důkaz. Buďte u,v řešení soustavy Ax = o. Pak pro každé reálné k, l platí A(ku + lv) = kAu + lAv = ko + lo = o. Věta 54 Rozdíl dvou řešení soustavy lineárních rovnic je vždy řešením přiřazené homogenní soustavy. Důkaz. Nechť u,v jsou dvě libovolná řešení soustavy Ax = b. Pak A(u−v) = Au − Av = b − b = o. Věta 55 Sečteme-li libovolné řešení u soustavy Ax = b s libovolným řešením v přiřazené homogenní soustavy Ax = o, pak u + v je řešením soustavy Ax = b. 76
Důkaz. A(u + v) = Au + Av = b + o = b. Věta 56 Každé řešení soustavy Ax = b se dá napsat jako součet jednoho pevného partikulárního řešení té soustavy s jistým řešením přiřazené homogenní soustavy. Důkaz. Buď u libovolné řešení soustavy Ax = b a nechť p je její pevně zvolené partikulární řešení. Podle ?? je u − p = v jisté řešení soustavy Ax = o. Odtud u = p + v.
7.4
Homogenní soustava
Homogenní soustava Ax = o má vždy nulové řešení, kterému proto říkáme triviální řešení. Může se stát, že má pouze toto řešení, což není nijak zajímavé. Nastane-li druhá a poslední možnost, že má i netriviální řešení, pak už jich má samozřejmě nekonečně mnoho a podle ?? tato řešení tvoří vektorový prostor. Má-li soustava n neznámých a označíme-li h hodnost matice soustavy, pak obecné řešení závisí na volbě n−h parametrů. Volíme-li, například, postupně za jeden parametr jedničku a za ostatní nuly, pak dostaneme bázi toho prostoru, kterou nazýváme fundamentální systém řešení homogenní soustavy lineárních rovnic. Tento prostor má tedy dimenzi n − h. Je-li matice A čtvercová, pak lze říci, že homogenní soustava má netriviální řešení právě tehdy, když je determinant soustavy roven nule. V geometrii se často vyskytuje případ h = n − 1, který lze řešit pomocí determinantů takto: Mějme homogenní soustavu b11 x1 + · · · + b1n xn = 0 b21 x1 + · · · + b2n xn = 0 .. .. .. . . . bn−1,1 x1 + · · · + bn−1,n xn = 0 tedy maticově Bx = o. Víme, že její fundamentální systém řešení má jediný vektor. Označme Bk matici, kterou dostaneme z B vynecháním k -tého sloupce, k = 1, 2, . . . , n. Matice Bk je čtvercová a označíme-li |Bk | její determinant, pak vektor (|B1 |, −|B2 |, . . . , (−1)n+1 |Bn |) je partikulárním řešením dané soustavy. Opravdu, následující determinant má pro každé i = 1, 2, . . . , n 77
dva řádky stejné a je proto nulový. Rozvineme-li jej podle prvního řádku máme
bi1 b11 .. .
... ... .. .
bin b1n .. .
bn−1,1 . . . bn−1,n
= bi1 |B1 | + bi2 (−1)1+2 |B2 | + · · · + bin (−1)1+n |Bn | = 0
Obecné řešení pak je k · (|B1 |, −|B2 |, . . . , (−1)1+n |Bn |), a to se často vyjadřuje postupným poměrem |B1 | : (−1)|B2 | : · · · : (−1)1+n |Bn |. Například pro n = 3, h = 2, tedy pro dvě rovnice b11 x1 + b12 x2 + b13 x3 = 0 b21 x1 + b22 x2 + b23 x3 = 0 je zvykem obecné řešení vyjadřovat takto b 12 b22
b13 b23
b : 13 b23
b11 b21
b : 11 b21
b12 b22
kde se cyklicky zaměňují dvojice sloupců, začíná se druhým. Změna znaménka je u druhého determinantu vyjádřena transpozicí jeho sloupců.
7.5
Cvičení
Vypočtěte hodnost matic: 1 3 5 2 −1 3 −2 4 2 −1 −3 1 7 1. 4 −2 5 2. 5 1 −1 2 −1 1 8 2 7 7 9 4 3 −5 3 −1 3 2 5 8 6 −7 5 −3 2 3 4 3. 4. 4 3 −8 1 −3 −5 0 −7 1 4 3 7 −5 1 4 1 8 6 −1
78
−1 4 7 1 2 3 4 2 2 7 2 −5 4 −6
5.
25 75 75 25
31 94 94 32
24 19
49 40 7. 73 59
47 36
17 43 47 −67 53 132 98 6. 26 54 134 16 −428 20 48 17 36 72 −38 24 73 147 −80 8. 25 98 219 −118 31 71 141 −72 42
35 201 155 23 −294 86 1 1284 52 −28 −37 −7 12 13
45 11 39 61 13 50 32 −18 −11 19 −43 −55 29 −55 −68
Určete jak závisí hodnosti matic na paramatru a 9.
3 a 1 2
1 1 4 4 10 1 7 17 3 2 4 1
1 a −1 2 a 5 10. 2 −1 1 10 −6 1
Výsledky: 1. 2. 2. 3. 3. 3. 4. 2. 5. 3. 6. 2. 7. 3. 8. 2. 9. Pro a = 0 je hodnost 3, pro a 6= 0 je 4. 10. Pro a = 3 je hodnost 2, pro a 6= 3 je 3.
79
Kapitola 8 Matice (II. část) 8.1
Regulární, singulární, inverzní matice
Čtvercovou matici nazveme regulární, má-li nenulový determinant, jinak je singulární. Věta 57 V okruhu matic Mn jsou děliteli nuly právě všechny singulární matice. Důkaz. (a) Nechť matice A ∈ Mn je levým dělitelem nuly. Pak existuje matice B ∈ Mn taková, že AB = 0 a |B| = 6 0. Označme B = kb1 , . . . , bn k a nechť například b1 6= o. Platí 0 = AB = kAb1 , . . . , Abn k, tedy Ab1 = o, b1 6= o. Homogenní soustava Ax = o má tedy netriviální řešení, proto |A| = 0. (b) Obráceně, nechť |A| = 0, pak homogenní soustava Ax = o má netriviální řešení, např. u 6= o. Odtud Au = o. Položíme-li B = ku, o, . . . , ok, pak je AB = kAu, Ao, . . . , Aok = 0, B 6= 0; tedy A je levý dělitel nuly. (c) Nechť A je levý dělitel nuly, pak dle (a) je |A| = 0. Odtud |A0 | = |A| = 0. Tedy A0 je podle (b) levý dělitel nuly. Proto existuje B 6= 0 tak, že A0 B = 0, odtud transponováním dostaneme B0 A = 0, kde B0 6= 0, tedy A je pravý dělitel nuly. Označme RMn množinu všech reálných regulárních matic z Mn . Věta 58 Množina regulárních matic RMn obsahuje jednotkovou matici E, je uzavřena při násobení i při invertování, a tvoří tedy multiplikativní grupu. Důkaz. Zřejmě |E| = 1 6= 0, proto E ∈ RMn . 80
Dále, vezměme libovolné A, B ∈ RMn , pak 0 6= |A| · |B| = |AB|, proto je součin AB také regulární matice. Zbývá ukázat, že ke každé regulární matici existuje matice inverzní. Buď tedy A regulární matice a řešme rovnici AX = E. Označíme-li xk , resp. ek , k -tý sloupec neznámé matice X, resp. jednotkové matice E, pak pro každé k = 1, 2, . . . , n řešíme soustavu
Axk = ek =
0 1 k-řádek 0 .. .
0 . ..
0 která má nenulový determinant soustavy. Podle Cramera má tedy jediné řešení, označíme si je bk . Označíme-li a1 , . . . , an sloupce matice A a b1k , . . . , bnk složky sloupcového vektoru bk , pak je podle Cramera bik =
|a1 , . . . , ai−1 , ek , ai+1 , . . . , an | Aki = |A| |A|
kde Aki je algebraický doplněk k prvku aki z matice A; neboť ta jedna jediná jednička v ek stojí v k-tém řádku a i -tém sloupci čitatele a rozvineme-li determinant v čitateli dle i -tého sloupce dostane pouze Aki . Odtud se už snadno napíše řešení rovnice AX = E, a to
A−1
A11 |A| A12 |A|
= ...
1 = |A|
A21 |A| A22 |A|
.. .
n1 k1 . . . A|A| . . . A|A| n2 k2 . . . A|A| . . . A|A| . . .. . . .. . . . . Akn nn . . . |A| . . . A|A|
A1n |A|
A2n |A|
A11 A12 .. .
A21 . . . A22 . . . .. ... . A2n . . .
A1n
81
Ak1 . . . Ak2 . . . .. .. . . Akn . . .
=
An1 An2 .. . Ann
O poslední matici řekneme, že je adjungovaná k A a označíme ji adj A. Všimněte si, že platí adj A = adj kaik k = kAki k = kAik k0 . Adjungovanou matici tedy získáme tak, že prvky dané matice nahradíme jejich algebraickými doplňky a transponujeme. Dobře si tedy pamatujte, že pro regulární matici A platí vzorec adj A A−1 = |A| Ze vzorce dále plyne |A| · A−1 = adj A, násobíme-li zleva A, máme |A| · E = A · adj A. Determinant levé strany je ||A| · E| = |A|n a determinant pravé, podle věty o násobení determinantů, je |A·adj A| = |A| ·|adj A|. Odtud porovnáním plyne |adj A| = |A|n−1 . Tedy, uvědomíme-li si, že z determinantu se vytýká z každého sloupce zvlášť, máme −1
|A
adj A |A|n−1 1 |adj A| = = = |A|−1 = |= n n |A| |A| |A| |A|
Odtud A−1 ∈ RMn . Příklad. K matici
1 2 3 A= 1 3 4 1 4 3 vypočtěte inverzní. Řešení: Nejprve vypočteme determinant matice A, ten je |A| = −2. Matice je tedy regulární a existuje k ní matice inverzní. Dále vypočteme matici adjungovanou A11 adj A = A12
A13
3 4 = 4 3 1 = − 1 1 3 = 1 4
4 3
A21
A22 A23
= − 1 = 1 = −
3 3
A32
1 2 A33 1 4
−7 6 −1 0 −1 = 1 1 −2 1 82
2 3 2 3 A31 = 4 3 3 4 = − 1 = 1
1 3 1 4 2 3
=
Je tedy 7 1 −3 −7 6 −1 2 2 adj A 1 1 1 0 0 −1 − = = 1 = 2 2 |A| −2 1 −2 1 − 12 1 − 12
A−1
8.2
Elementární transformace matice, ekvivalence matic
Následující úpravy nazveme řádkové (respektive sloupcové) elementární transformace matic: (1) Výměna i -tého a j -tého řádku, značí se Rij . (2) Násobení i -tého řádku nenulovým skalárem k , značí se Ri (k). (3) Přičtení k -násobku i -tého řádku k j -tému řádku, značí se Rji (k). Pro sloupcové elementární transformace matic se použije místo písmene R písmeno S . O dvou reálných maticích A, B téhož typu řekneme, že jsou řádkově (sloupcově) ekvivalentní, jestliže existuje konečný počet řádkových (sloupcových) elementárních transformací, které převedou A v B. Používáme-li současně elementárních transformací obou druhů, pak mluvíme o ekvivalenci matic. Všechny tři vyjmenované druhy ekvivalence matic jsou zřejmě ekvivalencemi v obecném slova smyslu. Jsou to tedy relace reflexivní, symetrické a tranzitivní. Budeme se nyní zajímat o to, jak vypadá nejjednodušší neboli kanonický tvar matice vzhledem k relaci ekvivalence matic. Příklad.
1 2 −1 4 ∼ 1 2 −1 4 ∼ 2 4 3 5 R (−2) 0 0 5 −3 A= 21 R32 (−1) −1 −2 6 −7 R31 (1) 0 0 5 −3
1 −1 2 4 1 2 −1 4 ∼ ∼ 5 −3 5 0 −3 ∼ 0 0 0 S32 S2 ( 51 ) 0 0 0 0 0 0 0 0 83
1 ∼ 0 0
−1 5
2 4 1 ∼ 1 0 −3 0 S42 (3) 0 0 0 0
−1 5
2 1 0 0 0
17 5
∼
0 S2 (5) 0
S4 (5)
∼ 1 −1 2 17 1 0 0 0 S21 (1) ∼ 5 0 0 ∼ 0 0 5 0 0 S31 (−2) S2 ( 15 ) 0 0 0 0 0 0 0 0 S41 (−17)
1 0 0 0 ∼ 0 1 0 0 = 0 0 0 0
E2 0 0 0
!
Z tohoto výpočtu se snadno vidí, že platí Věta 59 Každá matice s hodností h je ekvivalentní právě s jednou maticí téhož typu tvaru Eh 0 0 0
!
kde Eh je jednotková matice řádu h a nuly 0 jsou nulové matice vhodných typů. O této matici říkáme, že je kanonickým tvarem dané matice vzhledem k ekvivalenci matic a volíme ji za reprezentanta třídy všech matic ekvivalentních s danou maticí. Typ a hodnost matice jsou tedy jedinými invarianty (neměnnými veličinami) relace ekvivalence matic. Každá třída ekvivalence matic téhož typu je tedy jednoznačně určena hodností svých matic. Proto je počet těchto tříd konečný a rovná se min(m, n), jedná-li se o matice typu m × n. Z ?? snadno plyne Věta 60 Vzhledem k řádkové ekvivalenci matic je jednotková matice kanonickým tvarem každé regulární matice. Přímým důsledkem je, že každá regulární matice je řádkově ekvivalentní s jednotkovou. Silnější tvrzení o řádkové ekvivalenci vyplývá snadno z toho, když si uvědomíme, že nejprve na danou regulární matici lze dělat řádkové elementární transformace od prvního sloupce „shora dolůÿ tak, že dostaneme matici, které má na hlavní diagonále samé jedničky a pod ní samé nuly a pak 84
opět řádkovými elementárními transformacemi prováděnými od posledního sloupce „zdola nahoruÿ vynulujeme všechny prvky nad diagonálou. Podobný důsledek platí o sloupcové ekvivalenci. Provedeme-li nějakou elementární transformaci na matici jednotkovou, pak dostaneme tzv. elementární matici té elementární transformace. Elementární matice budeme značit stejně jako elementární transformace. Z následujících výpočtů
0 0 1 a11 a12 a13 a31 a32 a33 R13 · A = 0 1 0 · a21 a22 a23 = a21 a22 a23 1 0 0 a31 a32 a33 a11 a12 a13
1 0 0 a11 a12 a13 a11 a12 a13 R2 (k) · A = 0 k 0 · a21 a22 a23 = ka21 ka22 ka23 0 0 1 a31 a32 a33 a31 a32 a33
1 0 0 a11 a12 a13 R23 (k) · A = 0 1 k · a21 a22 a23 = 0 0 1 a31 a32 a33
a11 a12 a13 = a21 + ka31 a22 + ka32 a23 + ka33 a31 a32 a33 snadno plyne tvrzení: Věta 61 Provést na matici nějakou řádkovou (sloupcovou) elementární transformaci je totéž, jako násobit ji zleva (zprava) elementární maticí té transformace. Věta 62 Matice A, B ∈ Mmn jsou: (a) řádkově ekvivalentní, (b) sloupcově ekvivalentní, (c) ekvivalentní, právě když existují regulární matice P ∈ Mm , Q ∈ Mn takové, že: (a) B = PA, (b) B = AQ, (c) B = PAQ. Důkaz. Podle ?? je matice P, resp. Q součinem elementárních matic řádkových, resp. sloupcových elementárních transformací, které převádějí A v B. Praktický význam pro výpočet inverzní matice má následující tvrzení Věta 63 Převedou-li řádkové elementární transformace matici A v E, pak tytéž transformace převedou E v A−1 . 85
Důkaz. Převedou-li řádkové elementární transformace R1 , . . . , Rk matici A v E, pak pro jejich elementární matice podle ?? platí E = Rk . . . R1 A Odtud vynásobením zprava maticí A−1 (A je regulární) máme EA−1 = Rk . . . R1 AA−1 tedy A−1 = Rk . . . R1 E Odtud je vidět, že tytéž řádkové elementární transformace převedou E v A. Při praktickém výpočtu se píší dvojice matic, začne se (A|E), končí se (E|A−1 ) a úpravy se dělají na obě matice současně. Příklad.
1 0 0 1 3 3 ∼ 0 1 0 0 1 0 R 0 0 1 0 0 1
1 3 3 (A|E) = 1 4 3 1 3 4
1 0 0 ∼ −1 1 0 R −1 0 1
1 0 0 7 −3 −3 ∼ −1 1 0 ∼ 0 1 0 = (E|A−1 ) R 0 0 1 −1 0 1 Důležité upozornění: Z výkladu je patrno, že je třeba používat buď pouze řádkové nebo pouze sloupcové transformace.
8.3
Cvičení
Vypočtěte inverzní matice k maticím: 1.
5.
9.
1 3 2 6 5 1 1 1 1
2 4
!
2.
5 7 3 4 −2 −3 1 1 1 −1 −1 1 −1 −1
3 4 5 7
!
!
a b cos α 3. 4. c d sin α 3 −4 5 2 7 3 1 7. 3 9 4 6. 2 −3 3 −5 −1 1 5 3 1 1 2 3 4 2 3 −1 1 2 10. 1 1 −1 1 −1 1 1 0 −2 −6 86
− sin α cos α
!
1 2 2 1 −2 8. 2 2 −2 1
Pomocí inverzních matic řešte znovu cvičení 21.–29. ke kapitole ??. Výsledky: −2 1 3/2 −1/2
!
!
7 −4 1 2. 3. ad−bc −5 3 ! 1 −1 1 cos α sin α 41 −34 5. −38 − sin α cos α 27 −29 24
1. 4. 7.
−7/3 2 −1/3 5/3 −1 −1/3 −2 1 1
22 −6 −26 5 20 0 2 4 −1 −5
−17 10. −1
!
d −b −c a −8 29 −11 −7 6. −5 18 1 −3 1 1 1 1 1 1 2 2 1 1 −1 −1 1 −2 8. 1/9 2 9. 1/4 1 −1 1 −1 2 −2 1 1 −1 −1 1 17 −13 −1 3
87
Kapitola 9 Vektorové prostory (II. část) 9.1
Změna báze a souřadnic
Nyní budeme předpokládat, že máme v daném abstraktním vektorovém prostoru dány dvě různé báze. Týž vektor zřejmě bude mít různé souřadnicové vektory vzhledem k těmto bázím. Zkoumejme nyní, jak bude záviset změna souřadnic na změně bází. Věta 64 Pro libovolné dvě báze a1 , . . . , an , b1 , . . . , bn vektorového prostoru V dimenze n existuje jediná regulární matice P řádu n taková, že kb1 , . . . , bn k = ka1 , . . . , an k · P Důkaz. Tvrzení plyne přímo z věty ?? o izomorfismu. Sloupce matice P jsou totiž souřadnicovými vektory vektorů b1 , . . . , bn v bázi a1 , . . . , an , tj. P = ksa (b1 ), . . . , sa (bn )k a z izomorfismu plyne, že tvoří bázi v aritmetickém vektorovém prostoru Rn . Řekneme, že P je matice přechodu od a-báze k b-bázi, je-li splněna podmínka z věty ??. Matice přechodu od a-báze k b-bázi má tedy ve sloupcích souřadnicové vektory vektorů b-báze vzhledem k a-bázi. Zřejmě P−1 je maticí přechodu od b-báze k a-bázi, neboť ka1 , . . . , an k = kb1 , . . . , bn k · P−1 tedy P−1 = ksb (a1 ), . . . , sb (an )k 88
Je-li A regulární matice, pak matici (A0 )−1 nazveme kontragradientní k A. Věta 65 Změna báze je kontragradientní ke změně souřadnic. Důkaz. Buď P matice přechodu od a-báze k b-bázi ve vektorovém prostoru V dimenze n. Buď x ∈ V libovolný vektor o souřadnicích x1 , . . . , xn v a-bázi a o souřadnicích y1 , . . . , yn v b-bázi. Potom platí
x
1
x = ka1 , . . . , an k ·
...
xn
y
1
.
x = kb1 , . . . , bn k · .. = ka1 , . . . , an k · P ·
yn
y1 .. . yn
Vzhledem k jednoznačnosti souřadnic v téže bázi (??) máme
x1 .. . xn
y
1
= P · ..
.
yn
Odtud násobením zleva P−1 a transponováním (y1 , . . . , yn ) = (x1 , . . . , xn )(P−1 )0 přitom platí kb1 , . . . , bn k = ka1 , . . . , an k · P Jak je tedy vidět, jsou obě změny navzájem kontragradientní.
9.2
Eukleidovské vektorové prostory
DEFINICE: Buď V reálný vektorový prostor, nechť ϕ : V 2 → R : (u, v) 7→ (u, v) = ϕ(u, v) je zobrazení splňující axiomy: (S1 )
(u + v, z) = (u, z) + (v, z) 89
(S2 ) (S3 ) (S4 )
(ku, v) = k(u, v) (u, u) > 0 pro u 6= o (u, v) = (v, u)
pro všechna u, v ∈ V, k ∈ R. Pak řekneme, že ϕ je skalární součin vektorů a V spolu s ϕ se nazývá eukleidovský vektorový prostor. Skalární součin vektorů u, v značíme (u,v). První dva axiomy říkají, že skalární součin zachovává lineární kombinaci vektorů pro první činitele, třetí axiom se nazývá kladná definitnost a poslední vyjadřuje komutativitu skalárního součinu. Příklady eukleidovských prostorů: 1. V aritmetickém vektorovém prostoru sloupcových, resp. řádkových vektorů je (u, v) = uv0 , resp. (u, v) = u0 v. V obou případech ve složkách je (u, v) = u1 v1 + . . . + un vn . Například pro u = (1, 2, 3), v = (0, 1, 0) je (u, v) = 1 · 0 + 2 · 1 + 3 · 0 = 2. 2. V geometrickém vektorovém prostoru je (u, v) = |u| · |v| · cos α kde α je úhel a |u|, |v| jsou délky vektorů u, v. Skalární součin je tedy definován pomocí délky a úhlu vektorů. V abstraktním vektorovém prostoru, tedy při axiomatické definici, je tomu naopak. 3. V prostoru reálných funkcí je (u, v) =
Z
1
f (x) · g(x)
0
Funkce jsou definovány na intervalu h0, 1i, kde jsou spojité, ohraničené a mají všechny derivace. Takovými funkcemi jsou například polynomy. V eukleidovském vektorovém prostoru má skalární součin vektorů následující jednoduché vlastnosti. Věta 66 Pro každé u, v, z ∈ V a každé k ∈ R platí: (1) (u, v + z) = (u, v) + (u, z) 90
(2) (u, k v) = k (u, v) (3) (o, u) = 0 = (u, o) Důkaz: (1) Podle axiomů (S1 ) a (S4 ) platí (u, v + z) = (v + z, u) = (v, u) + (z, u) = (u, v) + (u, z). (2) Podle axiomů (S2 ) a (S4 ) platí (u, kv) = (kv, u) = k(v, u) = k(u, v). (3) Podle axiomu (S2 ) platí (o, u) = (0v, u) = 0(v, u) = 0. q
V eukleidovském vektorovém prostoru klademe |u| = (u, u) pro každé u ∈ V a řekneme, že |u| je délka neboli norma vektoru u. Je-li |u| = 1, pak řekneme, že u je normovaný vektor. Dále řekneme, že α je úhel vektorů u,v, (u,v) . Dále řekneme, že vektory u,v jsou ortogonální nebo jestliže cos α = |u|·|v| kolmé, jestliže (u, v) = 0. Jsou-li navíc oba normované, pak řekneme, že jsou ortonormální. Věta 67 Délka vektoru má v eukleidovském vektorovém prostoru vlastnosti: Pro všechna u, v ∈ V, k ∈ R platí (1) |ku| = |k||u| (2) |u| > 0 pro u 6= o (3) |(u, v)| ≤ |u| · |v| (4) |u + v| ≤ |u| + |v| Poznamenejme, že vlastnost (2) se nazývá kladná definitnost, vlastnost (3) se nazývá Schwarzova nebo Cauchyova nebo také Buňakovského nerovnost a konečně vlastnost (4) q se nazývá trojúhelníková nerovnost. q √ q 2 Důkaz: (1) |k u| = (ku, ku) = k (u, u) = k 2 (u, u) = |k| · |u|. Dále, vlastnost (2) je zřejmá z definic. Ve Schwarzově nerovnosti pro lineárně závislé vektory, například u = kv, nastane rovnost, neboť |(u, v)| = |(k v, v)| = |k (v, v)| = |k||(v, v)| = |k||v||v| = |kv||v| = |u||v|, podle (1). Pro lineárně nezávislé vektory u,v je pro každé k ∈ R, ku + v 6= o, tedy z kladné definitnosti plyne 0 < (ku + v, ku + v) = (ku, ku) + (ku, v) + (v, ku) + (v, v) = 91
= k 2 (u, u) + k(u, v) + k(v, u) + (v, v) = k 2 |u|2 + 2k(u, v) + |v|2 Poslední kvadratický trojčlen (v proměnné k ) nemá tedy reálný kořen. Je známo, že to nastane právě tehdy, když má záporný diskriminant, tj. D = b2 − 4ac = 4(u, v)2 − 4|u|2 |v|2 < 0 tedy |(u, v)| < |u||v| Konečně, trojúhelníkovou nerovnost odvodíme pomocí Schwarzovy: |u + v|2 = (u + v, u + v) = (u, u) + 2(u, v) + (v, v) = = |u|2 + 2(u, v) + |v|2 ≤ |u|2 + 2|(u, v)| ≤ |u|2 + 2|u||v| + |v|2 = (|u| + |v|)2 Podle (2) lze odvozenou nerovnost |u + v|2 ≤ (|u| + |v|)2 odmocnit a dostaneme trojúhelníkovou nerovnost. Věta 68 V eukleidovském vektorovém prostoru jsou ortogonální nenulové vektory lineárně nezávislé. Důkaz. Nechť u 6= o 6= v, (u, v) = 0 a položme ku + lv = o. Pak 0 = (u, o) = (u, ku + lv) = k(u, u) + l(u, v) = k(u, u) + l · 0 = k(u, u), kde (u, u) 6= 0, tedy k = 0. Podobně se dokáže, že l = 0, a naše lineární kombinace je tedy triviální. Věta 69 (Gram-Schmidtův ortogonalizační proces) V eukleidovském vektorovém prostoru lze z libovolných lineárně nezávislých vektorů u1 , . . . , un získat nenulové ortogonální vektory v1 , . . . , vn takové, že generují týž podprostor, a to vzorci: v1 = u1 , vk = uk −
k−1 X i=1
(uk , vi ) · vi (vi , vi )
pro k = 2, 3, . . . , n
Důkaz. Buďte u1 , . . . , un lineárně nezávislé vektory z V . Důkaz provedeme matematickou indukcí. Položme v1 = u1 , pak [v1 ] = [u1 ], v1 6= o. Jeden nenulový vektor považujeme za ortogonální bázi jednorozměrného prostoru.
92
Indukční předpoklad: Předpokládejme, že už máme sestrojen ortogonální systém nenulových vektorů v1 , . . . , vk−1 tak, že generují týž podprostor, který si označíme W , tedy [v1 , . . . , vk−1 ] = [u1 , . . . , uk−1 ] = W Položme uk = vk + tk , kde tk ∈ W, vk ⊥ W Poznamenejme, že vk je ortogonální složka a tk je ortogonální průmět vektoru uk do podprostoru W . Platí vk = uk − tk . Dále výrok tk ∈ W implikuje tk =
k−1 X
ckj vj pro vhodná reálná čísla ckj
j=1
tedy vk = uk −
k−1 X
ckj vj
j=1
Dále výrok vk ⊥ W implikuje vk ⊥ vi pro každé i = 1, 2, . . . , k − 1, tj. 0 = (vk , vi ) = (uk −
k−1 X
ckj vj , vi ) =
j=1
= (uk , vi ) −
k−1 X
ckj (vj , vi ) = (uk , vi ) − cki (vi , vi )
j=1
neboť vzhledem k ortogonalitě jsou ostatní sčítanci nuly. Odtud cki =
(uk , vi ) (vi , vi )
pro i = 1, 2, . . . , k − 1
Platí [u1 , . . . , uk−1 , uk ] = [v1 , . . . , vk−1 , uk ] = [vk , . . . , vk−1 , vk + k−1 j=1 ckj vj ] = [v1 , . . . , vk−1 , vk ]. Podle principu matematické indukce věta platí pro libovolné přirozené číslo n. Důsledek: Normujeme-li ještě, tj. dělíme-li vektory jejich délkami vn v1 ,..., |v1 | |vn | P
plyne odtud, že v každém eukleidovském vektorovém prostoru nenulové konečné dimenze existuje ortonormální báze. Ta má v eukleidovských vektorových prostorech zvláštní důležitost. Příkladem ortonormálních bází jsou jednotkové báze. 93
Příklad. Ortogonalizujte vektory u1 = (1, 1, 1), u2 = (1, −2, 1), u3 = (1, 2, 3) Řešení: (i) v1 = u1 = (1, 1, 1) (ii) v2 = u2 − (iii) v3 = u3 −
(u2 ,v1 ) v (v1 ,v1 ) 1
= (1, −2, 1) − 03 v1 = (1, −2, 1)
(u3 ,v1 ) v (v1 ,v1 ) 1
−
(u3 ,v2 ) v (v2 ,v2 ) 2
= (1, 2, 3) − 63 (1, 1, 1) − 60 v2 = (−1, 0, 1)
Jestliže ještě normuje, obdržíme ortonormální bázi v R3 √ √ √ v1 = (1/ 3, 1/ 3, 1/ 3), |v1 | √ √ √ v2 = (1/ 6, −2/ 6, 1/ 6), |v2 | √ √ v3 = (−1/ 2, 0, 1/ 2) |v3 | Věta 70 Každý eukleidovský vektorový prostor dimenze n > 0 je izomorfní s aritmetickým reálným vektorovým prostorem Rn . Izomorfismem je souřadnicová funkce při libovolné ortonormální bázi. Důkaz. Stačí ukázat, že souřadnicová funkce při libovolné ortonormální bázi zachovává skalární součin vektorů. Je-li tedy a1 , . . . , an ortonormální báze daného eukleidovského vektorového prostoru V , x, y ∈ V libovolné vektory o souřadnicových vektorech sa (x) = (x1 , . . . , xn ), sa (y) = (y1 , . . . , yn ), pak (x, y) = = (x1 a1 + · · · + xn an , y1 a1 + · · · + yn an ) = = x1 y1 (a1 , a1 ) + x1 y2 (a1 , a2 ) + · · · + x1 yn (a1 , an )+ +x2 y1 (a2 , a1 ) + x2 y2 (a2 , a2 ) + · · · + x2 yn (a2 , an )+ ...................... +xn y1 (an , a1 ) + xn y2 (an , a2 ) + · · · + xn yn (an , an ) = = x1 y1 + · · · + xn yn = = (sa (x), sa (y)) 94
neboť
(
(ai , ak ) = δik =
0 pro i 6= k 1 pro i = k
Poznamenejme, že symbol δik se v tomto významu, jakožto právě uvedená dvojhodnotová funkce, používá v matematice běžně a říká se mu Kroneckerovo delta. Leopold Kronecker žil v letech 1823–1891 a patřil k tak zvané berlínské škole.
9.3
Cvičení
Dokažte, že následující dvojice množin vektorů tvoří báze a najaděte souvislost mezi souřadnicemi téhož vektoru v obou bazích: a1
1. a2 a3 a1 a 2 2. a 3 a4
= = = = = = =
(1, (2, (3, (1, (1, (1, (1,
2, 3, 7, 1, 2, 1, 3,
1) 3) 1) 1, 1, 2, 2,
b1
= (3, b2 = (5, b3 = (1, b1 = 1) b2 = 1) b 1) 3 = b4 = 3)
1, 4) 2, 1) 1, −6) ( 1, 0, 3, 3) (−2, −3, −5, −4) ( 2, 2, 5, 4) (−2, −3, −4, −4)
Ortogonalizujte: (1, 2,
2, −1) 3) 3. (1, 1, −5, (3, 2, 8, −7)
(1, 1, −1, −2)
4. (5, 8, −2, −3) (3, 9, 3, 8)
1, 3, −1) (7, 4, 3, −3) (1, 1, −6, 0) (5, 7, 7, 8)
(2,
5.
Výsledky: = 2y1 +y3 −y4 = −27y1 −71y2 −42y3 x2 = −3y1 + y2 −2y3 + y4 9y1 +20y2 +9y3 2. 1. x2 = x y1 −2y2 +2y3 − y4 3 = x3 = 4y1 +12y2 +8y3 x4 = y1 − y2 + y3 − y4 3. (1, 2, 2, −1), (2, 3, −3, 2), (2, −1, −1, −2) 4. (1, 1, −1, −2), (2, 5, 1, 3) 5. (2, 1, 3, −1), (3, 2, −3, −1), (1, 5, 1, 10) x1
x1
95
Kapitola 10 Analytická geometrie Analytická geometrie obsahuje pravidla, metody a postupy, kterými se geometrické úlohy mění na úlohy algebraické. Zavádějí se soustavy souřadnic a pomocí nich se geometrické úlohy řeší pomocí reálných čísel a algebraických rovnic. V analytické geometrii se používají převážně prostředky lineární algebry. Při studiu geometrických útvarů nás zajímají jednak polohové-afinní vlastnosti jako jsou incidence, rovnoběžnost a pod. a jednak metrické vlastnosti těchto útvarů, například vzdálenosti, kolmost a podobně. Již starořecký učenec Apolónius viděl jisté těžkosti a nejednotnost řešení geometrických úloh konstruktivní cestou a snažil se je změnit na úlohy algebraické. Rozvoj vědy a techniky v 17. století si vynutil, aby geometrické problémy byly popsány algebraickými prostředky. Zasloužili se o to nezávisle na sobě dva francouzští matematici R. Descartes (1596–1650) a P. Fermat (1610–1665). O sto let později L. Euler (1707–1783) tuto snahu dovršil a položil základy nové geometrické disciplíny, která se dnes nazývá analytická geometrie.
10.1
Afinní prostor
V našem výkladu se omezíme na stručný informativní výklad základních pojmů a vztahů. Takové omezení uděláme hned při zavádění nejzákladnějšího pojmu — afinního prostoru.
96
DEFINICE: Mějme reálný aritmetický vektorový n-rozměrný prostor R ve dvou vydáních. Reálný aritmetický afinní n-rozměrný prostor se nazývá uspořádaná trojice An = (Rn , Rn , +), kde prvky prvního exempláře Rn se nazývají body a označíme je A = [a1 , . . . , an ]; druhý exemplář Rn se nazývá zaměření, jeho prvky se nazývají vektory a označíme je jako dosud a = (a1 , . . . , an ) a konečně sčítání ze třetí složky je tzv. „bodově-vektorová operaceÿ, při které „součtem bodu a vektoru je bodÿ. Například, je-li součtem bodu A a vektoru u bod X, pak píšeme n
X =A+u Protože jiné afinní prostory studovat nebudeme, říkejme stručně pouze afinní prostor místo reálný aritmetický afinní prostor. Příklad. Pro body A = [1, 2, 0] a X = [4, 3, 1] z afinního prostoru A3 je −−→ u = AX = X − A = [4, 3, 1] − [1, 2, 0] = (3, 1, 1) −−→ v = XA = A − X = [1, 2, 0] − [4, 3, 1] = (−3, −1, −1) −−→ Odtud je zřejmé, že je nutné dávat pozor na pořadí bodů (vektor XA je −−→ opačný k vektoru AX). Snadno se ověří, že pro bodově-vektorovou operaci platí A + (u + v) = (A + u) + v pro každý bod A a libovolné vektory u, v. DEFINICE: Buď An afinní n-rozměrný prostor, nechť W je vektorový podprostor jeho zaměření a nechť A je jeho libovolný bod, pak klademe L=A+W a řekneme, že L je afinní podprostor v An . Dále řekneme, že bod A je počátek nebo umístění a konečně řekneme, že W je zaměření podprostoru L. Klademe dim L = dim W ; je-li dim L = r, píšeme L = Lr . Afinní podprostor dimenze nula, tj. A + {o} = A je tedy bod. Afinní podprostor L je tedy určen umístěním A a zaměřením W , což zapisujeme takto L = {A; W } nebo L = {A; u1 , . . . , ur }, kde u1 , . . . , ur je báze W 97
což bude současně znamenati množinu všech bodů podprostoru L. Vektory u1 , . . . , ur báze zaměření se nazývají směrové vektory afinního podprostoru L. Buď nyní Lr = {A; u1 , . . . , ur } libovolný podprostor afinního podprostoru An nenulové dimenze r. Pak je známo, že každý vektor ze zaměření Lr lze P psát ve tvaru ri=1 ti ui pro vhodná reálná čísla t1 , . . . , tr , a tedy každý bod X afinního podprostoru Lr můžeme napsat ve tvaru X =A+
r X
ti ui
i=1
pro vhodná reálná čísla t1 , . . . , tr , v této souvislosti nazývané parametry bodu X prostoru Lr . Poslední rovnost se nazývá parametrické vyjádření nebo parametrická rovnice podprostoru Lr . Říkáme též, že podprostor Lr je dán parametricky. Rozepíšeme-li parametrickou rovnici pro každou složku zvlášť, pak dostaneme soustavu n-rovnic x1 = a1 + t1 u11 + · · · + tr u1r x2 = a2 + t1 u21 + · · · + tr u2r .. .. .. . . . xn = an + t1 un1 + · · · + tr unr kde A = [a1 , . . . , an ] a ui = (u1i , . . . , uni ) pro i = 1, . . . , r. V An jednorozměrný, dvojrozměrný, resp. (n − 1)-rozměrný afinní podprostor nazýváme přímkou, rovinou, resp. nadrovinou. Přímka p = {A; u} daná umístěním A = [a1 , . . . , an ] a směrem u = (u1 , . . . , un ) má parametrické vyjádření X = A + tu neboli ve složkách x1 = a1 + tu1 x2 = a2 + tu2 ............ xn = an + tun Tyto rovnosti můžeme též formálně zapsat ve tvaru x 2 − a2 x n − an x1 − a1 = = ··· = =t u1 u2 un 98
Tomuto zápisu budeme říkat kanonické (parametrické) vyjádření přímky p. Poznamenejme, že tento zápis je ryze formální, tj. má význam i výraz tvaru r pro libovolné reálné číslo r . 0 Příklad. Rozhodněte zda body P = [3, 4, 7], Q = [1, 0, 0] leží na přímce p = {A; u}, kde A = [2, 1, 5], u = (2, 6, 4). Řešení: Dosadíme-li do parametrické rovnice p ≡ X = A + tu bod P za X , dostaneme P = A + tu a hledáme hodnotu parametru bodu P . Řešením příslušné soustavy rovnic 3 = 2 + 2t 4 = 1 + 6t 7 = 5 + 4t snadno zjistíme, že t = 12 . Bod P proto leží na p. Uděláme-li totéž z bodem Q, zjistíme, že příslušná soustava 1 = 2 + 2t 0 = 1 + 6t 0 = 5 + 4t nemá řešení. Bod Q tedy neleží na p. Poznamenejme, že přímku p můžeme též určit dvěma různými body A,B . Zvolíme-li například bod A za umístění a za směrový vektor například vektor −→ AB = B − A, pak parametrická rovnice přímky p má tvar p ≡ X = A + t(B − A),
t∈R
Různé body této přímky dostaneme dosazením reálných čísel za parametr t. Například pro t = 0 je X = A, pro t = 1 je X = B, pro t = 21 je po malé úpravě X = A+B , což je střed úsečky AB. Probíhá-li parametr t ∈ h0, 1i, 2 proběhne bod X celou úsečku AB . Parametrická rovnice úsečky AB tedy je X = A + t(B − A),
t ∈ h0, 1i
Podobně při vhodné volbě množiny hodnot parametru t získáme další podmnožiny přímky. Například pro t ∈ h0, ∞) představuje rovnice X = A + t(B − A) rovnici polopřímky AB . 99
Z kapitoly ??, nazvané „Obecné řešení soustav lineárních rovnicÿ, zejména pak z vět ?? a ?? plyne: Jestliže Ax = b je soustava m lineárních rovnic o n neznámých, ve které je hodnost h matice soustavy rovna hodnosti matice rozšířené, pak množina všech řešení této soustavy tvoří afinní podprostor v An dimenze n − h. Obráceně, ke každému afinnímu podprostoru dimenze h existuje taková soustava n − h lineárně nezávislých lineárních rovnic, že daný podprostor je jejím řešením. Je zřejmé, že takových soustav, navzájem ekvivalentních, majících tedy totéž řešení, je pak nekonečně mnoho. Každá taková soustava se nazývá soustava obecných rovnic daného lineárního podprostoru. Příklad. Najděte obecnou rovnici přímky p = {A; u} v A2 , je-li A = [1, 0], u = (2, −3). Řešení: Obecná rovnice přímky p je tvaru ax1 + bx2 + c = 0 kde bod A je jejím řešením a vektor u je řešením přiřazené homogenní rovnice ax1 + bx2 = 0 Z těchto podmínek dostáváme rovnice pro koeficienty a, b, c a+c=0 2a − 3b = 0 pro které je (a, b, c) = k(3, 2, −3). Tedy rovnice 3x1 + 2x2 − 3 = 0 a každý její nenulový násobek je obecnou rovnicí přímky p v A2 . Jiné řešení: Napíšeme parametrické rovnice přímky p x1 = 1 + 2t x2 = − 3t a vyloučíme parametr t, třeba tím že vytvoříme lineární kombinaci našich rovnic s koeficienty 3 a 2 3x1 + 2x2 = 3 100
což je tatáž rovnice jako nahoře. Příklad. Najděte obecné rovnice přímky p = {A, u} v A3 , je-li A = [1, −1, 2], u = (1, 0, 1). Řešení: Soustava obecných rovnic přímky p je tvaru a1 x1 + b1 x2 + c1 x3 + d1 = 0 a2 x1 + b2 x2 + c2 x3 + d2 = 0 Bod A je jejím řešením a platí tedy a1 − b1 + 2c1 + d1 = 0 a2 − b2 + 2c2 + d2 = 0 a vektor u je řešením přiřazené homogenní soustavy a platí tedy a1 + c 1 = 0 a2 + c 2 = 0 Řešme tedy Gaussovou eliminací soustavu čtyř lineárních homogenních rovnic o osmi neznámých a1 , b1 , c1 , d1 , a2 , b2 , c2 , d2 , v tomto pořadí, s maticí
1 −1 2 1 0 0 0 0 0 0 0 0 1 −1 2 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0
→
1 0 1 0 0 0 0 0 0 1 −1 −1 0 0 0 0
!
Matice soustavy má hodnost h = 2. Napíšeme-li její obecné řešení a1 = −c1 , b1 = c1 + d1 a ostatní neznámé c1 , . . . , d2 jsou parametry, pak například při volbách parametrů c1 = 1, d1 = a2 = b2 = c2 = d2 = 0 a d1 = 1, c1 = a2 = b2 = c2 = d2 = 0 dostaneme dvě lineárně nezávislá řešení a1 = −1, b1 = 1, c1 = 1, d1 = a2 = b2 = c2 = d2 = 0 a1 = 0, b1 = 1, c1 = 0, d1 = 1, a2 = b2 = c2 = d2 = 0 která dávají hledanou soustavu dvou obecných rovnic dané přímky −x1 + x2 + x3 = 0 x2 + 1 = 0 101
Poznamenejme, že lze zase postupovat tak, že nejprve napíšeme parametrické rovnice přímky a potom vyloučíme parametr. Příklad. V A3 najděte obecnou rovnici roviny α = {A = [1, 3, 0]; u = (1, −1, 1), v = (−1, −1, 1)}. Řešení: Parametrické rovnice roviny α jsou x1 = 1 + t1 − t2 x2 = 3 − t1 − t2 x3 = t1 + t2 Po vyloučení parametrů dostaneme obecnou rovnici roviny α x2 + x3 − 3 = 0 Budeme se nyní zabývat zkoumáním vzájemné polohy dvou afinních podprostorů v An . Vyšetřujme, zda mají dva dané afinní podprostory společný afinní podprostor a jaké dimenze a vyšetřujme také, zda mají společné směry. Zůstaneme u tradičních podprostorů jako jsou přímky a roviny. Uvidíme však, že někdy jejich vzájemná poloha může být netradiční, a to tenkrát, bude-li n > 3. Příklad. Vyšetřete vzájemnou polohu dvou přímek p = {A; u}, q = {B; v} v An , n > 2. Řešení: Napíšeme si parametrické rovnice obou přímek X = A+tu, X = B + sv a hledáme společné body. Položíme tedy A + tu = B + sv a řešíme soustavu tu − sv = B − A (aspoň tří) lineárních rovnic o dvou neznámých t, −s. Označme h hodnost matice soustavy ku, vk a označme h0 hodnost matice rozšířené ku, v, B − Ak. Podle Frobeniovy věty pak pro (a)
h = h0 = 1 má soustava nekonečně mnoho řešení a obě přímky tedy splynou, říkáme, že jsou rovnoběžné splývající.
(b)
h = 1, h0 = 2 soustava nemá řešení, přímky nemají žádný společný bod avšak mají společný směr, a jsou tedy rovnoběžné různé .
(c)
h = h0 = 2 má soustava jediné řešení a přímky tedy mají společný jediný bod a říkáme, že jsou různoběžné . 102
(d)
h = 2, h0 = 3 soustava nemá řešení, přímky nemají společný bod a ani nemají společný směr, nejsou tedy rovnoběžné. Takové přímky nazýváme mimoběžné .
Příklad. Vyšetřete vzájemnou polohu dvou rovin α = {A; u, v}, β = {B; w, z} v An , n > 4. Řešení: Řešíme-li tuto úlohu podobně jako předchozí, poloha obou rovin je závislá na hodnostech h matice ku, v, w, zk a h0 matice ku, v, w, z, B −Ak. Je-li (a)
h = h0 = 2, pak roviny splynou a říkáme, že jsou rovnoběžné splývající.
(b)
h = 2, h0 = 3, pak mají roviny společný dvojsměr a nemají společných bodů. Říkáme, že jsou rovnoběžné různé .
(c)
h = h0 = 3, pak roviny mají společný právě jeden směr a nekonečně mnoho bodů. Jsou tedy různoběžné se společnou přímkou.
(d)
h = 3, h0 = 4, pak roviny nemají společný bod, ale mají společný právě jeden směr. Říkáme, že jsou mimoběžné se společným směrem.
(e) h = h0 = 4, pak roviny mají společný právě jeden bod a nemají společný směr. Říkáme, že jsou různoběžné se společným bodem. (f )
h = 4, h0 = 5, pak roviny nemají společný ani žádný bod a ani žádný směr. Nazývají se mimoběžné bez společného směru.
Vraťme se znovu k poznámce o tom, že studujeme-li vzájemnou polohu afinních podprostorů, je nutné si uvědomit, že existence typu vzájemné polohy závisí na dimenzi obou podprostorů, ale také na dimenzi celého prostoru An . Například kdybychom vyšetřovali vzájemnou polohu dvou rovin v A3 , pak by poslední tři možnosti vůbec nemohly nastat. Příklad. V A4 určete vzájemnou polohu přímky p = {A; u} a roviny α = {B; v, w}, jestliže A = [−2, −1, 3, −4], u = (1, −1, 0, 1), B = [2, 2, 3, 0], v = (3, 4, 1, 2), w = (0, 0, −1, 1). Řešení: Parametry společného bodu musí vyhovovat rovnici A + ru = B + sv + tw neboli ru − sv − tw = B − A, takže budeme řešit soustavu čtyř
103
lineárních rovnic o třech neznámých s maticí
(u, −v, −w|B − A) =
1 −1 0 1
−3 0 −4 0 −1 1 −2 −1
4 3 0 4
Řešení dané soustavy je r = 1, s = t = −1. Hledaný bod X = A + u = [−1, −2, 3, −3]. Poznamenejme, že přímka může ležet v rovině , je-li h = h0 = 2, být rovnoběžná a neležet v rovině, je-li h = 2, h0 = 3 nebo může být různoběžná s rovinou a pak s ní má jediný společný bod, je-li, jako v našem příkladě, h = h0 = 3. Přímka, která protne současně dvě různé přímky se nazývá jejich příčka. Ze školské geometrie jsou známé úlohy na sestrojení příčky dvou mimoběžek. Příklad. V A3 nalezněte příčku mimoběžek p = {A = [1, 2, −1]; u = (1, −1, 1)}, q = {B = [0, 9, −2]; v = (1, 0, 0)} rovnoběžnou se směrem w = (1, 2, 0). Řešení: Položíme-li ρ = {B; v, w}, pak rovina ρ je rovnoběžná se směrem w a přímka q v ní leží. Stačí najít průsečík přímky p s rovinou ρ. Jeho parametry získáme řešením rovnice A + ru = B + sv + tw a řešíme tedy soustavu lineárních rovnic s maticí
1 −1 −1 0 −2 (u, −v, −w|B − A) = −1 1 0 0
−1 7 −1
Odtud snadno spočítáme r = −1 (s = 3, t = −3) a bod C = A−u = [0, 3, −2] je průsečíkem přímky p s rovinou ρ. Hledaná příčka je pak r = {C; w}. Příklad. V A3 nalezněte příčku mimoběžek p = {A = [3, 3, 3]; u = (2, 2, 1)}, q = {B = [0, 5, −1], v = (1, 1, 1)}, která prochází bodem C = [4, 5, 3]. Řešení: Stačí najít průsečík přímky q s rovinou ρ = {A; u, C − A} proloženou přímkou p. Jeho parametry získáme řešením rovnice A + tu + r(C − A) = B + sv 104
Je s = 0 a průsečík přímky q s rovinou ρ je bod B + 0v = B. Poznamenejme, že příčka dvou mimoběžek nemusí existovat. To nastane, když je přímka q rovnoběžná s pomocnou rovinou ρ proloženou přímkou p.
10.2
Eukleidovské prostory
Eukleidovský prostor je svými vlastnostmi nejbližší fyzikálnímu prostoru, pokud tento prostor zkoumáme pozorovacími metodami. Je to afinní prostor, který je obohacen o metrické vlastnosti, mezi které patří zjišťování vzdáleností podprostorů, odchylek a podobně. My se omezíme pouze na výpočet vzdáleností, a to dvou bodů, bodu od podprostoru, dvou rovnoběžných podprostorů a dvou mimoběžek. DEFINICE: Reálný afinní prostor An jehož zaměření tvoří eukleidovský vektorový prostor (tj. reálný vektorový prostor se skalárním součinem) budeme nazývat n-rozměrný eukleidovský prostor a označovat E n . Protože eukleidovský prostor je speciálním případem afinního prostoru, platí pro něj všechna tvrzení, která jsme uvedli v předchozí kapitole o afinních prostorech. Nově studovanými vlastnostmi budou vlastnosti metrické. −→ Pro dva body A, B eukleidovského prostoru E n délka vektoru AB se nazývá vzdálenost bodů A, B a značí se d(A, B). Je tedy v u n uX −→ d(A, B) = |AB| = |B − A| = t (bi − ai )2 i=1
Například vzdálenost bodů A = [2, 1, 3], B = [1, 3, 2] z eukleidovského prostoru E 3 je d(A, B) =
q
(1 − 2)2 + (3 − 1)2 + (2 − 3)2 =
√
6
V E n mějme dán podprostor L= {A; u1 , . . . , ur } dimenze r > 0 a bod B. Řekneme, že vektor v je kolmý na podprostor L, jestliže je v kolmý na každý vektor jeho směrového zaměření, tj. v je kolmý ke všem vektorům u1 , . . . , ur . Přímka p = {B; v} se nazývá kolmice spuštěná z bodu B na podprostor L, její průsečík B ∗ s L se nazývá její pata nebo kolmý průmět bodu B do podprostoru L. Vzdálenost bodu B od jeho kolmého průmětu B ∗ do podprostoru L se nazývá vzdálenost bodu B od podprostoru L, značí se 105
d(B, L). Dá se ukázat, že pata B ∗ kolmice je vždy určena jednoznačně a že má minimální vzdálenost od bodu B ze všech bodů podprostoru L. Příklad. Určete vzdálenost bodu B = [1, −2, −1, 1] od roviny ρ = {A = [−2, 3, 1, 8]; u = (1, 1, −1, −4), v = (−4, 2 − 1, 2)}. Řešení: Podle definice vzdálenosti bodu od podprostoru najdeme vektor −−→∗ BB kolmý na rovinu ρ takový, že jeho koncový bod B ∗ leží v rovině ρ. Délka tohoto vektoru pak bude hledaná vzdálenost. Z podmínky B ∗ ∈ ρ dostaneme B ∗ = A + tu + sv K tomu, aby byl vektor −−→∗ BB = B ∗ − B = A − B + tu + sv kolmý na rovinu ρ stačí, aby byl kolmý na její směrové vektory, tj. −−→ 0 = (BB ∗ , u) = (A − B + tu + sv, u) = (A − B, u) + t(u, u) + s(u, v) −−→ 0 = (BB ∗ , v) = (A − B + tu + sv, v) = (A − B, v) + t(u, v) + s(v, v) Hledané parametry t, s bodu B ∗ jsou tedy složkami řešení soustavy dvou lineárních rovnic s maticí (u, u) (u, v) (u, v) (v, v)
(u, B − A) (v, B − A)
!
Determinant soustavy se nazývá Gramův determinant z vektorů u,v, značí se |G(u, v)| a dá se o něm dokázat, že z lineární nezávislosti vektorů u,v plyne jeho nenulovost. Podle Cramera má tedy soustava jediné řešení a bod B má jediný kolmý průmět do roviny ρ. Nechceme-li už dále počítat obecně, pak na tomto místě dosadíme složky a řešíme tedy soustavu lineárních rovnic s maticí 19 −9 −9 25
28 −34
!
Parametry bodu B ∗ tedy jsou t = 1, s = −1, odtud B ∗ = [3, 2, 1, 2] a tedy −−→∗ BB = (2, 4, 2, 1). Hledaná vzdálenost bodu B od roviny ρ je √ d(B, ρ) = d(B, B ∗ ) = 22 + 42 + 22 + 12 = 5 106
Kdybychom před chvílí počítali ještě i nadále obecně, pak d(B, ρ) = d(B, B ∗ ) = =
q
(B ∗ − B, B ∗ − B) =
q
(A − B + tu + sv, A − B + tu + sv)
Po dosazení parametrů
t=
(u, B − A) (u, v) (v, B − A) (v, v)
|G(u, v)|
,
s=
(u, u) (u, B − A) (u, v) (v, B − A)
|G(u, v)|
a po dosti pracné úpravě bychom dostali vzorec v u u |G(u, v, B − A)| d(B, ρ) = t
|G(u, v)|
který lze zobecnit Věta 71 V E n je vzdálenost bodu B od podprostoru Lr = {A; u1 , . . . , ur }, kde r < n, dána vzorcem s
d(B, Lr ) =
|G(u1 , . . . , ur , B − A)| |G(u1 , . . . , ur )|
Vrátíme-li se ještě k řešení posledního příkladu, máme (u, u) (u, v) (u, B − A) (u, v) (v, v) (v, B − A) = |G(u, v, B − A)| = (u, B − A) (v, B − A) (B − A, B − A) 19 −9 28 10 −9 19 10 −9 19 25 −34 = 16 25 −9 = 10 −9 44 = −9 28 −34 87 −6 −34 53 −6 −34 53 10 −9 19 10 −9 0 25 = −25 · = 0 = 25 · 394 −6 −34 −6 −34 53 q √
Protože je |G(u, v)| = 394, máme d(B, ρ) = jednou vypočetli. 107
25·394 394
=
=
25 = 5, jak už jsme
Poznamenejme, že definici rovnoběžnosti lze zobecnit takto: Jestliže zaměření jednoho afinního podprostoru je vektorovým podprostorem zaměření jiného afinního podprostoru, pak jsou oba afinní podprostory rovnoběžné . Dále pak, vzdáleností dvou rovnoběžných afinních podprostorů nazýváme vzdálenost libovolného bodu jednoho podprostoru od druhého. Osou mimoběžek nazýváme příčku, která je na obě mimoběžky kolmá. Osa mimoběžek se také nazývá nejkratší příčkou. Vzdáleností mimoběžek se nazývá vzdálenost průsečíků osy s mimoběžkami. Příklad. V E3 najděte osu mimoběžek p = {A = [1, 3, −1]; u = (−1, −2, 1)} a q = {B = [2, 3, 0]; v = (1, −1, 1)} a jejich vzdálenost. Řešení: Nejprve zjistíme, že jde opravdu o mimoběžky
−1 −2 1 u −1 −2 1 v = 1 −1 1 ∼ 0 −3 2 0 −2 2 B−A 1 0 1 tedy h = 2, h0 = 3 a proto jsou přímky p, q mimoběžné. Nyní najdeme vektor w tak, aby byl kolmý jak na vektor u, tak na vektor v, tedy (u, w) = (v, w) = 0, což dává řešení například w = (−1, 2, 3). Dále přímkou p proložíme rovinu α, jejíž zaměření obsahuje vektor w, a přímkou q proložíme rovinu β, jejíž zaměření též obsahuje vektor w. Snadno zjistíme, že rovnice roviny α je 4x1 − x2 + 2x3 + 1 = 0, parametrické rovnice roviny β jsou x1 = 2 + t − s x2 = 3 − t + 2s x3 = t + 3s Hledáme průsečnici získaných rovin tak, že z parametrických rovnic roviny β dosadíme do obecné rovnice roviny α. Dostaneme rovnici (8 + 4t − 4s) − (3 − t + 2s) + 2(t + 3s) + 1 = 0 ze které t = −6 . 7 Osa o mimoběžek p,q je tedy dána parametrickými rovnicemi x1 = x2 = x3 =
8 7 27 7 −6 7
108
− s + 2s + 3s
Snadno se přesvědčíme, že průsečík osy o s přímkou q je bod X = [ 87 , 27 , −6 ]. 7 7 Zjistíme i průsečík Y osy o s přímkou p, řešíme-li soustavu rovnic 8 7 27 7 −6 7
1 − t = 3 − 2t = −1 + t = Je to bod přímky p s parametrem t =
−2 , 7
− s + 2s + 3s
tj. Y = [ 79 , 25 , −9 ]. Potom 7 7
s 1 −2 −3 2 = d(p, q) = d(X, Y ) = , ,
7
7
7
7
Pokud bychom hledali pouze vzdálenost mimoběžek p,q, stačilo by uvažovat o dvou rovnoběžných rovinách γ = {A; u, v}, δ = {B; u, v} a hledat například vzdálenost bodu A od roviny δ. Ta je dána vzorcem v s u u |G(u, v, B − A)| 2 = d(p, q) = d(A, δ) = t
|G(u, v)|
10.3
7
Cvičení
Polohové příklady: 1. Najděte obecné rovnice přímky p, která v A3 má parametrické rovnice x1 = 1 + t, x2 = 1 − t, x3 = 2 + 3t. /x1 + x2 − 2 = 0, 3x2 + x3 − 5 = 0/ 2. V A3 najděte rovinu jdoucí bodem A = [1, 2, 1] a obsahující přímku p danou obecnými rovnicemi x1 − x2 + 2 = 0, x1 + x3 − 1 = 0. /x2 + x3 − 3 = 0/ 3. Najděte parametrické vyjádření roviny v A4 , která je dána soustavou obecných rovnic 3x1 − x2 − x3 + x4 + 1 = 0, 2x1 + x2 + 2x3 − 2 = 0. /x1 = −r − s, x2 = −8r + 2s, x3 = 1 + 5r, x4 = 5s/ 4. V prostoru A4 najděte průsečnici nadroviny 3x1 + x2 + x3 + x4 − 2 = 0 s rovinou x1 = u + v, x2 = u − v, x3 = 2u, x4 = 1 − v. /x1 = 1 − 5u, x2 = −1 + 7u, x3 = 2u, x4 = 6u/ 5. V A4 zjistěte vzájemnou polohu daných podprostorů a určete o jaké podprostory jde: 109
• {[1, 0, 2, 2]; (1, −1, 0, 0), (1, 2, 0, −1)}, {[0, 0, −6, 5]; (1, 2, −3, 0)}. /Protínají se v bodě [− 83 , − 16 , 2, 5]./ 3 • {[0, 3, 1, 3]; (1, 1, −2, −2), (1, 5, −4, 0)}, {[−9, 2, 1, −5]; (5, −1, 0, 2), (3, 1, 2, 0)}. /Protínají se v bodě [1, 0, 1, −1]./ •
= y−7 = z − 4 = −u−5 , x+1 = 3 2 2 /Protínají se v bodě [1, 1, 2, −1]./ x−5 2
y+1 2
=3−z =
u+4 . 3
• {[0, 0, 0, 0]; (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0)}, {[0, 0, 0, 3]; (1, 1, 1, 0)}. /Rovnoběžné./ • {[2, 1, 1, 1]; (1, 1, 1, 1), (1, 1, 1, −1), (1, 1, −1, −1)}, {[3, 2, 0, −2]; (1, 1, −1, 1)}. /Přímka leží v nadrovině./ • {[2, 3, 1, 3]; (−1, 1, 0, 2), (0, 2, −3, 2)}, {[−1, 0, 2, 1]; (2, 4, −9, 2), (1, 1, 1, 1)}. /Protínají se v přímce {[1, 2, 4, 3]; (2, 4, −9, 2)}./ 6. V A4 • určete parametry a, b tak, aby přímka {[1, 2, 1, 2]; (1, a, 0, 2)} ležela v rovině {[1, 1, 2, b]; (1, 2, 1, 2), (1, 1, 2, 2)}. /a = 3, b = 2/ • stanovte hodnotu parametru a tak, aby roviny {[1, −1, −1, 4]; (1, 2, 2, −3), (1, 1, 0, 2)}, {[3, −1, 1, −3]; (2, 1, 1, −3), (0, 0, 1, a)} byly mimoběžné. /a = −4/ • V závislosti na parametru a zjistěte vzájemnou polohu rovin {[3, −1, −1, 6]; (−2, 1, −2, 1), (4, −1, −1, 0)}, {[4, 1, 3, a]; (0, −2, 0, 1), (2, 2, −, 1, −1)}. 43 /Pro a 6= 11 mimoběžné, pro a = 11 se protínají v přímce {[4, − 21 , 3, 10 ]; 4 4 10 (10, −2, −5, 1)}./ • určete parametry a, b tak, aby přímky {[3, 2, 1, 0]; (0, a, 1, b)}, {[−2, 4, 4, −1]; (5, −5, −6, 4)} byly různoběžné, a nalezněte jejich průsečík. /a = 1, b = −1, průsečík [3, −1, −2, 3]./ 7. V A5 určete vzájemnou polohu podprostorů: • {[1, 1, 1, 1, 1]; (2, −8, 3, −5, −9)}, {[1, 1, 2, −1, 3]; (1, −1, 0, 2, 3), (0, 2, −1, 3, 5)}. /Rovnoběžné./ 110
• {[−2, 10, −1, 2, −1]; (2, −8, 3, −5, 1)}, {[1, 1, 2, −1, 3]; (1, −1, 0, 2, 3), (0, 2, −1, 3, 5)}. /Protínají se v bodě [0, 2, 2, −3, 0]./ • {[4, −4, 2, 1, 1]; (2, −8, 3, −5, 1)}, {[1, 1, 2, −1, 3]; (1, −1, 0, 2, 3), (0, 2, −1, 3, 5)}. /Mimoběžné./ • {[2, 0, 2, 0, 1]; (2, 1, 0, 0, 0), (0, 0, 1, 2, 3)}, {[1, 0, 0, 1, 0]; (1, 0, 0, 0, 0), (0, 1, 0, 0, 0), (0, 0, 0, 0, 1)}. /Mimoběžné./ 8. V A3 najděte příčku mimoběžek • {[1, 0, 2], (1, −1, 1)}, {[3, −1, 0]; (0, 1, 0)}, která má směr (0, 0, 1). /Hledaná přímka je určena vektorem (0, 0, 1) a například bodem [3, −2, 4] na první přímce./ •
= y+3 = z−5 , x5 = 2 − y = 4 3 /{[4, 0, −1]; (1, 1, −2)}/ x−1 2
z+5 , 2
která prochází bodem [4, 0, −1].
• {[1, 2, −1]; (1, −1, 1)}, {[2, 0, −2]; (1, 0, 0)}, která je rovnoběžná s přím= z−3 . kou x − 1 = y−2 2 0 /{[0, 3, −2]; (1, 2, 0)}/ • x − 5 = y−6 = z−7 , x−3= 3 5 y / /x − 3 = 2 = z+3 3 •
y 2
= z4 , která je určena vektorem (1, 2, 3).
= y−3 = z − 3, x = y − 5 = z + 1, která prochází bodem [4, 5, 3]. 2 /x − z − 1 = 0, y − 5 = 0/ x−3 2
• x − 2 = y+3 = −z−1 , x − 3 = y = z+58 , která je rovnoběžná s průsečnicí 2 2 3 rovin 2x − z − 15 = 0, x − y + 324 = 0. /x − 4 = y − 1 = z+5 / 2 • {[1, 3, 4]; (1, 0, 2)}, 2x − z + 2 = 0, y − 3 = 0, která prochází bodem [13, 17, 29]. /Příčka neexistuje, přímky jsou totožné./ 9. V A4 určete příčku přímek 111
• {[1, 0, −2, 1]; (1, 2, −1, −5)}, {[0, 1, 1, −1]; (2, 3, −2, −4)}, která prochází bodem [8, 9, −11, −15] a najděte příslušné průsečíky. /Směr příčky (6, 7, −8, −11), průsečíky [2, 2, −3, −4], [−4, −5, 5, 7]./ • {[1, 1, 1, 1]; (1, 2, 1, 0)}, {[2, 2, 3, 1]; (1, 0, 1, 3)}, která prochází bodem [4, 5, 2, 7] a najděte příslušné průsečíky. /Směr příčky (1, 1, 0, 3), průsečíky [2, 3, 2, 1], [1, 2, 2, −2]/ 10. V A4 najděte příčku přímky {[0, 0, −6, −7]; (1, 1, 2, 1)} a roviny {[2, 1, 1, 1]; (1, 2, −1, 1), (−1, 2, 1, 2)}, která prochází bodem [7, −2, −1, 0]. /Směr příčky (2, −1, 1, 2)/ Metrické příklady: 11. Najděte nejkratší příčku mimoběžek a spočtěte vzdálenost těchto mimoběžek. = • 2x − 14 = y − 3 = 18 − 2z, 3−x 7 √ x−3 z−1 / 2 = y − 1 = 4 , 2 21/
y−1 2
=
z−1 . 3
• {[6, 3, −3]; (−3, 2, 4)}, {[−1, −7, 4]; (−3, 3, 8)}. /{[3, 5, 1]; (4, 12, −3)}, 13/ 12. Určete vzdálenost bodu B = [0, 1, 0, −1] od následujících podprostorů • {[4, √5, 2, 5]; (1, 1, −1, 3), (1, 2, 0, 1)} /2 3/ • x√ 1 − x2 + 2x3 + x4 = 5 / 7/ • {[0, 3, 8, 1], (1, −1, −5, 3)} /6/ • {[−1, 2 − 2, −1]; (1, 2, 0, 1), (3, 0, 4, 1)} /0/ • {[5, √4, 1, 1]; (2, 4, −1, 0), (1, 5, 2, −1), (−1, 3, 1, 2)} /3 2/
112
Kapitola 11 Matematické základy lineárního programování 11.1
Základní pojmy
Chceme-li naše dosavadní znalosti z lineární algebry využít k lineárnímu programování, musíme si zavést ještě některé další pojmy a doplnit některé souvislosti. Především každou soustavu m lineárních rovnic o n neznámých (předpokládejme nyní vždy, že matice soustavy má hodnost rovnu počtu rovnic m, a tedy rovnice soustavy jsou lineárně nezávislé) lze pomocí Gaussovy eliminace převést na tvar Ax = b kde matice soustavy A obsahuje jednotkovou submatici E řádu m, který nazýváme kanonickým tvarem dané soustavy. Pro účely lineárního programování má význam pouze případ m < n. Pak má ovšem soustava nekonečně mnoho řešení závislých na n−m parametrech. Neznámé, které jsou v kanonickém tvaru soustavy přiřazené sloupcům jednotkové matice nazveme základní neznámé (nebo proměnné); ostatní neznámé, dříve volené za parametry, nazveme nezákladní neznámé . Jedno z partikulárních řešení soustavy, přiřazené k danému kanonickému tvaru, dostaneme jednoduše tak, že za všechny nezákladní neznámé dosadíme nuly a základní neznámé jsou pak rovny pravým stranám. Takto obdržené řešení nazýváme základní řešení. Rovná-li se nule i některá základní neznámá, mluvíme někdy o tzv. degenerovaném základ113
ním řešení. Soustava má zřejmě vždy konečný počet základních řešení, který n není větší než m . Například jedním z kanonických tvarů soustavy lineárních rovnic je tvar x1 + a1,m+1 xm+1 + · · · + a1n xn = b1 x2 + a2,m+1 xm+1 + · · · + a2n xn = b2 .. .. .. . . . xm + am,m+1 xm+1 + · · · + amn xn = bm a k němu příslušné základních řešení tedy je (b1 , b2 , . . . , bm , 0, 0, . . . , 0) Gaussovou eliminační metodou můžeme přecházet od jednoho kanonického tvaru soustavy k jinému jejímu kanonickému tvaru tak, že jedna ze základních neznámých se stane nezákladní a jedna z původně nezákladních se stane základní neznámou. Tímto způsobem lze získat všechna základní řešení dané soustavy. Příklad. Určete všechny kanonické tvary a základní řešení soustavy lineárních rovnic 2x1 + 7x2 + 3x3 + x4 = 6 3x1 + 5x2 + 2x3 + 2x4 = 4 Po úpravách R21 (−2), R12 (2), R2 (−1) dostaneme kanonický tvar soustavy s maticí 0 −11 −5 1 1 9 4 0
−10 8
!
a k němu základní řešení (8, 0, 0, −10)
a protože je první, říkáme mu někdy výchozí základní řešení. Dále po úpra1 ), R21 (−9) poslední matice dostaneme druhý kanonický tvar vách R1 (− 11 soustavy s maticí 5 1 0 1 − 11 11 1 9 1 0 − 11 11
10 11 2 − 11
!
a k němu základní řešení (−
1 Dále po úpravách R2 ( 11 ), R12 ( 11 ) máme 9 1 9 11 9
4 1 0 9 0 − 19 1
8 9 − 29
114
!
,
8 2 (0, , 0, − ) 9 9
2 10 , , 0, 0) 11 11
Dále po úpravách R2 (−9), R12 (− 94 ) máme 5 1 0 4 −11 0 1 −9
!
0 2
,
(0, 0, 2, 0)
Dále po úpravách R1 ( 15 ), R21 (11) máme 1 0
1 5 11 5
4 0 5 1 − 15
!
0 2
,
(0, 0, 2, 0)
Konečně po úpravách R1 ( 45 ), R21 ( 15 ) máme 5 4 1 4
1 4 45 20
0 1 1 0
0 2
!
,
(0, 0, 2, 0)
Všimněte si, že poslední tří základní řešení jsou stejná a jsou degenerovaná. V závěru našeho výkladu si popíšeme obecnou metodu pro řešení problémů lineárního programování, tzv. simplexovou metodu. Uvidíme potom, že simplexová metoda, stručně řečeno, je eliminační postup obohacený o dva předpisy. První z nich udává do kterého sloupce se bude jeden z předchozích jednotkových sloupců přesouvat - transformovat, určuje tedy novou základní neznámou. Druhý předpis určuje, který z jednotkových vektorů se do tohoto sloupce přesune.
11.2
Matematický model lineárního programování
Základní úlohu lineárního programování můžeme formulovat takto: Hledáme vektor x1 x2 x= .. . xn který vyhovuje tzv. vlastním omezením úlohy, tj. soustavě lineárních rovnic
115
a11 x1 + a12 x2 + · · · + a1n xn = b1 a21 x1 + a22 x2 + · · · + a2n xn = b2 .. .. .. . . . am1 x1 + am2 x2 + · · · + amn xn = bm kde vždy předpokládáme, že m < n a že rovnice jsou lineárně nezávislé. Dále chceme, aby hledaný vektor vyhovoval podmínkám nezápornosti , tj. aby platilo xj ≥ 0 pro j = 1, 2, . . . , n a konečně, aby optimalizoval (minimalizoval nebo maximalizoval) lineární formu, někdy zvanou účelová funkce z = c1 x1 + c2 x2 + · · · + cn xn Poznamenejme, že soustavu i formu můžeme zapsat maticově Ax = b,
resp. z = cx
kde
A=
a11 a21 .. . am1
a12 . . . a1n a22 . . . a2n .. . . .. . . . am2 . . . amn
,
c = (c1 , c2 , . . . , cn )
Připomeňme předpoklad, že hodnost matice A je m. Vektor vyhovující vlastním omezením úlohy a podmínkám nezápornosti se nazývá přípustné řešení úlohy lineárního programování. Optimálním řešením úlohy lineárního programování se nazývá takové přípustné řešení, pro něž je hodnota účelové funkce z optimální, tj. takové přípustné řešení xo , že v případě maximalizace, resp. minimalizace pro všechna přípustná řešení platí cxo ≥ cx,
resp. cxo ≤ cx
Bez důkazu uvedeme nyní tzv. základní větu lineárního programování.
116
Věta 72 Existuje-li optimální řešení problému lineárního programování, pak existuje základní optimální řešení. Odtud vyplývá důležitý praktický závěr: Optimální řešení problému lineárního programování stačí hledat mezi základními přípustnými řešeními, kterých je konečný počet. Není nutné se tedy zabývat množinou všech přípustných řešení, která je obecně nekonečná. Všechny metody řešení problému lineárního programování se o toto tvrzení opírají.
11.3
Tvorba matematického modelu
Nyní vysvětlíme jak se ekonomický problém převede na matematickou úlohu. Bývá obvyklý následující postup: 1. Rozbor ekonomického modelu, uvědomění si co jsou činnosti (procesy) modelu, co jsou zdroje - činitelé vstupující do činnosti, co výsledky - činitelé vystupující z činnosti a konečně co je kriteriem optimality v modelu. 2. Stanovit proměnné - neznámé, jejich věcný význam, rozměr a měrnou jednotku. 3. Vyjádřit lineárními rovnicemi nebo nerovnostmi omezení úlohy v činitelích. Na pravých stranách stojí omezené disponibilní množství vstupujícího činitele nebo požadované množství vystupujícího činitele. Na levých stranách je buď potřebné množství vstupujícího činitele nebo produkované množství vystupujícího činitele, v obou případech vyjádřeno jako lineární funkce proměnných úlohy. Příklad. Formulujte matematický model výrobního programu: Čokoládovna má možnost vyrábět pět druhů výrobků. Spotřebovává tři základní suroviny, a to tuk, kakao a cukr, které jsou k dispozici v omezených množstvích, a to 1 500 kg, 300 kg a 450 kg na den. Kapacita strojového zařízení je dostatečná, stejně tak energie, pracovní síly a další zdroje. Spotřeba surovin je uvedena v tabulce 1.
117
Koeficienty spotřeby surovin v kg na 1 kg výroby V1
V2 V3 V4 V5 Tuk 0,4 0,3 0,6 0,6 Kakao 0,05 0,2 0,1 0,1 Cukr 0,1 0,2 0,2 0,1 0,2 Tabulka 1
Odbytové ceny v Kč / kg jsou: V1 V2 V3 V4 V5
........... ........... ........... ........... ...........
20,120,100,140,40,-
Stanovte denní výrobní program takový, aby hodnota výroby v Kč byla maximální. Řešení: Rozebereme si problém. Do výroby vstupují tři suroviny a vystupuje z ní pět výrobků. Výrobky jsou vyráběny nezávisle na sobě, výroba žádného z nich není technologicky vázána na výrobu jiného. Výroba se tedy uskutečňuje formou pěti do jisté míry izolovaných procesů, i-tému procesu odpovídá výroba výrobku Vi . Těchto pět výrobních procesů tvoří kostru ekonomického modelu. Každý z nich může být charakterizován po technické stránce sloupcem koeficientů. Pro jednotlivé výrobky máme následující charakteristiky:
0 0, 05 0, 1 20
,
0, 4 0, 2 0, 2 120
,
0, 3 0, 1 0, 2 100
,
0, 6 0, 1 0, 1 140
,
0, 6 0 0, 2 40
spotřeba tuku v kg
spotřeba kakaa v kg spotřeba cukru v kg cena v Kč / kg
V dalším budeme tento ekonomický model transformovat do matematické formy. Proměnné matematického modelu musí vyjadřovat hledaný výrobní program a to určením úrovní jednotlivých výrobních procesů a tím také množství jednotlivých výrobků, které mají být vyráběny. Budeme tedy potřebovat pět proměnných x1 , x2 , x3 , x4 , x5 . Jejich věcný smysl je xi je množství výrobku Vi v kg, jež bude vyráběno za den. 118
Tyto proměnné, v souladu se svým věcným významem, mohou nabývat pouze nezáporných hodnot, je tedy xi ≥ 0, i = 1, . . . , 5. Množství výroby je omezeno limity ve spotřebě tří surovin. Hovoříme o omezeních na straně vstupu. Omezení zapíšeme také ve formě vektorové sloupcové charakteristiky, jak jsme to učinili pro jednotlivých pět výrobních procesů. Tyto vektorové charakteristiky označíme p1 , . . . , p5 a vektor omezení b bude tvaru
b=
1500 300 450 Q
kde význam položky Q bude objasněn později. Ekonomický model lze nyní popsat nerovností p1 x 1 + p2 x 2 + p3 x 3 + p4 x 4 + p5 x 5 ≤ b která reprezentuje čtyři nerovnosti, z nichž první udává ve své levé části spotřeby tuku na výrobu všech výrobků v příslušných počtech na jeden den. Tato spotřeba tuku nesmí překročit limit ve spotřebě, který je 1 500 kg. První nerovnost má tedy tvar 0, 4x2 + 0, 3x3 + 0, 6x4 + 0, 6x5 ≤ 1 500 Proměnná x1 v nerovnosti nevystupuje, je to proto, že na výrobu výrobku V1 se tuk nepožaduje. Podobně druhá, resp. třetí nerovnost z vektorové nerovnice popisují ve svých levých částech spotřebu kakaa a cukru na jeden den rozepsanou na jednotlivé výrobky a jejich počty. Na pravých stranách vystupují příslušné limity. Jsou tvaru 0, 05x1 + 0, 2x2 + 0, 1x3 + 0, 1x4 ≤ 300 0, 1x1 + 0, 2x2 + 0, 2x3 + 0, 1x4 + 0, 2x5 ≤ 450 Hodnota výroby má být maximální. Účelová funkce bude tvaru z = 20x1 + 120x2 + 100x3 + 140x4 + 40x5 a požadujeme, aby byla maximální. Optimální řešení, jehož metodiku výpočtu vysvětlíme v následujícím textu, je xo = (0, 0, 1 000, 2 000, 0, 0, 50); z = 380 000 119
Interpretace optimálního řešení: Při formulaci problému jsme zavedli pět proměnných. Jejich hodnoty nalezneme v optimálním řešení na prvních pěti místech vektoru xo . Optimální výrobní program tedy je vyrábět 1 000 kg výrobku V3 a 2 000 kg výrobku V4 za den, ostatní výrobky nevyrábět. Tak se dosáhne maximálního obratu 380 000 Kč.
11.4
Simplexová metoda
Vyjdeme ze soustavy x1 + a1,m+1 xm+1 + · · · + a1n xn = b1 x2 + a2,m+1 xm+1 + · · · + a2n xn = b2 .. .. .. . . . xm + am,m+1 xm+1 + · · · + amn xn = bm kde bi > 0 (jinak vybereme jiné proměnné, případně vynásobíme příslušnou rovnici číslem −1). Dostáváme základní přípustné řešení b0 = (b1 , b2 , . . . , bm , 0, . . . , 0) Hodnota účelové funkce pro toto základní řešení je z0 = c1 b1 + c2 b2 + · · · + cm bm Zkoumejme nyní, zda je možno získat větší (menší) hodnotu účelové funkce, když ji maximalizujeme (minimalizujeme) tak, že do dané soustavy dosadíme například za proměnnou xm+1 nezáporný parametr t (aby byla splněna podmínka o nezápornosti) a ostatní nezákladní proměnné ponecháme rovny nule. Dostaneme tak novou soustavu rovnic x1 + · · · · · · · · · + a1,m+1 t = b1 x2 + · · · · · · + a2,m+1 t = b2 .. .. .. .. .. . . . . . xm + am,m+1 t = bm Z těchto rovnic obdržíme nový vektor řešení x1 = (b1 − a1,m+1 t, b2 − a2,m+1 t, . . . , bm − am,m+1 t, 0, . . . , 0) 120
Vypočítáme hodnotu účelové funkce po dosazení vektoru řešení x1 z1 = c1 (b1 − a1,m+1 t) + c2 (b2 − a2,m+1 t) + · · · + cm (bm − am,m+1 t) + cm+1 t Po úpravě dostaneme z1 = c1 b1 + c2 b2 + · · · + cm bm − t(c1 a1,m+1 + c2 a2,m+1 + · · · + cm am,m+1 − cm+1 ) Zavedeme nový koeficient c0m+1 vztahem c0m+1 = c1 a1,m+1 + c2 a2,m+1 + · · · + cm am,m+1 Dosazením dostáváme z1 = z0 − t(c0m+1 − cm+1 ) Označíme-li přírůstek účelové funkce Dz = z1 − z0 dostaneme Dz = −t(c0m+1 − cm+1 ) Přírůstek Dz bude kladný, když přírůstek Dc = c0m+1 − cm+1 bude záporný. Bude-li Dc = 0, hodnota účelové funkce se nezmění. Bude-li přírůstek Dc kladný, hodnota účelové funkce klesne, jak plyne z posledního vztahu. Pokud maximalizujeme, určuje tedy záporný koeficient, který je představován rozdílem c0m+1 − cm+1 zařazovanou proměnnou a tedy klíčový sloupec. Současně určuje znaménko rozdílu c0m+1 − cm+1 kritérium pro to, zda je nalezené přípustné řešení optimální. Z podmínky nezápornosti vyplývá, že všechny složky vektoru x1 musí být nezáporné, to znamená, že musí být splněny nerovnice b1 − a1,m+1 t ≥ 0 b2 − a2,m+1 t ≥ 0 .. . bm − a2,m+1 t ≥ 0 Protože bi (i = 1, 2, . . . , m) jsou kladná potom pro ai,m+1 < 0 je nerovnost splněna. Budeme proto v dalším uvažovat a studovat pouze ty případy, kdy ai,m+1 jsou kladná. Nechť index j značí tyto případy, potom pro kladná aj,m+1 můžeme poslední soustavu nerovnic upravit následovně t≤
bj aj,m+1 121
Hodnota t, která splňuje soustavu našich nerovností je určena minimální hodnotou zlomku na pravé straně posledních vztahů. Nechť zlomek nabývá minimální hodnotu pro k-tý řádek. Ten se bude v dalším nazývat klíčový řádek . Minimální parametr tmin bude pak určen rovnicí tmin =
bk ak,m+1
Po dosazení do jednotlivých složek vektoru řešení x1 dostáváme při i = 1, 2, . . . , m bk xi = bi − ai,m+1 ak,m+1 což znamená, že původní k-tá proměnná se stává nulou a (m + 1)-proměnná je bk (= t) xm+1 = ak,m+1 a dále xm+2 = · · · = xm = 0. Tím jsme však dosáhli opět základní přípustné řešení, neboť jedna základní dříve nenulová proměnná se stala nulovou, tudíž nezákladní a jiná dříve nenulová, nezákladní proměnná se stala základní nenulová. Je tedy k-tá proměnná vylučovanou proměnnou a (m + 1)-ní proměnná zařazovanou proměnnou. Když jsme určili nové základní řešení s vyšší hodnotou účelové funkce, můžeme postup opakovat. Zjistíme, zda je u některé nezákladní proměnné rozdíl (c0 − c) záporný. Není-li, máme optimální řešení. Je-li rozdíl (c0 − c) záporný u více nezákladních proměnných, určíme nejdříve klíčový sloupec a to tak, že za něj zvolíme ten, kde hodnota rozdílu (c0 − c) je nejmenší záporné číslo. Potom určíme klíčový řádek a dosazením příslušné hodnoty za zařazovanou proměnnou nalezneme nové, lepší základní přípustné řešení. Protože počet základních řešení je konečný, musíme posléze dojít k jednomu z následujících dvou výsledků: • U žádné proměnné už není rozdíl (c0 − c) záporný. To znamená, že nelze hodnotu účelové funkce zvýšit, tj. máme optimální řešení (maximalizujeme). • Alespoň u jedné proměnné je rozdíl (c0 − c) záporný, avšak všechny koeficienty u této proměnné jsou záporné nebo nuly. Pak může účelová funkce růst neomezeně, ale řešení nebudou základní. 122
Příklad. Simplexovou metodu užijeme při hledání, již uvedeného, optimálního řešení z předchozího praktického příkladu. Zároveň si ukážeme práci s přídatnými proměnnými. Hledejme tedy nezáporný vektor x = (x1 , . . . , x5 ) vyhovující nerovnostem 0, 4x2 + 0, 3x3 + 0, 6x4 + 0, 6x5 ≤ 1 500 0, 05x1 + 0, 2x2 + 0, 1x3 + 0, 1x4 ≤ 300 0, 1x1 + 0, 2x2 + 0, 2x3 + 0, 1x4 + 0, 2x5 ≤ 450 a maximalizující funkci z = 20x1 + 120x2 + 100x3 + 140x4 + 40x5
(11.1)
K levé straně každé nerovnosti připočteme postupně nezáporné přídatné proměnné x6 , x7 , x8 , které vyjadřují rozdíl mezi levou a pravou stranou. O přídatné proměnné je třeba rozšířit vektor řešení. V účelové funkci se přídatné proměnné neobjeví, mají nulové ceny. Výraz pro účelovou funkci však připojíme k soustavě rovnic, přičemž z budeme považovat za další proměnnou a členy na pravé straně rovnice převedeme nalevo. Po těchto úpravách dostáváme následující model: Hledáme vektor x = (x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 ) vyhovující rovnostem 0, 4x2 + 0, 3x3 + 0, 6x4 + 0, 6x5 + x6 0, 05x1 + 0, 2x2 + 0, 1x3 + 0, 1x4 + x7 0, 1x1 + 0, 2x2 + 0, 2x3 + 0, 1x4 + 0, 2x5 + x8 −20x1 − 120x2 − 100x3 − 140x4 − 40x5 + z
= = = =
1 500 300 450 0
maximalizující funkci z = 20x1 + 120x2 + 100x3 + 140x4 + 40x5 a splňující podmínky nezápornosti xj ≥ 0
(j = 1, 2, . . . , 8)
Vysvětleme ekonomický smysl přídatných proměnných, které vyjadřují rozdíly mezi pravými a levými stranami nerovností. Pravá strana první nerovnosti vyjadřuje množství tuku, jež je k dispozici pro výrobu, levá strana 123
udává spotřebu tuku na uvažovaný výrobní program x. Proměnná x6 představuje tedy rozdíl mezi množstvím tuku, jež je k dispozici a množstvím, jež se spotřebuje, tj. nespotřebovanou část suroviny − tuku. Podobně x7 a x8 . Problém lineárního programování, který právě řešíme, je typu Ax ≤ b. Obecně nerovnosti typu ≤ vyjadřují omezenost nějakých výrobních zdrojů a přídatné proměnné vyrovnávající tyto nerovnosti vyjadřují pak nespotřebovaná množství, nevyužitý díl těchto zdrojů. Ekonomickou interpretací se vysvětluje nulové ocenění přídatných proměnných v účelové funkci. Koeficienty proměnných v účelové funkci obecně vyjadřují přínos jednotkové hodnoty proměnné k hodnotě účelové funkce, v našem případě přínos výroby jednoho kilogramu výrobku k hodnotě odbytu. Nevyužité zdroje odbyt nezvýší, proto přídatné proměnné oceňujeme nulou. Kanonický tvar soustavy přepisujeme do simplexové tabulky x1
x6 x7 x8 z
x2 x3 x4 x5 x6 0, 4 0, 3 0, 6 0, 6 1 0, 05 0, 2 0, 1 0, 1 0, 1 0, 2 0, 2 0, 1 0, 2 −20 −120 −100 −140 −40
x7
x8
1 1
1 500 300 450
v níž také provádíme celý optimalizační proces. Základní proměnné jsou x6 , x7 , x8 a z, ty zapisujeme do řádkového záhlaví tabulky. Nezákladní proměnné jsou x1 , x2 , x3 , x4 , x5 , ty zapisujeme do sloupcového záhlaví tabulky. Výchozí základní řešení x1 = (0, 0, 0, 0, 0, 1 500, 300, 450, z = 0) běžně čteme přímo ze simplexové tabulky. Základní proměnné jsou rovny hodnotám v odpovídajícím řádku sloupce pravých stran tabulky. Nezákladní jsou rovny nule. K ekonomické interpretaci řešení poznamenejme: Nevyrábí se, hodnota produkce je nulová, zůstává nespotřebováno veškeré množství disponibilních surovin. Toto řešení nepřináší žádnou novou informaci. Slouží pouze jako výchozí bod optimalizačního procesu pro další výpočet. Optimalizační proces není ukončen. Podle testu optimality, budeme pokračovat tak, že určíme klíčový sloupec. Tím se stane příslušná nezákladní proměnná základní proměnnou. Při maximalizační úloze přichází do úvahy ty proměnné, jejichž koeficient v účelové funkci je záporný. Při minimalizační úloze naopak kladný. 124
Nastane-li tato situace u více proměnných, volíme tu, pro kterou je absolutní hodnota jejího koeficientu největší. V našem případě je to proměnná x4 . Zároveň určíme klíčový řádek následovně: Vydělíme postupně koeficienty posledního sloupce všemi kladnými koeficienty již určeného klíčového sloupce. Nejmenší z podílů určuje klíčový řádek. V našem případě postupně dostaneme 1 500/0, 6 = 2 500 < 300/0, 1 = 3 000 < 450/0, 1 = 4 500 Klíčovým je tudíž první řádek tabulky. Tím je určen klíčový prvek. V prvním řádku je základní proměnná x6 . Při přechodu od výchozího základního řešení na nové základní řešení se proměnná x4 stane základní proměnnou a x6 nezákladní proměnnou (říká se: zařadí se x4 ). Přechod provedeme eliminační metodou. První (klíčový) řádek vydělíme číslem 0, 6. Ke druhému a třetímu řádku přičteme (−0, 1)-násobek upraveného prvního řádku a ke čtvrtému ) řádku přičteme 140-násobek upraveného prvního řádku. Tj., uděláme R1 ( 10 6 a pak R21 (−0, 1), R31 (−0, 1), R41 (140). Výpočty zapisujeme opět do tabulky x1
x4 x7 x8 z
x2 x3 x4 2/3 1/2 1 1/20 2/15 1/20 1/10 2/15 3/20 −20 −26, 6 −30
x5 x6 x7 1 5/3 −1/10 −1/6 1 1/10 −1/6 100 233, 3
x8
1
2 500 50 200 350 000
Nové základní řešení vyplývající z druhého kroku je x2 = (0, 0, 0, 2 500, 0, 0, 50, 200, 350 000) Jeho ekonomický smysl je: Vyrábí se 2 500 kg čtvrtého výrobku. Ze surovin je plně spotřebován tuk, zůstává nevyužito 50 kg kakaa a 200 kg cukru. Hodnota produkce je rovna 350 000 Kč. Výpočet dále pokračuje testem optimality posledního řešení, které, jak se ukazuje ještě není optimální. Přejdeme tedy ke třetímu kroku výpočtu v simplexové tabulce. Vstupující (zařazenou) proměnnou bude x3 . Ve skupině základních proměnných nahradí proměnnou x7 , která se stává základní. Je to proto, že 2500 : (1/2) = 5000 > 200 : (3/20) > 50 : (1/20) = 1000. Klíčovým prvkem se stává 1/20. Zařazení proměnné x3 provedeme analogicky jako v kroku druhém. Druhý řádek vydělíme číslem 1/20. Upravený řádek nejdříve 125
násobíme číslem (−1/2) a přičítáme k prvnímu řádku, potom číslem(−3/20) a přičítáme k třetímu řádku a konečně číslem třicet a přičítáme ke čtvrtému řádku. Symbolicky, jde o úpravy R2 (20), R12 (−1/2), R32 (−3/20), R42 (30). Výsledky zapisujeme opět do simplexové tabulky
x4 x3 x8 z
x1 x2 x3 −1/2 −2/3 1 8/3 1 −1/20 −4/15 10 53, 3
x4 1
x5 x6 x7 x8 2 10/3 −10 −2 −10/3 20 2/5 1/3 −3 1 40 133, 3 600
2 000 1 000 50 380 000
Ve třetím kroku dostáváme řešení x3 = (0, 0, 1 000, 2 000, 0, 0, 0, 50, 380 000) které je již optimální, neboť všechny koeficienty v řádku se záhlavím z jsou nezáporné. V ekonomické interpretaci dává toto řešení optimální výrobní program: Vyrábět pouze dva výrobky, a to třetí výrobek v množství 1 000 kg a čtvrtý výrobek v množství 2 000 kg. Při tomto výrobním programu se plně spotřebují dvě suroviny, tuk a kakao. Nevyužito zůstane 50 kg cukru. Hodnota produkce je 380 000 Kč. Z daných surovin není možno za předpokládaných podmínek (pevné koeficienty spotřeby) získat větší. Pokud se nepoužívá některý s programů na řešení úloh lineárního programování, ruční výpočet se provede tak, že jednotlivé tabulky na sebe navazují a vytvoří tak jednu tabulku.
126
Literatura [1] Bican, L.: Lineární algebra. SNTL, Praha 1979 [2] Coufal, J.–Klůfa, J.: Učebnice matematiky I. VŠE, Praha 1996 [3] Havel, V.–Holenda, J.: Lineární algebra. SNTL, Praha 1984 [4] Kořínek, V.: Algebra. ČSAV, Praha 1956 [5] Klucký, D.–Marková, L.: Lineární algebra a geometrie pro fyziky. Skriptum UP, Olomouc 1991 [6] Mac Lane–Birkhoff: Algebra. ALFA, Bratislava 1973 [7] Novotný, M.: S algebrou od jazyka ke gramatice a zpět. Academia, Praha 1988 [8] Tarski, A.: Úvod do logiky. Academia, Praha 1966 [9] Proskurjakov, V., I.: Sbornik zadač po linejnoj algebre. Nauka, Moskva 1970 [10] Dubčák, F.: Cvičení z matematiky. Skriptum FT VUT, Zlín 1981 [11] Ayres, F., Jr.: Matrices. Schaum publ. co., New York 1962 [12] Vaculík, J.–Zapletal, J.: Podpůrné metody rozhodovacích procesů. Masarykova univerzita, Brno 1998
127
Obsah
128