가우스-자이델 방법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

가우스-자이델 방법(Gauss-Seidel method)은 연립방정식수치적으로 계산하는 방법으로, 카를 프리드리히 가우스필리프 루트비히 폰 자이델의 이름을 따서 붙여졌다. 가우스-자이델 방법은 연립방정식에 대응하는 행렬을 두 개의 삼각행렬로 분해한 뒤 해를 반복적으로 계산해 수렴시키는 방식을 사용한다.

연립방정식 A\mathbf x = \mathbf 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를 다음과 같이 A = L_*+U의 두 삼각행렬로 분할하는 방식으로 시작한다.

L_* = \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}
U = \begin{bmatrix} 0 & a_{12} & \cdots & a_{1n} \\ 0 & 0 & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & 0 \end{bmatrix}

그러면 원래 방정식을 L_* \mathbf{x} = \mathbf{b} - U \mathbf{x}로 변환할 수 있고, 따라서 다음과 같은 식이 성립한다.

\mathbf{x} = L_*^{-1} (\mathbf{b} - U \mathbf{x})

이제 이 식에서 우변의 결과를 좌변에 대입하는 방식으로 수치적 계산을 실행한다.

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

또한, 여기에서 L_*^{-1}은 삼각행렬이기 때문에, 다음과 같이 계산하는 것이 가능하다.

x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i - \sum_{j>i}a_{ij}x^{(k)}_j - \sum_{j<i}a_{ij}x^{(k+1)}_j \right), 여기에서 i=1,2,\ldots,n

이 방식은 A대칭행렬이면서 양정치행렬일 경우, 또는 강하거나 기약적인 대각지배행렬일 경우 항상 수렴한다는 것이 증명되어 있다. 또한, 이에 해당하지 않는 경우에도 수렴하는 경우가 존재한다.