선형대수학_2.선형방정식 Ax=b(Part1)(2)

안녕하세요. (설 쇠고 돌아온) 김경찬입니다. 오늘은 지난 글에서 이야기했다시피 $A\mathrm{x}=b$에서 $A$가 정사각행렬이고, $rank(A)$와 행의 개수가 같은 경우의 선형 방정식의 해법에 대해 알아보도록 하겠습니다.

가우스 소거법(Gaussian Elimination)

다음과 같은 방정식이 주어져 있다고 칩시다.
$$A\mathrm{x}=\left[\begin{array}{ccc}2& 1& 1\\ 4& -6& 0\\ -2& 7& 2\end{array}\right]\left[\begin{array}{c}x\\ y\\ z\end{array}\right]=\left[\begin{array}{c}5\\ -2\\ 9\end{array}\right]=b$$
이제부터 위와 같은 방정식을 아래와 같이 행렬의 각 원소들과 $b$의 값들만 사용해서 간편하게 나타내도록 하겠습니다.

$$\left[\begin{array}{ccccc}2& 1& 1& |& 5\\ 4& -6& 0& |& -2\\ -2& 7& 2& |& 9\end{array}\right]$$
가우스 소거법의 목적은 위의 방정식을 “동등하게 변환해” 아래와 같은 형태로 만드는 것입니다.

$$\left[\begin{array}{ccccc}a& \ast & \ast & |& c_1\\ 0& b& \ast & |& c_2\\ 0& 0& c& |& c_3\end{array}\right]$$
위와 같이 $n\times n$ 행렬에 대해 행렬의 대각성분 위로만 0이 아닌 값이 존재하는 형태를 Upper Triangular form 이라고 합니다. $A$가 Upper triangular form 의 형태를 갖는 경우에 방정식의 해는, 가장 마지막 미지수부터 차례대로 값을 대입해서 위의 식에서 빼주는 방식으로 매우 쉽게 구할 수 있습니다.

그럼 과연 어떻게 기존의 행렬을 “동등하게 변환해서” Upper triangular form 을 만드는 것일까요? 다음과 같이 3가지 Elementary row operation 을 사용합니다. Elementary row operation 을 사용할 때는 행렬 $A$와 $b$에 동시에 적용합니다.

1. 2개의 row 를 교환한다(Row exchange)
   예시) (2번째, 3번째 row를 교환)
   $$\left[\begin{array}{ccccc}2& 1& 1& |& 5\\ 4& -6& 0& |& -2\\ -2& 7& 2& |& 9\end{array}\right]⟹\left[\begin{array}{ccccc}2& 1& 1& |& 5\\ -2& 7& 2& |& 9\\ 4& -6& 0& |& -2\end{array}\right]$$
2. 한 개의 row 에 다른 row의 상수배만큼을 더해준다.
   예시) 2번째 row에 1번째 row의 1배만큼을 더해줌
   $$\left[\begin{array}{ccccc}2& 1& 1& |& 5\\ -2& 7& 2& |& 9\\ 4& -6& 0& |& -2\end{array}\right]⟹\left[\begin{array}{ccccc}2& 1& 1& |& 5\\ 0& 8& 3& |& 14\\ 4& -6& 0& |& -2\end{array}\right]$$
3. row 에 0이 아닌 숫자를 곱해준다.
   예시) 1번째 row 에 $\frac{1}{2}$, 2번째 row 에 $\frac{1}{8}$을 곱해준다.
   $$\left[\begin{array}{ccccc}2& 1& 1& |& 5\\ 0& 8& 3& |& 14\\ 0& 0& 1& |& 2\end{array}\right]⟹\left[\begin{array}{ccccc}1& 1/2& 1/2& |& 5/2\\ 0& 1& 3/8& |& 7/4\\ 0& 0& 1& |& 2\end{array}\right]$$

위와 같이 3종류의 row operation을 적당한 순서로 적용하다 보면 어느새 Upper triangular form 으로 변환된 것을 볼 수 있습니다. 이제 방정식을 푸는 것은 쉽습니다. 결과는 $x=1,y=1,z=2$이네요.

Singular Case에서는?

만약에 해가 유일하지 않은 경우(부정 혹은 불능) 위의 Elementary row operation 을 적용하면 어떻게 될까요?(앞선 글에서 이런 경우를 Singular이라고 했던 것이 기억나시나요?) 행렬에서 각 행의 가장 왼쪽에 있는 0이 아닌 원소를 Pivot 이라 합니다.( Upper trianguler form 은 각 행의 Pivot이 위에 있는 행들의 pivot 보다 더 오른쪽에 있는 형태입니다.) 여기서 증명하지는 않겠지만, Singular case에 대해서는 Row operation 을 적용하다 보면 Pivot 이 0인 행이 남게 됩니다. 가우스 소거법을 풀다가 아래와 같은 행렬이 나온다면, 해당 방정식이 Singular 하다는 것입니다.
$$\left[\begin{array}{ccccc}a& \ast & \ast & |& c_1\\ 0& b& \ast & |& c_2\\ 0& 0& 0& |& c_3\end{array}\right]$$

Row Operation 을 행렬로 나타내기

위의 Elementary row operation 들을 모두 다음과 같은 행렬을 $A$와 $b$의 왼쪽에 곱하는 것으로 생각할 수 있습니다.

1. 행 교환 : Permutation matrix $P$
   예시) 1번째 행과 2번째 행을 교환
   $$P\left[\begin{array}{cc}A& b\end{array}\right]=\left[\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{cc}A& b\end{array}\right]$$
2. 한 개의 row 에 다른 row의 상수배만큼을 더하기
   예시) 2번째 행에 1번째 행의 2배만큼을 더하기
   $$M\left[\begin{array}{cc}A& b\end{array}\right]=\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{cc}A& b\end{array}\right]$$
   여기서 $M$은 대각 성분 아래로만 0이 아닌 값들이 있으므로, Lower triangular form 이라고 합니다.
3. 한 개의 row 에 0이 아닌 값을 곱해주기
   예시) 1번째 row 에 $\frac{1}{2}$​, 2번째 row 에 $\frac{1}{8}$​을 곱해준다.
   $$D\left[\begin{array}{cc}A& b\end{array}\right]=\left[\begin{array}{ccc}1/2& 0& 0\\ 0& 1/8& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{cc}A& b\end{array}\right]$$

Triangular Factorization $PA=LU$

앞서 가우스 소거법은 3가지 Elementary row operation 들을 조합하므로써 나타낼 수 있다는 것을 알아보았고, Elementary row operation 들이 사실은 행렬의 곱셈으로 나타낼 수 있다는 것을 알아보았습니다. 그렇다면, 가우스 소거법을 행렬의 곱으로 나타낼 수 있겠군요. 바로 위에서 설명한 3가지 행렬들로 말이죠. 그런데 가우스 소거법을 적용한 행렬 곱의 결과물을 단순화하기 위해 적용하면 좋은 팁들이 여기에 있습니다.

1. 우선은 행 바꾸기 $P$는 바로 아래 행의 Pivot 이 0인 경우에만 사용하도록 합시다.
   예시)
   $$\left[\begin{array}{ccc}2& 1& 1\\ 0& 0& 3\\ 0& 5& 1\end{array}\right]⟹\left[\begin{array}{ccc}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right]\left[\begin{array}{ccc}2& 1& 1\\ 0& 0& 3\\ 0& 5& 1\end{array}\right]=\left[\begin{array}{ccc}2& 1& 1\\ 0& 5& 1\\ 0& 0& 3\end{array}\right]$$
2. 각 row 에 0이 아닌 값을 곱해주는 $D$ 행렬은, 마지막에 $A$의 Upper triangular form이 완성된 이후에 대각선을 모두 1로 만들어주기 위한 용도로만 사용합니다.(아니면 아예 사용하지 않아도 됩니다.)
   $$\left[\begin{array}{ccc}2& 1& 1\\ 0& 5& 1\\ 0& 0& 3\end{array}\right]=\left[\begin{array}{ccc}2& 0& 0\\ 0& 5& 0\\ 0& 0& 3\end{array}\right]\left[\begin{array}{ccc}1& 1/2& 1/2\\ 0& 1& 1/5\\ 0& 0& 1\end{array}\right]$$

즉 위의 두 가지 row operation 을 제외한, 2번째 row operation 만을 활용해 Upper triangular form 을 만드는 것이 가능하다면 가장 깔끔하다는 것이죠. 이 2번째 row operation 을 이제부터 편의상 Addition 이라고 부르도록 하겠습니다.

Addition 의 역연산은 Substitution

Addition 에 해당하는 행렬 곱의 역연산을 생각해봅시다. 앞서 예를 든 행렬
$$M=\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ 0& 0& 1\end{array}\right]$$
는 2번째 행에 1번째 행의 2배 만큼을 더해주는 연산입니다. 이 연산의 역연산은? 자연스럽게 생각해보면 2번째 행에서 1번째 행의 2배 만큼을 빼주는 연산입니다.

$$ML=\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ -2& 1& 0\\ 0& 0& 1\end{array}\right]=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$$
실제로도 위와 같이 두 행렬을 곱하면 단위 행렬을 얻을 수 있음을 알 수 있고요.

종합해 보기

그럼 이제까지 결과들을 종합해, 다음의 방정식을 Upper triangular form으로 바꾸어 봅시다. 아래의 풀이에서 한 줄은 각각 왼쪽에 표시한 행렬을 이전 단계의 행렬에 계속 곱해주는 것입니다.
$$\begin{array}{rl}A\mathrm{x}=b:& \left[\begin{array}{ccccc}1& 2& 4& |& 0\\ -1& 0& -5& |& 3\\ 1& 3& 4& |& 1\end{array}\right]\\ M_1=\left[\begin{array}{ccc}1& 0& 0\\ 1& 1& 0\\ 0& 0& 1\end{array}\right]⟹& \left[\begin{array}{ccccc}1& 2& 4& |& 0\\ 0& 2& -1& |& 3\\ 1& 3& 4& |& 1\end{array}\right]\\ M_2=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ -1& 0& 1\end{array}\right]⟹& \left[\begin{array}{ccccc}1& 2& 4& |& 0\\ 0& 2& -1& |& 3\\ 0& 1& 0& |& 1\end{array}\right]\\ M_3=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& -1/2& 1\end{array}\right]⟹& \left[\begin{array}{ccccc}1& 2& 4& |& 0\\ 0& 2& -1& |& 3\\ 0& 0& 1/2& |& -1/2\end{array}\right]\\ ⟹M_3{M}_2{M}_{1}A\mathrm{x}=& \left[\begin{array}{ccc}1& 2& 4\\ 0& 2& -1\\ 0& 0& 1/2\end{array}\right]\mathrm{x}=U\mathrm{x}=\left[\begin{array}{c}0\\ 3\\ -1/2\end{array}\right]=c\end{array}$$
위의 변환 과정을 통해, $A\mathrm{x}=b$를 해결하는 것은 $U\mathrm{x}=c$를 해결하는 것과 동치가 되었습니다. 우리가 원하는 결과를 얻었어요!!(짝짝짝)

$LU$ 분해

처음으로 “행렬의 분해” 에 대해 소개하게 되는데요. 행렬의 분해는 행렬에 대해 수행하는 다양한 연산을 빠르게 수행할 수 있도록 행렬을 특정 성질을 가진 다른 행렬들의 곱으로 나타내는 것을 말합니다. $LU$분해는 행렬 $A$를 Lower triangular matrix $L$과 Upper triangular matrix $U$의 곱으로 분해하는 것으로, 위와 같은 선형 방정식을 빠르게 풀거나, 행렬의 역행렬을 구할 때 사용할 수 있습니다.
위의 풀이 전개의 마지막 과정에 다음과 같은 식이 등장하는데요.
$$M_3{M}_2{M}_{1}A=\left[\begin{array}{ccc}1& 2& 4\\ 0& 2& -1\\ 0& 0& 1/2\end{array}\right]=U$$
앞서 언급한 "Addition 의 역연산은 Substitution이다"를 적용하면,
$$\begin{array}{rl}A& =M_1^{-1}{M}_2^{-1}{M}_3^{-1}\left[\begin{array}{ccc}1& 2& 4\\ 0& 2& -1\\ 0& 0& 1/2\end{array}\right]\\ & =\left[\begin{array}{ccc}1& 0& 0\\ -1& 1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 1& 0& 1\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 1/2& 1\end{array}\right]\left[\begin{array}{ccc}1& 2& 4\\ 0& 2& -1\\ 0& 0& 1/2\end{array}\right]\\ & =\left[\begin{array}{ccc}1& 0& 0\\ -1& 1& 0\\ 1& 1/2& 1\end{array}\right]\left[\begin{array}{ccc}1& 2& 4\\ 0& 2& -1\\ 0& 0& 1/2\end{array}\right]=LU\end{array}$$
LU 분해를 진행하다가 Pivot 이 0이 되는 경우가 있는데요. 이 경우에는 Row exchange(Permutation)을 사용해 해당 성분이 0이 아닌 행과 교환 한 뒤 진행해주면 됩니다. 이 경우 그 Permutation matrix $P$를 $A$ 앞에 곱연산 해주어, $PA=LU$의 형태로 분해하면 됩니다.

$LU$분해를 어디에 쓸까?

그냥 선형 방정식 $A\mathrm{x}=b$를 해결하는 것만이 목적이라면 굳이 $L$을 알 필요 없이 $U\mathrm{x}=c$만 해결하면 됩니다. 그러나 만약 행렬 $A$가 정해져 있고, 다양한 $b$의 값에 대해 선형 방정식을 해결해야 할 경우가 있다면 어떨까요? 그 경우 $LU$분해를 사용하면 반복적인 연산을 줄일 수 있답니다.

$$\begin{array}{rl}A\mathrm{x}=b⟹& LU\mathrm{x}=b\\ ⟹& Lc=b,U\mathrm{x}=c\end{array}$$

위의 과정에서 $Lc=b$를 Forward substitution(전진 대입), $Ux=c$를 Backward Substitution(후진 대입)이라 합니다. 만약 행렬 $A$에 대해 $L,U$를 미리 알고 있다면, $b$가 어떤 값으로 주어지더라도 먼저 전진 대입을 통해 $c$의 값을 계산해주고, $Ux=c$에서 $x$를 계산하는 것으로 해당 방정식의 해를 구할 수 있는데요. $Lc=b,Ux=c$라는 방정식을 해결하기는 굉장히 쉽기 때문에, 매번 가우스 소거법을 적용하는 것보다 효율적으로 방정식의 해를 구할 수 있습니다.

이번 글에서는 이렇게 가우스 소거법과 $LU$ 분해에 대해 알아보았습니다. 어쩌다 보니 또 글이 매우 길어졌네요 ㅜㅜ. 다음부터는 글의 길이를 조금 줄이는 법을 고민해 봐야할까요? 모르는 점 있으면 댓글 달아주시면 답해 드리도록 하겠습니다. 감사합니다!!