선형대수 3강. 연립방정식과 가우스 소거법
가우스 소거법은 가우스보다 1800년쯤 먼저 중국에서 완성되어 있었습니다.
풀고 시작
가우스보다 먼저, 구장산술
여러 미지수가 얽힌 방정식 여러 개를 동시에 만족시키는 문제, 즉 연립일차방정식은 인류가 가장 오래 풀어 온 수학 문제 중 하나입니다. 그런데 놀라운 사실이 있습니다. 그 표준 풀이법이 이미 고대 중국에 있었다는 것이죠. 한나라 시기에 집대성된 수학서 『구장산술』(九章算術)의 제8장 "방정"(方程)은 벼 묶음의 수확량 문제 같은 실무 문제를 다루는데, 계수를 산가지로 격자에 배열하고 한 열의 배수를 다른 열에서 빼서 미지수를 차례로 지워 나갑니다. 오늘날 첨가행렬에 대한 소거법과 본질적으로 같은 절차이며, 3세기의 수학자 유휘(劉徽)가 상세한 주석을 달았습니다. 서양에서 이 방법이 가우스(Carl Friedrich Gauss)의 이름을 얻은 것은 그가 19세기 초 소행성 궤도와 측지 계산의 최소제곱 문제를 풀며 이 절차를 체계적으로 썼기 때문입니다. 이름은 후대의 관행일 뿐, 방법 자체는 훨씬 오래됐죠.
소거법의 원리, 해를 바꾸지 않는 세 가지 손질
소거법의 핵심은 방정식들을 해가 변하지 않는 방식으로만 고쳐 쓰는 것입니다. 허용되는 손질은 세 가지입니다. 두 방정식의 순서를 바꾸는 것, 한 방정식 전체에 0이 아닌 수를 곱하는 것, 한 방정식의 배수를 다른 방정식에 더하는 것이죠. 각각이 해집합을 보존한다는 것은 쉽게 확인됩니다. 이 세 손질만 반복해 계단 모양(위 방정식일수록 미지수가 많고 아래로 갈수록 적은 형태)을 만들면, 맨 아래에서 미지수 하나가 바로 읽히고 위로 거슬러 오르며 나머지가 차례로 풀립니다. 이를 전진 소거와 후진 대입이라 부릅니다.
이 절차의 미덕은 기계성입니다. 통찰이나 요령 없이, 유한한 단계 안에 반드시 끝나는 알고리즘이죠. n개의 미지수에 대해 대략 n³에 비례하는 횟수의 연산이면 충분하다는 것도 계산됩니다. 풀이가 알고리즘이 되는 순간, 사람의 문제가 기계의 문제가 됩니다.
해가 하나, 무한, 없음인 세 경우
연립일차방정식의 해는 정확히 세 가지 경우만 가능합니다. 유일해, 무한히 많은 해, 해 없음이죠. 해가 정확히 두 개인 경우는 없습니다. 왜일까요. 두 해가 있으면 그 사이를 잇는 직선 위의 점이 모두 해가 되기 때문입니다.
기하로 보면 명료합니다. 미지수 2개짜리 방정식 하나는 평면의 직선입니다. 두 직선이 한 점에서 만나면 유일해, 겹치면 무한해, 평행하면 해가 없죠. 미지수 3개면 각 방정식은 공간의 평면이고, 세 평면이 한 점에서 만나거나, 한 직선을 공유하거나, 공통점이 없는 경우들로 나뉩니다. 소거법을 돌리면 이 구분이 저절로 드러납니다. 0 = 0 꼴의 빈 방정식이 나오면 자유변수가 생겨 무한해이고, 0 = 1 꼴의 모순이 나오면 해가 없습니다. 2강의 언어로 말하면, 계수행렬의 행렬식이 0이 아닐 때가 유일해의 경우입니다. 공간이 짜부라지지 않아 모든 결과가 정확히 하나의 원인 벡터를 갖는 상황이죠.
현대 계산의 뼈대
연립일차방정식이 왜 그렇게 중요할까요. 세계의 수많은 문제가 결국 이 형태로 환원되기 때문입니다. 공학에서는 다리와 건물의 골조에 걸리는 힘, 회로의 전류(키르히호프 법칙)가 연립방정식입니다. 경제학에서는 레온티예프(Wassily Leontief)의 산업연관분석이 국가 경제 전체를 거대한 연립방정식으로 모형화했고, 그는 이 작업으로 1973년 노벨 경제학상을 받았죠. 컴퓨터 그래픽스와 기계학습에서도 최소제곱 적합, 물리 시뮬레이션의 각 단계가 대규모 연립방정식 풀이입니다. 비선형 문제조차 미분으로 국소 선형화하여 연립일차방정식의 반복으로 풉니다. 슈퍼컴퓨터 순위를 매기는 LINPACK 벤치마크가 다름 아닌 거대 연립방정식 풀이 속도 측정이라는 사실이 이 위상을 상징합니다. 다음 강에서는 행렬 자체의 본성을 드러내는 고유값과 고유벡터로 나아갑니다.
인출 문제
생각해볼 질문 (정답 없음)
- 미지수가 100만 개인 연립방정식을 소거법으로 풀면 연산량이 감당하기 어렵게 커집니다. 근사해라도 빨리 얻는 편이 나은 상황은 언제이고, 그때 "푼다"의 의미는 무엇으로 바뀔까요.
이전: 2강 행렬과 선형변환 · 다음: 4강 고유값과 고유벡터