K 10:15-12:00 (IB026)
Tartalomjegyzék
- Előadások
- Feladatsorok
- Házi feladatok
- 1. Lineáris leképezések (5 pont, határidő: 2020-03-24 24:00)
- 2. Az összes optimális megoldás (5 pont, határidő: 2020-04-09 24:00)
- 3. A főirány meghatározása (5 pont, határidő: 2020-05-12 24:00)
- 4. Lineáris mátrixegyenlet megoldása (5 pont, határidő: 2020-05-19 24:00)
- ZH, konzultáció, ZH-követelmények
Előadások
- Matlab/Octave: mint lineáris algebra kalkulátor (txt V.03-29)
- Elemi sorműveletek (V.02-10)
- Algebrai struktúrák, lineáris leképezések (V.02-25)
- Euklideszi terek (V.03.03)
- Ortogonalitás (V.03-24)
- Diagonalizálhatóság (V.04-03)
- SVD, norma (V.04.17)
- Jordan-féle normálalak, mátrixfüggvények (V.04-28)
- Nemnegatív mátrixok (V.05-03)
- Lineáris mátrixegyenletek
- Lineáris programozás
- Néhány alkalmazás
Feladatsorok
- Elemi sorműveletek, eredmények (V.04-07)
- Vektorterek, lineáris leképezések, megoldások (V.04-07)
- Ortogonalitás, megoldások
- Diagonalizálás, SVD, megoldások
- Norma, Jordan-alak, mátrixfv., pozitív mátrix, mátrixegyenlet, megoldások
Házi feladatok
A házi feladatokat a megadott időpontban az előadáson lehet beadni, vagy az előtt be lehet dobni a H. épület V. emeleti liftajtó mellett 30cm-re lévő postaládába.
1. HF: Lineáris leképezések (5 pont, határidő: 2020-03-24 kedd 24:00)
Jelölje a legföljebb harmadfokú polinomok vektorterét \(\mathcal P\). Tegyük fel, hogy egy \(\mathcal P\)-beli \(p\) polinommal leírható mennyiségre végzünk ,,pontos'' mérést az egymástól páronként különböző \(x_0,x_1,x_2,x_3\) helyeken. Gondoljuk meg, hogy a \((p(x_0),p(x_1),p(x_2),p(x_3))\in\mathbb R^4\) vektorhoz a \(p\in\mathcal P\) polinomot rendelő leképezés lineáris! Minket azonban nem is maga a polinom érdekel, hanem csak a \(p'(0)\), az \(\int_0^1p(x)\,\mathrm dx\), és az \(\int_{-1}^1p(x)\,\mathrm dx\) értékek. Tehát a \[ (p(x_0),p(x_1),p(x_2),p(x_3)) \mapsto \left(p'(0),\int_0^1p(x)\,\mathrm dx, \int_{-1}^1p(x)\,\mathrm dx\right) \] leképezést szeretnénk megadni minél egyszerűbben.
- Adjunk tömör indoklást arra, hogy e leképezés lineáris!
- Mivel e leképezés lineáris, így megadható egy mátrixszal való szorzással. Válasszunk konkrét \(x_i\) értékeket (csupa különbözőt!), és határozzuk meg e mátrixot. (Aki e feladatot programmal oldja meg, válasszon nem egész \(x_i\) értékeket.)
- Számításainkat ellenőrizzük a \(p_1(x)=x^3-x^2+x-1\) és a \(p_2(x)=1\) polinomból számolt értékekkel.
2. Az összes optimális megoldás (5 pont, határidő: 2020-04-10 0:00)
Írjuk fel (számítógéppel generáljuk) 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átrixszal.
- Az \(\mathbf A\) együtthatómátrix (a) pszeudoinverzének valamint (b) QR-felbontásának segítségével határozzuk meg az egyenletrendszer optimális megoldását! (Itt elég a megfelelő függvények hívása.)
- Legyen \(\mathbf B = \mathbf A^T\), azaz az együtthatómátrix transzponáltja, és \(\mathbf b\) egy tetszőleges \(n\)-dimenziós vektor. Írjuk fel a \(\mathbf{Bx} = \mathbf b\) egyenletrendszer összes megoldását az \(\mathbf x=\mathbf B^+\mathbf b+(\mathbf I-\mathbf B^+\mathbf B)\mathbf y\) képlettel, ahol \(\mathbf y\) tetszőleges vektor.
- Igazoljuk, hogy a fenti képlet (a) valóban megoldás, (b) megadja az egyenletrendszer összes megoldását! (c) Az igazolt részállítást ellenőrizzük a megadott mátrixokon!
A feladat numerikus részének megoldásához használjunk mátrixalapú programot (Octave, Matlab). Az utolsó ponthoz útmutatás: mit tudunk \(\mathbf B^+\mathbf B\)-ről és \(\mathbf B\) nullterének kapcsolatáról?
3. A főirány megkeresése (5 pont, határidő: 2020-05-12 kedd)
Sok olyan alkalmazás van, melyben a valóság bizonyos dolgait $n$ paraméterrel jellemezzük, azaz egy $n$-dimenziós vektorral. Keressük azt az irányt, amely mentén haladva a legjobban szét tudjuk választani és sorba tudjuk rendezni a pontokat.
Adva van $m$ darab $n$-dimenziós $\mathbf{a}_i$ vektor. A belőlük mint sorvektorokból képzett mátrix legyen $\mathbf{A}\in\mathbb{R}^{m\times n}$. Generáljuk a vektorokat véletlenszerűen, többdimenziós normális eloszlás szerint. Ehhez használjuk a Matlab (Octave-ban statistics csomag) A = mvnrnd(mu,C,m) parancsát, ahol mu a várható érték vektora (itt bármilyen $n$-dimenziós vekor lehet), C a kovarianciamátrix, ami egy $n\times n$-es pozitív szemidefinit mátrix (ilyet konstruálhatunk egy véletlen $X$ mátrixból is az $X^TX$ formulával, de más módszert is kitalálhatunk). Vonjuk ki mindegyik vektorból a vektorok átlagát, hogy így \[ \frac1m \sum_{i=1}^m \mathbf{a}_i=\mathbf0\] legyen. Első feladatként legyen $n=2$, és ábrázoljuk e pontokat a plot függvény segítségével úgy, hogy a tengelyeken (axis) a skálázás azonos legyen (equal). Keressük azt az egyenest, melynek az egységnyi $\mathbf x$ az irányvektora, és amelyre merőlegesen vetítve a vektorokat, azokat a legjobban szét tudjuk választani, a legjobban sorba tudjuk rendezni, azaz ahol a vetületek szórása a lehető legnagyobb. A merőleges vetületeket a $\mathbf{a}_i\cdot\mathbf{x}$ skalárszorzatok adják. E számok átlaga (tapasztalati várható értéke) \[ M(\{\mathbf{a}_i\cdot\mathbf{x}: i=1,\dots,m\})= \frac1m \sum_{i=1}^m \mathbf{a}_i\cdot\mathbf x =\left(\frac1m \sum_{i=1}^m \mathbf{a}_i\right)\cdot\mathbf x =0, \] (korrigált tapasztalati) szórásnégyzete pedig \[ s^2(\{\mathbf{a}_i\cdot\mathbf x: i=1,\dots,m\})= \frac1{m-1} \sum_{i=1}^m \left(\mathbf{a}_i\cdot\mathbf x - M(\mathbf{a}_i\cdot\mathbf x)\right)^2= \frac1{m-1} \sum_{i=1}^m\left(\mathbf{a}_i\cdot\mathbf x \right)^2 =\frac1{m-1} \mathbf{x}^T\mathbf{A}^T\mathbf{A}\mathbf x = \frac1{m-1} \|\mathbf{A}\mathbf{x}\|_2^2. \] Ennek maximuma megegyezik az $\frac1{m-1} \|\mathbf{A}\|_2^2$ értékkel (ld. az előadás anyagát).
A feladat:
- Generáljunk a fent leírt módon $m\ge100$ darab $n=2$ dimenziós sorvektort, normális eloszlással, melyek átlaga a $(0,0)$ vektor, majd ábrázoljuk a ponthalmazt.
- Az SVD-ről tanultak alapján határozzuk meg azt az irányt, melynek egyenesére eső vetületi pontok szórása a legnagyobb, és nyomtassuk ki e vektort.
- Hogyan számolható ki e maximális szórásnégyzet az std, norm, svd függvényekkel?
- Ismételjük meg a fentieket legalább $5$-dimenziós vektorokkal (irány, szórásnégyzet, kivéve az ábrázolást).
- A programkód tömör áttekinthető részét, az ábrát, valamint a tömör magyarázatokat mentsük egy fájlba (pdf, esetleg Word), ezt töltsük fel.
4. Lineáris mátrixegyenlet (5 pont, határidő: 2020-05-19 kedd 24:00)
- 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. Oldjuk meg a fenti lineáris mátrixegyenletet a tanult módszerrel (a részletszámításokat Matlab/Octave segítségével).
- 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.
- 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]. \] (Segítség: a hasonlóság igazolásához fölhasználható az egyenlet $X$ megoldása).
ZH, konzultáció
- 1. ZH: 2020-04-07, kedd 18-20 (megoldás)
- 2. ZH: 2020-05-14, csütörtök 18-20 (megoldás)
- pótZH: 2020-05-26, kedd pótlási hét
- pótpót: 2020-06-04, csütörtök 1. vizsgahét
1. ZH követelményei
Az alább kiemelt gyakorlati feladattípusok közül lesz kiválasztva a kérdések nagyobb része, de más típus is lehetséges. Felkészülésül a kiadott három feladatsor feladatainak megoldását ajánljuk, az online feladatok közül elsősorban a vastag betűvel kiemelteket. Az elméleti kérdések teszt-jellegűek lesznek. Gyakorlásként érdemes megoldani az online tananyag elméleti tesztkérdéseit. Azok azonnal ki is értékelődnek. De röviden összefoglaljuk azokat az alapfogalmakat, amelyek ismeretének számonkérése a elméleti kérdések legnagyobb részét kiteszi.
A ZH elején a hallgatónak vállalnia kell, hogy semmilyen kommunikációs csatornát nem nyit meg a ZH ideje alatt, így semmilyen módon nem osztja meg saját munkáját, eredményeit, és nem használja fel másokét. A munka közben az eredmények/részeredmények ellenőrzésére használható mátrixalapú program, sőt ezt bátorítjuk.
- Kiemelt gyakorlati alap-feladattípusok:
- Elemi sorműveletek alkalmazása (pl. függetlenség, bázis, bázisra vonatkozó koordináták, altér dimenziója, bázisfelbontás),
- adott bázisban megadott mátrixú lineáris leképezés mátrixának fölírása másik bázisban, az áttérés mátrixának használata
- egyenletrendszer összes megoldása, ill. optimális megoldása a sortérbe eső megoldással a normálegyenletből, a pszeudoinverzzel, a QR-, az LU-, a PLU-felbontással)
- valamely lineáris leképezés mátrixának fölírása, (pl. 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)
- Fontosabb elméleti témák:
- a négy kitüntetett altér, a dimenziótétel, a lineáris algebra alaptétele
- az elemi sorműveletek hatása a sortérre és az oszloptérre
- egyenletrendszer megoldhatóságának mátrixrangos feltétele
- a megoldások tereinek jellemzése
- invertálhatóság és az egyenletrendszerek kapcsolata
- lineáris vektortér és euklideszi tér definíciója, izomorfizmus \({\mathbb F}^n\)-nel
- mátrixleképezés, lineáris leképezés
- merőleges vetítés és a legjobb közelítés, Gram-mátrix, a legjobb közelítés ONB esetén
- polinomiális regresszió
- pszeudoinverz fogalma, tulajdonságai és a Moore-Penrose-tétel
- (szemi)ortogonális mátrixok, Givens-forgatás, Householder-tükrözés
- ortogonalizáció, QR-felbontás
- szimmetrikus, ferdén szimmetrikus, ortogonális, nilpotens, önadjungált, ferdén önadjungált, unitér és normális mátrixok fogalma
2. ZH követelményei
- Kiemelt gyakorlati alap-feladattípusok:
- saját- és spektrálfelbontás, és abból mátrixhatvány számítás, ortogonális (unitér) diagonalizáció, főtengelytranszformáció
- teljes és redukált SVD és abból pszeudoinverz, polárfelbontás és legjobb $k$-rangú közelítés számítása
- a Jordan-normálalak meghatározása az $\mathbf A-\lambda\mathbf I$-re vonatkozó ismeretekből, minimálpolinom felírása
- mátrixfüggvény (pl. $e^{tA}$) a Jordan-alakból vagy az Hermite-polinomból, homogén diffegyenletrendszer megoldása
- vektornormák ($p$-norma, $p=1,2,\infty$), mátrixnormák (Frobenius-, 1, 2, $\infty$) kiszámítása
- mátrix primitív, (ir)reducibilis voltának meghatározása, mátrixhatvány (vagy átlaguk) határértéke
- Fontosabb elméleti témák:
- mátrixfaktorizációk: spektrál-, Cholesky-, Schur-, szinguláris érték szerinti, Jordan-felbontás
- bilineáris függvény mátrixa, kongruens mátrixok, szimmetrikus mátrix tehetetlensége, Sylvester-tétel
- kvadratikus alak és jellegének (definitségének) meghatározása a definíció, a sajátértékek, egy csak négyzetes tagokat tartalmazó alakja vagy a minorai segítségével
- pozitív (szemi)definit mátrix faktorizációi (${\mathbf B}^2$, ${\mathbf C}^T{\mathbf C}$, Cholesky)
- szinguláris érték, jobb és bal szinguláris vektor, szinguláris felbontás és geometriai interpretációja, pszeudoinverz, polárfelbontás, kis rangú approximáció (Eckart–Young-tétel) SVD-ből
- vektornorma és ekvivalenciájuk, mátrixnorma, indukált norma
- invariáns altér, általánosított sajátvektor, Jordan-bázis
- Jordan-normálalak, minimálpolinom és tulajdonságai
- mátrix spektrumán definiált függvény, mátrixfüggvény Jordan-alakból és Hermite-polinomból
- nemnegatív mátrixok: pozitív, primitív, irreducibilis, reducibilis
- Perron- és Perron–Frobenius-tételek, a tételbeli mátrixhatványok kiszámítása, reducibilitás és primitívség eldöntése
- sztochasztikus mátrixok, Frobenius–Kőnig-tétel, Markov-láncok, stacionárius vektor
- vec függvény, Kronecker-szorzat, lineáris mátrixegyenlet megoldása egyenletrendszerre való visszavezetéssel