축차가속완화법

틀:위키데이터 속성 추적 축차가속완화법(逐次加速緩和法,successive over-relaxation,SOR)은 가우스-자이델 방법의 수렴성을 가속시키는 반복법이다.

공식

n개의 선형방정식과 미지수 x를 가진 사각형 시스템에서:

$A𝐱=𝐛$

여기서

$A=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right],𝐱=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right],𝐛=\left[\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_n\end{array}\right].$

A는 대각성분 D, 하삼각행렬 부분 L, 상삼각행렬 부분 U의 합으로 행렬 분리될 수 있다.:

$A=D+L+U,$

여기서

$D=\left[\begin{array}{cccc}{a}_{11}& 0& \cdots & 0\\ 0& a_{22}& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & a_{nn}\end{array}\right],L=\left[\begin{array}{cccc}0& 0& \cdots & 0\\ a_{21}& 0& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & 0\end{array}\right],U=\left[\begin{array}{cccc}0& a_{12}& \cdots & a_{1n}\\ 0& 0& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 0\end{array}\right].$

연립방정식을 아래와 같이 다시 쓰자.

$(D+\omega L)𝐱=\omega 𝐛-[\omega U+(\omega -1)D]𝐱$

상수 ω를 완화계수(relaxation factor)라고 하는데, 가우스-자이델 방법은 ω=1에 해당한다. 가우스-자이델 방법보다 x를 빠르게 바꾸는 가속완화(over-relaxation)를 위해서는 ω > 1이어야 한다. 반대로 ω < 1인 경우는 감속완화(under-relaxation)이라고 한다.

축차가속완화법은 왼쪽에 새로운 x를 놓고, 이전의 x는 오른쪽에 놓는 반복법이다. 해석학적으로, 다음과 같이 설명할 수 있다.

${𝐱}^{(k+1)}=(D+\omega L{)}^{-1}(\omega 𝐛-[\omega U+(\omega -1)D]{𝐱}^{(k)})=L_w{𝐱}^{(k)}+𝐜,$

여기서 ${𝐱}^{(k)}$는 $𝐱$ 의 k번째 근사 또는 반복이고, ${𝐱}^{(k+1)}$는 $𝐱$ 의 k+1번째 근사이다. 하지만 (D+ωL)이 하삼각행렬임을 활용하기 위해, x^(k+1)의 각 원소는 전진대입(forward substitution)을 통해 순차적으로 구할 수 있다.:

$x_i^{(k+1)}=(1-\omega )x_i^{(k)}+\frac{\omega }{a_{ii}}(b_i-\sum _{j<i}{a}_{ij}{x}_j^{(k+1)}-\sum _{j>i}{a}_{ij}{x}_j^{(k)}),i=1,2,\dots ,n.$

수렴성

1947년에 대칭 정부호 행렬에서는 $\rho (L_{\omega })<1$ 가 $0<\omega <2$일 때 성립함이 보여져, $0<\omega <2$이면 감속완화이든 가속완화이든 수렴한다는게 보여졌다. $\omega$가 1보다 조금 클때 가장 수렴이 빠르다.

같이 보기

• 가우스-자이델 방법
• 야코비 방법
• 대칭축차가속완화법
• 리처드슨 외삽법