Lineární algebra a geometrie – ZS Základní informace Doc. RNDr. Jiří Tůma, DrSc., Katedra algebry http://www.karlin.mff.cuni.cz/~tuma/ akademický rok 2011/2012, zimní semestr
Základní informace .......................................................................................................................................................................... 1 Přednáška 1 _ 4. 10. 2011 ................................................................................................................................................................. 2 Různé formulace: Z předpokladu P plyne závěr Q................................................................................................................. 2 Častá forma matematických tvrzení .......................................................................................................................................... 2 Význam spojek a, nebo ................................................................................................................................................................ 2 Přednáška 2 _ 5. 10. 2011 ................................................................................................................................................................. 3 Kvantifikátory............................................................................................................................................................................... 3 Princip vyloučeného třetího ....................................................................................................................................................... 3 Negace složeného výroku ........................................................................................................................................................... 3 Důkaz nepřímý ............................................................................................................................................................................. 3 Důkaz sporem .............................................................................................................................................................................. 3 Přednáška 3 _ 11. 10. 2011 ............................................................................................................................................................... 4 Incidenční matice grafu ............................................................................................................................................................... 4 Kap1: Matice soustavy, rozšířená matice soustavy ................................................................................................................. 4 Definice 1.1 .................................................................................................................................................................................... 4 Definice 1.2 .................................................................................................................................................................................... 4 Tvrzení 1.1 ..................................................................................................................................................................................... 5 Definice 1.3 .................................................................................................................................................................................... 5 Důkaz 1.1 ....................................................................................................................................................................................... 5 Tvrzení 1.2 ..................................................................................................................................................................................... 5 Důkaz 1.2 ....................................................................................................................................................................................... 5 Definice 1.4 .................................................................................................................................................................................... 5 Tvrzení 1.3 ..................................................................................................................................................................................... 5 Důkaz 1.3 ....................................................................................................................................................................................... 5 Definice 1.5 .................................................................................................................................................................................... 5 Tvrzení 1.4 ..................................................................................................................................................................................... 6 Přednáška 4 _ 12. 10. 2011 ............................................................................................................................................................... 7 Důkaz 1.4 ....................................................................................................................................................................................... 7 Definice 1.6 .................................................................................................................................................................................... 8 Tvrzení 1.5 (Jednoznačnost inverzní matice) ........................................................................................................................... 8 Důkaz 1.5 ....................................................................................................................................................................................... 8 Přednáška 5 _ 18. 10. 2011 ............................................................................................................................................................... 9 Tvrzení 1.6 ..................................................................................................................................................................................... 9 Důkaz 1.6 ....................................................................................................................................................................................... 9 Definice 1.7 .................................................................................................................................................................................... 9 Definice 1.8 .................................................................................................................................................................................... 9 Věta 1.7 .......................................................................................................................................................................................... 9 Důkaz 1.7.1 .................................................................................................................................................................................. 10 Řešení soustav lineárních rovnic.............................................................................................................................................. 10 Definice 1.9 .................................................................................................................................................................................. 10 Maticový zápis............................................................................................................................................................................ 10 Definice 1.10 ................................................................................................................................................................................ 10
Rozklad matic do bloků ............................................................................................................................................................ 10 Definice 1. 11 ............................................................................................................................................................................... 11 Tvrzení 1. 8 .................................................................................................................................................................................. 11 Kap2: Řešení soustav lineárních rovnic .................................................................................................................................. 11 Definice 2.1 .................................................................................................................................................................................. 11 Přednáška 6 _ 19. 10. 2011 ............................................................................................................................................................. 12 Algoritmus 2.1 (pro zpětnou substituci) ................................................................................................................................. 12 Algoritmus 2.1 (pro přímou substituci) .................................................................................................................................. 12 Příklady elementárních úprav .................................................................................................................................................. 12 Tvrzení 2.1 ................................................................................................................................................................................... 12 Důkaz 2.1 ..................................................................................................................................................................................... 12 Definice 2.2 Elementární řádkové úpravy (EŘÚ) .................................................................................................................. 12 Tvrzení 2.2 ................................................................................................................................................................................... 13 Řádkově odstupňovaný tvar .................................................................................................................................................... 13 Definice 2.4 .................................................................................................................................................................................. 13 Algoritmus 2.3 (Gaussova eliminace – GE) ............................................................................................................................ 13 Věta 2.3 ........................................................................................................................................................................................ 13 Důkaz 2.3 ..................................................................................................................................................................................... 13 Věta 2.4 ........................................................................................................................................................................................ 14 Důkaz 2.4 ..................................................................................................................................................................................... 14 Přednáška 7 _ 25. 10. 2011 ............................................................................................................................................................. 15 Důkaz 2.4 (pokračování) ........................................................................................................................................................... 15 Algoritmus 2.4 ............................................................................................................................................................................. 15 Problémy s řešením na počítači................................................................................................................................................ 15 Tvrzení 2.5 ................................................................................................................................................................................... 15 Důkaz 2.5 ..................................................................................................................................................................................... 15 Důsledek 2.6 ................................................................................................................................................................................ 16 Důkaz 2.6 ..................................................................................................................................................................................... 16 Věta 2.7 ........................................................................................................................................................................................ 16 Důkaz 2.7 ..................................................................................................................................................................................... 16 Algoritmus 2.5 Pro výpočet inverzní matice k matici A ....................................................................................................... 17 Přednáška 8 _ 1. 11. 2011 ........................................................................................................................................................... 18 Tvrzení 2.8 ................................................................................................................................................................................... 18 Důkaz 2.8 ..................................................................................................................................................................................... 18 Tvrzení 2.9 ................................................................................................................................................................................... 18 Důkaz 2.9 ..................................................................................................................................................................................... 18 Příklad 2.1 (Výpočet proudu v el. obvodu) ............................................................................................................................ 18 Lemma 2.10 ................................................................................................................................................................................. 18 Důkaz 2.10 ................................................................................................................................................................................... 19 Věta 2.11 ...................................................................................................................................................................................... 19 Postup řešení pomocí LU-rozkladu ......................................................................................................................................... 19 Důkaz 2.11 ................................................................................................................................................................................... 20 Konstruktivní důkaz existence LU–rozkladu ........................................................................................................................ 20 Přednáška 9 _ 2. 11. 2011 ............................................................................................................................................................... 21 Algoritmus 2.6 ............................................................................................................................................................................ 21 Definice 2.5 (LU–rozklad matice A) ........................................................................................................................................ 21 Definice 2.6 .................................................................................................................................................................................. 21 Věta 2.12 ...................................................................................................................................................................................... 22 Důkaz 2.12 ................................................................................................................................................................................... 22 Příklad 2.2 Počty operací ........................................................................................................................................................... 22 Kap3: Tělesa ................................................................................................................................................................................ 22
Definice 3.1 .................................................................................................................................................................................. 22 Tvrzení 3.1 ................................................................................................................................................................................... 22 Příklady těles .............................................................................................................................................................................. 23 Přednáška 10 _ 8. 11. 2011 ............................................................................................................................................................. 24 Definice 3.2 .................................................................................................................................................................................. 24 Věta 3.2 ........................................................................................................................................................................................ 24 Důkaz 3.2 ..................................................................................................................................................................................... 24 Kap4: Aritmetické vektorové prostory.................................................................................................................................... 24 Definice 4.1 .................................................................................................................................................................................. 24 Definice 4.2 .................................................................................................................................................................................. 24 Operace s vektory dimenze n ................................................................................................................................................... 24 Definice 4.3 .................................................................................................................................................................................. 24 Definice 4.4 .................................................................................................................................................................................. 24 Tvrzení 4.1 ................................................................................................................................................................................... 24 Důkaz 4.1 ..................................................................................................................................................................................... 24 Tvrzení 4.2 ................................................................................................................................................................................... 25 Důkaz 4.2 ..................................................................................................................................................................................... 25 Definice 4.5 .................................................................................................................................................................................. 25 Tvrzení 4.3 ................................................................................................................................................................................... 25 Důkaz 4.3 ..................................................................................................................................................................................... 25 Definice 4.6 .................................................................................................................................................................................. 25 Definice 4.7 .................................................................................................................................................................................. 25 Tvrzení 4.4 ................................................................................................................................................................................... 25 Důkaz 4.4 ..................................................................................................................................................................................... 26 Tvrzení 4.5 ................................................................................................................................................................................... 26 Důkaz 4.5 ..................................................................................................................................................................................... 26 Přednáška 11 _ 9. 11. 2011 ............................................................................................................................................................. 27 Definice 4.8 .................................................................................................................................................................................. 27 Tvrzení 4.6 ................................................................................................................................................................................... 27 Důkaz 4.6 ..................................................................................................................................................................................... 27 Definice 4.9 .................................................................................................................................................................................. 27 Tvrzení 4.7 ................................................................................................................................................................................... 28 Důkaz 4.7 ..................................................................................................................................................................................... 28 Věta 4.8 (Steinitzova věta o výměně – SVoV)......................................................................................................................... 28 Důkaz 4.8 ..................................................................................................................................................................................... 28 Definice 4.10 ................................................................................................................................................................................ 28 Příklad 4.1 ................................................................................................................................................................................... 28 Věta 4.9 ........................................................................................................................................................................................ 29 Důkaz 4.9 ..................................................................................................................................................................................... 29 Přednáška 12 _ 15. 11. 2011 ........................................................................................................................................................... 30 Tvrzení 4.10 ................................................................................................................................................................................. 30 Důkaz 4.10 ................................................................................................................................................................................... 30 Věta 4.11 ...................................................................................................................................................................................... 31 Důkaz 4.11 ................................................................................................................................................................................... 31 Definice 4.11 ................................................................................................................................................................................ 31 Tvrzení 4.12 ................................................................................................................................................................................. 31 Důkaz 4.12 ................................................................................................................................................................................... 31 Věta 4.13 (O dimenzi průniku a součtu podprostorů) .......................................................................................................... 31 Důkaz 4.13 ................................................................................................................................................................................... 31 Tvrzení 4.14 ................................................................................................................................................................................. 32 Důkaz 4.14 ................................................................................................................................................................................... 32
Přednáška 13 _ 16. 11. 2011 ........................................................................................................................................................... 33 Příklad 4.2 (Vzorec pro n-tý člen Fibonacciovy posl.) ........................................................................................................... 33 Tvrzení 4.15 ................................................................................................................................................................................. 34 Důkaz 4.15 ................................................................................................................................................................................... 34 Definice 4.12 ................................................................................................................................................................................ 34 Definice 4.13 ................................................................................................................................................................................ 34 Tvrzení 4.16 ................................................................................................................................................................................. 34 Důkaz 4.16 ................................................................................................................................................................................... 34 Věta 4.17 ...................................................................................................................................................................................... 34 Důkaz 4.17 ................................................................................................................................................................................... 34 Definice 4.14 ................................................................................................................................................................................ 35 Důsledek 4.18 (Věty 4.17) .......................................................................................................................................................... 35 Přednáška 14 _ 22. 11. 2011 ........................................................................................................................................................... 36 Věta 4.19 ...................................................................................................................................................................................... 36 Důkaz 4.19 ................................................................................................................................................................................... 36 Tvrzení 4.20 ................................................................................................................................................................................. 36 Důkaz 4.20 ................................................................................................................................................................................... 36 Příklad 4.3 ................................................................................................................................................................................... 36 Tvrzení 4.2.1 ................................................................................................................................................................................ 37 Důkaz 4.21 ................................................................................................................................................................................... 37 Věta 4.22 ...................................................................................................................................................................................... 37 Důkaz 4.22 ................................................................................................................................................................................... 37 Věta 4.23 ...................................................................................................................................................................................... 38 Důkaz 4.23 ................................................................................................................................................................................... 38 Věta 4.24 (Frobeniova věta) ...................................................................................................................................................... 38 Důkaz 4.23 ................................................................................................................................................................................... 38 Kap5: Permutace ........................................................................................................................................................................ 38 Definice 5.1 .................................................................................................................................................................................. 38 Lemma 5.1 ................................................................................................................................................................................... 38 Přednáška 15 _ 23. 11. 2011 ........................................................................................................................................................... 39 Příklady zápisu permutací ........................................................................................................................................................ 39 Skládání permutací .................................................................................................................................................................... 39 Definice 5.2 .................................................................................................................................................................................. 39 Lemma 5.2 ................................................................................................................................................................................... 39 Důkaz 5.2 ..................................................................................................................................................................................... 39 Lemma 5.3 ................................................................................................................................................................................... 39 Důkaz 5.3 ..................................................................................................................................................................................... 40 Lemma 5.4 ................................................................................................................................................................................... 40 Důkaz 5.4 ..................................................................................................................................................................................... 40 Definice 5.3 .................................................................................................................................................................................. 40 Tvrzení 5.5 ................................................................................................................................................................................... 40 Důkaz 5.5 ..................................................................................................................................................................................... 40 Lemma 5.6 ................................................................................................................................................................................... 41 Důkaz 5.6 ..................................................................................................................................................................................... 41 Přednáška 16 _ 29. 11. 2011 ........................................................................................................................................................... 42 Kap6: Determinanty ................................................................................................................................................................... 42 Definice 6.1 .................................................................................................................................................................................. 42 Příklad 6.1 ................................................................................................................................................................................... 42 Lemma 6.1 ................................................................................................................................................................................... 42 Důkaz 6.1 ..................................................................................................................................................................................... 42 Příklad 6.2 (Geometrický význam determinantu matic 2. a 3. řádu) .................................................................................. 43
Tvrzení 6.2 ................................................................................................................................................................................... 44 Důkaz 6.2 ..................................................................................................................................................................................... 44 Tvrzení 6.3 ................................................................................................................................................................................... 44 Důkaz 6.3 ..................................................................................................................................................................................... 45 Přednáška 17 _ 30. 11. 2011 ........................................................................................................................................................... 46 Věta 6.4 ........................................................................................................................................................................................ 46 Důkaz 6.4 ..................................................................................................................................................................................... 46 Důsledek 6.5 ................................................................................................................................................................................ 46 Důkaz 6.5 ..................................................................................................................................................................................... 46 Věta 6.6 ........................................................................................................................................................................................ 47 Důkaz 6.6 ..................................................................................................................................................................................... 47 Věta 6.7 (O součinu determinantů) .......................................................................................................................................... 47 Důkaz 6.7 ..................................................................................................................................................................................... 47 Definice 6.2 .................................................................................................................................................................................. 47 Věta 6.8 (O rozvoji determinantu) ........................................................................................................................................... 47 Důkaz 6.8 ..................................................................................................................................................................................... 47 Úloha 6.1 ...................................................................................................................................................................................... 48 Úloha 6.2 ...................................................................................................................................................................................... 50 Příklad 6.3 (Shamirovo schéma pro sdílení tajemství) .......................................................................................................... 50 Přednáška 18 _ 6. 12. 2011 ............................................................................................................................................................. 51 Tvrzení 6.9 ................................................................................................................................................................................... 51 Důkaz 6.9 ..................................................................................................................................................................................... 51 Tvrzení 6.10 (Cramerovo pravidlo) ......................................................................................................................................... 51 Důkaz 6. 10 .................................................................................................................................................................................. 52 Kap7: Skalární součin ................................................................................................................................................................ 52 Definice 7.1 .................................................................................................................................................................................. 52 Definice 7.2 .................................................................................................................................................................................. 52 Tvrzení 7.1 ................................................................................................................................................................................... 52 Důkaz 7.1 ..................................................................................................................................................................................... 52 Úloha 7.1 ...................................................................................................................................................................................... 53 Přednáška 19_7. 12. 2011 ............................................................................................................................................................... 54 Definice 7.3 .................................................................................................................................................................................. 54 Úloha 7.2 ...................................................................................................................................................................................... 54 Věta 7.2 (Cauchy–Schwartzova–Bunjakovského nerovnost) ............................................................................................... 54 Důkaz 7.2 ..................................................................................................................................................................................... 54 Tvrzení 7.3 (Trojúhelníková nerovnost) .................................................................................................................................. 54 Důkaz 7.3 ..................................................................................................................................................................................... 54 Příklad 7.1 (Geometrický význam SSS v ℝn) .......................................................................................................................... 55 Definice 7.4 .................................................................................................................................................................................. 55 Definice 7.5 .................................................................................................................................................................................. 55 Tvrzení 7.4 ................................................................................................................................................................................... 55 Důkaz 7.4 ..................................................................................................................................................................................... 55 Definice 7.6 .................................................................................................................................................................................. 55 Tvrzení 7.5 ................................................................................................................................................................................... 55 Důkaz 7.5 ..................................................................................................................................................................................... 55 Definice 7.7 .................................................................................................................................................................................. 55 Tvrzení 7.6 ................................................................................................................................................................................... 56 Důkaz 7.6 ..................................................................................................................................................................................... 56 Tvrzení 7.7 (Pythagorova věta) ................................................................................................................................................ 56 Důkaz 7.7 ..................................................................................................................................................................................... 56 Kap8: Gramova–Schmidtova ortogonalizace ......................................................................................................................... 56
Důkaz 8.1 ..................................................................................................................................................................................... 56 Přednáška 20 _ 13. 12. 2011 ........................................................................................................................................................... 57 Algoritmus 8.1 (Klasický GS–algoritmus) .............................................................................................................................. 57 Věta 8.1 ........................................................................................................................................................................................ 57 Důkaz 8.2 ..................................................................................................................................................................................... 57 Věta 8.2 ........................................................................................................................................................................................ 58 Definice 8.1 .................................................................................................................................................................................. 58 Algoritmus 8.2 (Modifikovaný GS-algoritmus) ..................................................................................................................... 59 Tvrzení 8.3 ................................................................................................................................................................................... 59 Přednáška 21 _ 14. 12. 2011 ........................................................................................................................................................... 60 Kap9: Unitární a ortogonální matice ....................................................................................................................................... 60 Definice 9.1 .................................................................................................................................................................................. 60 Věta 9.1 ........................................................................................................................................................................................ 60 Důkaz 9.1 ..................................................................................................................................................................................... 60 Důsledek 9.2 ................................................................................................................................................................................ 61 Důkaz 9.2 ..................................................................................................................................................................................... 61 Věta 9.3 ........................................................................................................................................................................................ 61 Důkaz 9.3 ..................................................................................................................................................................................... 61 Definice 9.2 .................................................................................................................................................................................. 61 Přednáška 22 _ 20. 12. 2011 ........................................................................................................................................................... 62 Tvrzení 9.4 ................................................................................................................................................................................... 62 Důkaz 9.4 ..................................................................................................................................................................................... 62 Definice 9.3 .................................................................................................................................................................................. 63 Tvrzení 9.5 ................................................................................................................................................................................... 63 Důkaz 9.5 ..................................................................................................................................................................................... 63 Definice 9.4 .................................................................................................................................................................................. 63 Tvrzení 9.6 ................................................................................................................................................................................... 63 Důkaz 9.6 ..................................................................................................................................................................................... 63 Příklad 9.1 (elementární rotátory) ............................................................................................................................................ 64 Definice 9.5 .................................................................................................................................................................................. 64 Tvrzení 9.7 ................................................................................................................................................................................... 64 Důkaz 9.7 ..................................................................................................................................................................................... 64 Přednáška 23 _ 21. 12. 2011 ........................................................................................................................................................... 65 Tvrzení 9.8 ................................................................................................................................................................................... 65 Důkaz 9.8 ..................................................................................................................................................................................... 65 Tvrzení 9.9 ................................................................................................................................................................................... 65 Důkaz 9.9 ..................................................................................................................................................................................... 65 Věta 9.10 (Ortogonální redukce) .............................................................................................................................................. 65 Důkaz 9.10 ................................................................................................................................................................................... 66 Definice 9.6 .................................................................................................................................................................................. 66 Tvrzení 9.11 ................................................................................................................................................................................. 66 Důkaz 9.11 ................................................................................................................................................................................... 66 Přednáška 24 _ 3. 1. 2012 ............................................................................................................................................................... 67 Kap10: Ortogonální projekce a metoda nejmenších čtverců ................................................................................................ 67 Tvrzení 10.1 ................................................................................................................................................................................. 67 Důkaz 10. 1 .................................................................................................................................................................................. 67 Tvrzení 10. 2 ................................................................................................................................................................................ 67 Důkaz 10.2 ................................................................................................................................................................................... 68 Definice 10.1 ................................................................................................................................................................................ 68 Příklad 10.1 ................................................................................................................................................................................. 68
Příklad 10.2 ................................................................................................................................................................................. 68 Věta 10.3 (Ortogonální rozklad) ............................................................................................................................................... 68 Důkaz 10.3 ................................................................................................................................................................................... 68 Důsledek 10.4 (Fredholmova alternativa) .............................................................................................................................. 69 Důkaz 10.4 ................................................................................................................................................................................... 69 Tvrzení 10.5 (URV-rozklad) ...................................................................................................................................................... 69 Přednáška 25 _ 4. 1. 2012 ........................................................................................................................................................... 70 Důkaz 10.5 ................................................................................................................................................................................... 70 Definice 10.2 ................................................................................................................................................................................ 70 Tvrzení 10.6 ................................................................................................................................................................................. 70 Důkaz 10.6 ................................................................................................................................................................................... 70 Definice 10.3 ................................................................................................................................................................................ 70 Tvrzení 10.7 ................................................................................................................................................................................. 71 Důkaz 10.7 ................................................................................................................................................................................... 71 Definice 10.4 ................................................................................................................................................................................ 71 Tvrzení 10. 8 ................................................................................................................................................................................ 71 Důkaz 10. 8 .................................................................................................................................................................................. 71 Tvrzení 10.9 ................................................................................................................................................................................. 72 Důkaz 10.9 ................................................................................................................................................................................... 72 Věta 10.10 (Metoda nejmenších čtverců) ................................................................................................................................ 72 Důkaz 10.10 ................................................................................................................................................................................. 72 Kap11: Matice jako lineární zobrazení .................................................................................................................................... 72 Definice 11.1 ................................................................................................................................................................................ 72 Tvrzení 11.1 ................................................................................................................................................................................. 72 Přednáška 26 _ 10. 1. 2012 ............................................................................................................................................................. 73 Příklad 7.1 ................................................................................................................................................................................... 73 Definice 11.2 ................................................................................................................................................................................ 73 Tvrzení 11.2 ................................................................................................................................................................................. 73 Důkaz 11.2 ................................................................................................................................................................................... 73 Tvrzení 11.3 ................................................................................................................................................................................. 73 Důkaz 11.3 ................................................................................................................................................................................... 73 Definice 11.3 ................................................................................................................................................................................ 74 Tvrzení 11.4 ................................................................................................................................................................................. 74 Důkaz 11.4 ................................................................................................................................................................................... 74 Definice 11.4 ................................................................................................................................................................................ 74 Tvrzení 11.5 ................................................................................................................................................................................. 75 Důkaz 11.5 ................................................................................................................................................................................... 75 Tvrzení 11.6 ................................................................................................................................................................................. 75 Důkaz 11.6 ................................................................................................................................................................................... 75 Definice 11.5 ................................................................................................................................................................................ 75 Tvrzení 11.7 ................................................................................................................................................................................. 76 Důkaz 11.7 ................................................................................................................................................................................... 76 Tvrzení 11.8 ................................................................................................................................................................................. 76 Důkaz 11.8 ................................................................................................................................................................................... 76 Tvrzení 11.9 ................................................................................................................................................................................. 76 Důkaz 11.9 ................................................................................................................................................................................... 76 Přednáška 27 _ 11. 1 2012 .............................................................................................................................................................. 77
Přednáška 1 _ 4. 10. 2011 Tvar matematického tvrzení: Z předpokladu P plyne závěr Q. (implikace) Př. Je-li (P:) Tj. Je-li Tj. Je-li
kladné reálné číslo, pak (Q:) existuje právě jedno kladné reálné číslo , pak existuje právě jedno , pro které platí , pak existuje právě jedna druhá odmocnina z .
Definice: Druhou odmocninou z reálného čísla Je-li
(
.
.
rozumíme reáné číslo
takové, že
kladné racionální číslo, pak existuje právě jedno kladné racionální číslo
Protipříklad:
takové, že
. Pozn.: snaha o obecnost
takové, že
.
) Pozn.: pozor na KONTEXT: reálná, racionální…
Existuje právě jedno = existuje alespoň jedno + existuje nejvýše jedno. Pozn.: 2 implikace Věta: Je-li , pak existuje právě jedno , pro které platí Důkaz: Jsou-li kladná reálná čísla, pro která platí, že . Protože platí také, že .
. a
, pak , tedy
, tedy . Proto
, proto , a tedy
Různé formulace: Z předpokladu P plyne závěr Q. 1) Jestliže platí P, pak platí také Q. 2) Z P plyne Q. 3) Platí-li P, pak platí Q. 4) Nechť/Ať platí P, pak platí také Q. 5) P implikuje Q. 6) P je postačující podmínka pro Q. 7) Q je nutná podmínka pro P. 8) Jestliže neplatí Q, pak neplatí ani P. a) Jestliže platí Q, pak platí P. b) Jestliže platí P, pak platí Q. • opačná tvrzení; mohou mít stejnou i různou pravdivostní hodnotu Častá forma matematických tvrzení 1) P platí, právě když platí Q. (ekvivalence) 2) P je ekvivalentní s Q. a. tzn., že P→Q a zároveň Q→P v matematickém tvrzení musí po každém „jestliže“ následovat „pak“ Význam spojek a, nebo Jsou-li P, Q výroky pak 1) P a Q je také výrok (konjunkce) o P a Q platí, právě když platí P a současně platí Q. 2) P nebo Q je také výrok (disjunkce) o P nebo Q platí, jestliže platí alespoň jeden z výroků P, Q.
2
P
Q
Q →P
P→Q
1 1 0 0
1 0 1 0
1 1 0 1
1 0 1 1
Přednáška 2 _ 5. 10. 2011 Definice: Přirozené číslo
se nazývá prvočíslo právě tehdy, když jeho děliteli jsou
Jestliže prvočíslo dělí , pak dělí P: je prvočíslo a (konjunkce) dělí Q: dělí nebo (disjunkce) dělí Pokud z P plyne Q, pak z R plyne S. z P plyne Q = předpoklad z R plyne S = závěr Př.: Najděte všechna řešení soustavy
nebo dělí
skryté logické spojky v rovnicích: Jestliže a splňují tyto rovnice pak… Jeli
a
, pak (
a
) nebo …
Máme-li dokázat, že z předpokladu P nebo P´plyne Q, důkaz se rozpadá na dvě části: 1) důkaz, že z P→Q 2) důkaz, že z P´→Q Máme-li dokázat, že z P plyne Q nebo Q´, pak: 1) důkaz že z P→Q 2) důkaz, že z P→Q´ Kvantifikátory Pro
a .
existuje
takové, že
Princip vyloučeného třetího Jestliže P není pravdivý, pak platí ¬Q. princip důkazu sporem Negace složeného výroku
Důkaz nepřímý Z P plyne Q… Důkaz nepřímý: Z ¬Q plyne ¬P. Důkaz sporem ¬Q je ve sporu s P.
3
.
Přednáška 3 _ 11. 10. 2011 Incidenční matice grafu Bridges of Köningsberg 1 2 3 4
1 0 0 2 1
2 0 0 2 1
3 2 2 0 1
4 1 1 1 0
Kap1: Matice soustavy, rozšířená matice soustavy
matice soustavy
rozšířená matice soustavy
Definice 1.1 Matice typu Matice typu
je soubor čísel uspořádaných do obdélníkové tabulky o se nazývá čtvercová matice řádu .
Označení
řádcích a
sloupích.
,
prvek matice
na místě
lze také značit
.
Matice typu je zobrazení → (komplexní matice) → ℝ (reálná matice) → (racionální matice) → (celočíselná matice) → (binární matice) Matice typu
se nazývají řádkové vektory:
Matice typu
se nazývají sloupcové vektory:
Definice 1.2 Jsou-li
matice téhož typu
, pak definujeme jejich součet
kde Je-li kde
jako matici
,
. matice typu
a
číslo, pak definujeme součin
jako matici
.
4
,
Tvrzení 1.1 Jsou-li matice stejného typu 1) 2) 3) označíme-li matici typu 4)
Pozn.: vlastnosti počítání s čísly:
, pak platí:
1) 2) 3) 4)
, jejíž všechny prvky jsou , pak
+ komutativní + asociativní ex. 0 ex. 1, opačný prvek
Definice 1.3 Dvě matice
se rovnají, pokud jsou stejného typu
a platí
.
Důkaz 1.1 1) máme dokázat • prvek na místě
:
2) máme dokázat • prvek na místě Tvrzení 1.2 Jsou-li matice stejného typu jsou čísla, pak platí: 1) 2) 3) 4) Důkaz 1.2 Vždy porovnáváme prvky na stejných místech v maticích na obou stranách rovnosti. Definice 1.4 Je-li
matice typu
, pak matice transponovaná k
kde
je matice
Pozn.: vlastnosti počítání s čísly: 1) 3)
distributivita * asociativní
,
.
Označení transponované matice:
.
Tvrzení 1.3 Jsou-li matice stejného typu , a je-li číslo, pak platí: 1) 2) Důkaz 1.3 Na obou stranách rovnosti jsou vždy matice téhož typu 1) prvek na místě v matici se rovná prvek na místě
v matici
se rovná součtu prvků na místě
v maticích
a
tj.
.
Definice 1.5 Je-li
matice typu
jako matici
typu
a
matice typu
, pak definujeme jejich součin
(pozor na pořadí!)
, kde
Př.:
Jednotková matice řádu pokud Značení:
je čtvercová matice
řádu
.
pro kterou platí, že
pokud
, Př.:
; Kroneckerův symbol: 5
Tvrzení 1.4 1) Jsou-li
matice typu
,
2) Jsou-li
matice typu
,
3) Jsou-li
matice typu
matice typu
,
pak platí
matice typu
pak platí
matice typu
,
matice typu
5) Jsou-li
matice typu
,
matice typu
matice typu
matice typu
matice typu
4) Jsou-li
6) Je-li
,
,
je číslo pak pak platí
, pak platí
6
, pak platí Důkazy: a) b) c)
ověřit, zda je operace proveditelná (správné typy) porovnat typy matic na obou stranách rovnosti rovnost (prvky na stejných místech)
Přednáška 4 _ 12. 10. 2011 Důkaz 1.4 1) a. b. c.
typu , typu , typu typu , typu typu , typu v matici je prvek na místě roven
v matici
v matici
je prvek na místě
je prvek na místě
v matici
je prvek na místě
roven
roven
roven
– násobení je asociativní k prohození sum: pokud nás zajímá prvek na místě
a sumy jsou pro
2) a. b. c.
je typu , typu i jsou typu je typu je typu , je typu prvek na místě v matici je roven
v matici
v matici
prvek na místě =
v matici
prvek na místě
v matici
3) analogicky jako 2 4)
(pozor
je roven je roven
není definováno!)
7
tak je můžeme prohodit
5) a. b.
c.
je typu , typu je typu je typu je typu , je typu je typu prvek matice na místě
tj. prvek na místě
je roven
v matici
prvek na místě
v matici
prvek na místě
v matici
prvek na místě
v matici
je roven prvku na místě je roven prvku na místě je roven
v matici v matici
tedy tedy
Pozn.: vlastnosti počítání s čísly: * komutativní
6)
prvek na místě
v součinu
je roven
Př. 1.1 (ilustrace) Fibonacciova posloupnost je definována
Značení: čtvercová matice řádu
(rekurentní formule) → lineární rekurentní posloupnost
• celkem –krát
Indukcí lze snadno dokázat, že chceme spočítat prvek
– podle definice to vyžaduje ?? operací
pomocí násobení matic to vyžaduje pouze → pro k dostatečně velké…
–
součinů matic řádu
Definice 1.6 Čtvercová matice řádu se nazývá regulární (invertovatelná), pokud existuje čtvercová matice že V tom případě se nazývá inverzní matice k a označuje se . Čtvercová matice, která není regulární, se nazývá singulární. Tvrzení 1.5 (Jednoznačnost inverzní matice) Inverzní matice k regulární matici je určená jednoznačně. Důkaz 1.5 Nechť je regulární matice řádu a jsou inverzní matice k
8
řádu
taková,
Přednáška 5 _ 18. 10. 2011 Tvrzení 1.6 Je-li a jsou regulární matice řádu , potom 1) je také regulární matice a 2) je regulární matice a 3) je regulární matice a 4) je regulární matice a Důkaz 1.6 1) 2) 3) 4)
→ z definice regulární matice
je regulární a inverzní k
Součet regulárních matic nemusím být regulární!
Definice 1.7 Je-li
, pak: pro každé
nazýváme vektor
i–tý řádkový vektor matice .
Značíme:
pro každé
nazýváme vektor
j–tý sloupcový vektor matice .
Značíme: Definice 1.8 Jsou-li
matice stejného typu
a
čísla, pak sumu (matic)
nazýváme lineární kombinace matic a čísla nazýváme koeficienty lineární kombinace. Jsou-li vektory, pak mluvíme o lineární kombinaci vektorů.
Věta 1.7 Je-li
a
, potom platí
1)
2)
9
Důkaz 1.7.1 Prvek na místě
ve vektoru
Prvek na místě
v
neboť prvek na místě
je roven prvku na místě
v
se rovná
v součinu
, tj.
.
Řešení soustav lineárních rovnic Definice 1.9 Soustavou
kde
lineárních rovnic o
jsou známá čísla a
Matice
neznámých rozumíme soustavu rovnic:
jsou neznámá.
se nazývá maticí soustavy, vektor
a matice
typu
se nazývá vektor pravých stran
se nazývá rozšířená matice soustavy.
Maticový zápis soustavy lineárních rovnic o neznámých a vektor neznámých.
, kde
je matice soustavy,
1)
Definice 1.10 Čtvercovou matici 1) 2) 3) 4)
je vektor pravých stran
nazýváme 2)
symetrická, pokud , tj. kososymetrická, pokud , tj. horní trojúhelníková, platí-li dolní trojúhelníková, pokud platí
3)
5) diagonální, pokud
4)
Rozklad matic do bloků n1
5)
n2
m1 m2
je typu je typu … prvek na místě prvek na místě
v matici v matici
rozklad součinu
určený součty
je roven prvku v matici je roven prvku v matici
na místě na místě
10
platí, že
Definice 1. 11 Je-li
matice typu
pak definujeme rozklad matice jako matici:
do bloků určený součty
… …
…
… …
a prvek na místě Tvrzení 1. 8 Jsou-li matice
typu
,
je prvek na místě
v matici .
typu
1) 2) 3) je rozklad matice
určený součty
je rozklad matice
určený součty
je rozklad matice potom platí, že
určený součty
Kap2: Řešení soustav lineárních rovnic Př. Předpokládáme, že
je horní trojúhelníková matice řádu
a prvky
→zpětná substituce ( spočtu , dosadím do předchozí, spočtu (vs. dolní trojúhelníková matice: přímá substituce) → zp. subst:
(analogicky pro přímou substituci (od
atd.)
))
Definice 2.1 Máme-li a upravíme-li ji do soustavy udělali ekvivalentní úpravu.
tak, že obě soustavy mají stejné množiny řešení, říkáme, že jsme
11
Přednáška 6 _ 19. 10. 2011 Algoritmus 2.1 (pro zpětnou substituci) viz sešit str. 9 Algoritmus 2.1 (pro přímou substituci) viz sešit str. 9 Příklady elementárních úprav 1) prohození 2 rovnic (řádků) 2) vynásobení nějaké rovnice nenulovým činitelem 3) přičtení libovolného násobku nějaké rovnice k jiné rovnici Všechny elementární úpravy jsou vratné, z upravených soustav lze dostat původní soustavu pomocí nějaké jiné elementární úpravy (zpětně). Tvrzení 2.1 Všechny elementární úpravy jsou ekvivalentní. Důkaz 2.1 1) jakékoli řešení původní soustavy je i řešením upravené soustavy 2) je-li řešením původní soustavy, platí odtud plyne: Tedy opět je 3) každé
• •
řešením každé rovnice nové soustavy řešení původní soustavy je řešením
a je také řešením všech ostatních rovnic nové soustavy Tedy každé řešení původní soustavy je řešením upravené soustavy, kterou jsme dostali z původní soustavy nějakou EÚ rovněž každé řešení upravené soustavy je i řešením původní soustavy, protože každá EÚ je vratná
Definice 2.2 Elementární řádkové úpravy (EŘÚ) Elementární řádkové úpravy pro matici
jsou následující:
1) prohození 2 řádků matice 2) vynásobení nějakého řádku matice nenulovým číslem 3) přičtení násobku nějakého řádku k jinému řádku
Všechny řádky původní matice jsou vždy lineární kombinací řádků původní matice; novou matici můžeme dostat tak, že původní matici vynásobíme zleva vhodnou maticí. Je-li typu , pak vhodné matice musí být čtvercové typu Podle Věty 1.7 najdeme vhodné matice: 1 EŘÚ:
.
elementární matice 1. typu
(ve zbývajících případech)
12
2EŘÚ
elementární matice 2. typu
3EŘÚ elementární matice 3. typu
Tvrzení 2.2 Elementární řádkovou úpravu matice
pro
horní trojúhelníková
pro
dolní trojúhelníková
dostaneme tak, že ji vynásobíme zleva příslušnou elementární maticí.
Řádkově odstupňovaný tvar
sloupců s indexy
se říká bázové
Definice 2.4 Matice
je v řádkově odstupňovaném tvaru (ŘOT) pokud
Algoritmus 2.3 (Gaussova eliminace – GE) • převede jakoukoli matici do ŘOT pomocí EŘÚ 1) najde (zleva) 1. nenulový sloupec o (pokud žádný nenajde → a ta je v ŘOT o pokud → označí j1 nejmenší index nenulového sloupce v 2) pokud pak prohodí 1. a i-tý řádek 3) je třeba vynulovat prvky pod o pokud pak
(nenulový člen v prvním řádku) přičteme k i-tému řádku
násobek prvního řádku 4) pak použijeme alg. znovu pro matici
Věta 2.3 Pomocí GE převedeme libovolnou matici
tvořenou řádky
typu
a sloupci
matice
do matice ŘOT.
matice v ŘOT není určena jednoznačně indexy jsou určeny jednoznačně, ale neumíme to dokázat Důkaz 2.3 1) je-li je v ŘOT 2) je-li , předpokládáme, že GE převede do ŘOT libovolnou matici, která má řádků 3) pomocí kroků 1, 2, 3 (Algoritmus 2.3) najdeme , dále použijeme indukční předpoklad. 13
Věta 2.4 Soustava je neřešitelná právě když po převedení rozšířené matice soustavy do ŘOT sloupec pravých stran bázový. Důkaz 2.4 Je-li sloupec pravých stran
bázový, existuje
(poslední nenulový řádek) tak, že
Tj. po elementárních úpravách původní soustavy dostaneme rovnici:
Tato rovnice je nesplnitelná a tedy ani původní soustava není řešitelná.
14
pomocí GE je
Přednáška 7 _ 25. 10. 2011 Důkaz 2.4 (pokračování) Pokud sloupec pravých stran není bázový: Nechť není bázový sloupec. Nechť (počet nenulových sloupců), Zvolme libovolně hodnoty
splňují podmínky z def. ŘOT (→ vystupují jako parametry)
(s původní soustavou) jdeme odspodu:
u této soustavy známe pravé strany je to soustava rovnic o neznámých tyto prvky jsou nenulové (z definice ŘOT): Matice této soustavy je horní trojúhelníková s nenulovými prvky na hlavní diagonále – tato soustava má jednoznačné řešení, které získáme pomocí zpětné substituce. Algoritmus 2.4 Obecná zpětná substituce pro soustavu , kde je v ŘOT z definice ŘOT je-li , pak je bázový sloupec → soustava je neřešitelná pokud zvolíme libovolné hodnoty zbylé neznámé dopočteme pomocí zpětné substituce Problémy s řešením na počítači 1) zaokrouhlovací chyby (+mohou se kumulovat) v důsledku floating point artihmetic 2) špatně podmíněné soustavy o závislost na měřených veličinách (měření není přesné…) o př.: řešení soustavy 2 lineárních rovnic o 2 neznámých = hledání průsečíku přímek → svírají-li malý úhel, pak se nepatrnou změnou řešení velmi mění Tvrzení 2.5 Všechny elementární matice jsou regulární. Důkaz 2.5
dopočítej!
15
Důsledek 2.6 Pro každou matici
typu
existuje regulární matice
řádu
taková, že
je v ŘOT.
Důkaz 2.6 Použijeme GE na . Z Věty 2.3 dostaneme matici v ŘOT. Jednotlivé kroky GE jsou EŘÚ a podle Tvrzení 2.2 existuje elementární matice Podle Tvrzení 2.5 jsou všechny regulární. Podle Tvrzení 1.6.1 je regulární také jejich součin
tak, že
je v ŘOT.
.
Věta 2.7 Buď čtvercová matice řádu , pak následující podmínky jsou ekvivalentní: 1) je regulární 2) soustava má právě jedno řešení pro všechna 3) soustava má právě jedno řešení 4) GE použitá na vede k matici se všemi řádky nenulovými 5) lze převést pomocí EŘÚ do jednotkové matice 6) existuje regulární matice taková, že 7) existuje regulární matice taková, že Důkaz 2.7 1) 1→2 • existuje inverzní k • vynásobme zleva • • • je jednoznačně určené řešení 2) 2→3 • speciální případ 2, kdy • 3) 3→4 (sporem) • Pokud by po převedení do ŘOT na matici pomocí GE byl poslední řádek nulový, existoval by sloupec v , který by nebyl bázový (neboť počet bázových sloupců je roven počtu nenulových řádků) • je-li jeho index , můžeme zvolit libovolně např.: a dopočteme řešení pomocí zpětné substituce; poté pro → dostaneme alespoň 2 řešení → SPOR s 3 4) 4→5 • Pomocí EŘÚ dostaneme z matici v ŘOT a všechny sloupce jsou bázové • platí, že ( je počet nenulových řádků) • • 1 2 n – indexy řádků, tedy • Matice je horní trojúhelníková s nenulovými prvky na hlavní diagonále • (tvoříme jednotkovou matici pomocí EŘÚ) •
i-tý řádek vynásobíme
→ matice, kde na hlavní diagonále jsou 1, stále horní trojúhelníková
• • •
(postupně odečítáme násobky řádků pod – začneme od prvního řádku) odečítáme násobek i-tého řádku od j-tého pro , pro
5) 5→6 • existují elementární matice tak, že • (součin) je regulární podle Tvrzení 2.5
16
6) 6→7 • existuje , regulární • pak existuje • • • • • • můžeme zvolit 7) 7→1 • , regulární • • • Algoritmus 2.5 Pro výpočet inverzní matice k matici A Při důkazu 5→6 jsme našli elementární matice Při důkazu 6→7 jsme zjistili, že . Tedy →
tak, že
17
Přednáška 8 _ 1. 11. 2011 Tvrzení 2.8 Nechť je čtvercová matice řádu . Pak pro čtvercovou matici Důkaz 2.8 → Dokážeme, že Buď
řádu
platí
právě když
.
je regulární tak, že dokážeme, že splňuje podmínku Věty 2.7.
(sloupcový vektor) takový, že Pro ← zaměň
Z
plyne
Podle Věty 2.7.3 je Z
regulární, čili existuje inverzní matice
.
plyne
Tvrzení 2.9 Je-li matice typu
,
regulární matice řádu
,
čísla, pak platí:
Důkaz 2.9 (pomocí Věty 1.7.1)
→ Je-li
←
Příklad 2.1 (Výpočet proudu v el. obvodu) Dostaneme soustavu rovnic, kde levá strana závisí pouze na odporech, a tudíž se při připojení nového zdroje nemění. Úprava levé strany tedy zůstává stejná a je dobré si ji pamatovat → LU-rozklad matice Lemma 2.10 Předpokládáme, že Potom 1) 2)
jsou dolní trojúhelníkové matice řádu
… je také D∆ s1HD je regulární a je také D∆s1HD.
18
s jednotkami na hl. diagonále (značení: D∆s1HD).
Důkaz 2.10 1) , chceme dokázat, že
Buď Pak tedy
Je-li tedy 2)
, nebo 1
platí buď
k
n
, nebo
… horní trojúhelníková s jednotkami na hl. diagonále (značení: H∆s1HD) → v ŘOT, všechny řádky jsou nenulové • podle Věty 2.7.4 je regulární • podle Tvrzení 1.6.3 je i regulární → počítáme podle Algoritmu 2.5 → používáme pouze EŘÚ 3. typu (přičítáme násobek k řádku nad) → používáme odpovídající el. matici – D∆ , ostatní prvky jsou 0 Tedy existují matice D∆s1HD takové, že … = součinu D∆s1HD tedy i je D∆s1HD
Věta 2.11 Předpokládejme, že je regulární čtvercová matice řádu existují jednoznačně určené matice takové, že: 1) 2) 3)
i
je D∆.
taková, že při GE vystačíme pouze s EŘÚ 3. typu. Potom
je D∆s1HD je H∆ s nenulovými prvky na HD
Postup řešení pomocí LU-rozkladu Řešíme , známe LU-rozklad matice , označíme Dostaneme (D∆ – přímá substituce) a Jak získat z GE matice
(zpětná substituce)
… (viz cvičení str.7b)
19
Důkaz 2.11 Na provedeme GE pomocí EŘÚ 3. typu (odpovídají •
existují matice
•
s nenulovými prvky na HD ,
•
D∆s1HD)
takové, že
je D∆s1HD, existuje
v ŘOT; podle Věty 2.7.4 jsou všechny nenulové → H∆
D∆s1HD, tedy
→
Jednoznačnost matic • • • • • • • • •
Je-li a a
a jsou D∆s1HD jsou H∆ s nenulovými prvky na HD
D∆s1HD* D∆s1HD= H∆* H∆ s nenulovými prvky na HD D∆s1HD= H∆ → tedy je diagonální (1naHD) →
Konstruktivní důkaz existence LU–rozkladu , protože stačí pouze EŘÚ 3. typu, je
→ obecně:
, pak
, odečteme násobek 1. řádku od 2. řádku , odečteme násobek 1. řádku od i–tého řádku , víme
…
20
Přednáška 9 _ 2. 11. 2011 → pokračování důkazu: všechny prvky v 1. sloupci vynulujeme pomocí matice , i–tý řádek matici
násobek 1. řádku
vynásobíme zleva maticí
, potom
,
,
GE bez prohazování řádků lze vyjádřit maticově: , je D∆s1HD ,
, kde prvních
k–tý sloupec
prvků je nulových,
ostatní prvky jsou nulové, protože např.:
→
Algoritmus 2.6 viz sešit str. 16 Definice 2.5 (LU–rozklad matice A) LU–rozklad matice
je vyjádření
kde
je D∆s1HD a
je H∆ s nenulovými prvky na HD.
Definice 2.6 Je-li prvními
čtvercová matice řádu , pak pro řádky a
definujeme hlavní minor matice
sloupci matice .
.
Př.:
21
jako matici
tvořenou
Věta 2.12 LU-rozklad čtvercové matice
řádu
existuje, právě když je každý hlavní minor matice
regulární pro
Důkaz 2.12 → Pokud LU-rozklad existuje: rozklad
rozklad
je hl. minor; součin ← použitím Věty 2.11
do bloků určený
do bloků určený
; potom
regulárních matic je také regulární
Příklad 2.2 Počty operací viz sešit str. 17. v principu jde o to, že pomocí LU–rozkladu je to rychlejší ;)
Kap3: Tělesa Definice 3.1 (těleso je) … množina s operacemi „ “, „ “ splňující axiomy: (A0) … (množina je uzavřená na ) (A1) … (asociativita) (A2) … (komutativita) (A3) … (existence nulového prvku) (A4) … (existence opačného prvku) (M0) (M1) (M2) (M3) (M4)
… (množina je uzavřená na ) … (asociativita) … (komutativita) … (existence jednotkového prvku) … (existence inverzního prvku)
(D) (N)
… (distributivita)
Tvrzení 3.1 V každém tělesu
platí: (důkazy viz materiály na webu přednášejícího – měly se tam objevit)
1) 2) 3) 4) 5) 6)
nulový prvek je určen jednoznačně opačný prvek je určen jednoznačně jednotkový prvek je určen jednoznačně inverzní prvek je určen jednoznačně
7) 8) 9) 10) 11) 12)
– rovnice rovnice z z
Pokud má právě jedno řešení má právě jedno řešení plyne plyne
22
.
Příklady těles ℝ jsou tělesa vs.
• • •
není těleso, protože:
vezmeme „normální výsledek“ a zapíšeme zbytek po dělení dvěma dvouprvkové těleso modulo 2 modulo 3 není těleso!!!, protože
Obecně: modulo
je těleso právě tehdy, když
je prvočíslo.
23
Přednáška 10 _ 8. 11. 2011 V
ℝ
Definice 3.2 Pokud existuje přirozené číslo takové, že v tělese platí charakteristika tělesa . Pokud žádné takové neexistuje, říkáme, že
, pak nejmenší takové má charakteristiku .
nazýváme
Věta 3.2 Charakteristika každého tělesa je buď , nebo prvočíslo. Důkaz 3.2 Pokud je charakteristika
větší než , pak existuje
Je-li
, kde
složené číslo,
takové, že
.
. → z Tvrzení 3.1.6 plyne, že buď
Tedy složené číslo
nemůže být nejmenší takové číslo, pro které platí
nebo . Tedy charakteristika
musí být prvočíslo.
Kap4: Aritmetické vektorové prostory Definice 4.1 Aritmetický vektor nad tělesem
je matice
,
nazýváme dimenze aritmetického vektoru.
Definice 4.2 Je-li aritmetický vektor dimenze • vektory značíme • prvky budeme nazývat skaláry
nad tělesem , pak každý prvek
nazýváme i–tá souřadnice .
Operace s vektory dimenze n 1) sčítání 2) násobení skalárem • základní vlastnosti těchto operací jsou popsány v Tvrzení 1.1, Tvrzení 1.2 Definice 4.3 Množinu všech aritmetických vektorů dimenze nad tělesem a označujeme .
nad tělesem
nazýváme aritmetický vektorový prostor dimenze
Definice 4.4 Neprázdná podmnožina se nazývá podprostor a pro každý vektor a každý prvek platí, že Tvrzení 4.1 Pro každou matici Důkaz 4.1 Platí, že Je-li a Je-li a
typu
nad
pokud pro každé dva vektory .
je množina všech řešení homogenní soustavy
– množina řešení
je neprázdná. . .
24
také
podprostor
.
Tvrzení 4.2 je těleso 1) každý podprostor obsahuje 2) průnik libovolně mnoha podprostorů je opět podprostor 3) Pro každou podmnožinu existuje nejmenší podprostor (v uspořádání inkluzí) obsahující Důkaz 4.2 1) a pro libovolný vektor platí 2) Jsou-li podprostory , potom má být podprostor 3) Průnik všech podprostorů obsahujících je podprostor podle 2) a je obsažen v každém podprostoru který obsahuje . Definice 4.5 Nejmenší podprostor
obsahující množinu
Tvrzení 4.3 Jsou-li podmnožiny 1) Je-li 2) 3) 4)
se nazývá lineární obal
a označujeme jej
, pak platí:
pak
Důkaz 4.3 1) platí , tedy 2) zřejmé 3) podle 2) neboť potřebujeme dokázat : je podprostor, který obsahuje 4) : platí, že (protože pak násobek : k tomu stačí ukázat, že Jsou-li
) je podprostor
.
prvky U potom
Definice 4.6 Pro každou matici 1) 2) 3) 4)
typu
nad
definujeme:
nulový prostor jako množinu všech řešení homogenní soustavy , (značení:) podprostor levý nulový prostor jako podprostor sloupcový prostor jako lineární obal sloupcových vektorů , označujeme podprostor řádkový prostor jako sloupcový prostor , označujeme
Definice 4.7 Jsou-li
podmnožiny
Tvrzení 4.4 Součet podprostorů
, pak definujeme jejich součet
je (opět) podprostor
.
25
,
Důkaz 4.4 jsou podprostory • •
Jsou-li
, ,
neboť jsou to podprostory
Tedy
•
Je-li
Tvrzení 4.5 je matice typu
nad
, pak platí:
1) Jsou-li řešení , pak 2) Jsou-li řešení , pak existuje takový, že 3) Množina všech řešení soustavy se rovná , kde Důkaz 4.5 1) – – – , stejně tak 2) ; 3) Je-li řešením a , potom prvek je řešením Naopak libovolné řešení z rovnice lze vyjádřit ve tvaru
26
je libovolné pevně zvolené řešení
je řešením , kde
podle 2.
tedy každý
Přednáška 11 _ 9. 11. 2011 Pozn.: • Nejmenší podprostor • pokud podprostor obsahuje pouze jeden prvek → (podprostoru) obsahuje přímku • Podprostory ℝ o {0} o ℝ → přímka procházející 0 a (bodem) o + další bod → rovina … • vℝ o počátek o přímka – procházející o rovina o prostor Definice 4.8 Platí-li
, pak říkáme, že
Tvrzení 4.6 Jsou-li podmnožiny
a
generuje podprostor . Je-li
, potom Pozn.: = Pokud k
, říkáme, že
přidáme vektory, které na
lineárně závisí na .
lineárně závisí, tak
Důkaz 4.6 podle Tvrzení 4.3.2 Je-li podprostor obsahující , pak musí obsahovat i Takže Každý podprostor , který obsahuje , obsahuje i tedy Pozn.: Platí, že
, tedy
Definice 4.9 •
Množina vektorů z rovnosti
se nazývá lineárně nezávislá (LN) v , jestliže plyne, že .
•
Pokud
není LN, říkáme, že je lineárně závislá (LZ).
Pozorování Pokud , je lineárně závislá, protože Je-li LN v , pak každá její podmnožina je také LN v z definice se změní pouze počet podmnožin Je-li , pak je LZ
27
a každé vektory
nezměníme.
Tvrzení 4.7 Množina
je LN, právě když pro každý vektor
platí, že
.
Důkaz 4.7 → Sporem: Kdyby platilo , pak by existovaly navzájem různé vektory že pro tedy je nenulový koeficient → SPOR s LN množiny ← Sporem: Kdyby byla LZ, existovaly by navzájem různé vektory a koeficienty že a alespoň jeden tedy tedy Věta 4.8 (Steinitzova věta o výměně – SVoV) Je-li podprostor , konečná množina LN v a lze přeindexovat tak, že generuje podprostor .
takové,
takové,
generuje , pak platí
a vektory
Důkaz 4.8 indukcí podle 1)
(je LN) Tedy Protože Vyjádříme Tedy a
pro . Přeindexováním dosáhneme
existuje
Tvrzení 4.6 2) Nechť o tvrzení platí: Tj. a po přeindexování … můžeme vyjádřit jako lineární kombinaci kdyby Tedy alespoň 1
.
můžeme odebrat, protože je lin. komb.
generuje
bylo by
(spor s tím, že
je LN)
pro
Proto . Po přeindexování můžeme předpokládat, že → pokračujeme stejně jako v 1) Definice 4.10 Jestliže množina
Příklad 4.1 Vektory Důkaz: • • Tedy • pokud
,
je podprostor
,
generuje
i–tá souřadnice , kde
tvoří bázi v
generuje
se nazývá standardní báze v
28
.
a je LN v
, tak ji nazýváme báze .
Věta 4.9 Každý podprostor pouze v případě
má nějakou bázi. Všechny báze
mají stejný počet prvků
, přičemž rovnost nastává
.
Důkaz 4.9 • Je-li , je prázdná množina bází v . • Pokud , existuje • Platí-li je báze v • Je-li , pak existuje • Množina je LN, je-li • … kdyby , pak , pak i • pak … Spor s volbou • Tedy je LN • … Pokračujeme dále analogicky pro … atd. až po takové, že je LN v a • Spor: kdyby , dostaneme LN a současně generuje – měli bychom množinu větší, než standardní báze, která generuje a to je spor s Větou 4.8
29
Přednáška 12 _ 15. 11. 2011 Je-li množina vektorů
LN a
Je-li Kdyby
a
platilo by Tedy
Znovu a přehledněji: Je-li je báze. Pokud zvolíme Pokud Pokud
,
Důkaz (pomocného tvrzení) pro . což je ve sporu s volbou a z LN plyne
je LN
, je báze , existuje
tak, že
je LN
po krocích najdeme LN množinu takovou, že Pokud by , našli bychom množinu →Spor s: v existuje (standardní) báze, která má prvků, tedy každá LN v
• •
•
Jsou-li a báze v podle SVoV je , stejně tak Je-li báze v víme, že je báze v podle SVoV je v existuje báze velikosti – standardní báze je-li podprostor a je báze v je LN v Pokud by Použijeme Tvrzení (pomocné) – pro k nalezení
Tvrzení 4.10 Pro množinu 1) 2) 3)
, kde
Tvrzení (pomocné) takový, že je LN.
, potom existuje
je podprostor
takové, že
má nejvýše
je LN v
prvků
– spor s SVoV
jsou následující podmínky ekvivalentní:
je báze v je minimální generující množina v je maximální LN množina
Důkaz 4.10 1→2 generuje pokud
, plyne z SVoV, že
2→3 Chceme dokázat, že je LN v : Kdyby nebyla LN, existoval by , který by byl lineární kombinací ostatních vektorů (Tvrzení 4.7) Podle Tvrzení 4.6 platí, že – Spor s tím, že je minimální generující množina 3→1 Chceme dokázat, že Kdyby ne, tak podle Tvrzení (pomocného – z důkazu 4.10) najdeme větší LN množinu v – Spor s maximalitou 30
Věta 4.11 Je-li podprostor
a
je LN podmnožina , pak lze
Důkaz 4.11 Zvolíme bázi v . Podle SVoV je , po přeuspořádání Podle Tvrzení 4.10 je to báze.
rozšířit do báze .
platí, že
generuje .
Definice 4.11 Počet prvků libovolné báze podprostoru
se nazývá dimenze
Tvrzení 4.12 Jsou-li podprostory
.
pak
a označujeme ji
Důkaz 4.12 • pomocí SVoV Věta 4.13 (O dimenzi průniku a součtu podprostorů) Jsou-li podprostory potom Důkaz 4.13 myšlenka: zvolíme bázi v Podle Věty 4.11 ji rozšíříme do báze Podle Věty 4.11 ji rozšíříme do báze
podprostoru podprostoru
→ potřebujeme najít v bázi, která má dimenzi → sjednocení a → je podmnožina → chceme dokázat, že je to báze v 1) generuje … ok … Buď
.
má právě
tedy, že
je báze
, platí, že tedy
je báze
, kde
tedy
Tedy 2) je LN Je-li
31
prvků
.
Proto prvek
Protože
je báze
, lze vyjádřit
Tedy
Protože → , tedy
je báze v
je báze
→
Proto Tvrzení 4.14 je matice typu nad . Je-li 1) množina vektorů
je LN. regulární matice řádu a je LN v právě když
2) množina vektorů
generuje
3) množina vektorů
je báze
4) 5) Důkaz 4.14 • pomocí Tvrzení 2.9 1) → Je-li
(tedy LN), platí, že
, pak platí: je LN v
právě když
generuje
právě když
je báze
LN v
Podle Tvrzení 2.9 platí, že Protože
je LN, platí
Tedy
je LN
← opačná implikace – totéž, pouze násobíme zleva 2) → Pokud generuje existuje pro každé
vyjádření
Tedy
Podle Tvrzení 2.9 platí, že
j-tý sloupec je lineární kombinací vybraných sloupců Proto generuje ← opačná implikace: předpokládáme, že
generuje
3) plyne ihned z 1, 2 4) plyne ihned z 3 5) plyne z Věty 1.7.2 každý řádek v je lineární kombinací řádků matice Proto Tedy také pomocí násobení zleva 32
a vynásobíme zleva
Přednáška 13 _ 16. 11. 2011 Příklad 4.2 (Vzorec pro n-tý člen Fibonacciovy posl.) , , ℝ ℝ je podprostor ℝ dokaž: Je-li
.
… zvolit si mohu první dva prvky → Důkaz: musíme najít bázi , dostanu , dostanu Je-li
první dva prvky určují následující • • •
indukcí podle jsou LN Je-li musí být
dokážeme, že
Leží v U nějaká geometrická posloupnost? , q musí splňovat :
→ pokud jsou LN, tak tvoří bázi ,
… pro nultou souřadnici … pro první souřadnici jediné řešení: je báze v U, chceme najít vyjádřené (Fib. posl.)
,
Obecná lineární rekurentní posloupnost … libovolně. Pak:
33
Tvrzení 4.15 je matice typu . je matice v ŘOT, kterou dostaneme z pomocí EŘÚ. Následující podmínky jsou ekvivalentní: 1) je bázový sloupec 2) nelze vyjádřit jako lineární kombinaci předchozích sloupců 3)
nelze vyjádřit jako lineární kombinaci předchozích sloupců v
Důkaz 4.15 Existuje regulární matice řádu taková, že 2↔3 plyne z Tvrzení 4.14.2 1↔2 → indexy bázových sloupců v jsou , … z definice ŘOT lineární kombinace
←: Je-li
(vždy), ale
tedy
nebázový sloupec →
→ v tomto případě je
je lineární kombinací předchozích
→ lineární kombinací sloupců
Potřebujeme najít
tak, že
tuto soustavu řešíme pomocí zpětné substituce → analogicky Definice 4.12 Je-li matice typu , potom nazýváme sloupec předchozích sloupců matice .
bázový sloupec matice , pokud není lineární kombinací
Definice 4.13 Matice
typu
je v redukovaném řádkově odstupňovaném tvaru (RŘOT), je-li v ŘOT a jsou-li
indexy bázových sloupců
, potom
platí
a dále
.
Tvrzení 4.16 Každou matici lze pomocí EŘÚ převést do RŘOT. Důkaz 4.16 Pomocí GE převedeme řádek číslem . Poté
do ŘOT, označíme indexy bázových sloupců. Poté vynásobíme i-tý odečteme vhodný násobek m-tého řádku od řádku nad ním, abychom vynulovali
všechny prvky na místech Věta 4.17 Pro každou matici
pro
platí
Důkaz 4.17 Existuje regulární matice taková, že Podle Tvrzení 4.14.4 platí, že Podle Tvrzení 4.14.5 platí, že
.
je v RŘOT.
34
Stačí dokázat
bázové sloupce
… prvek standardní báze v
→ tedy jsou LN
Podle Tvrzení 4.15.2 je každý nebázový sloupec lineární kombinací bázových sloupců. To znamená, že bázové sloupce generují , jsou LN, tedy tvoří bázi , tedy (počtu bázových sloupců). Nenulové řádky matice jsou LN (lineární kombinace řádků → tedy jsou LN a generují , tedy tvoří bázi, proto
→ koeficienty jednotlivých řádků musí být nulové .
Definice 4.14 Číslo
se nazývá hodnost matice
a budeme ho označovat
.
Důsledek 4.18 (Věty 4.17) Pro každou matici platí: 1) 2)
je počet nenulových řádků v matici , která dostaneme z
35
pomocí GE
Přednáška 14 _ 22. 11. 2011 Věta 4.19 Pro čtvercovou matici
řádu
je ekvivalentní:
1) je regulární 2) Sloupcové vektory matice jsou lineárně nezávislé 3) Řádkové vektory matice jsou lineárně nezávislé 4) Důkaz 4.19 1→4 je regulární, z Věty 2.7.4 plyne, že v matici v ŘOT, kterou dostaneme z → podle Důsledku 4.18.2 je
pomocí GE jsou všechny řádky nenulové
4→1 Je-li , jsou všechny řádky v matici v ŘOT matice, kterou dostaneme z (Důsledek 4.18.2), tedy matice je regulární (podle Věty 2.7.4)
pomocí EŘÚ nenulové
4→3 je minimální generující množina v
a tedy je báze, tedy LN,
podle Tvrzení 4.10.2 3→4 Jsou-li
LN, tvoří bázi
, protože jej generují. Proto
4↔2 – úplně stejné jako 3↔4, protože Tvrzení 4.20 Je-li matice typu Důkaz 4.20 Každý sloupec proto
a
typu
(z definice
)
, pak
je lineární kombinací sloupců matice
(Věta 1.7.1). Tedy
,
Tedy stejně tak použijeme
(stejně jako pro sloupcové prostory:) , použijeme Větu 1.7.2 Příklad 4.3 Obyvatelé obce Hrátkov se rádi sdružují do klubů za účelem zábavy. Obecní úřad vydal vyhlášku regulující kluby. Musí platit: 1) každý klub má lichý počet členů 2) každé dva kluby mají společně sudý počet členů Dokažte, že počet klubů je počtu obyvatel Hrátkova Řešení: … obyvatelé Hrátkova … kluby
•
(0 je sudá) Definujeme matici
typu
nad
, 36
-
kde
-
• •
… čtvercová matice řádu
Tvrzení 4.2.1 Jsou-li matice typu
, pak
Důkaz 4.21
Věta 4.13 Věta 4.22 Pro každou matici
typu
platí
.
Důkaz 4.22 zvolíme bázi doplníme ji do báze Dokážeme, že
v (podle Věty 4.11) tvoří bázi
1) generují:
Protože
je báze v
, protože Tedy proto je generovaný 2) zbývá dokázat, že
je LN
37
Protože
je LN, platí: je LN
Tedy báze Věta 4.23 Je-li matice typu
, pak platí:
1) 2) 3) 4) Důkaz 4.23
… z Věty 4.22 … z Věty 4.22 Dodělej důkazy…
Věta 4.24 (Frobeniova věta) Soustava lineárních rovnic
nad tělesem
je řešitelná právě tehdy, když
Důkaz 4.23 Platí Rovnost nastává právě když což je právě když existuje takový, že
Rovnost
platí
.
,
je řešitelná.
Kap5: Permutace • •
• • •
čtvercová matice , řádu … chceme vybrat prvky matice tak, abychom z každého sloupce a za každého řádku vybrali právě
je zobrazení z je prosté a na
do
Definice 5.1 Permutace na množině je vzájemně jednoznačné zobrazení . Identické zobrazení se nazývá identická permutace na . Inverzní zobrazení se nazývá inverzní permutace. Jsou-li permutace na , pak je permutace na , nazývá se složení permutací Lemma 5.1 Pro skládání permutací na 1) 2) 3)
platí:
permutace permutace permutace
– množina všech permutací na
– metrická grupa na 38
.
Přednáška 15 _ 23. 11. 2011 Příklady zápisu permutací 1) zápis tabulkou případně – počítá s 1. řádkem automaticky 2) graficky graf permutace – z každého a do každého bodu vede právě 1 šipka
3) cyklický zápis
Skládání permutací
Definice 5.2 Permutace se nazývá transpozice má-li 1 cyklus délky 2 a ostatní cykly délky 1. Pozn.: Pro transpozice se hodí redukovaný cyklický zápis: Ekvivalentní definice: Existují prvky Lemma 5.2 Každou permutaci na
takové, že
lze složit z transpozic.
Důkaz 5.2 Předpokládáme, že . Existuje v ní alespoň jeden cyklus délky
Existují transpozice tak, že Pro každou transpozici platí , tedy
Lemma 5.3 Je-li a transpozice, pak počet cyklů v
,av
se liší od počtu cyklů v
39
o .
Důkaz 5.3
1) Jsou-li
v různých cyklech : cykly
–
cyklus –
2) jsou-li
cyklus
ve stejném cyklu : – 1 cyklus
Lemma 5.4 Jsou-li a 2 vyjádření permutace p jako složení transpozic, pak mají čísla
stejnou paritu (=obě sudá/obě lichá).
Důkaz 5.4
• • •
v je počet cyklů v je také cyklů protože každá transpozice změní počet cyklů o 1, musí být
sudé
Definice 5.3 Permutace se nazývá sudá, pokud jí lze složit ze sudého počtu transpozic. Permutace se nazývá lichá, pokud jí lze složit z lichého počtu transpozic. Definujeme znaménko permutace
Tvrzení 5.5 Pro dvě libovolné permutace
platí:
Tj. složení dvou sudých/lichých permutací je sudé, složení liché a sudé permutace je liché. Speciálně . Důkaz 5.5
transpozic… 40
Lemma 5.6 Je- li počet cyklů v permutaci
, potom
.
Důkaz 5.6 cyklů délky 1 cyklů;
každá transpozice změní počet cyklů o 1
– ;
(2 transpozice)
Praktické využití: • hra s posouváním čísel (tabulka ) – pomocí znamínek permutace lze určit, zda lze daná pozice složit • Marian Rejewski – rozluštil Enigmu (permutace na )
41
Přednáška 16 _ 29. 11. 2011 Kap6: Determinanty Definice 6.1 čtvercová matice řádu
nad .
Determinant:
Pozn.:
– výběr prvků z matice (z každého řádku a sloupce právě jeden)
Příklad 6.1 Matice 2. řádu
Matice 3. řádu +
Lemma 6.1 Je-i
–
H∆ řádu , pak
Důkaz 6.1 je H∆ matice pokud Zvolme Buď
.
(z definice H∆).
Tedy a tedy
Zbývá dokázat, že v každé permutaci existuje takový prvek ( Pokud – cyklus obsahující se rovná Je-li posloupnost striktně rostoucí platí, že Tedy prvek Pokud posloupnost pak existuje takové, že označíme , potom Tedy V
není striktně rostoucí,
je pouze 1 případně nenulový sčítanec odpovídající .
42
).
Příklad 6.2 (Geometrický význam determinantu matic 2. a 3. řádu) Řešení (matice 2. řádu): Předpokládejme, že pak obsah rovnoběžníku určeného sloupcovými vektory
α
a pokud pokud → znaménko
– pokud úhel
a
měřený proti směru hodinových ručiček je
f
φ
vektor
– lineární kombinace
matice, která každý vektor pootočí o φ
č
otáčíme o úhel –
vektor ú
č
ý
! matice otočení o úhel
obsah rovnoběžníku určeného
v opačném směru
se rovná 43
).
Řešení (matice 3. řádu): je objem rovnoběžnostěnu určeného sloupcovými vektory tvoří-li sloupcové vektory pravotočivý systém tvoří-li sloupcové vektory levotočivý systém
vℝ
(obsah podstavy výška) Givensovy rotace: – matice otočení kolem 1. osy o úhel φ v kladném směru – matice otočení kolem 3. osy o úhel φ v kladném směru – matice otočení kolem 2. osy o úhel φ v kladném směru Tvrzení 6.2 Pro každou matici .
platí
Důkaz 6.2
výběr určitých permutací tj. permutace protože pro každou v obou sumách ( ) máme tytéž součiny se stejnými znaménky. Tvrzení 6.3 Má-li matice
2 stejné řádky, pak
.
44
Důkaz 6.3 Předpokládáme, že ( )
a nějaké
i j
(1 transpozice změní znaménko) Tedy permutace z do dvojic Různé dvojice a Pokud se protínají, je buď: , nebo , nebo , nebo Proto
– sčítance dávají dohromady 0 jsou disjunktní.
.
45
Přednáška 17 _ 30. 11. 2011 Věta 6.4 řádu
nad
dostaneme z
pomocí EŘÚ
potom platí: 1) 2) 3)
, pokud jsme prohodili 2 různé řádky , pokud jsme nějaký řádek násobili , pokud jsme k nějakému řádku přičetli násobek jiného řádku
Pozn. analogicky pro sloupce (důsledek
)
Důkaz 6.4 1) Prohazujeme i-tý a j-tý řádek:
Zvolme počítáme-li v
vezmeme sčítanec odpovídající
→ stejné členy, pouze jiné znaménko
2)
3)
kde má stejný i-tý a j-tý řádek, tedy tedy
(podle Tvrzení 6.3)
Pozn.: z Věty 6.4.1 plyne Tvrzení 6.3. Jsou-li dva řádky stejné (a charakteristika tělesa prohozením těchto řádků dostaneme matici . Podle Věty 6.4.1 platí , tedy . Důsledek 6.5 1) 2) 3) , je-li
elementární matice
Důkaz 6.5 Každou elementární matici dostaneme z pomocí příslušnou elementární transformací je H∆ → tedy (podle Lemmatu 6.1 – součin prvků a diagonále).
46
je různá od 2), pak , tedy
Věta 6.6 Matice je regulární právě tehdy, když
.
Důkaz 6.6 → Převedeme na matici v ŘOT pomocí EŘÚ Dostaneme elementární matice takové, že determinanty elementárních matic jsou vždy nenulové, proto ← má všechny řádky nenulové
. je regulární
Věta 6.7 (O součinu determinantů) Jsou-li čtvercové matice řádu , pak platí, že Důkaz 6.7 Je-li singulární (tedy potom Je-li regulární, platí, že
.
), je
je také singulární, , kde
jsou elementární matice
Definice 6.2 Je-li
čtvercová matice řádu , pak označíme
i-tého řádku a j-tého sloupce. nazýváme minor určený Číslo
.
se nazývá kofaktor
Matice Matice
čtvercovou matici řádu
určený
.
se nazývá kofaktorová matice k matici . se nazývá adjungovaná k , značíme ji
.
Věta 6.8 (O rozvoji determinantu) je čtvercová matice řádu . je kofaktorová k . Potom platí: 1) 2) Důkaz 6.8 (stačí dokázat 1, protože 2 plyne z
(Tvrzení 6.2)
→ stačí dokázat, že 1) zvolme nejdříve v součet všech součinů obsahujících prvek
se rovná
definujeme
2) zvolíme libovolně chceme a.
i-tý řádek posuneme na n-tý 47
, kterou dostaneme z
vynecháním
• prohazováním sousedních řádků převedeme i-tý řádek na pozici n-tého, ostatní řádky zůstávají ve stejném pořadí (prohazujeme po jednom) • vyžaduje to prohození b. j-tý sloupec posuneme na n-tý • prohazováním sousedních sloupců převedeme i-tý sloupec na pozici n-tého, ostatní sloupce zůstávají ve stejném pořadí (prohazujeme po jednom) • vyžaduje to prohození dostaneme matici označíme minor v Platí, že
určený
Součet všech součinů v v v
jako obsahujících
se rovná
je součet všech součinů obsahujících je součet všech součinů obsahujících
součet všech součinů v
obsahujících prvek
obsahujících prvek
, tj. rovná se
rovný rovný
se rovná
násobku součtu součinů v
V součtu
se v každém součinu vyskytuje právě jeden prvek
z i–tého řádku
Po přeuspořádání sum dostaneme, že
Úloha 6.1 Spočítejte determinant Vandermondovy matice a rozhodněte, kdy je Vandermondova matice regulární. Řešení: (převzato z textu k přednáškám)
48
49
Úloha 6.2 V rovině máme body
.
Dokažte, že existuje právě 1 polynom stupně nejvýše , jehož graf prochází body Řešení: Hledáme
pro
.
koeficienty musí splňovat
… tj. musí splňovat soustavu lineárních rovnic:
Pokud
je regulární
existuje právě 1 řešení
Příklad 6.3 (Shamirovo schéma pro sdílení tajemství) Chceme rozdělit nějakou informaci mezi lidí tak, aby tu informaci mohlo zjistit libovolných z méně než členů nic nezjistí.
50
lidí a skupina složená
Přednáška 18 _ 6. 12. 2011 Řeš. (Příklad 6.3) množina sdílených hodnot např. PIN kód … Zvolíme prvočíslo Důvěryhodná osoba (DP) zvolí , pracuje se … počet účastníků počet nutný ke zjištění využijeme Úlohy 6.2 sdílené tajemství je DP zvolí náhodně polynom stupně zvolí náhodně tak, že tedy polynom
s koeficienty v , navzájem různé , kde
i-tému účastníkovi sdělí dvojici Sejde-i se
tedy
pro
účastníků sdělí si
pro
Podle Úlohy 6.2 existuje právě 1polynm
s koeficienty v
musí platit Sejde-li se pouze Přidáme-li ke
takový, že
pro
indexů
, pokud znají , zjistí účastníků, znají hodnoty dvojicím dvojici pro
pro
kde
existuje právě jeden polynom
stupně
a navíc
pro jakýkoli absolutní člen
existuje právě jeden polynom → jakékoli „tajemství“ může být výsledkem
Tvrzení 6.9 Je-li regulární matice, pak
.
Důkaz 6.9 i-tý sloupec V součinu
platí
Potřebujeme dokázat, že
pro
j-tý řádek → kofaktor v nahradíme j-tý řádek i-tým. Dostaneme matici B, ve které se i-tý řádek rovná j-tému → Spočteme tak, že jej rozvineme podle j-tého řádku
tedy Tvrzení 6.10 (Cramerovo pravidlo) Je-li soustava lineárních rovnic nad tělesem a matice je regulární, potom , kde
, pro který platí, že
dostaneme z
tak, že nahradíme j-tý sloupec
51
sloupcem pravých stran .
Důkaz 6. 10
chceme
všechny sloupce, kromě j-tého se rovnají příslušným sloupcům , j-tý rozvoj podle j-tého sloupce
Kap7: Skalární součin Pozn.: pracujeme nad ℝ nebo Je-li potom označujeme číslo komplexně sdružené k číslu Platí Definice 7.1 Je-li
matice typu
nad , pak matici
typu
sdruženou k . Definice 7.2 ℝ
Jsou-li
potom standardní skalární součin (SSS)
Jsou-li
definujeme jako číslo
pak definujeme SSS jako
Tvrzení 7.1 Jsou-li 1) 2) 3) 4) 5)
a
, pak platí:
je nezáporné reálné číslo
Důkaz 7.1 1)
neboť 2) 3) 4) 5)
52
, kde
nazýváme hermitovsky
Úloha 7.1 Dokažte pouze s použitím Tvrzení 7.1 1) 2) 3) Řešení (na přednášce nebylo, tedy můj pokus) 1) pomocí 5, 4 2) pomocí 5, 3 3) pomocí 5, 3 (kde
)
53
Přednáška 19_7. 12. 2011 Definice 7.3 Norma vektoru
ℝ
určená SSS je číslo ℝ
Úloha 7.2 Dokažte, že platí: ℝ
1) 2) 3)
ℝ ℝ
ℝ
Řešení (na přednášce nebylo, tedy můj pokus) 1) plyne z vlastností SSS tedy
(podle Tvrzení 7.1.1)
2)
(podle Tvrzení 7.1.2)
3) Věta 7.2 (Cauchy–Schwartzova–Bunjakovského nerovnost) Pro každé dva vektory ℝ platí: přičemž rovnost platí, právě když
pro nějaké
ℝ
Důkaz 7.2 Je-li … zjevně platí. Předpokládejme, že . Najdeme ℝ takové, že
Dosadíme-li
dostaneme, že
Pozn. dále pracujeme v
z
Tvrzení 7.3 (Trojúhelníková nerovnost) Pro každé ℝ platí: . Důkaz 7.3 (CSB nerovnost) … 54
.
Příklad 7.1 (Geometrický význam SSS v ℝn) ℝ
kosinová věta: →
Definice 7.4 ℝ
Vektory
jsou kolmé, pokud
.
Definice 7.5 Množina vektorů ℝ • ortogonální (OG), pokud •
se nazývá:
pro Tzn.: nemůže tam být
a všechny jsou na sebe kolmé
ortonormální (ON), pokud
Tvrzení 7.4 Každá OG množina v ℝ Důkaz 7.4 Nechť je OG Nechť Chceme
pro když
je LN.
jsou všechny členy rovny 0 :
Definice 7.6 Báze prostoru ℝ se nazývá ortogonální (ortonormální), pokud Standardní báze v ℝ je ON. Tvrzení 7.5 Je-li ON báze v ℝ
a
ℝ
pak
. Důkaz 7.5 Nechť = Pozn.:
,
pro
Definice 7.7 Koeficienty
se nazývají Fourierovy koeficienty a vyjádření
se nazývá Fourierův rozklad
vzhledem k ON bázi
.
55
je OG (ON).
Tvrzení 7.6 Jsou-li
vektory z ℝ a ON báze v ℝ
, potom
Důkaz 7.6
Pozn.: Tvrzení 7.7 (Pythagorova věta) Dva vektory ℝ jsou kolmé, právě když
.
Důkaz 7.7 → Jsou-li kolmé, platí Potom ← Pokud platí
. jsou na sebe kolmé
Kap8: Gramova–Schmidtova ortogonalizace Důkaz 8.1 Úkol: Dána LN množina
ℝ
ℝ
, chceme najít ON množinu
takovou, že
Postupujeme indukcí podle 1)
musíme zvolit
… bude mít délku 1 a zároveň bude násobkem
2) Předpokládejme, že pro nějaké hledáme má platit, že
jsme již sestrojili
je ON množina v
, tedy
Musí platit:
Kdyby to by byl spor s LN Tedy musí platit označme
ℝ
známe
musí být
56
, která je ON a platí
má být ON báze v
Přednáška 20 _ 13. 12. 2011 pokračování: (zbývá dokázat kolmost a rovnost lineárních obalů) 1) chceme předpokládáme: z formulky pro Tedy
plyne, že
opačnou inkluzi dokazujeme stejně, použijeme:
2) chceme z formulky pro 3) kolmost
pro
pro pro
je tento člen 1 je to 0
Algoritmus 8.1 (Klasický GS–algoritmus) input: ℝ je LN output: ON pro
for
to do
Věta 8.1 Je-li LN množina v ℝ pro kterou platí Důkaz – viz výše
, pak klasický GS–algoritmus sestrojí ON množinu .
Důkaz 8.2 Vezmeme matici typu nad ℝ a předpokládáme, že označíme i-tý sloupec ℝ je LN Klasický GS-algoritmus vede k ON množině Platí
Označíme 57
má LN sloupce
ℝ
,
Platí
, kde
0 0 0
0
pro pro Věta 8.2 Je-li matice typu , , kde s kladnými čísly na HD, pro které platí: . Důkaz – viz výše
nad ℝ a je ON množina v ℝ
je LN v ℝ , potom existují matice typu a horní trojúhelníková matice řádu
Definice 8.1 Je-li matice typu s LN sloupci, pak se rozklad (obdélníkový) QR-rozklad matice . Pozn.:
má LN sloupce,
vynásobíme soustavu maticí
, kde
splňují podmínky z Věty 8.2, nazývá
je QR-rozklad matice
… to není ekvivalentní úprava!
: typu typu čtvercová řádu , protože
jsou ON
→ zpětná substituce Pozn.: pokud je řešitelná, pak řešení najdeme pomocí pokud není řešitelná … má řešení vždy (použili jsme neekvivalentní úpravu) a říká se mu řešení metodou nejmenších čtverců a to má speciální vlastnosti (viz později) Pozn.: GS-algoritmus není numericky stabilní
pro
Označíme pro
… viz str 42b typu 58
… jiné vyjádření vzorce pro k-tý vektor pro Označíme pro =…
Algoritmus 8.2 (Modifikovaný GS-algoritmus)
pro
Důkaz, že
→ → → atd. for
to pro
Tvrzení 8.3 Modifikovaný GS-algoritmus vede ke stejné ON množině
jako klasický GS-algoritmus.
59
Přednáška 21 _ 14. 12. 2011 Kap9: Unitární a ortogonální matice Definice 9.1 Čtvercová matice řádu nad se nazývá unitární, pokud její sloupce tvoří ON bázi v . Čtvercová matice řádu nad ℝ se nazývá ortogonální, pokud její sloupce tvoří ON bázi v ℝ . Pozn.: Každá unitární/ortogonální matice je regulární. Věta 9.1 Pro čtvercovou matici 1) 2) 3) 4)
nad
jsou následující podmínky ekvivalentní.
je unitární , tj. má ON řádky
Pro matici 5) 6) 7) 8)
řádu
řádu
nad ℝ jsou následující podmínky ekvivalentní.
je ortogonální má ON řádky ℝ
Důkaz 9.1 1→ 2 j-tý sloupec v i-tý řádek v
je je (sloupce jsou ON)
2 → 1 „čteme předchozí pozpátku“ 2↔3 má ON řádky 2→4
Pozn.: nebylo dokázáno! 4→1 : prvky standardní báze v chceme dokázat, že Pokud Pokud a) Reálná část
60
b) Imaginární část
Důsledek 9.2 Součin unitárních matic je unitární matice. Součin ortogonálních matic je ortogonální matice. Důkaz 9.2 jsou unitární matice řádu (Podle Věty 9.1.2) Věta 9.3 Je-li regulární matice nad ℝ, pak existují ortogonální matice . Matice jsou určené jednoznačně maticí .
a H∆ matice
s kladnými prvky na HD takové, že
Důkaz 9.3 • existenci jsme již dokázali (viz Důkaz 8.2) • jednoznačnost: Předpokládejme, že … splňující předpoklady ortogonální m. = H∆ s kladnými prvky na HD … ortogonální označme
i-tý sloupec
, pak
atd. Definice 9.2 Je-li
ℝ
, pak definujeme ortogonální doplněk
jako množinu
61
ℝ
.
Přednáška 22 _ 20. 12. 2011 Tvrzení 9.4 Je-li ℝ , podprostor 1) je podprostor ℝ 2) 3) 4) 5) 6) 7)
ℝ , potom platí:
… pozn.:
ℝ
Důkaz 9.4 1) Je-li Je-li Tedy 3) Je-li
… pouze pro větší názornost, dále jen
lze jednoznačně vyjádřit jako
a
, kde
, potom
ℝ je podprostor ℝ a potom
4) Je-li ℝ
5) Zvolíme bázi v , doplníme ji do báze pomocí GS-ortogonalizace najdeme ON bázi Pro tu platí, že Dokážeme, že
v v
ℝ
ℝ
Tedy podle 4 Tím jsme dokázali, že Zvolíme
, pak platí (podle Tvrzení 7.5)
pro
6) 7) Najdeme ON bázi
(…, protože
v
ℝ
(z 5) jednoznačně (podle 6) je-li
a
)
takovou, že
je báze
, , kde
62
… existuje
2) označíme Protože
… (viz 4) podprostor ℝ … (podle 5) ,
Definice 9.3 ℝ ,
Je-li
, pak matici
nazýváme elementární projektor určený .
Tvrzení 9.5 Buď elementární projektor určený , pak platí: 1) 2) ℝ platí 3) Důkaz 9.5 1) Pozn.:
, protože
2) Pozn.: 3)
řádkový.sloupcový vektor → číslo
, … (z 2)
Definice 9.4 ℝ
Je-li
pak matici nazýváme elementární (Householderův) reflektor určený .
Tvrzení 9.6 je elementární reflektor určený 1) 2) ( Důkaz 9.6
ℝ , potom platí: je unitární (ortogonální) matice)
1) 2) (Podle Věty 9.1 je
unitární (ortogonální)) 63
Příklad 9.1 (elementární rotátory) viz Givensovy rotace (Příklad 6.2) Definice 9.5 Elementární rovinný (Givensův) rotátor v ℝ je matice: i j
i j na HD jsou 1 ostatní prvky 0 … (cos, sin) Tvrzení 9.7 je ortogonální matice. Důkaz 9.7 Tzn., že sloupce musí tvořit ON bázi v ℝ : • velikost 1 … snadno se ukáže (buď nebo ) • kolmost … všechny sloupce kromě i-tého a j-tého jsou prvky standardní báze i-tý/j-tý sloupce násobený prvkem standardní báze = 0 i-tý krát j-tý sloupec = 0
64
Přednáška 23 _ 21. 12. 2011 Tvrzení 9.8 Nechť ℝ , potom existují Givensovy rotace takové, že
Důkaz 9.8 Je-li
, zvolíme
zvolíme
Je-li , zvolíme a libovolně tak, aby … tak pokračujeme, dokud nenarazíme na 1. nenulový prvek (např.: i-tý) pak máme Tvrzení 9.9 Buď . Označíme
, kde ℝ ℝ
Je-li
Householderův reflektor určený vektorem , tj.
, potom platí:
Důkaz 9.9
Pozn.:
jsou čísla;
je koeficient u
Dokážeme, že ℝ
ℝ Tedy Věta 9.10 (Ortogonální redukce) Pro každou matici typu nad kde .
ℝ existuje unitární (ortogonální) matice 65
taková, že
,
Důkaz 9.10 Householderův algoritmus Označíme , zvolíme a podle Tvrzení 9.9 je typu
najdeme
takovou, že
je čtvercová matice řádu
Položíme
… atd
Givensův algoritmus
atd. …
Definice 9.6 Je-li
matice typu
Tvrzení 9.11 Je-li ortogonální matice řádu Důkaz 9.11 pomocí Věty 9.1 platí:
nad ℝ
a
, potom Frobeniova norma matice
je matice typu
nad ℝ, potom
je číslo:
.
ℝ
Pozn.: na přednášce byly ještě poznámky o složitosti a numerické stabilitě jednotlivých algoritmů (GE, GSortogonalizace, Householderův alg., Givensův alg.) vyplynulo z toho mimo jiné, že GS–alg. modifikovaný se hodí spíše pro „husté“ matice a Householderův a Givensův spíše pro „řídké“ matice Následovala praktická úloha, kdy po nás někdo vystřelí raketu – ta letí samozřejmě po parabole … → metoda nejmenších čtverců
66
Přednáška 24 _ 3. 1. 2012 Kap10: Ortogonální projekce a metoda nejmenších čtverců Tvrzení 10.1 Je-li matice typu
nad ℝ, pak platí:
1) 2) 3) 4) 5) Pozn.: lze modifikovat na Důkaz 10. 1 1) Nechť je báze ukážeme, že tvoří bázi v víme, že tedy stačí dokázat, že je LN (pak bude maximální LN → tedy báze) odtud vyplyne, že , tedy
z
č
, tj. je lineární kombinací tj. existuje ℝ takový, že spočítáme tj. Víme tedy, že
, tedy
* protože je LN Tedy Položíme právě jsme dokázali, že 2) víme a 3) plyne z 2, položíme-li 4) 5) plyne ze 4, použité na Tvrzení 10. 2 Je-li matice typu ℝ , potom platí: 1) soustava je vždy řešitelná 2) Je-li řešitelná, pak množina všech řešení 3) má jednoznačné řešení právě když (tj. má LN sloupce); v tom případě
se rovná množině všech řešení
67
Důkaz 10.2 1) má řešení 2) násobení není ekvivalentní úprava… je-li řešením tedy je řešením (asociované) soustavy množina všech řešení se rovná – množina všech řešení asociované soustavy 3)
má jednoznačné řešení č
pokud
je regulární
není řešitelná, platí ℝ . Řešením → „řešení metodou nejmenších čtverců“.
Pozn.: Pokud minimalizují
jsou ty vektory
ℝ , které
Definice 10.1 Je-li soustava lineárních rovnic nad ℝ, potom soustavu rovnic k soustavě . Příklad 10.1 Máme body hodnoty . Koeficienty
nazýváme asociovaný systém normálních
v rovině, chceme najít polynom
, který v každém bodě
musí splňovat rovnici
• tato soustava nejspíš nebude řešitelná použije se metoda řešení pomocí asociované soustavy … tj. nejlepší možné řešení Příklad 10.2 Máme a známe QR-rozklad
je regulární,
, chceme jej použít pro řešení
je také regulární
Věta 10.3 (Ortogonální rozklad) je typu nad ℝ, potom platí: 1) ℝ 2) ℝ Důkaz 10.3 1) Označíme
ℝ
ℝ
ℝ
ℝ
ℝ 2) Použijeme 1) na matici
68
nabývá
Důsledek 10.4 (Fredholmova alternativa) Pro každou matici typu nad ℝ nastává právě jedna z následujících možností: 1) má řešení 2) má nenulové řešení Důkaz 10.4 • plyne z Věty 10.3.1 1) má vždy řešení 2) má nenulové řešení Tvrzení 10.5 (URV-rozklad) Buď matice typu nad ℝ Potom existují ortogonální matice
ℝ
má pouze nulové řešení ℝ
nemá vždy řeš.
. řádu
, ortogonální matice
řádu
a regulární matice
řádu takové, že
. Prvních sloupců matice tvoří ortonormální bázi Prvních sloupců matice tvoří ortonormální bázi zbylých sloupců tvoří ortonormální bázi
, zbylých
sloupců tvoří ortonormální bázi ,
.
69
.
Přednáška 25 _ 4. 1. 2012 Důkaz 10.5 Zvolíme ON bázi
v
a bázi je ON báze v
v
. Tedy je ON báze
je ortogonální.
typu
řádu Zbývá dokázat, že
je regulární Pozn.:
je regulární – tedy lze rozložit na součin elementárních matic, stejně tak
Definice 10.2 Vyjádření Tvrzení 10.6 Buď
, kde
splňují podmínky z Tvrzení 10. 5, se nazývá URV-rozklad matice .
URV-rozklad matice
Matice Splňuje rovnosti: 1) 2) 3) 4) Matice je těmito podmínkami určená jednoznačně. Důkaz 10.6 1) 2) stejně 3)
4) stejně jednoznačně určená: chceme: stejně se dokáže, že Potom Definice 10.3 Je-li matice typu nad ℝ, pak matice splňující podmínky 1–4 z Tvrzení 10.6 se nazývá Moore–Penrosova inverze (pseudoinverze) matice . Označuje se
70
Tvrzení 10.7 Je-li podprostor ℝ a ve tvaru Důkaz 10.7 Zvolíme a Pak
jeho ortogonální doplněk, pak každý vektor .
ℝ lze jednoznačným způsobem vyjádřit
ON bázi v ON bázi v . je ON báze v ℝ . Pak
Jednoznačnost: je-li , kde Potom chceme
protože Definice 10.4 Je-li
podprostor ℝ
ℝ a
. Potom
nazýváme ortogonální projekce
na
geometrická představa:
Tvrzení 10. 8 je podprostor ℝ ℝ Potom pro každý vektor
je ortogonální projekce platí, že
na
. .
Důkaz 10. 8
Poz
je typu , není řešitelná ℝ je ortogonální projekce na je řešitelná → metoda nejmenších čtverců Jak spočítat ?
71
.
Tvrzení 10.9 je typu je pseudoinverze matice . Potom pro každý vektor je ortogonální projekce vektoru
na
.
Důkaz 10.9 Pak platí:
ℝ pro nějaké
Ukážeme, že : Je-li , pak a : Je-li naopak , tj. zvolme ℝ
ℝ
chceme ukázat, že Je-li , platí Tedy a proto Tedy
je ortogonální projekce
na
Věta 10.10 (Metoda nejmenších čtverců) Buď soustava lineárních rovnic o Pak je ekvivalentní pro vektor ℝ
neznámých nad ℝ
je ortogonální projekce
na
1) 2) Důkaz 10.10 ℝ platí Platí i
z
, tj.
vyplývá
Pozn.: 2 možnosti jak řešit pomocí metody nejmenších čtverců (obě numericky nestabilní): 1) spočítat … potřebujeme pseudoinverzi, URV–rozklad 2) pomocí
Kap11: Matice jako lineární zobrazení Definice 11.1 Buď matice typu nad . Definujeme zobrazení zobrazení určené maticí . Tvrzení 11.1 Pro lineární zobrazení 1) 2) Důkaz: nebyl – dosaď
určené maticí
předpisem
platí:
za
72
, nazýváme jej lineární
Přednáška 26 _ 10. 1. 2012 Příklad 7.1 (ne to není chyba číslování) Existují 4 body v rovině takové, že vzdálenost libovolných dvou je liché číslo? Řešení: ne … 4 vektory v rovině ℝ předpokládejme: jsou lichá čísla
chceme dokázat, že B je regulární, to plyne z „jsou lichá čísla“ tedy je regulární = poškrtej dvojky označme SPOR! Definice 11.2 Libovolné zobrazení
splňující podmínky:
1) 2) se nazývá lineární zobrazení. Tvrzení 11.2 Každé lineární zobrazení
je určené nějakou maticí.
Důkaz 11.2 Vezmeme standardní bázi Označíme Je-li
je určené maticí Tvrzení 11.3 Buď
báze v
a platí
Platí i Důkaz 11.3 Z předpokladů plyne:
je LN nezávislá → 73
Definice 11.3 Je-li
báze v
pak vektor
,
se nazývá vektor souřadnic
Pozn.: Je-li
tj. Tvrzení 11.4 Nechť
tj. a
označme
vzhledem k bázi
.
, pak
je vektor souřadnic
a
vzhledem ke standardní bázi
dvě báze v
.
a
jsou souřadnice vzhledem k jsou souřadnice vzhledem k
řádu
potom platí: slouží k přepočítávání souřadnic, pokud známe souřadnice vzhledem k jedné bázi (z Důkaz 11.4
Tedy Definice 11.4 Jsou-li
pak matici
a
báze v
,
nazýváme matice přechodu od báze
k bázi
74
.
do )
Tvrzení 11.5 Nechť Nechť a pak
a je matice přechodu od
je matice přechodu od je matice přechodu od
jsou báze v
.
k
k
k
Důkaz 11.5
z definice matice přechodu
Označme
matici přechodu od
k
Tedy Tvrzení 11.6 Matice přechodu
od báze
k bázi
je regulární a
Důkaz 11.6 Použijeme Tvrzení 11.5 na případ Označme matici přechodu od k Podle Tvrzení 11.5 je matice přechodu od tedy matice přechodu od
k
je matice přechodu od
k .
k
je
(jsou čtvercové, tedy regulární) Definice 11.5 Buď
lineární zobrazení,
Matice
se nazývá matice lineárního zobrazení
Je-li zobrazení
pak matici vzhledem k bázi
je báze v
zobrazení
je báze v
vzhledem k bázím
a .
vzhledem k bázím
a
a
nazýváme matice lineárního
.
Pozn.: Je-li lineární zobrazení určené maticí , pak ke standardní bázi (třeba ověřit z definice)
75
je maticí lineárního zobrazení
vzhledem
Tvrzení 11.7 Jsou-li báze v
potom
,
lineární zobrazení, báze v
,
báze v
matice lineárního zobrazení
vzhledem k bázím
a
matice lineárního zobrazení
vzhledem k bázím
a
je matice
vzhledem k bázím
a
Důkaz 11.7
Pozn.:
Tvrzení 11.8 Matice přechodu od báze vzhledem bázím a . Důkaz 11.8 Označme
Tedy
k bázi
matici přechodu od
je matice vzhledem k bázím
Tvrzení 11.9 Je-li je matice lineárního zobrazení je matice lineárního zobrazení pak
je prvek na místě
k
v
je maticí identického zobrazení
, potom
a
dvě báze v vzhledem k bázi vzhledem k bázi
matice přechodu od
k
Důkaz 11.9 pomocný obrázek:
je matice přechodu od k je matice lineárního zobrazení vzhledem k bázi je matice identického zobrazení vzhledem k bázím
; označme
a
76
(tedy matice přechodu od
k )
Přednáška 27 _ 11. 1 2012 to už tu psát nebudu prý je to náskok do dalšího semestru ;) (byla jedna definice) plus byly nějaké příklady praktického použití lingebry ;)
77
