[행렬대수학] 가우스 소거법(Gaussian Elimination)

Review

참고 포스팅 : 

2020/06/28 - [Statistics/Matrix Algebra] - [행렬대수학] 행렬대수학(Matrix Algebra) 기초 - 행렬(Matrix)

[행렬대수학] 행렬대수학(Matrix Algebra) 기초 - 행렬(Matrix)

---

안녕하십니까, 간토끼입니다.

 

지난 포스팅에서는 행렬대수학을 다루기 위해 행렬의 기초적인 개념에 대해서 다뤄보았습니다.

 

이번 포스팅에서는 앞에서 정의한 Linear System을 풀기 위한 해법 중 하나인 가우스 소거법(Gaussian Elimination)에 대해서 다뤄보겠습니다.

 

가우스 소거법(Gaussian Elimination)은 미지수가 n개인 연립일차방정식을 나타내는 행렬에 기본 행 연산(Elementary Row Operation)을 적용하여 행 사다리꼴 행렬(Row Echelon Form of Matrix)로 만들어 해를 구하는 방법을 말합니다.

 

생소한 용어가 나오네요. 하나씩 차근차근 정리해보죠.

 

 

먼저 이러한 선형방정식 문제를 생각해보죠.

저번 포스팅에서 다루었던 행렬 표기법을 사용하면 우측과 같이 Ax = b 형태로 선형시스템을 간단하게 표현할 수 있습니다.

 

이때 새로운 표기법을 사용할 예정입니다.

바로 선형시스템의 계수행렬 A와, 방정식의 상수항 벡터 b를 결합한 첨가행렬을 다음과 같이 정의합니다.

첨가행렬(Augmented Matrix)은 계수행렬에 상수항 벡터를 첨가했다는 의미에서 첨가행렬이라고 하며,

다른 말로는 덧붙인 행렬이라고도 합니다. 표기법은 [A|b]라고 하고요.

 

이때 방정식의 해를 얻기 위해서는 다음 행렬을 특별한 형태로 바꿔줘야 하는데요.

바로 행렬의 우측 상단이 사다리꼴 형태(사실 삼각형에 가깝습니다...)가 되도록 바꿔주는 것인데요.

사다리꼴 형태로 바꿔준 모습을 행 사다리꼴 행렬(Row Echelon Form of Matrix)라고 하고, 행렬을 조작해주는 연산을 기본 행 연산(Elementary Row Operation)이라고 합니다.

 

기본 행 연산은 세 가지로 구분할 수 있습니다.

1. 두 행을 교환한다 (행의 교환)

2. 하나의 행에 0이 아닌 상수 k를 곱한다. (행의 상수배)

3. 한 행을 다른 행에 상수 k를 곱하여 이 행에 더한 행으로 교체한다. (행의 교체)

 

물론 기본 행 연산 대신 열(column)에 연산을 적용하는 기본 열 연산도 있으며, 위에서 행 대신 열로만 교체해주면 됩니다.

 

그럼 기본 행 연산을 이용해서 위 첨가행렬을 행 사다리꼴 행렬의 형태로 바꿔보도록 하죠.

 

 

참고로 L1은 1행이라고 이해하시면 됩니다. (책마다 표기법이 달라서 위키피디아를 참고하였습니다.)

 

먼저 1행에 3/2를 곱하여 2행에 더해주고, 3행에 1행을 더해주어 2행과 3행을 조작해줍니다.

조작하면 우측 행렬과 같이 바뀌는 걸 알 수 있습니다.

 

이는 2행과 3행의 1열의 성분을 0으로 바꿔주기 위한 연산 과정이며, 쉽게 얘기해서 우리가 연립방정식 문제를 풀 때 특정 변수를 소거해줬던 것과 같은 과정이라고 이해하시면 됩니다.

 

 

이후 2행에 2롤 곱해주어, 분수 형태의 성분을 정수로 바꿔줍니다.

이후 바뀐 2행에 2를 곱해준 후, 3행에 빼주어 3행의 2열 성분을 0으로 만들어줍니다.

 

그러면 우측과 같이 깔끔한(?) 형태로 바뀌게 되는데요.

 

이러한 과정을 우리는 가우스 소거법이라고 합니다.

 

그렇다면 가우스 소거법을 이용해 깔끔한 형태의 행렬로 바꿔준 후 어떻게 해를 구하는지 봅시다.

바로 첨가행렬을 다음과 같이 연립방정식 형태로 변환해준 후, 후진대입법을 이용해 해를 구해주면 됩니다.

후진대입법은 말 그대로 밑에서 위로 올라가는 연산 과정을 통해 값을 대입해주며 해를 구하는 과정인데요.

 

이러한 과정을 거쳐 최종적으로 x1 = 2, x2 = 3, x3 = -1 이라는 해를 얻었습니다.

 

728x90

 

여기서 용어를 다시 한번 정리하고 넘어가겠습니다.

위 첨가행렬의 계수행렬 부분만을 보시면 (삼각형 같지만) 우측 상단이 사다리꼴 형태로 정리된 것을 알 수 있으며,

좌측 하단은 성분이 0으로 변환된 것을 알 수 있습니다.

 

이를 행 사다리꼴 행렬이라고 정의하며, 이러한 형태로 정의해야 쉽게 해를 구할 수 있습니다.

 

또한 각 행에서 0이 아닌 첫 번째 성분을 pivot이라고 합니다.

이 pivot은 linear system에서 해가 있는지 알려주는 매우 중요한 역할을 합니다.

 

즉, 위 문제에서는 첫 번째 행의 pivot이 2이고, 그 다음은 1, 마지막 행은 -1임을 알 수 있는데요.

당장은 해의 존재를 알 수 있는 역할을 하지만, 사실 더 큰 의미가 숨겨져 있습니다.

이는 다음에 다뤄보도록 하죠.

 

다음 포스팅에서는 좀 더 업그레이드 된 형태인 가우스-조던 소거법에 대해서 다뤄보도록 하겠습니다.

 

감사합니다.

잘 읽으셨다면 게시글 하단에 ♡(좋아요) 눌러주시면 감사하겠습니다 :)

(구독이면 더욱 좋습니다 ^_^)

 

 

 

---

- 간토끼(DataLabbit)

- University of Seoul

- Economics, Big Data Analytics