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

Oktató: 
Tantárgy követelmény: 
Kurzus típus: 
Elmélet
Nyelv: 
magyar
Félév: 
2019/20/2
Órarendi információ: 

K 10:15-12:00 (IB026)

Tartalomjegyzék

Előadások

  1. Matlab/Octave: mint lineáris algebra kalkulátor (txt V.03-29)
  2. Elemi sorműveletek (V.02-10)
  3. Algebrai struktúrák, lineáris leképezések (V.02-25)
  4. Euklideszi terek (V.03.03)
  5. Ortogonalitás (V.03-24)
  6. Diagonalizálhatóság (V.04-03)
  7. SVD, norma (V.04.17)
  8. Jordan-féle normálalak, mátrixfüggvények (V.04-28)
  9. Nemnegatív mátrixok (V.05-03)
  10. Lineáris mátrixegyenletek
  11. Lineáris programozás
  12. Néhány alkalmazás

Feladatsorok

  1. Elemi sorműveletek, eredmények (V.04-07)
  2. Vektorterek, lineáris leképezések, megoldások (V.04-07)
  3. Ortogonalitás, megoldások
  4. Diagonalizálás, SVD, megoldások
  5. 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.

  1. 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.)
  2. 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.
  3. 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)

  1. 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).
  2. 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.
  3. 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:
    1. Elemi sorműveletek alkalmazása (pl. függetlenség, bázis, bázisra vonatkozó koordináták, altér dimenziója, bázisfelbontás),
    2. 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
    3. 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)
    4. 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:
    1. a négy kitüntetett altér, a 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. invertálhatóság és az egyenletrendszerek kapcsolata
    6. lineáris vektortér és euklideszi tér definíciója, izomorfizmus \({\mathbb F}^n\)-nel
    7. mátrixleképezés, lineáris leképezés
    8. merőleges vetítés és a legjobb közelítés, Gram-mátrix, a legjobb közelítés ONB esetén
    9. polinomiális regresszió
    10. pszeudoinverz fogalma, tulajdonságai és a Moore-Penrose-tétel
    11. (szemi)ortogonális mátrixok, Givens-forgatás, Householder-tükrözés
    12. ortogonalizáció, QR-felbontás
    13. 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