크릴로프 아공간

선형대수학에서 n-by-n 행렬 A와 치수 b에 의해 생성된 순서 r Krylov 하위공간은 A의 첫 번째 r $힘{\displaystyle {}^{}}$(${\displaystyle {A\mathrm{}}^{}}$ 0 =${\displaystyle {}^{}}$I ${\displaystyle A^{0}=I})$에서 b의 영상에 의해 확장된 선형 하위공간이다.$$^[1]

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

배경

이 개념은 1931년 그것에 관한 논문을 발표한 러시아의 응용 수학자 겸 해군 엔지니어 알렉세이 크릴로프의 이름을 따서 명명되었다.^[2]

특성.

• ${\displaystyle {\mathcal {\k}_{r}(A,b),$$A{\mathcal{K}_{r}(A,b)\subset {\mathcal {K}_{r+1}(A,b)}$.
• 벡터${\displaystyle }${ ${\displaystyle b}$, ${\displaystyle A}$ ${\displaystyle b}$, ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$ b${\displaystyle }$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle {}^{}}$ ${\displaystyle r^{}}$- 1 ${\displaystyle {}^{}}$ ${\displaystyle \}}$ ${\displaystyle \{b,Ab,$$A^{2}b,\ldots ,A^{r-1}b\}}$ are linearly independent until ${\displaystyle r<r_{0}}$, and ${\displaystyle {\mathcal {K}}_{r}(A,b)\subset {\mathcal {K}}_{r_{0}}(A,b)}$. Thus, ${\displaystyle r_{0}}$ denotes the maximal dimension of a Krylov subspace.
• 최대 치수는 $r{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle 1}$+ ${\displaystyle \mathrm{랭크}}$ ${\displaystyle r_{0}\leq$ 1$+\operatorname$ {$rank}$ A$}$및 $r$ 0${\displaystyle {}_{}\mathrm{0n}}$ ${\displaystyle r_{0}\leq$ n$}$을 만족한다$.$
• More exactly, ${\displaystyle r_{0}\leq \deg[p(A)]}$, where ${\displaystyle p(A)}$ is the minimal polynomial of ${\displaystyle A}$. Furthermore, there exists a ${\displaystyle b}$ such that ${\displaystyle r_{0}=\deg[p(A)]}$.
• ${\displaystyle {\mathcal{K}}_{}}$ ${\displaystyle r_{}}$( ${\displaystyle A}$, ${\displaystyle b}$) ${\displaystyle {\mathcal {K}_{r}(A,b)}$은(는) ${\displaystyle \mathrm{비틀림<img\; alt="b"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/f11423fbb2e967f986e36804a8ae4271734917c3"\; style="vertical-align:\; -0.338ex;\; width:0.998ex;\; height:2.176ex;">}}$ $k{\displaystyle }$[ x$$ ${\displaystyle k[x$]} -module$$${\displaystyle }$(${\displaystyle k^{}{}^{}}$n ) ${\displaystyle A^{}}$ ${\$$A$ 여기서 $k{\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\$는 k ${\displaystyle k}$의 선형 공간이다$.$
• ${\displaystyle k^{}}$ ${\displaystyle n^{}}$ ${\$은(는) 크릴로프 서브스페이스의 직접 합으로 분해할 수 있다$$.

사용하다

Krylov 하위공간은 고차원 선형 대수 문제에 대한 대략적인 해결책을 찾기 위한 알고리즘에 사용된다.^[1]

아놀디 반복과 같은 현대의 반복적 방법은 큰 희소 행렬의 (또는 몇 개의) 고유값을 찾거나 선형 방정식의 큰 시스템을 해결하는 데 사용될 수 있다. 그들은 매트릭스-매트릭스 연산을 피하려고 하지만 오히려 벡터에 매트릭스를 곱하고 결과 벡터로 작업한다. 벡터 $b{\displaystyle }$ ${\displaystyle b}$에서 $시작$하여 ${\displaystyle A}$ b$${\$displaystyle Ab}$을(를) 계산한 다음$,$ $A{\displaystyle }${\$displaystyle A}$을(를) $곱하여$ A ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle A^{2$}b$}$ 등을$$ 찾는다$.$ 이런 식으로 작용하는 모든 알고리즘을 Krylov 하위공간 방법이라고 한다; 그것들은 현재 수치 선형대수학에서 이용할 수 있는 가장 성공적인 방법들 중 하나이다.

문제들

벡터는 대개 전력 반복의 특성 때문에 거의 곧 선형적으로 의존하게 되기 때문에, 크릴로프 하위 공간에 의존하는 방법은 종종 은둔자 행렬을 위한 Lanczos 반복이나 보다 일반적인 행렬을 위한 Arnoldi 반복과 같은 어떤 직교화 체계를 포함한다.

기존 방법

가장 잘 알려진 크릴로프 아공간법은 아놀디, 랭크조스, 콘게이트 그라데이션, IDR(유인 치수 감소), GMRES(일반화된 최소 잔차), BiCSTAB(바이콘주게이트 그라데이션 안정화), QMR(Quasi 최소 잔차), TFQMR(투과 프리 QMR), 최소 잔차 방법이다.

참고 항목

• Krylov 하위 공간 방법에 대한 섹션이 있는 반복적 방법

참조

추가 읽기

• Nevanlinna, Olavi (1993). Convergence of iterations for linear equations. Lectures in Mathematics ETH Zürich. Basel: Birkhäuser Verlag. pp. viii+177 pp. ISBN 3-7643-2865-7. MR 1217705.
• Saad, Yousef (2003). Iterative methods for sparse linear systems (2nd ed.). SIAM. ISBN 0-89871-534-2. OCLC 51266114.
• Gerard Meurant와 Jurijen Duintjer Tebbens: "비대칭 선형 시스템을 위한 크릴로프 방법 - 이론에서 계산까지", 계산 수학의 Springer 시리즈, vol.57, (202020년 10월) ISBN 978-3-030-55250-3, url=https://doi.org/10.1007/978-3-030-55251-0
• Iman Farahbakhsh: "압축 불가능한 유체 흐름 솔버에 적용된 Krylov Subspace Methods in Uncluid Flow Solvers," Wiley, ISBN 978-1119618683 (2020년 9월)