Egyenletrendszerek optimális megoldása, pszeudoinverz
Ellentmondó egyenletrendszerek optimális megoldása
Ha egy egyenletrendszernek nincs megoldása, akkor az optimális megoldás megadja a legjobb közelítést.
Az $A\underline{x}=\underline{b}$ egyenletrendszer optimális megoldásai megegyeznek az
\( A^T \cdot A\underline{x} = A^T \cdot \underline{b} \)
egyenletrendszer megoldásaival.
Gauss-féle normálegyenlet
Az $A\underline{x}=\underline{b}$ egyenletrendszer Gauss-féle normálegyenlete:
\( A^T \cdot A\underline{x} = A^T \cdot \underline{b} \)
Legjobb közelítés
Egy $\underline{b}$ vektort nem csak merőlegesen vetíthetjük, hanem ferdén is. Viszont egyedül a merőleges vetítés rendelkezik a legjobb közelítés tulajdonságával.
A $\underline{b}$ vektor legjobb közelítése a $W$ altérben egy olyan $\underline{b}'$ vektor, amire $ \mid \underline{b} - \underline{b}' \mid$ minimális.
Lineáris regresszió a lineáris algebrában
Az $x$ és $y$ változó közötti kapcsolat meghatározásához méréseket végzünk.
Az $x_1$, $x_2$, ..., és $x_n$ értékekhez...
Az $y_1$, $y_2$, ..., és $y_n$ értékek tartoznak.
Keressük az a lineáris függvényt, amely a lehető legjobban illeszkedik a mérési pontokra.
Éppen itt is van.
$y=b_1\cdot x + b_0$
A függvény garfikonja akkor illeszkedik a legjobban a mérési pontokra, ha ezek az egyenletek egyszerre teljesülnek:
\( b_1 \cdot \sum_{i=1}^{n} x_i^2 + b_0 \cdot \sum_{i=1}^{n} x_i = \sum_{i=1}^{n} x_i \cdot y_i \)
\( b_1 \cdot \sum_{i=1}^{n} x_i + b_0 \cdot n = \sum_{i=1}^{n} y_i \)
Ezeket az egyenleteket normálegyenleteknek nevezzük.
Moore-Penrose pszeudoinverz
Az $A$ mátrix Moore-Penrose-féle pszeudoinverze egy olyan $A^{*}$ mátrix, amely ezt a négy dolgot tudja:
1) $AA^{+}A=A$
2) $A^{+}AA^{+}=A^{+}$
3) $\left( AA^{+} \right)^T = A A^{+}$
4) $ \left( A^{+}A \right)^T = A^{+} A $
Van egy nagyon ravasz dolog, amire a merőleges vetítéseket használhatjuk.
A vetítés működik síkban is…
És működik térben is.
Sőt, tovább általánosítható egy V vektortérben bármilyen W altérre.
Hogyha az A mátrix oszlopvektorai W-nek egy bázisát alkotják, akkor a W altérre történő merőleges vetítés mátrixa:
Itt van például ez a sík:
Ez a sík a háromdimenziós térben egy kétdimenziós altér.
És itt van a síkban két vektor.
Ez a két vektor a síknak egy bázisa.
Berakjuk most szépen őket ebbe az A mátrixba…
És egy kis számolással meg is van a merőleges vetítés mátrixa.
A ravasz dolog pedig most jön.
Itt van ez az egyenletrendszer…
Az egyenletrendszer együttható-vektorai mind ugyanabban a síkban helyezkednek el.
A jobb oldalon álló vektor viszont…
Na, az nincs benne ebben a síkban.
Így hát aztán nem meglepő, hogy az a1, a2 és a3 vektorok lineáris kombinációjával…
A b vektor nem állítható elő.
Vagyis az egyenletrendszer nem megoldható.
Az, hogy ez az egyenletrendszer nem megoldható, még nem nagy tragédia.
Gyakran vannak azonban olyan helyzetek, amikor valamilyen gazdasági vagy mérnöki probléma megoldása közben az ismeretlen mennyiségek meghatározására méréseket végzünk.
Az elkerülhetetlen mérési hibák pedig ellentmondó egyenletrendszerre vezetnek.
Vajon hogyan határozható meg a valóságban egészen biztosan létező megoldás, ezekből az ellentmondásos, tehát nem megoldható egyenletrendszerekből?
A gondot az okozza, hogy az egyenletrendszer együttható-vektorai által kifeszített altérben a b vektor nincsen benne.
Ettől ellentmondásos az egyenletrendszer és ezért nincs megoldása.
Hogyha a gondot az okozza, hogy a b vektor nincs benne az együttható-vektorok által kifeszített altérben…
Hát vetítsük bele, és minden rendbe is jön.
Ezzel a ravasz megoldással intézhetjük el azokat az egyenletrendszereket, amelyek elsőre nem megoldhatók.
Belevetítjük az együttható-vektorok síkjába a b vektort…
És most már a jobb oldalon álló vektor is ugyanabban a síkban van.
Ezt az egyenletrendszert bármelyik szokásos módszerrel megoldhatjuk.
Az elemi bázistranszformációval vagy a Gauss-eliminációval is.
Hogyha ezt a megoldást most behelyettesítjük az eredeti egyenletrendszerbe…
Akkor nem egészen fog stimmelni.
A kapott megoldás tehát nem pontosan az eredeti egyenletrendszer megoldása…
Ne feledkezzünk meg ugyanis arról az apróságról, hogy az eredeti egyenletrendszernek egyáltalán nincs is megoldása.
Amit így kaptunk nem más, mint az eredeti egyenletrendszer optimális megoldása.
Olyankor, amikor az eredeti egyenletrendszer megoldható, az optimális megoldás egybeesik a valódi megoldással.
Abban az esetben pedig, amikor egyébként nincs megoldás…
Nos, olyankor az optimális megoldás adja a megoldás legjobb közelítését.
Egyetlen kis gond van csak ezzel.
Az, hogy túl sokat kellett számolni.
De itt jön egy őrülten jó trükk, és hopp, egy pillanat alatt megkapjuk ugyanezt.
Az 
egyenletrendszer optimális megoldásai megegyeznek az
egyenletrendszer megoldásaival.
Hát, ez valóban elég barátságosnak tűnik.
Próbáljuk is ki.
Nem kell mást tennünk, mint az egyenletrendszer együtthatómátrixát transzponálni…
És a transzponáltat megszorozni az A mátrixszal …
Meg a b vektorral.
Ennek a megoldásai lesznek az eredeti egyenletrendszer optimális megoldásai.
Hát igen, valóban ugyanaz jött ki így is.
Rögtön folytatjuk…
Van egy nagyon ravasz dolog, amire a merőleges vetítéseket használhatjuk.
A vetítés működik síkban is…
És működik térben is.
Sőt, tovább általánosítható egy V vektortérben bármilyen W altérre.
Hogyha az A mátrix oszlopvektorai W-nek egy bázisát alkotják, akkor a W altérre történő merőleges vetítés mátrixa:
Itt van például ez a sík:
Ez a sík a háromdimenziós térben egy kétdimenziós altér.
És itt van a síkban két vektor.
Ez a két vektor a síknak egy bázisa.
Berakjuk most szépen őket ebbe az A mátrixba…
És egy kis számolással meg is van a merőleges vetítés mátrixa.
A ravasz dolog pedig most jön.
Itt van ez az egyenletrendszer…
Az egyenletrendszer együttható-vektorai mind ugyanabban a síkban helyezkednek el.
A jobb oldalon álló vektor viszont…
Na, az nincs benne ebben a síkban.
Így hát aztán nem meglepő, hogy az a1, a2 és a3 vektorok lineáris kombinációjával…
A b vektor nem állítható elő.
Vagyis az egyenletrendszer nem megoldható.
Az, hogy ez az egyenletrendszer nem megoldható, még nem nagy tragédia.
Gyakran vannak azonban olyan helyzetek, amikor valamilyen gazdasági vagy mérnöki probléma megoldása közben az ismeretlen mennyiségek meghatározására méréseket végzünk.
Az elkerülhetetlen mérési hibák pedig ellentmondó egyenletrendszerre vezetnek.
Vajon hogyan határozható meg a valóságban egészen biztosan létező megoldás, ezekből az ellentmondásos, tehát nem megoldható egyenletrendszerekből?
A gondot az okozza, hogy az egyenletrendszer együttható-vektorai által kifeszített altérben a b vektor nincsen benne.
Ettől ellentmondásos az egyenletrendszer és ezért nincs megoldása.
Hogyha a gondot az okozza, hogy a b vektor nincs benne az együttható-vektorok által kifeszített altérben…
Hát vetítsük bele, és minden rendbe is jön.
Ezzel a ravasz megoldással intézhetjük el azokat az egyenletrendszereket, amelyek elsőre nem megoldhatók.
Belevetítjük az együttható-vektorok síkjába a b vektort…
És most már a jobb oldalon álló vektor is ugyanabban a síkban van.
Ezt az egyenletrendszert bármelyik szokásos módszerrel megoldhatjuk.
Az elemi bázistranszformációval vagy a Gauss-eliminációval is.
Hogyha ezt a megoldást most behelyettesítjük az eredeti egyenletrendszerbe…
Akkor nem egészen fog stimmelni.
A kapott megoldás tehát nem pontosan az eredeti egyenletrendszer megoldása…
Ne feledkezzünk meg ugyanis arról az apróságról, hogy az eredeti egyenletrendszernek egyáltalán nincs is megoldása.
Amit így kaptunk nem más, mint az eredeti egyenletrendszer optimális megoldása.
Olyankor, amikor az eredeti egyenletrendszer megoldható, az optimális megoldás egybeesik a valódi megoldással.
Abban az esetben pedig, amikor egyébként nincs megoldás…
Nos, olyankor az optimális megoldás adja a megoldás legjobb közelítését.
Egyetlen kis gond van csak ezzel.
Az, hogy túl sokat kellett számolni.
De itt jön egy őrülten jó trükk, és hopp, egy pillanat alatt megkapjuk ugyanezt.
Az egyenletrendszer optimális megoldásai megegyeznek az
egyenletrendszer megoldásaival.
Hát, ez valóban elég barátságosnak tűnik.
Próbáljuk is ki.
Nem kell mást tennünk, mint az egyenletrendszer együtthatómátrixát transzponálni…
És a transzponáltat megszorozni az A mátrixszal …
Meg a b vektorral.
Ennek a megoldásai lesznek az eredeti egyenletrendszer optimális megoldásai.
Hát igen, valóban ugyanaz jött ki így is.
Rögtön folytatjuk…
Az egyenletrendszereknél tartottunk…
Annyit már tudunk, hogyha van egy olyan egyenletrendszer, ami ellentmondásos…
Akkor még azért van remény a megoldásra.
Ennek az egyenletrendszernek az együttható-vektorai…
Egy síkot feszítenek ki.
Egy olyan síkot, amiben a b vektor nincsen benne…
A b vektor tehát egészen biztosan nem áll elő az a1 a2 és a3 vektorok lineáris kombinációjaként.
Így hát az egyenletrendszer nem megoldható.
De ha belevetítjük a b vektort az együttható-vektorok által kifeszített síkba…
Akkor már igen.
Nem kell mást tennünk, mint ezt a másik egyenletrendszert megoldanunk, amit egyébként Gauss-féle normálegyenletnek nevezünk.
Ez pedig már egy szokásos egyenletrendszer, amit mondjuk Gauss-eliminációval szépen megoldunk.
Bár ez a megoldás is ugyanolyan három koordinátás vektor, mint a többiek…
Így hát ez a vektor sehol sem látható az ábrán.
De van itt még egy vicces dolog.
Keressük meg azt a megoldást, amire teljesül, hogy minimális.
Ez nem akkor van, amikor t nulla.
Hanem akkor, amikor ide…
Beírjuk ezeket a koordinátákat.
És így kiszámoljuk x3 értékét.
Meg is van a legkisebb abszolútértékű megoldás.
És itt jön még egy dolog.
A b vektort nem csak merőlegesen vetíthetjük, hanem ferdén is…
Viszont egyedül a merőleges vetítés rendelkezik a legjobb közelítés tulajdonságával.
A vektor legjobb közelítése a W altérben egy olyan vektor, amire minimális.
Mindjárt ki fog derülni, hogy a legjobb közelítés mindig a merőleges vetítés.
Legyen a V vektortérből a W altérbe történő merőleges vetítés mátrixa P.
Így hát a vektor W-re eső merőleges vetülete .
A vektornak a W-re eső valamilyen ferde vetülete pedig .
Lehet ez a W altér akár százdimenziós is, és vektorok mindig egy síkot feszítenek ki.
Mivel a BC szakasz merőleges erre a síkra, így merőleges a síkban fekvő minden szakaszra is.
Tehát merőleges AC-re is.
Így aztán ACB egy derékszögű háromszög, amiben BC egy befogó, AB pedig az átfogó, vagyis
Ez pedig azt jelenti, hogy valóban a legjobb közelítés.
A vektor legjobb közelítése a W altérben egy olyan vektor, amire minimális.
Az egyenletrendszereknél tartottunk…
Annyit már tudunk, hogyha van egy olyan egyenletrendszer, ami ellentmondásos…
Nagyon sok módszer van, amivel egy fának az életkorát meg tudjuk határozni.
Az egyik ilyen módszer, hogy kivágjuk, és megszámoljuk szépen az évgyűrűket.
A módszer előnye, hogy rendkívül pontos, hátránya viszont az, hogy ártalmas a fának.
Kevésbé ártalmas, amikor egy fúróval, amit egyébként Pressler-fúrónak hívnak, átfúrják a fa törzsét és mintát vesznek belőle, amin aztán meg lehet számolni az évgyűrűket.
Valószínűleg ezért a módszerért sem rajonganak a fák, de kisebb károsodással meg lehet állapítani, hogy ez a mamutfenyő, aminek a törzskerülete 28 méter, 3210 éves.
Törzskerület (m)
Életkor (év)
Ez a másik mamutfenyő pedig 1268 éves, és a törzsének a kerülete 12 méter.
És itt van még további három.
Az öt fán végzett mérési adatokat arra fogjuk használni, hogy készítünk belőlük egy függvényt.
Egy olyan függvényt, amely bármelyik mamutfenyő törzsének kerületéből képes megmondani a fa életkorát.
Ez a függvény egy lineáris függvény...
Éppen itt is van.
Hogyha ránk tör néhány régi emlék az általános iskolából…
És épp a lineáris függvény is köztük van…
Akkor tudjuk, hogy már két pont is elegendő a koordinátarendszerben ahhoz, hogy a lineáris függvény képletét megkapjuk.
Itt van mondjuk ez a kettő…
Egy olyan lineáris függvényünk lesz, ami 12-ben 1268-at vesz föl.
És 28-ban pedig 3210-et.
A mamutfenyők életkorát leíró lineáris függvényt úgy kapjuk meg…
Hogyha megoldjuk ezt az egyenletrendszert:
És meg is van a mamutfenyők életkorát leíró függvény.
De sajnos van egy kis gond.
A függvény nem őrületes pontossággal számítja ki a mamutfenyők életkorát…
A másik három mamutfenyőnél például egyiket sem sikerül eltalálnia.
A három pont közül egyik sem illeszkedik a függvény grafikonjára.
Ezen még talán valahogy túltesszük magunkat.
A nagyobb baj az, hogy a függvényt csak két mérés adataiból alkottuk meg, a másik három fa mérési adatait nem építettük bele.
Pedig sokkal pontosabban számítaná ki a mamutfenyők életkorát a függvényünk, ha valahogyan ezt a másik három mérést is fel tudnánk használni.
Hát, akkor használjuk…
Most, hogy mind az öt mérést felhasználtuk…
Egy olyan egyenletrendszert kaptunk, amiben két ismeretlen van és öt egyenlet.
Mivel vannak benne egymásnak ellentmondó egyenleteik is, az egyenletrendszer nem megoldható.
Hát, ez nem jó hír…
De éppen az ilyen esetekre használhatjuk a Gauss-féle normálegyenletet.
Itt jön az egyenletrendszer optimális megoldása:
Ezzel a módszerrel egy olyan egyenest kaptunk, amely a lehető legközelebb halad mind az öt ponthoz.
Ezt az egyenest regressziós egyenesnek nevezzük.
A módszer általánosítható…
Az x és y változó közötti kapcsolat meghatározásához méréseket végzünk.
Az x1, x2, … és xn értékekhez…
Az y1, y2 … és yn értékek tartoznak.
Keressük azt a lineáris függvényt, amely a lehető legjobban illeszkedik a mérési pontokra.
Éppen itt is van.
A függvény grafikonja akkor illeszkedik a legjobban a mérési pontokra, ha ezek az egyenletek egyszerre teljesülnek.
Nem sok esély van arra, hogy ez az egyenletrendszer megoldható.
De nem baj, úgyis itt van nekünk a módsszer az optimális megoldás megtalálására.
Ezeket az egyenleteket normálegyenleteknek nevezzük.
A normálegyenletek által alkotott egyenletrendszer megoldásával kapjuk meg a lineáris regresszió paramétereit, b1-et és b0-t.
eket már a grafikon két pontja alapján is
Hogyha ábrázoljuk ebben a koordinátarendszerben ennek az öt mérésnek az eredményeit
Hogyha kíváncsiak vagyunk rá, hogy a többi mamutfenyő hány éves…
Akkor nem kell mindet átfúrni.
Egyszerűen csak vesszük a két mérési adatunkat…
És felírunk egy lineáris függvényt.
Egy olyan lineáris függvényt, ami 12-ben 1268-at vesz föl.
És 28-ban pedig 3210-et.
A mamutfenyők életkorát leíró lineáris függvényt úgy kapjuk meg…
Hogyha megoldjuk ezt az egyenletrendszert:
És meg is van a mamutfenyők életkorát leíró függvény.
Ha most lemérjük például ennek a mamutfenyőnek a törzskerületét…
Aztán behelyettesítjük a függvénybe…
Akkor azt kapjuk, hogy ez a fa 1754 éves.
De sajnos van itt egy kis probléma…
Hogyha pontosan megmérjük az évgyűrűk számát…
Akkor az jön ki, hogy ez a fa nem 1754, hanem csak 1476 éves.
És tulajdonképpen a másik két fánál sem stimmel a függvény.
Ami pedig még ennél is nagyobb gond, hogyha például a másik két fa mérési adatait vesszük alapul…
Akkor teljesen más függvényt kapunk.
Az világos, hogy öt fa mérési adataiból precízebben meg tudjuk adni az életkort leíró függvényt.
Csak éppen az a kérdés, hogyan írjuk fel az egyenes egyenletét.
ennek a másik három mamutfenyőnek a törzskerületét és az évgyűrűk számát…
És aztán ábrázoljuk ezeket is a koordinátarendszerben…
Akkor ezek nem illeszkednek az egyenesre.
Ha egy mátrix nem invertálható, azért még nincs minden veszve…
Ilyenkor is létezik valami, ami olyasmi, mint az inverz: ezt hívjuk pszeudoinverznek.
Pszeudoinverzből sokféle van…
De csak egy olyan van közülük, amelyik teljesíti a négy darab Moore-Penrose kritériumot.
Ezt hívjuk Moore-Penrose pszeudoinverznek.
Ha az A mátrix teljes oszloprangú, akkor a Moore-Penrose-féle pszeudoinverze:
Ha az A mátrix teljes sorrangú, akkor a Moore-Penrose-féle pszeudoinverze:
Próbáljuk is ki ezeket a képleteket.
Itt van például ez a mátrix. Számoljuk ki a Moore-Penrose-féle pszeudoinverzét.
Ebben a mátrixban a két sorvektor lineárisan független.
Így hát ez egy teljes sorrangú mátrix.
És meg is van a Moore-Penrose-féle pszeudoinverz.
Van itt még egy dolog, amire a Moore-Penrose pszeudoinverz használható.
Itt ez az egyenletrendszer…
Aminek sajnos nincsen megoldása.
Túl sok ugyanis benne az egyenlet, és az egyenletrendszer ellentmondásos.
Az ilyen ellentmondásos egyenletrendszerekre már volt egy megoldási módszerünk, a Gauss-féle normálegyenlet segítségével.
Most ugyanazt a megoldást kapjuk a Moore-Penrose inverzzel is.
Olyankor, amikor az A mátrixnak létezik valódi inverze, az egyenletrendszer biztosan megoldható.
A pszeudoinverzzel pedig ez mindig működik.
Hiszen pszeudoinverze minden mátrixnak van.
Nem kell mást tennünk, mint kiszámolni az együtthatómátrix Moore-Penrose-féle pszeudoinverzét…
És az egyenletrendszer megoldása:
A Gauss-féle normálegyenlettel pontosan ugyanezt a megoldást kaptuk volna.
Végül itt jön még egy mátrix.
Ennek a mátrixnak két független oszlopvektora van.
És két független sorvektora.
Tehát nem teljes oszloprangú…
És nem is teljes sorrangú.
Így hát egyik képlet sem használható a Moore-Penrose inverz kiszámolására.
Szerencsére bármelyik mátrixot fel lehet bontani két olyan mátrix szorzatára…
Amelyek közül az egyik teljes oszloprangú, a másik pedig teljes sorrangú.
Ezt bázisfelbontásnak hívják, és egy kis Gauss-eliminációval tudjuk elkészíteni.
Pontosabban egy Gauss-Jordan eliminációval.
Ez egy apró módosítása a Gauss-eliminációnak, és mindössze arról van szó, hogy a vezéregyesek felett is ki kell nulláznunk.
Meg is van.
És most jöhet a bázisfelbontás.
Íme, a bázisfelbontás.
És még egy dolog…
Két mátrix szorzatának pszeudoinverze:
Próbáljuk meg kiszámolni ennek a mátrixnak az inverzét.
Azért túl sok jóra ne számítsunk…
Ennek a mátrixnak biztos, hogy nincs inverze.
A gondot az okozza, hogy mátrix oszlopvektorai lineárisan összefüggők.
Na meg a sorvektorai is.
Hogyha erről a sok rossz hírről mind nem veszünk tudomást, és mégis elkezdjük kiszámolni a mátrix inverzét…
Akkor meg kell oldanunk három egyenletrendszert.
Három darab Gauss-eliminációval.
Amit csinálhatunk akár egyszerre is.
Itt sajnos elérkezünk ahhoz a ponthoz, amikor kiderül: az egyenletrendszer nem megoldható.
Ez egy ellentmondásos egyenletrendszer.
Mondjuk éppen az ilyen esetekre van ez az új módszerünk…
Megpróbáljuk valahogyan mégis megoldani a Gauss-féle normálegyenlet segítségével.
Megint jön a Gauss-elimináció…
Az első oszlop meg is van.
Hasonló izgalmak után kapjuk meg a másik két oszlopot is…
Ez a rengeteg szabad paraméter pedig bármi lehet…
De azért inkább legyen nulla.
Készen is vagyunk.
Ez ugyan nem olyan jó, mint egy valódi inverz…
De a semminél jobb.
Ahogy végignéztük itt a B mátrix keletkezésének történetét, nagyon nem kell meglepődnünk azon, hogy végtelen sok ilyen B mátrix létezik.
Van azonban közülük egyetlen egy, amely képes megfelelni négy darab kritériumnak.
Azt a mátrixot az A mátrix Moore-Penrose-féle pszeudoinverzének nevezzük.
Ez nem az…
Az A mátrix Moore-Penrose-féle pszeudoinverze egy olyan A+ mátrix, amely ezt a négy dolgot tudja:
És most lássuk, hogyan lehet ezt a pszeudoinverzet előállítani.
Egy mátrixot teljes oszloprangúnak nevezünk, hogyha az oszlopvektorai lineárisan független rendszert alkotnak.
Ez a mátrix itt, például teljes oszloprangú.
Egy mátrix teljes sorrangú, ha a sorvektorai lineárisan független rendszert alkotnak.
Hát erről a mátrixról ez most nem mondható el…
Erről a másikról viszont…
Na, erről igen.
Ha az A mátrix teljes oszloprangú, akkor a Moore-Penrose-féle pszeudoinverze:
Ha az A mátrix teljes sorrangú, akkor a Moore-Penrose-féle pszeudoinverze:
És aztán itt van nekünk ez a mátrix.
Erre egyik eset sem illik rá.
Úgyhogy egy kis cselre van szükség.
