A lineáris algebra numerikus módszerei

A lineáris algebra numerikus módszerei (alkalmazott lineáris algebra) a számítási matematika és a lineáris algebra területéről származó problémák közelítő megoldásának módszerei . A tudományág célja mátrixfeladatok numerikus megoldására szolgáló algoritmusok kidolgozása és elemzése . A legfontosabb feladatok a lineáris algebrai egyenletrendszerek megoldása és a sajátértékek kiszámítása .

A numerikus lineáris algebra azt vizsgálja, hogyan lehet mátrixműveletekkel olyan számítógépes algoritmusokat létrehozni , amelyek hatékonyan közelítő válaszokat adnak a folytonos matematika problémáira . A numerikus lineáris algebra a lineáris algebra egy fajtája, és a numerikus elemzés területe . A számítógépek lebegőpontos aritmetikát használnak , és nem tudják pontosan ábrázolni az irracionális adatokat , így amikor egy számítógépes algoritmust alkalmaznak egy adatmátrixra, az időnként növelheti a különbséget egy számítógépben tárolt szám és a valós szám között, amelynek ez közelítése. A numerikus lineáris algebra a vektorok és mátrixok tulajdonságait használja fel hatékony algoritmusok kidolgozására, amelyek minimalizálják a számítógép által okozott hibákat.

A numerikus lineáris algebra a folytonos matematika problémáinak megoldására irányul véges pontosságú számítógépek felhasználásával, ezért alkalmazásai a természet- és társadalomtudományokban ugyanolyan kiterjedtek, mint a folytonos matematikáé. Gyakran alapvető része olyan mérnöki és számítási problémáknak, mint a kép- és jelfeldolgozás , a telekommunikáció , a pénzügyi számítástechnika az anyagtudomány , a szerkezetbiológia , az adatbányászat , a bioinformatika és a folyadékdinamika . A mátrixmódszereket különösen széles körben használják a véges differencia -módszerekben , a végeselemes módszerekben és a differenciálegyenlet - modellezésben . Lloyd N. Trefeten és David Bau, III a numerikus lineáris algebra széles körben elterjedt használatára tekintettel azzal érvelnek, hogy az „olyan alapvető a matematikai tudományok számára, mint a számítás és a differenciálegyenletek” [1] :x , bár ez viszonylag kicsi terület [2] . Mivel a mátrixok és vektorok számos tulajdonsága függvényekre és operátorokra is vonatkozik, a numerikus lineáris algebra a funkcionális elemzés egy fajtájaként is felfogható , a gyakorlati algoritmusokra összpontosítva [1] :ix .

A numerikus lineáris algebra fő feladatai közé tartozik a mátrixbontások származtatása, mint például a szinguláris érték dekompozíció , a QR dekompozíció , az LU dekompozíció vagy a sajátdekompozíció , amelyek aztán általános lineáris algebrai problémák megoldására használhatók, mint például lineáris egyenletrendszerek megoldása, sajátértékek vagy legkisebb négyzetek meghatározása. optimalizálás. A numerikus lineáris algebra fő feladata olyan algoritmusok kifejlesztése, amelyek nem okoznak hibákat, ha véges pontossággal alkalmazzák a valós adatokra egy számítógépen, gyakran iteratív módszerekkel .

Történelem

A numerikus lineáris algebrát John von Neumann , Alan Turing , James H. Wilkinson , Alston Scott Householder , George Forsyth és Heinz Rutishauser fejlesztette ki, hogy a legkorábbi számítógépeket alkalmazzák a folytonos matematika problémáira, mint pl. ballisztikai feladatok és differenciálegyenlet-rendszer megoldási feladatai parciális deriváltokban [2] . Az első komoly kísérletet a számítási hibák minimalizálására az algoritmusok valós adatokra történő alkalmazásakor John von Neumann és Herman Goldstein tette 1947-ben [3] . Ez a terület bővült, ahogy a technológia egyre inkább lehetővé tette a kutatók számára, hogy rendkívül nagy, nagy pontosságú mátrixokon oldjanak meg összetett problémákat, és egyes numerikus algoritmusok előtérbe kerültek, mivel az olyan technológiák, mint a párhuzamos számítástechnika, lehetővé tették a tudományos problémák gyakorlati megközelítésének alkalmazását [2 ] .

Mátrix dekompozíciók

Block Matrix

Az alkalmazott lineáris algebra számos problémája esetén hasznos a mátrixot oszlopvektorok kombinált halmazának tekinteni. Például egy lineáris rendszer megoldásánál a és a szorzás helyett jobb együtthatóvektorként ábrázolni lineáris bővítésben az [1] :8 oszlopok által alkotott bázisban . A mátrixok, mint oszlopok kombinált halmazának fogalma praktikus a mátrixalgoritmusok szempontjából, mivel a mátrixalgoritmusok gyakran két egymásba ágyazott hurkot tartalmaznak, az egyik a mátrix oszlopai, a másik a mátrix sorai felett . Például mátrixok és vektorok és , oszlopfelosztást használhatjuk a következő számításokhoz $x = A^{-1}b$ $x$ $A^{{-1}}$ $b$ $x$ $b$ $A$ $A$ $A$ $A^{m\times n}$ $x^{n\times 1}$ $y^{m\times 1}$ $Ax+y$

ha j = 1 : n i = 1 esetén : m y ( i ) = A ( i , j ) x ( j ) + y ( i ) vége _

Szinguláris érték dekompozíció

A mátrix szinguláris értékű dekompozíciója , ahol és unitárius mátrixok és átlós . Az átlós mátrix elemeit a mátrix szinguláris értékeinek nevezzük . Mivel a szinguláris értékek a mátrix sajátértékeinek négyzetgyökei , szoros kapcsolat van a szinguláris érték és a sajátérték-bontás között. Ez azt jelenti, hogy a szinguláris érték-kiterjesztés kiszámítására szolgáló módszerek többsége hasonló a sajátérték-módszerekhez [1] :36 ; talán a leggyakoribb módszer a Householder transzformáció [1] :253 . ${\displaystyle A^{m\times n}=U\Sigma V^{\ast ))$ $U$ $V$ $\Sigma$ $\Sigma$ $A$ ${\displaystyle AA^{\ast ))$

QR dekompozíció

Egy mátrix QR-felbontását egy mátrix szorzata reprezentálja úgy , hogy ahol egy ortogonális mátrix és egy felső háromszögmátrix [1] :50, [4] :223 . Két fő algoritmus a QR dekompozíció kiszámítására: a Gram-Schmidt folyamat és a Householder transzformáció . A QR-felbontást gyakran használják legkisebb négyzetek és sajátérték-problémák esetén (az iteratív QR-algoritmus használatával ). $A^{m\times n}$ ${\displaystyle Q^{m\times m))$ ${\displaystyle R^{m\times n))$ $A = QR$ $K$ $R$

LU dekompozíció

Egy mátrix LU-felbontása egy alsó háromszögmátrixból és egy felső háromszögmátrixból áll , így . A mátrixot a Gauss-módszerrel találjuk meg , amely balra szorzást foglal magában egy mátrixkészlettel , ahonnan [1] :147 [4] :96 . $A$ $L$ $U$ $A=LU$ $U$ $A$ ${\displaystyle M_{1},\ldots ,M_{n-1))$ $M_{n-1}\cdots M_{1}A=U$ ${\displaystyle L=M_{1}^{-1}\cdots M_{n-1}^{-1))$

Spektrális dekompozíció

A mátrix spektrális dekompozíciója , ahol az oszlopok a mátrix sajátvektorai , és egy diagonális mátrix, amelynek átlós elemei a mátrix megfelelő sajátértékei [1] :33 . Nincs közvetlen módszer egy tetszőleges mátrix spektrális dekompozíciójának megtalálására: mivel lehetetlen olyan programot írni, amely véges időben megtalálja egy tetszőleges polinom pontos gyökereit, a sajátértékek megtalálására szolgáló algoritmusoknak szükségszerűen iteratívnak kell lenniük [1] :192 . ${\displaystyle A^{m\times m}=X\Lambda X^{-1))$ $x$ $A$ $\lambda$ $A$

Algoritmusok

Gauss-módszer

A numerikus lineáris algebra szempontjából a Gauss-módszer egy mátrix LU-felbontásra bontásának eljárása, amelyet a Gauss-módszer úgy hajt végre, hogy balról megszoroz egy mátrixsorozattal addig , amíg felső háromszög alakúvá nem válik, és nem lesz . alsó háromszög, ahol [1] : 148 . A naiv Gauss-programokról ismert, hogy számításilag nagyon instabilok , és hatalmas hibákat adnak, ha sok jelentős számjegyű mátrixokra alkalmazzák [2] . A legegyszerűbb megoldás egy pivot bevezetése , amely módosított stabil Gauss-algoritmust [1] :151 . $A$ $A$ $L_{m-1}\cdots L_{2}L_{1}A=U$ $U$ $L$ ${\displaystyle L\equiv L_{1}^{-1}L_{2}^{-1}\cdots L_{m-1}^{-1))$

Lineáris rendszerek megoldásai

A numerikus lineáris algebra általában a mátrixokat oszlopvektorok kombinált halmazának tekinti. A hagyományos megközelítés szerint egy lineáris rendszert kell megoldani, hogy megkapjuk a és a szorzatát is . Ehelyett a numerikus lineáris algebra lineáris kiterjesztési együtthatók vektoraként értelmezi az [1] :8 oszlopok által alkotott bázist . $x = A^{-1}b$ $x$ $A^{{-1}}$ $b$ $x$ $b$ $A$

A mátrixegyenletek felhasználhatók lineáris egyenletrendszerek megoldására. A mátrix és a vektorok jellemzőitől függően egyes bővítések egyszerűbbek lehetnek, mint mások. sok különböző dekompozíció használható a mátrix és a vektorok jellemzőitől és a vektoroktól függően , ami sokkal könnyebbé teheti az egyik dekompozíciót, mint a többit. Ha a mátrix QR dekompozíciója , akkor [1] :54 . Ha a mátrix spektrális dekompozíciója , akkor arra törekszünk, hogy olyat találjunk , hogy , -val és -vel . Hová jutunk [1] :33 . Végül, ha a mátrix LU dekompozíciója , akkor háromszögmátrixok és [1] :147 [4] :99 segítségével megoldható . $A$ $x$ $b$ $A$ $x$ $b$ $A=QR$ $A$ $Rx=Q^{\ast }b$ ${\displaystyle A=X\Lambda X^{-1))$ $A$ $b$ $b = Ax$ $b^{\prime }=X^{-1}b$ $x^{\prime }=X^{-1}x$ ${\displaystyle b^{\prime }=\Lambda x^{\prime ))$ $A=LU$ $A$ $ax=b$ $Ly=b$ $Ux=y$

Legkisebb négyzetek optimalizálás

A mátrix dekompozíciós megközelítés számos módot kínál egy lineáris rendszer megoldására, ahol a minimalizálásra törekszünk , mint egy lineáris regressziós modellnél . A QR-algoritmus úgy oldja meg ezt a problémát, hogy először meghatározza , majd kiszámítja a finom QR-felbontást , és továbblép az egyenlethez . Ez a felső háromszögrendszer tekintetében megoldható . Hasonló algoritmust kaphatunk a legkisebb négyzetek megoldására az SVD-felbontással. A finom SVD-bővítés kiszámításával, majd a vektor kiszámításával a legkisebb négyzetek problémáját egy egyszerű átlós rendszerre redukáljuk [1] :84 . Az a tény, hogy QR-felbontással és SVD-felbontással a legkisebb négyzetek megoldása is előállítható, azt jelenti, hogy a normálegyenletek klasszikus módszere mellett , amely megoldja a legkisebb négyzetek problémáit, ezek a problémák megoldhatók olyan módszerekkel is, mint például a Gram-algoritmus - Schmidt és Householder módszerek . $r=b-Ax$ $r$ $y=Ax$ $A$ ${\widehat {R}}x={\widehat {Q}}^{\ast }b$ $b$ $A={\widehat {U}}{\widehat {\Sigma }}V^{\ast }$ ${\widehat {U}}^{\ast }b$

Feltételesség és számítási stabilitás

Tekintsük a függvényt , ahol az adatok normált vektortere és a megoldások normált vektortere. Egy bizonyos ponton a problémát rosszul kondicionáltnak nevezik, ha egy kis perturbáció az értékben nagy változáshoz vezet . Ezt számszerűsíthetjük a feltételszám meghatározásával , amely azt jelzi, hogy a probléma milyen jól kondicionált. Határozzuk meg úgy $f:X\Y-ig$ $x$ $Y$ $x\X-ben$ $x$ $f(x)$

{\widehat {\kappa }}=\lim _{\delta \to 0}\sup _{\|\delta x\|\leq \delta }{\frac {\|\delta f\|} {\|\delta x\|}}.

Az instabilitás a számítógépes algoritmusok azon tendenciája, amelyek a lebegőpontos aritmetikára támaszkodnak, hogy olyan eredményeket hozzanak létre, amelyek élesen eltérnek a probléma pontos matematikai megoldásától. Ha egy mátrix valós adatokat tartalmaz sok jelentős számjegyből, akkor a problémák megoldására szolgáló számos algoritmus, például a lineáris egyenletrendszerek vagy a legkisebb négyzetek optimalizálása nagyon pontatlan eredményeket adhat. A numerikus lineáris algebra központi problémája a stabil algoritmusok létrehozása rosszul kondicionált problémákra. Példa erre, hogy a Householder-reflexiós módszer stabilitása az algoritmust robusztus módszerré teszi lineáris rendszerek megoldására, míg a legkisebb négyzetek problémáinak megoldására szolgáló normál egyenletmódszer instabilitása az oka annak, hogy mátrixbontási módszereket, például SVD-felbontást választanak. Egyes mátrixbontási módszerek instabilok lehetnek, de egyszerű módosításokkal stabillá teszik őket; például az instabil Gram-Schmidt módszer, amely könnyen módosítható, hogy stabil Gram-Schmidt módosítást kapjunk [1] :140 . A numerikus lineáris algebra másik klasszikus problémája, hogy a Gauss-módszer instabil, de a pivot bevezetésével stabillá válik.

Iteratív módszerek

Két oka van annak, hogy az iteratív algoritmusok a numerikus lineáris algebra fontos részét képezik. Először is, sok numerikus feladatnak nincs közvetlen megoldása; egy tetszőleges mátrix sajátértékeinek és sajátvektorainak megtalálásához csak iteratív megközelítést alkalmazhatunk. Másodszor, egy tetszőleges mátrix nem iteratív algoritmusaihoz idő kell, ami váratlanul hosszú, mivel a mátrixok csak számokat tartalmaznak. Az iteratív megközelítések a mátrixok bizonyos jellemzőit felhasználhatják ennek az időnek a csökkentésére. Például, ha a mátrix ritka , az iteratív algoritmus sok olyan lépést kihagyhat, amelyeket a közvetlen megközelítésnek feltétlenül követnie kell, még akkor is, ha azok redundánsak. $m \szer m$ $O(m^{3})$ $m^{2}$

A numerikus lineáris algebra számos iteratív módszerének lényege egy mátrix vetítése egy alacsonyabb , alacsonyabb dimenziójú Krylov-altérre , amely lehetővé teszi egy nagydimenziós mátrix jellemzőinek közelítését hasonló mátrixok ekvivalens jellemzőinek iteratív kiszámításával. egy alacsony dimenziós térből indulva, és egymás után haladva a magasabb dimenziók felé. Ha szimmetrikus és egy lineáris problémát akarunk megoldani , akkor a klasszikus iteratív megközelítés a konjugált gradiens módszer . Ha nem szimmetrikus, akkor egy lineáris probléma iteratív megoldására példa az általánosított minimum maradék módszer (GMRES) és a konjugált gradiens módszer a normál egyenletekre (CGN) a normál egyenletek esetében. Ha szimmetrikus, akkor a Lanczos-algoritmust használhatjuk sajátértékek és sajátvektorok keresésére , ha pedig nem szimmetrikus, akkor Arnoldi-iterációt használunk . $A$ $ax=b$ $A$ $A$ $A$

Numerikus elemző szoftver

Egyes programozási nyelvek numerikus lineáris algebra optimalizálási módszereket használnak, és az algoritmusok megvalósítására szolgálnak. Ezek a nyelvek közé tartozik a MATLAB , az Analytica, a Maple és a Mathematica . Más programozási nyelvek, amelyeket nem kifejezetten numerikus lineáris algebrához terveztek, olyan könyvtárakkal rendelkeznek, amelyek rutinokat és optimalizálásokat biztosítanak; A C és a Fortran rendelkezik az alapvető lineáris algebrai alprogramokkal és a LAPACK csomagokkal , a python a NumPy könyvtárral , a Perl pedig a Perl adatnyelvvel . Számos numerikus lineáris algebrai parancs az R -ben olyan alapvető könyvtárakra támaszkodik, mint a LAPACK [5] .

Linkek

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Trefethen Lloyd, Bau III David. Numerikus lineáris algebra (1. kiadás) (angol) . - Philadelphia: SIAM, 1997. - ISBN 978-0-89871-361-9 .
↑ 1 2 3 4 Golub, Gene H. A modern numerikus lineáris algebra története . Chicagói Egyetem Statisztikai Osztálya . Letöltve: 2019. február 17. (határozatlan)
↑ von Neumann, János; Goldstine, Herman H. (1947). „Magasrendű mátrixok numerikus invertálása” (PDF) . Az Amerikai Matematikai Társaság közleménye . 53 (11): 1021-1099. DOI : 10.1090/s0002-9904-1947-08909-6 . S2CID 16174165 . Archivált az eredetiből (PDF) ekkor: 2019-02-18 . Letöltve : 2019. február 17 . Elavult használt paraméter |url-status=( súgó )
↑ 1 2 3 Golub, Gene H. Matrix Computations / Gene H. Golub, Charles F. Van Loan. — 3. - Baltimore: The Johns Hopkins University Press, 1996. - ISBN 0-8018-5413-X .
↑ Rickert, Joseph R és a lineáris algebra . R-bloggerek (2013. augusztus 29.). Letöltve: 2019. február 17. (határozatlan)