Numerické metody lineární algebry

Numerické metody lineární algebry (aplikovaná lineární algebra) jsou metody pro přibližné řešení úloh z oblasti výpočetní matematiky a lineární algebry . Cílem disciplíny je vývoj a analýza algoritmů pro numerické řešení maticových úloh . Nejdůležitější úlohy jsou řešení soustav lineárních algebraických rovnic a počítání vlastních čísel .

Numerická lineární algebra zkoumá, jak lze maticové operace použít k vytvoření počítačových algoritmů , které efektivně poskytují přibližné odpovědi na problémy spojité matematiky . Numerická lineární algebra je druh lineární algebry a je pole numerické analýzy . Počítače používají aritmetiku s plovoucí desetinnou čárkou a nemohou přesně reprezentovat iracionální data , takže když je počítačový algoritmus aplikován na matici dat, může někdy zvýšit rozdíl mezi číslem uloženým v počítači a skutečným číslem, jehož je přiblížení. Numerická lineární algebra využívá vlastnosti vektorů a matic k vývoji účinných algoritmů, které minimalizují chyby způsobené počítačem.

Numerická lineární algebra je zaměřena na řešení problémů spojité matematiky pomocí počítačů s konečnou přesností, takže její aplikace v přírodních a společenských vědách jsou stejně rozsáhlé jako aplikace spojité matematiky. Často je základní součástí inženýrských a výpočetních problémů, jako je zpracování obrazu a signálu , telekomunikace , finanční výpočetní technika věda o materiálech , strukturální biologie , dolování dat , bioinformatika a dynamika tekutin . Maticové metody jsou zvláště široce používány v metodách konečných diferencí , metodách konečných prvků a modelování diferenciálních rovnic . Lloyd N. Trefeten a David Bau, III si všímají rozšířeného používání numerické lineární algebry, tvrdí, že je „stejně zásadní pro matematické vědy jako počet a diferenciální rovnice“ [1] :x , i když jde o relativně malý oblast [2] . Protože mnoho vlastností matic a vektorů platí také pro funkce a operátory, lze numerickou lineární algebru také považovat za typ funkční analýzy se zaměřením na praktické algoritmy [1] :ix .

Mezi hlavní úkoly v numerické lineární algebře patří odvozování rozkladů matic, jako je rozklad singulárních hodnot , QR rozklad , rozklad LU nebo vlastní rozklad , které lze následně použít k řešení obecných problémů lineární algebry, jako je řešení systémů lineárních rovnic, lokalizace vlastních hodnot nebo nejmenších čtverců. optimalizace. Hlavním úkolem numerické lineární algebry je vývoj algoritmů, které nezavádějí chyby při aplikaci na reálná data na počítači s konečnou přesností, často dosahované pomocí iteračních metod .

Historie

Numerickou lineární algebru vyvinuli John von Neumann , Alan Turing , James H. Wilkinson , Alston Scott Householder , George Forsyth a Heinz Rutishauser , aby aplikovali nejstarší počítače na problémy v spojité matematice, jako je např. balistické úlohy a úlohy pro řešení soustavy diferenciálních rovnic v parciálních derivacích [2] . První vážný pokus minimalizovat výpočetní chybu při aplikaci algoritmů na reálná data provedli John von Neumann a Herman Goldstein v roce 1947 [3] . Tato oblast se rozšířila, protože technologie stále více umožňovala výzkumníkům řešit složité problémy na extrémně velkých, vysoce přesných maticích a některé numerické algoritmy získaly na významu, protože technologie jako paralelní výpočty umožnily aplikovat praktický přístup k vědeckým problémům [2 ] .

Maticové rozklady

Block Matrix

Pro mnoho problémů v aplikované lineární algebře je užitečné uvažovat o matici jako o kombinované množině sloupcových vektorů. Například při řešení lineárního systému , místo hledání jako násobení a , je lepší jej znázornit jako vektor koeficientů v lineárním rozvoji v bázi tvořené sloupci [1] :8 . Pojem matic jako kombinované sady sloupců je praktický pro účely maticových algoritmů, protože maticové algoritmy často obsahují dvě vnořené smyčky, jednu nad sloupci matice a druhou nad řádky matice . Například pro matice a vektory a lze použít rozdělení sloupců k výpočtu jako $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$

pro j = 1 : n pro i = 1 : m y ( i ) = A ( i , j ) x ( j ) + y ( i ) konec konec

Dekompozice singulární hodnoty

Singulární rozklad matice , kde a jsou unitární matice a je diagonální . Prvky diagonální matice se nazývají singulární hodnoty matice . Protože singulární hodnoty jsou odmocniny vlastních hodnot matice , existuje úzký vztah mezi rozkladem singulárních hodnot a rozkladem vlastních hodnot. To znamená, že většina metod pro výpočet expanze singulární hodnoty je podobná metodám vlastních čísel [1] :36 ; možná nejběžnější metoda zahrnuje transformaci domácnosti [1] :253 . ${\displaystyle A^{m\times n}=U\Sigma V^{\ast ))$ $U$ $PROTI$ $\Sigma$ $\Sigma$ $A$ ${\displaystyle AA^{\ast ))$

QR rozklad

QR rozklad matice je reprezentován součinem matice tak , že , kde je ortogonální matice a je horní trojúhelníková matice [1] :50, [4] :223 . Dva hlavní algoritmy pro výpočet QR rozkladu: Gram-Schmidtův proces a Householderova transformace . QR rozklad se často používá pro problémy nejmenších čtverců a problémy s vlastními hodnotami (pomocí iterativního QR algoritmu ). $A^{m\times n}$ ${\displaystyle Q^{m\times m))$ ${\displaystyle R^{m\times n))$ $A = QR$ $Q$ $R$

Rozklad LU

LU rozklad matice se skládá z dolní trojúhelníkové matice a horní trojúhelníkové matice tak, že . Matice se nachází pomocí Gaussovy metody , která zahrnuje násobení levým sadou matic za účelem vytvoření , odkud [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ální rozklad

Spektrální rozklad matice , kde sloupce jsou vlastními vektory matice , a je diagonální maticí, jejíž diagonální prvky jsou odpovídajícími vlastními hodnotami matice [1] :33 . Neexistuje žádná přímá metoda pro nalezení spektrálního rozkladu libovolné matice: protože není možné napsat program, který najde přesné kořeny libovolného polynomu v konečném čase, jakýkoli algoritmus pro hledání vlastních hodnot musí být nutně iterativní [1] :192 . ${\displaystyle A^{m\times m}=X\Lambda X^{-1))$ $X$ $A$ $\lambda$ $A$

Algoritmy

Gaussova metoda

Z hlediska numerické lineární algebry je Gaussova metoda postup rozkladu matice na LU rozklad, který Gaussova metoda provádí násobením zleva posloupností matic , dokud se nestane horním trojúhelníkem a nestane se spodní trojúhelníkový, kde [1] : 148 . Je známo, že naivní gaussovské programy jsou velmi výpočetně nestabilní a dávají obrovské chyby při aplikaci na matice s mnoha platnými číslicemi [2] . Nejjednodušším řešením je zavést pivot , který dává upravený stabilní Gaussův algoritmus [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))$

Řešení lineárních systémů

Numerická lineární algebra obvykle považuje matice za kombinovanou sadu sloupcových vektorů. Tradiční přístup spočívá v řešení lineárního systému , aby se získal součin a . Místo toho numerická lineární algebra interpretuje jako vektor koeficientů lineární expanze v bázi tvořené sloupci [1] :8 . $x = A^{-1}b$ $X$ $A^{{-1}}$ $b$ $X$ $b$ $A$

Maticové rovnice lze použít k řešení soustav lineárních rovnic. V závislosti na charakteristikách matice a vektorů a mohou být některá rozšíření jednodušší než jiná. lze použít mnoho různých rozkladů v závislosti na vlastnostech matice a vektorů a , což může učinit jeden rozklad mnohem snáze dosažitelný než ostatní. Jestliže je QR rozklad matice , pak [1] :54 . Jestliže je spektrální rozklad matice , pak se snažíme najít takový, že , s a . Kam se dostaneme [1] :33 . Konečně, pokud je LU rozklad matice , pak jej lze vyřešit pomocí trojúhelníkových matic a [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$ $sekera=b$ $Ly=b$ $Ux=y$

Optimalizace metodou nejmenších čtverců

Přístup maticového rozkladu nabízí řadu způsobů řešení lineárního systému, kde se snažíme minimalizovat , jako v lineárním regresním modelu . Algoritmus QR řeší tento problém tak, že nejprve určí a poté vypočítá jemný rozklad QR a pokračuje k rovnici . Tento horní trojúhelníkový systém lze řešit s ohledem na . Podobný algoritmus pro řešení nejmenších čtverců lze získat pomocí SVD rozkladu. Výpočtem jemné expanze SVD a následným výpočtem vektoru redukujeme problém nejmenších čtverců na jednoduchý diagonální systém [1] :84 . Skutečnost, že řešení nejmenších čtverců lze získat pomocí QR rozkladu a SVD rozkladu, znamená, že kromě klasické metody normálních rovnic řešení úloh nejmenších čtverců lze tyto úlohy řešit také metodami včetně Gramova algoritmu -Schmidt a Householderovy metody. . $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$

Podmíněnost a výpočetní stabilita

Uvažujme funkci , kde je normovaný vektorový prostor dat a je normovaný vektorový prostor řešení. V určitém okamžiku se problém nazývá špatně podmíněný, pokud malá porucha vede k velké změně hodnoty . Můžeme to kvantifikovat určením čísla podmínky , které udává, jak dobře je problém podmíněn. Definujme to jako $f:X\to Y$ $X$ $Y$ $x\in X$ $X$ $f(x)$

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

Nestabilita je tendence počítačových algoritmů, které se spoléhají na aritmetiku s plovoucí desetinnou čárkou, aby produkovaly výsledky, které se ostře liší od přesného matematického řešení problému. Když matice obsahuje reálná data s mnoha platnými číslicemi, mnoho algoritmů pro řešení problémů, jako jsou lineární soustavy rovnic nebo optimalizace nejmenších čtverců, může vést k velmi nepřesným výsledkům. Vytvoření stabilních algoritmů pro špatně podmíněné problémy je ústředním problémem numerické lineární algebry. Jedním příkladem je, že stabilita metody Householderova odrazu činí z algoritmu robustní metodu pro řešení lineárních systémů, zatímco nestabilita metody normální rovnice pro řešení problémů nejmenších čtverců je důvodem pro výběr metod rozkladu matic, jako je použití rozkladu SVD. Některé metody rozkladu matrice mohou být nestabilní, ale mají jednoduché úpravy, aby byly stabilní; například nestabilní Gram-Schmidtova metoda, kterou lze snadno upravit tak, aby se získala stabilní Gram-Schmidtova modifikace [1] :140 . Dalším klasickým problémem v numerické lineární algebře je, že Gaussova metoda je nestabilní, ale se zavedením pivotu se stává stabilní.

Iterační metody

Existují dva důvody, proč jsou iterační algoritmy důležitou součástí numerické lineární algebry. Za prvé, mnoho numerických problémů nemá přímé řešení; k nalezení vlastních hodnot a vlastních vektorů libovolné matice můžeme použít pouze iterační přístup. Za druhé, neiterativní algoritmy pro libovolnou matici vyžadují čas, který je neočekávaně dlouhý, vzhledem k tomu, že matice obsahují pouze čísla. Iterační přístupy mohou využívat některé vlastnosti matic ke zkrácení této doby. Například, když je matice řídká , iterační algoritmus může přeskočit mnoho kroků, které musí přímý přístup následovat, i když jsou nadbytečné. $m \krát m$ $O(m^{3})$ $m^{2}$

Jádrem mnoha iteračních metod v numerické lineární algebře je projekce matice do nižšího , nízkorozměrného Krylovova podprostoru , což umožňuje aproximovat charakteristiky vysokorozměrné matice iterativním výpočtem ekvivalentních charakteristik podobných matic, počínaje nízkorozměrným prostorem a postupně přecházet do vyšších dimenzí. Když je symetrický a chceme vyřešit lineární problém , klasickým iteračním přístupem je metoda konjugovaného gradientu . Pokud nejsou symetrické, pak příklady iterativních řešení lineárního problému jsou zobecněná metoda minimálního rezidua (GMRES) a metoda konjugovaného gradientu pro normální rovnice (CGN) pro normální rovnice. Pokud je symetrický, pak můžeme použít Lanczosův algoritmus k nalezení vlastních čísel a vlastních vektorů , a pokud symetrický není, použije se Arnoldiho iterace . $A$ $sekera=b$ $A$ $A$ $A$

Software pro numerickou analýzu

Některé programovací jazyky používají optimalizační metody numerické lineární algebry a jsou navrženy tak, aby implementovaly její algoritmy. Mezi tyto jazyky patří MATLAB , Analytica, Maple a Mathematica . Jiné programovací jazyky, které nejsou explicitně navrženy pro numerickou lineární algebru, mají knihovny, které poskytují rutiny a optimalizace; C a Fortran mají základní podprogramy lineární algebry a balíčky LAPACK , python má knihovnu NumPy a Perl má datový jazyk Perl . Mnoho příkazů numerické lineární algebry v R se spoléhá na základní knihovny, jako je LAPACK [5] .

Odkazy

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Trefethen Lloyd, Bau III David. Numerická lineární algebra (1. vydání) (anglicky) . - Philadelphia: SIAM, 1997. - ISBN 978-0-89871-361-9 .
↑ 1 2 3 4 Golub, Gene H. Historie moderní numerické lineární algebry . Oddělení statistiky University of Chicago . Staženo: 17. února 2019. (neurčitý)
↑ von Neumann, John; Goldstine, Herman H. (1947). “Numerická inverze matic vyššího řádu” (PDF) . Bulletin Americké matematické společnosti . 53 (11): 1021-1099. DOI : 10.1090/s0002-9904-1947-08909-6 . S2CID 16174165 . Archivováno z originálu (PDF) dne 2019-02-18 . Staženo 17. února 2019 . Použitý zastaralý parametr |url-status=( nápověda )
↑ 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 a lineární algebra . R-blogeři (29. srpna 2013). Staženo: 17. února 2019. (neurčitý)