맨위로가기

가우스-자이델 방법

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

1. 개요

가우스-자이델 방법은 선형 연립 방정식을 풀기 위한 반복적인 수치 해석 방법이다. 이 방법은 주어진 선형 방정식 시스템의 해를 반복적으로 근사하며, 각 반복에서 이전 반복에서 계산된 값을 사용하여 변수를 업데이트한다. 가우스-자이델 방법은 일반적으로 야코비 방법보다 빠르게 수렴하지만, 각 변수를 순차적으로 업데이트해야 하므로 병렬 처리가 어렵다는 단점이 있다. 이 방법은 행렬이 대각 지배적이거나 대칭 양의 정부호 행렬일 때 수렴이 보장된다.

2. 설명

가우스-자이델 방법은 다음과 같은 n개의 선형 방정식 시스템을 반복적으로 풀어 해를 근사하는 방법이다.

:\mathbf 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와 b가 주어져 있고 x가 미지수일 때, 가우스-자이델 방법을 사용하여 x를 반복적으로 근사할 수 있다. 벡터 x(0)은 x의 초기 추측값을 나타내며, 종종 i=1,2,...,n에 대해 x(0)i=0으로 설정한다. x(k)는 x의 k번째 근사값 또는 반복을 나타내고, x(k+1)는 다음 (k+1번째) 반복에서 x의 근사값을 나타낸다.

n차 정사각 행렬 A는 상삼각 행렬 U, 하삼각 행렬 L, 대각 행렬 D의 합으로 표현할 수 있다. (A = L + D + U) 이를 이용하면 다음과 같은 변형이 가능하다.

:

\begin{array}{ccc}

(L+D+U) \vec{x} &=& \vec{b} \\

(L+D)\vec{x} &=& \vec{b}-U\vec{x} \\

\end{array}



이 식을 만족하는 x를 구한다. 초기값 x(0)에 대해, k번째 반복에서 얻어진 x1의 값을 x1(k)라고 하면, 다음과 같은 반복법의 점화식을 얻을 수 있다.

:(L+D)\vec{x}^{(k+1)} = \vec{b}-U\vec{x}^{(k)}

이 식은 다음과 같이 변형할 수 있다.

:

\vec{x}^{(k+1)} = D^{-1}(\vec{b}-L\vec{x}^{(k+1)} - U\vec{x}^{(k)})



만약 해가 수렴하는 경우, x1(k+1)와 x1(k)는 공통 값 x1(*)을 가지게 된다. 이때,

:

\vec{x}^{(*)} = D^{-1}(\vec{b}-L\vec{x}^{(*)} - U\vec{x}^{(*)})



가 되어, 원래의 연립방정식 형태로 돌아간다. 따라서 가우스-자이델 방법으로 해가 수렴하는 경우, 그 해는 연립방정식의 해가 된다.

가우스-자이델 방법은 각 성분마다 다음과 같은 식으로 표현할 수 있으며, 수치 해석에서 주로 사용된다.

:

x_{i}^{(k+1)} = \frac{1}{a_{ii}} \left( b_{i} - \sum_{j=1}^{i-1} a_{ij}x_{j}^{(k+1)} - \sum_{j=i+1}^{n} a_{ij}x_{j}^{(k)} \right)



SOR 방법은 야코비 방법과 가우스-자이델 방법을 가속하는 방법으로 알려져 있다.

2. 1. 행렬 기반 공식

가우스-자이델 방법은 주어진 선형 방정식 \mathbf A\mathbf x = \mathbf b에서 행렬 \mathbf A를 하삼각 행렬 \mathbf L과 상삼각 행렬 \mathbf U로 분해하여 해를 반복적으로 구하는 방법이다. 즉, \mathbf {A} = \mathbf L + \mathbf U 일 때,[4] 다음 식을 이용하여 반복 계산을 수행한다.

: \mathbf L \mathbf{x}^{(k+1)} = \mathbf{b} - \mathbf U \mathbf{x}^{(k)}

여기서 \mathbf x^{(k)}는 \mathbf{x}의 k번째 근사값 또는 반복을 나타내고, \mathbf{x}^{(k+1)}는 다음 (k+1번째) 반복에서 \mathbf{x}의 근사값을 나타낸다.

n차 정사각 행렬 A를 상삼각 행렬 U, 하삼각 행렬 L, 대각 행렬 D로 나타내면, ''A=L+D+U''로 쓸 수 있다. 이를 이용해 다음과 같이 변형 가능하다.

: (L+D+U) \vec{x} = \vec{b}

: (L+D)\vec{x} = \vec{b}-U\vec{x}

위 식을 만족하는 ''x''를 구하기 위해, 초기값 \vec{x}^{(0)}에 대해 k번째 반복에서 얻어진 x_1의 값을 x_1^{(k)}라고 하면, 다음과 같은 반복법의 점화식을 얻을 수 있다.

: (L+D)\vec{x}^{(k+1)} = \vec{b}-U\vec{x}^{(k)}

이 식은 다음과 같이 변형할 수 있다.

: \vec{x}^{(k+1)} = D^{-1}(\vec{b}-L\vec{x}^{(k+1)} - U\vec{x}^{(k)})

만약 해가 수렴하는 경우, x_1^{(k+1)}와 x_1^{(k)}는 공통 값 x_1^{(*)}을 갖게 된다. 이때,

: \vec{x}^{(*)} = D^{-1}(\vec{b}-L\vec{x}^{(*)} - U\vec{x}^{(*)})

가 성립하며, 이를 변형하면 원래의 연립방정식 형태로 돌아간다. 따라서 가우스-자이델 방법으로 해가 수렴하는 경우, 그 해는 연립방정식의 해가 된다.

가우스-자이델 방법의 식은 벡터 \vec{x}의 각 성분마다 다음과 같은 식으로 쓸 수 있으며, 수치 해석에서는 이 식을 사용한다.

: x_{i}^{(k+1)} = \frac{1}{a_{ii}} \left( b_{i} - \sum_{j=1}^{i-1} a_{ij}x_{j}^{(k+1)} - \sum_{j=i+1}^{n} a_{ij}x_{j}^{(k)} \right)

SOR 방법은 가우스-자이델 방법과 야코비 방법을 가속하는 방법으로 알려져 있다.

2. 1. 1. 행렬 기반 공식의 원리

하삼각 행렬 성분 \mathbf L과 상삼각 행렬 성분 \mathbf U로 분해되는 행렬 \mathbf A는 \mathbf {A} = \mathbf L + \mathbf U 를 만족한다.[4] A를 L과 U로 분해하면 다음과 같다.

:\mathbf A =

\underbrace{

\begin{bmatrix} a_{11} & 0 & \cdots & 0 \\ a_{21} & a_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}

}_{\textstyle \mathbf L}

+

\underbrace{

\begin{bmatrix} 0 & a_{12} & \cdots & a_{1n} \\ 0 & 0 & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & 0 \end{bmatrix}

}_{\textstyle \mathbf U}

.

선형 방정식 시스템은 다음과 같이 다시 쓸 수 있다.

:\begin{alignat}{1}

\mathbf A \mathbf x &= \mathbf b \\

(\mathbf L + \mathbf U) \mathbf x &= \mathbf b \\

\mathbf L \mathbf x+ \mathbf U \mathbf x &= \mathbf b \\

\mathbf L \mathbf{x} &= \mathbf{b} - \mathbf U \mathbf{x}

\end{alignat}

가우스-자이델 방법은 위 식의 좌변을 '''\mathbf{x}'''에 대해 풀고, 우변에서는 '''\mathbf{x}'''의 이전 값을 사용한다. 이를 분석적으로 표현하면 다음과 같다.

\mathbf {x}^{(k+1)} = \mathbf L^{-1} \left(\mathbf{b} - \mathbf U \mathbf{x}^{(k)}\right).

n차 정사각 행렬 A를 상삼각 행렬 U, 하삼각 행렬 L, 대각 행렬 D로 나타내면, ''A=L+D+U''와 같이 쓸 수 있다. 이를 이용해 다음과 같은 변형이 가능하다.



\begin{array}{ccc}

(L+D+U) \vec{x} &=& \vec{b} \\

(L+D)\vec{x} &=& \vec{b}-U\vec{x} \\

\end{array}



위 식을 만족하는 ''x''를 구하기 위해, 초기값 \vec{x}^{(0)}에 대해 k번째 반복에서 얻어진 x_1의 값을 x_1^{(k)}라고 하면, 다음과 같은 반복법의 점화식을 얻을 수 있다.



(L+D)\vec{x}^{(k+1)} = \vec{b}-U\vec{x}^{(k)}



이 식은 다음과 같이 변형할 수 있다.



\vec{x}^{(k+1)} = D^{-1}(\vec{b}-L\vec{x}^{(k+1)} - U\vec{x}^{(k)})



만약 해가 수렴하면, x_1^{(k+1)}와 x_1^{(k)}는 공통 값 x_1^{(*)}을 갖게 된다. 이때,



\vec{x}^{(*)} = D^{-1}(\vec{b}-L\vec{x}^{(*)} - U\vec{x}^{(*)})



가 성립하며, 이를 변형하면 원래의 연립방정식 형태로 돌아간다. 따라서 가우스-자이델 방법으로 해가 수렴하는 경우, 그 해는 연립방정식의 해가 된다.

가우스-자이델 방법의 식은 벡터 \vec{x}의 각 성분마다 다음과 같은 식으로 쓸 수 있으며, 수치 해석에서는 이 식을 사용한다.



x_{i}^{(k+1)} = \frac{1}{a_{ii}} \left( b_{i} - \sum_{j=1}^{i-1} a_{ij}x_{j}^{(k+1)} - \sum_{j=i+1}^{n} a_{ij}x_{j}^{(k)} \right)


2. 2. 원소별 공식

각 행 *i*에 대해 전진 대입법을 사용하여 \mathbf{x}^{(k+1)}의 원소를 순차적으로 계산한다.[5]

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

이 공식은 반복마다 두 개의 합을 사용하며, x_j의 가장 최근에 계산된 반복을 사용하는 하나의 합 \sum_{j \ne i} a_{ij}x_j로 표현할 수 있다.

가우스-자이델 방법의 식은 벡터 \vec{x}의 각 성분마다 다음과 같은 식으로 쓸 수 있으며, 수치 해석에서는 이 식을 사용한다.

:

x_{i}^{(k+1)} = \frac{1}{a_{ii}} \left( b_{i} - \sum_{j=1}^{i-1} a_{ij}x_{j}^{(k+1)} - \sum_{j=i+1}^{n} a_{ij}x_{j}^{(k)} \right)



3원 연립 일차 방정식의 경우,

:\left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right) \left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array} \right) = \left( \begin{array}{c} b_1 \\ b_2 \\ b_3 \end{array} \right)

를 푸는 것을 생각한다. *k*번째 반복에서 얻어진 x_1의 값을 x_1^{(k)}로 쓴다. 초기값 \vec{x}^{(0)}는, 적당한 값, 예를 들어 영벡터라도 상관없다.

:x_1^{(k+1)} = (b_1 - a_{12} x_2^{(k)} - a_{13} x_3^{(k)}) / a_{11}

:x_2^{(k+1)} = (b_2 - a_{21} x_1^{(k+1)} - a_{23} x_3^{(k)}) / a_{22}

:x_3^{(k+1)} = (b_3 - a_{31} x_1^{(k+1)} - a_{32} x_2^{(k+1)}) / a_{33}

위의 식을 반복한다. 여기서, 두 번째 식에서 x_1^{(k+1)}이 사용되고 있다는 것에 주의한다. 연달아 새로운 x_i^{(k+1)}을 구해서, 다음 식에서 사용한다.

2. 3. 논의

가우스-자이델 방법은 야코비 방법과 유사하지만, 몇 가지 중요한 차이점이 있다. 가우스-자이델 방법에서는 \mathbf{x}^{(k+1)}을 계산할 때 이미 계산된 \mathbf{x}^{(k+1)}의 원소를 사용하고, 아직 계산되지 않은 \mathbf{x}^{(k)}의 원소만 사용하여, 계산된 최신 원소를 즉시 사용한다.

이러한 특징 덕분에 야코비 방법과 달리 하나의 저장 벡터만 필요하며, 이는 매우 큰 문제에서 유리할 수 있다. 또한, 일반적으로 야코비 방법보다 수렴 속도가 빠르다.

하지만, 야코비 방법과 달리 각 원소의 계산은 원래 방정식의 순서에 따라 달라지며, 병렬 알고리즘으로 구현하기 어렵다. 각 원소 계산이 매우 긴 임계 경로를 가질 수 있기 때문에, 희소 행렬에 가장 적합하다.

가우스-자이델 방법은 \omega=1일 때 연속 과잉 완화(SOR)와 동일하다.

3. 수렴성

가우스-자이델 방법의 수렴성은 행렬 \mathbf A의 특성에 따라 결정된다. 다음 조건 중 하나라도 만족하면 수렴이 보장된다.


  • \mathbf A가 대칭 양의 정부호 행렬인 경우.[6]
  • \mathbf A가 엄격(기약) 대각 지배 행렬인 경우.[7]


이러한 조건이 충족되지 않더라도 가우스-자이델 방법이 수렴하는 경우도 있다.

골럽(Golub)과 반 로언(Van Loan)은 \mathbf A를 두 부분으로 나누는 알고리즘에 대한 정리를 제시했다. \mathbf A = \mathbf M - \mathbf N가 비특이 행렬이라고 가정하고, r = \rho (\mathbf M^ {-1} \mathbf N)을 \mathbf M^{-1} \mathbf N의 스펙트럼 반경이라고 하자. 그러면 \mathbf M \mathbf x^{(k+1)} = \mathbf N \mathbf x^{(k)} + \mathbf b로 정의된 반복 \mathbf x^{(k)}는 \mathbf M이 비특이 행렬이고 r < 1이면 어떤 시작 벡터 \mathbf x^{(0)}에 대해서도 \mathbf x = \mathbf A^{-1} \mathbf b로 수렴한다.[8]

가우스-자이델 방법은 계수 행렬이 양의 정부호 대칭 행렬이면 수렴한다.

또한, 계수 행렬의 각 행에서 비대각 성분의 절대값의 합이 대각 성분의 절대값보다 작으면 수렴한다(이는 야코비 방법도 마찬가지이다). 즉, 대각 우세 행렬이면 수렴한다.

:\left | a_{ii} \right | > \sum_{i \ne j} {\left | a_{ij} \right |}.

계수 행렬이 양의 정부호 대칭인 경우, 가우스-자이델 방법의 수렴성을 이용하여 A\vec{x}=\vec{b} 대신 동치인 A^TA\vec{x}=A^T \vec{b}를 푸는 방법이 고려될 수 있다. 이 방법은 \vec{x}의 각 요소를 갱신할 때마다 잔차가 감소하지만, 조건수가 원래 행렬 A의 조건수의 제곱이 되어 수렴 속도가 느려질 수 있다.

A\vec{x}=\vec{b} 대신 A^TA\vec{x}=A^T \vec{b}를 푸는 방법은 비대칭, 비정부호 행렬을 공액 기울기법으로 풀 때도 사용된다. 그러나 공액 기울기법(CG법)에서도 조건수가 증가하여 수렴성이 나빠진다.

4. 알고리즘

가우스-자이델 방법은 반복적인 방법으로 선형 방정식의 해를 구하는 알고리즘이다. 알고리즘의 과정은 다음과 같다.
입력: A (n x n 정방 행렬), b (상수 벡터)
출력: φ (해 벡터)

1. 초기 추측값 φ를 선택한다. (보통 0으로 설정)

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


  • i = 1부터 n까지 반복:
  • σ = 0
  • j = 1부터 n까지 반복:
  • j ≠ i 이면, σ = σ + aijφj
  • φi = (bi - σ) / aii
  • 수렴 여부 확인 (변화량이 허용 오차보다 작으면 수렴)


이 알고리즘은 계산되는 즉시 원소를 덮어쓰므로, 저장 벡터는 하나만 필요하며 벡터 인덱싱은 생략 가능하다.

5. 예제

가우스-자이델 방법의 적용 과정을 보여주는 예제들이다.


  • 행렬 버전 예제: 주어진 행렬 방정식에 대해 가우스-자이델 방법을 적용하여 해를 구하는 과정을 단계별로 보여준다. 초기 추정값에서 시작하여 반복적으로 해를 업데이트하며, 최종적으로 수렴하는 해를 제시한다.

  • 방정식 버전 예제: 주어진 연립 방정식에 대해 가우스-자이델 방법을 적용하여 해를 구하는 과정을 보여준다. 각 변수에 대한 식을 유도하고, 초기값에서 시작하여 반복적으로 근사해를 계산한다. 반복 결과와 정확한 해를 표로 비교하여 보여준다.

```python

import numpy as np

ITERATION_LIMIT = 1000

# 행렬 초기화

A = np.array(

[

[10.0, -1.0, 2.0, 0.0],

[-1.0, 11.0, -1.0, 3.0],

[2.0, -1.0, 10.0, -1.0],

[0.0, 3.0, -1.0, 8.0],

]

)

# b 벡터 초기화

b = np.array([6.0, 25.0, -11.0, 15.0])

print("연립 방정식:")

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

row = [f"{A[i,j]:3g}*x{j+1}" for j in range(A.shape[1])]

print("[{0}] = [{1:3g}]".format(" + ".join(row), b[i]))

x = np.zeros_like(b, np.float_)

for it_count in range(1, ITERATION_LIMIT):

x_new = np.zeros_like(x, dtype=np.float_)

print(f"반복 {it_count}: {x}")

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

s1 = np.dot(A[i, :i], x_new[:i])

s2 = np.dot(A[i, i + 1 :], x[i + 1 :])

x_new[i] = (b[i] - s1 - s2) / A[i, i]

if np.allclose(x, x_new, rtol=1e-8):

break

x = x_new

print(f"해: {x}")

error = np.dot(A, x) - b

print(f"오차: {error}")

```

위 코드는 가우스-자이델 방법을 사용하여 선형 연립 방정식의 해를 구하는 파이썬 및 NumPy 예제이다. 초기화, 반복, 결과 출력을 단계별로 수행하며, 각 단계에 대한 설명을 포함하고 있다.

5. 1. 행렬 버전 예제

선형 시스템 \mathbf A \mathbf{x} = \mathbf{b}가 다음과 같이 주어졌다고 하자.

\mathbf A=

\begin{bmatrix}

16 & 3 \\

7 & -11 \\

\end{bmatrix}

\quad \text{and} \quad

\mathbf b =

\begin{bmatrix}

11 \\

13

\end{bmatrix}.



이때, 다음 식을 사용한다.

\mathbf{x}^{(k+1)} = \mathbf L^{-1} (\mathbf{b} - \mathbf U \mathbf{x}^{(k)})

이는 다음과 같이 표현할 수 있다.

\mathbf{x}^{(k+1)} = \mathbf T \mathbf{x}^{(k)} + \mathbf c

여기서 \mathbf T = - \mathbf L ^{-1} \mathbf U 이고 \mathbf c = \mathbf L ^{-1} \mathbf{b}이다.

\mathbf A를 하부 삼각 성분 \mathbf L과 엄격한 상부 삼각 성분 U의 합으로 분해하면 다음과 같다.

\mathbf L=

\begin{bmatrix}

16 & 0 \\

7 & -11 \\

\end{bmatrix}

\quad \text{and} \quad

\mathbf U =

\begin{bmatrix}

0 & 3 \\

0 & 0

\end{bmatrix}.



\mathbf L의 역행렬은 다음과 같다.

\mathbf L^{-1} =

\begin{bmatrix}

16 & 0 \\

7 & -11

\end{bmatrix}^{-1}

=

\begin{bmatrix}

0.0625 & 0.0000 \\

0.0398 & -0.0909 \\

\end{bmatrix}.



이제 \mathbf T와 \mathbf c를 구하면 다음과 같다.

\begin{align}

\mathbf T & = -

\begin{bmatrix}

0.0625 & 0.0000 \\

0.0398 & -0.0909

\end{bmatrix}

\begin{bmatrix}

0 & 3 \\

0 & 0

\end{bmatrix}

=

\begin{bmatrix}

0.000 & -0.1875 \\

0.000 & -0.1194

\end{bmatrix},

\\[1ex]

\mathbf c & =

\begin{bmatrix}

0.0625 & 0.0000 \\

0.0398 & -0.0909

\end{bmatrix}

\begin{bmatrix}

11 \\

13

\end{bmatrix}

=

\begin{bmatrix}

0.6875 \\

  • 0.7439

\end{bmatrix}.

\end{align}

\mathbf T 와 \mathbf c 를 사용하여 벡터 \mathbf{x}를 반복적으로 구할 수 있다. 우선, 초기 추정값 \mathbf{x}^{(0)}을 선택한다. 예를 들어, \mathbf x^{(0)} = \begin{bmatrix} 1.0 \\ 1.0 \end{bmatrix}로 설정한다. 추정값이 최종 해에 가까울수록 알고리즘에 필요한 반복 횟수가 줄어든다.

그 후, 다음을 계산한다.

\begin{align}

\mathbf x^{(1)} &=

\begin{bmatrix}

0.000 & -0.1875 \\

0.000 & -0.1193

\end{bmatrix}

\begin{bmatrix}

1.0 \\

1.0

\end{bmatrix}

+

\begin{bmatrix}

0.6875 \\

  • 0.7443

\end{bmatrix}

=

\begin{bmatrix}

0.5000 \\

  • 0.8636

\end{bmatrix}.

\\[1ex]

\mathbf x^{(2)} &=

\begin{bmatrix}

0.000 & -0.1875 \\

0.000 & -0.1193

\end{bmatrix}

\begin{bmatrix}

0.5000 \\

  • 0.8636

\end{bmatrix}

+

\begin{bmatrix}

0.6875 \\

  • 0.7443

\end{bmatrix}

=

\begin{bmatrix}

0.8494 \\

  • 0.6413

\end{bmatrix}.

\\[1ex]

\mathbf x^{(3)} &=

\begin{bmatrix}

0.000 & -0.1875 \\

0.000 & -0.1193

\end{bmatrix}

\begin{bmatrix}

0.8494 \\

  • 0.6413 \\

\end{bmatrix}

+

\begin{bmatrix}

0.6875 \\

  • 0.7443

\end{bmatrix}

=

\begin{bmatrix}

0.8077 \\

  • 0.6678

\end{bmatrix}.

\\[1ex]

\mathbf x^{(4)} &=

\begin{bmatrix}

0.000 & -0.1875 \\

0.000 & -0.1193

\end{bmatrix}

\begin{bmatrix}

0.8077 \\

  • 0.6678

\end{bmatrix}

+

\begin{bmatrix}

0.6875 \\

  • 0.7443

\end{bmatrix}

=

\begin{bmatrix}

0.8127 \\

  • 0.6646

\end{bmatrix}.

\\[1ex]

\mathbf x^{(5)} & =

\begin{bmatrix}

0.000 & -0.1875 \\

0.000 & -0.1193

\end{bmatrix}

\begin{bmatrix}

0.8127 \\

  • 0.6646

\end{bmatrix}

+

\begin{bmatrix}

0.6875 \\

  • 0.7443

\end{bmatrix}

=

\begin{bmatrix}

0.8121 \\

  • 0.6650

\end{bmatrix}.

\\[1ex]

\mathbf x^{(6)} & =

\begin{bmatrix}

0.000 & -0.1875 \\

0.000 & -0.1193

\end{bmatrix}

\begin{bmatrix}

0.8121 \\

  • 0.6650

\end{bmatrix}

+

\begin{bmatrix}

0.6875 \\

  • 0.7443

\end{bmatrix}

=

\begin{bmatrix}

0.8122 \\

  • 0.6650

\end{bmatrix}.

\\[1ex]

\mathbf x^{(7)} & =

\begin{bmatrix}

0.000 & -0.1875 \\

0.000 & -0.1193

\end{bmatrix}

\begin{bmatrix}

0.8122 \\

  • 0.6650

\end{bmatrix}

+

\begin{bmatrix}

0.6875 \\

  • 0.7443

\end{bmatrix}

=

\begin{bmatrix}

0.8122 \\

  • 0.6650

\end{bmatrix}.

\end{align}

예상대로, 이 알고리즘은 다음 해로 수렴한다.

\mathbf{x} = \mathbf A ^{-1} \mathbf{b} \approx \begin{bmatrix} 0.8122\\ -0.6650 \end{bmatrix}.

행렬 A는 엄격하게 대각 지배적이지만, 양의 정부호는 아니다.[4]

5. 2. 방정식 버전 예제

주어진 선형 방정식 시스템에 대해 가우스-자이델 방법을 적용하는 구체적인 예시를 살펴보자.

다음과 같은 연립 방정식이 주어졌다고 가정한다.

:\begin{array}{rrrrl}

10x_1 &- x_2 &+ 2x_3 & & = 6, \\

  • x_1 &+ 11x_2 &- x_3 &+ 3x_4 & = 25, \\

2x_1 &- x_2 &+ 10x_3 &- x_4 & = -11, \\

& 3x_2 &- x_3 &+ 8x_4 & = 15.

\end{array}

각 변수에 대해 풀면 다음과 같이 표현할 수 있다.

:\begin{align}

x_1 & = x_2/10 - x_3/5 + 3/5, \\

x_2 & = x_1/11 + x_3/11 - 3x_4/11 + 25/11, \\

x_3 & = -x_1/5 + x_2/10 + x_4/10 - 11/10, \\

x_4 & = -3x_2/8 + x_3/8 + 15/8.

\end{align}

초기값 (0, 0, 0, 0)에서 시작하여 반복을 진행하면 다음과 같은 근사해를 얻을 수 있다.[5]

:\begin{align}

x_1 & = 3/5 = 0.6, \\

x_2 & = (3/5)/11 + 25/11 = 3/55 + 25/11 = 2.3272, \\

x_3 & = -(3/5)/5 +(2.3272)/10-11/10 = -3/25 + 0.23272-1.1 = -0.9873,\\

x_4 & = -3(2.3272)/8 +(-0.9873)/8+15/8 = 0.8789.

\end{align}

이후 반복을 계속하면 다음 표와 같은 결과를 얻는다.

x_1x_2x_3x_4
0.62.32727-0.9872730.878864
1.030182.03694-1.014460.984341
1.006592.00356-1.002530.998351
1.000862.0003-1.000310.99985



이 시스템의 정확한 해는 (1, 2, -1, 1)이다.

일반적으로, n개의 방정식과 시작점 \mathbf {x} _0이 주어졌을 때, 가우스-자이델 방법의 각 단계는 다음과 같이 진행된다.[5]

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

위 식은 반복마다 두 개의 합을 사용하며, x_j의 가장 최근에 계산된 반복을 사용하는 하나의 합 \sum_{j \ne i} a_{ij}x_j로 표현할 수 있다. 이 절차는 일반적으로 반복에 의해 이루어진 변화가 충분히 작은 잔차와 같은 어떤 허용 오차보다 작아질 때까지 계속된다.

3원 연립 일차 방정식의 경우,

:\left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right) \left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array} \right) = \left( \begin{array}{c} b_1 \\ b_2 \\ b_3 \end{array} \right)

k번째 반복에서 얻어진 x_1의 값을 x_1^{(k)}로 쓰고, 초기값 \vec{x}^{(0)}를 적당한 값(예: 영벡터)으로 설정하면, 다음과 같은 반복을 통해 해를 구할 수 있다.

:x_1^{(k+1)} = (b_1 - a_{12} x_2^{(k)} - a_{13} x_3^{(k)}) / a_{11}

:x_2^{(k+1)} = (b_2 - a_{21} x_1^{(k+1)} - a_{23} x_3^{(k)}) / a_{22}

:x_3^{(k+1)} = (b_3 - a_{31} x_1^{(k+1)} - a_{32} x_2^{(k+1)}) / a_{33}

여기서 두 번째 식에서 x_1^{(k+1)}이 사용되는 것에 주의해야 한다. 즉, 새로운 x_i^{(k+1)}을 구해서 다음 식에서 사용한다. 이 때문에 가우스-자이델 방법은 병렬 계산이 불가능하며, 병렬 계산을 위해서는 야코비 방법을 사용해야 한다. 야코비 방법은 직렬 계산에서는 가우스-자이델 방법보다 느리지만, 쉽게 병렬 계산을 할 수 있다.

5. 3. 파이썬 및 NumPy 예제

python

import numpy as np

ITERATION_LIMIT = 1000

# 행렬 초기화

A = np.array(

[

[10.0, -1.0, 2.0, 0.0],

[-1.0, 11.0, -1.0, 3.0],

[2.0, -1.0, 10.0, -1.0],

[0.0, 3.0, -1.0, 8.0],

]

)

# b 벡터 초기화

b = np.array([6.0, 25.0, -11.0, 15.0])

print("연립 방정식:")

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

row = [f"{A[i,j]:3g}*x{j+1}" for j in range(A.shape[1])]

print("[{0}] = [{1:3g}]".format(" + ".join(row), b[i]))

x = np.zeros_like(b, np.float_)

for it_count in range(1, ITERATION_LIMIT):

x_new = np.zeros_like(x, dtype=np.float_)

print(f"반복 {it_count}: {x}")

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

s1 = np.dot(A[i, :i], x_new[:i])

s2 = np.dot(A[i, i + 1 :], x[i + 1 :])

x_new[i] = (b[i] - s1 - s2) / A[i, i]

if np.allclose(x, x_new, rtol=1e-8):

break

x = x_new

print(f"해: {x}")

error = np.dot(A, x) - b

print(f"오차: {error}")

```

위 코드는 가우스-자이델 방법을 사용하여 선형 연립 방정식의 해를 구하는 파이썬 및 NumPy 예제이다.
코드 설명:1. 초기화:

  • `A`: 계수 행렬
  • `b`: 상수 벡터
  • `ITERATION_LIMIT`: 최대 반복 횟수
  • `x`: 초기 해 벡터 (0으로 초기화)


2. 반복:

  • `for` 루프를 사용하여 최대 `ITERATION_LIMIT` 횟수만큼 반복
  • `x_new`: 새로운 해 벡터 (0으로 초기화)
  • `for` 루프를 사용하여 각 방정식에 대해 가우스-자이델 공식 적용
  • `s1`: 현재 방정식의 이전 변수들에 대한 항들의 합
  • `s2`: 현재 방정식의 이후 변수들에 대한 항들의 합
  • `x_new[i]`: 현재 방정식의 새로운 해 계산
  • `np.allclose()`: 이전 해 `x`와 새로운 해 `x_new`를 비교하여 수렴 여부 확인 (상대 오차 `rtol=1e-8` 이내)
  • 수렴하면 반복 종료
  • `x = x_new`: 해 업데이트


3. 결과 출력:

  • `print()`를 사용하여 연립 방정식, 각 반복 단계에서의 해, 최종 해, 오차를 출력

실행 결과:```

연립 방정식:

[ 10*x1 + -1*x2 + 2*x3 + 0*x4] = [ 6]

[ -1*x1 + 11*x2 + -1*x3 + 3*x4] = [ 25]

[ 2*x1 + -1*x2 + 10*x3 + -1*x4] = [-11]

[ 0*x1 + 3*x2 + -1*x3 + 8*x4] = [ 15]

반복 1: [ 0. 0. 0. 0.]

반복 2: [ 0.6 2.32727273 -0.98727273 0.87886364]

반복 3: [ 1.03018182 2.03693802 -1.0144562 0.98434122]

반복 4: [ 1.00658504 2.00355502 -1.00252738 0.99835095]

반복 5: [ 1.00086098 2.00029825 -1.00030728 0.99984975]

반복 6: [ 1.00009128 2.00002134 -1.00003115 0.9999881 ]

반복 7: [ 1.00000836 2.00000117 -1.00000275 0.99999922]

반복 8: [ 1.00000067 2.00000002 -1.00000021 0.99999996]

반복 9: [ 1.00000004 1.99999999 -1.00000001 1. ]

반복 10: [ 1. 2. -1. 1.]

해: [ 1. 2. -1. 1.]

오차: [ 2.06480930e-08 -1.25551054e-08 3.61417563e-11 0.00000000e+00]

6. 가속 방법 (SOR 방법)

야코비 방법과 가우스-자이델 방법은 SOR(Successive Over-Relaxation) 방법을 통해 가속할 수 있다.

7. 구체적인 예 (3원 연립 일차 방정식)

3원 연립 일차 방정식, 즉

:\left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right) \left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array} \right) = \left( \begin{array}{c} b_1 \\ b_2 \\ b_3 \end{array} \right)

를 푸는 것을 생각한다. k번째 반복에서 얻어진 x_1의 값을 x_1^{(k)}로 쓴다. 초기값 \vec{x}^{(0)}는 적당한 값, 예를 들어 영벡터라도 상관없다.

반복식은 다음과 같다.

:x_1^{(k+1)} = (b_1 - a_{12} x_2^{(k)} - a_{13} x_3^{(k)}) / a_{11}

:x_2^{(k+1)} = (b_2 - a_{21} x_1^{(k+1)} - a_{23} x_3^{(k)}) / a_{22}

:x_3^{(k+1)} = (b_3 - a_{31} x_1^{(k+1)} - a_{32} x_2^{(k+1)}) / a_{33}

위 식을 반복해 가며 해를 구한다. 여기서 두 번째 식에서 x_1^{(k+1)}이 사용되고 있다는 것에 주의한다. 연달아 새로운 x_i^{(k+1)}을 구해서, 다음 식에서 사용한다. 이 때문에 가우스-자이델 방법은 이대로는 병렬 계산할 수 없다.

따라서 병렬 계산을 위해서는 위의 반복식 우변의 x_i^{(k+1)} 대신에 x_i^{(k)}를 사용하는 야코비 방법을 사용한다. 즉, 새로운 \vec{x}^{(k+1)}를 다른 장소에 기억해 두고, 일제히 \vec{x}를 갱신한다.

야코비 방법은 직렬 계산에서는 가우스-자이델 방법보다 느리지만, 쉽게 병렬 계산할 수 있다.

참조

[1] 서적 Numerical Analysis Pearson Education, Inc.
[2] 기타 http://gdz.sub.uni-g[...]
[3] 논문 Über ein Verfahren, die Gleichungen, auf welche die Methode der kleinsten Quadrate führt, sowie lineäre Gleichungen überhaupt, durch successive Annäherung aufzulösen https://www.biodiver[...] 1874
[4] 기타
[5] 기타
[6] 기타
[7] 논문 A Unified Proof for the Convergence of Jacobi and Gauss-Seidel Methods 1995-03
[8] 기타


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

문의하기 : help@durumis.com