선형대수(Linear algebra)

가우스 소거법(Gaussian elimination)

한 식의 몇 배를 다른 식에서 빼 미지수를 하나씩 없애는 방법. 행렬⁠(matrix)⁠을 계단 모양으로 만든 뒤 아래에서부터 거꾸로 대입해 푼다.

\left[\begin{array}{ccc|c} a_{11} & a_{12} & a_{13} & b_1 \\ a_{21} & a_{22} & a_{23} & b_2 \\ a_{31} & a_{32} & a_{33} & b_3 \end{array}\right] \;\to\; \left[\begin{array}{ccc|c} p_1 & * & * & * \\ 0 & p_2 & * & * \\ 0 & 0 & p_3 & * \end{array}\right]

먼저 보면 좋은 개념연립일차방정식과 역행렬 행렬

연립일차방정식⁠(system of linear equations)⁠을 푸는 가장 기본적인 방법입니다. 식에서 계수만 떼어 행렬 모양의 표(첨가행렬⁠, augmented matrix⁠)로 적고, 세 가지 행 연산만 씁니다. 한 행의 몇 배를 다른 행에서 빼기, 두 행 바꾸기, 한 행에 0이 아닌 수 곱하기. 어느 연산이든 되돌릴 수 있으니 해는 바뀌지 않습니다. 을 한 단계씩 풀어 봅시다.

세 식은 공간의 세 평면입니다(파랑·분홍·초록이 첫째·둘째·셋째 식). 행 연산⁠(row operation)⁠을 하면 평면이 바뀌지만, 세 평면이 만나는 노란 점, 곧 해는 움직이지 않습니다. 끌어서 돌려 볼 수 있습니다.

앞 단계에서는 첫째 열의 피벗(소거의 기준으로 삼는, 그 행 맨 앞의 0이 아닌 수. 여기 보기들에서는 대각선 자리에 옵니다) 아래를 0으로 만들고, 이어 둘째 열의 피벗⁠(pivot)⁠ 아래를 0으로 만듭니다. 그러면 표가 계단 모양(행 사다리꼴⁠, row echelon form⁠)이 되고, 마지막 식에는 미지수가 하나만 남습니다. 그림에서 초록 평면이 $z$ = 상수인 수평면이 되는 순간입니다. 그다음에는 아래에서 위로 올라가며 구한 값을 대입합니다(뒤로 대입⁠, back substitution⁠). 이것까지 표 위에서 끝까지 하면 세 평면은 $x$ = 상수, $y$ = 상수, $z$ = 상수인 평면이 되어 해에서 직각으로 만납니다(가우스–조르당 소거법⁠, Gauss–Jordan elimination⁠).

피벗에서 행렬식⁠(determinant)⁠이 나옵니다. 한 행의 몇 배를 다른 행에 더하는 것은 부피를 바꾸지 않는 밀기이고, 두 행을 바꾸면 부호만 바뀝니다. 소거가 끝난 계단 모양은 대각선 아래가 모두 0이라 행렬식이 대각선의 곱입니다. 그래서 행렬식은 피벗들의 곱입니다(행을 바꾼 횟수만큼 부호를 뒤집고, 피벗이 모자라면 0입니다). 지금 . '행렬식이 0인 식'을 골라 보세요. 셋째 식이 앞의 두 식의 합이라 소거하다 보면 $0 = 0$ 이 되고, 피벗이 둘뿐이며, 해는 한 점이 아니라 노란 직선 전체입니다.

행 연산 하나하나는 간단한 행렬을 왼쪽에 곱하는 일, 곧 행렬의 곱⁠(matrix multiplication)⁠이기도 합니다. 정사각행렬⁠(square matrix)⁠ 오른쪽에 단위행렬(대각선이 1이고 나머지가 0인 행렬)을 붙이고 같은 연산을 끝까지 하면, 그 자리에 역행렬(곱하면 단위행렬⁠(identity matrix)⁠이 되는 행렬)이 나옵니다. 피벗이 모자라면 거기서 멈추고, 역행렬⁠(inverse matrix)⁠이 없다는 것이 드러납니다.

미지수가 $n$ 개면 소거에 드는 곱셈은 대략 $n^3/3$ 번, 상수배를 무시하고 적으면 $O(n^3)$ 입니다(점근 표기법⁠, asymptotic notation⁠). 행렬식을 정의대로 전개할 때의 $n!$ 개 항과는 비교가 안 되게 적어서, 컴퓨터가 연립방정식을 풀 때도 기본은 이 방법입니다. 이름은 19세기 초 가우스가 소행성 궤도⁠(orbit)⁠를 구하는 최소제곱⁠(least squares)⁠ 계산에서 이 절차를 체계적으로 쓴 데서 왔습니다. 하지만 기원전후 무렵 한나라 때 엮인 중국의 수학책 『구장산술』의 '방정' 장은 이미 같은 방식으로 연립방정식을 풀었습니다. 셈에 쓰는 작은 막대인 산가지⁠(counting rods)⁠를 셈판 위에 늘어놓아 계수를 적고, 식 하나를 세로 한 줄로 두어 줄끼리 빼 나갔습니다(둘째 보기가 그 첫 문제입니다).

이어지는 곳. 관측이 미지수보다 많은 최소제곱 회귀⁠(least-squares regression)⁠에서는 식을 모두 만족하는 해가 대개 없으니, 오차의 제곱합이 가장 작은 해를 찾는 정규방정식⁠(normal equations)⁠ $A^{\top}A\hat x = A^{\top}\vec b$ 를 세운 뒤 소거법⁠(elimination)⁠으로 풉니다. 소거 뒤 남은 피벗의 개수가 행렬의 계수(rank), 곧 열들이 실제로 펼치는 공간인 열공간⁠(column space)⁠의 차원입니다. 고유값⁠(eigenvalue)⁠ $\lambda$ 는 $A - \lambda I$ 를 소거했을 때 피벗이 모자라게 되는 값입니다. 0이 아닌 수로 언제나 나눌 수 있는 수 체계(체)라면 어디서든 쓸 수 있어서, 소수⁠(prime number)⁠ $p$ 로 나눈 나머지⁠(remainder)⁠의 세계(모듈러 연산⁠(modular arithmetic)⁠)에서도 그대로 통합니다. 마르코프 연쇄⁠(Markov chain)⁠의 정상 분포⁠(stationary distribution)⁠, 곧 한 걸음 더 가도 각 상태에 있을 확률⁠(probability)⁠이 바뀌지 않는 분포도 연립방정식을 소거해 구합니다. 행 연산은 행을 벡터⁠(vector)⁠로 보고 더하고 늘이는 일이니, 소거법은 선형변환⁠(linear transformation)⁠을 한 단계씩 풀어 되돌리는 일이기도 합니다.

관련된 시대와 장소조선의 산학

이 개념이 나오는 큰 생각선형화: 휘어진 것을 곧게 보기

이 개념이 나오는 긴 글

최소제곱과 선형대수 잃어버린 소행성 1801년, 발견 몇 주 만에 태양 뒤로 사라진 세레스. 스물네 살의 가우스는 흩어진 관측값에서 궤도를 되찾았다. 매칭과 흐름 짝을 찾는 알고리즘 의대 졸업생과 병원, 신장 기증자와 환자, 철도와 화물. 누구를 누구와 이을지 정하는 수학은 냉전의 철도 지도에서 노벨 경제학상까지 이어진다. 신경망과 기계 학습 배우는 기계 예를 보여 주면 규칙을 스스로 찾는 기계. 1958년의 퍼셉트론에서 오늘의 심층 신경망까지, 그 밑바닥에는 미분과 연쇄법칙이 있다. 역문제 거꾸로 푸는 문제는 왜 어려운가 원인에서 결과를 계산하기는 쉽다. 흐린 사진, CT, 블랙홀 사진은 왜 결과에서 원인을 되찾기 어려웠을까? 작은 특잇값이 잡음을 키우는 벽과, 정규화·릿지 회귀·베이즈 사전확률이 사실은 같은 처방이라는 이야기. 반환과 동적 계획법 같은 계산, 다른 덧셈 가장 짧은 길, 길의 가짓수, 가장 그럴듯한 해석, 갈 수 있는지 없는지. 따로 태어난 알고리즘들이 사실은 한 계산이고, 달라지는 것은 더하기와 곱하기 자리에 무엇을 넣느냐뿐이다. 그렇게 바꿔 넣어도 되는 까닭은 분배법칙 하나다.

이 개념을 언급하는 페이지

행렬
… b를 알고 Av = b가 되는 v를 찾는 문제가 연립일차방정식입니다. 그 연립방정식을 푸는 표준 방법이가우스 소거법입니다. 한 행에 수를 곱해 다른 행에서 빼는 조작을 되풀이해 미지수를 하나씩 없애 나갑니다.
행렬식
… 정의대로 계산하지 않습니다. 정의대로라면 n×n 행렬에서 n!개의 항을 더해야 하기 때문입니다. 대신가우스 소거법으로 대각선 아래가 모두 0인 삼각형 모양을 만듭니다. 한 행의 배수를 다른 행에서 빼는 조작은 행렬식을 …
연립일차방정식과 역행렬
… 일과 같습니다. 식이 셋 이상이면 한 식에 수를 곱해 다른 식에서 빼는 조작으로 변수를 하나씩 지워 나가는가우스 소거법이 표준입니다. 등식 대신 부등식이 들어가면 또 다른 분야가 열립니다. 1781년 프랑스 수학자 ⟦가스파르 …
열공간
… 열공간은 직선으로 쪼그라듭니다. 열공간의 차원을 행렬의 계수 (rank)라 하고, 지금은 입니다. 계수는가우스 소거법을 마친 뒤 남는 피벗의 개수와 같습니다. 정사각행렬은 열공간이 공간 전체일 때, 곧 행렬식이 0이 …
홀의 정리
… 골라 곱한 값을 모든 고르는 방법에 대해 더합니다. 부호 하나만 다른데 난이도는 딴판입니다. 행렬식은가우스 소거법으로 빠르게 계산되지만, 퍼머넌트를 빠르게 계산하는 방법이 있다면 P 대 NP 문제가 P = NP로 …
반환
… 수렴하면(A의 고윳값의 절댓값이 모두 1보다 작으면) A^* = (I - A)^{-1} 이고, 이 반복은가우스 소거법으로 그 역행렬을 구하는 계산과 같습니다. (min, +)에서는 음수 고리가 없을 때 최단 경로의 …
역문제와 잘 놓인 문제
… 수 있습니다. 조건수만큼의 불어남은 문제 자체의 성질이라 어떤 풀이법도 피할 수 없습니다. 연립방정식을소거법으로 풀 때 피벗을 고르는 까닭은, 계산 과정이 반올림 오차를 그보다 더 키우지 않게 하려는 것입니다. …

이 페이지가 가리키는 개념

행렬식 행렬의 곱 점근 표기법 카를 프리드리히 가우스 최소제곱 회귀 열공간 고유벡터와 고유값 소수와 에라토스테네스의 체 모듈러 연산 마르코프 연쇄 벡터 선형변환