가우스-자이델 방법

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

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

$A=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right],𝐱=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right],𝐛=\left[\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_n\end{array}\right]$

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

$L_{*}=\left[\begin{array}{cccc}{a}_{11}& 0& \cdots & 0\\ a_{21}& a_{22}& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right]$

$U=\left[\begin{array}{cccc}0& a_{12}& \cdots & a_{1n}\\ 0& 0& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 0\end{array}\right]$

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

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

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

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

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

$x_i^{(k+1)}=\frac{1}{a_{ii}}(b_i-\sum _{j>i}{a}_{ij}{x}_j^{(k)}-\sum _{j<i}{a}_{ij}{x}_j^{(k+1)})$, 여기에서 $i,j=1,2,\dots ,n$

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

같이 보기

• LU 분해
• 축차가속완화법(successive over-relaxation)
• 야코비 방법

참고 문헌

• Abdelwahab Kharab; Ronald B. Guenther (2013). 《An Introduction to Numerical Methods A MATLAB Approach》 [이공학도를 위한 수치해석]. 학산미디어. ISBN 978-89-966211-8-8.