가우스-조르당 소거법(Gauss-Jordan 소거법)

  가우스-조르당 소거법은 연립방정식의 해를 구하는 방법이다.

  (발음에 따라 가우스-조던 소거법, 가우스-요르단 소거법으로 표기하기도 함)

 

  연립방정식 $Ax = b$ 가 다음과 같이 주어졌을 때

 

$ \begin{pmatrix} 2 & 2 & 1 \\ 2 & 1 & 3 \\ 1 & 2 & 3 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} 11 \\ 11 \\ 10 \end{pmatrix} $

 

  계수행렬(방정식의 계수들로 이루어진 행렬) $A$와 방정식의 결과인 $b$를 묶어 다음과 같은 첨가행렬(Augmented Matrix)로 만들 수 있다.

 

$\begin{pmatrix} 2 & 2 & 1 &|11 \\ 2 & 1 & 3 & | 11\\ 1 & 2 & 3  & | 10 \end{pmatrix} $

 

  이때, 첨가행렬을 기본행연산을 통해 기약행사다리꼴(Reduced Row Echelon Form)으로 만들어 주는 것이 바로 가우스-조르당 소거법이다.

*행사다리꼴 : 아래 행의 선행 원소(행의 첫 0이 아닌 원소)가 윗 행보다 오른쪽에 위치하는 행렬

*행사다리꼴을 만드는 연산을 가우스 소거법이라고 함

*기약행사다리꼴 : 선행원소가 1이고 선행원소를 제외한 모든 나머지 원소가 0인 행사다리꼴

 

 

  전체 코드는 가우스-조르당 소거법의 파이썬 구현(깃허브)를 참조하도록 하고, 여기서는 주요 알고리즘에 대해서만 설명할 것이다.

 

 

 

가우스-조르당 소거법은 크게 

 

2. Back Substitution과정을 통해 선행원소가 아닌 원소를 제거하는 과정

으로 구분할 수 있는데, 두 알고리즘 모두 for 반복문을 활용하여 구현하였다.

 

 

 

1. 선행원소를 찾아 행사다리꼴을 만드는 알고리즘

#1. Leading 1(선행원소)을 찾기 위한 알고리즘
# mcol = 첨가행렬의 열의 갯수
row_count = 0  #연산 중인 열을 지시
for col_count in range(mcol-1): #선행 원소 아래의 값(열 하단)이 0이 될때까지 반복 수행
    comp_num = np.inf # 비교할 숫자의 기본값을 무한대로 지정(보다 작은 수)
 
 
    # 첫 열이 1이거나, 0이 아닌 수 중 가장 작은 행을 추출
    for i in range(row_count,mrow):
        if (0 < abs(matrix[i][col_count])) & (abs(matrix[i][col_count]) < abs(comp_num)) : 
            comp_num = matrix[i][col_count] #절댓값이 가장 작은 첫 행의 값
            first_row = i #첫 행으로 사용할 행
            if matrix[i][0] == 1: #1을 찾은 경우 
                break
    matrix[first_row]=matrix[first_row]/comp_num  #첫 행의 첫 열을 1로 변환
 
    matrix[first_row], matrix[row_count] = matrix[row_count].copy(), matrix[first_row].copy() #대상 인덱스와 첫 행을 교환
    #상수배 후 덧셈연산
    for j in range(row_count+1,mrow):
        if matrix[j][col_count] != 0:
            con_no = matrix[j][col_count]
            matrix[j] = matrix[j] - con_no * matrix[row_count]
 
    #이미 Leading 1을 찾은 행을 연산에서 제외
    row_count += 1
 

  첫 번째 알고리즘에서는 첫번째 반복문을 통해 선행원소가 1이거나 절댓값이 가장 작은 원소를 선택한다. 꼭 0이 아니라면 절댓값이 가장 작을 필요는 없지만, 이후의 연산을 간편하게 하기 위해 임의로 지정한 알고리즘이다(실제로는 0이 아니면 관계없다).

  기본행 연산을 통해 행사다리꼴로 변환할 때 가장 중요한 것은, 첫 원소(1행,1열의 원소)가 0인지 여부이다. 만약 첫 원소가 0이라면, 첫 열의 원소가 0이 아닌 다른 행과 행교환을 해주어야 한다.  예시의 행렬 $A$는 첫 원소가 2이므로 행교환이 필요하지 않다. 첫번째 반복문을 통해 첫 행을 찾았다면, 기본행 연산 중 다른 행과의 덧셈(뺄셈)연산을 통해 이 행의 선행원소를 1로 만들고, 선행원소를 제외한 원소를 0으로 만든다. 

 

  위 과정이 끝나면  다음과 같은 행렬이 반환된다.

$\begin{pmatrix} 1 & 2 & 3 &|10 \\ 0 & -5 & -2 & | -9\\ 0 & -3 & -3  & | -9 \end{pmatrix} $

 

  첨가행렬의 1열은 변환(첫 열의 원소는 1, 이외의 원소는 0)이 완료된 상태이다. 따라서 1열을 제외한 나머지 열에 동일한 변환 연산을 적용하면 되는데, 이 때 1행의 경우 1열의 원소가 0이 아니므로 기본행 연산 시 영향을 줄 수 있으므로 같이 제외한 후 연산한다. 즉, 첨가행렬 M에 1행과 1열을 제외한 부분행렬

$\begin{pmatrix} -5 & -2 & | -9 \\ -3 & -3  & | -9 \end{pmatrix} $

에 대하여 동일한 연산을 수행하면 된다.

따라서 1행/1열부터(파이썬의 인덱스 0) 반복을 지정하여 마지막 행/열까지 순차적으로 수행하면 된다. 반복문 대신 재귀함수의 형태로 구현할 수도 있다.

 

첫 번째 알고리즘이 모두 완료되면 다음과 같은 행사다리꼴이 출력된다(연산 편의를 위해 행교환을 수행하므로, 재귀 형식과는 결과가 다를 수 있다).

$\begin{pmatrix} 1 & 2 & 3 &|10 \\ 0 & 1 & 2 & | -9\\ 0 & 0 & 3 & | 3   \end{pmatrix} $

 

 

 

 

2. 행사다리꼴을 기약행사다리꼴로 만드는 알고리즘

for col in range(mcol-2,0,-1):
    for row in range(col-1,-1,-1): #col/row를 파이썬 인덱스에 맞게 적용
        const = matrix[row][col] * -1 #constraint
        print(col+1,"행을",const, "만큼 상수배하여", row+1, "행의", col+1,"열을 소거") #
        matrix[row] += const * matrix[col]
 
        print(matrix, "\n")

  행사다리꼴 형태를 기약행사다리꼴로 변환하기 위해서는, 계수 행렬의 마지막 열이 1(이고 나머지 열은 0)인 행과 다른 (상위) 행의 덧셈 연산을 수행하고, 이 연산으로 발생한 계수행렬의 한 원소만 0이 아닌 다른 행을 다시 상위 행과 더하여 열을 소거하는 연산을 Back Substitution이라고 한다. 반대로 맨 윗 행부터 소거 연산을 Forward Substitution이라고 하는데, 이 연산에 대해서는 LU 분해 관련 포스팅 에서 보다 자세히 다루었다.

* Forward/Back Substitution은 전진/후진 대입 또는 전/후치환 등으로 번역하기도 한다.

 

  위 알고리즘은 Back Substitution을 통해 행사다리꼴로 변환하면 다음과 같다. 

$\begin{pmatrix} 1 & 0 & 0 &|3 \\ 0 & 1 & 0 & | 2\\ 0 & 0 & 1 & | 1   \end{pmatrix} $

 

  이 때, 첨가행렬의 오른쪽 원소인 $3,2,1$이 각각 $x,y,z$의 해이다.

 

 

 

  실제로 위 알고리즘을 포함한 파이썬 함수(깃허브)를 실행하였을 때 동일한 결과가 추출된다.