축차가속완화법 (逐次加速緩和法,successive over-relaxation,SOR)은 가우스-자이델 방법 의 수렴성을 가속시키는 반복법 이다.
n 개의 선형방정식과 미지수 x 를 가진 사각형 시스템에서:
A
x
=
b
{\displaystyle A\mathbf {x} =\mathbf {b} }
여기서
A
=
[
a
11
a
12
⋯
a
1
n
a
21
a
22
⋯
a
2
n
⋮
⋮
⋱
⋮
a
n
1
a
n
2
⋯
a
n
n
]
,
x
=
[
x
1
x
2
⋮
x
n
]
,
b
=
[
b
1
b
2
⋮
b
n
]
.
{\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 의 합으로 행렬 분리 될 수 있다.:
A
=
D
+
L
+
U
,
{\displaystyle A=D+L+U,}
여기서
D
=
[
a
11
0
⋯
0
0
a
22
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
a
n
n
]
,
L
=
[
0
0
⋯
0
a
21
0
⋯
0
⋮
⋮
⋱
⋮
a
n
1
a
n
2
⋯
0
]
,
U
=
[
0
a
12
⋯
a
1
n
0
0
⋯
a
2
n
⋮
⋮
⋱
⋮
0
0
⋯
0
]
.
{\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}}.}
연립방정식을 아래와 같이 다시 쓰자.
(
D
+
ω
L
)
x
=
ω
b
−
[
ω
U
+
(
ω
−
1
)
D
]
x
{\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 는 오른쪽에 놓는 반복법 이다. 해석학적으로, 다음과 같이 설명할 수 있다.
x
(
k
+
1
)
=
(
D
+
ω
L
)
−
1
(
ω
b
−
[
ω
U
+
(
ω
−
1
)
D
]
x
(
k
)
)
=
L
w
x
(
k
)
+
c
,
{\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} ,}
여기서
x
(
k
)
{\displaystyle \mathbf {x} ^{(k)}}
x
{\displaystyle \mathbf {x} }
k 번째 근사 또는 반복이고,
x
(
k
+
1
)
{\displaystyle \mathbf {x} ^{(k+1)}}
x
{\displaystyle \mathbf {x} }
k+1 번째 근사이다.
하지만 (D +ωL )이 하삼각행렬 임을 활용하기 위해, x (k +1) 의 각 원소는 전진대입(forward substitution)을 통해 순차적으로 구할 수 있다.:
x
i
(
k
+
1
)
=
(
1
−
ω
)
x
i
(
k
)
+
ω
a
i
i
(
b
i
−
∑
j
<
i
a
i
j
x
j
(
k
+
1
)
−
∑
j
>
i
a
i
j
x
j
(
k
)
)
,
i
=
1
,
2
,
…
,
n
.
{\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년에 대칭 정부호 행렬 에서는
ρ
(
L
ω
)
<
1
{\displaystyle \rho (L_{\omega })<1}
0
<
ω
<
2
{\displaystyle 0<\omega <2}
0
<
ω
<
2
{\displaystyle 0<\omega <2}
ω
{\displaystyle \omega }
![{\displaystyle (D+\omega L)\mathbf {x} =\omega \mathbf {b} -[\omega U+(\omega -1)D]\mathbf {x} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e83bbf90bf4402a87819cdff801fb3c075eeb46)
![{\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} ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee7574980404f589965d6027b5f20112270e84d0)
