66강에서 연립방정식을 한 줄로 적었습니다. 그런데 적는 것과 푸는 것은 다릅니다.
미지수가 둘이면 대입해서 풉니다. 셋이면 좀 번거롭지만 여전히 됩니다. 그런데 미지수가 열이 되면 어느 것부터 대입할지, 어떤 순서로 정리할지가 사람마다 달라지고 실수가 늘어납니다.
필요한 것은 요령이 아니라 절차입니다. 생각하지 않고 따라가기만 해도 반드시 답이 나오고, 답이 없으면 없다고 알려 주며, 컴퓨터에 그대로 옮길 수 있는 절차여야 합니다.
그것이 가우스 소거법입니다. 이 강의에서 절차를 세우고, 그 절차가 왜 답을 바꾸지 않는지 증명하며, 각 단계가 행렬 곱으로 표현된다는 사실까지 봅니다. 마지막 사실이 70강의 LU 분해로 이어집니다.
문제. 다음을 푸세요.
(1) 계수와 상수항을 한 표에 담으세요.
(2) 아래쪽 방정식에서 를 없애세요.
(3) 계속해서 계단 모양으로 만들고 해를 구하세요.
생각의 실마리. (2)에서 첫 방정식을 몇 배 해서 빼면 가 사라집니다. 어느 방정식에서 다른 방정식의 배수를 빼도 해는 변하지 않는다는 사실을 쓰는 것인데, 이 점은 문제 2에서 따집니다.
풀이. (1) 계수와 상수항을 함께 적습니다. 이것을 첨가행렬이라 합니다.
(2) 첫 행을 기준으로 삼습니다. 둘째 행에서 첫 행의 배를, 셋째 행에서 첫 행의 배를 뺍니다.
(3) 이제 둘째 행을 기준으로 셋째 행에서 배를 뺍니다.
계단 모양이 되었습니다. 아래에서부터 거슬러 올라갑니다.
이 문제에서 배우는 것: 소거의 절차.
세 가지 행 연산.
이름 조작 표기 교환 두 행을 맞바꿉니다 R_{i}\leftrightarrow R_ 배수 한 행에 아닌 수를 곱합니다 R_{i}\to cR_ 덧셈 한 행에 다른 행의 배수를 더합니다 R_{i}\to R_{i}+cR_
이 셋만으로 모든 연립방정식을 풉니다. 셋 다 되돌릴 수 있다는 점이 핵심이며 문제 2에서 그 뜻을 봅니다.
목표하는 모양도 이름을 붙입니다.
행사다리꼴. 다음을 만족하는 모양입니다.
- 성분이 모두 인 행은 맨 아래에 모입니다.
- 각 행에서 처음 나오는 이 아닌 성분(피벗)이 위 행의 피벗보다 오른쪽에 있습니다.
- 피벗 아래는 모두 입니다.
절차를 정리합니다.
앞의 절반을 전진소거, 뒤의 절반을 후진대입이라 합니다.
여기서 주의할 것이 하나 있습니다. 피벗을 만들 때 위쪽부터 순서대로 진행해야 합니다. 아래 행을 먼저 건드리면 이미 만들어 둔 이 되살아납니다.
바로 확인 1.
확인 1-1. 세 가지 행 연산을 쓰세요.
답. 두 행 교환, 한 행에 아닌 수 곱하기, 한 행에 다른 행의 배수 더하기입니다.
확인 1-2. 피벗이 무엇인지 쓰세요.
답. 각 행에서 처음 나오는 이 아닌 성분입니다.
확인 1-3. 전진소거와 후진대입이 각각 무엇을 합니까?
답. 전진소거는 계단 모양을 만들고 후진대입은 아래에서부터 미지수를 구합니다.
문제. 행 연산이 해집합을 바꾸지 않음을 보이려 합니다.
(1) 무엇을 증명해야 합니까?
(2) 의 경우를 증명하세요.
(3) 이 성질이 세 연산 모두에 성립하는 공통 이유를 말하세요.
생각의 실마리. (1)에서 "해집합이 같다"는 것은 양쪽 포함을 뜻합니다. 원래 해가 새 방정식의 해이고, 새 해가 원래의 해여야 합니다. (3)에서는 각 연산을 되돌리는 연산이 있는지 확인합니다.
풀이. (1) 원래 방정식계를 , 연산 후를 라 하면 해집합이 서로 같음, 즉 를 보여야 합니다.
(2) 방정식 두 개를 , 라 하고 연산 후를 봅니다.
의 해는 의 해입니다. 과 가 성립하면 양변을 배해 더한 도 성립합니다.
거꾸로도 성립합니다. 의 해라면 이고 입니다. 둘째 식에서 첫째 식의 배를 빼면 입니다.
따라서 해집합이 같습니다.
(3) 거꾸로 가는 방향의 증명이 핵심이었습니다. 그 부분에서 한 일은 연산을 되돌린 것입니다.
| 연산 | 되돌리는 연산 |
|---|---|
| R_{i}\leftrightarrow R_ | 다시 R_{i}\leftrightarrow R_ |
| () | R_{i}\to \frac1cR_ |
| R_{i}\to R_{i}+cR_ | R_{i}\to R_{i}-cR_ |
세 연산 모두 같은 종류의 연산으로 되돌릴 수 있으므로 해집합이 보존됩니다.
이 문제에서 배우는 것: 가역성이 근거입니다.
동치인 방정식계. 세 가지 행 연산으로 서로 옮겨 갈 수 있는 두 방정식계는 같은 해집합을 가집니다.
이것이 소거법의 정당성 전부입니다. 계단 모양은 원래 방정식과 다르게 생겼지만 같은 것을 묻습니다.
배수 연산에서 조건이 왜 붙는지도 분명합니다. 이면 한 행이 통째로 사라지므로 되돌릴 수 없고, 정보를 잃어 해가 늘어납니다.
왼쪽은 해가 하나인데 오른쪽은 모든 가 해입니다. 되돌릴 수 없는 조작은 해집합을 바꿉니다.
이 관점은 뒤에서 계속 쓰입니다. 69강에서 역행렬을 다룰 때 "되돌릴 수 있는가"가 중심 질문이 되고, 문제 5의 정사영처럼 정보를 잃는 변환에 역행렬이 없는 이유가 여기 있습니다.
바로 확인 2.
확인 2-1. 해집합이 같음을 보이려면 무엇을 증명해야 합니까?
답. 양쪽 포함, 즉 원래 해가 새 해이고 새 해가 원래 해임을 보여야 합니다.
확인 2-2. 를 되돌리는 연산을 쓰세요.
답. 입니다.
확인 2-3. 배수 연산에서 이 필요한 이유를 쓰세요.
답. 이면 되돌릴 수 없고 정보를 잃어 해집합이 커지기 때문입니다.
문제. 세 방정식계를 소거해 마지막 모양을 비교하세요.
(1) (가)를 소거하고 마지막 행을 해석하세요.
(2) (나)를 소거하고 해를 모두 구하세요.
(3) 해의 개수가 결정되는 규칙을 정리하세요.
생각의 실마리. 두 계는 상수항 하나만 다릅니다. 왼쪽이 같으므로 소거 과정도 같고, 마지막 행의 상수항만 달라집니다. 그 한 칸이 무엇을 가르는지 보는 것이 이 문제입니다.
풀이. (1) 소거합니다.
마지막 행이 뜻하는 것은
인데 **왼쪽은 언제나 **입니다. 만족하는 가 없으므로 해가 없습니다.
(2) 상수항만 바뀝니다.
마지막 행은 이므로 아무 제약도 주지 않습니다. 남은 두 방정식은
입니다. 이고 이므로 를 아무 값 로 두면 입니다.
해가 무수히 많습니다. 검산에서 세 경우 모두 원래 방정식을 만족함이 확인됩니다.
(3) 규칙을 정리합니다.
이 문제에서 배우는 것: 해의 개수 판정.
판정법. 첨가행렬을 행사다리꼴로 만든 뒤 읽습니다.
마지막 모양 해 , 인 행이 있습니다 해가 없습니다 그런 행이 없고 피벗 개수 = 미지수 개수 유일한 해 그런 행이 없고 피벗 개수 < 미지수 개수 무수히 많은 해
용어를 붙입니다. 피벗이 있는 열의 미지수를 선행변수, 없는 열의 미지수를 자유변수라 합니다. (2)에서 피벗은 첫 열과 둘째 열에 있으므로 가 선행변수이고 가 자유변수입니다.
자유변수의 개수가 해집합의 차원입니다. (2)에서 자유변수가 하나이므로 해집합이 직선이고, 실제로 는 을 지나고 방향이 인 직선입니다.
기하로 읽으면 더 분명합니다. 각 방정식이 평면 하나이므로 세 평면의 교차를 묻는 것입니다.
| 상황 | 기하 |
|---|---|
| 해 없음 | 공통점이 없습니다 |
| 유일한 해 | 한 점에서 만납니다 |
| 무수히 많음 | 직선이나 평면에서 만납니다 |
(가)와 (나)에서 둘째 평면은 첫째 평면의 배이므로 같은 평면이거나 평행한 평면입니다. (나)는 같은 평면이라 겹치고, (가)는 평행해서 만나지 않습니다. 상수항 하나가 그 차이를 만들었습니다.
여기서 피벗의 개수가 중요한 양임이 드러났습니다. 그것이 73강의 계수이며, 74강에서 해집합의 구조를 완전히 기술하는 정리로 정식화됩니다.
바로 확인 3.
확인 3-1. 인 행이 나오면 무엇을 뜻합니까?
답. 이므로 해가 없습니다.
확인 3-2. 선행변수와 자유변수를 구별하는 기준을 쓰세요.
답. 그 열에 피벗이 있으면 선행변수이고 없으면 자유변수입니다.
확인 3-3. 미지수가 개이고 피벗이 개이며 모순 행이 없으면 해집합은 어떤 모양입니까?
답. 자유변수가 개이므로 이차원 평면 모양입니다.
문제. 에 대해 다음을 구하세요.
(1) 을 수행하는 행렬을 찾으세요.
(2) 교환과 배수 연산의 행렬도 찾으세요.
(3) 소거 전체를 하나의 식으로 쓰세요.
생각의 실마리. 66강 심화 1의 셋째 관점을 씁니다. 의 각 행은 의 그 행이 의 행들을 조합한 것이므로, 원하는 조합을 의 행에 적으면 됩니다.
풀이. (1) 결과의 첫 행은 의 첫 행 그대로이고 둘째 행은 (둘째 행) (첫 행)입니다. 조합의 계수를 그대로 적습니다.
단위행렬에서 원하는 연산을 한 번 수행한 것과 같습니다.
(2) 같은 방법입니다.
검산에서 이고 입니다.
(3) 소거를 단계 했다면 각 단계의 행렬을 순서대로 왼쪽에 곱한 것입니다.
전체 소거가 행렬 곱 하나가 되었습니다.
이 문제에서 배우는 것: 기본행렬.
기본행렬. 단위행렬에 행 연산을 한 번 적용한 행렬입니다. 왼쪽에서 곱하면 그 연산을 수행합니다.
만드는 법이 간단합니다. 하려는 연산을 에 그대로 하면 됩니다.
| 연산 | 기본행렬 () |
|---|---|
| R_{1}\leftrightarrow R_ | \begin{pmatrix}0&1\\ 1&0\end |
| R_{1}\to cR_ | \begin{pmatrix}c&0\\ 0&1\end |
| R_{2}\to R_{2}+cR_ | \begin{pmatrix}1&0\\ c&1\end |
모든 기본행렬은 역행렬을 가집니다. 문제 2에서 각 연산을 되돌리는 연산이 있다고 했는데, 그 되돌리는 연산의 기본행렬이 곧 역행렬입니다.
빼기를 더하기로 바꾸면 됩니다. 69강에서 이 사실로 역행렬을 계산하는 방법을 얻습니다.
라는 식이 왜 중요한지도 짚어 둡니다. 양변에 역행렬을 곱하면
인데, 행 교환이 없으면 왼쪽의 곱이 아래삼각행렬이 됩니다. 그러면 의 꼴이며 이것이 70강의 LU 분해입니다. 소거법을 행렬 곱으로 읽은 결과가 곧 분해입니다.
바로 확인 4.
확인 4-1. 기본행렬을 만드는 법을 한 문장으로 쓰세요.
답. 단위행렬에 그 행 연산을 한 번 적용합니다.
확인 4-2. 의 기본행렬을 쓰세요.
답. 입니다.
확인 4-3. 기본행렬이 언제나 역행렬을 가지는 이유를 쓰세요.
답. 모든 행 연산에 그것을 되돌리는 행 연산이 있기 때문입니다.
문제. 다음을 봅니다. 입니다.
(1) 정확한 해를 구하세요.
(2) 첫 행을 피벗으로 삼아 부동소수점으로 소거하면 어떻게 됩니까?
(3) 어떻게 고칩니까?
생각의 실마리. (2)에서 소거 계수가 이라는 엄청나게 큰 수가 됩니다. 그것을 곱해서 빼면 원래 있던 정보가 밀려납니다. 45강에서 본 자릿수 손실과 같은 구조입니다.
풀이. (1) 둘째 식에서 첫 식을 빼면 이므로
**정확한 해는 거의 **입니다.
(2) 첫 행을 피벗으로 쓰면 계수가 입니다. 둘째 행이
이 되는데 이므로 이고 입니다. 과 가 옆에서 사라집니다. 그러면 은 제대로 나오지만 첫 식으로 돌아가
를 계산할 때 분자가 반올림으로 정확히 이 되어 ****이 나옵니다.
검산에서 이 계산이 0.000000 1.000000을 줍니다. 가 완전히 틀렸습니다.
(3) 두 행을 바꿔 큰 성분을 피벗으로 씁니다.
이제 소거 계수가 로 작습니다. 둘째 행이 이 되어 이고 입니다.
검산에서 1.000000 1.000000으로 정확한 값이 나옵니다.
이 문제에서 배우는 것: 부분 피벗팅.
부분 피벗팅. 각 단계에서 그 열의 남은 성분 중 절댓값이 가장 큰 것을 피벗이 되도록 행을 교환한 뒤 소거합니다.
이렇게 하면 소거 계수의 절댓값이 언제나 이하가 되므로 작은 수를 큰 수로 밀어내는 일이 생기지 않습니다.
주의할 점이 있습니다. 수학적으로는 (2)와 (3)이 똑같은 방정식입니다. 해도 같고 소거 결과도 같습니다. 달라지는 것은 오직 부동소수점 계산의 오차이며, 정확한 산술이라면 피벗팅은 필요 없습니다.
| 관점 | 피벗팅이 필요한가 |
|---|---|
| 정확한 산술 | 필요 없습니다 (피벗이 일 때만 교환) |
| 부동소수점 | 거의 언제나 필요합니다 |
이 구별이 중요합니다. 이론에서 나온 알고리즘을 그대로 코드로 옮기면 위와 같이 무너지는 일이 자주 있습니다. 45강의 파국적 상쇄, 47강의 뉴턴법 수렴 조건에 이어 세 번째로 만나는 사례입니다.
이면 이야기가 또 다릅니다. 그때는 피벗이 이므로 교환이 필수이고, 이것은 수치 문제가 아니라 절차의 문제입니다. 문제 1의 절차 1단계가 그 경우를 처리합니다.
이 주제가 90강부터 다시 나옵니다. 조건수로 문제 자체가 얼마나 민감한지를 재고, 알고리즘의 안정성과 문제의 조건을 구별합니다. 위의 예는 문제가 나쁜 것이 아니라 알고리즘이 나빴던 경우이며, 피벗팅으로 고쳐집니다.
바로 확인 5.
확인 5-1. 부분 피벗팅이 무엇인지 쓰세요.
답. 그 열에서 절댓값이 가장 큰 성분이 피벗이 되도록 행을 교환하는 것입니다.
확인 5-2. 피벗팅이 오차를 줄이는 이유를 쓰세요.
답. 소거 계수의 절댓값이 이하가 되어 작은 수가 밀려나지 않기 때문입니다.
확인 5-3. 정확한 산술에서도 피벗팅이 필요합니까?
답. 피벗이 일 때만 교환이 필요하고 그 밖에는 필요하지 않습니다.
| 개념 | 내용 |
|---|---|
| 첨가행렬 | 계수와 상수항을 함께 적은 표 |
| 행 연산 | 교환, 배수(), 덧셈 |
| 행사다리꼴 | 피벗이 오른쪽으로 내려가고 아래가 |
| 전진소거 | 계단 모양을 만듭니다 |
| 후진대입 | 아래에서부터 미지수를 구합니다 |
| 기본행렬 | 에 연산을 한 번 적용한 행렬 |
| 부분 피벗팅 | 절댓값 최대를 피벗으로 |
| 해의 개수 | 판정 |
|---|---|
| 없음 | , |
| 유일 | 모순 행 없고 피벗 수 = 미지수 수 |
| 무수히 | 모순 행 없고 피벗 수 < 미지수 수 |
| 되돌리는 연산 | 짝 |
|---|---|
| R_{i}\leftrightarrow R_ | 자기 자신 |
| R_{i}\to cR_ | R_{i}\to\frac1cR_ |
| R_{i}\to R_{i}+cR_ | R_{i}\to R_{i}-cR_ |
| 자주 하는 실수 | 바로잡기 |
|---|---|
| 상수항을 빼먹습니다 | 첨가행렬로 함께 다룹니다 |
| 아래 행부터 소거합니다 | 위에서부터 순서대로 합니다 |
| 을 곱합니다 | 정보를 잃으므로 금지입니다 |
| 자유변수를 잊습니다 | 피벗 없는 열이 자유변수입니다 |
| 큰 계수로 소거합니다 | 절댓값 최대를 피벗으로 삼습니다 |
문제 6. 을 소거로 푸세요.
답. 둘째에서 첫째의 배를 빼면 이고 입니다.
문제 7. 첨가행렬이 무엇인지 쓰세요.
답. 계수행렬 오른쪽에 상수항을 붙여 함께 적은 행렬입니다.
문제 8. 의 해를 판정하세요.
답. 둘째 행이 이므로 해가 없습니다.
문제 9. 에서 자유변수를 찾으세요.
답. 피벗이 첫 열과 셋째 열에 있으므로 둘째 미지수가 자유변수입니다.
문제 10. 문제 9의 해를 매개변수로 쓰세요.
답. 로 두면 이고 이므로 입니다.
문제 11. 의 기본행렬을 쓰세요.
답. 입니다.
문제 12. 문제 11의 역행렬을 쓰세요.
답. 입니다.
문제 13. 행 연산이 해집합을 보존하는 이유를 한 문장으로 쓰세요.
답. 세 연산 모두 같은 종류의 연산으로 되돌릴 수 있기 때문입니다.
문제 14. 미지수 개, 피벗 개, 모순 행 없음일 때 자유변수의 개수를 쓰세요.
답. 개입니다.
문제 15. 부분 피벗팅을 쓰면 소거 계수의 크기가 어떻게 됩니까?
답. 절댓값이 언제나 이하가 됩니다.
문제 16. 방정식이 미지수보다 적으면 해가 유일할 수 있습니까?
답. 없습니다. 피벗 수가 미지수 수보다 작으므로 해가 없거나 무수히 많습니다.
문제 17. 에서 를 나타내세요.
답. 입니다.
문제 18. 세 평면이 해를 갖지 않는 경우를 하나 설명하세요.
답. 두 평면이 평행하고 겹치지 않으면 공통점이 없습니다.
심화 1. 가우스 소거법의 계산량을 세고 이 클 때의 주도항을 구하세요.
풀이. 계수행렬을 소거합니다. 번째 단계에서 피벗 아래에 개의 행이 있고, 각 행마다 소거 계수를 구하는 나눗셈 번과 오른쪽 성분을 갱신하는 곱셈 번이 필요합니다.
로 두고 곱셈과 나눗셈의 횟수를 셉니다.
전개하면 주도항이 입니다. 검산에서 확인합니다.
| 정확한 횟수 | ||
|---|---|---|
이 커질수록 비율이 에 가까워집니다.
후진대입은 훨씬 쌉니다. 번째 미지수를 구할 때 곱셈이 번이므로 합이 약 이며, 에 비하면 무시할 수 있습니다.
이 값의 실용적 의미를 봅니다.
| 연산 횟수 | 초당 회로 | |
|---|---|---|
| 10^ | 3\times10^ | 초 |
| 10^ | 3\times10^ | 분 |
| 10^ | 3\times10^ | 일 |
이 배가 되면 시간이 배입니다. 그래서 큰 문제에서는 직접 소거를 쓰지 않고 반복법을 씁니다. 심화 5에서 희소성을 이용하는 방법을 보고, 208강 이후 대규모 최적화에서 반복법이 나옵니다.
심화 2. 소거의 각 단계를 기하로 해석하세요.
풀이. 세 미지수의 방정식 하나는 평면 하나입니다. 소거는 그 평면들을 다루는 조작입니다.
덧셈 연산이 하는 일을 봅니다. 은 두 평면 를 과 새 평면 로 바꿉니다. 그런데
이고, 의 점은 과 를 모두 만족하므로 에도 있습니다. 교선은 그대로 두고 평면 하나만 그 교선을 축으로 돌린 것입니다.
소거의 목적은 그렇게 돌려서 평면을 좌표축에 맞추는 것입니다. 최종 형태에서 셋째 방정식은 만 담고 있으므로 평면에 평행한 평면이고, 둘째는 만 담으므로 축에 평행합니다. 점점 단순한 자세로 정렬됩니다.
세 가지 결말도 기하로 읽힙니다.
| 결말 | 세 평면의 배치 |
|---|---|
| 유일한 해 | 한 점에서 만납니다 |
| 무수히 많음(자유변수 1) | 공통 직선을 가집니다 |
| 무수히 많음(자유변수 2) | 세 평면이 모두 같습니다 |
| 해 없음 | 평행하거나, 셋이 삼각기둥을 이룹니다 |
마지막 줄의 둘째 경우가 흥미롭습니다. 세 평면이 서로 다 만나는데 두 개씩 만든 교선 셋이 평행해서 공통점이 없는 배치입니다. 어느 두 평면도 평행하지 않은데 해가 없습니다.
기하적 직관은 까지만 그려지고 그 이상에서는 쓸 수 없습니다. 소거법의 가치가 여기 있습니다. 절차는 차원과 무관하게 작동하므로, 그림을 그릴 수 없는 곳에서도 답을 줍니다. 74강에서 이 상황을 부분공간의 언어로 정리합니다.
심화 3. 크라메르 공식과 소거법을 비교하고 왜 소거법을 쓰는지 밝히세요.
풀이. 크라메르 공식은 의 해를 행렬식으로 줍니다.
여기서 는 의 번째 열을 로 바꾼 행렬입니다. 78강에서 행렬식을 배운 뒤 증명합니다.
공식이 아름답지만 계산에는 쓰이지 않습니다. 이유가 셋입니다.
첫째, 계산량입니다. 행렬식을 정의대로 계산하면 개의 항이 나옵니다. 소거로 행렬식을 구하더라도 개의 행렬식이 필요하므로 소거법을 번 하는 셈입니다.
| 방법 | 계산량 |
|---|---|
| 소거법 | |
| 크라메르(소거로 행렬식) | 약 |
| 크라메르(정의대로) |
이면 셋째 줄은 을 넘습니다.
둘째, 수치 안정성입니다. 행렬식은 가 에 가까울 때 나눗셈이 위험하고, 큰 행렬에서는 행렬식 자체가 넘침이나 밑넘침을 일으킵니다. 이고 성분이 정도면 행렬식이 규모가 될 수 있습니다.
셋째, 정보량입니다. 크라메르는 일 때만 쓸 수 있고, 해가 없거나 무수히 많은 경우에는 아무것도 말해 주지 않습니다. 소거법은 세 경우를 모두 판정합니다.
그러면 크라메르 공식은 무엇에 쓰입니까. 이론적 도구입니다. 해를 성분으로 명시했으므로 해가 계수에 어떻게 의존하는지 미분할 수 있고, 성분이 정수면 해가 유리수임이 즉시 보입니다. 78강에서 그 용도를 봅니다.
공식이 있다고 그것으로 계산해야 하는 것은 아니라는 점이 이 문제의 교훈입니다. 47강에서 근의 공식보다 뉴턴법이 실용적이었던 것과 같은 구조입니다.
심화 4. 행 교환이 필요한 경우와 그것이 LU 분해에 미치는 영향을 논하세요.
풀이. 문제 4에서 를 얻었고, 행 교환이 없으면 가 된다고 했습니다. 교환이 있으면 무엇이 달라지는지 봅니다.
왜 이 아래삼각행렬이 되는가. 교환 없는 소거에서 쓰는 연산은 이고 언제나 입니다. 아래 행에서 위 행의 배수를 빼기 때문입니다. 그 기본행렬은
이므로 대각 아래에만 성분이 붙습니다. 아래삼각행렬끼리의 곱과 역행렬도 아래삼각이므로 이 아래삼각입니다.
교환이 끼면 이 구조가 깨집니다. 교환행렬은 대각 아래위에 모두 성분이 있어 삼각이 아닙니다.
해결은 교환을 미리 몰아서 하는 것입니다. 어떤 순서로 행을 바꿀지 미리 알고 있다면, 그 교환들을 모아 순열행렬 로 만들고 에 대해 소거하면 교환 없이 진행됩니다.
모든 정사각행렬에 대해 이런 가 존재합니다. 부분 피벗팅을 하면서 교환 기록을 남기면 그것이 입니다.
의 성질도 간단합니다. 각 행과 각 열에 이 하나씩 있고 나머지가 이며, 입니다. 순열행렬은 직교행렬이며 80강에서 그 뜻이 분명해집니다.
정리합니다.
| 상황 | 분해 |
|---|---|
| 교환 없음 | |
| 교환 있음 | |
| 대칭이고 양정치 | (콜레스키) |
셋째 줄이 87강에서 나옵니다. 대칭성을 이용하면 계산량이 절반인 으로 줄어듭니다.
실무 라이브러리는 언제나 를 씁니다. 부분 피벗팅이 기본이므로 교환이 늘 일어나기 때문입니다.
심화 5. 희소 행렬에서 소거의 문제점을 설명하고 대응책을 논하세요.
풀이. 성분 대부분이 인 행렬을 희소 행렬이라 합니다. 격자 위의 미분방정식, 그래프의 인접행렬, 추천 시스템의 평점 행렬이 모두 그렇습니다.
희소하면 저장과 곱셈이 싸집니다. 이 아닌 성분만 저장하고 그것만 계산하면 됩니다. 이고 행마다 아닌 성분이 개면 저장이 이며, 조밀하게 저장했을 때의 에 비해 압도적으로 작습니다.
그런데 소거를 하면 희소성이 깨집니다. 에서 에 아닌 성분이 있는 자리는 에서 이었더라도 이 아니게 됩니다.
이 예는 온건하지만, 첫 행이 빽빽하면 아래 행이 모두 빽빽해집니다. 이렇게 새로 생기는 아닌 성분을 채움이라 합니다.
대응책이 여럿입니다.
| 대책 | 내용 |
|---|---|
| 재배열 | 채움이 적게 생기도록 행과 열의 순서를 바꿉니다 |
| 반복법 | 소거를 아예 하지 않고 근사해에 다가갑니다 |
| 불완전 분해 | 채움을 일부러 버리고 전처리로만 씁니다 |
첫째 줄이 미묘합니다. 재배열은 채움을 줄이지만 부분 피벗팅과 충돌합니다. 안정성을 위해서는 큰 성분을 피벗으로 써야 하는데, 희소성을 위해서는 채움이 적은 성분을 써야 합니다. 두 요구가 대립하므로 절충합니다.
둘째 줄이 대규모 문제의 표준입니다. 켤레기울기법 같은 반복법은 행렬을 벡터에 곱하는 연산만 쓰므로 희소성이 그대로 유지되고, 정확한 해 대신 충분히 가까운 근사해를 얻습니다. 208강 이후 최적화에서 다시 나옵니다.
소거법이 만능이 아니라는 점이 이 문제의 교훈입니다. 이 수천 이하이고 조밀하면 소거가 최선이지만, 그 밖에서는 다른 도구가 필요합니다.
심화 6. 소거 과정에서 피벗이 에 가까울 때 무엇이 위험한지 조건수와 구별해 논하세요.
풀이. 문제 5에서 피벗이 작으면 계산이 무너지는 것을 보았고 피벗팅으로 고쳤습니다. 그런데 피벗팅으로 고쳐지지 않는 경우도 있습니다. 둘을 구별해야 합니다.
첫째 경우는 알고리즘의 문제입니다. 문제 5의 예에서 방정식 자체는 멀쩡했습니다. 두 평면이 거의 수직으로 만나므로 교점이 뚜렷하고, 계수를 조금 바꿔도 해가 조금만 움직입니다. 문제는 좋은데 푸는 방법이 나빴을 뿐이며 행을 바꾸니 해결됐습니다.
둘째 경우는 문제 자체가 나쁩니다. 다음을 봅니다.
해는 입니다. 그런데 오른쪽 상수항을 에서 로 아주 조금 바꾸면 해가 로 크게 움직입니다. 두 직선이 거의 평행하기 때문입니다.
이 경우는 어떤 알고리즘을 써도 정확한 답을 얻을 수 없습니다. 입력의 작은 오차가 출력의 큰 오차로 증폭되는 것이 문제의 성질이기 때문입니다.
두 경우를 구별하는 이름이 있습니다.
| 개념 | 무엇의 성질인가 | 고칠 수 있는가 |
|---|---|---|
| 안정성 | 알고리즘 | 고칠 수 있습니다 (피벗팅) |
| 조건 | 문제 | 고칠 수 없습니다 |
이 구별이 수치해석의 근본입니다. 계산이 이상하면 먼저 물어야 합니다. 알고리즘을 바꿔서 나아지는가, 아니면 문제 자체가 민감한가.
조건이 나쁜 정도를 재는 양이 조건수이며 91강에서 정의합니다. 미리 말하면 의 조건수는 최대 특이값과 최소 특이값의 비이고, 위의 예에서 그 값이 약 입니다. 해의 상대오차가 입력의 상대오차의 그만큼까지 커질 수 있다는 뜻입니다.
조건이 나쁜 문제를 만나면 할 수 있는 일이 있습니다.
| 대응 | 내용 |
|---|---|
| 재정식화 | 같은 것을 묻는 다른 식을 세웁니다 |
| 정칙화 | 해에 제약을 걸어 민감도를 낮춥니다 |
| 정밀도 상향 | 자릿수를 늘려 시간을 벌어 봅니다 |
둘째 줄이 82강의 능형회귀이며 233강의 가중치 감쇠와 같은 발상입니다. 데이터가 결정하지 못하는 방향을 사람이 정해 주는 것입니다.
이 강의에서는 numpy만 씁니다. 소거 절차를 직접 구현해 손계산과 맞춰 보고, 부분 피벗팅의 효과를 눈으로 확인하는 것이 목적입니다. np.linalg.solve는 답만 주므로 절차 확인에는 쓰지 않고 대조용으로만 씁니다.
import numpy as np
def elim(M):
"""가우스 소거로 행사다리꼴을 만들고 (U, 교환횟수, 피벗열)을 돌려줍니다."""
U = M.astype(float).copy()
m, n = U.shape
r, swaps, piv = 0, 0, []
for c in range(n):
k = None
for i in range(r, m):
if abs(U[i, c]) > 1e-12: k = i; break
if k is None: continue
if k != r: U[[r, k]] = U[[k, r]]; swaps += 1
for i in range(r+1, m):
U[i] -= (U[i, c]/U[r, c]) * U[r]
piv.append(c); r += 1
if r == m: break
return U, swaps, piv
# --- 문제 1: 유일해 -----------------------------------------------------
A1 = np.array([[1.,2.,1.],[2.,5.,3.],[1.,3.,4.]]); b1 = np.array([6.,17.,20.])
U1,_,p1 = elim(np.column_stack([A1,b1]))
print(np.round(U1,10).tolist(), p1)
# [[1.0, 2.0, 1.0, 6.0], [0.0, 1.0, 1.0, 5.0], [0.0, 0.0, 2.0, 9.0]] [0, 1, 2]
x1 = np.linalg.solve(A1,b1); print(np.round(x1,10).tolist()) # [0.5, 0.5, 4.5]
print(np.allclose(A1@x1, b1)) # True
# --- 문제 3: 해 없음 ----------------------------------------------------
A2 = np.array([[1.,1.,1.],[2.,2.,2.],[1.,0.,1.]]); b2 = np.array([1.,3.,0.])
U2,_,p2 = elim(np.column_stack([A2,b2]))
print(np.round(U2,10).tolist(), p2)
# [[1.0, 1.0, 1.0, 1.0], [0.0, -1.0, 0.0, -1.0], [0.0, 0.0, 0.0, 1.0]] [0, 1, 3]
# 마지막 행이 0 = 1 이므로 해가 없습니다 (피벗이 상수항 열에 섰습니다)
# --- 문제 3: 해가 무수히 많음 -------------------------------------------
A3 = np.array([[1.,1.,1.],[2.,2.,2.],[1.,0.,1.]]); b3 = np.array([1.,2.,0.])
U3,_,p3 = elim(np.column_stack([A3,b3]))
print(np.round(U3,10).tolist(), p3)
# [[1.0, 1.0, 1.0, 1.0], [0.0, -1.0, 0.0, -1.0], [0.0, 0.0, 0.0, 0.0]] [0, 1]
for t in [0., 1., -2.5]:
print(t, np.round(A3 @ np.array([-t, 1.0, t]), 10).tolist())
# 0.0 [1.0, 2.0, 0.0]
# 1.0 [1.0, 2.0, 0.0]
# -2.5 [1.0, 2.0, 0.0]
# --- 문제 4: 행 연산이 곧 행렬 곱 ---------------------------------------
A = np.array([[2.,1.],[6.,5.]])
print((np.array([[1.,0.],[-3.,1.]]) @ A).tolist()) # [[2.0, 1.0], [0.0, 2.0]]
print((np.array([[0.,1.],[1.,0.]]) @ A).tolist()) # [[6.0, 5.0], [2.0, 1.0]]
print((np.array([[0.5,0.],[0.,1.]]) @ A).tolist()) # [[1.0, 0.5], [6.0, 5.0]]
# --- 문제 5: 부분 피벗팅이 필요한 이유 ----------------------------------
eps = 1e-18
M = np.array([[eps, 1.0],[1.0, 1.0]]); rhs = np.array([1.0, 2.0])
f = M[1,0]/M[0,0] # 소거 계수가 1e18
u11 = M[1,1] - f*M[0,1]; r1 = rhs[1] - f*rhs[0]
y = r1/u11; x = (rhs[0] - M[0,1]*y)/M[0,0]
print("%.6f %.6f" % (x, y)) # 0.000000 1.000000 (x가 완전히 틀렸습니다)
M2 = M[[1,0]]; r2 = rhs[[1,0]] # 행을 바꾸면 소거 계수가 1e-18
f2 = M2[1,0]/M2[0,0]
u = M2[1,1] - f2*M2[0,1]; rr = r2[1] - f2*r2[0]
y2 = rr/u; x2 = (r2[0] - M2[0,1]*y2)/M2[0,0]
print("%.6f %.6f" % (x2, y2)) # 1.000000 1.000000
ex = np.linalg.solve(np.array([[1e-18,1.],[1.,1.]]), np.array([1.,2.]))
print("%.6f %.6f" % (ex[0], ex[1])) # 1.000000 1.000000
# --- 심화 1: 계산량이 n^3/3에 가까워집니다 ------------------------------
for n in [3, 10, 100]:
print(n, sum(j*(j+1) for j in range(1, n)), round(n**3/3))
# 3 8 9
# 10 330 333
# 100 333300 333333
실행하면 주석과 같은 값이 나옵니다. 다섯 곳을 짚어 둡니다.
첫째, 문제 1의 손계산과 코드의 행사다리꼴이 정확히 같습니다. 마지막 행이 이므로 이고, 대조용 해가 입니다.
둘째, 해가 없는 경우의 신호가 분명합니다. 피벗 열 목록이 [0, 1, 3]인데 번 열은 상수항 열입니다. 상수항 열에 피벗이 서면 그 행이 꼴이라는 뜻이므로 해가 없습니다. 피벗 열 목록만 보고도 판정할 수 있습니다.
셋째, 해가 무수히 많은 경우입니다. 피벗 열이 [0, 1]이므로 셋째 미지수가 자유변수이고, 어느 값을 넣어도 가 으로 원래 상수항과 같습니다. 매개변수 표현이 실제로 해집합 전체입니다.
넷째, 세 가지 행 연산이 모두 왼쪽 곱으로 재현됩니다. 특히 첫 줄에서 가 소거 결과와 같습니다.
다섯째가 이 강의의 핵심 경고입니다. 수학적으로 동일한 두 계산이 완전히 다른 답을 줍니다. 피벗 없이 하면 이고 행을 바꾸면 인데, 참값은 입니다. 종이 위에서는 구별할 수 없는 차이가 부동소수점에서는 답을 통째로 바꿉니다.
심화 1의 계산량도 확인됩니다. 에서 대 으로 차이입니다.
코드로 할 수 없는 일도 분명히 해 둡니다. 행 연산이 해집합을 보존한다는 것은 몇 개의 예로 확인할 수 없습니다. 문제 2의 증명이 그 자리를 맡습니다. 코드가 하는 일은 절차가 손계산과 맞는지, 그리고 부동소수점에서 무슨 일이 벌어지는지를 보여 주는 것입니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 첨가행렬 | 계수와 상수항을 함께 적습니다 | |
| R_{i}\leftrightarrow R_ | 행 교환 | 두 행을 맞바꿉니다 |
| R_{i}\to cR_ | 행 배수 | 이어야 합니다 |
| R_{i}\to R_{i}+cR_ | 행 덧셈 | 다른 행의 배수를 더합니다 |
| 피벗 | pivot | 각 행에서 처음 나오는 아닌 성분입니다 |
| 위삼각 | 소거의 결과입니다 | |
| 기본행렬 | 행 연산 하나를 수행합니다 | |
| 순열행렬 | 행 교환을 모은 것입니다 | |
| 채움 | fill-in | 소거 중 새로 생기는 아닌 성분입니다 |
다음 68강에서는 소거를 끝까지 밀어붙입니다. 지금은 피벗 아래만 으로 만들었는데 위쪽도 으로 만들고 피벗을 로 맞추면 후진대입조차 필요 없어집니다. 그 모양을 기약행사다리꼴이라 하며, 그것이 유일하게 정해진다는 사실이 해집합의 구조를 완전히 드러냅니다.