축차가속완화법 문서 원본 보기

{{위키데이터 속성 추적}}
'''축차가속완화법'''(逐次加速緩和法,successive over-relaxation,SOR)은 [[가우스-자이델 방법]]의 수렴성을 가속시키는 [[반복법]]이다.
== 공식 ==
''n''개의 선형방정식과 미지수 '''x'''를 가진 사각형 시스템에서:

:<math>A\mathbf x = \mathbf b</math>

여기서

:<math>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}.</math>

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

:<math>A=D+L+U, </math>
여기서
:<math>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}. </math>

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

:<math>(D+\omega L) \mathbf{x} = \omega \mathbf{b} - [\omega U + (\omega-1) D ] \mathbf{x} </math>

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

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

:<math> \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}, </math>

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

:<math> x^{(k+1)}_i  = (1-\omega)x^{(k)}_i + \frac{\omega}{a_{ii}} \left(b_i - \sum_{j<i} a_{ij}x^{(k+1)}_j - \sum_{j>i} a_{ij}x^{(k)}_j \right),\quad i=1,2,\ldots,n. </math>

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

== 같이 보기 ==
* [[가우스-자이델 방법]]
* [[야코비 방법]]
* [[대칭축차가속완화법]]
* [[리처드슨 외삽법]]

[[분류:수치선형대수학]]
[[분류:완화법 (반복법)]]