[MML] 2.3 Row Echelon Form
Mathematics for machine Learning(머신러닝수학)
이번 글에 대한 저의 유튜브 강의 2개부터 먼저 걸어드립니다. :) 뒤 이어 글이 시작됩니다.
- 이 글은 Mathematics for Machine Learning(Cambridge Univ. Marc Peter Deisenroth 외 2)- 머신러닝을 위한 수학-의 내용을 번역 및 재해석해서 작성한 글입니다. 위 책의 내용에 이해를 돕는 글을 추가로 첨부하였으며 완전한 번역본이 아님을 알려드립니다. -
이번 글의 도입 : Row Echelon Form
지난 시간에 일차연립방정식에서 식의 개수가 문자의 개수보다 작을 때 나타나는 해가 무수히 많은 상황에서 '특수해'와 '일반해'의 개념을 도입했습니다. 그 두 개념을 설명하는데 집중했을 뿐 이를 구하는 일반적인 방법을 소개하지는 않았습니다. 오늘은 어떻게 특수해와 일반해를 잘 구할 수 있는지에 대해서 살펴봅니다.
이 과정에서 중2 때 배웠던 가감법, 양변을 적절한 수로 곱하는 등의 간단한 연산이 진행이 됩니다. 이런 정도의 연산을 통해 잘 정리된 형태를 일컽는 row-echolon form (행 사다리꼴) , 더욱 잘 정리한 reduced row echelon form등의 용어에 대해서 다룰 예정입니다.
[Ch 2.3.2] Elementary Transformations
이 단원에서 복잡한 행렬을 간단하게 만드는 변환인 Elementary Transformations에서 가장 중요한 키포인트는
- 식 까리의 가감법, 양변을 같은 수로 곱하기 등의 방법으로 계수는 간단하게 바꾼다.
- 해는 변화시키지 않는다.
입니다.
예를 들어서 아래의 식을 간단하게 바꾸어봅시다.
그러면 좌변의 계수들은 행렬로 나타내되, 행렬 맨 뒤에 한 줄을 긋고 우변의 값들도 함께 표현해줍니다. 이러한 형태를 augmented matrix(첨가 행렬)이라고 합니다.
그러면 1행과 3행을 서로 바꾸어볼까요? (swap R1 with R3) 기왕이면 맨 앞에 1이 있는 열이 맨 위에 있는게 좋으니까요.
그리고 2,3,4행의 맨 앞 숫자를 가감법을 통해 0으로 바꾸려고 합니다. 그러면 아래처럼 앞 부분이 정리가 되죠.
그리고 각 행에서 0이 아닌 처음 나오는 숫자는 1로 바꾸어줍니다. 그래서 적절하게 행에 숫자를 곱해줍니다.
이렇게 마지막으로 정리된 형태가 아래의 결과입니다.
그러면 원래의 식은 다음과 같이 바뀌는거죠.
마지막 열에서 a의 값은 -1이란 걸 알 수 있습니다. 그리고 위의 식을 만족시키는 특수해 하나를 찾아보면
을 구할 수 있고, 아까 일반해 찾던 방법대로 찾아보면
를 찾아낼 수 있습니다.
Row Echelon Form과 연립방정식의 해
위에서 열심히 행을 바꾸고 빼고 실수배를 하면서 단순하게 찾아낸 행렬의 형태를 Row-Echelon Form이라고 합니다. 다음의 조건을 만족해야 합니다.
- 모든 성분이 0인 행은 맨 아래에 위치합니다. 그 외의 행들은 0이 아닌 값들을 적어도 하나 포함합니다.
- 0이 아닌 값들을 포함하는 열은 첫 행을 제외하고는 앞 부분에는 0부터 시작합니다.
각 행에서 0이 아닌 처음의 값들을 pivot이라고 부릅니다. 예를 들면
위의 row-echelon Form에서 pivot은 1행의 1, 2행의 1, 3행의 1이 됩니다. 이 pivot과 곱해지는 x값들도 있고 곱해지지 않는 x도 있겠죠? 위의 식에서는 pivot과 곱해지는 변수들은 x1, x3, x4가 되는데, 그러한 변수들을 basic variables, 그 외의 나머지 변수들을 free variable이라고 부릅니다.
이러한 row-echelon form을 활용하면 특수해를 좀 더 쉽게 찾을 수 있습니다. 위의 행렬에서 왼쪽에 정리된 행렬 중 pivot을 포함하고 있는 column을 잘 조합해서 오른쪽에 있는 값들을 만족하면 되는데요,
위의 조합에서 보면 일단 3번째 행이 1이 되어야 하므로 λ3의 값이 1이라는 것을 알 수 있습니다. 그러면 λ2=-1, λ1이 2라는 걸 찾을 수 있죠. 이 값들을 basic variable로 주고, 그리고 pivot이 포함되지 않은 free variable로 주면 [2,0,-1, 1, 0] 이라는 특수해를 쉽게 찾아낼 수 있습니다.
[정의] reduced row echelon form
한 걸음 더 나가서.. 우리가 구한 위 식에서 1행과 2행도 좀 더 정리할 수 있습니다. 아래의 조건
- row-echelon form 이면서
- 모든 pivot이 1이고
- pivot은 그 열에서 유일하게 0이 아닌 값일 때
을 만족하면 reduced row echelon form이라고 부릅니다.
예를 들면
위의 행렬의 왼쪽 부분은 row-echelon form은 맞지만 reduced row-echelon form은 아닙니다. 좀 더 정리를 해 줄 필요가 있죠. 아래처럼
이렇게 정리가 되면 reduced row echelon form이 됩니다.
마지막 단계에요. 위에서 먼저 특수해는 pivot을 포함한 열을 조합하는 방법을 통해 찾을 수 있었습니다. 이제 일반해를 찾기 위해 Ax=O의 해를 찾아야죠.
자.. reduced row echelon form으로 정리된 행렬을 통해 Ax=O의 해를 어떻게 찾는 법을 살펴보겠습니다.
따라서 Ax=O의 특수해 중 하나는 [-3, 1, 0, 0, 0] = -[3, -1, 0, 0, 0]이 됩니다. 그리고
나머지 열도 처리를 해주면 됩니다. [-3, 0, -9, 4, 1]=-[3, 0, 9, -4, -1]도 하나의 Ax=O의 특수해가 되죠.
따라서 Ax=O의 모든 해는
가 된다는 것을 확인할 수 있습니다.
The minus 1 Trick
연립방정식에서 row operation을 통해 reduced row echelon form을 만든 상태라고 해보죠.
위의 그림처럼 pivot에 1이 나타나도록 하고 그 row를 다른 row에 더하고 빼는 등의 과정을 마친 상태입니다. 따라서 pivot이 있는 열에서는 pivot을 제외하고는 0 밖에 없는 상황입니다.
예를 들어볼께요. 위에서 봤던 예시를 통해서 살펴보겠습니다. 차근차근 진행방향을 따라 살펴보세요.
이렇게 Ax=O의 해를 쉽게 찾을 수도 있습니다. 이걸 The minus 1 Trick이라고 합니다..
다음 글 : 미지수의 개수와 행의 개수가 같을 때, 역행렬을 통해 Ax=B의 해를구하는 Gaussian Elimination을 향해서 한 번 가보도록 하겠습니다.
