성공의 커다란 비결은 결코
지치지 않는 인간으로 인생을 살아가는 것이다.
- 알버트 슈바이처 -
안녕하세요 저번 포스팅에서는 선형 대수 공부의 첫 단원으로써, 선형 방정식을 Row picture와 Column picture의 관점에서 바라보고 이를 이용하여 식의 솔루션을 구하는 방법들에 대해 간단히 살펴보았습니다. 해당 포스팅을 먼저 읽고 이번 포스팅을 공부하시면 면 이해하는데 큰 도움이 됩니다 :)
[이론/MIT 선형대수] - [문과도 이해하는 선형대수 for 딥러닝] 1. 선형 방정식 (The geometry of linear equations)
[문과도 이해하는 선형대수 for 딥러닝] 1. 선형 방정식 (The geometry of linear equations)
사람들이 대개 기회를 놓치는 이유는 기회가 작업복 차림의 일꾼같아 일로 보이기 때문이다. - 토마스 A. 에디슨 - 제 블로그의 'MIT 선형대수' 카테고리의 포스팅들은 Gilbert Strang 교수님의 Linear Al
box-world.tistory.com
이번 시간은 앞서 본 선형 방정식의 해를 구하는 또 하나의 방법인 소거 (Elimination)에 대해 공부해보겠습니다!
1. 소거 (Elimination)
아래엔 우리가 풀어야 할 선형 방정식이 주어져있습니다.
$$\begin{cases}x+2y+z=2 \\ 3x+8y+z=12 \\ 4y+z=2 \end{cases}$$
위 식에서 좌변의 계수 (coefficient)를 행렬로 표현하면 다음과 같습니다. 우변에 존재하던 벡터 $\begin{bmatrix}2 \\ 12 \\ 2 \end{bmatrix}$는 이따가 함께 다시 고려하겠습니다.
$$\begin{bmatrix}1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix}$$
이제부터 elimination을 해볼텐데요. 이것의 목표는 결국 아래와 같은 모양의 상 삼각행렬 (Upper triangle matrix)를 도출하는 것입니다. 이렇게 되면 가장 아래의 row에서는 $u_{n,n}=?$의 식부터 미지수가 하나씩 풀리면서 이 값을 바로 위 식들에 차례로 연쇄적으로 대입해가며 풀리게 됩니다! (이 과정이 이따 살펴볼 역 대입입니다)
다시 $\begin{bmatrix}1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix}$로 돌아와서 이것을 위 형태로 변형시키기 위해서는 2행의 3을 제거해줘야합니다. 이를 위해서 1행에 3을 곱해서 2행에서 빼면 간단히 해결되겠죠? 결과는 다음과 같습니다.
$$\begin{bmatrix}1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix}$$
이제 우리는 3행의 4를 지우면 Upper triangle matrix (=$U$)의 형태를 얻을 수 있습니다. 이를 위해서 2행에 2를 곱하여 3행에 빼면 될 것이고 결과는 다음과 같습니다.
$$U = \begin{bmatrix} \underline{1} & 2 & 1 \\ 0 & \underline{2} & -2 \\ 0 & 0 & \underline{5} \end{bmatrix}$$
이때 위 식에서 밑줄 친 숫자들은 피봇 (pivot)이라고 칭합니다. 이때 pivot은 절대 0이 될 수 없습니다.
그렇다면 다른 예로 소거 과정에서 $\begin{bmatrix}0& 2 & 1 \\ 1 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix}$처럼 1행의 첫번째 자리에 0이 있다고 해서 elimination에 실패한 것일까요? 그렇진 않고 간단하게 1행과 2행을 바꾸어 주면 됩니다! 그러나 $\begin{bmatrix}0& 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix}$처럼 어떤 행과 교환해도 소용없다면 이 경우 elimination을 할 수 없다고 판단합니다.
2. 역 대입 (Back subtitution)
이제 우변까지 고려하여 함께 elimination을 진행해보겠습니다. 이를 위해 우변의 벡터를 다음과 같이 첨가하겠습니다. 이때 첨가된 우변의 벡터를 augmented matrix라고 부릅니다.
$$\begin{bmatrix}1 & 2 & 1 & 2 \\ 3 & 8 & 1 & 12\\ 0 & 4 & 1 &2 \end{bmatrix}$$
위 식을 아까 우리가 같이 했던 소거 방식을 똑같이 적용하면 다음과 같은 결과가 도출됩니다! 계산 과정은 생략하겠습니다..ㅎㅎ
$$\begin{bmatrix}1& 2 & 1 & 2 \\ 0 & 2 & -2 & 6\\ 0 & 0 & 5 & -10\end{bmatrix}$$
이제 위 행렬 식을 아래와 같이 우리에게 친숙한 연립 방정식의 형태로 가져오면, 그 다음은 제가 설명드리지 않아도 모두가 너무나도 잘 아시는 과정이죠? $z$부터 시작하여 아래에서 위로 올라가면서 연쇄적으로 미지수를 구하게 됩니다! 이것을 역 대입 (Back subtitution)이라고 합니다.
3. Matrix multiplication
방금까지 우리는 행렬 $A$에서 Upper triangle 행렬 $U$를 도출하는 과정을 보았습니다. 그리고 이때 $A$와의 곱셈을 통해 $U$를 도출시켜주는 행렬을 Elimination matrix라고 부르는데요. 이 과정이 보다 직관적으로 쉽게 다가오게 하는 연산 두가지에 대해 먼저 공부해보겠습니다. 우선 행렬과 Column vector의 곱셈에 대해 살펴보겠습니다.
$$\begin{bmatrix}-&-&- \\ -&-&-\\ -&-&- \end{bmatrix} \begin{bmatrix}3 \\ 4 \\ 5 \end{bmatrix}=\begin{bmatrix}3 \times Column \ 1 \\ 4 \times Column \ 2 \\ 5 \times Column \ 3 \end{bmatrix}$$
위에서 보다시피 행렬곱셈, 즉 왼쪽에 행렬이 있고 이것과 벡터를 곱하게 될땐 Columns에 대한 linear combination과 같습니다. 이제 row vector과 행렬의 곱셈에 대해 살펴보겠습니다.
$$\begin{bmatrix}1 & 2 & 7 \end{bmatrix} \begin{bmatrix}-&-&- \\ -&-&-\\ -&-&- \end{bmatrix}=\begin{bmatrix}1 \times row \ 1 \\ 2 \times row \ 2 \\ 7 \times row \ 2 \end{bmatrix}$$
위와 같이 row vector와 행렬의 곱셈은 row에 대한 선형결합이 됩니다.
4. 소거 행렬 (Elimination matrix) 구하기
$$\begin{bmatrix}E_{1,1}&E_{1,2}&E_{1,3} \\ E_{2,1}&E_{2,2}&E_{2,3}\\ E_{3,1}&E_{3,2}&E_{3,3} \end{bmatrix} \begin{bmatrix}1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix} = \begin{bmatrix}1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix}$$
이제 우리는 앞서 보았듯 행렬 $A$를 $U$로 만드는 Elimination matrix를 구해보려 합니다. 우선 $E_1$의 첫번째 row인 $\begin{bmatrix}E_{1,1}&E_{1,2}&E_{1,3}\end{bmatrix}$는 무엇일까요? 쉽게 생각해서 첫번째 row가 무엇이어야 이것을 $A$를 곱하여 $U$의 첫번째 row가 나올까?를 생각하면 됩니다!
마찬가지로 Elimination matrix의 두번째 row와 $A$를 곱하여 $\begin{bmatrix}0 & 2 & -2 \end{bmatrix}$가 나오게 하는 row는 앞서 말했듯 $A$의 첫번째 row를 3배하여 두번째 row에 빼야하므로 $\begin{bmatrix}-3 & 1 & 0 \end{bmatrix}$이 됩니다. 마찬가지의 원리를 세번째 row에도 적용하면 다음과 같이 나오겠죠
$$\begin{bmatrix}1&0&0 \\ -3&1&0\\ 0&0&1 \end{bmatrix} \begin{bmatrix}1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix} = \begin{bmatrix}1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix}$$
이제 우리는 $\begin{bmatrix}1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix}$을 최종적인 U로 만들어준 또다른 Elimination matrix를 찾아야합니다. 마찬가지로 구하면 다음과 같겠죠? (계산은 생략하겠습니다!)
$$\begin{bmatrix}1&0&0 \\ 0&1&0\\ 0&-2&1 \end{bmatrix} \begin{bmatrix}1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix} = \begin{bmatrix}1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 5 \end{bmatrix}$$
이때 앞서 첫번째 찾았던 Elimination matrix를 $E_1$, 방금 구한 Elimination matrix를 $E_2$라고 한다면, 우린 결국 $U$를 구하는 과정을
$$E_2(E_1A)$$
라고 표현할 수 있습니다. 이때 본래 행렬 간의 곱셈에선 순서를 바꿀 수 없지만, 누굴 먼저 곱할지는 괄호를 바꿔 $$(E_2E_1)A$$처럼 사용할 순 있습니다.
이번 포스팅에서는 선형 방정식의 Solution을 구하는 또 하나의 방법인 Elimination matrix에 대해 공부해보았습니다.
긴 글 읽어주셔서 감사합니다. 오늘도 행복한 하루 보내세요 :)
다음 포스팅도 바로 보러 고고!
[문과도 이해하는 선형대수 for 딥러닝] 3. 행렬곱, 역행렬, 가우스-조던 소거법 (Multiplication and Inve
늘 명심하라. 성공하겠다는 너 자신의 결심이 다른 어떤 것보다 중요하다는 것을. - 아브라함 링컨 - 곱셈(multiplication)과 역행렬(inverse matrix)은 선형 대수학에서 가장 기본이 되는 연산 중 하나입
box-world.tistory.com