수학

MATH / 초급 43번

가우스 소거: 미지수 셋을 요령이 아니라 절차로 푸는 법

미지수 둘짜리는 대입·가감으로 풀렸지만 셋을 넘으면 요령이 무너집니다. 첨가행렬 위에서 세 가지 행 연산으로 사다리꼴을 만들고 후진 대입으로 답을 내는 절차를 세우고, 마지막 행이 결정하는 해가 하나·무한·없음의 세 갈래를 손계산으로 확인합니다.

PALDYN Team41 MIN READ

미지수 둘짜리 연립은 요령으로 풀렸습니다. 대입해 넣거나 두 식을 빼서 미지수 하나를 없앴습니다.

{x+y=52x−y=1\begin{cases} x + y = 5 \\ 2x - y = 1 \end{cases}

두 식을 더하면 3x=63x = 6 이므로 x=2x = 2 이고, 첫 식에서 y=3y = 3 입니다. 이 해가 곧 24번 · 좌표평면과 직선에서 그린 두 직선의 교점입니다.

두 직선이 (2, 3)에서 만나는 그림

교점이 있으면 해가 하나, 두 직선이 나란하면 해가 없고, 같은 직선이면 해가 무한히 많습니다. 두 개짜리는 이렇게 눈으로도 됩니다. 손 소거의 세세한 손놀림은 16번 · 일차방정식과 이항에서 이미 다뤘습니다.

그런데 미지수가 셋을 넘으면 요령이 무너집니다. 무엇을 먼저 없앨지, 어떤 두 식을 조합할지가 매번 달라지고, 실수 한 번이면 앞에서 한 것을 다시 해야 합니다. 이번 글은 요령이 아니라 절차 하나를 세웁니다.

첨가행렬

지난 글 · 행렬이라는 표기에서 연립방정식을 Ax=bAx = b 한 줄로 적었습니다. 소거 작업은 사실 미지수의 이름을 잊고 계수와 우변만으로 돌아가므로, 계수행렬 AA 오른쪽에 우변 bb 를 세로 막대로 붙인 표를 씁니다. 이것을 첨가행렬이라 하고 [A∣b][A \mid b] 로 적습니다.

{x+y+z=62x+3y+z=14x+2y+3z=14⟶[A∣b]=[11162311412314]\begin{cases} x + y + z = 6 \\ 2x + 3y + z = 14 \\ x + 2y + 3z = 14 \end{cases} \quad\longrightarrow\quad [A \mid b] = \left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 2 & 3 & 1 & 14 \\ 1 & 2 & 3 & 14 \end{array}\right]

이제 미지수 이름을 다시 볼 일이 없습니다. 자리와 부호만 지키면 됩니다.

빠진 자리의 0

옮겨 적을 때 가장 자주 나는 실수는 눈에 안 보이는 미지수를 빠뜨리는 것입니다. 다음 연립을 봅니다.

{x+z=52y−z=1x+y+z=6\begin{cases} x + z = 5 \\ 2y - z = 1 \\ x + y + z = 6 \end{cases}

첫 식에는 yy 가 없고 둘째 식에는 xx 가 없습니다. 하지만 없는 것이 아니라 계수가 0인 것입니다. 첫 식은 1⋅x+0⋅y+1⋅z=51 \cdot x + 0 \cdot y + 1 \cdot z = 5 를 줄여 적은 것이니, 첨가행렬에는 그 0을 반드시 적어야 합니다.

[101502−111116]\left[\begin{array}{ccc|c} 1 & 0 & 1 & 5 \\ 0 & 2 & -1 & 1 \\ 1 & 1 & 1 & 6 \end{array}\right]

0을 적지 않고 수만 붙여 쓰면 −1-1 이 yy 자리에 들어와 전혀 다른 연립이 됩니다. 자리가 곧 미지수의 이름이라, 표에서는 비어 있는 칸이 허용되지 않습니다. 부호도 마찬가지입니다 — 2y−z2y - z 의 zz 계수는 11 이 아니라 −1-1 입니다.

행렬의 크기

첨가행렬의 크기를 읽으면 문제의 모양이 그대로 보입니다. 가로줄 하나가 방정식 하나이고, 막대 왼쪽의 세로줄 하나가 미지수 하나입니다. 방정식이 mm 개, 미지수가 nn 개이면 계수행렬은 m×nm \times n 이고 첨가행렬은 막대 오른쪽 한 줄이 더 붙어 m×(n+1)m \times (n+1) 입니다.

보이는 것 뜻하는 것
행의 개수 mm 방정식의 개수
막대 왼쪽 열의 개수 nn 미지수의 개수
세 번째 열 셋째 미지수 zz 의 계수들
막대 오른쪽 열 우변의 상수들

위 예는 3×33 \times 3 계수행렬에 우변이 붙은 3×43 \times 4 첨가행렬입니다. 방정식과 미지수의 개수가 같은 이 모양이 가장 흔하지만, 둘이 다를 수도 있습니다. 방정식이 미지수보다 많으면 세로로 길쭉하고, 적으면 가로로 납작합니다. 그 비율이 해의 갈래를 미리 귀띔해 주는데, 무엇을 귀띔하는지는 다섯째 절에서 셈으로 확인합니다.

여러 개의 우변

같은 계수행렬에 우변만 다른 문제를 여러 개 풀어야 하는 일이 자주 있습니다. 그때는 막대 오른쪽에 열을 여러 개 붙이면 됩니다.

[111632311451231410]\left[\begin{array}{ccc|cc} 1 & 1 & 1 & 6 & 3 \\ 2 & 3 & 1 & 14 & 5 \\ 1 & 2 & 3 & 14 & 10 \end{array}\right]

행 연산은 한 가로줄 전체에 걸쳐 하는 것이라, 오른쪽 열이 둘이든 열이든 같은 손놀림이 그대로 적용됩니다. 왼쪽이 사다리꼴이 될 때까지 소거하면 오른쪽 두 열이 각각 자기 문제의 우변으로 함께 따라옵니다. 소거는 한 번만 하고 답만 두 벌 얻는 셈입니다. 이 구조는 다음 글에서 한 번 더 쓰이니 기억해 둘 만합니다.

세 가지 행 연산

첨가행렬 위에서 할 수 있는 조작은 다음 셋뿐입니다.

세 가지 행 연산: 두 행 맞바꾸기, 한 행에 0이 아닌 수 곱하기, 한 행의 몇 배를 다른 행에 더하기

셋 다 해를 바꾸지 않습니다. 방정식의 순서만 바꾸는 것, 양변에 같은 수를 곱하는 것, 한 방정식으로 다른 방정식의 미지수 하나를 없애는 것은 우리가 원래 알던 조작 그대로입니다. 곱하는 수가 0이면 안 되는 이유는 정보가 사라지기 때문입니다 — 0=00 = 0 이 된 방정식은 아무것도 말하지 않으니 원래 있던 조건 하나를 잃습니다.

역연산과 해집합

"해를 바꾸지 않는다"는 말은 생각보다 강한 주장입니다. 원래 연립의 해가 새 연립의 해라는 것만으로는 부족하고, 새 연립의 해가 원래 연립의 해이기도 해야 두 연립이 같은 답을 갖습니다. 한쪽만 성립하면 새 연립에 없던 해가 끼어들었을 수 있습니다.

세 연산이 이 조건을 만족하는 이유는 셋 다 같은 종류의 연산으로 되돌려지기 때문입니다.

연산 되돌리는 연산
Ri↔RjR_i \leftrightarrow R_j 다시 Ri↔RjR_i \leftrightarrow R_j
Ri→kRiR_i \to k R_i (k≠0k \ne 0) Ri→1kRiR_i \to \tfrac{1}{k} R_i
Ri→Ri+kRjR_i \to R_i + k R_j Ri→Ri−kRjR_i \to R_i - k R_j

되돌리는 연산도 같은 목록 안에 있으므로, 새 연립의 해는 그 역연산을 타고 원래 연립의 해로 돌아옵니다. 양쪽으로 갈 수 있으니 두 연립의 해집합이 완전히 같습니다. 둘째 줄에서 k≠0k \ne 0 이 필요한 이유도 여기서 드러납니다 — k=0k = 0 이면 나눌 수가 없어 되돌아올 길이 없습니다.

열 맞바꾸기

행은 맞바꿔도 되는데 열은 함부로 맞바꾸면 안 됩니다. 행을 맞바꾸는 것은 방정식을 적는 순서를 바꾸는 것이라 아무것도 달라지지 않지만, 열을 맞바꾸는 것은 미지수의 순서를 바꾸는 것입니다.

[111601−120036]→ C1↔C3 [1116−11023006]\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -1 & 2 \\ 0 & 0 & 3 & 6 \end{array}\right] \quad \xrightarrow{\ C_1 \leftrightarrow C_3\ } \quad \left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ -1 & 1 & 0 & 2 \\ 3 & 0 & 0 & 6 \end{array}\right]

오른쪽 표를 아무 생각 없이 읽으면 첫 열이 xx 인 줄 알고 3x=63x = 6 에서 x=2x = 2 를 얻습니다. 그런데 실제로 첫 열은 zz 의 자리였으므로 그 값은 z=2z = 2 입니다. 답이 틀린 것이 아니라 답의 이름표가 섞인 것이고, 이름표가 섞이면 틀린 답과 구별할 방법이 없습니다. 열을 꼭 바꿔야 한다면 어느 열이 어느 미지수였는지를 따로 적어 두고 마지막에 되돌려야 합니다. 손으로 푸는 동안에는 아예 쓰지 않는 편이 안전합니다.

한 줄에 몰아 쓰기

R2→R2−2R1R_2 \to R_2 - 2R_1 과 R3→R3−R1R_3 \to R_3 - R_1 은 한 줄에 함께 적어도 됩니다. 둘 다 R1R_1 만 읽고 R1R_1 을 고치지 않기 때문입니다. 읽기만 하는 행과 고치는 행이 겹치지 않으면 순서가 상관없습니다.

문제는 이런 짝입니다.

R2→R2−2R1,R1→R1−R2R_2 \to R_2 - 2R_1, \qquad R_1 \to R_1 - R_2

둘째 연산의 R2R_2 가 방금 고친 R2R_2 인지 원래 R2R_2 인지가 정해지지 않았습니다. 어느 쪽으로 읽느냐에 따라 결과가 달라지므로 이런 짝은 반드시 두 줄로 나눠 차례로 합니다. 규칙 하나만 지키면 됩니다 — 한 줄에 몰아 쓸 연산들은 고치는 행이 서로 다르고, 그 행들이 읽는 행에 들어 있지 않아야 합니다.

가우스 소거와 사다리꼴

목표는 왼쪽 아래를 전부 0으로 만드는 것입니다.

사다리꼴 만들기

위 첨가행렬로 해 봅니다. 첫 열의 아래 두 자리를 0으로 만듭니다. 두 번째 행에서 첫 번째 행의 2배를 빼고, 세 번째 행에서 첫 번째 행을 뺍니다.

R2→R2−2R1,R3→R3−R1R_2 \to R_2 - 2R_1, \quad R_3 \to R_3 - R_1

[111601−120128]\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -1 & 2 \\ 0 & 1 & 2 & 8 \end{array}\right]

이제 두 번째 열의 세 번째 자리를 0으로 만듭니다.

R3→R3−R2R_3 \to R_3 - R_2

[111601−120036]\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -1 & 2 \\ 0 & 0 & 3 & 6 \end{array}\right]

왼쪽 아래가 전부 0인 이 모양을 행 사다리꼴이라고 합니다. 각 행에서 처음으로 0이 아닌 자리를 피벗이라 부릅니다. 위 결과에서는 각 행의 피벗이 1, 1, 3 입니다.

피벗 자리의 0

절차를 그대로 밟다 보면 피벗으로 쓰려던 자리에 0이 앉아 있는 일이 생깁니다.

[012311162107]\left[\begin{array}{ccc|c} 0 & 1 & 2 & 3 \\ 1 & 1 & 1 & 6 \\ 2 & 1 & 0 & 7 \end{array}\right]

첫 행 첫 자리가 0이라 이 행으로는 아래 행의 xx 를 없앨 수 없습니다. 0에 무엇을 곱해도 0이라 아래의 1과 2를 지울 수가 없기 때문입니다. 이때 쓰는 것이 첫 번째 행 연산입니다 — 그 열에서 0이 아닌 값을 가진 아래 행을 찾아 맞바꿉니다.

R1↔R2:[111601232107]R_1 \leftrightarrow R_2: \quad \left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & 2 & 3 \\ 2 & 1 & 0 & 7 \end{array}\right]

이제 첫 자리가 1이므로 평소대로 R3→R3−2R1R_3 \to R_3 - 2R_1 로 진행합니다. 행을 맞바꾸는 것은 방정식의 순서만 바꾸는 것이니 해에는 아무 영향이 없습니다.

건너뛰는 열

맞바꿀 행마저 없는 경우도 있습니다. 그 열의 그 자리부터 아래가 전부 0일 때입니다.

[121300240012]\left[\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 1 & 2 \end{array}\right]

둘째 열은 둘째 행 아래가 전부 0이라 아무리 맞바꿔도 0이 아닌 값이 올라오지 않습니다. 이럴 때는 그 열을 그냥 두고 오른쪽 열로 옮겨 가 거기서 피벗을 찾습니다. 셋째 열의 2를 피벗으로 삼아 R3→R3−12R2R_3 \to R_3 - \tfrac12 R_2 를 하면

[121300240000]\left[\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{array}\right]

가 되어 사다리꼴이 완성됩니다. 피벗이 꼭 대각선 위에 있어야 하는 것은 아닙니다. 계단이 한 칸이 아니라 두 칸씩 내려가도 되고, 그렇게 건너뛴 열이 있다는 것 자체가 뒤에서 볼 판별의 재료가 됩니다.

소거의 연산 횟수

절차가 정해졌으니 품이 얼마나 드는지도 셀 수 있습니다. 미지수가 nn 개일 때 소거에 드는 곱셈과 나눗셈의 횟수는 대략 n3/3n^3/3 입니다. 첫 열을 지우는 데 nn 개 남짓한 행마다 nn 개 남짓한 자리를 고쳐야 하고, 그 일을 열마다 되풀이하기 때문입니다.

미지수 nn 대략의 연산 횟수
3 9
30 9,000
300 9,000,000

미지수가 열 배가 되면 계산은 천 배가 됩니다. 세제곱이라는 말이 실감나는 자리입니다. 손으로 푸는 3이나 4까지는 아무 문제가 없지만, 미지수가 수천 개인 연립을 다룰 때 이 세제곱이 곧바로 시간으로 나타납니다.

후진 대입

사다리꼴이 되면 아래 행부터 거꾸로 대입해 미지수를 구합니다. 이것을 후진 대입이라 합니다.

아래에서 위로

세 번째 행 3z=63z = 6 에서 z=2z = 2.

두 번째 행 y−z=2y - z = 2 에 z=2z = 2 를 넣으면 y=4y = 4.

첫 번째 행 x+y+z=6x + y + z = 6 에 y=4,z=2y = 4, z = 2 를 넣으면 x=0x = 0.

해는 x=0,y=4,z=2x = 0, y = 4, z = 2 입니다. 원래 식에 넣어 검산합니다.

0+4+2=6 ✓0+12+2=14 ✓0+8+6=14 ✓0 + 4 + 2 = 6 \ \checkmark \qquad 0 + 12 + 2 = 14 \ \checkmark \qquad 0 + 8 + 6 = 14 \ \checkmark

세 미지수를 요령 없이, 정해진 순서만으로 구했습니다. 이 절차 전체를 가우스 소거라 부릅니다.

후진 대입의 비용

후진 대입은 마지막 행에서 곱셈 한 번, 그 위 행에서 두 번 하는 식으로 올라가므로 연산 횟수가 대략 n2n^2 입니다. 앞 절의 n3/3n^3/3 과 나란히 놓으면 크기 차이가 분명합니다.

미지수 nn 소거 후진 대입
30 9,000 900
300 9,000,000 90,000

n=300n = 300 에서 후진 대입은 전체의 1%에 못 미칩니다. 전체 비용은 소거가 지배합니다. 그래서 같은 계수행렬을 여러 번 쓸 일이 있으면, 비싼 소거를 한 번만 해 두고 싼 대입만 되풀이하고 싶어집니다. 여섯째 절의 LU 분해가 정확히 그 이야기입니다.

검산의 한계

검산은 반드시 하되, 검산이 무엇을 보장하고 무엇을 보장하지 않는지는 갈라 두어야 합니다.

  • 구한 값을 원래 식에 넣어 전부 맞으면, 그 값이 해라는 것은 확실합니다. 소거 도중에 실수가 있었더라도 결과가 맞으면 맞은 것입니다.
  • 그러나 다른 해가 없다는 보장은 되지 않습니다. 해가 무한히 많은 연립에서 그중 하나를 집어 넣어도 검산은 똑같이 통과합니다.

해가 하나뿐인지는 검산이 아니라 사다리꼴의 모양이 답합니다. 다음 절에서 볼 피벗의 개수가 그 판별을 맡습니다.

분수와 소수

손으로 소거할 때는 나눗셈이 나와도 분수를 그대로 끌고 갑니다. 소수로 반올림하면 뒤 계산이 조금씩 어긋나기 때문입니다. R2→23R2R_2 \to \tfrac23 R_2 를 해야 하는 자리에서 23\tfrac23 을 0.670.67 로 적었다고 해 봅니다.

23×3=2vs0.67×3=2.01\tfrac23 \times 3 = 2 \qquad \text{vs} \qquad 0.67 \times 3 = 2.01

한 번은 0.01 차이지만, 이 값이 다음 행 연산의 곱하는 수로 들어가고 그 결과가 또 다음 연산에 들어갑니다. 어긋남이 자리를 옮겨 가며 커지므로 마지막 미지수에서는 눈에 띄는 오차가 됩니다. 분수로 두면 23×3=2\tfrac23 \times 3 = 2 가 정확히 2라 이런 일이 아예 없습니다.

나눗셈을 늦추는 요령도 있습니다. 피벗을 1로 만들려고 서둘러 나누는 대신, R2→3R2−2R1R_2 \to 3R_2 - 2R_1 처럼 양쪽에 정수를 곱해 빼면 분수가 나오지 않습니다. 해를 바꾸지 않는 연산 안에 있으므로 써도 되는 손놀림입니다.

해의 세 갈래

방정식 셋을 세워도 늘 답이 하나 나오는 것은 아닙니다. 세 가지 경우가 있고, 어느 경우인지는 소거 마지막 행의 모양이 정합니다.

소거 마지막 줄이 세 갈래를 정한다

무한히 많은 해

방금 예에서 세 번째 방정식을 바꿔 봅니다.

{x+y+z=62x+3y+z=143x+4y+2z=20\begin{cases} x + y + z = 6 \\ 2x + 3y + z = 14 \\ 3x + 4y + 2z = 20 \end{cases}

첫 두 방정식을 그냥 더하면 3x+4y+2z=203x + 4y + 2z = 20 — 이것이 정확히 셋째 방정식입니다. 셋째 식은 앞의 두 식이 이미 말하는 것을 되풀이한 것이라 새 정보가 없습니다.

소거로 확인합니다.

[11162311434220]→R2−2R1, R3−3R1[111601−1201−12]\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 2 & 3 & 1 & 14 \\ 3 & 4 & 2 & 20 \end{array}\right] \xrightarrow{R_2 - 2R_1,\ R_3 - 3R_1} \left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -1 & 2 \\ 0 & 1 & -1 & 2 \end{array}\right]

→R3−R2[111601−120000]\xrightarrow{R_3 - R_2} \left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -1 & 2 \\ 0 & 0 & 0 & 0 \end{array}\right]

마지막 줄이 0=00 = 0 이 되었습니다. 참인 문장이지만 아무 조건이 안 붙었으므로, 남은 두 방정식으로 세 미지수를 정해야 하는 상황입니다. 셋 중 하나는 자유롭게 정할 수 있고, 나머지 둘이 그것에 따라 정해집니다. 해가 무한히 많다는 뜻입니다.

이 무한한 해를 어떻게 매개변수로 적는지는 중급 8번 · 생성·일차독립·기저의 것이라 여기서는 소거 마지막 줄이 0=00 = 0 으로 나온다는 판별까지만 합니다.

해가 없는 연립

한 번 더 바꿔 봅니다.

{x+y+z=62x+3y+z=143x+4y+2z=21\begin{cases} x + y + z = 6 \\ 2x + 3y + z = 14 \\ 3x + 4y + 2z = 21 \end{cases}

앞 두 식을 더한 것이 3x+4y+2z=203x + 4y + 2z = 20 인데, 셋째 식은 그것이 21이라 주장합니다. 20과 21이 동시에 성립할 수는 없습니다. 소거로도 이것이 잡힙니다.

[11162311434221]→R2−2R1, R3−3R1[111601−1201−13]\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 2 & 3 & 1 & 14 \\ 3 & 4 & 2 & 21 \end{array}\right] \xrightarrow{R_2 - 2R_1,\ R_3 - 3R_1} \left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -1 & 2 \\ 0 & 1 & -1 & 3 \end{array}\right]

→R3−R2[111601−120001]\xrightarrow{R_3 - R_2} \left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -1 & 2 \\ 0 & 0 & 0 & 1 \end{array}\right]

마지막 줄이 0=10 = 1 입니다. 이것은 절대로 참이 될 수 없으므로 해가 없습니다.

피벗의 개수

세 예에서 앞 두 방정식은 같았는데 소거의 마지막 줄만 달랐습니다.

마지막 줄 해
피벗⋅z=수\text{피벗} \cdot z = \text{수} (본문 첫 예에서 3z=63z = 6) 하나
0=00 = 0 무한히 많음
0=(≠0)0 = (\ne 0) 없음

이 표를 한 번 더 조여 셀 수 있는 규칙으로 바꿀 수 있습니다. 막대 왼쪽에서 피벗을 가진 열은 값이 따라 정해지는 미지수이고, 피벗이 없는 열은 값을 마음대로 골라도 되는 미지수입니다. 그러니 마음대로 고를 수 있는 미지수의 개수는 다음과 같습니다.

(자유롭게 정하는 미지수의 수)=n−(피벗의 수)(\text{자유롭게 정하는 미지수의 수}) = n - (\text{피벗의 수})

앞의 세 예에 넣어 보면 갈래가 그대로 나옵니다. 첫 예는 n=3n = 3 에 피벗이 셋이라 자유가 0이고 해가 하나입니다. 무한히 많던 예는 피벗이 둘이라 자유가 하나입니다. 해가 없던 예는 셈을 하기 전에 막대 오른쪽에서 0=10 = 1 이 나와 그 자리에서 끝납니다.

피벗 수와 미지수 수를 견주는 세 경우

여기서 방정식을 몇 개 세워야 하는지에 대한 답도 나옵니다. 피벗은 한 행에 많아야 하나씩 생기므로 피벗의 수는 방정식의 수를 넘을 수 없습니다. 방정식이 미지수보다 적어 m<nm < n 이면 피벗의 수도 nn 보다 작아 자유로운 미지수가 적어도 하나 남습니다. 그러면 해가 하나일 수가 없습니다 — 무한히 많거나 아예 없거나 둘 중 하나입니다.

반대로 방정식이 미지수보다 많다고 해서 해가 잘 정해지는 것도 아닙니다. 되풀이된 식이 섞여 있으면 피벗이 그만큼 안 생기고, 서로 어긋나는 식이 섞여 있으면 0=(≠0)0 = (\ne 0) 이 나옵니다. 해의 개수는 방정식의 수 그 자체가 아니라, 소거한 뒤 남는 정보의 양이 정합니다.

조건수와 LU 분해

마지막으로 소거에서 자연스럽게 따라 나오는 두 이름을 짚고 넘어갑니다. 이 글에서 절차로 굳히지는 않고, 나중에 다시 만났을 때 처음 보는 말이 아니도록 해 두는 정도입니다.

흔들리는 연립

계수를 아주 조금만 바꿨는데 해가 크게 움직이는 연립이 있습니다. 손으로 한 번 봅니다.

{x+y=2x+1.001y=2.001\begin{cases} x + y = 2 \\ x + 1.001y = 2.001 \end{cases}

둘째 식에서 첫 식을 빼면 0.001y=0.0010.001y = 0.001 이므로 y=1y = 1 이고 x=1x = 1 입니다. 이제 둘째 식의 계수 1.0011.001 을 1.0021.002 로, 딱 0.0010.001 만 바꿔 봅니다.

{x+y=2x+1.002y=2.001\begin{cases} x + y = 2 \\ x + 1.002y = 2.001 \end{cases}

같은 방식으로 빼면 0.002y=0.0010.002y = 0.001 이므로 y=0.5y = 0.5 이고 x=1.5x = 1.5 입니다. 계수를 천분의 일 흔들었더니 해가 0.5씩 움직였습니다 — 흔든 양의 오백 배입니다.

왜 이런 일이 생기는지는 그림으로 보면 분명합니다. 두 식이 나타내는 직선의 기울기가 −1-1 과 −1.001-1.001 로 거의 같습니다. 거의 나란한 두 직선의 교점은 한쪽을 아주 조금만 기울여도 멀리 미끄러집니다. 계수가 0이 아니고 소거도 멀쩡히 끝나므로 해는 분명히 하나인데, 그 하나가 불안한 자리에 있는 것입니다.

조건수

이 흔들림의 크기를 재는 수에 이름이 있습니다. 조건수는 계수나 우변의 작은 변화가 해를 얼마나 크게 움직이는지를 나타내는 값으로, 클수록 위의 예처럼 불안합니다.

조건수가 큰 연립은 손으로 풀 때도 앞서 본 반올림 문제에 훨씬 약합니다. 자릿수를 조금 잃은 중간값이 해에서는 크게 벌어지기 때문입니다. 이론상 유일한 해가 있다는 것과 그 해를 믿을 만하게 구할 수 있다는 것은 다른 이야기라는 것이 이 이름이 짚어 주는 자리입니다. 자릿수와 오차 자체는 초급 47번 · 자릿수와 오차가 다룹니다.

LU 분해

소거를 하는 동안 우리는 "둘째 행에서 첫째 행의 2배를 뺐다", "셋째 행에서 둘째 행을 뺐다" 같은 기록을 만듭니다. 그 기록을 버리지 않고 표로 모아 두면, 계수행렬 AA 를 왼쪽 아래만 채워진 행렬 LL 과 왼쪽 아래가 비어 있는 사다리꼴 UU 의 곱으로 적을 수 있습니다. 이것을 LU 분해라 합니다.

A=LUA = LU

쓸모는 앞서 셈한 두 비용에서 곧바로 나옵니다. 소거는 n3/3n^3/3 인데 대입은 n2n^2 이었습니다. 같은 AA 에 우변만 바꿔 백 번 풀어야 한다면, 비싼 소거는 한 번만 하고 싼 대입만 백 번 하면 됩니다. 우변을 여러 열로 붙여 한꺼번에 소거하던 첫 절의 요령이 우변을 미리 알 때의 방법이라면, LU는 우변이 나중에 하나씩 도착할 때의 방법입니다.

연습 문제

연습 1 — 3×3 연립방정식 풀기

다음 연립방정식을 첨가행렬로 적고 가우스 소거로 사다리꼴까지 만든 뒤 후진 대입으로 답을 내고 원래 식에 넣어 검산하세요.

{x+2y+z=82x+5y+3z=21x+3y+4z=15\begin{cases} x + 2y + z = 8 \\ 2x + 5y + 3z = 21 \\ x + 3y + 4z = 15 \end{cases}

답. 첨가행렬은 [12182532113415]\left[\begin{array}{ccc|c} 1 & 2 & 1 & 8 \\ 2 & 5 & 3 & 21 \\ 1 & 3 & 4 & 15 \end{array}\right] 입니다. R2→R2−2R1R_2 \to R_2 - 2R_1, R3→R3−R1R_3 \to R_3 - R_1 로 [121801150137]\left[\begin{array}{ccc|c} 1 & 2 & 1 & 8 \\ 0 & 1 & 1 & 5 \\ 0 & 1 & 3 & 7 \end{array}\right] 이 됩니다. 다시 R3→R3−R2R_3 \to R_3 - R_2 로 [121801150022]\left[\begin{array}{ccc|c} 1 & 2 & 1 & 8 \\ 0 & 1 & 1 & 5 \\ 0 & 0 & 2 & 2 \end{array}\right] 이 됩니다. 후진 대입: 2z=22z = 2 에서 z=1z = 1, y+z=5y + z = 5 에서 y=4y = 4, x+2y+z=8x + 2y + z = 8 에서 x=8−8−1=−1x = 8 - 8 - 1 = -1. 원래 식에 넣어 −1+8+1=8-1 + 8 + 1 = 8 ✓, −2+20+3=21-2 + 20 + 3 = 21 ✓, −1+12+4=15-1 + 12 + 4 = 15 ✓ 로 검산됩니다.

연습 2 — 세 갈래를 소거 마지막 줄로 판별

각 연립방정식에 대해 첨가행렬로 옮겨 사다리꼴까지 소거하고, 마지막 줄이 어떤 모양인지와 해가 어느 갈래인지를 답하세요.

  1. {x+y=3x−y=12x+y=4\begin{cases} x + y = 3 \\ x - y = 1 \\ 2x + y = 4 \end{cases}
    방정식이 셋인데 미지수는 둘입니다. [1131−11214]→R2−R1, R3−2R1[1130−2−20−1−2]→R3−12R2[1130−2−200−1]\left[\begin{array}{cc|c} 1 & 1 & 3 \\ 1 & -1 & 1 \\ 2 & 1 & 4 \end{array}\right] \xrightarrow{R_2 - R_1,\ R_3 - 2R_1} \left[\begin{array}{cc|c} 1 & 1 & 3 \\ 0 & -2 & -2 \\ 0 & -1 & -2 \end{array}\right] \xrightarrow{R_3 - \frac{1}{2}R_2} \left[\begin{array}{cc|c} 1 & 1 & 3 \\ 0 & -2 & -2 \\ 0 & 0 & -1 \end{array}\right]. 마지막 줄이 0=−10 = -1 이므로 해가 없습니다.
  2. {x+y+z=32x+2y+2z=63x+3y+3z=9\begin{cases} x + y + z = 3 \\ 2x + 2y + 2z = 6 \\ 3x + 3y + 3z = 9 \end{cases}
    R2→R2−2R1R_2 \to R_2 - 2R_1, R3→R3−3R1R_3 \to R_3 - 3R_1 로 아래 두 행이 모두 0 0 0∣00\ 0\ 0 \mid 0 이 되므로 사다리꼴이 [111300000000]\left[\begin{array}{ccc|c} 1 & 1 & 1 & 3 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array}\right] 입니다. 마지막 줄이 0=00 = 0 이고 두 줄이나 그렇습니다. 해가 무한히 많습니다 — 셋 다 같은 방정식을 배수로 적은 것이었습니다.
  3. {x+2y−z=32x+4y−z=8x+2y+z=5\begin{cases} x + 2y - z = 3 \\ 2x + 4y - z = 8 \\ x + 2y + z = 5 \end{cases}
    R2→R2−2R1R_2 \to R_2 - 2R_1, R3→R3−R1R_3 \to R_3 - R_1 로 [12−1300120022]\left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 2 & 2 \end{array}\right] 이 되고 다시 R3→R3−2R2R_3 \to R_3 - 2R_2 로 [12−130012000−2]\left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & -2 \end{array}\right]. 마지막 줄이 0=−20 = -2 이므로 해가 없습니다.

연습 3 — 손 소거의 계단

[24−2649−315−2−37−3]\left[\begin{array}{ccc|c} 2 & 4 & -2 & 6 \\ 4 & 9 & -3 & 15 \\ -2 & -3 & 7 & -3 \end{array}\right]

  1. 첫 열 아래를 0으로 만드는 두 행 연산을 적고 그 결과를 쓰세요.
    R2→R2−2R1R_2 \to R_2 - 2R_1, R3→R3+R1R_3 \to R_3 + R_1 로 [24−2601130153]\left[\begin{array}{ccc|c} 2 & 4 & -2 & 6 \\ 0 & 1 & 1 & 3 \\ 0 & 1 & 5 & 3 \end{array}\right] 이 됩니다.
  2. 두 번째 열 아래를 0으로 만드는 행 연산을 적고 사다리꼴을 완성하세요.
    R3→R3−R2R_3 \to R_3 - R_2 로 [24−2601130040]\left[\begin{array}{ccc|c} 2 & 4 & -2 & 6 \\ 0 & 1 & 1 & 3 \\ 0 & 0 & 4 & 0 \end{array}\right] 이 됩니다. 피벗은 2, 1, 4로 셋 다 0이 아닙니다.
  3. 후진 대입으로 x,y,zx, y, z 를 구하고 원래 식에 넣어 검산하세요.
    4z=04z = 0 이므로 z=0z = 0. y+z=3y + z = 3 에서 y=3y = 3. 2x+4y−2z=62x + 4y - 2z = 6 에서 2x+12=62x + 12 = 6, x=−3x = -3. 원래 식에 넣으면 2(−3)+4(3)−2(0)=62(-3) + 4(3) - 2(0) = 6 ✓, 4(−3)+9(3)−3(0)=154(-3) + 9(3) - 3(0) = 15 ✓, −2(−3)−3(3)+7(0)=−3-2(-3) - 3(3) + 7(0) = -3 ✓.

연습 4 — 자유로운 미지수 세기

다음 사다리꼴을 보고 피벗의 수, 자유롭게 정할 수 있는 미지수의 수, 해의 갈래를 차례로 답하세요. 미지수는 모두 x,y,z,wx, y, z, w 넷입니다.

  1. [120140031600000]\left[\begin{array}{cccc|c} 1 & 2 & 0 & 1 & 4 \\ 0 & 0 & 3 & 1 & 6 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right]
    피벗은 첫 열의 1과 셋째 열의 3으로 둘입니다. 미지수가 넷이므로 자유로운 미지수는 4−2=24 - 2 = 2 개이고, 마지막 줄이 0=00 = 0 이므로 해가 무한히 많습니다.
  2. [21005011030041800026]\left[\begin{array}{cccc|c} 2 & 1 & 0 & 0 & 5 \\ 0 & 1 & 1 & 0 & 3 \\ 0 & 0 & 4 & 1 & 8 \\ 0 & 0 & 0 & 2 & 6 \end{array}\right]
    피벗이 2, 1, 4, 2로 넷입니다. 자유로운 미지수는 4−4=04 - 4 = 0 개이므로 해가 하나뿐입니다. 마지막 줄 2w=62w = 6 에서 w=3w = 3 으로 후진 대입이 시작됩니다.
  3. [111120210400005]\left[\begin{array}{cccc|c} 1 & 1 & 1 & 1 & 2 \\ 0 & 2 & 1 & 0 & 4 \\ 0 & 0 & 0 & 0 & 5 \end{array}\right]
    마지막 줄이 0=50 = 5 라 해가 없습니다. 이 경우에는 피벗을 세어 자유로운 미지수를 구할 필요가 없습니다 — 모순이 하나라도 있으면 그 자리에서 끝입니다.

정리

  • 미지수 셋 이상의 연립방정식은 요령이 아니라 절차로 풀어야 실수가 줄어듭니다. 그 절차가 가우스 소거입니다.
  • 계수행렬 오른쪽에 우변을 붙인 것이 첨가행렬 [A∣b][A \mid b] 입니다. 빠진 미지수 자리에는 0을 반드시 적고, 행은 방정식·열은 미지수로 읽습니다. 우변이 여럿이면 막대 오른쪽에 열을 여러 개 붙여 한 번에 소거합니다.
  • 해를 바꾸지 않는 행 연산은 셋뿐이고, 셋 다 되돌릴 수 있어서 해집합이 양쪽으로 보존됩니다. 열은 맞바꾸지 않으며, 한 줄에 몰아 쓸 연산은 고치는 행과 읽는 행이 겹치지 않아야 합니다.
  • 왼쪽 아래를 0으로 만들어 만든 모양이 행 사다리꼴이고, 각 행에서 처음 0이 아닌 자리가 피벗입니다. 피벗 자리가 0이면 아래 행과 맞바꾸고, 맞바꿀 행도 없으면 그 열을 건너뜁니다.
  • 소거는 대략 n3/3n^3/3, 후진 대입은 대략 n2n^2 번의 곱셈이 듭니다. 미지수가 열 배면 소거는 천 배가 되고, 전체 비용은 소거가 지배합니다.
  • 검산은 그 값이 해라는 것만 보장하고 다른 해가 없다는 것은 보장하지 않습니다. 손계산에서는 반올림한 소수 대신 분수를 끌고 갑니다.
  • 해의 개수는 소거 마지막 줄이 정합니다 — 자유로운 미지수의 수가 nn 에서 피벗 수를 뺀 값이고, 0=(≠0)0 = (\ne 0) 이 한 줄이라도 나오면 해가 없습니다. 방정식이 미지수보다 적으면 해가 하나일 수 없습니다.
  • 조건수는 계수를 조금 흔들었을 때 해가 얼마나 크게 움직이는지를 재는 값이고, LU 분해는 소거의 기록을 남겨 우변만 바뀔 때 소거를 되풀이하지 않는 방식입니다. 둘 다 이름만 알아 둡니다.

다음 글은 이 소거가 2×2에서 남긴 분모 ad−bcad - bc 를 별도의 이름으로 세워, 그 값이 무엇을 재는지와 역행렬로 어떻게 이어지는지를 봅니다.


읽어주셔서 감사합니다. 😊

LATEST

수학의 최신 글

수학2026.11.17

다양체 위의 최적화: 직교 제약과 Muon의 직교화가 하는 일

차트·접공간·리만 계량·측지선·후퇴로 다양체를 세우고, 스티펠·그라스만·양정치 행렬·확률 단체의 접공간과 사영을 계산한 뒤, 리만 그래디언트가 유클리드 그래디언트의 접공간 사영임을 증명하고 극분해 후퇴와 뉴턴–슐츠 반복의 수렴 조건을 다룹니다.

고급46 MIN
수학2026.11.17

프리컨디셔닝의 이론: Adam에서 K-FAC·Shampoo·Muon까지 한 줄로

갱신 −ηP⁻¹∇를 노름의 최급강하로 읽고 헤세·가우스–뉴턴·피셔·경험적 피셔의 관계를 정리한 뒤, 준뉴턴과 3차 정규화, K-FAC의 크로네커 인수분해와 그 독립 가정, Shampoo의 −1/4 지수, Muon의 스펙트럴 노름 유도를 차례로 세워 이들이 어디서 일치하는지 보입니다.

고급41 MIN
수학2026.11.17

확률적 근사와 SGD의 연속 극한: 수렴한다는 말의 정확한 뜻

로빈스–먼로 조건과 마팅게일 잡음으로 SGD의 수렴을 정확히 정의하고, 볼록·강볼록·PL·비볼록에서의 수렴률과 오라클 하한을 계산한 뒤, SGD를 확률미분방정식으로 읽어 학습률/배치가 온도가 되는 관점과 안정성의 가장자리를 다룹니다.

고급48 MIN