Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35 Matfiz : LineárníAlgebra/ZkouškaLS2007

Matfiz: LineárníAlgebra/ZkouškaLS2007

Lineární algebra a optimalizace — zkouška LS 2007

Zkouška trvá přesně devadesát minut, což na množství příkladů není mnoho. Z maxima 60 bodů je třeba (aspoň 13. 6. to tak bylo) nějak 31 nebo 32, od 25 výše Kolman dozkušoval ústně, stejně tak na hranicích mezi jednotlivými známkami. Známky nebyly čteny nahlas, ale mám pocit, že to výrazná část lidí neudělala. Minulý semestr jsem v pohodě dostal jedničku, teď mám trojku a vím, že lépe bych to bez několika dní přípravy navíc nenapsal. Takže pozor na lingebru... — Adam

No, tak ja som mal síce trojku aj v zime, ale aj mne by tých pár dní navyše pomohlo. Podľa mňa to zase až také ťažké nebolo, akurát mi chýbali nejaké vedomosti, ktoré sa dajú nabifľovať...a to som už nestihol. Inak odporúčam si pozrieť teóriu o Lineárnom programovaní. Bolo tam toho aspoň za 15–20 bodov... Roman

To je pravda. Doporučuju pro začátek zkusit Tůmova skripta, má to tam bez zbytečných formalismů a srozumitelně (až na prvních pár motivačních odstavců, které navazují na předchozí kapitolu), a teprv až vás tohle osvítí, tak se vraťte k naší přednášce. Poměrně zákeřné mi připadá ptát se na cokoli co souvisí s dualitou LP, protože jsme si o tom mimo dvou nedokázaných vět mnoho neřekli, nicméně asi není těžké to nastudovat a téměř jistě na to jednu pětibodovou otázku dostanete. Za povšimnutí stojí ještě, že přes Kolmanovy výhrůžky tam nebylo nic ke skalárnímu součinu (i když, co není, může být...). — Adam

Poopravim poslednu Adamovu vetu, konkretne moja skupina(A) mala zistit, ci pre lub. A, ktora sa da rozlozit na U * U_transp predpis x_transp * A * y definuje skalarny sucin – bolo treba overit axiomy. Nic tazke, ale taketo lahke veci sa casto pri uceni podcenia. Inak moj dojem z pisomky? Myslim ze som priprave na skusku venoval viac nez hodne casu a aj tak som dostal trojku, pricom lepsie by som sa to uz asi nenaucil(a den pred skuskou som mal pocit ze celkom solidne tomu rozumiem). Tiez sa mi zda ze priklady su bodovane strasne prisne, miestami sa mi pri pohlade na pisomku zdalo ze body sa strhavaju aj za tie najmensie detaily. Takze vela stastia ostatnym — nardew

Dovolte mi také pár slov k písemce. Psal jsem 13. 6. zadání A a u druhého příkladu jsem poslední dva body prostě nestihnul. Vrátil jsem se k nim ale v poslední minutě a během ní jsem u obou příkladů pouze rychle teoreticky popsal, jak bych je řešil, kdyby mi zbyl čas a kdybych měl výsledky předešlých příkladů. No a ke svému vlastnímu překvapení jsem za jedinou větu «Lze to, musím vlastní vektory zortogonalizovat, ale už na to bohužel nemám čas.» dostal 2 body a za teoretický popis získání polární báze (vlastně jsem napsal kus důkazu Silvestrova zákonu setrvačnosti) celé 3 body! Takže jsem místo deseti bodů ztratil jenom pět… Díky tomu jsem od zkoušky odcházel s jedničkou, což jsem vůbec nečekal a což mě příjemně překvapilo. — Honza

Stará zadání 2005/6

Převztato od Ošklivého supa, odkaz na Kolmanově stránce nefunguje:

3. 7., varianta A

1. viz http://www.osklivy-sup.cz/mff/dok/zk-minula-kolman.pdf, zadani z 20. 6. 2006, skupina A

2. zadany matice A a B rozmeru 3x3 (zadany konkretni hodnoty)

a) najit vlastni cisla matic A a B

b) bez pocitani vlastnich vektoru urcit, jestli jsou A a B podobne, pokud neumime, tak si je muzeme spocitat

(vlastni cisla vysla, resp. mela vyjit :) stejna)

c) napsat presne zneni tvrzeni, co se uplatnuje pri odpovedi b), byla uvedena napoveda, ze se tyka diagonalizovatelnosti matic
3. neco z linearniho programovani, nejsem si jisty, jestli i nejaka prakticka uloha, spis ne

Je pravda, ze kdyz je uloha LP tvaru Ax<=b, x>=0, max ctx neomezena, tak existuje index i, ze {max xi} je neomezena? (ano)

asi jeste neco...

4. tri tvrzeni, ano/ne?

  1. ||v|| = 1, v je vlastni vektor matice A. Je pravda, ze...? Tvrzeni bylo neco ve stylu xTx * cosi – neco * neco_uplne_jineho_a_par_zavorek – I = 0, nemapatuju si, sorry, ale platilo to 
  2. nejaka kvadraticka forma na R2, urcit, zda je pozitivne definitni (nebyla)
  3. matice A = (2, 0 \n 1 5) ma Jordanovu matici (2 1 \n 0 5) (ihned je videt, ze ne, anzto to neni Jordanuv tvar)

13. 6., varianta B (aspoň myslím)

(Tak jak si to pamatuju, možná jsem jednu dvě věci vynechal/pozměnil, je to dost podobné starým zadáním výše — Adam)

  1. Kvadratické formy
    • Definice kvadratické formy, definice bilineární formy, definice matice kvadratické formy.
    • Sylvestrova věta o setrvačnosti kv. f. a důkaz aspoň jedné části.
  2. Vlastní čísla a vektory
    • Spočtěte vlastní čísla dvou matic 3x3.
    • Určete zda jsou podobné.
    • Spočtěte jejich vlastní vektory.
  3. Lineární programování
    • Úloha zadána jako Ax = b, převeďte ji do základní simplexové tabulky. (Tzn. vše se mělo udělat obecně, žádné konkrétní zadání).
    • Zapište odpovídající přípustné bázové řešení (tzn. opět obecně) a dokažte, že množina přípustných řešení je konvexní.
    • Zadejte co nejjednodušší neomezenou úlohu v R2 a přehledně graficky znázorněte.
    • Zkonstruujte k ní duální úlohu a řekněte něco o vztahu primární a duální úlohy (přesnou formulaci si nepamatuju).
  4. Rozhodněte a zdůvodněte
    • Úloha lineárního programování má jen (mn)2 bázových řešení, což zaručuje konečnost simplexového algoritmu. Ne, sice konečně mnoho, ale exponenciálně.
    • Jestliže A je podobná diagonální matici D, je podobná také matici D', která (následuje můj neformální popis) má na diagonále to samé, ale v obráceném pořadí.
    • Rovnoběžnostěn daný třemi vektory (...) má větší objem než rovnoběžnostěn daný třemi vektory (...).

13. 6., varianta A (napsal jsem, co si pamatuji, prosím ostatní o doplnění a opravení)

  1. Věta a důkaz
    • Napište větu o diagonizovatelnosti hermitovských matic. (5 bodů)
    Věřím, že zadání bylo “Definujte podobnost matic” — Honza

    • Napište a dokažte větu o diagonizovatelnosti reálných symetrických matic velikosti nxn s n různými vlastními čísly. (10 bodů)
    Alternativně bylo možno dokázat podobnou větu o hermitovských maticích, je to o pár kroků (jeden?) kratší... — Honza

  2. Vlastní čísla a vektory, kvadratická forma
    • Spočtěte vlastní čísla a vlastní vektory dané matice 3x3. (5 bodů)
    Doplním, že šlo o matici samých jedniček — Honza

    • Rozhodněte, zda lze najít tři různé vlastní vektory (k matici z minulé úlohy) tak, aby každé dva různé byly na sebe kolmé. (5 bodů)
    • Máte kvadratickou formu: f(x)=...nějak zadaná... Najděte její matici takovou, že je diagonální pouze s 1, -1, 0 na diagonále a napište bázi, vzhledem ke které má ta forma tuhle matici. (5 bodů)
    Forma byla zadaná v analytickém tvaru, ale měla tutéž matici, co předchozí příklady, takže na sebe výpočet navazoval — Honza

  3. Lineární programování
    • Definujte bázi, přípustnou bázi, přípustné bázické řešení. (5 bodů)
    • Jak najít výchozí bázické přípustné řešení úlohy Ax = b ? (5 bodů)
    • Zkonstruujte primární úlohu tak, aby neměla žádné přípustné řešení a aby příslušná duální úloha byla neomezená + nakreslit. (5 bodů)
  4. Rozhodněte a zdůvodněte
    • Mají-li dvě matice stejný charakteristický polynom, pak jsou podobné. (5 bodů)
    • Pokud existuje pro matici A rozklad A=UTU, pak tato matice definuje nějaký skalární součin f(x, y)=xTAy. (5 bodů)
    • Rovnoběžnostěn daný třemi vektory (...) má větší objem než rovnoběžnostěn daný třemi vektory (...). (5 bodů)
    Dovolím si pár poznámek k tomuto příkladu: — Honza

    • Na přednášce byla obrácená implikace a nikoliv ekvivalence, což je hint, že toto by nemělo fungovat. Je nutno najít protipříklad, což není těžké, víte-li, že Jordanův tvar až na pořadí buněk jednoznačně identifikuje třídy ekvivalence podobnosti. Nejlépe se to dokazuje na příkladu 2x2, kde jedna matice je jednotková a druhá taky, ale má v pravém horním rohu místo nuly jedničku. Tyto mají jistě stejný charakteristický polynom, ale jak se dá snadno dokázat, jednotková matice je podobná pouze sobě sama.
    • Zde není třeba ověřovat všechny axiomy skalárního součinu, pokud člověk zná něco o pozitivní semidefinitnosti. Kdyby byla U regulární, je A pozitivně definitní a podle věty na přednášce je zadaná funkce skalární součin. Chybí-li ale předpoklad regulárnosti U, je A pouze pozitivně semidefinitní a skutečně v případě singulární U existuje x nenulové takové, že f(x, x) = 0, a stačí vyvrátit jediný axiom. Nejjednodušší protipříklad je U = matice samých nul :-).
    • Objem se počítá přes determinanty, ale u tohoto konkrétního zadání si mohl člověk všimnout, že postavíme-li z obou sad vektorů matice, jsou tyto navzájem transponované, takže bylo možné odpovědět rovnou bez počítání, že jejich objem je stejný.

Martin

31.5.

Byli jsme tam tři.

Každý dostal téma na rozmyšlenou(já ortogonální bázi a ortogonalizaci, vedle jsem zaslech něco o diagonizovatelnosti, třetí člověk byl za rohem)

a pak jsme to postupně prezentovali. Když jsem se někde zasekl, tak mě dr. Kolman nechal si to rozmyslet, asi dvakrát mi dal menší hint(možná větší, já nevim).

Když jsme se dostali přes tohle, tak jsem ještě dostal jednu úlohu na LP(byla z těch starých písemek) a po úspěšném vyřešení jsem odcházel s výbornou v indexu.

Ale příště, až tam bude víc lidí, tak to asi bude vypadat jinak. tk

Jo a ještě jsme si popovídali o tom, co mě na lingebře bavilo a co ne a o tom, že jak jsme ty přednášky měli po tělocviku a po obědě, tak tam všichni spali.