비콘주게이트 구배 안정화 방법

이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 삭제하지 않고 비전문가가 이해할 수 있도록 개선하십시오.(2015년 5월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

수치 선형대수학에서, 종종 BiCSTAB로 약칭되는 비콘주게이트 구배 안정화 방법은 비대칭 선형 시스템의 수치해결을 위해 H. A. Van der Vorst가 개발한 반복적 방법이다.바이콘주게이트 그라데이션 방식(BiCG)의 변형이며, 기존 BiCG는 물론, 콘센트 그라데이션 스쿼드 방식(CGS) 등 다른 변형보다 빠르고 부드러운 수렴을 가지고 있다.그것은 크릴로프 아공간 방법이다.

알고리즘 단계

비조건 BiCSTAB

선형 시스템 = , BiCSTAB는 초기 추측으로 시작하여 다음과 같이 진행한다.

1. r₀ = b − Ax₀
2. (,r̂₀ ) ≠ 0, 예를 들어 = . (,)xy 벡터(,)xy의 도트 곱을 나타내는 임의 벡터를 선택하십시오.
3. ρ₀ =α=ω₀ = 1
4. v₀ = p₀ = 0
5. 용 = 1, 2, 3, …
   1. ρ_i= (r̂₀, r_i−1)
   2. β= (ρ_i/ρ_i−1)(α/ω_i−1)
   3. p_i= r_i−1 +β(p_i−1 −ω_i−1v_i−1)
   4. v_i= Ap_i
   5. α=ρ_i/(r̂₀,v_i)
   6. h= x_i−1 +αp_i
   7. 충분히 정확한 경우 =를 설정하고 종료하십시오.
   8. s=r_i−1 −αv_i
   9. t = As
   10. ω_i= (t,s)/(t,t)
   11. x_i=h+ω_is
   12. 충분히 정확하다면 그만둬라.
   13. r_i=s−ω_it

전제조건 BiCSTAB

전제조건은 대개 반복적인 방법의 수렴을 가속화하기 위해 사용된다.선형 시스템을 해결하기 위해 = 전제조건 = ≈ , 전제조건 BiCSTAB는 초기 추측으로 시작하여 다음과 같이 진행한다.

1. r₀ = b − Ax₀
2. (,r̂₀ ) ≠ 0, 예를 들어 =와 같은 임의 벡터를 선택하십시오.
3. ρ₀ =α=ω₀ = 1
4. v₀ = p₀ = 0
5. 용 = 1, 2, 3, …
   1. ρ_i= (r̂₀, r_i−1)
   2. β= (ρ_i/ρ_i−1)(α/ω_i−1)
   3. p_i= r_i−1 +β(p_i−1 −ω_i−1v_i−1)
   4. y = K −1
      2 K −1
      1 p_i
   5. v_i= Ay
   6. α=ρ_i/(r̂₀,v_i)
   7. h= x_i−1 +αy
   8. 충분히 정확한 경우 = 그리고 종료
   9. s = r_i−1 −αv_i
   10. z = K −1
       2 K −1
       1 s
   11. t = Az
   12. ω_i= (K −1
       1 t, K −1
       1 s)/(K −1
       1 t, K −1
       1 t)
   13. x_i=h+ω_iz
   14. 충분히 정확하다면 그만둬라.
   15. r_i= s −ω_it

이 공식은 명시적으로 전제된 시스템에 조건 없는 BiCSTAB를 적용하는 것과 동등하다.

Ãx̃ = b̃

는 = -11
-12
, =, 그리고 = -11
. 다시 말해서 이 공식으로 좌-우-우-예비 조건이 모두 가능하다.

파생

다항식 BiCG

BiCG에서 검색 방향 및 잔차 및 다음과 같은 반복 관계를 사용하여 업데이트된다.

p_i = r_i−1 + β_ip_i−1,

p̂_i = r̂_i−1 + β_ip̂_i−1,

r_i = r_i−1 − α_iAp_i,

r̂_i = r̂_i−1 − α_iA^Tp̂_i.

상수 및 이 선택됨

α_i = ρ_i/(p̂_i, Ap_i),

β_i=ρ_i/ρ_i−1

여기서 = (,r̂_i−1 )는 잔차 및 검색 방향이 각각 biorthogonality와 biconjugacy를 만족하도록 한다. 즉, ≠에 대해,

(r̂_i, r_j) = 0,

(p̂_i, Ap_j) = 0.

라는 것을 보여주는 것은 간단하다.

r_i = P_i(A)r₀,

r̂_i = P_i(A^T)r̂₀,

p_i+1 = T_i(A)r₀,

p̂_i+1 =T_i(A^T)r̂₀

여기서()A와()A는 에서 t-도 다항식이다.이러한 다항식들은 다음과 같은 재발 관계를 만족시킨다.

P_i(A) = P_i−1(A) − α_iAT_i−1(A),

T_i(A) = P_i(A) + β_i+1T_i−1(A).

BiCG에서 BiCSTAB의 도출

BiCG의 잔차 및 검색 방향을 명시적으로 추적할 필요는 없다.즉, BiCG 반복은 암묵적으로 수행할 수 있다.BiCGSTAB에서, 사람들은 다음에 대해 다시 관계를 갖기를 원한다.

r̃_i =Q_i(A)P_i(A)r₀

여기서 ()A = I()(-)(-)((-I )((-I )은 ()A보다 더 빠르고 부드러운 의 수렴을 가능하게 하기를 바라는 마음에서 ()A 대신 적절한 상수를 갖는 것이다.

()A와 ()A에 대한 재발 관계와 ()A에 대한 정의에서 비롯된다.

Q_i(A)P_i(A)r₀ = (I − ω_iA)(Q_i−1(A)P_i−1(A)r₀ − α_iAQ_i−1(A)T_i−1(A)r₀),

()AT_iAr₀에 대한 재발 관계의 필요성을 수반한다.이것은 또한 BiCG 관계에서 파생될 수 있다.

Q_i(A)T_i(A)r₀ = Q_i(A)P_i(A)r₀ + β_i+1(I − ω_iA)Q_i−1(A)P_i−1(A)r₀.

정의와 유사하게 BiCSTAB 정의

p̃_i+1 = Q_i(A)T_i(A)r₀.

벡터 형태로 쓰여, 다음에 대한 재발 관계 및 다음 사항.

p̃_i = r̃_i−1 + β_i(I − ω_i−1A)p̃_i−1,

r̃_i = (I − ω_iA)(r̃_i−1 − α_iAp̃_i).

에 대한 반복 관계를 도출하려면 정의하십시오.

s_i = r̃_i−1 − α_iAp̃_i.

다음에 대한 재발 관계는 다음과 같이 기록될 수 있다.

r̃_i = r̃_i−1 − α_iAp̃_i − ω_iAs_i,

에 해당하는

x_i = x_i−1 + α_ip̃_i + ω_is_i.

BiCSTAB 상수 결정

이제 BiCG 상수를 결정하고 적합한 를 선택하는 것이 남아있다.

BiCG의 경우, = /ρ_i−1 포함

ρ_i = (r̂_i−1, r_i−1) = (P_i−1(A^T)r̂₀, P_i−1(A)r₀).

BiCSTAB는 명시적으로 또는 를 추적하지 않기 때문에 이 공식에서 즉시 계산할 수 없다.그러나 스칼라와 관련이 있을 수 있다.

ρ̃_i = (Q_i−1(A^T)r̂₀, P_i−1(A)r₀) = (r̂₀, Q_i−1(A)P_i−1(A)r₀) = (r̂₀, r_i−1).

biorthogonality로 인해 = ()Ar₀는 ()A^Tr̂₀에 직교하며, 여기서 ()A^T는 도 - 2의 어떤 다항식이다. 따라서 (), (),P_i−1A^Tr̂₀ (),P_i−1Ar₀ ()의 도트 제품에서 ()A^T와 (),A^T (),Q_i−1A^Tr̂₀ (), (), ()의 가장 높은 순서 조건만이 중요하다.P_i−1Ar₀()A^T와 ()A^T의 선행 계수는 각각 (-1)⋯ⁱ⁻¹α₁α₂α_i−1과 (-1)⋯ⁱ⁻¹ω₁ω₂ω_i−1이다.그 뒤를 잇는다.

ρ_i = (α₁/ω₁)(α₂/ω₂)⋯(α_i−1/ω_i−1)ρ̃_i,

따라서

β_i = ρ_i/ρ_i−1 = (ρ̃_i/ρ̃_i−1)(α_i−1/ω_i−1).

에 대한 간단한 공식은 유사하게 도출될 수 있다.BiCG에서는

α_i = ρ_i/(p̂_i, Ap_i) = (P_i−1(A^T)r̂₀, P_i−1(A)r₀)/(T_i−1(A^T)r̂₀, AT_i−1(A)r₀).

위의 사례와 유사하게, 바이오토건성과 바이오주그제이션 덕분에 도트 제품에서 가장 높은 순서의 ()A^T와 ()A^T만 문제가 된다.우연히 ()A^T와 ()A^T는 같은 선행 계수를 가지고 있다.따라서 공식에서 ()A^T와 동시에 교체할 수 있어 다음과 같은 결과를 초래할 수 있다.

α_i = (Q_i−1(A^T)r̂₀, P_i−1(A)r₀)/(Q_i−1(A^T)r̂₀, AT_i−1(A)r₀) = ρ̃_i/(r̂₀, AQ_i−1(A)T_i−1(A)r₀) = ρ̃_i/(r̂₀, Ap̃_i).

마지막으로, BiCSTAB는 의 함수로 2-노른에서 = (I - s_i)를 최소화하도록 선택한다.이것은 다음에 달성된다.

((I - ) s_i= 0,

최적가치를 부여

ω_i = (As_i, s_i)/(As_i, As_i).

일반화

BiCSTAB는 BiCSG와 GMRES의 조합으로 볼 수 있으며, 여기서 각 BiCG 단계가 GMRES(1) (즉, 각 단계에서 GMRES가 재시작됨) 단계를 수행하여 CGS의 불규칙한 수렴 동작을 보수하는 것으로, BiCSTAB가 개발된 개선으로 볼 수 있다.그러나 도 1 최소 잔류 다항식을 사용하기 때문에 행렬에 큰 복잡한 고유점이 있는 경우 이러한 수리는 효과적이지 않을 수 있다.그러한 경우, BiCSTAB는 수치 실험에 의해 확인되었듯이 정체될 가능성이 있다.

어떤 사람은 이 상황을 더 높은 수준의 최소 잔류 다항식들이 더 잘 다룰 수 있다고 기대할 수 있다.이것은 BiCSTAB2를 포함한 알고리즘과 보다 일반적인 BiCSTAB()l^[2]를 발생시킨다.BiCSTAB()l에서 GMRES()l 단계는 모든 BiCG 단계를 따른다.BiCSTAB2는 BiCSTAB()l = 2와 동일하다.

참고 항목

• 비콘주게이트 그라데이션 방식
• 공차 그라데이션 제곱법
• 공차 그라데이션법

참조

• Van der Vorst, H. A. (1992). "Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems". SIAM J. Sci. Stat. Comput. 13 (2): 631–644. doi:10.1137/0913035. hdl:10338.dmlcz/104566.
• Saad, Y. (2003). "§7.4.2 BICGSTAB". Iterative Methods for Sparse Linear Systems (2nd ed.). SIAM. pp. 231–234. doi:10.2277/0898715342. ISBN 978-0-89871-534-7.
• ^ Gutknecht, M. H. (1993). "Variants of BICGSTAB for Matrices with Complex Spectrum". SIAM J. Sci. Comput. 14 (5): 1020–1033. doi:10.1137/0914062.
• ^ Sleijpen, G. L. G.; Fokkema, D. R. (November 1993). "BiCGstab(l) for linear equations involving unsymmetric matrices with complex spectrum" (PDF). Electronic Transactions on Numerical Analysis. Kent, OH: Kent State University. 1: 11–32. ISSN 1068-9613. Archived from the original (PDF) on 2011-06-06. Retrieved 2010-02-07.