Lineaarialgebran numeeriset menetelmät

Lineaarialgebran numeeriset menetelmät (sovellettu lineaarinen algebra) ovat menetelmiä laskennallisen matematiikan ja lineaarialgebran tehtävien likimääräiseen ratkaisuun . Tieteen tavoitteena on algoritmien kehittäminen ja analysointi matriisiongelmien numeeriseen ratkaisuun . Tärkeimmät tehtävät ovat lineaaristen algebrallisten yhtälöiden ratkaiseminen ja ominaisarvojen laskeminen .

Numeerinen lineaarinen algebra tutkii, kuinka matriisioperaatioiden avulla voidaan luoda tietokonealgoritmeja, jotka antavat tehokkaasti likimääräisiä vastauksia jatkuvan matematiikan ongelmiin . Numeerinen lineaarinen algebra on eräänlainen lineaarialgebra ja numeerisen analyysin ala . Tietokoneet käyttävät liukulukuaritmetiikkaa eivätkä voi esittää tarkasti irrationaalista dataa , joten kun tietokonealgoritmia sovelletaan datamatriisiin, se voi joskus lisätä eroa tietokoneeseen tallennetun luvun ja todellisen luvun välillä, jonka likiarvo se on. Numeerinen lineaarinen algebra käyttää vektorien ja matriisien ominaisuuksia kehittääkseen tehokkaita algoritmeja, jotka minimoivat tietokoneen aiheuttaman virheen.

Numeerinen lineaarinen algebra on tarkoitettu jatkuvan matematiikan ongelmien ratkaisemiseen äärellisen tarkkuuden tietokoneilla, joten sen sovellukset luonnon- ja yhteiskuntatieteissä ovat yhtä laajat kuin jatkuvan matematiikan. Se on usein olennainen osa suunnittelu- ja laskennallisia ongelmia , kuten kuvan- ja signaalinkäsittelyä , tietoliikennettä , talouslaskentaa materiaalitieteitä , rakennebiologiaa , tiedon louhintaa , bioinformatiikkaa ja virtausdynamiikkaa . Matriisimenetelmiä käytetään erityisen laajalti äärellisten erojen menetelmissä, elementtimenetelmissä ja differentiaaliyhtälöiden mallintamisessa . Lloyd N. Trefeten ja David Bau, III huomauttavat numeerisen lineaarisen algebran laajan käytön, että se on "yhtä perustavanlaatuinen matemaattisille tieteille kuin laskenta ja differentiaaliyhtälöt" [1] :x , vaikka tämä on suhteellisen pieni alue [2] . Koska monet matriisien ja vektorien ominaisuudet koskevat myös funktioita ja operaattoreita, numeerista lineaarista algebraa voidaan pitää myös eräänlaisena funktionaalisena analyysinä , jossa keskitytään käytännön algoritmeihin [1] :ix .

Numeerisen lineaarisen algebran tärkeimmät tehtävät sisältävät matriisihajotelmien johtamisen, kuten singulaaristen arvojen hajottelun , QR-hajoamisen , LU-hajoamisen tai ominaisdekomposition , joita voidaan sitten käyttää yleisten lineaarialgebran ongelmien ratkaisemiseen, kuten lineaariyhtälöjärjestelmien ratkaisemiseen, ominaisarvojen tai pienimmän neliösumman paikantamiseen. optimointi. Numeerisen lineaarisen algebran päätehtävä on sellaisten algoritmien kehittäminen, jotka eivät aiheuta virheitä, kun niitä sovelletaan todelliseen tietoon tietokoneella äärellisellä tarkkuudella, usein iteratiivisilla menetelmillä .

Historia

Numeerisen lineaarisen algebran ovat kehittäneet John von Neumann , Alan Turing , James H. Wilkinson , Alston Scott Householder , George Forsyth ja Heinz Rutishauser soveltaakseen varhaisimpia tietokoneita jatkuvan matematiikan ongelmiin, kuten esim. ballistisia tehtäviä ja tehtäviä differentiaaliyhtälöjärjestelmän ratkaisemiseksi osittaisissa derivaatoissa [2] . John von Neumann ja Herman Goldstein tekivät ensimmäisen vakavan yrityksen minimoida laskentavirhe sovellettaessa algoritmeja todelliseen dataan vuonna 1947 [3] . Tämä alue on laajentunut, kun teknologia on yhä useammin antanut tutkijoille mahdollisuuden ratkaista monimutkaisia ongelmia erittäin suurilla, erittäin tarkoilla matriiseilla, ja jotkut numeeriset algoritmit ovat nousseet esiin, kun tekniikat, kuten rinnakkaislaskenta, ovat mahdollistaneet käytännön lähestymistavan tieteellisiin ongelmiin [2 ] .

Matriisihajotelmat

Block Matrix

Monissa sovelletun lineaarisen algebran ongelmissa on hyödyllistä ajatella matriisia sarakevektoreiden yhdistettynä sarjana. Esimerkiksi, kun ratkaistaan lineaarista järjestelmää , sen sijaan, että etsittäisiin kertolaskuna ja , se on parempi esittää kertoimien vektorina lineaarisessa laajennuksessa sarakkeiden muodostamassa kannassa [1] :8 . Matriisien käsitys yhdistettynä sarakejoukona on käytännöllinen matriisialgoritmien tarkoituksiin, koska matriisialgoritmit sisältävät usein kaksi sisäkkäistä silmukkaa, toinen matriisin sarakkeiden yli ja toinen matriisin rivien päällä . Esimerkiksi matriiseille ja vektoreille ja , voidaan käyttää sarakkeen jakamista laskeaksesi muodossa $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$

jos j = 1 : n , jos i = 1 : m y ( i ) = A ( i , j ) x ( j ) + y ( i ) loppupää

Yksittäisen arvon hajottelu

Matriisin singulaariarvohajotus , jossa ja ovat unitaarisia matriiseja ja on diagonaalinen . Diagonaalimatriisin elementtejä kutsutaan matriisin singulaariarvoiksi . Koska yksikköarvot ovat matriisin ominaisarvojen neliöjuuria, singulaariarvon ja ominaisarvon hajottelun välillä on läheinen yhteys. Tämä tarkoittaa, että useimmat singulaariarvon laajennuksen laskentamenetelmät ovat samanlaisia kuin ominaisarvomenetelmät [1] :36 ; ehkä yleisin menetelmä sisältää Householder-muunnos [1] :253 . ${\displaystyle A^{m\times n}=U\Sigma V^{\ast ))$ $U$ $V$ $\Sigma$ $\Sigma$ $A$ ${\displaystyle AA^{\ast ))$

QR-hajotus

Matriisin QR-hajotus esitetään matriisin tulona siten , että missä on ortogonaalinen matriisi ja on ylempi kolmimatriisi [1] :50, [4] :223 . Kaksi pääalgoritmia QR-hajotelman laskemiseen: Gram-Schmidt-prosessi ja Householder-muunnos . QR-hajottelua käytetään usein pienimmän neliösumman ongelmiin ja ominaisarvoongelmiin ( iteratiivisen QR-algoritmin avulla ). $A^{m\times n}$ ${\displaystyle Q^{m\times m))$ ${\displaystyle R^{m\times n))$ $A = QR$ $K$ $R$

LU:n hajoaminen

Matriisin LU-hajotelma koostuu alemmasta kolmiomatriisista ja ylemmästä kolmiomatriisista siten, että . Matriisi löydetään Gaussin menetelmällä , jossa kerrotaan vasemmalle matriisijoukolla muodostamaan , josta [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))$

Spektrihajoaminen

Matriisin spektrihajotelma , jossa sarakkeet ovat matriisin ominaisvektoreita , ja on diagonaalimatriisi, jonka diagonaaliset alkiot ovat matriisin vastaavat ominaisarvot [1] :33 . Ei ole olemassa suoraa menetelmää mielivaltaisen matriisin spektrihajotelman löytämiseen: koska on mahdotonta kirjoittaa ohjelmaa, joka löytää mielivaltaisen polynomin tarkat juuret äärellisessä ajassa, minkä tahansa ominaisarvojen löytämisalgoritmin on välttämättä oltava iteratiivinen [1] :192 . ${\displaystyle A^{m\times m}=X\Lambda X^{-1))$ $X$ $A$ $\lambda$ $A$

Algoritmit

Gaussin menetelmä

Numeerisen lineaarisen algebran näkökulmasta Gauss-menetelmä on menetelmä matriisin hajottamiseksi LU-hajotukseksi, jonka Gauss-menetelmä suorittaa kertomalla vasemmalta matriisijonolla, kunnes siitä tulee ylempi kolmio, eikä siitä tule alempi kolmio, jossa [1] : 148 . Naiivien Gaussin ohjelmien tiedetään olevan laskennallisesti erittäin epävakaita ja aiheuttavat valtavia virheitä, kun niitä sovelletaan matriiseihin, joissa on monia merkitseviä numeroita [2] . Yksinkertaisin ratkaisu on ottaa käyttöön pivot , joka antaa muunnetun stabiilin Gauss-algoritmin [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))$

Lineaaristen järjestelmien ratkaisut

Numeerinen lineaarinen algebra pitää matriiseja yleensä sarakevektoreiden yhdistettynä sarjana. Perinteinen lähestymistapa on ratkaista lineaarinen järjestelmä saada sekä tulo ja . Sen sijaan numeerinen lineaarinen algebra tulkitsee lineaaristen laajennuskertoimien vektoriksi sarakkeiden [1] :8 muodostamassa kannassa . $x = A^{-1}b$ $x$ $A^{{-1}}$ $b$ $x$ $b$ $A$

Matriisiyhtälöitä voidaan käyttää lineaaristen yhtälöjärjestelmien ratkaisemiseen. Riippuen matriisin ja vektorien ominaisuuksista ja , jotkut laajennukset voivat olla yksinkertaisempia kuin toiset. voidaan käyttää monia erilaisia hajotuksia riippuen matriisin ja vektorien ominaisuuksista ja , mikä voi tehdä yhden jaottelun paljon helpommaksi saada kuin muut. Jos on matriisin QR-hajotus , niin [1] :54 . Jos on matriisin spektrihajotelma , niin pyrimme löytämään sellaisen, että , kanssa ja . Mistä saamme [1] :33 . Lopuksi, jos on matriisin LU-hajotelma , niin se voidaan ratkaista käyttämällä kolmiomatriiseja ja [1] :147 [4] :99 . $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$

Pienimmän neliösumman optimointi

Matriisihajotusmenetelmä tarjoaa useita tapoja ratkaista lineaarinen järjestelmä, jossa pyrimme minimoimaan , kuten lineaarisessa regressiomallissa . QR-algoritmi ratkaisee tämän ongelman määrittämällä ensin ja sitten laskemalla hienon QR-hajoamisen ja siirtyy yhtälöön . Tämä ylempi kolmiojärjestelmä voidaan ratkaista suhteessa . Samanlainen algoritmi pienimmän neliösumman ratkaisemiseksi voidaan saada käyttämällä SVD-hajottelua. Laskemalla hieno SVD-laajennus ja sitten vektori , pienennämme pienimmän neliösumman ongelman yksinkertaiseksi diagonaalijärjestelmäksi [1] :84 . Se, että pienimmän neliösumman ratkaisuja voidaan saada QR-hajotuksella ja SVD-hajottelulla, tarkoittaa, että perinteisen pienimmän neliösumman ongelman ratkaisevan normaaliyhtälöiden menetelmän lisäksi nämä ongelmat voidaan ratkaista myös menetelmillä, kuten Gramin algoritmilla -Schmidt ja Householderin menetelmät. . $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$

Ehdollisuus ja laskennallinen vakaus

Tarkastellaan funktiota , jossa on datan normivektoriavaruus ja ratkaisujen normivektoriavaruus. Jossain vaiheessa ongelmaa kutsutaan huonosti ehdollistukseksi, jos pieni häiriö in johtaa suureen muutokseen arvossa . Voimme kvantifioida tämän määrittämällä ehtonumeron , joka osoittaa, kuinka hyvin ongelma on ehdollistettu. Määritellään se näin $f:X\Y:ksi$ $X$ $Y$ $x\in X$ $x$ $f(x)$

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

Epävakaus on liukulukuaritmetiikkaan tukevien tietokonealgoritmien taipumus tuottaa tuloksia, jotka eroavat jyrkästi ongelman täsmällisestä matemaattisesta ratkaisusta. Kun matriisi sisältää todellista dataa, jossa on monia merkitseviä numeroita, monet ongelmien ratkaisualgoritmit, kuten lineaariset yhtälöjärjestelmät tai pienimmän neliösumman optimointi, voivat tuottaa erittäin epätarkkoja tuloksia. Vakaiden algoritmien luominen huonosti ehdollistettuihin ongelmiin on keskeinen ongelma numeerisessa lineaarisessa algebrassa. Eräs esimerkki on, että Householder-heijastusmenetelmän stabiilius tekee algoritmista robustin menetelmän lineaaristen järjestelmien ratkaisemiseen, kun taas normaalin yhtälömenetelmän epävakaus pienimmän neliösumman ongelmien ratkaisemiseen on syynä matriisihajotusmenetelmien, kuten SVD-hajottamisen, valintaan. Jotkut matriisin hajottelumenetelmät voivat olla epävakaita, mutta niissä on yksinkertaisia muunnelmia, jotta ne olisivat stabiileja; esimerkiksi epästabiili Gram-Schmidt-menetelmä, jota voidaan helposti muokata stabiilin Gram-Schmidt-muunnoksen saamiseksi [1] :140 . Toinen numeerisen lineaarisen algebran klassinen ongelma on, että Gaussin menetelmä on epävakaa, mutta muuttuu vakaaksi kääntöpisteen käyttöönoton myötä.

Iteratiiviset menetelmät

On kaksi syytä, miksi iteratiiviset algoritmit ovat tärkeä osa numeerista lineaarista algebraa. Ensinnäkin monilla numeerisilla ongelmilla ei ole suoraa ratkaisua; mielivaltaisen matriisin ominaisarvojen ja ominaisvektorien löytämiseksi voimme käyttää vain iteratiivista lähestymistapaa. Toiseksi mielivaltaisen matriisin ei-iteratiiviset algoritmit vievät aikaa, mikä on odottamattoman pitkä, koska matriisit sisältävät vain numeroita. Iteratiiviset lähestymistavat voivat käyttää joitain matriisien ominaisuuksia lyhentääkseen tätä aikaa. Esimerkiksi kun matriisi on harvassa , iteratiivinen algoritmi voi ohittaa monet vaiheet, joita suora lähestymistapa on velvollinen noudattamaan, vaikka ne olisivatkin redundantteja. $m \ kertaa m$ $O(m^{3})$ $m^{2}$

Monien iteratiivisten menetelmien ydin numeerisessa lineaarisessa algebrassa on matriisin projektio alempaan , matalampiulotteiseen Krylov-aliavaruuteen , mikä mahdollistaa korkeadimensionaalisen matriisin ominaisuuksien approksimoimisen laskemalla iteratiivisesti samanlaisten matriisien ekvivalentit ominaisuudet, alkaen matalaulotteisesta tilasta ja siirtymällä peräkkäin korkeampiin ulottuvuuksiin. Kun symmetrinen ja haluamme ratkaista lineaarisen ongelman , klassinen iteratiivinen lähestymistapa on konjugaattigradienttimenetelmä . Jos ne eivät ole symmetrisiä, esimerkkejä lineaarisen ongelman iteratiivisista ratkaisuista ovat yleistetty minimijäännösmenetelmä (GMRES) ja konjugaattigradienttimenetelmä normaaliyhtälöille (CGN) normaaliyhtälöille. Jos se on symmetrinen, voimme käyttää Lanczos-algoritmia löytääksemme ominaisarvot ja ominaisvektorit , ja jos ei symmetristä, niin Arnoldi-iteraatiota käytetään . $A$ $ax=b$ $A$ $A$ $A$

Numeerinen analyysiohjelmisto

Jotkut ohjelmointikielet käyttävät numeerisia lineaarialgebran optimointimenetelmiä ja on suunniteltu toteuttamaan sen algoritmit. Näitä kieliä ovat MATLAB , Analytica, Maple ja Mathematica . Muissa ohjelmointikielissä, joita ei ole erityisesti suunniteltu numeeriseen lineaariseen algebraan, on kirjastoja, jotka tarjoavat rutiineja ja optimointeja; C :ssä ja Fortranissa on Basic Linear Algebra -aliohjelmat ja LAPACK-paketit , pythonissa on NumPy - kirjasto ja Perlissä on Perl Data Language . Monet numeeriset lineaarisen algebran komennot R :ssä perustuvat peruskirjastoihin, kuten LAPACK [5] .

Linkit

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Trefethen Lloyd, Bau III David. Numeerinen lineaarinen algebra (1. painos) (englanniksi) . - Philadelphia: SIAM, 1997. - ISBN 978-0-89871-361-9 .
↑ 1 2 3 4 Golub, Gene H. Modernin numeerisen lineaarialgebran historia . Chicagon yliopiston tilastoosasto . Haettu: 17.2.2019. (määrätön)
↑ von Neumann, John; Goldstine, Herman H. (1947). "Korkean asteen matriisien numeerinen invertointi" (PDF) . American Mathematical Societyn tiedote . 53 (11): 1021-1099. DOI : 10.1090/s0002-9904-1947-08909-6 . S2CID 16174165 . Arkistoitu alkuperäisestä (PDF) 2019-02-18 . Haettu 17.2.2019 . _ Käytöstä poistettu parametri |url-status=( ohje )
↑ 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 ja lineaarinen algebra . R-bloggaajat (29. elokuuta 2013). Haettu: 17.2.2019. (määrätön)