[bskyvision의 선형대수학, 제5강] 소거법 (elimination)

지난 강의

[bskyvision의 선형대수학, 제0강] 동기부여: 선형대수학 F 받았던 학생이 선형대수학을 이용해서 SCI 논문을 쓰다

[bskyvision의 선형대수학, 제1강] 벡터와 선형결합  

[bskyvision의 선형대수학, 제2강] 점곱과 길이  

[bskyvision의 선형대수학, 제3강] 행렬    

[bskyvision의 선형대수학, 제4강] row picture와 column picture  

 

 

오늘은 선형 방정식들을 푸는 방법 중 하나인 소거법(elimination)에 대해서 배우려고 합니다. 소거법은 이미 우리가 다 알고 있는 방법입니다. 그러나 이와 관련해서 삼각시스템(triangular system), 피벗(pivot), 전진소거(forward elimination), 후진대입(back substitution) 등의 새로운 용어들을 배우게 될 것입니다. 먼저 간단히 스포를 하고 간다면, 삼각시스템은 선형대수학에서 중요한 의미를 갖습니다. 0이 아닌 완전한 세트의 피벗을 갖는 삼각시스템의 경우 유일한 해를 갖기 때문입니다. "이게 무슨 멍멍이소리야?"하시는 분들 분명 있을 것입니다. 그렇다면 잘 찾아오셨습니다. 이 글은 이게 뭔 소리인지 알아들을 수 없는 분들을 위한 것입니다. 하지만 이 글을 끝까지 읽고 나시면 "아는 자"가 되실 겁니다. 

 

 

소거법

2개의 미지수를 갖고 있는 2개의 선형방정식이 있습니다.

 

 

이 경우에는 일반적으로 하나의 해를 갖습니다. 그리고 가끔 해가 없거나, 무수히 많은 해를 갖습니다. 이처럼 세 가지의 경우의 수를 갖습니다. 일단 이 선형시스템은 하나의 해를 갖는다는 점 미리 알려드리고 시작하겠습니다. 

 

우리가 아는 방식대로 연립해서 하나의 미지수를 소거해보겠습니다. 두번째 방정식의 x를 없애보겠습니다. 그러기 위해서는 첫번째 방정식에 2를 곱한 것을 두번째 방정식에서 빼줘야 합니다. 참고로 소거를 위해 방정식에 곱하는 숫자를 선형대수학에서는 multiplier라고 합니다. 

 

 

결과적으로 y=-3이고 이것을 첫번째 방정식에 대입하면 x=-4이라는 것도 알게 됩니다. 즉, 해 (x, y) = (-4, -3)입니다.

 

여기서 주목할 만한 것은 소거 후에 상삼각(upper triangular) 형태가 되었다는 점입니다. 

 

 

소거법을 통해서 상삼각 형태를 도출해낼 수 있다면, 이 시스템은 단 하나의 해를 갖습니다. 따라서, 소거법의 목적은 선형시스템을 상삼각 형태로 변환해주는 것입니다. 상삼각 형태로 변환해준 이후에는 피벗(pivot)이라는 것이 드러납니다.

 

 

이 선형시스템의 첫번째 피벗은 1이고, 두번째 피벗도 1입니다. 피벗은 각 행에서 첫번째로 만나게 되는 0이 아닌 계수를 의미합니다. 

 

여기서 잠깐 집고 넘어가야 할 것이 있습니다. 지난 시간에 row picture와 column picture에 대해 배웠었죠? 소거 전과 후의 상황을 row picture로 그려보는 것은 왜 소거를 해도 괜찮은 것인지에 대한 물리적인 답을 줍니다. 

 

 

 

보다시피, 소거 전이나 소거 후나 두 선의 접점의 위치가 같습니다. 접점의 위치가 바로 해를 나타내는 것이니 소거를 해도 해는 바뀌지 않았다는 뜻이죠. 따라서, 우리가 마음껏 연립해서 소거해도 괜찮았던 것입니다. 

 

소거법이 막히는 경우1 (해가 없다)

그런데 소거법이 막히는 경우들이 있습니다. 영구적으로 막히는 경우가 있고, 일시적으로 막히는 경우가 있습니다. 영구적으로 막히는 경우에는 해가 없는 경우와 해가 무수히 많은 경우, 총 2가지 경우가 있습니다. 다음과 같은 선형시스템을 살펴보겠습니다. 

 

 

첫번째 방정식에 multiplier 3을 곱한 것을 두번째 방정식에서 빼줘 보겠습니다.

 

x만 소거가 되지 않고 y도 같이 소거가 되어 버립니다. 소거법이 여기서 탁 막혀버렸습니다(breakdown). 두번째 피벗이 없습니다. 그리고 0 = 5 라는 말이 안 되는 결과가 나왔습니다. 이런 경우에는 해가 없습니다.  

 

소거법이 막히는 경우2 (해가 무수히 많다)

 

 

이 선형시스템은 어떤지 한번 소거법을 이용해 보겠습니다. 마찬가지로 첫번째 방정식에 3을 곱한 것을 두번째 방정식에서 빼줍니다.

 

 

이 경우에도 x와 y가 동시에 소거되었습니다. 따라서 두번째 피벗이 없습니다. 하지만 말은 되는 결과(0=0)가 도출되었습니다. 0은 0이 맞죠. ㅋㅋ

 

따라서, 이 경우에는 첫번째 방정식인 x - 2y =1 을 만족시키는 모든 (x, y)가 해가 됩니다. (3, 1)도 되고요. (1, 0)도 됩니다. (2, 0.5)도 되죠. 셀 수 없이 많습니다. 

 

소거법이 막히는 경우3 (row exchange 이후 정상 작동)

소거법이 막혔다고 해서 무조건 해가 없거나, 해가 무수히 많은 것은 아닙니다. 소거법이 영구적으로(permanently) 막힌 것이 아니라, 일시적으로(temporarily) 막힌 경우도 있습니다.

 

이 선형시스템의 경우 첫번째 방정식에서 x의 계수가 0입니다. 이 상황에서는 첫번째 방정식에 어떤 multiplier를 곱한 다음에 두번째 방정식에서 빼주는 방식으로 두번째 방정식의 x를 소거시킬 수가 없습니다. 소거법이 막힌 것이죠. 그러나 두 행의 위치를 교환해준다면, 문제없이 작동합니다. 행의 위치를 서로 바꿔주는 것을 row exchange라고 합니다. 

 

 

row exchange를 해줬더니, 상삼각 형태가 되었습니다. 첫번째 피벗은 3이고, 두번째 피벗은 2입니다. 위에서 살펴봤듯이 해가 없는 경우와 해가 무수히 많은 경우에는 첫번째 피벗만 존재했었습니다. 그런데 지금은 두 개의 피벗이 모두 존재합니다. 이런 경우에는 단 하나의 해가 존재합니다. 풀어보면, y = 2, x = 3이 이 선형방정식의 해임을 알 수 있습니다. 

 

3개의 미지수, 3개의 방정식

이제 더 나아가서 3개의 미지수, 3개의 방정식의 경우를 생각해봅시다. 미리 말씀드리면 이 선형시스템은 단 하나의 해를 갖습니다. 따라서 소거법을 통해 우리는 상삼각 형태를 얻을 수 있을 것을 기대할 수 있습니다. 

 

 

먼저 두번째 방정식에 있는 x를 소거하겠습니다. 그러기 위해선, 첫번째 방정식에 multiplier 2를 곱한 것을 두번째 방정식에서 빼주면 됩니다. 위에 위치한 방정식에 multiplier를 곱해준 것을 아래에 위치한 방정식에서 빼주는 방식을 취하는 이유는 나중에 이것을 알고리즘화하고 행렬 연산으로 만들기 위함입니다. 우리가 느끼기엔 어색하더라도 동일한 방식으로 작동하도록 해줘야 컴퓨터가 이해할 수 있는 알고리즘이 됩니다. 

 

 

이번에는 세번째 방정식에 있는 x를 소거하겠습니다. 첫번째 방정식에 multiplier -1을 곱한 것을 세번째 방정식에서 빼주면 됩니다. 

 

 

이번에는 new 세번째 방정식에 있는 y를 소거시키겠습니다. 이것만 소거되면 상삼각 형태가 만들어집니다. new 두번째 방정식에 1을 곱한 것을 new 세번째 방정식에서 빼주면 되겠죠?  

 

상삼각 형태가 만들어졌고, 첫번째 피벗은 2, 두번째 피벗은 1, 세번째 피벗은 4라는 것을 알게 되었습니다. 지금까지의 과정을 전진소거(forward elimination)라고 부릅니다. 위에서 아래로 순차적으로 소거해왔기 때문입니다. 그리고 처음 선형시스템을 Ax = b라고 표현한다면, 전진소거 이후 상삼각형태는 Ux = c라고 표현할 수 있습니다. 여기서 U는 upper triangular에서 따온 것입니다. 

 

 

따라서 전진소거의 목적은 Ax = b를 Ux = c로 바꿔주는 것이라고 말할 수도 있겠습니다. 

 

이제 아래부터 시작해서 위로 하나씩 대입하면 이 선형시스템의 해를 구할 수 있습니다. 이 과정을 후진대입(back substitution)이라고 부릅니다. 즉, 소거법은 전진소거와 후진대입으로 이루어집니다.

 

소거법 = 전진소거 + 후진대입

이제 후진대입을 시작하겠습니다. 일단 z = 2라는 것을 금방 알 수 있고요, 그것을 new 두번째 방정식에 대입하면 y = 2라는 것도 알 수 있습니다. z = 2, y = 2를 첫번째 방정식에 대입하면 x = -1이라는 것도 알 수 있습니다. 따라서, 이 선형시스템의 해는 (x, y, z) = (-1, 2, 2)입니다. 

 

 

이 소거법은 3개의 미지수를 가진 3개의 방정식을 넘어 100개의 미지수를 가진 100개의 방정식에도 적용될 수 있습니다. 손으로 풀면 시간은 오래 걸리겠지만, 상삼각 형태만 만들 수 있다면 해를 구할 수 있습니다. 고등학교 때 배운 대로 되는 대로 연립해서 풀어 나간다면 절대 못 풉니다. ㅋㅋ 하지만 위에서 아래로 전진소거의 방식으로 하나씩 차근차근 푼다면 풀 수 있습니다. 

 

제5강 끝

끝까지 읽으시느라 고생하셨습니다. 제가 서두에 말씀 드린대로 이제 "아는 자"가 되셨나요? 천천히 정독했는데, 아는 자가 못 되셨다면, 그것은 설명을 잘못한 제 탓이니 너무 자책하지 마세요. 대신 포기하지 마시고 다시 한번 읽어보세요. 그리고 이해가 안 되는 부분에 대해 댓글로 질문을 남겨주세요. 또한 가지고 계신 선형대수학 책이 있다면 관련 챕터의 연습문제들 꼭 풀어보세요. 다양한 연습문제들을 풀면서 생각을 확장해나가는 것만큼 좋은 공부법도 없습니다. 그럼 6강에서 다시 찾아뵙겠습니다. 선형대수학 강의를 한 주에 하나씩 포스팅하는 게 쉽지만은 않네요. 이 글이 도움이 되셨다면, 공감과 댓글로 저 좀 격려해주세요. ㅋㅋ 

 

(이 글의 내용 및 그림들을 무단으로 가져가지 말아주세요.)