2. Gauss Elimination

예제를 통해 보는 것이 가장 쉽다.

\[\left[\begin{array}{clr}1&2&3\\4&5&6\\7&8&9\end{array}\right]\]

위 매트릭스를 upper triangle로 만드는 것이 목적이다. Row2 - 4\(\times\)Row1와 Row3 - 7\(\times\)Row1을 하면

\[\left[\begin{array}{clr}1&2&3\\0&-3&-6\\0&-6&-12\end{array}\right]\]

Row3 - 2\(\times\)Row1를 하면

\[\left[\begin{array}{clr}1&2&3\\0&-3&-6\\0&0&0\end{array}\right]\]

Upper triangle \(U\)가 완성됐다.

규칙은 간단하다. 먼저 매트릭스의 엔트리 중 제일 왼쪽 위 요소를 1st pivot으로 잡는다. 이후 그 피봇이 있는 열을 피봇을 제외하고 0이 되도록 행 연산을 해줘야한다. 두번째 행에서 첫번째 행의 상수배를 빼주고 세번째 행에서 첫번째 행의 상수배를 빼준다. 그럼 첫번째 피봇이 있는 열에는 피봇을 제외하고 모두 0이 된다. 마찬가지로 다음 열에 대해서도 하면 된다.

 

Python implementaion

def gauss_elimination(A:np.ndarray, b:np.ndarray):
    row_num, col_num = A.shape
    pivot_row, pivot_col = 0, 0
    while pivot_row < row_num and pivot_col < col_num:
        if A[pivot_row, pivot_col] == 0:
            pivot_col += 1
            continue
        else:
            pivot = A[pivot_row,:]
            for i in range(pivot_row + 1,row_num):
                ratio = A[i,pivot_col] / pivot[pivot_col]
                A[i,:] = A[i,:] - ratio * pivot
                b[i] = b[i] - ratio * b[pivot_row]
            pivot_row += 1
            pivot_col += 1
    return A, b