1
060221
1 060221 1.1 Permutace Definice 1. Permuntací množiny {1, 2, , n} rozumíme zobranení p: {1, 2, , n} → {1, 2, , n}, které je prosté a na. zápis permutace tabulkou: x 1 2 3 4 5 6 p(x) 4 1 3 2 6 5 zkrácený zápis: (4, 1, 3, 2, 6, 5) grafem: (šipky) rozkladem na cykly: (1, 4, 2), (5, 6), (3) zkráceně se cykly délky 1 vynechávají pozor - zkrácený zápis se shoduje (graficky) se zápisem rozkladem na cykly Notace 2. |Sn | = n! sn množina všech permutací množiny {1, 2, , n} ◦ skládání permutací - binární operace na Sn !není komut. př:(1, 3, 2) ◦ (2, 1, 3) = (3, 1, 2) p−1 inverzní permutace p(i) = j ⇔ p−1(j) = i
?
Definice 3. Transpozice je permutace s pouze jedním cyklem délky 2 a ostatní cykly mají délku 1. Pozorování: Každá permutace lze složit z transpozic
Důkaz. indukcí podle cyklů délky ≥ 3 Bůno - cyklus délky k probíhající postupně čísla 1, 2, , k můžu složit jako transpozici (1, k) a cyklus délky k − 1 cyklus délky k lze rozložit na k − 1 transpozici pozn.:
rozložení není jednoznačné
Definice 4. Nechť p je permutace množiny {1, 2, , n} potom inverzí permutace p rozumíme dvojici prvků i, j ∈ {1, 2, , n} takovou, že i < j & p(i) > p(j) Příklad 5. pro p = (4, 1, 3, 2, 6, 5) tvoří (1, 4) inverzi jsou to ty šipky, které se kříží
Definice 6. znaménko permutace p nazveme veličinu sgn(p) = ( − 1)počet
in verzí perm uta ce p
znaménko je jednoznačné určení počtu inverzí ze zápisu tabulkou: pro každé číslo se dívám, kolik je před ním větších čísel; všechna tato čísla sečtu znaménko permutace (4, 1, 3, 2, 6, 5) = ( − 1)5 = − 1 Pozorování: sgn(q ◦ p) = sgn(p) · sgn(q)
Důkaz.
#křížení(q ◦ p) = #křížení(p) + #křížení(p) − 2|{(i, j): i < j & p(i) > p(j)& q(p(i)) < q(p(j))}| t ento člen se nepro jeví v argum entu nad (-1)
2
Sekce 2
Pozorování: Každá transpozice má znaménko -1 Důkaz. každá šipka protne všechny šipky mezi nimy + navíc se protnou spolu
Důsledky: Znaménko permutace lze určit jako: sgn(p) = ( − 1)# transpozic nebo jako: sgn(p) = ( − 1)# cyklů sudé délky Důsledek: sgn(p−1) = sgn(p) Důkaz. p ◦ p−1 = id
sgn(id) = 1
1.2 Determinant Definice 7. Nechť A je čtvercová matice řádu n nad tělesem T. Potom Determinant matice A je dán výrazem n X Y det(A) = sgn(p) ai,p(i) p∈Sn
i=1
dá se dobře násobit z definice - horní trojůhelníková, 2x2, 3x3, 1x1 1.2.1 Vlastnosti determinantu Pozorování: det(AT ) = det(A) Důkaz. det(AT ) =
X
sgn(p)
p∈Sn
kde
n Y
(AT )i,p(i) =
X
sgn(p)
p∈Sn
i=1
n Y
a p(i),i =
X
q∈Sn
i=1
sgn(q)
n Y
ai ′,q(i ′) = det(A)
i ′ =1
q = p−1 p(i) = i ′ q(i ′) = i Korolár 8. přerovnání sloupců matice A podle permutace Q Důkaz.
det(A ′)
? =
X
sgn(q)
X
sgn(p)sgn(q −1)
p∈Sn
= sgn(p◦ q
−1
)
n ezm ěn í zna m én ko d eterm inan tu ⇔ sgn(q) = 1 zm ěn í zn am énko determ in an tu ⇔ sgn(q) = − 1
(A ′)i j = ai,q(j); aij = (A ′)i, q −1(j)
sgn(p)
p∈Sn
n Y
(A ′)i, p(q(i))
i=1 n Y
=
X
sgn(p)sgn(q)sgn(q −1)
p∈Sn
ai,(p◦ q −1)(i) = sgn(q)det(A)
i=1
2 060228
Důsledky: přerovnání řádků se chová stejně, jako přerovnání sloupců
n Y
ai, p(q −1(i))
=
i=1
3
060228
- záměna dvou řádků změní znaménko determinantu (odpovídá transpozici ... ta má znaménko -1). -jsou-li 2 řádky shodné, potom je determinant roven nule. A ′ po záměně dvou stejných řádků => A ′ = A det(A) = − det(A ′) = − det(A) ⇔ 2 det(A) = 0 ⇒ det(A) = 0 -tato úvaha platí pouze v tělesech charakteristiky
2
Tvrzení 9. Determinant je lineární funkcí každého sloupce (i řádku) dané matice. Důkaz. búno se omezíme jen na řádky. 1. Linearita vůči skalárnímu násobku. Buď A ∈ T n×n , t ∈ T , označím A ′ skalárem t. a1 1 A = ai1 an 1 det(A ′) = t
X
sgn(p)
X
sgn(p)
p∈Sn n Y
a1 1 A ′ = tai1 an 1
a1 n ain i an n
X
(A ′) j, p(j) =
j =1
řádku aij = bij + cij
a1 1 ai 1 an 1
a1 n ai n an n
=
′
=
j =1
??
sgn(p)a1, p(1) bi, p(i) an,p(n) +
p∈Sn
X
a1 n b i n + ci n an n
mějme rozklad i-tého
?
=
ai, p(i)
sgn(p)a1,p(1) ci, p(i)an,p(n) = det(B) + det(C)
p∈Sn
=
A )i,p(i)
Důsledek: Přičtení t-násobku j-tého řádku (nebo sloupce) k i-tému (i nant A...původní matice A ′...pozměněná det(A ′) = [matice ij] + t det[matice jj] = det(A) det(A)
an, p(n)
a1 1 a1 n B = bi 1 bin an 1 an n a1 1 a1 n C = ci1 cin an 1 an n n X X Y sgn(p) a1,p(1) (bi, p(i) + ci, p(i)) an, p(n) sgn(p) a j , p(j) =
p∈Sn
p∈Sn
sgn(p) a1, p(1)a2,p(2) tai, p(i)
a1 1 bi 1 + ci 1 an 1
X
?
a1 n tai n an n
p∈Sn
pro j = 1, , n
2. Linearita vůči sčítání A =
det(A)
a j ,p(j) = t det(A)
j =1
p∈Sn
n Y
matici, která vznikne z A vynásobením i-tého řádku
j) nezmění determi-
0
2.0.2 Výpočet determinantu: −
převedením matice na odstupňovaný tvar využitím elem. operace - přičtení t-násobku jtého řádku k i-tému. ...podobně jako Gaussovou eliminací NESMÍME: řádky násobit t ∈ T ; zaměňovat dvojice řádků ALE: můžeme provádět elementární operace i na sloupcích
Úkol: spočtěte determinant Vandermondovy matice.
4
Sekce 3
pro různá x1, , xn−1
1 x1 x21 1 x2 x22 1 x3
1 xn x2n
xn−1 1 xn−2 2
xn−1 n
2.1 Geometrický význam determinantu matic z
R
n×n
... |det(A)| udává objem rovnoběžnstěnu z Rn jehož hrany jsou určeny řádky (sloupci) matice A V = {x ∈ R3 : x = α1 v1 + α2 v2 + α3 v3 : α1, α2, α3 ∈ h0, 1i Také: je-li f lineární zobrazení f : Rn → Rn a A je matice tohoto zobrazení (A = [f ]xx) potom se objemy těles mění podle předpisu: vol(f (v)) = |det(A)| vol (v) v ⊆ Rn Teorém 10. Nechť A a B jsou čtvercové matice stejného řádu nad tělesem T. Potom platí: det(A · B) = det(A) · det(B) Důkaz. Je-li A nebo B singulární singulární matice A ... alespoň 1 řádek je lineární kombinací ostatních nemění determinant lze získat nulový řádek det(A) = 0 součin A · B je též singulární → det(A · B) = 0
n úpravami které
Předpokládejme, že A i B jsou regulární, rozložíe A jako součin elementárních matic A = E1E2 Ek det(A B) det(E1)
det((E1E2 Ek)B)
= det(E2
inverzním p ostup em
=
E3 Ek
=
iterace
B) = det(E1)
det(E1(E2 EkB)) det(E2) det(Ek)
det(B)
= =
det(E1E2 Ek) det(B)
Pokud provedeme elementární operaci En (vynásobíme) na matici (En+1 EkB), projeví se na determinantu jako
1 násob ek, t
pokud byla úprava vynob ení nějakého řádku číslem t − 1násobek, p okud úprava byla prohození dvou řádků jinak se determ inant nezm ění
Teorém 11. Čtvercová matice A je regulární ⇔ det(A) 0
3 060307 1
Důsledek: det(A −1) = det(A) Značení: Nechť Aij je matice, která vznikne z matice A vypuštěním i-tého řádku a j-tého sloupce n P Pozorování: Pro libovolné i platí: det(A) = ( − 1)i+ j det(Aij )ai j rozvoj determinantu podle i-tého řádku
j =1
Důkaz. a) vytýkáním prvků aij ze vzorce pro det. b) využitím linearity - i-tý řádek rozložím jako lin. kombinaci řádků z kanonické báze (ai1, ai2, , ain) = ai1(1, 0, , 0) + ai2 (0, 1, 0, 0) + + ain (0, 0, , 0, 1)
5
060314
potom: det
(
? ? A
na i-tém řádku je ai 1 ai n
ai1det(
=
? A(1)
)
+
na i-tém řádku je 1 0 0 0
) + + ain det(A(n))
A(2)
ai2 det(
)
na i-tém řádku je 0 1 0 ... 0
Definice 12. Pro čtvercovou matici A definujeme adjungovanou matici adj(A) předpisem (adj(A))ij = ( − 1)i+ j det(A ji )
? !!!!
1
Teorém 13. Pro libovolnou regulární matici A nad tělesem T platí: A −1 = det(A) adj(A) 1 A det(A) adj(A) = In
Důkaz. prozkoumáme součin A · adj(A) = det(A)In
i-tý řádek A · i-tý sloupec adj(A) = rozvoj det(A) podle i-tého řádku
n P
aij ( −
j =1
1)i+j det(Aij ) = det(A) k-tý řádek A · i-tý sloupec adj(A) = rozvoj determinantu v matici, kde i-tý řádek byl n P akj ( − 1)i+j det(Aij ) = 0 nahrazen k-tým řádkem...t.j. má 2 stejné řádky j =1
Důsledek: A ∈ Rn×n , celočíselná: det(A) = ± 1 ⇔ A−1 celočíselná
Dcv: Určete det(adj(A)), zkuslosti na det(A) & pro regulární matice Teorém 14. (Cramerovo pravidlo) Nechť A je regulární matice. Potom řešení soustavy A x = b lze psát jako xi = Ai→b je matice, která vznikne z matice A nahrazením i-tého sloupce vektorem b
det(Ai→b) , det(A)
kde
Důkaz. odtud
Ax = b ⇔ x = A−1b =
1 adj(A)b det(A)
n X 1 1 xi = det(Ai→b) adj(A)ij bj = det(A) det(A)
j=1
3.1 Vlastní čísla a vlastní vektory Definice 15. Nechť V je vektorový prostor nad tělesem T a f : V → V je lineární zobrazení. Potom λ ∈ T pro nějž existuje nenulový vektor x ∈ V t.ž. f (x) = λ x se nazývá vlastní číslo zobrazení f. Vlastní vektor příslušný vlastnímu číslu λ je libovolné x ∈ V t.ž. f (x) = λx Poznámka 16. Je-li dim(V ) < ∞ potom V ≃ T n a f lze reprezentovat maticí ∈ T n×n. Odtud můžeme definici rozšířít a hovorit o vlastních číslech matic & vlastních vektorech matic. Ax = λx
4 060314 Pozorování: Vlastní vektory příslušné stejnému λ tvoří podprostor V . f (cx) = cf (x) = cλx = λ(cx) f (x + y) = f (x) + f (y) = λx + λy = λ(x + y)
6
Sekce 4
DÚ [f ]kk =
1 1 1 0
Teorém 17. Nechť f je lineární zobrazení a λ1, λ2, , λn jsou navzájem různá vlastní čísla zobrazení f a x1, , xn jsou příslušné nenulové vlastní vektory. Potom platí, že x1, x2, , xn jsou lineárně nezávislé. Důsledky a) různá vlastní čísla mají různé vl. vektory b) #vlastních čísel ≤ dim(V ) Důkaz. indukcí & sporem nechť x1, , xk & λ1, , λk tvoří nejmenší protipříklad (tzn. λ1, , λk jsou různá, x1, , xk LZ) k X aixi = 0 ∃a1, ,ak ∈T i=1
k X
0 = f (0) = f
!
aixi =
i=1
?
0 = λk 0 = λk
k X
k X
ai x i =
k P
aiλixi −
i=1
k P
aiλkxi =
i=1
k P
?
k X
aiλkxi
i=1
(λi − λk) aixi =
i=1 = 0 pro i=k
k X i=1
i=1
i=1
0=0−0=
aif (xi) =
k−1 P i=1
lze vzít bázi X & nalézt matici A = [f ]B B [f ]B B [x]B = λ[x]B přeznačením
[f ]B B [x]B
dostaneme maticovou rovnici A ∈ T n×n Ax¯ = λx¯ x¯ ∈ T n x∈λ
A x¯
[x]B
?
(λi − λk)
aixi
x1, ,xk −1 jsou LZ - sp or s m inim alitou
4.0.1 Vlastnosti vlastních čísel matic f : V → V ; dim(V ) = n; x ∈ V ; f (x) = λx
aiλixi
[f (x)]B = [f ]BB [x]B ?vektor x ∈ V k [λx]B = λ[x]B
∈T n
?Co platí pro 2 matice téhož zobrazení (vůči různým bazím) Označme báze X , Y [f ]XX = A platí [f ]XX = [id]Y X [f ]Y Y [id]X Y matice přechodu jsou regulární označíme R = [id]X Y [f ]Y Y = B rovnost přepíšu A = R −1BR Definice 18. Čtvercové matice A a B řádu n se nazývají podobné, pokud existuje regulární R taková, že A = R−1BR. Teorém 19. Jsou-li matice A a B podobné a λ je vlastní číslo matice A a x je příslušný vlastní vektor. Potom λ je také vlastní číslo matice B a y = R x je příslušný vlastní vektor (pro R: AR−1BR)
060321
Důkaz. BÚNO x je netriviální
??
7
By = (RAR−1)(Rx) = R(Ax) = R(λx) = λy B
y
⇒ λ je vl. číslo B (x netriv ⇒ Rx = y je také netriv.) ⇒ Y je vl. vektor příslušný x
Cíl k dané matici hledáme co nejjednodušší matici, která je jí podobná, pokud možno diagonální. Dcv Nalezněte vl. čísla & vektory diagonální matice Definice 20. Matice se nazývá diagonalizovatelná, pokud je podobná nějaké diagonální matici. Užití diagonalizovatelných matic A = R −1DR a) výpočty součinu matic An = (R−1DR)n = R −1 DRR −1 DR R = R −1DnR lze použít i výpočet inverze n = − 1
5 060321 1. Určete vlastní čísla a vlastní vektory diagonální matice vlastní vektory ... e1, , en d1 1 0 kanonické báze d 2 2 D = Dei = diiei ⇒ d1 1, , dnn jsou vlastní čísla. 0 dn n (0, , 0, 1, 0, 0, , 0) Vlastní čísla matice
1 1 1 0
A = R −1DR A prostá, D diagonální. potom λi = dii je i-té vlastní číslo matice A (A a D jsou podobné ⇒ vlastní čísla) i-tý sloupec R−1 je vlastní vektor příslušný λi Tvrzení 21. Pokud má matice A ∈ T n×n telná.
n různých vlastních čísel, potom je diagonalizova-
vlastní vektory x1, , xn Důkaz. Vlastní čísla λ1, , λn příslušné sestavím matici
| R = x1 |
| xn |
LN
R je regulární
Axi = λi xi A R=R D
⇓
matice
m A=R DR −1
x1 0
0 xn
t.j. různá vlastní čísla ... postačující podmínka na diagonalizovatelnost. Nutná & postačující podmínka (charakterizace diagonalizovatelných matic): Tvrzení 22. Matice A ∈ T n×n je diagonalizovatelná ⇔ existuje n lineárně nezávislých vlastních vektorů. Důkaz. ⇒ . existuje R: R −1AR = D neboli AR = RD potom sloupce R jsou LN vlastní vektory ⇐ . z LN vlastních vektorů sestavíme R a ta splňuje AR = RD
8
Sekce 5
5.0.2 Charakteristický mnohočlen Definice 23. Nechť A je čtvercová matice řádu n nad T. Potom charakteristický mnohočlen matice A v proměnné t je dán výrazem PA(t) = det(A − t · I) Příklad 24. A = 11 10
PA(t) = det
1−t 1 1 0−t
= t2 − t − 1
?
Pozorování je vždy stupně n
Teorém 25. Pro matici A ∈ T n×n platí: číslo λ je vlastním číslem matice A ⇔ λ je kořenem charakteistického polynomu matice A t.j. PA(λ) = 0 Důkaz. λ je vlastní číslo matice A ⇔ ∃ netriv. x takové, že Ax = λx ⇔ ∃ netriviální x takové, že (A − λI)x = 0
x = Ix λx = (λI)x
h om . soustava
⇔ x je neriv. řešení hom. soustavy s maticí A − λI ⇔ matice A − λI je regulární ⇔ det(A − λI) = 0
?
|| PA(λ)
Příklad 26. osová souměrnost A = rotace o 90˚: A=
0 −1 −1 0
−t ; PA(t) = − 1
− 1 = t2 − 1 −t
kořeny jsou λ1 = 1; λ2 = − 1
Tvrzení 27. Podobné matice mají stejná vlastní čísla, protože mají shodné charakteristické mnohočleny. Důkaz.
?
A = R−1 BR I
PA(t) = det(A − t I) = det(R
−1
tI) det(R) = PB (t)
B R − t (R
−1
IR )) = det(R−1(B − t I)R) = det(R −1) det(B −
Tvrzení 28. Pro libovolné čtvercové matice A a B stejného řádu mají matice AB a B A stejná vlastní čísla Dcv:
Nalezněte jednoduchý důkaz, jsou-li A, B regulární
Důkaz. Opakování:
I J K L
P Q R S
=
IP + J R IQ + J S K P + LR KQ + L S
∈T Zn ×Zn AB 0 I A AB AB A = B 0 0 I B BA I A 0 0 A B AB A = 0 I B BA B BA t.j matice ABB 00 a B0 B0A jsou
I ,J ,K ,L,P ,Q,R,S ∈T n ×n
Teorém 29. (Cayley-Hamilton)
si podobné protože
I A 0 I
je regulární (má hodnost Zn)
9
060328
Nechť A ∈ T n×n a PA(t) = ( − 1)ntn + an−1tn−1 + + a1t + a0 je charakteristický mnohočlem matice A Potom platí: ( − 1)nAn + an−1An−1 + + a1A + a0I = 0 k
an
Důkaz. využijeme faktu: M adj(M ) = det(M )I, za M dosadíme A − tI prvky adj(A − tI) jsou determinanty minorů matice A − tI a to jsou mnohočleny stupně nejvýše n − 1 lze adj(A − tI) rozepsat jako adj(A − tI) = tn−1Bn−1 + tn−2Bn−2 + + tB1 + B0 kde Bi je matice koeficientů u ti z prvků v adj(A − tI) (rovnost polynomů ... musí mít stejné koeficienty)
(A − t I)(t
tB1 + B0) = det(A − tI)I = PA(t)I = ( − 1) t I + an−1t n n
n−1
Bn−1 + tn−2Bn−2 +
I + + antI + a0I
+
n−1
utn: − Bn−1 = ( − 1)nI i ut pro i = 1, , n − 1 ABi − Bi−1 = aiI ut0 AB0 = a0I
vynásobíme zleva An vynásobíme zleva Ai & sečtu vše dohromady
na levé straně dostanu 0 0 = − AnBn−1 + An−1(ABn−1 − Bn−2 + = ( − 1)nAn + an−1An−1 + + a1A + a0I
Dcv: dokažte sami a jednoduše pro diagonalizovatelné A
6 060328 Pro dnešní přednášku se omezíme na těleso C ... tzv. algebraicky uzavřené těleso ... zde platí tzv. základní věta algebry Teorém 30. Každý mnohočlen stupně ≥ 1 má v tělese komplexních čísel alespoň 1 kořen Důsledek: Každý komplexní mnohočlen stupně n ≥ 1 lze rozložit na součin n jednočlenů. p(t) = an(t − λ1)(t − λ2) (t − λn)
kde λ1, , λn jsou kořeny daného mnohočlenu (důkaz indukcí)
Důkaz. Idea důkazu: p(t) = antn + an−1tn−1 + + a1t + a0 ∀i=0, ,n ai ∈ C búno a0 0 (jinak t = 0 je kořen) an 0 n ≥ 1 & techn. předp. a1 0 označme si Dr = {t ∈ C: |t| = r} pro r ∈ R je r ≥ 0 a) r → ∞ ?Jak vypadá p(Dr) pro b) r→0
chceme ∃λ∈C p(λ) = 0
b) pro r → 0 je p(Pr) v okolí a0 a) r ≫ max {ai } obraz p(Dr) pro r hodně velké Zvážíme-li spojitý přechod od r → 0 k r → ∞ musí obraz Dr pro nějaké r ∈ R obsahovat 0 ⇒ ∃ kořen pokud máme A ∈ Cn×n, víme, že pA(t) lze rozložit na jednočleny pA(t) = (λ1 − t)r1(λ2 − t) (λk − t)rk r2
? ?
10
Sekce 6
λ1, , λk různé kořeny ri algebraickou násobností vlastního čísla λi r1 + r2 + + rk = n
Pozorování:
?
? an a0
pA(t) = ant n + + a1t + a0
= ( − 1)n = det(A)
= λr11λr22 λrkk
dosazením 0 do PA(t)
an−1 = ( − 1)
n−1
(r1λ1 + r2λ2 + + rkλk) = ( − 1)
prvky na diag. A
(a1,1 + a2,2 + + an,n)
n−1
?Jaký člen získáme u ( − t)n−1 v součinu (λ1 − t)(λ1 − t) (λ1 − t)(λ2 − t) (λk − t) tento koer1 x
ficient = λ1 + λ1 + + λ1 + λ2 + + λn = r1λ1 + r2λ2 + + rkλk r1x
?Jaký koef. získáme u ( − t)n−1 v det(A − tI) = pA(t)
Pozorování: tn−1 lze získat pouze ze součinu odpovídající identické permutaci t.j. (a1,1 − t)(a2,2 − t) (an,n − t) n Q ′ ai, (ostatní permutace p ∈ Sn dají součin p(i) který je stupně ≤ n − 2 v t) koef n( − t)n−1 je (a1,1 + + an,n)
i=1
Tvrzení 31. Matice A ∈ Cn×n je diagonalizovatelná ⇔ každé vlastní číslo λi splňuje rank(A − λiI) = n − ri (neboli dim(ker(A − λiI)) = ri) Důkaz. A diagonalizovatelná ⇔ ∃ báze Cn složená z vlastních vektorů A ⇔ součty dimenží prostorů vlastních vektorů t.j. ker(A − λiI) dají dohromady n. Fakt: každá čtvercová komplexní matice je podobná matici ve tvaru Jordanovy buňky Jordanův normální tvar matice λ1, , λk jsou (ne nutně různá) vl. čísla Příklad 32. matice která není diagonalizovatelná A = 10 11 λ1 = λ2 = 1
?
kdyby A měla být podobná nějaké D potom D =
1 0 0 1
∃R: R −1AR = D neboli A = R D R −1 = RR −1 = I2 I2
Cíl:
A
sp or
každá reálná symetrická matice má všechna vl. čísla
Definice 33. Nechť A je komplexní matice, potom matici AH pro níž platí (AH )ij = aj i nazýváme Hermitovskou transpozicí k matici A. (Někdy se značí A∗ , konjungovaná matice) Pozorování: platí (AB)H = B HAH pokud je součin def. Pozorování: pro standardní skalární součin hx|y i na Cn platí
11
060405
hx|y i = užití:
n P
?
Y Hx
xiy¯i =
i=1
zde sloup cové vektory vním ám e jako matice
ON (ortonormální) báze C x1, , xn sestavíme n
H
A =
− x1 −
− xn −
AHA = I
| A = x1 |
?
| xn |
Definice 34. Komplexní čtvercová matice A se nazývá unitární pokud splňuje AHA = I Definice 35. komplexní čtvercová matice se nazývá Hermitovská, pokud je rovna své Hermitovské transpozici, t.j. AH = A Teorém 36. Tvrdím, že každá hermitovská matice A má všechna vlastní čísla reálná a dokonce existuje unitární matice R taková, že R −1AR je diagonální Důkaz. příště
7 060405
Teorém 37. Každá Hermitovská matice má všechna vlastní čísla reálná, a exitstuje unitární matice R taková, že R −1AR je diagonální Důkaz. Indukcí podle n (řád matice) A ∈ Cn×n označím An zádladní věta algebry ... ∃ vlastní číslo λ (kořen ch. polynomu) & příslušný vl. vektor x. P je unitární búno vezmu kxk = 1 & doplním x na ON bázi Cn n
z těchto vektorů sestavíme pomocnou matici
| Pn = x |
H H H H H H (PnHAH n Pn) = Pn An (Pn ) = Pn AnPn = PnHAnPn je Herm
λ 0 0 An−1
AnPn 1 sloupec λ − nás. x
?
⇒λ∈R −1 & použijeme ind. předp na An−1 tzn. ∃ unitární Rn−1: Rn−1 An−1Rn−1 = Dn−1 vezmu
R n 4 Pn
?
1 0 0 Rn−1 o znač. Sn
Pozorování Pn , Sn unitární ⇒ Rn = PnSn je také unitární
? I
RnHRn = (PnSn)HPn Sn = SnH PnHPn
Sn
I
Zbývá ověřit RnHARn = (PnSn)HAPnSn = SnHPnHAPnSn =
1 0 λ 0 0 RH n−1 0 An−1
1 0 λ 0 = = Dn 0 Rn−1 0 Dn−1
Poznámka 38. větu lze sesílit pro tzv normální matice AAH = AHA
12
Sekce 7
?
interpretace v R
Důsledek: Každá reálná symetrická matice má n vl. čísel (počítáno vč. násobnosti) a navíc ∃ ortogonální R t.ž. R−1AR je diagonální ...třeba ukázat ∃ reálných vlastních vektorů, ale ty jsou řešením soustavy (A − λI) x = 0 ⇒ r eálná m atice
∃ reálné řešení
7.1 SVD rozklad (singular value decomposition) Definice 39. SVD rozkladem matice A ∈ Cm×n nazveme součin A = SDRH kde R ∈ Cn×n , S ∈ Cm×m jsou unitární a D je nezáporná reálná (částečně) diagonální matice. Geometrický význam: Je-li f : Cn → Cm lineární zobrazení s maticí A = [f ]KK tak hledáme ON báze x = {x1, , xn } prostoru Cn a Y = {y1, , ym } prostoru Cm tak, že pro i = 1, , r f (xi) = dii yi & f (xi) = 0 jinak D = S HAR ⇔ A = SDRH [f ]X Y = [id] [f ]KK [id] KY XK [id]XK = [id]Y K = S
| | x1 x2 | |
| xn = R |
Teorém 40. Pro libovolnou A ∈ Cm×n vždy existuje SVD rozklad. dokonce pro A ∈ Rm×n vždy existuje reálný SVD rozklad
?
?
“Důkaz” pokud by existoval A = SDRH AAH = (SDRH )(SDRH ) = SDRHRD H S H = S DDH S H H
H H
H
H
A A = (SDR ) (SDR ) = RD DR
d iagonální
H
d iagonální
Konstrukce R, S: AAH .Hermitovská .podobná diag. ∃unit. S: S D¯S H = AAH AH A ..Hermitovská ... podobná diag ∃unit R: R D¯ RH = AHA Konstrukce D “odmocněním” D¯ nebo D¯ Třeba ještě ukázat A = SDRH Užití: r = rank(A) prvních r řádků v RH (= prvních r sloupců v R) ... ON báze R(A) zbylých n − r řádků = zbylých n − r sloupců v R ... ON báze Ker(A) prvních r sloupců S ... ON báze S(A) 1
pseudoinverze A+ = RD +S H kde (D+)i i = d
ii
pro i = 1, , r
další užití ... přibližná řešení soustav, statistika, numerika, komprese obrazu (!jiná než F. transf. - jpeg)
7.2 Vztah skalárního součinu & unitárních matic pozorování Nechť V je vekt. prostor se skalárním součinem konečné dimenze a X = {x1, xn } je jeho ON báze.
,
13
060411
Potom pro ∀u,v ∈V platí hu|v i = Důkaz. n P αixi u= v=
i=1 n P
βi = ([v]x)i = hv |xi i
βixi
hu|vi =
n X i=1
i=1
hu|xi ihxi |vi = [v]H x [u]x
αi = ([u]x)i = hu|xi i
i=1
*
n X
n + n n X n n X X X a) = 1 pokud i = j X αiβ j hxi |x j i β jx j = αixi αiβ j = = hu|xi ihxi |v i b) = 0 pokud i j j =1
i=1 j=1
i=1
i=1
hu + v |z i = hu|z i + hv |z i hαu|vi = αhu|vi Tvrzení 41. Nechť V je vektorový prostor se skalárním součinem konečné dimenze a X = {x1, , xn } je jeho ortonormální báze a f : V → V je lineární zobrazení. Potom f zachovává skalární součin (t.j. hf (u)|f (v)i = hu|v i) právě když matice [f ]XX je unitární Důkaz. hu|vi = [v]H X [u]X H H hf (u)|f (v)i = [f (v)]H X [f (u)]X = ([f ]XX [v]X ) [f ]XX [u]X = [v]X
hu|v i = hf (u)|f (v)i ∀u,v ⇔ [f ]XX je unit.
?
[f ]H XX [f ]X X
[u]x
=In⇔[f ]X X je unitární
8 060411 8.1 Pozitivně definitní matice Skalární součin na konečnědimenzionálním prostoru X...ON báze hu|vi = [v]H x [u]x Pozorování Nechť V ≃ Cn je prostor se skalárním součinem (ne nutně tím standardním n P xiy¯i ) potom existuje matice E taková, že hu|vi = v HEu
i=1
Důkaz. vezmeme kanonickou bázi k:
u = [u]k = (u1, u2, , un)T v = [v]k = (v1, , vn)T k = e1, e2, , en ei = (0, , 0, 1, 0, , 0)
14
Sekce 8
u=
n X
uiei; v =
hu, vi =
n X
uiei ,
i=1
n X
v je j
j=1
v je j
j =1
i=1
*
n X
+
=
n X n X
uiv¯j hei |e j i = v HEu
i=1 j =1
?Jaké vlastnsti musí E splňovat, aby j. bylo možné použít pro výpočet v HEu? DCV Ukažte, že pro libovolnou bázi X prostoru V konečné dimenze ∃ matice E: hu|vi = [v]H XE[u]X Pozorování (E)ij = (E) j i Definice 42. Splňuje-li Hermitovská matice A řádu n, že pro každé x ∈ Cn {0} platí xH Ax > 0 potom se A nazává pozitivně definitní matice. Poznámka 43. xHAx ≥ 0 <, ≤ ∃x1: xH 1 Ax1 > 0 ∃x2: xH 2 A2 < 0
- pozitivně semidefinitní - negativně semidefinitní - indefinitní
Užití pozitivně definitních matic: − −
ve výpočtu sk. součinu (vůči různým bazím) Analýza: vyšetřování funkcí více proměnných .... lokální extrémy
Teorém 44. Pro Hermitovskou matici A jsou následující podmínky ekvivalentní: a) A je pozitivně defininí (tzn. xHAx > 0 ∀x 0x ∈ Cn) b) A má všechna vlastní čísla kladná.
c) existuje regulární matice U taková, že A = U HU (dokonce lze vzít U horní trojůhelníkovou) Důkaz. a) ⇒ b) . A Hermitovská ⇒ všechna vlastní čísla jsou ∈ R nechť x ∈ Cn vlastní vektor příslušný vl. číslu λ Ax = λx potom xHAx > 0 n H H P ⇒λ>0 x Ax = λx x ⇒ H xixi > 0 x x= i=1
b) ⇒ c). A Hermitovská A = RHDR kde R je unitární ^———má vl. čísla na diag. rozložím D = D˜ D˜ H ˜H ˜ H ˜ , R jsou také reg. t.j A = R D DR = U U pro U 4 D˜R ... regulární protože D
c) ⇒ a) . netriviální x: xHA x = xHU HU x = (U x)H (U x)... součin 2 netriviálních komplexně sdružených vektorů
15
060411
hUx|Uxi pro std. skalární součin
Dcv: Rozšiřte tvrzení pro p. semidefinitní matice,... Tvrzení 45. Pro pozitivně definitní matici existuje jediná horní trojúhelníková matice s kladnými prvky na diagonále ... tzv. Choleského rozklad, která splňuje A = U HU Algoritmus pro výpočet Choleského rozkladu: vstup: Hermitovská matice A výstup: Choleského rozklad, nebo odpověď, že A není poz. definitní pro i 4 1 do n opakuj uii =
s
aii −
i−1 X
uki uki
k=1
√ pokud není reálná STOP A není pozitivně definitní pro j = i + 1 do n projdi ! i−1 X 1 aij − uki ukj uij = uii k=1
Dcv: Ukažte, že pro pozitivně definitní matice A, B platí -A + B je pozitivně definitní -A−1 je pozitivně definitní
? ? ? Pozorování: Pozitivně definitní matice mají kladný determinant.
Tvrzení 46. (Jacobiho podmínka) Hermitovská matice A řádu n je pozitivně definitní pravě když mají matice A = A0, A1, An−1 kladný determinant, Ai vznikne z A umazáním posledních i sloupců a řádků. (Bez důkazu) Tvrzení 47. Bloková matice A =
a matice A˜ −
1 aaH α
α aH ˜ a A
je pozitivně definitní.
!
,
je pozitivně definitní tehdy a jenom tehdy když α > 0
Důkaz.
x1 x = x˜
∈C
⇐ vezmeme libovoné x ∈ Cn označíme ∈ Cn−1 x1 H a α = x1 α + x˜Ha x1 aH + x˜HA˜ xHA x = x1 x˜H a A x˜ 0
x˜HA˜x˜
x1 aHx˜
+
x˜H (A˜ −
1 H aa )x˜ > 0 α
> 0 pokud x˜ netriv
⇒
1. eH 1 Ae1 = α > 0
+
1 H H 1 x˜ aa x˜ − x˜HaaHx˜ α α
=
x1
x˜
= x1 αx1 + x˜Hax1 +
√ √ 1 1 (x1 α + √ x˜Ha)(x1 α + √ aHx) α α k omplexně sdr. >0 pokud netriv.
+
16
Sekce 9
1
2. nechť x˜ ∈ Cn−1 je lib. netriv. x1 = − α aHx˜ & položím x =
x1 x ˜
√ √ 1 1 1 Potom 0 < xHAx = x˜H (A − α aaH )x˜ + ( α x1 + √α x˜Ha)( α x1 + √α aHx˜ ) = 0 volbou x1
9 060418 9.0.1 Bilineární a kvadratické formy Definice 48. Nechť V je vektorový prostor nad tělesem T a f : V × V → T je zobrazení splňující: ∀α∈T ∀u,v ∈V f (αu, v) = αf (u, v) ∀u,v,w ∈V f (u + v, w) = f (u, w) + f (v, w) ∀α∈T ∀u,v ∈V f (u, αv) = αf (u, v) ∀u,v,w ∈V f (u, v + w) = f (u, w) + f (u, w) potom se f nazývá bilineární forma na V. Bilineární forma je symetrická, pokud: ∀u,v ∈Vf (u, v) = f (v, u) Zobrazení g: V → T se nazývá kvadratická forma, pokud existuje bilineární forma f t.ž. g(u) = f (u, u) ∀u∈V.
Definice 49. Nechť V je vektorový prostor nad T konečné dimenze a X = {u1, , un } je jeho báze. Pro bilineární formu f : V × V → T definujeme matici B formy f vůči bázi X předpisem bij = f (ui , u j ) Maticí kvadratické formy g: V → T rozumíme matici symetrické formy f, která g vytvořuje (pokud f existuje, je určeno jednoznačně, ovšem takové f nemusí existovat nad tělesem char. 2) Pozorování: Cauchy Počítání s maticí formy u ∈ V , [u]x = (α1, , αn)T ! n n n n n X n XX X X X αiα jbij = [u]TxB[u]x αiui α ju j = αiα jf (ui , u j ) = g(u) = f (u, u) = f i=1
j =1
i=1 j =1
i=1 j=1
Podobně f (u, v) = [u]TxB[v]x Definice 50. Analytické vyjádření bilineární formy f : V × V → T vůči konečné bázi X je n P n P bijxiy j kde xi, resp yj jsou souřadnice vektorů u a v vůči bázi X. polynom f (u, v) = i=1 j =1
(tzn. bi j jsou koeficienty z matice formy)
Podobně pro kvadratickou formu dostaneme g(u) =
n n P P
i=1 j =i
aijxix j kde aij =
2 bi j pro i j bi i pro i = j
Pozorování: g(αu) = α2 g(u) dcv Lemma 51. Nechť g: V → T je kvadratická forma s maticí B vůči bázi X potom B ′[id]TYXB [id]YX je její matice vůči bázi Y.
?
060418
Důkaz.
17
[u]x = [id]Y X [u]Y
g(u) = [u]TXB[u]X = [u]TY [id]TY XB [id]YX [u]Y
B′
Pozorování Matice kv. formy musí být symetrická.
Teorém 52. Sylvesterův zákon setrvačnosti kvadratických forem Nechť V je vektorový prostor nad R konečné dimenze a g: V → R je kvadratická forma. Potom existuje báze X prostoru V taková, že matice B této formy je diagonální a prvky na diagonále splňují bi i ∈ { − 1, 0, 1}. Navíc počet kladných prvků a počet záporných prvků nezávisí na volě X (tudíž je pro všechny vhodné X stejný) Poznámka 53. vektoru (#1, #0, # − 1) se říká signatura formy. Příslušná báze je tzv. polární báze. Důkaz. a) existence. Zvolme X0...libovolná báze V vůči ní máme matici B0 ... reálná, symetrická věta o diag. ∃ unitární (ortogonální) R: RTB0R = D <— diagonální.
Herm. matic
D˜ : (D˜ )i i =
√ dii
= D˜ TB D˜ B je dagonální ± 1, 0 matice které určují znaménka
?
D = D˜ TBD˜
T B0 = D˜R −1 B
(D˜R −1)
m atice přecho du o d X0 k hledané X
aby součin byl regulární dodefinuji: D˜ii = 1 pro ai i = 0 b) Důkaz jednoznačnosti
1
značení X = {v1, , vn }, Y = {w1, , wn }, příslušné matice jsou B, B ′ ve tvaru i) #0 v B = #0 v B ′ B = [id]TXY B ′[id]X Y obě regulární pro reg. R platí rank(A) = rank(RA) čili rank(B) = rank(B ′) #0 v B = n − rank(B) = n − rank(B ′) = #0 v B ′
0 -1 -1
0
0
ii) sporem #1 v B #1 v B ′ ( x21 + x22 + + x2r − x2r+1 − − x2n ′ pro [u]x = (x1, , xn)T & n ′ = rank(B) g(u) = 2 − − yn2 ′ pro [u] y = (y1, , yn)T &n ′ = rank(B) y12 + y22 + + ys2 − ys+1 búno r > s potom lze vzít z ∈ Z(v1, v2, , vr) ∩ Z(ws+1, , wn) z 0 g(z) > 0 protože některá z prnvích r složek [z]x je nenulová & poslední n − r složek jsou nulové. ≤ 0 protože některá z prnvích r složek [z] y je nenulová & poslední s − r složek jsou nulové.
18
Sekce 10
spor s r > s ⇒ r = s
10 060425 10.1 Lineární programování Literature: skripta Tůma-Matoušek J.Rohr:Lineární algebra a optimalizace (karolinum 2004) L. Grygarová: Úvod do lineárního programování (SPN 1975) J. Dupačová: Lineární programování (SPN 1982) 10.1.1 Úloha LP - optimalizovat hodnotu lineární účelové funkce přes množinu vymezenou lineárními podmínkami Lineární účelová funkce o proměnných x1, , xn
c1x1 + c2x2 + + cnxn omezující podmínky
max min
a1 1x1 + a1 2x2 + + a1 nxn ≤ b1 a2 1x1 + a2 2x2 + + a2 nxn ≤ b2
nerovnost může být i ≥ nebo = Definice 54. Úloha LP zní: Nalezněte vektor x ∈ Rn jež maximalizuje účelovou funkci ctx za podmínek Ax ≤ b (provnávání vektorů je po složkách x ≤ y ∀ixi ≤ yi) kde c ∈ Rn, b ∈ Rm, A ∈ Rm×n Každý vektor, který splňuje Ax ≤ b se nazývá přípustné řešení. Optimální řešení úlohy LP je libovolné přípustné řešení x ∗ pro nějž platí, že každé jiné přípustné řešení x splňuje cTx ≤ cTx∗. Geometrická interpretace prostor všech řešení ... Rn (podmínka nezápornosti ⇒ nezáporný ortant) 1 podmínka ... podprostor vymezený nadrovinou všechny podmínky ... průnik těchto podprostorů ... t.j. mnohostěn přípustných řešení účelová funkce ... udává gradient. t.j. směr ve kterém se mění hodnota účelové funkce optimum ... takový bod x∗, že celý mnohostěn přípustných řešení leží “pod” nadrovinou T c x = z, kde z = cTx∗ (tzn. leží v poloprostoru cTx ≤ z) 1. x1 ≥ 0 2. x2 ≥ 0
3. x1 − x2 ≤ 2
4. − x1 + x2 ≤ 1
5. 2x1 + x2 ≤ 7 max x1 + 2x2
k oboru hodnot ... proč jen R C, ZP nelze ... nejsou uspořádané Q (stejně jako R)
19
060509
šlo by Z ... přísloušné úlohy jsou tzv. celočíselné programovíní ILP
1 2
Rozdíl mezi LP (lze v polinomiálním čase) a ILP (je NP těžký) geometricky Zn jsou mřížové body v Rn a zaokrouhlování nemusí pomoci 1 1 př: u proměnných x1, , xn max x1 + x2 + + xn LP: ∀ixi ∈ h0, 1i ... optimum x∗ = 2 , 2 , ,
T
n
tzn cTx = 2 za podmínky ∀i j : xi + x j ≤ 1 cT x = 1
ILP: ∀ixi ∈ {0, 1} ... optimum x∗ = 1, 0, 0, , 0)T tzn
Pomocí ILP lze spočítat velikost max nezávislé množiny v grafu (což je NP těžká) Převod na ILP: vrchol ni → xi ∈ {0, 1} 0....nepatří do nez. 1...patří max x1 + x2 + + xn (ui , u j ) ∈ E ϕ: xi + x j ≤ 1 nez. množina: vrcholy, které nejsou spojeny hranou x1 + x2 ≤ 1 x2 + x3 ≤ 1 optimum(1, 0, 1) Různé tvary uloh LP: (neboli jak dostat tvar max cTx, Ax ≤ b) min -> max ≥→≤ =→≤ ≤ → = & nezápornost
min cTx ⇔ max − cTx ai 1x1 + ai2x2 + + ainxn ≥ bi ⇔ − ai1x1 − ai2x2 − − ainxn ≤ − bi “=⇔≤&≥” ai 1x1 + ai2x2 + + ainxn ≤ bi ⇔ ai1x1 + + ai nxn + xn+1 = bi & xn+1 ≥ 0
neom. → nezáp. prom. xi ∈ R
substituce ′ xi − xi′′
xi′ , xi′′ ≥ 0
Dcv: ?nezáporné prom → nekladné prom? Jaké mohou být výsledky úloh LP? a) Úloha nemá optimum, protože neexistuje žádné přípustné řešení. b) Úloha nemá optimum, protože úč. funkce není omezena na mnohostěn příp. řešení Pozn: neomezenost mnohostěnu neznamená vždy nemonezenost účelové funkce c) Úloha má jednoznačné řešení d) Úloha má ∞ mnoho optimálních řešení (každý bod na úsečce je optimem)
11 060509 11.0.2 Konvexita Definice 55. Množina A ⊆ Rn je konvexní pokud ∀u,v ∈A ∀α∈h0,1iαu+(1−α)v ∈A. Pozorování: Množina přípustných řešení je konvexní. ... plyne z Pozorování: libovolný průnik konvexních množin je konvexní Pozorování: Množina optimálních řešení je konvexní.
20
Sekce 11
Definice 56. Konvexní mnohostěn ... průnik konečně mnoha poloprostorů. Hraniční nadroviny ... hranice poloprostorů které vymezují mnohostěn Př: R2....... Vrchol mnohostěnu P ... průnik n lineárně nezávislých hraničních nadrovin, x ∈ P ...jednoznačné řešení soustavy A x = b kde A je sestavena z rovnic vybraných n hraničních nadrovin Teorém 57. Má-li úloha LP ve tvaru A x ≤ b optimální řešení a matice A má hodnost rovnu # proměnných, potom se optima nabývá v nějakém vrcholu mnohostěnu přípustných řešení. 11.0.3 Simplexová metoda: -postup řešení úlohy LP takový, že se prochází množina vrcholů mnohostěnu přípustných řešení tak, že účelová funkce neklesá. pozn: může trvat i exp. dlouho (klee-mintyho krychle) Motivační příklad: řešte úlohu LP: max x1 + 2x2 za podmínek: x1 − x2 ≤ 2, − x1 + x2 ≤ 1, 2x1 + x2 ≤ 7, x1, x2 ≥ 0 Výchozí tvar pro simplexovou metodu je Ax = b x ≥ 0 x1 − x2 + x3 = 2 − x1 + x2 + x4 = 1 2x1 + x2 + x5 = 7 výchozí pozice ... zvolím hodnoty 2 volných proměnných tak, aby zbylé byly nezáporné. nabízí se x1, x2 = 0, vyjádřím bázické proměnné pomocí volných. -> x3 = − x1 + x2 + 2 x4 = x1 − x2 + 1 x5 z
x1 ≤ 2 x1 neomezuje 7 = − 2x1 − x2 + 7 x1 ≤ 2 = x1 + 2x2
-snažím se ho maximalizovat
vybereme jednu z proměnných na které úč. fce závisí v přímé úměrnostni s kladným koeficientem a určím, která ze stávajícíh rovnic nejvíce omezuje hodnotu této proměnné z podmínky, která nejvíce omezuje x1 vyjádřím x1 pomocí x3 a dosadím -> x1 = − x3 + x2 + 2 x4 = − x3 + 3 x5 = 2x3 − 3x2 + 3 z = − x3 + 3x2 + 2 Výchozí tvar pro simplexovou metodu: max cTx za podmínek Ax = b, x ≥ 0 kde A je matice řádu m × n m ≤ n a rank(A) = m Pozorování:
21
060509
pokud n − m proměnným přiřadíme hodnotu 0 a sloupce odpovídající zbylým proměnným jsou LN (n − m ... volné prom., m ... bázické), potom jsou hodnoty zbylých m proměnných určené jednoznačně. Definice 58. Nechť max cTx, A x = b, x ≥ 0 je úloha LP, kde A ∈ Rm×n, b ∈ Rm, c ∈ Rn a rank(A) = m. Nechť dále B ⊆ {1, 2, , n} je množina indexů velikosti |B | = m taková, že matice AB sestává ze sloupců matice A určených indexy z množiny B je regulární. Jestliže existuje přípustné řešení x takové, že xi = 0 pro ∀i B tak potom x se nazývá bázické přípustné řešení určené bází indexů B. A → AB B ⊆ {1, , n} xB .(x1, x3, x5) chcem e ≥ 0 xN .(x2, x4) = 0 B = {1, 3, 5}
B = {3, 4, 5} XB = (2, 1, 7)T ≥ 0
(x3, x4, x5)
XN = (0, 0)T = 0
(x1, x2)
→ x = (0, 0, 2, 1, 7) bázické přípustné řešení pro B = {3, 4, 5} B = {1, 3, 4} x2 = 0 x5 = 0 => x3 < 0 ... příslušné x1, , x5 není přípustné řešení => B není přípustná báze Pozorování I různé báze mohou dát stejné bázické přípustné řešení Příklad 59. x1 + x3 = 1 x2 + x4 = 1 x1 + x2 + x5 = 2 B = {1, 2, 3} B ′ = {1, 2, 4} -> dávají stejné bázické přípustné řešení x = (1, 1, 0, 0, 0)T úloha Ax = b x ≥ 0 odvozenou z A ′ x ′ ≤ b m podmínek ... n proměnných ... n ′ proměnných (t.j. n = n ′ + m) ? když zvolím n − m volných složek ve vektoru x? BÚNO zvolím jen pomocné proměnné AB je regulární....*1 x je přípustné......*2 x je přípustné bázické řešení v původní úloze si zvolím n − m hraničních nadrovim & hledám jejich průnik *1....průnik je jednoznačný *2....průnik je v mnohostěnu
22
Sekce 12
x ′ je vrcholem mnohostěnu přípustných řešení. Lemma 60. Báze B určuje bázické přípustné řešení −1 ⇔ AB b≥0 Důkaz. x je řešení ... Ax = b
⇔
−1 −1 AB Ax = AB b −1 AB AB = In
−1 −1 xB = InxB = AB AB xB = AB b≥0
xN = 0 tzn. vektor −1 AB b určuje bázické složky býzického příp. řešení určeného bází B a ty musí být nezáporné.
12 060516 Definice 61. Pro úlohu LP a přípustnou bázi B definujeme simplexovou tabulku následovně: B A b , kde matice podmínek A|b je upravena elementárními úpravami tak, aby AB = I ct − z a navíc aby řádek cT | − z byl upraven tak, aby cB = 0 (t. j. ci = 0 pro ∀i∈B) Příklad 1. B = {3, 4, 5} AB = I 3 1 -1 1 0 0 2 4 -1 1 0 1 0 1 5 2 1 0 0 1 7 b3 0 1 2 0 0 0 cT B
Značení: řádky simplexové tabulky budeme indexovat prvky báze B ?kolik je hodnota účelové funkce za f (x) = cTx dáme na začátku do simplexové tabulky řádek cT |0 ⇔ cTx = f (x) = 0 co se stane, když elementární úpravou získáme cT | − z ⇔ cTx = f (x) − z = 0 ⇔ f (x) = z cB = 0...tak počítáme s.t. xN = 0...to je volba báz. příp. řešení }—–>cTx = 0 Simplexový algoritmus 0. Nalezni nějaké bázické přípustné řešení a sestav simplexovou tabulku. opakuj: 1. Jestliže c j ≤ 0 pro ∀ j B potom STOP...bázické řešení je optimální, jinak zvol j B: c j > 0
2. Jestliže akj ≤ 0 pro k ∈ B potom STOP...účelová fce je neomezená b b jinak zvol i ∈ B: a i = min { a k , kde akj > 0,k ∈ B} ij
kj
3. Polož B 4 B ∪ {j }\{i} a uprav simplexovou tabulku vzhledem k nové bázi.
Příklad 62. 3 1 -1 1 0 0 4 -1 1 0 1 0 5 2 1 0 0 1 1 2 0 0 0
2 1 7 0
23
060516
1 4 5
1 0 0 0
-1 0 3 3
1 1 -2 -1
0 1 0 0
0 0 1 0
2 3 3 -2
Pozorování elementární úpravy nemění prostor řešení t.j. simplexová tabulka popisuje stále stejnou úlohu LP Lemma 63. 3. krok je korektní, neboli nová báze je opět přípustná. B půl báze B ′ nová báze podobně A, A ′ , b, b ′ b stačí ukázat b ′ ≥ 0: pro i: bi ≥ 0&ai j > 0 ⇒ bi′ = a i ≥ 0 pro k ∈ B , b
ij
b i: bk′ = bk − akj a i ij
≥ 0 protože
bk ak j
b
≥ a i volbou i. ij
Lemma 64. 2.krok jee korektní, neboli úloha LP je neomezená jakmile c j > 0 a akj ≤ 0 pro ∀k∈B Důkaz. nechť xje bázické příp. řešení k akt. bázi yj = 1
zvol y: yk = − ak j pro k ∈ B yl = 0 jinak
?
1. y ≥ 0 ⇒ x + ty ≥ 0 pro t ≥ 0 2. A(x + ty) = Ax + t
(A y)
= b + t0 = b
0 volb ou y . na kterém řádku dostaneme −ak j 1+1 ak j =0
x + ty je příp. řešení
3. f (x + ty) = z + cTx + tcTy = z + tc j → ∞ =0
+→∞
Lemma 65. 1. krok je korektní, neboli jakmile c ≤ 0 tak potom příslušné bázické řešení je optimální. Důkaz. Pro všechna x ≥ 0 musí platit cTx ≤ 0 f (x) = z + cTx ≤ z = f (x ∗ )
Dokončení: 0. krok lze vyřešit simplexovou metodou na pomocnou úlohu. Původní úloha: max cTx: Ax = b, x ≥ 0 P búno b ≥ 0 jinak vynásobíme přísl. řádek − 1 pomocná úloha min yi: Ax + Iy = b, x, y ≥0 pokud opt = 0 ⇒ y = 0& přípustná báze vybírá jen indexy vektoru x opt > 0 ⇒ ∃ žádné příp. řešení x. Poznámka 66. ∃ různá pravidle jak vybrat nejlepší i a j např. tzv. Blandovo pravidlo (nejmenší možné i& j)... ukazuje konečnost simpl. metody Dualita lineárního programování x1 − x2 ≤ 2 příklad LP(P) max x1 + 2x2: − x1 + x2 ≤ 1 ; x1, x2 ≥ 0 2x1 + x2 ≤ 7 ?lze nějak odhadnout hodnotu účelové funkce? 2x1 + x2 ≤ 7 ⇔ ≤ 4x1 + 2x2 ≤ 14 f (x) = x1 + 2x2 ≤
24
Sekce 12
lépe: 2. a 3. nerovnost dohromady f (x) = x1 + 2x2 ≤ − x1 + x2 + 2x1 + x2 ≤ 1 + + 7 = 8 Obecně: pro úlohu LP max c1x1 + + cnxn
a11 x1 + + a1 nxn
≤ b1
am1x1 + + am nxn ≤ bm
y1 ym
takové, aby c j ≤ a1 jy1 + + am jym pro ∀ j =1, ,n a navíc aby y1b1 + + ymbm bylo co nejmenší protože pro libovolné přípustné x získáme odhad: ! ! m n m n m n X X X X X X T biyi = bTy e x= aijx j yi ≤ c jx j ≤ aijyi x j = j =1
j =1
i=1
i=1
j=1
i=1
Definice 67. Pro úlohu LP: max cTx, A x ≤ b, x ≥ 0, tzv. primární úlohu (p) definujeme tzv. duální úlohu jako min bTy: ATy ≥ c, y ≥ 0. Příklad 68. k (p) dostáváme (d) min 2 y1 + y2 + 7 + y3: y1 − y2 + 2y3 ≥ 1 − y1 + y2 + y3 ≥ 2 y1, y2, y3 ≥ 0 x∗ = (2, 3)T y ∗ = (0, 1, 1)T cTx∗ = bTy∗ = 8 Teorém 69. Nechť (P) a (D) jsou vzájemě duální úlohy LP potom platí BUĎ obě mají přípustná řešení a potom platní cTx∗ = bTy ∗ pro optima x∗ , y ∗. NEBO jedna z úloh nemá příp. řešení a druhá je pak neomezená nebo také nepřípustná. Bez Důkazu
