가우스 소거법으로 역행렬 구하는 알고리즘 📂행렬대수

가우스 소거법으로 역행렬 구하는 알고리즘

알고리즘

Input

가역행렬 $M \in \mathbb{R}^{n \times n}$ 이 주어져 있다고 하자.

Step 1. 초기화

$M$ 과 같은 사이즈의 항등행렬 $X$ 를 만든다.

Step 2. 에쉘론 폼

가우스 소거법을 통해 $M$ 을 에쉘론 폼으로 만든다. 원래 에쉘론 폼이라고 하면 상삼각행렬의 꼴이면 충분하지만, 역행렬 계산 알고리즘에서는 그냥 대각행렬까지 계산한다. 단, 이 때 $M$ 에 취해지는 행연산을 $X$ 에도 똑같이 취한다.

Output

$MX = XM = E_{n}$ 을 만족하는, 즉 $M$ 의 역행렬인 $X$ 를 얻는다.

예시

구구절절 설명을 듣는 것보다 예시 하나를 보는 게 낫다.

Input

행렬 $M = \begin{bmatrix} 1 & 0 & 1 & 1\\ 2 & 0 & 1 & 0\\ -2& 3 & 4 & 0\\ -5& 5 & 6 & 0\end{bmatrix}$ 이 주어져 있다고 하자.

Step 1. 초기화

$$ \begin{bmatrix} 1 & 0 & 1 & 1 \\ 2 & 0 & 1 & 0 \\ -2& 3 & 4 & 0 \\ -5& 5 & 6 & 0 \end{bmatrix} \cdots \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $$

주어진 행렬과 같은 사이즈의 항등행렬을 만든다. 위에서 좌측이 $M$, 우측이 후에 역행렬이 될 $X$ 다.

Step 2. 에쉘론 폼

엄밀히 따졌을 때, 이 포스트에서 소개하는 방법으로 에쉘론 폼을 만들지는 않는다. 계산의 편의를 위해 대각행렬을 먼저 만들고, 각 행을 피벗으로 나눌 것이다.

$M$ 에 행연산을 취하면서 $X$ 에도 똑같이 취한다는 것은 것은 위와 같이 $M$ 의 첫번째 행에 $-2, 2, 5$ 를 곱해 두번째, 세번째, 네번째 행에 더하는 연산을 $X$ 에서도 똑같이 한다는 것이다.

$$ \begin{align*} & \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 0 & -1 & -2 \\ 0 & 3 & 6 & 2 \\ 0 & 5 & 11 & 5 \end{bmatrix} & \cdots & \begin{bmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ 2 & 0 & 1 & 0 \\ 5 & 0 & 0 & 1 \end{bmatrix} \\ \to & \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 3 & 6 & 2 \\ 0 & 0 & -1 & -2 \\ 0 & 5 & 11 & 5 \end{bmatrix} & \cdots & \begin{bmatrix} 1 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 \\ -2 & 1 & 0 & 0 \\ 5 & 0 & 0 & 1 \end{bmatrix} \end{align*} $$

피벗^pivot이 $0$ 인 경우, 즉 $M_{ii} = 0$ 이면 $M_{ji} \ne 0$ 인 $j$ 번째 행과 $i$ 번째 행을 서로 바꾼다. $M_{ji} \ne 0$ 를 만족하는 $j$행의 존재성은 $M$ 이 가역행렬이라는 가정에 의해 보장된다. 당연히 이 행교환 연산 역시 $X$ 에 똑같이 취해주어야한다.

$$ \begin{align*} & \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 3 & 6 & 2 \\ 0 & 0 & -1 & -2 \\ 0 & 5 & 11 & 5 \end{bmatrix} & \cdots & \begin{bmatrix} 1 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 \\ -2 & 1 & 0 & 0 \\ 5 & 0 & 0 & 1 \end{bmatrix} \\ \to & \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 3 & 6 & 2 \\ 0 & 0 & -1 & -2 \\ 0 & 0 & 1 & 5/3 \end{bmatrix} & \cdots & \begin{bmatrix} 1 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 \\ -2 & 1 & 0 & 0 \\ 5/3 & 0 & -5/3 & 1 \end{bmatrix} \\ \to & \begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 3 & 0 & -10 \\ 0 & 0 & -1 & -2 \\ 0 & 0 & 0 & -1/3 \end{bmatrix} & \cdots & \begin{bmatrix} -1 & 1 & 0 & 0 \\ -10 & 6 & 1 & 0 \\ -2 & 1 & 0 & 0 \\ -1/3 & 1 & -5/3 & 1 \end{bmatrix} \\ \to & \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & -1/3 \end{bmatrix} & \cdots & \begin{bmatrix} 0 & -2 & 5 & -3 \\ 0 & -24 & 51 & -30 \\ 0 & -5 & 10 & -6 \\ -1/3 & 1 & -5/3 & 1 \end{bmatrix} \end{align*} $$

$M$ 이 대각행렬이 될 때까지 반복한다. 원래는 상삼각행렬의 꼴로 만든 후 행을 피벗으로 나누어 에쉘론 폼으로 만든 후, 다른 행의 피벗 이후 성분들을 소거시키는 식으로 하지만 코드 작성에서 번거롭기 때문에 그냥 순서를 바꾼 것이다. 이렇게 순서를 바꿔도 무방한 이유는 가우스 소거법의 이론적인 배경에서 찾을 수 있다.

$$ \begin{align*} & \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & -1/3 \end{bmatrix} & \cdots & \begin{bmatrix} 0 & -2 & 5 & -3 \\ 0 & -24 & 51 & -30 \\ 0 & -5 & 10 & -6 \\ -1/3 & 1 & -5/3 & 1 \end{bmatrix} \\ \to & \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} & \cdots & \begin{bmatrix} 0 & -2 & 5 & -3 \\ 0 & -8 & 17 & -10 \\ 0 & 5 & -10 & 6 \\ 1 & -3 & 5 & -3 \end{bmatrix} \end{align*} $$

대각행렬을 완성했다면 각 행을 각각의 피벗으로 나누어준다. 이제 $M$ 은 항등행렬의 꼴이어야한다.

Output

$$ X = \begin{bmatrix} 0 & -2 & 5 & -3 \\ 0 & -8 & 17 & -10 \\ 0 & 5 & -10 & 6 \\ 1 & -3 & 5 & -3 \end{bmatrix} $$

$X$ 는 $M$ 의 역행렬이다. 지금까지의 과정를 요약하면 다음과 같다.

$$ \begin{align*} & \begin{bmatrix} 1 & 0 & 1 & 1 \\ 2 & 0 & 1 & 0 \\ -2& 3 & 4 & 0 \\ -5& 5 & 6 & 0 \end{bmatrix} & \cdots & \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \\ \to & \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 0 & -1 & -2 \\ 0 & 3 & 6 & 2 \\ 0 & 5 & 11 & 5 \end{bmatrix} & \cdots & \begin{bmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ 2 & 0 & 1 & 0 \\ 5 & 0 & 0 & 1 \end{bmatrix} \\ \to & \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 3 & 6 & 2 \\ 0 & 0 & -1 & -2 \\ 0 & 5 & 11 & 5 \end{bmatrix} & \cdots & \begin{bmatrix} 1 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 \\ -2 & 1 & 0 & 0 \\ 5 & 0 & 0 & 1 \end{bmatrix} \\ \to & \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 3 & 6 & 2 \\ 0 & 0 & -1 & -2 \\ 0 & 0 & 1 & 5/3 \end{bmatrix} & \cdots & \begin{bmatrix} 1 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 \\ -2 & 1 & 0 & 0 \\ 5/3 & 0 & -5/3 & 1 \end{bmatrix} \\ \to & \begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 3 & 0 & -10 \\ 0 & 0 & -1 & -2 \\ 0 & 0 & 0 & -1/3 \end{bmatrix} & \cdots & \begin{bmatrix} -1 & 1 & 0 & 0 \\ -10 & 6 & 1 & 0 \\ -2 & 1 & 0 & 0 \\ -1/3 & 1 & -5/3 & 1 \end{bmatrix} \\ \to & \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & -1/3 \end{bmatrix} & \cdots & \begin{bmatrix} 0 & -2 & 5 & -3 \\ 0 & -24 & 51 & -30 \\ 0 & -5 & 10 & -6 \\ -1/3 & 1 & -5/3 & 1 \end{bmatrix} \\ \to & \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} & \cdots & \begin{bmatrix} 0 & -2 & 5 & -3 \\ 0 & -8 & 17 & -10 \\ 0 & 5 & -10 & 6 \\ 1 & -3 & 5 & -3 \end{bmatrix} \end{align*} $$

코드

다음은 가우스 소거법으로 역행렬을 구하는 줄리아 코드다.

using LinearAlgebra

M = [
      1 0 1 1
      2 0 1 0
     -2 3 4 0
     -5 5 6 0
     ]
inv_M = inv(M)

n = size(M)[1]
M = Float64.(M)
X = Matrix(1.0I,n,n)
for j = 1:n
    if iszero(M[j,j])
        for i = j:n
            if !iszero(M[i,i])
                M[[j,i],:] = M[[i,j],:]
                X[[j,i],:] = X[[i,j],:]
                break
            end
        end
    end

    pivot = M[j,j]
    for i = 1:n
        if i == j continue end
        r = (- M[i,j] / pivot)
        M[i,:] += r*M[j,:]
        X[i,:] += r*X[j,:]
    end
end

for i = 1:n
    pivot = M[i,i]
    M[i,:] /= pivot
    X[i,:] /= pivot
end
M
X
inv_M