세 조건을 모두 만족하는 값을 찾는다고 하자. 조건의 순서를 바꾸어 읽어도 답은 변하지 않는다. 한 조건을 다른 조건과 조합해 더 간단하게 만들되, 원래 조건을 복원할 수 있어야 한다.
연립방정식의 식 하나를 행렬의 한 행으로 옮기면, 식을 조합하는 과정이 숫자의 행을 바꾸는 과정이 된다. 연립일차방정식에서 쓴 가감법을 미지수가 셋인 경우에도 일정한 순서로 적용해 보자. 계수와 미지수는 모두 실수로 다룬다. 이 순서는 컴퓨터가 큰 연립방정식을 풀 때 쓰는 기본 절차이기도 하다.
가우스 소거법은 기본행연산으로 미지수를 차례로 없애는 방법이다
가우스 소거법은 해집합을 보존하는 행연산으로 연립일차방정식을 계단 모양으로 정리한 뒤 푸는 방법이다. 미지수의 열 순서를 고정하고 상수항을 마지막 열에 붙인 것을 확대행렬이라 한다. 첨가행렬이라고도 부른다.
같은 연립방정식을 행렬의 곱으로 쓰면 식 (2)다. 계수행렬 A의 한 행과 미지수 열 X의 대응 성분을 곱해 더하면 식 (1)의 왼쪽이 하나씩 나온다. 첫 행이면 0⋅x+1⋅y+1⋅z다.
A012113114Xxyz=B5620.(2)
정의
기호
이름
원어
뜻
x,y,z
미지수
unknown
세 식에서 공통으로 찾는 실수
A
계수행렬
coefficient matrix
미지수의 계수만 열 순서대로 모은 행렬
X, B
미지수 열, 상수항 열
column
미지수와 상수항을 세로로 쓴 행렬
[A∣B]
확대행렬
augmented matrix
A 오른쪽에 B를 붙인 행렬, 첨가행렬
Ri
제 i행
row
위에서 i번째 식의 계수와 상수항 전체
k
행연산의 배수
scalar
행 전체에 곱하는 실수
피벗
소거의 기준 성분
pivot
소거 단계에서 기준으로 고른 0이 아닌 성분
식 (1)의 첫 열은 끝까지 x의 계수다. 첫 식에 x가 보이지 않아도 그 자리에 0을 남겨야 다른 열이 밀리지 않는다. 세로선은 계수와 상수항을 구별할 뿐 곱셈 기호가 아니다.
어떤 행연산이 해를 보존할까?
다음 세 연산을 기본행연산이라 한다. 마지막 상수항까지 행 전체에 적용한다.
연산
약속
되돌리는 방법
두 행 교환
Ri↔Rj
같은 두 행을 다시 교환
한 행의 0 아닌 상수배
Ri←kRi, k=0
1/k배
다른 행의 배를 더하기
Ri←Ri+kRj, i=j
바꾸지 않은 Rj의 k배를 다시 빼기
세 연산 모두 원래 식의 해를 새 식의 해로 그대로 남긴다. 역연산도 가능하므로 새 식을 만족하는 값은 원래 식도 만족한다. 이 양방향 설명 때문에 해 하나만 보존하는 것이 아니라 해집합 전체가 같다. 특히 셋째 연산에서 다른 행 Rj는 그대로 두어야 이 복원 설명이 성립한다.
미지수가 둘인 예로 확인하자. x−y=2, 2x+y=7의 해는 (3,1)이다. 둘째 행에서 첫째 행의 2배를 빼면 식 (3)이 된다.
[12−1127]R2←R2−2R1[10−1323].(3)
새 둘째 식은 3y=3, 즉 y=1이다. 원래 둘째 식과 다른 직선이지만 교점 (3,1)을 그대로 지난다. 둘째 식을 R2+kR1로 바꾸면 (2+k)x+(1−k)y=7+2k이고, (3,1)을 넣은 왼쪽도 7+2k다. 그림 1은 k=0,−1,−2일 때의 세 직선이 같은 교점을 지나는 모습이다.
그림 1x−y=2(R1)와, 둘째 식을 R2+kR1로 바꾼 직선. k=0은 원래 식 2x+y=7, k=−1은 x+2y=5, k=−2는 3y=3이며 세 직선 모두 교점 (3,1)을 지난다. figures/row_operation_lines.py
되돌릴 때는 R2←R2+2R1을 하면 2x+y=7이 돌아온다. 0배는 허용하지 않는다. 예를 들어 x=2를 0배하면 0=0이 되어 x=7까지 허용하므로 정보가 사라진다.
이처럼 피벗 아래를 0으로 만드는 과정을 전진소거라 한다. 0이 아닌 행의 첫 0 아닌 성분이 아래 행으로 갈수록 오른쪽에 있고, 모든 성분이 0인 행은 아래에 놓인 행렬이 행 사다리꼴이다. 피벗을 1로 만드는 것은 편리하지만 이 모양 자체에 꼭 필요한 조건은 아니다.
그림 2 식 (6)의 확대행렬에서 원으로 표시한 피벗은 아래로 갈수록 오른쪽에 있다. 색칠한 칸은 피벗 아래의 0이고, 마지막 열 6, 5, 3은 각 식의 상수항이다. figures/pivot_staircase.py
그림 2에서 피벗 아래가 모두 0인지 확인하자. 이제 아래 식부터 위로 대입하는 후진대입을 한다.
z=3,y=5−3=2,x=6−2−3=1.(7)
원식의 왼쪽은 차례로 2+3=5, 1+2+3=6, 2+6+12=20이므로 모두 맞는다. 모든 미지수가 차례로 결정되어 해는 (1,2,3) 하나다.
Q. 가우스 소거법에서 피벗 위의 성분도 0으로 만들어야 하나요?
아니다. 후진대입으로 풀 때는 피벗 아래만 0으로 만들어도 충분하다. 피벗을 1로 맞추고 위까지 0으로 만들면 식 (6)은 [100∣1;010∣2;001∣3]이 되어 해를 바로 읽는다. 이 방식이 가우스–조르당 소거법이며 역행렬 계산에서 쓴다.
Q. 가우스 소거법에서 행을 다른 순서로 소거하면 답이 달라지나요?
아니다. 허용된 기본행연산만 정확히 했다면 해집합은 같다. 다만 중간 행렬과 행 사다리꼴은 달라질 수 있다. 식 (6)에서 R1←R1−R2를 더 하면 첫 행이 (1,0,0∣1)인 다른 사다리꼴이 되지만 해는 여전히 (1,2,3)이다.
가우스 소거법은 왼쪽 열부터 한 열씩 처리한다
가우스 소거법은 왼쪽 열부터 한 열씩 같은 일을 되풀이한다. 열마다 피벗을 정하고 그 아래를 0으로 만든 뒤 다음 행·다음 열로 옮긴다. 식 (4)–(6)도 이 순서를 따랐다.
확대행렬을 쓴다. 빠진 미지수 자리에는 0을 쓴다.
현재 열에서 현재 행의 성분을 본다. 그것이 0이면 같은 열에 0이 아닌 성분이 있는 아래 행과 바꾼다.
피벗 아래의 각 행에서 피벗 행의 m배를 뺀다. 배수 m은 식 (8)로 정한다.
다음 행·다음 열로 옮겨 2와 3을 되풀이한다. 현재 행부터 아래가 모두 0인 열은 건너뛴다.
행 사다리꼴이 되면 후진대입하고, 원식에 대입해 검산한다.
m=피벗없앨성분,Ri←Ri−mR피벗행.(8)
식 (5)에서는 없앨 성분이 2, 피벗이 1이어서 m=2였다. 그림 3은 3×3 연립계에서 이 과정이 만드는 모양을 숫자 대신 ∗로 나타낸다. 열을 하나 처리할 때마다 0의 계단이 한 칸씩 내려간다.
그림 3 3×3 확대행렬의 전진소거 모양. 화살표의 1, 2, 3은 처리하는 열의 번호이고, 원은 0이 아닌 피벗, 색칠한 0은 소거된 성분, ∗는 아직 정해지지 않은 임의의 수다. 셋째 열에서는 아래에 남은 행이 없어 피벗만 정한다. figures/elimination_pattern.py
Q. 가우스 소거법에서 피벗 후보가 전부 0이면 어떻게 하나요?
그 열은 건너뛰고 오른쪽 다음 열에서 피벗을 찾는다. 예를 들어 계수행 (0,1,2)만 남았다면 피벗은 둘째 열의 1이다. 피벗이 없는 미지수가 생기면 해가 하나로 정해지지 않을 수 있으며, 그 판정은 연립일차방정식의 해집합에서 다룬다.
세 점을 지나는 포물선은 가우스 소거법으로 어떻게 찾을까?
포물선 y=ax2+bx+c가 세 점을 지날 조건은 a,b,c에 관한 연립일차방정식이다. 점 (−1,6), (1,2), (2,3)의 좌표를 대입하면 식 (9)를 얻는다. 이번에는 미지수가 a,b,c다.
식 (10)에서 둘째 피벗은 2이고 그 아래에서 없앨 성분은 6이다. 식 (8)의 배수는 m=6/2=3이다.
R3←R3−3R2100−12010−36−4−9.(11)
후진대입하면 −3c=−9에서 c=3, 2b=−4에서 b=−2, a−(−2)+3=6에서 a=1이다. 그림 4처럼 y=x2−2x+3은 세 점을 모두 지난다. 피벗 2와 −3을 1로 바꾸지 않고도 끝까지 풀었다.
그림 4y=x2−2x+3의 그래프와 이 포물선을 정한 세 점 (−1,6), (1,2), (2,3). 식 (11)의 행 사다리꼴을 후진대입해 얻은 계수 a=1, b=−2, c=3으로 그렸다. figures/parabola_three_points.py
핵심
가우스 소거법은 해집합을 보존하는 기본행연산으로 실수 연립일차방정식을 행 사다리꼴로 만든 뒤 후진대입하는 방법이다. 피벗은 0이 아니기만 하면 되고, 0이면 아래 행과 바꾼다.
Q. 가우스 소거법에서 피벗을 꼭 1로 만들어야 하나요?
아니다. 가우스 소거법의 피벗은 0이 아니기만 하면 된다. 식 (11)의 피벗 2와 −3도 그대로 두고 후진대입 단계에서 나누었다. 1로 만들면 배수 계산이 쉬워지지만 분수가 일찍 생길 수 있다.
가우스 소거법의 흔한 오해
계수만 소거하고 상수항은 그대로 둔다 — 식 (5)에서는 상수항도 20−2⋅6=8로 바뀐다. 오른쪽을 두면 다른 방정식이다.
R1←R1+R2, R2←R1+R2를 옛 두 행으로 동시에 계산해도 된다 — x−y=2, 2x+y=7에서 이렇게 하면 두 식이 모두 3x=9가 된다. 그림 5처럼 원래 해가 아닌 (3,0)까지 해가 된다. 한 연산이 바꾼 행을 다른 연산이 쓰면 차례대로 적용한다.
그림 5 옛 두 행으로 R1←R1+R2와 R2←R1+R2를 동시에 하면 두 식이 모두 3x=9가 된다. 원래 해는 교점 (3,1) 하나지만, 새 식은 직선 x=3 전체를 허용해 (3,0) 같은 점도 받아들인다. figures/bad_simultaneous_update.py
직접 해보기
연립방정식 2x−z=1, y+3z=4, x+y=3의 확대행렬을 써라. 또 확대행렬 [1−10∣3;021∣4;003∣6]이 나타내는 연립방정식을 후진대입으로 풀어라.
다음 중 행 사다리꼴인 것을 고르고, 아닌 것은 이유를 말하라. P=100200030, Q=010100231, S=200100105.
x+y+z=2, 2x+2y+3z=6, x+2y+z=1을 소거법으로 풀어라. 둘째 피벗 자리에 0이 생기면 어떻게 하는가?
세 점 (0,1), (1,0), (2,3)을 지나는 포물선 y=ax2+bx+c를 구하라. 첫 피벗 자리에 무엇이 오는지 주의하라.
해가 (2,1)인 x+y=3, x−y=1에 다음을 하면 해집합이 바뀌는가? 바뀌면 원래 해가 아닌 새 해를 하나 들어라. (가) R2←−R2 (나) R2←0R2 (다) 옛 두 행으로 R1←R1+R2, R2←R1+R2를 동시에.
답과 풀이
빠진 미지수 자리에 0을 두면 [20−1∣1;013∣4;110∣3]이다. 둘째 확대행렬은 x−y=3, 2y+z=4, 3z=6이다. z=2, 2y+2=4에서 y=1, x−1=3에서 x=4다.
P만 행 사다리꼴이며 피벗은 1열과 3열에 있다. Q는 둘째 행의 첫 0 아닌 성분(1열)이 첫째 행의 것(2열)보다 왼쪽에 있다. S는 0행이 0 아닌 행 위에 있다.
R2←R2−2R1, R3←R3−R1을 하면 [111∣2;001∣2;010∣−1]이다. 둘째 행 둘째 열이 0이므로 R2↔R3을 한다. 그러면 y=−1, z=2, x=2+1−2=1이다. 검산하면 1−1+2=2, 2−2+6=6, 1−2+2=1이다.
대입하면 c=1, a+b+c=0, 4a+2b+c=3이다. 확대행렬 [001∣1;111∣0;421∣3]은 첫 피벗 자리가 0이라 R1↔R2를 한다. R3←R3−4R1로 [0−2−3∣3]을 얻고, 둘째 열의 피벗을 위해 R2↔R3을 한다. c=1, −2b−3=3에서 b=−3, a=0−b−c=2이므로 y=2x2−3x+1이다.
(가) 바뀌지 않는다. −x+y=−1은 x−y=1과 같은 직선이다. (나) 바뀐다. 둘째 식이 0=0이 되어 x+y=3만 남으므로 (0,3)도 해가 된다. (다) 바뀐다. 두 식이 모두 2x=4가 되어 (2,0)도 해가 된다.
더 읽기
College Algebra 2e 7.6절 — OpenStax. 확대행렬과 행연산·후진대입을 확인했다. 본문은 피벗이 1일 필요가 없는 행 사다리꼴과 기약형을 구별한다.
Notes on Diffy Qs, A.3 Elimination — Jiří Lebl. 0 아닌 배수 조건과 자유변수·동차계를 대조했다. 이 원문은 사다리꼴의 선두 성분도 1로 정규화한다는 점에서 본문 관례와 다르다. 미분방정식을 선수로 쓰지 않는다.
Interactive Linear Algebra 1.2절 — Dan Margalit·Joseph Rabinoff. 본문처럼 사다리꼴에서는 선두 성분이 1일 것을 요구하지 않고, 기약 사다리꼴에서 1을 요구하는 정의를 확인했다. 기약 사다리꼴이 하나로 정해진다는 정리도 이 절에 있다.