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

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

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

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

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

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

첨가행렬

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

$\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

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

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

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

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

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

행렬의 크기

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

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

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

여러 개의 우변

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

$\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$ 이 된 방정식은 아무것도 말하지 않으니 원래 있던 조건 하나를 잃습니다.

역연산과 해집합

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

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

연산	되돌리는 연산
$R_i \leftrightarrow R_j$	다시 $R_i \leftrightarrow R_j$
$R_i \to k R_i$ ($k \ne 0$)	$R_i \to \tfrac{1}{k} R_i$
$R_i \to R_i + k R_j$	$R_i \to R_i - k R_j$

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

열 맞바꾸기

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

$\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]$

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

한 줄에 몰아 쓰기

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

문제는 이런 짝입니다.

$R_2 \to R_2 - 2R_1, \qquad R_1 \to R_1 - R_2$

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

가우스 소거와 사다리꼴

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

사다리꼴 만들기

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

$R_2 \to R_2 - 2R_1, \quad R_3 \to R_3 - R_1$

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

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

$R_3 \to R_3 - R_2$

$\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이 앉아 있는 일이 생깁니다.

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

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

$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이므로 평소대로 $R_3 \to R_3 - 2R_1$ 로 진행합니다. 행을 맞바꾸는 것은 방정식의 순서만 바꾸는 것이니 해에는 아무 영향이 없습니다.

건너뛰는 열

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

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

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

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

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

소거의 연산 횟수

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

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

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

후진 대입

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

아래에서 위로

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

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

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

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

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

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

후진 대입의 비용

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

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

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

검산의 한계

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

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

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

분수와 소수

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

$\tfrac23 \times 3 = 2 \qquad \text{vs} \qquad 0.67 \times 3 = 2.01$

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

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

해의 세 갈래

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

무한히 많은 해

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

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

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

소거로 확인합니다.

$\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]$

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

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

해가 없는 연립

한 번 더 바꿔 봅니다.

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

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

$\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]$

$\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 = 1$ 입니다. 이것은 절대로 참이 될 수 없으므로 해가 없습니다.

피벗의 개수

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

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

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

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

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

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

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

조건수와 LU 분해

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

흔들리는 연립

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

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

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

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

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

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

조건수

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

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

LU 분해

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

$A = LU$

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

연습 문제

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

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

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

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

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

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

1. $\begin{cases} x + y = 3 \\ x - y = 1 \\ 2x + y = 4 \end{cases}$

   방정식이 셋인데 미지수는 둘입니다. $\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 = -1$ 이므로 해가 없습니다.
2. $\begin{cases} x + y + z = 3 \\ 2x + 2y + 2z = 6 \\ 3x + 3y + 3z = 9 \end{cases}$

   $R_2 \to R_2 - 2R_1$, $R_3 \to R_3 - 3R_1$ 로 아래 두 행이 모두 $0\ 0\ 0 \mid 0$ 이 되므로 사다리꼴이 $\left[\begin{array}{ccc|c} 1 & 1 & 1 & 3 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array}\right]$ 입니다. 마지막 줄이 $0 = 0$ 이고 두 줄이나 그렇습니다. 해가 무한히 많습니다 — 셋 다 같은 방정식을 배수로 적은 것이었습니다.
3. $\begin{cases} x + 2y - z = 3 \\ 2x + 4y - z = 8 \\ x + 2y + z = 5 \end{cases}$

   $R_2 \to R_2 - 2R_1$, $R_3 \to R_3 - R_1$ 로 $\left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 2 & 2 \end{array}\right]$ 이 되고 다시 $R_3 \to R_3 - 2R_2$ 로 $\left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & -2 \end{array}\right]$. 마지막 줄이 $0 = -2$ 이므로 해가 없습니다.

연습 3 — 손 소거의 계단

$\left[\begin{array}{ccc|c} 2 & 4 & -2 & 6 \\ 4 & 9 & -3 & 15 \\ -2 & -3 & 7 & -3 \end{array}\right]$

1. 첫 열 아래를 0으로 만드는 두 행 연산을 적고 그 결과를 쓰세요.

   $R_2 \to R_2 - 2R_1$, $R_3 \to R_3 + R_1$ 로 $\left[\begin{array}{ccc|c} 2 & 4 & -2 & 6 \\ 0 & 1 & 1 & 3 \\ 0 & 1 & 5 & 3 \end{array}\right]$ 이 됩니다.
2. 두 번째 열 아래를 0으로 만드는 행 연산을 적고 사다리꼴을 완성하세요.

   $R_3 \to R_3 - R_2$ 로 $\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, z$ 를 구하고 원래 식에 넣어 검산하세요.

   $4z = 0$ 이므로 $z = 0$. $y + z = 3$ 에서 $y = 3$. $2x + 4y - 2z = 6$ 에서 $2x + 12 = 6$, $x = -3$. 원래 식에 넣으면 $2(-3) + 4(3) - 2(0) = 6$ ✓, $4(-3) + 9(3) - 3(0) = 15$ ✓, $-2(-3) - 3(3) + 7(0) = -3$ ✓.

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

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

1. $\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 = 2$ 개이고, 마지막 줄이 $0 = 0$ 이므로 해가 무한히 많습니다.
2. $\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 = 0$ 개이므로 해가 하나뿐입니다. 마지막 줄 $2w = 6$ 에서 $w = 3$ 으로 후진 대입이 시작됩니다.
3. $\left[\begin{array}{cccc|c} 1 & 1 & 1 & 1 & 2 \\ 0 & 2 & 1 & 0 & 4 \\ 0 & 0 & 0 & 0 & 5 \end{array}\right]$

   마지막 줄이 $0 = 5$ 라 해가 없습니다. 이 경우에는 피벗을 세어 자유로운 미지수를 구할 필요가 없습니다 — 모순이 하나라도 있으면 그 자리에서 끝입니다.

정리

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

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

---

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