축차가속완화법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 공식
3. 수렴성
4. 알고리즘
5. 예제
6. 대칭 축차 가속 완화법 (SSOR)
7. 활용
참조

1. 개요

축차 가속 완화법(Successive Over-Relaxation, SOR)은 선형 연립 방정식을 풀기 위한 반복법의 일종이다. 이 방법은 가우스-자이델 방법의 개선된 형태로, 완화 계수(ω)를 사용하여 수렴 속도를 향상시킨다. ω > 1인 경우를 가속 완화, ω < 1인 경우를 감속 완화라고 한다. SOR은 대칭 정부호 행렬에서 0 < ω < 2일 때 수렴이 보장되며, 최적 완화 인자를 통해 수렴 속도를 극대화할 수 있다. SOR 방법은 알고리즘, 예제, 대칭 축차 가속 완화법(SSOR) 및 활용 분야에 대한 설명과 함께, 유사한 기술이 다른 반복적인 방법에도 적용될 수 있다는 점을 제시한다.

더 읽어볼만한 페이지

완화법 (반복법) - 야코비 방법
야코비 방법은 n개의 선형 방정식 시스템 해를 구하기 위해 행렬을 분리하여 반복적으로 해를 근사 계산하며, 대각 지배 행렬이거나 양의 정부호 행렬인 경우 수렴성이 보장되는 특징을 갖는다.
완화법 (반복법) - 가우스-자이델 방법
가우스-자이델 방법은 선형 연립 방정식의 해를 반복적으로 근사하는 수치 해석 방법으로, 이전 반복에서 계산된 값을 사용하여 변수를 업데이트하며, 야코비 방법보다 빠르게 수렴하지만 병렬 처리가 어렵고, 행렬이 대각 지배적이거나 대칭 양의 정부호 행렬일 때 수렴이 보장된다.
수치선형대수학 - 가우스 소거법
가우스 소거법은 연립 일차 방정식의 해를 구하기 위해 행렬을 사다리꼴로 변환하는 알고리즘이며, 기본 행 연산을 통해 전진 소거와 후퇴 대입 단계를 거쳐 해를 계산하고, 행렬식 계산 등 다양한 분야에 응용된다.
수치선형대수학 - LINPACK
LINPACK은 부동소수점 연산 성능을 평가하는 벤치마크 프로그램이자 FORTRAN 라이브러리로, 슈퍼컴퓨터 성능 측정 기준으로 사용되는 HPLinpack 벤치마크의 기반이 되었으며, TOP500 목록에서 고성능 컴퓨터 순위를 결정하는 데 기여한다.

축차가속완화법
개요
종류	선형 시스템을 푸는 방법
분야	수치해석학
SOR법
한국어 명칭	축차가속완화법
영어 명칭	Successive Over-Relaxation
목적	선형 시스템의 해 구하기
방법	가우스-자이델 방법의 수렴 속도 향상
설명	선형 방정식 시스템의 해를 구하기 위한 반복적인 방법이다.
참고 문헌	Young, David M. (1950). Iterative methods for solving partial difference equations of elliptical type (PhD thesis). Harvard University. 山本哲朗『数値解析入門』サイエンス社、2003年6月、増訂版。ISBN 4-7819-1038-6。

2. 공식

''n''개의 선형 방정식과 미지수 '''x'''를 가진 정사각 시스템에서, 주어진 선형 방정식은 다음과 같이 표현된다.

: $A\mathbf x = \mathbf b$

여기서 ''A''는 계수 행렬, '''x'''는 미지수 벡터, '''b'''는 상수 벡터이다.

: $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,$

여기서

: $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+\omega L) \mathbf{x} = \omega \mathbf{b} - [\omega U + (\omega-1) D ] \mathbf{x}$

여기서 ''ω''는 완화 계수(relaxation factor)라고 불리며, 가우스-자이델 방법은 ''ω''=1에 해당한다.

축차 가속 완화법은 반복법을 사용하여 해를 구하며, 다음과 같이 표현된다.

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

여기서 $\mathbf{x}^{(k)}$ 는 $\mathbf{x}$ 의 ''k''번째 근사값, $\mathbf{x}^{(k+1)}$ 는 $\mathbf{x}$ 의 ''k+1''번째 근사값이다. (''D''+''ωL'')이 하삼각행렬임을 이용하여, '''x'''^(''k''+1)의 각 원소는 전진 대입법을 통해 순차적으로 계산할 수 있다.

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

또는 행렬-벡터 형태로 다음과 같이 나타낼 수 있다.^[2]

: $\mathbf{x}^{(k+1)} = (1-\omega)\mathbf{x}^{(k)} + \omega D^{-1} \big( \mathbf{b} - L \mathbf{x}^{(k+1)} - U \mathbf{x}^{(k)} \big).$

3. 수렴성

1947년에 대칭 정부호 행렬에서는 0 < ω < 2 일 때 ρ(Lω) < 1 이 성립함이 증명되어, 이 범위에서 수렴성이 보장된다.^[3]^[4] 일반적으로 ω가 1보다 조금 클 때 수렴 속도가 가장 빠르다.

SOR 방법의 수렴 속도는 해석적으로 유도될 수 있다. 다음과 같은 가정을 해야 한다.^[3]^[4]

완화 인자는 적절하다: ω ∈ (0,2)
야코비 방법 반복 행렬 C_Jac:= I-D^-1A 는 실수 고유값만을 갖는다.
야코비 방법은 수렴한다: μ := ρ(C_Jac) < 1
행렬 분해 A=D+L+U 는 임의의 z∈ℂ{0} 및 λ∈ℂ에 대해 det(λD + zL + 1/zU) = det(λD + L + U) 의 속성을 만족한다.

그러면 수렴 속도는 다음과 같이 표현될 수 있다.

:

\rho(C_\omega) =\begin{cases}\frac{1}{4} \left( \omega \mu + \sqrt{\omega^2 \mu^2-4(\omega-1)} \right)^2\,,& 0 < \omega \leq \omega_\text{opt}\\\omega -1\,,& \omega_\text{opt} < \omega < 2\end{cases}

여기서 최적 완화 인자는 다음과 같다.

:

\omega_\text{opt} := 1+ \left( \frac{\mu}{1+\sqrt{1-\mu^2}} \right)^2 = 1 + \frac{\mu^2}{4} + O(\mu^3)\,.

특히, ω = 1 일 때 (가우스-자이델 방법) ρ(C_ω)=μ²=ρ(C_Jac)²가 성립한다. 최적 ω에 대해 ρ(C_ω) = (1 - √(1 - μ²)) / (1 + √(1 - μ²)) = μ² / 4 + O(μ³)을 얻으며, 이는 SOR이 가우스-자이델보다 대략 4배 더 효율적임을 보여준다.

마지막 가정은 대각 행렬 Z의 경우 Z_ii=z^i-1인 대각 행렬 Z에 대해 Z(λD + L + U)Z^-1=λD + zL + 1/zU이고 det(λD + L + U) = det(Z(λD + L + U)Z^-1)이므로 삼중 대각 행렬에 대해 만족된다. 반복 행렬의 고유값을 λ라고 하면,

:

\max|\lambda| \geq |\omega-1| \quad \forall\omega

이 성립하므로, 적어도 0 < ω < 2가 아니면 SOR법의 수렴성은 보장되지 않는다.^[6]

또한, 양의 정부호 대칭 행렬 A를 계수로 가지는 방정식 Ax=b에 대한 SOR법은, 가속 파라미터 ω가 0 < ω < 2일 때 반드시 수렴한다 (오스트로프스키의 정리).^[5]

ω=1일 때 가우스-자이델 방법과 같아지며^[5], ω가 1보다 작을 때 가우스-자이델 방법보다 수렴이 느려진다. 단, 가우스-자이델 방법으로 수렴하지 않는 문제에 사용할 수 있다.^[7] 일반적으로 가속 매개변수 ω의 값을 미리 최적으로 결정하는 것은 불가능하다. 따라서 문제마다 적절한 값을 선택할 필요가 있다.

그러나 ω의 최적값을 결정할 수 있는 예도 존재한다. 그것은 계수 행렬 A가 어떤 기본 행렬 P에 대해

:

PAP^{-1}=\left[\begin{matrix}D_1 & M_1 \\M_2 & D_2\end{matrix}\right]

라는 형태의 행렬로 닮음 변환할 수 있고, 게다가 야코비법의 반복 행렬 M_J=-D^-1(L+U)의 스펙트럼 반경 ρ(M_J)가 알려져 있을 때이다. 덧붙여, 위의 행렬 내의 D₁,D₂는 대각 행렬이다.

이때, SOR법의 반복 행렬의 스펙트럼 반경 ρ(M_ω)가 최소가 되는 ω의 최적값은, 다음 형태로 얻을 수 있다.^[8]

:

\omega = \frac{2}{1+\sqrt{1-\rho\left(M_J\right)^2}}

4. 알고리즘

축차가속완화법(SOR)은 주어진 행렬 ''A'', 벡터 '''b''', 완화 계수 ''ω''를 이용하여 선형 방정식 시스템의 해를 구하는 반복법이다. 해의 초기 추측값 ''φ''를 선택하고, 수렴할 때까지 다음 단계를 반복한다.^[5]
알고리즘:입력: ''A'', '''b''', ''ω''

출력: ''φ''

1. 해의 초기 추측값 ''φ''를 선택한다.

2. 수렴할 때까지 다음을 반복한다:

1. 1부터 ''n''까지 ''i''에 대해 반복한다:

1. ''σ''를 0으로 설정한다.

2. 1부터 ''n''까지 ''j''에 대해 반복한다:

1. ''j'' ≠ ''i'' 이면, ''σ'' = ''σ'' + ''a_ij'' ''φ_j'' 로 설정한다.

3. ''φ_i'' = (1 - ''ω'')''φ_i'' + ''ω''(''b_i'' - ''σ'') / ''a_ii'' 로 설정한다.

2. 수렴 여부를 확인한다.
참고: $(1-\omega)\phi_i + \frac{\omega}{a_{ii}} (b_i - \sigma)$ 는 $\phi_i + \omega \left( \frac{b_i - \sigma}{a_{ii}} - \phi_i\right)$ 로 쓸 수 있으며, 이렇게 하면 외부 ''for''-루프의 각 반복에서 곱셈을 하나 줄일 수 있다.
예시:다음 선형 시스템을 고려한다.

: $\begin{align}4x_1 - x_2 - 6x_3 + 0x_4 &= 2, \\$

5x_1 - 4x_2 + 10x_3 + 8x_4 &= 21, \\

0x_1 + 9x_2 + 4x_3 - 2x_4 &= -12, \\1x_1 + 0x_2 - 7x_3 + 5x_4 &= -6.\end{align}

완화 인자

\omega = 0.5

와 초기 추측 벡터

\phi = (0, 0, 0, 0)

을 선택하면, 축차가속완화법을 통해 아래 표와 같이 38단계에서 정확한 해

(3, -2, 2, 1)

에 수렴한다.

반복	$x_1$	$x_2$	$x_3$	$x_4$
1	0.25	-2.78125	1.6289062	0.5152344
2	1.2490234	-2.2448974	1.9687712	0.9108547
3	2.070478	-1.6696789	1.5904881	0.76172125
...	...	...	...	...
37	2.9999998	-2.0	2.0	1.0
38	3.0	-2.0	2.0	1.0

5. 예제

주어진 선형 시스템은 다음과 같다.

: $\begin{align}4x_1 - x_2 - 6x_3 + 0x_4 &= 2, \\$

5x_1 - 4x_2 + 10x_3 + 8x_4 &= 21, \\

0x_1 + 9x_2 + 4x_3 - 2x_4 &= -12, \\1x_1 + 0x_2 - 7x_3 + 5x_4 &= -6.\end{align}

이 방정식들을 풀기 위해 완화 인자

\omega = 0.5

와 초기 추측 벡터

\phi = (0, 0, 0, 0)

을 선택한다. 축차 과잉 완화(SOR) 알고리즘에 따르면, 다음 표는 38단계에서 정확한 해

(3, -2, 2, 1)

에 수렴하는 근사값을 보여준다.

반복	$x_1$	$x_2$	$x_3$	$x_4$
1	0.25	-2.78125	1.6289062	0.5152344
2	1.2490234	-2.2448974	1.9687712	0.9108547
3	2.070478	-1.6696789	1.5904881	0.76172125
...	...	...	...	...
37	2.9999998	-2.0	2.0	1.0
38	3.0	-2.0	2.0	1.0

다음은 Common Lisp로 구현된 알고리즘 예시이다.

```lisp

(setf *read-default-float-format* 'long-float)

(defparameter +maximum-number-of-iterations+ 100)

(declaim (type (integer 0 *) +maximum-number-of-iterations+))

(defun get-errors (computed-solution exact-solution)

(declare (type (vector number *) computed-solution))

(declare (type (vector number *) exact-solution))

(map '(vector number *) #'- exact-solution computed-solution))

(defun is-convergent (errors &key (error-tolerance 0.001))

(declare (type (vector number *) errors))

(declare (type number error-tolerance))

(flet ((error-is-acceptable (error)

(declare (type number error))

(<= (abs error) error-tolerance)))

(every #'error-is-acceptable errors)))

(defun make-zero-vector (size)

(declare (type (integer 0 *) size))

(make-array size :initial-element 0.0 :element-type 'number'))

(defun successive-over-relaxation (a b omega

&key (phi (make-zero-vector (length b)))

(convergence-check

#'(lambda (iteration phi)

(declare (ignore phi))

(>= iteration +maximum-number-of-iterations+))))

(declare (type (array number (* *)) a))

(declare (type (vector number *) b))

(declare (type number omega))

(declare (type (vector number *) phi))

(declare (type (function ((integer 1 *)

(vector number *))

)

convergence-check))

(let ((n (array-dimension a 0)))

(declare (type (integer 0 *) n))

(loop for iteration from 1 by 1 do

(loop for i from 0 below n by 1 do

(let ((rho 0))

(declare (type number rho))

(loop for j from 0 below n by 1 do

(when (/= j i)

(let ((a[ij] (aref a i j))

(phi[j] (aref phi j)))

(incf rho (* a[ij] phi[j])))))

(setf (aref phi i)

(+ (* (- 1 omega)

(aref phi i))

(* (/ omega (aref a i i))

(- (aref b i) rho))))))

(format t "~&~d. solution = ~a" iteration phi)

(when (funcall convergence-check iteration phi)

(return))))

(the (vector number *) phi)))

(let ((a (make-array (list 4 4)

:initial-contents

'(( 4 -1 -6 0 )

( -5 -4 10 8 )

( 0 9 4 -2 )

( 1 0 -7 5 ))))

(b (vector 2 21 -12 -6))

(omega 0.5)

(exact-solution (vector 3 -2 2 1)))

(successive-over-relaxation

a b omega

:convergence-check

#'(lambda (iteration phi)

(declare (type (integer 0 *) iteration))

(declare (type (vector number *) phi))

(let ((errors (get-errors phi exact-solution)))

(declare (type (vector number *) errors))

(format t "~&~d. errors = ~a" iteration errors)

(or (is-convergent errors :error-tolerance 0.0)

(>= iteration +maximum-number-of-iterations+)))))))

```

다음은 Python으로 구현된 알고리즘 예시이다.

```python

import numpy as np

from scipy import linalg

def sor_solver(A, b, omega, initial_guess, convergence_criteria):

step = 0

phi = initial_guess[:]

residual = linalg.norm(A @ phi - b)

while residual > convergence_criteria:

for i in range(A.shape[0]):

sigma = 0

for j in range(A.shape[1]):

if j != i:

sigma += A[i, j] * phi[j]

phi[i] = (1 - omega) * phi[i] + (omega / A[i, i]) * (b[i] - sigma)

residual = linalg.norm(A @ phi - b)

step += 1

print("Step {} Residual: {:10.6g}".format(step, residual))

return phi

residual_convergence = 1e-8

omega = 0.5

A = np.array(

[-5, -4, 10, 8],

[0, 9, 4, -2],

[1, 0, -7, 5]])

b = np.array([2, 21, -12, -6])

initial_guess = np.zeros(4)

phi = sor_solver(A, b, omega, initial_guess, residual_convergence)

print(phi)

6. 대칭 축차 가속 완화법 (SSOR)

대칭 행렬 ''A''에 대해,

: $U=L^T,\,$

를 '''대칭 축차 가속 완화법(SSOR)'''이라고 하며, 여기서

: $P=\left(\frac{D}{\omega}+L\right)\frac{\omega}{2-\omega}D^{-1}\left(\frac{D}{\omega}+U\right),$

반복 방법은 다음과 같다.

: $\mathbf{x}^{k+1}=\mathbf{x}^k-\gamma^k P^{-1}(A\mathbf{x}^k-\mathbf{b}),\ k \ge 0.$

축차 가속 완화법(SOR) 및 SSOR 방법은 데이비드 M. 영 주니어의 공로이다.

7. 활용

축차가속완화법(SOR, Successive Over-Relaxation)은 다양한 반복적인 방법들에 적용될 수 있다. 원래 반복식이 $x_{n+1}=f(x_n)$ 형태라면, 수정된 버전은 $x^\mathrm{SOR}_{n+1}=(1-\omega)x^{\mathrm{SOR}}_n+\omega f(x^\mathrm{SOR}_n)$ 과 같이 표현된다.

여기서 $\omega$ 는 완화 매개변수로, $\omega > 1$ 인 경우를 과도 완화(over-relaxation)라고 하며, 이는 수렴 속도를 높이는 데 사용된다. 반대로 $\omega < 1$ 인 경우는 감속 완화(under-relaxation)라고 하며, 발산하는 반복 프로세스의 수렴을 돕거나 과도하게 발산하는 프로세스의 수렴 속도를 높이는 데 사용된다.^[2]

최근에는 SOR 방법이 이산 기울기법(구조 보존형 수치 해법 중 하나)과의 관계가 밝혀지면서 다시 주목받고 있다.^[9]^[10]

참조

_[1] 논문 Iterative methods for solving partial difference equations of elliptical type http://www.ma.utexas[...] 1950-05-01
_[2] 서적 Numerische Mathematik für Ingenieure und Physiker https://link.springe[...] Springer Berlin, Heidelberg 2024-05-20
_[3] 서적 Iterative Solution of Large Sparse Systems of Equations
_[4] 서적 Iterative Methods for Solving Linear Systems
_[5] 서적 数値解析入門サイエンス社 2003-06
_[6] 간행물 連立一次方程式の解法2 -- 反復法 http://na-inet.jp/na[...] 2007-10-13
_[7] 웹사이트 SOR法 http://www.yamamo10.[...] 2004-12-16
_[8] 서적 Matrix iterative analysis Springer Science & Business Media 2009
_[9] 논문 微分方程式に対する離散勾配法に基づく線形方程式の数値解法の生成日本応用数理学会 2017
_[10] 논문 On the equivalence between SOR-type methods for linear systems and the discrete gradient methods for gradient systems 2018

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com