Jordanův rozklad Problém lineárního programování Matematika I – 8b Jordanův tvar matic (dokončení) problém lineárního programování Jan Slovák Masarykova univerzita 7. 11. 2012 Jordanův rozklad Problém lineárního programování Obsah přednášky 1 Jordanův rozklad 2 Problém lineárního programování Jordanův rozklad Problém lineárního programování Plán přednášky 1 Jordanův rozklad 2 Problém lineárního programování Jordanův rozklad Problém lineárního programování Nilpotentní a cyklická zobrazení – připomenutí Definition Lineární zobrazení f : V → V se nazývá nilpotentní, jestliže existuje celé číslo k ≥ 1 takové, že iterované zobrazení f k je identicky nulové. Nejmenší číslo k s touto vlastností se nazývá stupněm nilpotentnosti zobrazení f . Zobrazení f : V → V se nazývá cyklické, jestliže existuje báze (u1, . . . , un) prostoru V taková, že f (u1) = 0 a f (ui ) = ui−1 pro všechna i = 2, . . . , n. Jordanův rozklad Problém lineárního programování Jinými slovy, matice f v bázi z definice cyklického zobrazení je tvaru A =    0 1 0 . . . 0 0 1 . . . ... ... ...    . Jordanův rozklad Problém lineárního programování Jinými slovy, matice f v bázi z definice cyklického zobrazení je tvaru A =    0 1 0 . . . 0 0 1 . . . ... ... ...    . Je-li f (v) = a · v, pak pro každé přirozené k je f k(v) = ak · v. Zejména tedy může spektrum nilpotentního zobrazení obsahovat pouze nulový skalár (a ten tam vždy je). Jordanův rozklad Problém lineárního programování Přímo z definice plyne, že každé cyklické zobrazení je nilpotentní, navíc je jeho stupeň nilpotentnosti roven dimenzi prostoru V . Operátor derivování na polynomech je příkladem cyklického zobrazení. Kupodivu to platí i naopak a každé nilpotentní zobrazení je přímým součtem cyklických. Navíc pro každé lineární zobrazení f : V → V , pro které je součet algebraických násobností vlastních čísel roven dimenzi (to nastane vždy pro prostory nad komplexními skaláry), existuje jednoznačný rozklad V na invariantní podprostory Vi příslušné k jednotlivým vlastním číslům λi , na kterých je zobrazení f − λi idVi nilpotentní. Jordanův rozklad Problém lineárního programování V Jordanově rozkladu vystupují vektorové (pod)prostory a lineární zobrazení na nich s jediným vlastním číslem λ a maticí J =      λ 1 0 . . . 0 0 λ 1 . . . 0 ... ... ... ... 0 0 0 . . . λ      . Takovýmto maticím (a odpovídajícím invariantním podprostorům) se řídá Jordanův blok. Jordanův rozklad Problém lineárního programování Theorem (Věta o Jordanově kanonickém tvaru) Nechť V je vektorový prostor dimenze n a f : V → V je lineární zobrazení s n vlastními čísly včetně algebraických násobností. Pak existuje jednoznačný rozklad prostoru V na přímý součet podprostorů V = V1 ⊕ · · · ⊕ Vk takových, že f (Vi ) ⊂ Vi , zúžení f na každé Vi má jediné vlastní číslo λi a zúžení f − λi · id na Vi je buď cyklické nebo nulové zobrazení. Věta tedy říká, že ve vhodné bázi má každé lineární zobrazení blokově diagonální tvar s Jordanovými bloky podél diagonály. Celkový počet jedniček nad diagonálou v takovém tvaru je roven rozdílu mezi celkovou algebraickou a geometrickou násobností vlastních čísel. Jordanův rozklad Problém lineárního programování Theorem (Věta o Jordanově kanonickém tvaru) Nechť V je vektorový prostor dimenze n a f : V → V je lineární zobrazení s n vlastními čísly včetně algebraických násobností. Pak existuje jednoznačný rozklad prostoru V na přímý součet podprostorů V = V1 ⊕ · · · ⊕ Vk takových, že f (Vi ) ⊂ Vi , zúžení f na každé Vi má jediné vlastní číslo λi a zúžení f − λi · id na Vi je buď cyklické nebo nulové zobrazení. Věta tedy říká, že ve vhodné bázi má každé lineární zobrazení blokově diagonální tvar s Jordanovými bloky podél diagonály. Celkový počet jedniček nad diagonálou v takovém tvaru je roven rozdílu mezi celkovou algebraickou a geometrickou násobností vlastních čísel. Všimněme si, že jsme tuto větu plně dokázali v případech, kdy jsou všechna vlastní čísla různá nebo když jsou geometrické a algebraické násobnosti vlastních čísel stejné. Jordanův rozklad Problém lineárního programování Důkaz fakt komplikovaný – v učebnici je a zde náznak na tabuli :-) Jordanův rozklad Problém lineárního programování Plán přednášky 1 Jordanův rozklad 2 Problém lineárního programování Jordanův rozklad Problém lineárního programování Dualita v lineárním programování Uvažujme reálnou matici A s m řádky a n sloupci, vektor omezení b a řádkový vektor c zadávající účelovou funkci. Z těchto dat můžeme sestavit dva problémy lineárního programování pro x ∈ Rn a y ∈ Rm. Maximalizační problém: Maximalizuj c · x za podmínky A · x ≤ b a zároveň x ≥ 0. Minimalizační problém: Minimalizuj yT · b za podmínky yT · A ≥ cT a zároveň y ≥ 0. Říkáme, že tyto problémy jsou vzájemně duální. Jordanův rozklad Problém lineárního programování Řekneme, že jde o řešitelný problém, jestliže existuje nějaký přípustný vektor x, který vyhoví všem omezujícícm podmínkám. Řešitelný maximalizační, resp. minimalizační problém je ohraničený, jestliže je účelová funkce na množině vyhovující omezením ohraničená shora, resp. zdola. Lemma Je-li x ∈ Rn přípustný vektor pro standarní maximalizační problém a y ∈ Rm je přípustný vektor pro duální minimalizační problém, pak pro účelové fuknce platí c · x ≤ yT · b Důkaz. Jde vlastně jen o snadné pozorování: x ≥ 0 a cT ≤ yT · A, ale také y ≥ 0 a A · x ≤ b, proto musí platit i c · x ≤ yT · A · x ≤ yT · b. Jordanův rozklad Problém lineárního programování Odtud okamžitě vidíme, že jestliže jsou oba duální problémy řešitelné, pak musí být i ohraničené. Ještě zajímavější je následující postřeh přímo vycházející z nerovnosti v předchozí větě. Corollary Jestliže existují přípustné vektory x a y duálních lineárních problémů takové, že pro účelové funkce platí c · x = yT · b, pak jde o optimální řešení obou problémů. Theorem (Věta o dualitě) Je-li standardní problém lineárního programování řešitelný a ohraničený, pak je takový i jeho duální problém, optimální hodnoty jejich účelových funkcí splývají a optimální řešení vždy existuje. Jordanův rozklad Problém lineárního programování Povšimněme si ještě pěkného přímého důsledku právě zformulované věty o dualitě: Corollary (Věta o ekvilibriu) Uvažme příspustné vektory x a y pro standarní maximalizační problém a jeho duální problém. Pak jsou oba tyto vektory optimální, právě tehdy když yi = 0 pro všechny souřadnice s indexem i, pro které n j=1 aij xj < bi a zároveň xj = 0 pro všechny souřadnice s indexem j, pro které m i=1 yi aij > ci . Jordanův rozklad Problém lineárního programování proof Předpokládejme, že platí oba vztahy z předpokladu implikace ve větě. Pak tedy můžeme v následujím výpočtu počítat s rovnosti, protože sčítance s ostrou nerovností mají stejně u sebe nulové koeficienty: m i=1 yi bi = m i=1 yi n j=1 aij xj = m i=1 n j=1 yi aij xj a z stejného důvodu také m i=1 n j=1 yi aij xj = n j=1 cj xj . Tím máme dokázánu jednu implikaci z tvrzení díky větě o dualitě. Jordanův rozklad Problém lineárního programování Důkaz – pokračování Předpokládejme nyní, že x a y jsou skutečně optimální vektory. Víme tedy, že platí m i=1 yi bi ≥ m i=1 n j=1 yi aij xj ≥ n j=1 cj xj , ale zároveň jsou si levé a pravé strany rovny. Nastává tedy všude rovnost. Přepíšeme-li prvou rovnost jako m i=1 yi bi − n j=1 aij xj = 0 vidíme, že může být naplněna jen za podmínek ve větě, protože jde o nulový součet samých nezáporných čísel. Z druhé rovnosti stejně plyne i druhé zbylé tvrzení a důkaz je ukončen. Jordanův rozklad Problém lineárního programování Věty o dualitě a ekvilibriu jsou užitečné při řešení problémů lineárního programování, protože nám ukazují souvislosti mezi nulovostí jednotlivých dodatečných proměnných a naplňování omezujících podmínek.