[선형대수] 2. Elimination(소거법)

1. Elimination(소거법)

 

선형 연립 방정식의 해를 쉽게 구하는 방법으로 소거법(Elimination)이 있다.

 

다음과 같이 세 개의 선형 방정식이 있고, 이를 행렬과 벡터로 나타냈다고 해보자.

 

 

 

해 x, y, z를 구하기 위한 소거법을 적용하면 다음과 같다.

 

 

최종 목적은, 원래의 행렬을 상삼각행렬(upper triangular matrix)로 만드는 것이다.

 

 

Step 1) 첫 번째 pivot(1) 아래 1열의 성분을 모두 0으로 만들기 위해,  1행을 3배 한 것을 2행에서 빼준다.

* 해당 행렬은 3행 1열의 성분이 처음부터 0이었기 때문에 해당 과정만으로 1열의 성분이 모두 0이 되지만, 만약 아니었다면 같은 방법으로 3행에서 1행에 적당한 수를 곱해서 빼주면 된다.

 

Step 2) 두 번째 pivot(2) 아래 2열의 성분을 모두 0으로 만들기 위해,  2행을 2배 한 것을 3행에서 빼준다.

 

 

-> 위 예시로 든 행렬은 pivot에 해당하는 성분이 모두 0이 아니었기 때문에, 'good matrix'라고 할 수 있다. 그러나, pivot에 해당하는 성분이 0이 될 경우, 행의 위치를 바꿔 진행해야 한다. 

 

-> 그리고 만약, 세 번째 pivot이 0이되면 행의 위치를 바꾸는 것으로도 해결이 되지 않아 해당 행렬은 역행렬이 존재하지 않는 행렬이 된다.

 

 

2. Back-Substitution

 

이제, 위의 소거법과정을 전체 연립 선형방정식에 적용해 보자. 그 과정은 다음과 같다.

 

 

위 그림과 같이, Ax = b의 식에서 A와 b를 합쳐 놓은 형태의 행렬을 'augment matrix'라고 한다.

 

해당 행렬에 소거법을 적용하면 아래에서 부터 해를 구할 수 있다.

 

 

 

3. Elimination Matrices

 

소거법의 과정은 행렬로 나타낼 수 있다. 이것을 먼저 이해하기 전, 행렬의 연산을 이해할 필요가 있다.

 

 

위의 연산은 행의 선형결합을 어떻게 나타내는지에 대한 예시이다. 이를 활용하면 행을 이용한 소거법의 과정을 행렬로 나타내는 방법을 이해할 수 있다.

 

 

 

 

 

Step 1)에서의 '1행을 3배 한 것을 2행에서 빼준다.'는,

 

1행과 3행은 그대로 유지 ---> 각각 [1 0 0], [0 0 1]이 곱해짐

2행은 1행을 3배 한 것을 빼 주어야 하므로 ---> [-3 1 0]이 곱해짐

 

으로 나타낼 수 있다.

 

 

또한, 각각의 elimination matrix은 목표로 하는 바에 따라 'E₂₁', 'E₃₂' 로 나타낸다.

 

위의 과정을 식으로 나타내면 E₃₂E₂₁A = u 인데, 이때 E₃₂E₂₁을 한꺼번에 연산해 E로 나타낼 수는 있지만 둘의 순서를 바꿀 수는 없다는 사실에 주의해야 한다. 즉, 행렬의 곱셈에서 결합법칙은 성립하지만, 교환법칙은 성립하지 않는다는 것을 알 수 있다.

 

 

4. Permutation

 

소거법에서 pivot에 해당하는 성분이 0이 될 경우, 행의 위치를 바꾸는 식(row exchange)으로 해결할 수 있다고 했는데 그것을 가능하게 해주는 행렬을 Permutation matrix라고 한다. 

 

 

 

 

주의해야 할 것은, 소거법에서는 행의 위치를 바꾸는 것이므로 위와 같이 Permutation matrix이 조작하고자 하는 행렬의 왼쪽에 곱해져야 한다는 것이다.

 

 

5. Inverse of Elimination Matrices

 

그렇다면, 소거법의 과정을 역으로 거쳐 행렬 u를 A로 되돌리려면 어떻게 해야 할까?

 

생각보다 간단하게 떠올릴 수 있다.

 

 

 

E가 2행에서 1행을 3배 한 것을 빼주는 것이었으므로, E^-1(E의 역행렬)은 그 반대로 2행에서 1행을 3배 한 것을 더해주면 된다.

 

 

 

---

 

공부한 영상 : MIT 18.06 Linear Algebra, Spring 2005 - 2. Elimination with Matrices

링크 : https://youtu.be/QVKj3LADCnA

소개 : Gilbert Strang 교수님의 MIT 선형대수학 강의(2005)

 

MIT 18.06 Linear Algebra, Spring 2005