일반화 최소 잔차법

수학에서 일반화된 최소 잔차법(GMRES)은 선형 방정식의 무한 비대칭 시스템의 수치 해법에 대한 반복적인 방법이다.이 방법은 최소한의 잔류물로 Krylov 하위공간의 벡터에 의해 용액을 근사한다.아놀디 반복은 이 벡터를 찾는데 사용된다.null

GMRES 방법은 1986년 유세프 사드와 마틴 H. 슐츠에 의해 개발되었다.^[1]1975년 페이지와 손더스에 의한 MINRES 방식의 일반화·개선이다.^[2][3]MINRES 방법은 행렬이 대칭이어야 하지만 벡터 3개만 취급하면 된다는 장점이 있다.GMRES는 1980년 피터 풀레이가 개발한 DIIS 방식의 특수한 사례다.DIIS는 비선형 시스템에 적용된다.null

방법

모든 벡터 v의 유클리드 규범을 $\Vert {\displaystyle }$ ${\displaystyle v}$ ${\displaystyle \Vert }$ ${\displaystyle$\$v\ }$로 나타내며$,$ 다음에 의해 해결될 선형 방정식의 (제곱) 시스템을 나타낸다.

$(\displaystyle Ax=b.\,}$

매트릭스 A는 m-by-m 크기의 변환 불가능한 것으로 가정한다.더욱이, ${\displaystyle b}$가 정규화된 것으로 가정한다. ${\displaystyle \mathrm{즉}}$, $\Vert {\displaystyle }$ b ${\displaystyle \Vert }$= 1 $[\displaystyle$\$b\ =1$

이 문제에 대한 N-th Krylov 하위 공간은

${\displaystyle K_{n}=K_{n}(A,r_{0})=\span}\,\{r_{0},Ar_{0},A^{2}r_{0},\dots,A^{n-1}r_{0}\}.\,}$

여기서 $r{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$= ${\displaystyle b}$- ${\displaystyle {a\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ 0 ${\$0}} 초기 추측 x $x{\displaystyle {}_{}}$ 0$$ 0${\displaystyle {}_{}}${\$displaystyle x_{0}\neq$ 0$\}$이(가$)$ 주어진$$ 초기 오류임$.$ x ${\displaystyle {0\mathrm{}}_{}}$ =${\displaystyle {}_{}0}$이면$$r $0$ =${\displaystyle {}_{}{b\mathrm{}}_{}}$ ${\$$displaystyle$ $r_$${0}$

GMRES는 잔류 $r{\displaystyle {}_{}}$ =${\displaystyle {}_{}b}$ =${\displaystyle b_{}}$ =$b$= b의 유클리드 규범을 최소화하는 벡터 $x{\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle K_{}}$ ${\displaystyle {}_{}}$ K ${\$$displaystyle$ $x_{n}\in K_{n}}}$에 의한 $A{\displaystyle }$ ${\displaystyle x}$= ${\displaystyle b}$ =$$b = $b-Ax_{n$의$정확$한 용액에 근사한다.

The vectors ${\displaystyle r_{0},Ar_{0},\ldots A^{n-1}r_{0}}$ might be close to linearly dependent, so instead of this basis, the Arnoldi iteration is used to find orthonormal vectors ${\displaystyle q_{1},q_{2},\ldots ,q_{n}\,}$ which form a basis for ${\displaystyle K_{}}$${\displaystyle n_{}}$ ${\$ 특히 ${\displaystyle {q\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$= ${\displaystyle {}_{}{}_{}^{}}$ r ${\displaystyle {0\mathrm{}}_{}^{}}$ -${\displaystyle 1_{}^{}}$ r ${\displaystyle {0\mathrm{}}_{}}$ ${\$

Therefore, the vector ${\displaystyle x_{n}\in K_{n}}$ can be written as ${\displaystyle x_{n}=x_{0}+Q_{n}y_{n}}$ with ${\displaystyle y_{n}\in \mathbb {R} ^{n}}$, where ${\displaystyle Q_{n}}$ is the m-by-n matrix formed by ${\displaystyle q_1,\dots ,{}_{}}$${\displaystyle q_{}}$ n ${\$

또한 아놀디 프로세스는 (${\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle n+1})-$${\displaystyle }$ ${\displaystyle n}$ 상부$$ 헤센베르크 $행렬{\displaystyle {\stackrel{}{}}_{}}$ H${\displaystyle {\stackrel{}{}}_{}}$~ n ${\$을(를) 생성한다.

${\displaystyle AQ_{n}=Q_{n+1}{\tilde{H}_{n}\,}$

대칭 행렬의 경우 대칭 3-대칭 행렬이 실제로 달성되어 최소 행렬이 발생한다.null

${\displaystyle {Qn}_{}}$ ${\$의 컬럼이 정형이기$$ 때문에,

${\displaystyle \ r_{n}\ =\ b-Ax_{n}\ =\ b-A(x_{0}+Q_{n}y_{n})\ =\ r_{0}-AQ_{n}y_{n}\ =\ \beta q_{1}-AQ_{n}y_{n}\ =\ \beta q_{1}-Q_{n+1}{\tilde {H}}_{n}y_{n}\ =\ Q_{n+1}(\beta e_{1}-{\tilde {H}}_{n}y_{n})\ =\ \beta e_{1}-{\tilde {H}}_{n}y_{n}\ ,\,}$

어디에

${\displaystyle e_{1}=(1,0,0,\ldots,0)^{{T}\,}$

$R{\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {}^{}}$+ ${\displaystyle 1^{}}$ ${\$의 표준 기반에 있는 첫 번째 벡터 입니다$.$

${\displaystyle \cHB =\ r_{0}\\...}$

${\displaystyle r_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$ 첫 번째 시행 벡터(일반적으로$$ 0).따라서 잔존의 유클리드 규범을 $최소화함$으로써 x ${\displaystyle n_{}}$ ${\$을(를) 찾을 수 있다$$.

${\displaystyle r_{n}={\tilde {H}_{n}y_{n}-\beta e_{1}.}$

이것은 n 크기의 선형 최소 제곱 문제다.

이것은 GMRES 방법을 산출한다.$n{\displaystyle }$ ${\displaystyle n}$ -th$$ 반복 시:

1. ${\displaystyle {qn}_{}}$ ${\$를 Arnoldi$$ 방법으로 계산한다.
2. $\Vert {\displaystyle }$ ${\displaystyle {}_{}}$ $‖{\$$displaystyle$ \$r_{n}\}$; 최소화하는$$ ${\displaystyle y_{}}$ ${\$$displaystyle$\ r_{$n}}}$을(를) 찾으십시오.
3. ${\displaystyle {}_{}}$ x ${\displaystyle {n\mathrm{}}_{}{}_{}}$= 0${\displaystyle {}_{}}$+ Q ${\displaystyle n_{}}$ ${\displaystyle y_{}}$ ${\$;
4. 잔차가 아직 충분히 작지 않으면 반복한다.

반복할 때마다 매트릭스 벡터 제품 $Aq{\displaystyle }$ ${\displaystyle n_{}}$ ${\$을 계산해야 한다$$.이것은 크기 $m{\displaystyle }$ ${\displaystyle m}$의 일반 밀도 행렬에 대해 약 ${\displaystyle {}^{}}$ ${\$의 부동$$ 소수점 연산이 필요하지만, 희박한 행렬에 대해서는$$ $비용$이 O${\displaystyle }$( ${\displaystyle m}$) ${\displaystyle$ O$(m)}$로 감소할 수 있다$.$매트릭스 벡터 제품 외에 $O{\displaystyle }$(${\displaystyle n}$ m${\displaystyle }$) ${\displaystyle O(nm)}$ 부동 소수점$$ 연산을 n -th 반복에서 계산해야 한다.null

수렴

n번째 반복은 Krylov 하위공간 ${\displaystyle {Kn}_{}}$ ${\$의 잔차를 최소화한다$.$ 모든 하위공간은 다음 하위공간 안에 포함되기 때문에 잔차는 증가하지 않는다.m이 매트릭스 A의 크기인 m 반복 후에 Krylov space K는_m R의^m 전체로서 정확한 해법에 도달한다.그러나 소수의 반복(m에 상대적) 후에 벡터 x는_n 이미 정확한 용액에 대한 좋은 근사치가 된다는 생각이다.null

이것은 일반적으로 일어나지 않는다.실제로 Greenbaum, Ptak 및 Strakosh의 정리에서는 증가하지 않는 모든 시퀀스 a₁, …, a_m−1, a_m = 0에 대해 r_n = 모든 n에 대해_n a 행렬을 찾을 수 있으며, 여기서 r은_n 위에서 정의한 잔차다.특히 m - 1회 반복 시 잔차가 일정하게 유지되고 마지막 반복 시 0으로 떨어지는 행렬을 찾을 수 있다.null

그러나 실제로 GMRES는 종종 좋은 성과를 낸다.이것은 구체적인 상황에서 증명될 수 있다.A의 대칭 부분, 즉${\displaystyle }$(${\displaystyle A^{}}$ T${\displaystyle {}^{}}$+ ${\displaystyle A}$)${\displaystyle }$/ 2 ${\displaystyle (A^{T}+A)/2$}이$($가$)$ 양의 한정인 경우

${\displaystyle \ r_{n}\ \leq \leq (1-{\frac {\lambda _\\lambda _}^{{\min }^{2(A^{T}+A))}}}{\lambda _{\max }(A^{T}A)}}\오른쪽)^{n/2}\r_{0}\,}$

여기서 ${\displaystyle {\lambda m\mathrm{}}_{}}$ ${\displaystyle {\mathrm{i}}_{}}$ ${\displaystyle n{}_{}}$( M${\displaystyle }$) ${\displaystyle \lambda _{\mathrm {min}{}(M)}$ $및$ ${\displaystyle {\mathrm{am}}_{}}$ a (${\displaystyle M{)}_{}}$ x (M${\displaystyle )}$ ${\displaystyle \lambda _{\mathrmatrm}}}}(M$$)$은 각각 $행렬{\displaystyle }$ M ${\\\displaystystytytytytytytytym)$의 고유값 중 가장 작고 가장 큰 고유값을 나타낸다$$$.$^[4]null

A가 대칭적이고 확실하다면 우리는 심지어

${\displaystyle \ r_{n}\ \leq \left({\frac {\kappa _{2}-1}{2}-1}{2}-1}{2}(A)^{2}}\오른쪽)^{n/2}\ r_{0}\ .}$

여기서 $\kappa {\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$( ${\displaystyle A}$) ${\displaystyle \kappa _{2}(A)}$는 유클리드 표준에서 A의 조건 번호를 나타낸다.null

일반적으로 A가 확실하지 않은 경우, 우리는

${\displaystyle {\frac {\ r_{n}\ }{\ b\ }}\leq \inf _{p\in P_{n}}\ p(A)\ \leq \kappa _{2}(V)\inf _{p\in P_{n}}\max _{\lambda \in \sigma (A)} p(\lambda ) ,\,}$

여기서 P는_n p(0) = 1로 최대 n의 다항식 집합을 나타내고, V는 A의 스펙트럼 분해에 나타나는 행렬이며, σ(A)는 A의 스펙트럼이다.대략 A의 고유값이 원점에서 멀리 떨어져 군집되어 있고 A가 정규성에서 그리 멀지 않은 곳에 있을 때 빠른 수렴이 일어난다는 것이다.^[5]null

이 모든 불평등은 실제 오차 대신 잔차, 즉 현재 반복 x와_n 정확한 해법 사이의 거리만을 묶었다.null

메소드의 확장

다른 반복적 방법과 마찬가지로, GMRES는 융합 속도를 높이기 위해 전제조건화 방법과 결합된다.null

반복에 대한 비용은 O(n²)로 증가하며 여기서 n은 반복 번호다.따라서 이 방법은 초기 추측으로 x와_k 함께 k와 같은 숫자 뒤에 재시작되는 경우가 있다.결과적인 방법을 GMRES(k) 또는 Restarted GMRES라고 한다. 비양성 확정 행렬의 경우, 다시 시작된 서브스페이스가 이전 서브스페이스에 가까운 경우가 많기 때문에 이 방법은 융합에서 정체 상태에 시달릴 수 있다.null

GMRES와 다시 시작된 GMRES의 단점은 GCROT와 GMRODR와 같은 GMROT와 같은 GCRO 유형 방법에서 Krylov 하위 공간의 재활용에 의해 해결된다.^[6] GMRES에서 Krylov 하위 공간의 재활용 또한 선형 시스템의 시퀀스를 해결해야 할 때 융합을 가속화할 수 있다.^[7]null

다른 해결사와의 비교

아놀디 반복은 대칭 행렬에 대한 랭크조 반복으로 감소한다.대응하는 크릴로프 아공간법은 페이지와 손더스의 최소잔여법(MinRes)이다.비대칭 사례와 달리 MinRes 방법은 3개월의 재발 관계에 의해 주어진다.GMRES처럼 짧은 재발 관계에 의해 주어지지만 잔차의 규범을 최소화하는 일반 행렬에 대한 Krylov 하위 공간 방법이 없음을 알 수 있다.null

다른 종류의 방법은 비대칭 Lanczos 반복, 특히 BiCG 방법에 기초한다.이들은 3개월의 반복 관계를 사용하지만 최소 잔차를 달성하지 못하므로 이러한 방법에서 잔차는 단조롭게 감소하지 않는다.융합도 장담할 수 없다.null

세 번째 클래스는 CGS와 BiCSTAB와 같은 방법으로 형성된다.이것들은 또한 3개월의 재발 관계(헨스, 최적성 없이)로 작용하며 심지어 수렴을 달성하지 않고도 조기 종료할 수 있다.이러한 방법의 이면에 있는 아이디어는 반복 시퀀스의 생성 다항식을 적절하게 선택하는 것이다.null

이 세 가지 등급 중 어느 것도 모든 행렬에 가장 좋은 것은 아니다. 한 클래스가 다른 클래스를 능가하는 예는 항상 있다.따라서 주어진 문제에 대해 어떤 해결사가 최선인지를 알기 위해 여러 개의 해결사를 실제로 시도한다.null

최소 제곱 문제 해결

GMRES 방법의 한 부분은 최소화하는$$ 벡터 ${\displaystyle y_{}}$ ${\$를 찾는 것이다.

${\displaystyle \{\tilde{H}_{n}y_{n}-\beta e_{1}\,}$

$H{\displaystyle {\stackrel{}{}}_{}}$~ ${\displaystyle n_{}}$ ${\$는 (n + 1) by n 행렬이므로$$ n 미지의 경우 n+1 방정식의 과도한 구속 선형 시스템을 제공한다는 점에 유의하십시오.null

QR 분해를 사용하여 최소값을 계산할 수 있다: (n + 1)바이바이(n + 1) 직교 행렬 Ω_n 및 (n + 1)바이-앤 ${\displaystyle {상부}_{}}$ 삼각 행렬 $R{\displaystyle {\stackrel{}{}}_{}}$ ~${\$을 찾으십시오.

${\displaystyle \Oomega_{n}{{n}_{H}}={\tilde{R}_{n}.}$

삼각형 행렬은 열이 있는 것보다 한 행이 더 많으므로 맨 아래 행은 0으로 구성된다.따라서 다음과 같이 분해될 수 있다.

${\displaystyle {\tilde{R}_{n}={\begin{bmatrix}R_{n}\0\end{bmatrix},}$

여기서 ${\displaystyle {Rn}_{}}$ ${\$은(는) n-by-n(스퀘어) 삼각 행렬이다$$.null

Hessenberg 행렬은 0 행과 열로만 다르기 때문에 QR 분해는 한 반복에서 다음 반복으로 저렴하게 업데이트할 수 있다.

${\displaystyle {\tilde {H}_{n+1}={\begin{bmatrix}{{{H}_{n}_{n+1}\0&h_{n+2,n+1}\end{bmatrix},},}$

여기서_n+1 h = (h_1,n+1, …, h_n+1,n+1)^T이는 헤센베르크 행렬을 Ω으로_n, 0으로 증강하고, 복수 정체성을 가진 행으로, 거의 삼각형 행렬을 산출한다는 것을 의미한다.

${\displaystyle {\begin{bmatrix}\Oomega _{n}\0&1\end{bmatrix}{{{n+1}={\begin{bmatrix}R_{n}&r_{n+1}\0&\rho \sigmatrix}}}}}}}}}}}}}}}}}\bmatrix}}}}}}}}}}}}}}}}}}}}\bma \nsigmatrix}}}}}}}$

만약 σ이 0이라면 이것은 삼각형일 것이다.이를 치료하려면 기븐스 회전이 필요하다.

${\displaystyle G_{n}={\begin{bmatrix}I_{n}&0&0\\0&c_{n}s_{n}\0&s_{n}\0&-s_{n}&c_{n}\end{bmatrix}}}}}}}$

어디에

${\displaystyle c_{n}={\frac {\rho ^{2}+\rho ^{2}}:00\mbox{and}\n}={\frac {\sqrt{\rho ^{2}+\rho ^{2}}}}}}}}}$

이 기븐스 회전으로 우리는 형성된다.

${\displaystyle \Oomega _{n+1}=G_{n}{\begin{bmatrix}\Oomega _{n}&0\\0&1\end{bmatrix}}.}$

정말,

${\displaystyle \Omega _{n+1}{\tilde {H}}_{n+1}={\begin{bmatrix}R_{n}&r_{n+1}\\0&r_{n+1,n+1}\\0&0\end{bmatrix}}\quad {\text{with}}\quad r_{n+1,n+1}={\sqrt {\rho ^{2}+\sigma ^{2}}}}$

삼각행렬이다.null

QR 분해로 볼 때 최소화 문제는 다음과 같은 점에 유의하면 쉽게 해결된다.

${\displaystyle \ {\tilde {H}}_{n}y_{n}-\beta e_{1}\ =\ \Omega _{n}({\tilde {H}}_{n}y_{n}-\beta e_{1})\ =\ {\tilde {R}}_{n}y_{n}-\beta \Omega _{n}e_{1}\ .}$

벡터 $\beta {\displaystyle }$ ${\displaystyle {\mathrm{}}_{}}$ n ${\displaystyle {e\mathrm{}}_{}}$ 1 ${\$}을 나타내는$$ 방법

${\displaystyle {\tilde{g}_{n}={\\bmatrix}g_{n}\\nd{bmatrix}}}$

G_n ∈ R과ⁿ γ_n R으로, 이것은

${\displaystyle \ {\tilde {H}}_{n}y_{n}-\beta e_{1}\ =\ {\tilde {R}}_{n}y_{n}-\beta \Omega _{n}e_{1}\ =\left\ {\begin{bmatrix}R_{n}\\0\end{bmatrix}}y_{n}-{\begin{bmatrix}g_{n}\\\gamma _{n}\end{bmatrix}}\right\ .}$

이 식을 최소화하는 벡터 y는

${\displaystyle y_{n}=R_{n}^{-1}g_{n}.}$

벡터 ${\displaystyle g_{}}$ ${\$은(는) 업데이트하기$$ 쉽다.^[8]null

예시 코드

일반 GMRES(MATLAB/GNU 옥타브)

function [x, e] = gmres( A, b, x, max_iterations, threshold)  n = length(A);  m = max_iterations;  % use x as the initial vector  r = b - A * x;  b_norm = norm(b);  error = norm(r) / b_norm;  % initialize the 1D vectors  sn = zeros(m, 1);  cs = zeros(m, 1);  %e1 = zeros(n, 1);  e1 = zeros(m+1, 1);  e1(1) = 1;  e = [error];  r_norm = norm(r);  Q(:,1) = r / r_norm;  beta = r_norm * e1; %Note: this is not the beta scalar in section "The method" above but the beta scalar multiplied by e1  for k = 1:m  % run arnoldi  [H(1:k+1, k) Q(:, k+1)] = arnoldi(A, Q, k);    % eliminate the last element in H ith row and update the rotation matrix  [H(1:k+1, k) cs(k) sn(k)] = apply_givens_rotation(H(1:k+1,k),만약 임계 이 시점에서, k=m에 도달하지 않다 C, sn, k=,%,%오류를 e)[e오류]을 구합니다;만약(오류<>)임계치)방학, 끝% 끝나( 아니라 m+1)%y=H(1:k1:k))beta(1:k)결과를 계산하고, x=은 잔여 벡터 beta(k+1))-sn(k)*beta(k), beta(k))cs(k)*beta(k)오류)abs(베타(k+1))/b_norm를 업데이트합니다. x+ Q(:, 1:k) * y; end %----------------------------------------------------% %                  Arnoldi Function                  % %----------------------------------------------------% function [h, q] = arnoldi(A, Q, k)  q = A*Q(:,k); % Krylov Vector  for i = 1:k % Modified Gram-Schmidt, keeping the Hessenberg matrix  h(i) = q' * Q(:, i);  q = q - h(i) * Q(:, i); end h(k + 1) = norm(q); q = q / h(k + 1); end %------------------------------------------------------------------------------------------------------------------------------------------------------------------% 함수 [h, cs_k, sn_k, ap_k] = ap.ply for ith column  for i = 1:k-1  temp = cs(i) * h(i) + sn(i) * h(i + 1);  h(i+1) = -sn(i) * h(i) + cs(i) * h(i + 1);  h(i) = temp;  end  % update the next sin cos values for rotation  [cs_k sn_k] = givens_rotation(h(k), h(k + 1));  % eliminate H(i + 1, i)  h(k) = cs_k * h(k) + sn_k * h(k + 1);  h(k + 1) = 0.0; end %%----Calculate the Givens rotation matrix----%% function [cs, sn] = givens_rotation(v1, v2) %  if (v1 == 0) %    cs = 0; %    sn = 1; %  else  t = sqrt(v1^2 + v2^2); %    cs = abs(v1) / t; %    sn = cs * v2 / v1;  cs = v1 / t; % see http://www.netlib.org/eispack/comqr.f  sn = v2 / t; %  end end

참고 항목

• 비콘주게이트 그라데이션 방식

참조

메모들

• A. 마이스터, 오미자 글리충스스템임, 제2판 Vieweg 2005, ISBN 978-3-528-13135-7.
• Y. Saad, 희소 선형 시스템을 위한 반복 방법, 제2판, 산업 및 응용 수학 협회, 2003.ISBN 978-0-89871-534-7
• Y. Saad 및 M.H. Schultz, "GMRES: 비대칭 선형 시스템을 해결하기 위한 일반화된 최소 잔류 알고리즘", SIAM J. Sci. 통계분석 계산, 7:856–869, 1986. doi:10.1137/0907058.
• S. C. 아이젠스타트, H.C. 엘만 및 M.H. 슐츠, "선형 방정식의 비대칭 시스템에 대한 가변 반복 방법", SIAM 수치 분석 저널, 20(2), 345–357, 1983.
• J. 스토어와 R.Bulirsch, 2002년 뉴욕 Springer 3판 숫자 분석 소개.ISBN 978-0-387-95452-3.
• 로이드 N.Trefethen과 David Bau, III, 수치 선형 대수학, 산업 및 응용 수학 협회, 1997.ISBN 978-0-89871-361-9
• Dongarra 등 , 선형 시스템 솔루션 템플릿: 반복적 방법을 위한 빌딩 블록, 제2판, 필라델피아 SIAM, 1994
• 아미트, 아미트, 데 스터러, 에릭, ;위리도비치, 카타지나, 타프티, 다네쉬, 아후자, 카필(2015년)."CFD 애플리케이션을 위한 재활용 Krylov 하위 공간과 새로운 하이브리드 재활용 해결사"컴퓨터 물리학 저널 303: 222. doi:10.1016/j.jcp.2015.09.040