Felsőbb matematika villamosmérnököknek - Haladó lineáris algebra (BMETE90MX54) 2016

Előadások

• Vektorok, egyenletrendszerek
• Mátrixok
• Determinánsok
• Lineáris leképezések (2016-03-22)
• Ortogonalizáció (2016-03-22)
• Sajátérték, sajátaltér, diagonalizálhatóság, kvadratikus alakok (2016-03-28)
• SVD (2016-04-11, előadás után frissítve)
• Jordan-féle normálalak (2016-04-26)
• Nemnegatív mátrixok (2016-04-18)
• Mátrixfüggvények (2016-04-26)
• Mátrixegyenletek (2016-05-10)

A készülő jegyzet (V.16-02-27) folyamatosan frissülő változata itt található.

Gyakorlatok

1. feladatsor (egyik, másik változat – minimális különbség)
2. feladatsor (itt),
3. feladatsor (itt),
4. feladatsor (itt),
5. feladatsor (itt),

Házi feladatok

Mindegyik feladat 1 pont, hacsak nincs a feladathoz írva valami más. A megoldásokat papíron kérjük, de végszükség esetén lehet a felsobb pont mat kukac gmail pont com címre is. Más megoldását lemásolni nem szabad!

1. feladat: Írjunk fel egy valós 4x5-ös mátrixot (véletlen nem 0-elemekkel), melynek rangja 3. Írjunk fel egy másik 4x5-ös 3-rangú mátrixot is, melynek elemei a 2-elemű testből valók (itt elég, ha minden sorban vannak nemnulla elemek). Határozzuk meg mindkét mátrix alapvető altereinek (azaz a sortér, az oszloptér, a nulltér és a transzponált nulltér) egy-egy bázisát.
   Határidő: 4. előadás kezdete, 2016-03-08 10:15
2. feladat: Írjunk fel egy 2 egyeneletből álló valós, konzisztens, 4-ismeretlenes (nem triviális) egyenletrendszert. Adjuk meg az összes megoldását az egyetlen sortérbe eső megoldás segítségével. A sorvektorok megfelelő lineáris kombinációjával igazoljuk (ellenőrizzük), hogy e megoldás valóban a sortérben van.
   Határidő: 4. előadás kezdete, 2016-03-08 10:15
3. feladat: Ön egy többfős társasággal hatalmas pénzösszeg tulajdonosa, melyet egy széfben tartanak. A széf kódja egy titkos 8-jegyű t szám, melyet egy program véletlenszerűen állított be, és úgy osztott meg Önök közt, hogy csak legalább 3 fő egyetértésével lehessen (a véletlen tippelésnél nagyobb eséllyel) kinyitni. Ehhez mindenki kap egy 8-jegyű számokból alló (X,Y) számpárt, ahol X mindenkinél a a születésének napja évszázad nélkül, valamint telefonszáma utolsó 2 jegye, azaz ÉÉHHNNTT, míg Y mindenkinél egy csak általa ismert szám (a számok első jegye is lehet 0). A t titok és minden személy (X,Y) párja eleget tesz egy t+aX+bX²=Y alakú egyenletnek, ahol a műveleteket az F_p testben kell elvégezni, a, b és t mindenki előtt ismeretlen, és ahol p = 99999989 (a legnagyobb 8-jegyű prím).
   X az Ön esetén is a saját születési és telefonadata szerinti szám, míg Y = 12345678. Két társával megegyeznek, hogy kinyitják a széfet. Az ő számpárjaik: (90091456,51636639) és (91101022,34626431). Melyik szám nyitja a széfet? (A számításokhoz tetszőleges pontosságú moduláris aritmetikát tudó programot érdemes használni. Bármely komputer algebra program, pl. Sage, Geogebra, Mathematica, Maple,... jó erre (a Sage a felhőben is fut, nem kell telepíteni, ezt ajánlanám első helyen: https://cloud.sagemath.com/), de még egyszerűbb online program is elég pl. http://ptrow.com/perl/calculator.pl vagy Wolfram Alpha).
   A feladatot bármilyen módszerrel megoldhatjuk, de attól függetlenül írjuk fel az együtthatómátrix, vagy annak transzponáltja LU-felbontását is (természetesen ezt is F_p-ben számolva).
   Határidő: 2016-03-22 10:15
4. Válasszon három lineárisan független 3-dimenziós vektort véletlenszerűen (a standard egységvektoroktól különbözőket), és írja föl annak a lineáris leképezésnek az A mátrixát, mely az első két vektor síkjára vetít a harmadik vektor mentén, és annak a leképezésnek a B mátrixát, mely az első vektor által kifeszített altérre (egynesre) vetít a másik két vektor által kifeszített sík mentén! Számításait ellenőrizze úgy, hogy
   1. kiszámítja egy mátrixszorzással a három választott vektor képét mindkét leképezés esetén,
   2. mindkét mátrixról ellenőrzi, hogy valóban egy vetítés mátrixa.
   (A számításokhoz használhat mátrix-alapú nyelvet, pl. Octave, Matlab)
   Határidő: 2016-03-29 10:15
5. Írja fel egy n-ismeretlenes (n > 3) és m egyenletből álló (m > n) ellentmondásos lineáris egyenletrendszer bővített mátrixát (véletlen együtthatókkal, teljes oszloprangú együtthatómátrxszal).
   1. Igazolja, hogy az együtthatómátrix teljes oszloprangú és hogy a bővített mátrix valóban ellentmondásos egyenletrendszerhez tartozik!
   2. Az együtthatómátrix pszeudoinverzének segítségével határozza meg az egyenletrendszer optimális megoldását!
   3. Legyen B az együtthatómátrix transzponáltja, és b egy tetszőleges n-dimenziós vektor. Írja fel a Bx = b egyenletrendszer összes megoldását az x = B⁺b + (I - B⁺B)y képlettel, ahol y tetszőleges vektor.
   4. Igazoljuk, hogy a fenti képlet valóban megadja az egyenletrendszer összes megoldását!
   A feladat numerikus részének megoldásához használjon mátrixalapú programot (Octave, Matlab) vagy CAS programot (Sage, Mathematica, Maple). (Az utolsó ponthoz útmutatás: mit tudunk B⁺B-ről és B nullterének kapcsolatáról?)
   Határidő: 2016-03-29 10:15
6. (Octave vagy Matlab használatával) Legyen A egy 6x5-ös véletlen mátrix. Tekintsük ezt egy 4-ismeretlenes, 6 egyenletből álló egyenletrendszer bővített mátrixának. (Ha valóban véletlen valós elemű a mátrix, akkor az egyenletrendszer 1 valószínűséggel inkonzisztens, lebegőpontos számok esetén 1-hez nagyon közeli valószínűséggel. Az inkonzisztencia ellenőrizhető a rref függvénnyel.) Számítsuk ki az együtthatómátrix QR-felbontását ([Q R]=qr(M,0), a 0 argumentum biztosítja, hogy Q 6x4-es szemiortogonális mátrix legyen), majd Q és R segítségével határozzuk meg az egyenletrendszer optimális megoldását! Ellenőrizzük az eredményt mátrixosztással és a pszeudoinverz kiszámításával is (\, pinv).
   Határidő: 2016-04-05 10:15
7. (Octave, Matlab vagy Sage használatával) Vegyen egy (saját) pixelformátumú szürkeárnyalatos fényképet és készítsen belőle egy mátrixot, melynek minden eleme a kép egy pontjának árnyalaltát adja meg (pl. Octave-ban és Matlabban az imread/imwrite paranccsal lehet beolvasni/kiírni, de van parancs a színesből szürkére való konverzióra is). Legyen e mátrix rangja r. Írja fel a mátrix szinguláris felbontását, majd abból készítsen két olyan kép-mátrixot, melyek egyikének 10, másikának r/2 (egész része) a rangja, és ,,legközelebb'' van az eredeti mátrixhoz (ez úgy számolható, hogy az első 10, illetve első r/2 tagját adja össze a szinguláris felbontás diadikus alakjának). Jelenítse meg e két képet az eredeti mellett. Ezután mindkét képre számítsa ki az elhagyott szinguláris értékek négyzetösszegének gyökét (ez fogja mérni a két mátrix távolságát Frobenius-normában), és adja meg a legnagyobb elhagyott szinguláris értéket (ez fogja mérni a két mátrix távolságát 2-normában – a norma fogalma a következő előadás anyaga, akkor fogjuk tisztázni ezek matematikai tartalmát). (Akinek van kedve, és színes nyomtatója, megteheti hogy a három színösszetevő mindegyikére elvégzi a szinguláris felbontást, majd a fenti eljárást, így három színes képet jelenít meg). (2 pont)
   Határidő: 2016-04-12 10:15
8. Adva van $n$ darab $m$-dimenziós $\mathbf{a}_i$ vektor. A belőlük képzett mátrix legyen $\mathbf{A}\in\mathbb{R}^{m\times n}$. Tegyük fel, hogy a vektorok átlaga a zérusvektor (ha nem, akkor vonjuk ki mindegyikből az átlagukat), azaz tegyük fel, hogy $$ \frac1n \sum_{i=1}^n \mathbf{a}_i=\mathbf0. $$ Vizualizáljuk ezt a ponthalmazt egy origón átmenő egyenesre való merőleges vetítéssel. Ha az egyenes irányvektora $\mathbf x$ egységvektor, akkor az $\mathbf{a}_i$ vektor vetületének koordinátája az egyenesen $\mathbf{a}_i^T\mathbf x$. Nyilván kevessé jó a vetítés, ha a vetületek nagyon közel kerülnek egymáshoz, ezért azt az egyenest keressük, melynél a vetületek szórása a lehető legnagyobb. E számok átlaga $$ M(\{\mathbf{a}_i^T\mathbf x: i=1,\dots,n\})= \frac1n \sum_{i=1}^n \mathbf{a}_i^T\mathbf x =\left(\frac1n \sum_{i=1}^n \mathbf{a}_i\right)^T\mathbf x =0, $$ (tapasztalati) szórásnégyzetük pedig $$ S^2(\{\mathbf{a}_i^T\mathbf x: i=1,\dots,n\})= \frac1n \sum_{i=1}^n \left(\mathbf{a}_i^T\mathbf x - M(\mathbf{a}_i^T\mathbf x)\right)^2= \frac1n \sum_{i=1}^n \left(\mathbf{a}_i^T\mathbf x \right)^2 =\frac1n \mathbf{x}^T\mathbf A \mathbf{A}^T\mathbf x= \frac1n \|\mathbf{A}^T\mathbf{x}\|_2^2. $$ Ennek maximuma megegyezik a $\frac1n \|\mathbf{A}^T\|_2^2$ értékkel (ld. az előadás anyagát). A feladat: (a fenti szöveg megértése, majd) egy véletlen mátrixhoz (pl. rand függvénnyel az Octave/Matlab programokban generált legalább 6 darab 5-dimenziós vektort adó mátrixhoz) keressük meg a legnagyobb szórást adó egyenes egységnyi irányvektorát, és vetítsük a vektorokat erre az egyenesre, majd írjuk ki a vetületül kapott számokat. A maximális szórást számoljuk ki 2-féleképp is. (2 pont)
   Határidő: 2016-04-19 10:15
9. 12 (vagy több, de páros sok) gyerek körben ül, egyikük kezében rejtve egy gyűrű. Egy gyermekdal ritmusára mindenki úgy tesz, mintha egyik szomszédja kezébe adná a gyűrűt. Külső szemlélő nem látja hol a gyűrű, és hogy ki, mikor, kinek adja. Tegyük fel, hogy minden játékos a szomszédjai iránti szimpátia fix mértéke szerinti valószínűséggel, véletlenül választva adja át a gyűrűt. Ha az $n$-edik pillanatban a gyűrű helyzetének valószínűségeloszlását a 12-dimenziós sztochasztikus $\mathbf{v}$ sorvektor írja le, akkor a következő pillanatban (a csere után) a $\mathbf{vP}$ vektor, ahol a $\mathbf P$ mátrix megadja, hogy ki milyen valószínűséggel kinek adja a gyűrűt. E mátrix (átmenetmátrix) alakja \[ \mathbf{P}= \begin{bmatrix} 0 &1-p_1&0 & 0 &\dots &0&p_1\\ p_2& 0 &1-p_2& 0 &\dots &0& 0\\ 0 & p_3& 0 & 1-p_3&\dots &0& 0\\ \vdots&\vdots&\vdots&\vdots&\dots&\vdots&\vdots\\ 1-p_n&0&0&0&\dots&p_n&0 \end{bmatrix} \] ahol $[\mathbf P]_{i,i-1}=p_i$, $[\mathbf P]_{i,i+1}=1-p_i$, és $p_i\in[0,1]$ ($i=1,2,\dots,n$) tetszőleges.
   (a) Generáljunk véletlen elemekkel egy ilyen $\mathbf P$ mátrixot és egy véletlen nemnegatív $\mathbf v$ vektort (legyen $\|\mathbf{v}\|_1=1$)! Milyen pozitivitási osztályba tartozik a $\mathbf P$ mátrix (primitív, reducibilis, irreducibilis)?
   (b) Vizsgáljuk meg a $\mathbf{vP}^n$ vektorok viselkedését, ha $n$ tart végtelenhez! Létezik-e e vektorsorozatnak határértéke vagy torlódási pontja? Létezik-e a $\mathbf{v}, \mathbf{vP},\dots, \mathbf{vP}^{k-1}$ vektorok átlagának határértéke? Mi ezek jelentése?
   (c) Mi történik a fenti értékekkel, ha a $p_i$ valószínűségek egyike 0, egy másika 1, vagyis ha van olyan játékos, aki mindig jobbra, és olyan is, aki mindig balra adja a gyűrűt? Magyarázzuk meg az eredményeket.
   (d) Határozzuk meg $\mathbf P$ Perron-vektorait! Mi köze van az előző eredményeknek a Perron-vektorokhoz?
   A kérdésekre több módon is válaszolhatunk: a mátrixszal való számolással szerzett tapasztalatok alapján, a játék viselkedéséből levont következtetések és az elmélet alapján. Ahol lehet, világítsuk meg az eredményeket minden oldalról, de tömören! (3 pont)
   Határidő: 2016-04-25 10:15
10. Vegyen egy legalább 10×10-es valós $\mathbf J$ Jordan-mátrixot, amelyben nincsenek 1×1-es Jordan-blokkok és melynek pontosan két különböző sajátértéke van, egyik pozitív, másik negatív. Legyen $\mathbf C$ egy $\mathbf J$-vel azonos méretű véletlen (tehát invertálható) valós mátrix, és legyen $\mathbf{A} = \mathbf{CJC}^{-1}$. (a) Írja fel $\mathbf{A}$ minimálpolinomját! (b) Írja fel az $e^{\mathbf{A}}$ kiszámításához használható Hermite-polinomot, majd számítsa ki vele $e^{\mathbf{A}}$ értékét! (c) Számítsa ki $e^{\mathbf{A}}$ értékét a $\mathbf{C}e^\mathbf{J}\mathbf{C}^{-1}$ mátrix kiszámításával. (d) Számítsa ki az $\mathbf{A}^{1/3}$ és a $\mathrm{sgn}(\mathbf{A})$ mátrixokat, ahol $\mathrm{sgn}$ az előjelfüggvény. Értelmezve volnának-e e függvények, ha az $\mathbf{A}$ egyik sajátértéke 0 lenne? (4 pont)
    Határidő: 2016-05-10 10:15
11. Válasszunk olyan véletlen egész elemű $\mathbf{A}_1$, $\mathbf{A}_2$, $\mathbf{B}_1$, $\mathbf{B}_2$, $\mathbf{C}$ mátrixokat, melyek egyike sem négyzetes, és az \[\mathbf{A}_1\mathbf{X}\mathbf{B}_1+ \mathbf{A}_2\mathbf{X}\mathbf{B}_2=\mathbf{C}\] egyenletben szereplő műveletek elvégezhetőek. (a) Oldjuk meg a fenti lineáris mátrixegyenletet (Octave/Sage/Matlab). (b) Válasszunk egy egészelemű $m\times m$-es $\mathbf{A}$ és egy egész elemű $n\times n$-es $\mathbf{B}$ mátrixot ($2 \lt m\neq n \gt 2$) úgy, hogy $\mathbf{A}$-nak és $-\mathbf{B}$-nek legyen legalább egy közös sajátértéke. Válasszunk úgy egy $\mathbf{C}$ mátrixot, hogy az \[\mathbf{A}\mathbf{X}+ \mathbf{X}\mathbf{B}=\mathbf{C}\] egyenletnek legyen végtelen sok megoldása (határozzuk meg), és egy másikat úgy, hogy ne legyen megoldása. (c) Igazoljuk, hogy ha az előző mátrixegyenlet (Sylvester-egyenlet) megoldható, akkor fennáll az alábbi hasonlóság: \[ \left[ \begin{array}{rr} \mathbf{A} & \mathbf{C}\\ \mathbf{O} &-\mathbf{B} \end{array} \right] \sim \left[ \begin{array}{rr} \mathbf{A} & \mathbf{O}\\ \mathbf{O}& -\mathbf{B} \end{array} \right]. \] (3 pont - Ez az utolsó házi feladat)
    Határidő: 2016-05-17 10:15

Eredmények

1. ZH

2016 március 29, kedd, 18:00-20:00. Terembeosztás a vezetéknév kezdőbetűje szerint:

• A-Men: E1B
• Mer-Z: STFNAGY

• Gyakorlati feladattípusok
  1. Lineáris kapcsolatok meghatározása elemi sorműveletekkel (függetlenség, bázis, bázisra vonatkozó koordináták, altér dimenziója, mátrix bázisfelbontása, egyenletrendszer megoldása, mátrix inverze)
  2. egyenletrendszer megoldása LU vagy PLU felbontással valós vagy véges test fölött
  3. valamely lineáris leképezés mátrixának fölírása, (vetítés altérre egy másik altér mentén, tükrözés, forgatás a térben, altérre való merőleges vetítés (7.29)
  4. adott bázisban megadott mátrixú lineáris leképezés mátrixának fölírása másik bázisban
  5. egyenletrendszer optimális megoldásainak meghatározása és a legkisebb abszolút értékű optimális megoldás meghatározása,
  
  
• Elméleti témák
  1. a négy kitüntetett altér, dimenziótétel, a lineáris algebra alaptétele
  2. az elemi sorműveletek hatása a sortérre és az oszloptérre
  3. egyenletrendszer megoldhatóságának mátrixrangos feltétele
  4. a megoldások tereinek jellemzése
  5. (egyik bázisról a másikra való) áttérés mátrixa
  6. invertálhatóság és az egyenletrendszerek kapcsolata (5.15)
  7. a determinánsfüggvény soronkénti linearitása, determináns és a mátrixműveletek kapcsolata, determináns értékének kiszámítása elemi sorműveletekkel, sor vagy oszlop szerinti kifejtéssel, kígyók determinánsainak összegére bontással
  8. mátrixleképezés, lineáris leképezés
  9. merőleges vetítés és a legjobb közelítés, a legjobb közelítés ONB esetén (7.71)
  10. polinomiális regresszió (7.55. példa)
  11. pszeudoinverz fogalma és a Moore-Penrose-tétel
  12. (szemi)ortogonális mátrixok, Givens-forgatás, Householder-tükrözés
  
  
• Bizonyítások
  1. Minden A: R^m → Rⁿ lineáris leképezéshez létezik olyan A mátrix, hogy minden x vektorra A(x) = Ax.
  2. Ortonormált vektorrendszer független.
  3. Ortogonális mátrix tulajdonságai
  
  

2. ZH

2016 május 3, kedd, 18:00-20:00, terem: E1B,STFNAGY - terembeosztás, mint az 1. ZH-n:

• A-Men: E1B
• Mer-Z: STFNAGY

• Gyakorlati feladattípusok
  1. altérben ortogonális (ortonormált) bázis keresése
  2. pszeudoinverz kiszámítása
  3. QR-felbontás kiszámítása
  4. egyenletrendszer legkisebb abszolút értékű optimális megoldásának meghatározása (1) az együtthatómátrix pszeudoinverzének kiszámításával, (2) a QR-felbontás fölhasználásával
  5. mátrix diagonalizálása, sajátfelbontásának és spektrálfelbontásának felírása
  6. mátrix ortogonális diagonalizálása
  7. szinguláris értékek, bal és jobb szinguláris vektorok, SVD, redukált SVD, SVD diadikus alakjának meghatározása
  8. vektor- és mátrixnormák kiszámítása
  9. mátrix (ir)reducibilitásának és primitívségének eldöntése (az előadás alapján)
  10. (A/r)^k határértékének kiszámítása a Perron-vektorokkal (az előadás alapján)
  
  
• Elméleti témák
  1. speciális mátrixok sajátértékei
  2. hasonlóság, diagonalizálhatóság, sajátalterek direkt összege és a diagonalizálhatóság (8.40)
  3. Gersgorin-körök
  4. Cayley–Hamilton-tétel
  5. ortogonális és unitér diagonalizálás (9.3, 9.9)
  6. Schur-felbontás
  7. kvadratikus formák, mátrixok definitsége
  8. szinguláris értékek és vektorok fogalma, kapcsolatuk a négy alapvető altérrel
  9. a szinguláris érték szerinti felbontás geometriai ,,jelentése''
  10. norma definíciója
  11. normák ekvivalenciája (R-ben és C-ben)
  12. mátrixnorma definíciója, indukált norma és ekvivalens alakjai
  13. Eckart–Young-tétel (kis rangú approximáció tétele)
  14. a szinguláris értékek kapcsolata a 2- és a Frobenius-normával
  15. alterek direkt összegére bontás és a blokkdiagonális mátrix kapcsolata
  16. általánosított sajátvektor, Jordan-lánc, Jordan-bázis fogalma
  17. f definiálva van az A spektrumán jelentése
  18. Perron-tételek pozitív mátrixokra
  19. Perron-vektorok
  20. Perron–Frobenius-tételek nemnegatív mátrixokra
  21. sztochasztikus és duplán sztochasztikus mátrix
  
  
• Bizonyítások:
  1. A szinguláris értékek létezése (A^HA hasonló Σ^HΣ-hoz, önadjungált, pozitív szemidefinit, ortogonálisan diagonalizálható)
  2. Polárfelbontás előállítása SVD-ből
  3. Pszeudoinverz előállítása SVD-ből

pót-ZH

2016 május 19, csütörtök, 18:00-20:00 (IB025,026,027)

2016 május 24, kedd, 12:00-14:00 (EIC)