축차가속완화법

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

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

${\displaystyle A\mathbf {x} =\mathbf {b} }$

여기서

${\displaystyle A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{bmatrix}},\qquad \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\qquad \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{bmatrix}}.}$

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

${\displaystyle A=D+L+U,}$

여기서

${\displaystyle D={\begin{bmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}\end{bmatrix}},\quad L={\begin{bmatrix}0&0&\cdots &0\\a_{21}&0&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &0\end{bmatrix}},\quad U={\begin{bmatrix}0&a_{12}&\cdots &a_{1n}\\0&0&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &0\end{bmatrix}}.}$

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

${\displaystyle (D+\omega L)\mathbf {x} =\omega \mathbf {b} -[\omega U+(\omega -1)D]\mathbf {x} }$

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

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

${\displaystyle \mathbf {x} ^{(k+1)}=(D+\omega L)^{-1}{\big (}\omega \mathbf {b} -[\omega U+(\omega -1)D]\mathbf {x} ^{(k)}{\big )}=L_{w}\mathbf {x} ^{(k)}+\mathbf {c} ,}$

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

${\displaystyle x_{i}^{(k+1)}=(1-\omega )x_{i}^{(k)}+{\frac {\omega }{a_{ii}}}\left(b_{i}-\sum _{j<i}a_{ij}x_{j}^{(k+1)}-\sum _{j>i}a_{ij}x_{j}^{(k)}\right),\quad i=1,2,\ldots ,n.}$

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

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