가우스-자이델 방법

1. 개요

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

2. 설명

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

:

여기서 A와 b가 주어져 있고 x가 미지수일 때, 가우스-자이델 방법을 사용하여 x를 반복적으로 근사할 수 있다. 벡터 x⁽⁰⁾은 x의 초기 추측값을 나타내며, 종종 i=1,2,...,n에 대해 x⁽⁰⁾_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⁽⁰⁾에 대해, k번째 반복에서 얻어진 x₁의 값을 x₁^(k)라고 하면, 다음과 같은 반복법의 점화식을 얻을 수 있다.

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

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

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


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

:$$
\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. 행렬 기반 공식

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

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

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

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

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

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

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

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

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

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

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

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

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

:$x\_\{i\}^\{(k+1)\}\; =\; \backslash frac\{1\}\{a\_\{ii\}\}\; \backslash left(\; b\_\{i\}\; -\; \backslash sum\_\{j=1\}^\{i-1\}\; a\_\{ij\}x\_\{j\}^\{(k+1)\}\; -\; \backslash sum\_\{j=i+1\}^\{n\}\; a\_\{ij\}x\_\{j\}^\{(k)\}\; \backslash right)$

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

2.1.1. 행렬 기반 공식의 원리

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

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

선형 방정식 시스템은 다음과 같이 다시 쓸 수 있다.
:$\backslash 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}

가우스-자이델 방법은 위 식의 좌변을 $\backslash mathbf\{x\}$에 대해 풀고, 우변에서는 $\backslash mathbf\{x\}$의 이전 값을 사용한다. 이를 분석적으로 표현하면 다음과 같다.
$$\backslash mathbf\; \{x\}^\{(k+1)\}\; =\; \backslash mathbf\; L^\{-1\}\; \backslash left(\backslash mathbf\{b\}\; -\; \backslash mathbf\; U\; \backslash mathbf\{x\}^\{(k)\}\backslash 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를 구하기 위해, 초기값 $\backslash 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}^{(*)})


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

가우스-자이델 방법의 식은 벡터 $\backslash 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*에 대해 전진 대입법을 사용하여 $\backslash mathbf\{x\}^\{(k+1)\}$의 원소를 순차적으로 계산한다.

:$$x^\{(k+1)\}\_i\; =\; \backslash frac\{1\}\{a\_\{ii\}\}\; \backslash left(b\_i\; -\; \backslash sum\_\{j=1\}^\{i-1\}a\_\{ij\}x^\{(k+1)\}\_j\; -\; \backslash sum\_\{j=i+1\}^\{n\}a\_\{ij\}x^\{(k)\}\_j\; \backslash right),\backslash quad\; i=1,2,\backslash dots,n.$$

이 공식은 반복마다 두 개의 합을 사용하며, $x\_j$의 가장 최근에 계산된 반복을 사용하는 하나의 합 $\backslash sum\_\{j\; \backslash ne\; i\}\; a\_\{ij\}x\_j$로 표현할 수 있다.

가우스-자이델 방법의 식은 벡터 $\backslash 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원 연립 일차 방정식의 경우,

:

를 푸는 것을 생각한다. *k*번째 반복에서 얻어진 $x\_1$의 값을 $x\_1^\{(k)\}$로 쓴다. 초기값 $\backslash 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. 논의

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

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

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

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

3. 수렴성

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

* $\backslash mathbf\; A$가 대칭 양의 정부호 행렬인 경우.
* $\backslash mathbf\; A$가 엄격(기약) 대각 지배 행렬인 경우.

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

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

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

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

:$\backslash left\; |\; a\_\{ii\}\; \backslash right\; |\; >\; \backslash sum\_\{i\; \backslash ne\; j\}\; \{\backslash left\; |\; a\_\{ij\}\; \backslash right\; |\}.$

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

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

4. 알고리즘

가우스-자이델 방법은 반복적인 방법으로 선형 방정식의 해를 구하는 알고리즘이다. 알고리즘의 과정은 다음과 같다.

입력: A (n x n 정방 행렬), b (상수 벡터)
출력: φ (해 벡터)

1. 초기 추측값 φ를 선택한다. (보통 0으로 설정)
2. 수렴할 때까지 다음을 반복한다:
* i = 1부터 n까지 반복:
* σ = 0
* j = 1부터 n까지 반복:
* j ≠ i 이면, σ = σ + a_ijφ_j
* φ_i = (b_i - σ) / a_ii
* 수렴 여부 확인 (변화량이 허용 오차보다 작으면 수렴)

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

5. 예제

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

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

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

* 파이썬 및 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 예제이다. 초기화, 반복, 결과 출력을 단계별로 수행하며, 각 단계에 대한 설명을 포함하고 있다.

5.1. 행렬 버전 예제

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

$$\backslash mathbf\; A=$$
\begin{bmatrix}
16 & 3 \\
7 & -11 \\
\end{bmatrix}
\quad \text{and} \quad
\mathbf b =
\begin{bmatrix}
11 \\
13
\end{bmatrix}.


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

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

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

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

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

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

$$\backslash mathbf\; L=$$
\begin{bmatrix}
16 & 0 \\
7 & -11 \\
\end{bmatrix}
\quad \text{and} \quad
\mathbf U =
\begin{bmatrix}
0 & 3 \\
0 & 0
\end{bmatrix}.


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

$$\backslash mathbf\; L^\{-1\}\; =$$
\begin{bmatrix}
16 & 0 \\
7 & -11
\end{bmatrix}^{-1}
=
\begin{bmatrix}
0.0625 & 0.0000 \\
0.0398 & -0.0909 \\
\end{bmatrix}.


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

$$\backslash 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}

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

그 후, 다음을 계산한다.

$$\backslash 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}

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

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

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

5.2. 방정식 버전 예제

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

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

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

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

:$$\backslash 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)에서 시작하여 반복을 진행하면 다음과 같은 근사해를 얻을 수 있다.

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

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

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

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

:$$x^\{(k+1)\}\_i\; =\; \backslash frac\{1\}\{a\_\{ii\}\}\; \backslash left(b\_i\; -\; \backslash sum\_\{j=1\}^\{i-1\}a\_\{ij\}x^\{(k+1)\}\_j\; -\; \backslash sum\_\{j=i+1\}^\{n\}a\_\{ij\}x^\{(k)\}\_j\; \backslash right),\backslash quad\; i=1,2,\backslash dots,n.$$

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

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

:

$k$번째 반복에서 얻어진 $x\_1$의 값을 $x\_1^\{(k)\}$로 쓰고, 초기값 $\backslash 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원 연립 일차 방정식, 즉

:

를 푸는 것을 생각한다. $k$번째 반복에서 얻어진 $x\_1$의 값을 $x\_1^\{(k)\}$로 쓴다. 초기값 $\backslash 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)\}$를 사용하는 야코비 방법을 사용한다. 즉, 새로운 $\backslash vec\{x\}^\{(k+1)\}$를 다른 장소에 기억해 두고, 일제히 $\backslash vec\{x\}$를 갱신한다.

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