Krylovský podprostor - Krylov subspace - Wikipedia

v lineární algebra, objednávka-r Krylovský podprostor generované n-podle-n matice A a vektor b dimenze n je lineární podprostor překlenul podle snímky z b pod první r pravomoci A (začínající od ${ displaystyle A ^ {0} = I}$), to znamená,

${ displaystyle { mathcal {K}} _ {r} (A, b) = operatorname {span} , {b, Ab, A ^ {2} b, ldots, A ^ {r-1} b }. ,}$^[1]

Pozadí

Pojem je pojmenován podle ruského aplikovaného matematika a námořního inženýra Alexej Krylov, který o tom publikoval článek v roce 1931.^[2]

Vlastnosti

• ${ displaystyle { mathcal {K}} _ {r} (A, b), A { mathcal {K}} _ {r} (A, b) podmnožina { mathcal {K}} _ {r + 1} (A, b)}$.
• Vektory ${ displaystyle {b, Ab, A ^ {2} b, ldots, A ^ {r-1} b }}$ jsou lineárně nezávislé až do ${ displaystyle r$, a ${ displaystyle { mathcal {K}} _ {r} (A, b) podmnožina { mathcal {K}} _ {r_ {0}} (A, b)}$. ${ displaystyle r_ {0}}$ je maximální rozměr krylovského podprostoru.
• Pro takové ${ displaystyle r_ {0}}$ my máme ${ displaystyle r_ {0} leq 1+ mathrm {hodnost} A}$ a ${ displaystyle r_ {0} leq n}$přesněji ${ displaystyle r_ {0} leq částečné p (A)}$^{[je zapotřebí objasnění ]}, kde ${ displaystyle p (A)}$ je minimální polynom z ${ displaystyle A}$.
• Existuje a ${ displaystyle b}$ takhle ${ displaystyle r_ {0} = částečné p (A)}$.
• ${ displaystyle { mathcal {K}} _ {r} (A, b)}$ je cyklický submodul generovaný ${ displaystyle b}$ z kroucení ${ displaystyle k [x]}$-modul ${ displaystyle (k ^ {n}) ^ {A}}$, kde ${ displaystyle k ^ {n}}$ je lineární prostor na ${ displaystyle k}$.
• ${ displaystyle k ^ {n}}$ lze rozložit jako přímý součet krylovských podprostorů.

Použití

Krylovské podprostory se používají v algoritmech pro hledání přibližných řešení problémů vysokodimenzionální lineární algebry.^[1]

Moderní iterační metody pro nalezení jedné (nebo několika) vlastních čísel velkých řídké matice nebo řešení velkých soustav lineárních rovnic se vyhněte operacím matice-matice, ale spíše vynásobte vektory maticí a pracujte s výslednými vektory. Počínaje vektorem, b, jeden počítá ${ displaystyle Ab}$, pak jeden vynásobí tento vektor ${ displaystyle A}$ najít ${ displaystyle A ^ {2} b}$ a tak dále. Všechny algoritmy, které takto fungují, jsou označovány jako krylovské podprostorové metody; patří mezi nejúspěšnější metody v současné době dostupné v numerické lineární algebře.

Problémy

Protože vektory se obvykle brzy stanou téměř lineárně závislé vzhledem k vlastnostem iterace výkonu, metody spoléhající se na krylovský podprostor často zahrnují některé ortogonalizace schéma, jako je Lanczosova iterace pro Hermitovské matice nebo Arnoldiho iterace pro obecnější matice.

Stávající metody

Nejznámější krylovské podprostorové metody jsou Arnoldi, Lanczos, Konjugovaný gradient, IDR (Indukované zmenšení rozměrů), GMRES (zobecněný minimální zbytek), BiCGSTAB (gradient biconjugate stabilizovaný), QMR (kvazi minimální reziduum), TFQMR (QMR bez transpozice) a MINRY (minimální zbytkové) metody.

Viz také

• Iterační metoda, který obsahuje část o krylovských podprostorových metodách

Reference

Další čtení

• Nevanlinna, Olavi (1993). Konvergence iterací pro lineární rovnice. Přednášky z matematiky ETH Zürich. Basilej: Birkhäuser Verlag. str. viii + 177 str. ISBN  3-7643-2865-7. PAN  1217705.
• Saad, Yousef (2003). Iterační metody pro řídké lineární systémy (2. vyd.). SIAM. ISBN  0-89871-534-2. OCLC  51266114.
• Gerard Meurant a Jurjen Duintjer Tebbens: „Krylovovy metody pro nesymetrické lineární systémy - od teorie k výpočtům“, Springer Series in Computational Mathematics, sv. 57, (říjen 2020). ISBN  978-3-030-55250-3, url =https://doi.org/10.1007/978-3-030-55251-0.
• Iman Farahbakhsh: „Krylovské podprostorové metody s aplikací v nestlačitelných kapalných rozpouštědlech“, Wiley, ISBN  978-1119618683 (Září, 2020).