Numeriska metoder för linjär algebra

Numeriska metoder för linjär algebra (tillämpad linjär algebra) är metoder för ungefärlig lösning av problem från området beräkningsmatematik och linjär algebra . Syftet med disciplinen är utveckling och analys av algoritmer för numerisk lösning av matrisproblem . De viktigaste uppgifterna är att lösa system av linjära algebraiska ekvationer och beräkna egenvärden .

Numerisk linjär algebra utforskar hur matrisoperationer kan användas för att skapa datoralgoritmer som effektivt ger ungefärliga svar på problem i kontinuerlig matematik . Numerisk linjär algebra är en typ av linjär algebra och är ett område för numerisk analys . Datorer använder flyttalsaritmetik och kan inte representera irrationella data exakt , så när en datoralgoritm appliceras på en matris av data kan det ibland öka skillnaden mellan talet som är lagrat i datorn och det sanna antalet som det är en approximation. Numerisk linjär algebra använder egenskaperna hos vektorer och matriser för att utveckla effektiva algoritmer som minimerar det fel som datorn introducerar.

Numerisk linjär algebra syftar till att lösa problem med kontinuerlig matematik med hjälp av datorer med ändlig precision, så dess tillämpningar inom natur- och samhällsvetenskap är lika omfattande som de för kontinuerlig matematik. Det är ofta en grundläggande del av ingenjörs- och beräkningsproblem som bild- och signalbehandling , telekommunikation , finansiell beräkning materialvetenskap , strukturell biologi , datautvinning , bioinformatik och vätskedynamik . Matrismetoder används särskilt ofta i finita differensmetoder , finita elementmetoder och differentialekvationsmodellering . Lloyd N. Trefeten och David Bau, III noterar den utbredda användningen av numerisk linjär algebra och hävdar att den är "lika grundläggande för de matematiska vetenskaperna som kalkyl och differentialekvationer" [1] :x , även om detta är en relativt liten område [2] . Eftersom många egenskaper hos matriser och vektorer även gäller för funktioner och operatorer kan numerisk linjär algebra också ses som en typ av funktionsanalys , med fokus på praktiska algoritmer [1] :ix .

Stora uppgifter i numerisk linjär algebra involverar härledning av matrisuppdelningar såsom singulärvärdesuppdelning , QR -uppdelning , LU -uppdelning eller egenuppdelning , som sedan kan användas för att lösa allmänna linjära algebraproblem som att lösa system av linjära ekvationer, lokalisera egenvärden eller minsta kvadrater. optimering. Huvuduppgiften för numerisk linjär algebra är utvecklingen av algoritmer som inte introducerar fel när de tillämpas på verkliga data på en dator med ändlig noggrannhet, ofta uppnådd med iterativa metoder .

Historik

Numerisk linjär algebra utvecklades av John von Neumann , Alan Turing , James H. Wilkinson , Alston Scott Householder , George Forsyth och Heinz Rutishauser , för att tillämpa de tidigaste datorerna på problem i kontinuerlig matematik som t.ex. ballistiska uppgifter och uppgifter för att lösa ett system av differentialekvationer i partiella derivator [2] . Det första seriösa försöket att minimera beräkningsfel när man tillämpade algoritmer på verkliga data gjordes av John von Neumann och Herman Goldstein 1947 [3] . Detta område har expanderat i takt med att tekniken i allt högre grad har gjort det möjligt för forskare att lösa komplexa problem på extremt stora, högprecisionsmatriser, och vissa numeriska algoritmer har blivit framträdande eftersom teknologier som parallell beräkning har gjort det möjligt att tillämpa ett praktiskt förhållningssätt till vetenskapliga problem [2 ] .

Matrisupplösningar

Block Matrix

För många problem i tillämpad linjär algebra är det användbart att tänka på en matris som en kombinerad uppsättning kolumnvektorer. Till exempel, när man löser ett linjärt system , istället för att hitta som en multiplikation och , är det bättre att representera det som en vektor av koefficienter i en linjär expansion i grunden som bildas av kolumner [1] :8 . Begreppet matriser som en kombinerad uppsättning kolumner är praktiskt för matrisalgoritmer, på grund av det faktum att matrisalgoritmer ofta innehåller två kapslade loopar, en över matrisens kolumner och den andra över matrisens rader . Till exempel, för matriser och vektorer och , kan man använda kolumndelning för att beräkna som $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$

för j = 1 : n för i = 1 : m y ( i ) = A ( i , j ) x ( j ) + y ( i ) slutände _

Singular värdenedbrytning

Singular värdenedbrytning av matrisen , där och är enhetliga matriser och är diagonal . Elementen i en diagonal matris kallas singularvärden av matrisen . Eftersom singularvärden är kvadratrötterna av matrisens egenvärden finns det ett nära samband mellan singularvärdesupplösning och egenvärdesuppdelning. Detta betyder att de flesta metoderna för att beräkna singularvärdesexpansionen liknar egenvärdemetoderna [1] :36 ; kanske den vanligaste metoden involverar Householder transform [1] :253 . ${\displaystyle A^{m\times n}=U\Sigma V^{\ast ))$ $U$ $V$ $\Sigma$ $\Sigma$ $A$ ${\displaystyle AA^{\ast ))$

QR-sönderdelning

QR-sönderdelningen av en matris representeras av produkten av en matris av sådan att , där är en ortogonal matris och är en övre triangulär matris [1] :50, [4] :223 . Två huvudalgoritmer för att beräkna QR-nedbrytningen: Gram-Schmidt-processen och Householder-transformen . QR-sönderdelning används ofta för minsta kvadraters problem och egenvärdeproblem (med iterativ QR-algoritm ). $A^{m\times n}$ ${\displaystyle Q^{m\times m))$ ${\displaystyle R^{m\times n))$ $A = QR$ $F$ $R$

LU-nedbrytning

LU-sönderdelningen av en matris består av en nedre triangulär matris och en övre triangulär matris så att . Matrisen hittas med den Gaussiska metoden , som innebär vänstermultiplikationer med en uppsättning matriser för att bilda , varifrån [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))$

Spektral nedbrytning

Den spektrala nedbrytningen av matrisen , där kolumnerna är matrisens egenvektorer , och är en diagonal matris vars diagonala element är motsvarande egenvärden för matrisen [1] :33 . Det finns ingen direkt metod för att hitta den spektrala nedbrytningen av en godtycklig matris: eftersom det är omöjligt att skriva ett program som hittar de exakta rötterna till ett godtyckligt polynom i ändlig tid, måste varje algoritm för att hitta egenvärden nödvändigtvis vara iterativ [1] :192 . ${\displaystyle A^{m\times m}=X\Lambda X^{-1))$ $X$ $A$ $\lambda$ $A$

Algoritmer

Gauss-metoden

Ur synvinkel av numerisk linjär algebra är Gauss-metoden proceduren för att sönderdela en matris till en LU-nedbrytning, som Gauss-metoden utför genom att multiplicera från vänster med en sekvens av matriser tills den blir övre triangulär, och inte blir nedre triangulär, där [1] : 148 . Naiva Gaussiska program är kända för att vara mycket beräkningsmässigt instabila och ger enorma fel när de tillämpas på matriser med många signifikanta siffror [2] . Den enklaste lösningen är att införa en pivot , som ger en modifierad stabil Gauss-algoritm [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))$

Lösningar för linjära system

Numerisk linjär algebra betraktar vanligtvis matriser som en kombinerad uppsättning kolumnvektorer. Det traditionella tillvägagångssättet är att lösa ett linjärt system för att få både produkten av och . Istället tolkar numerisk linjär algebra som en vektor av linjära expansionskoefficienter i grunden som bildas av kolumnerna [1] :8 . $x = A^{-1}b$ $x$ $A^{{-1}}$ $b$ $x$ $b$ $A$

Matrisekvationer kan användas för att lösa linjära ekvationssystem. Beroende på egenskaperna hos matrisen och vektorerna och kan vissa expansioner vara enklare än andra. många olika sönderdelningar kan användas, beroende på egenskaperna hos matrisen och vektorerna och , vilket kan göra en sönderdelning mycket lättare att erhålla än andra. Om är QR-sönderdelningen av matrisen , då [1] :54 . Om är den spektrala nedbrytningen av matrisen , då strävar vi efter att hitta sådana att , med och . Där får vi [1] :33 . Slutligen, om är LU-sönderdelningen av matrisen , så kan den lösas med hjälp av triangulära matriser och [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$

Minsta kvadratoptimering

Matrisnedbrytningsmetoden erbjuder ett antal sätt att lösa ett linjärt system där vi strävar efter att minimera , som i en linjär regressionsmodell . QR-algoritmen löser detta problem genom att först bestämma och sedan beräkna den fina QR-sönderdelningen och fortsätter till ekvationen . Detta övre triangulära system kan lösas med avseende på . En liknande algoritm för att lösa de minsta kvadraterna kan erhållas med hjälp av SVD-sönderdelningen. Genom att beräkna den fina SVD-expansionen , och sedan beräkna vektorn , reducerar vi problemet med minsta kvadrater till ett enkelt diagonalsystem [1] :84 . Det faktum att minsta kvadratlösningar kan erhållas med QR-sönderdelning och SVD-nedbrytning innebär att förutom den klassiska metoden med normala ekvationer att lösa minsta kvadraters problem, kan dessa problem även lösas med metoder inklusive Grams algoritm -Schmidt och Householder-metoder . $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$

Villkorlighet och beräkningsstabilitet

Betrakta funktionen , där är det normerade vektorutrymmet för data och är det normerade vektorutrymmet för lösningar. För någon punkt kallas problemet dåligt konditionerat om en liten störning i leder till en stor förändring av värdet på . Vi kan kvantifiera detta genom att bestämma villkorsnumret , som anger hur väl problemet är betingat. Låt oss definiera det som $f:X\till Y$ $X$ $Y$ $x\i X$ $x$ $f(x)$

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

Instabilitet är tendensen hos datoralgoritmer som förlitar sig på flyttalsaritmetik för att ge resultat som skiljer sig kraftigt från den exakta matematiska lösningen på problemet. När en matris innehåller riktiga data med många signifikanta siffror kan många algoritmer för att lösa problem som linjära ekvationssystem eller optimering av minsta kvadrater ge mycket felaktiga resultat. Skapandet av stabila algoritmer för dåligt betingade problem är ett centralt problem inom numerisk linjär algebra. Ett exempel är att stabiliteten i Householder-reflektionsmetoden gör algoritmen till en robust metod för att lösa linjära system, medan instabiliteten hos den normala ekvationsmetoden för att lösa minsta kvadratproblem är anledningen till att man väljer matrisnedbrytningsmetoder som att använda SVD-nedbrytning. Vissa matrisnedbrytningsmetoder kan vara instabila, men har enkla modifieringar för att göra dem stabila; till exempel den instabila Gram-Schmidt-metoden, som enkelt kan modifieras för att få en stabil Gram-Schmidt-modifikation [1] :140 . Ett annat klassiskt problem inom numerisk linjär algebra är att Gaussmetoden är instabil, men blir stabil med införandet av en pivot.

Iterativa metoder

Det finns två anledningar till varför iterativa algoritmer är en viktig del av numerisk linjär algebra. För det första har många numeriska problem ingen direkt lösning; för att hitta egenvärdena och egenvektorerna för en godtycklig matris kan vi bara använda ett iterativt tillvägagångssätt. För det andra tar icke-iterativa algoritmer för en godtycklig matris tid, vilket är oväntat långt, med tanke på att matriser bara innehåller siffror. Iterativa tillvägagångssätt kan använda vissa funktioner i matriser för att minska denna tid. Till exempel, när matrisen är gles , kan den iterativa algoritmen hoppa över många av stegen som det direkta tillvägagångssättet måste följa, även om de är överflödiga. $m \ gånger m$ $O(m^{3})$ $m^{2}$

Kärnan i många iterativa metoder i numerisk linjär algebra är projektionen av en matris på ett lägre , lägre dimensionellt Krylov-underrum , vilket gör det möjligt att approximera egenskaperna hos en högdimensionell matris genom att iterativt beräkna motsvarande egenskaper hos liknande matriser, utgående från ett lågdimensionellt utrymme och successivt flytta till högre dimensioner. När symmetriska och vi vill lösa ett linjärt problem , är den klassiska iterativa metoden den konjugerade gradientmetoden . Om inte symmetrisk, så är exempel på iterativa lösningar av ett linjärt problem den generaliserade minimala residualmetoden (GMRES) och den konjugerade gradientmetoden för normala ekvationer (CGN) för normala ekvationer. Om det är symmetriskt kan vi använda Lanczos-algoritmen för att hitta egenvärden och egenvektorer , och om det inte är symmetriskt används Arnoldi-iteration . $A$ $ax=b$ $A$ $A$ $A$

Programvara för numerisk analys

Vissa programmeringsspråk använder numeriska linjära algebraoptimeringsmetoder och är designade för att implementera dess algoritmer. Dessa språk inkluderar MATLAB , Analytica, Maple och Mathematica . Andra programmeringsspråk som inte är explicit designade för numerisk linjär algebra har bibliotek som tillhandahåller rutiner och optimeringar; C och Fortran har de grundläggande linjära algebra-underprogrammen och LAPACK-paketen , python har NumPy - biblioteket och Perl har Perl Data Language . Många numeriska linjära algebrakommandon i R förlitar sig på grundläggande bibliotek som LAPACK [5] .

Länkar

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Trefethen Lloyd, Bau III David. Numerisk linjär algebra (1:a upplagan) (engelska) . - Philadelphia: SIAM, 1997. - ISBN 978-0-89871-361-9 .
↑ 1 2 3 4 Golub, Gene H. En historia av modern numerisk linjär algebra . University of Chicagos statistikavdelning . Hämtad: 17 februari 2019. (obestämd)
↑ von Neumann, John; Goldstine, Herman H. (1947). "Numerisk invertering av matriser av hög ordning" (PDF) . Bulletin från American Mathematical Society . 53 (11): 1021-1099. DOI : 10.1090/s0002-9904-1947-08909-6 . S2CID 16174165 . Arkiverad från originalet (PDF) 2019-02-18 . Hämtad 17 februari 2019 . Utfasad parameter används |url-status=( hjälp )
↑ 1 2 3 Golub, Gene H. Matrix Computations / Gene H. Golub, Charles F. Van Loan. — 3:a. - Baltimore: The Johns Hopkins University Press, 1996. - ISBN 0-8018-5413-X .
↑ Rickert, Joseph R och linjär algebra . R-bloggare (29 augusti 2013). Hämtad: 17 februari 2019. (obestämd)