가우스-자이델 방법

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

연립 일차 방정식 $A 𝐱 = 𝐛$ 와 이에 대응하는 변수와 상수

A = [\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}], 𝐱 = [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}], 𝐛 = [\begin{matrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{n} \end{matrix}]

에 대해, 가우스-자이델 방법은 행렬 $A$ 를 다음과 같이 $A = L_{*} + U$ 의 두 삼각행렬로 분리하는 방식으로 시작한다.

L_{*} = [\begin{matrix} a_{11} & 0 & \dots & 0 \\ a_{21} & a_{22} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}]

U = [\begin{matrix} 0 & a_{12} & \dots & a_{1 n} \\ 0 & 0 & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & 0 \end{matrix}]

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

𝐱 = L_{*}^{- 1} (𝐛 - U 𝐱)

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

𝐱^{(k + 1)} = L_{*}^{- 1} (𝐛 - U 𝐱^{(k)})

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

x_{i}^{(k + 1)} = \frac{1}{a_{i i}} (b_{i} - \sum_{j > i} a_{i j} x_{j}^{(k)} - \sum_{j < i} a_{i j} x_{j}^{(k + 1)})

, 여기에서

i, j = 1, 2, \dots, n

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

같이 보기