69강에서 를 계산하지 말라고 했습니다. 대신 소거로 풀라고 했는데, 그러면 이런 상황이 걸립니다.
같은 에 상수항만 바뀐 문제를 백 번 풀어야 하면 어떻게 합니까.
실제로 흔합니다. 구조물에 하중을 여러 조건으로 걸어 보거나, 회로에 입력을 바꿔 넣거나, 시뮬레이션에서 시간 단계마다 같은 계수로 푸는 경우가 그렇습니다.
매번 처음부터 소거하면 을 백 번 치릅니다. 그런데 생각해 보면 소거 과정이 매번 똑같습니다. 상수항은 그 과정에 끌려다닐 뿐 소거 계수를 바꾸지 않습니다.
그렇다면 소거를 한 번만 하고 그 결과를 저장해 두면 됩니다. 무엇을 저장해야 합니까. 답은 67강 문제 4에 이미 있었습니다.
이 강의는 그 이 무엇인지 밝히고, 저장하는 방법과 다시 쓰는 방법을 세웁니다. 그리고 02단원을 닫습니다.
문제. 을 소거합니다.
(1) 행 교환 없이 위삼각행렬 를 만드세요. 쓴 소거 계수를 모두 적으세요.
(2) 그 계수들로 을 만들고 를 계산하세요.
(3) 무엇이 관찰됩니까?
생각의 실마리. (2)에서 소거 계수를 쓴 자리에 그대로 넣어 봅니다. 에서 쓴 를 의 성분에 두는 것입니다. 대각은 로 채웁니다.
풀이. (1) 첫 열을 소거합니다. 이고 입니다.
둘째 열을 소거합니다. 입니다.
쓴 계수는 , , 입니다.
(2) 그 자리에 넣고 대각을 로 채웁니다.
곱하면
(3) 소거 계수를 모아 놓기만 했는데 가 복원됩니다.
이 문제에서 배우는 것: LU 분해.
LU 분해. 행 교환 없이 소거가 되는 행렬은
로 쓸 수 있습니다. 는 소거 결과인 위삼각행렬이고, 은 대각이 이고 아래에 소거 계수 가 든 아래삼각행렬입니다.
왜 소거 계수가 그대로 이 되는지 봅니다. 67강 문제 4에서 각 소거가 기본행렬이었습니다.
그 역행렬은 부호만 바꾼 것입니다.
그리고 인데, 소거 순서대로 곱하면 서로 간섭하지 않아 성분이 그대로 남습니다. 심화 1에서 그 이유를 정확히 봅니다.
저장에 필요한 공간도 눈여겨보십시오. 의 대각은 언제나 이고 위쪽은 이며, 의 아래쪽은 입니다. 둘을 한 배열에 겹쳐 담을 수 있습니다.
네모 친 자리가 의 소거 계수이고 나머지가 입니다. 추가 메모리가 필요 없으며, 실제 라이브러리가 이렇게 저장합니다.
바로 확인 1.
확인 1-1. 의 대각 성분은 무엇입니까?
답. 모두 입니다.
확인 1-2. 의 성분이 뜻하는 것을 쓰세요.
답. 셋째 행에서 첫째 행의 몇 배를 뺐는지, 즉 소거 계수입니다.
확인 1-3. 과 를 한 배열에 담을 수 있는 이유를 쓰세요.
답. 의 위쪽과 대각이 정해져 있고 의 아래쪽이 이라 자리가 겹치지 않습니다.
문제. 문제 1의 에 대해 을 풉니다.
(1) 를 두 단계로 나누세요.
(2) 각 단계를 계산하세요.
(3) 각 단계의 계산량을 세세요.
생각의 실마리. 에서 를 하나의 미지 벡터로 봅니다. 그것을 먼저 구하고, 그다음 그것에서 를 구합니다.
풀이. (1) 로 두면
(2) 첫 단계는 이 아래삼각이므로 위에서 아래로 내려가며 풉니다.
둘째 단계는 가 위삼각이므로 아래에서 위로 올라갑니다.
검산에서 가 확인됩니다.
(3) 각 대입에서 번째 성분을 구할 때 곱셈이 번 또는 번이므로 합이 약 입니다. 두 단계를 합쳐 입니다.
이 문제에서 배우는 것: 전진대입과 후진대입.
두 단계 풀이.
단계 식 방향 계산량 전진대입 L\mathbf{y}=\mathbf 위 → 아래 후진대입 U\mathbf{x}=\mathbf 아래 → 위
삼각행렬이 왜 쉬운지가 핵심입니다. 첫 방정식에 미지수가 하나뿐이므로 즉시 풀리고, 그것을 알면 둘째 방정식에도 미지수가 하나만 남습니다. 연쇄적으로 풀립니다.
의 정체도 짚어 둡니다. 이므로, 이것은 상수항에 소거 연산을 적용한 결과입니다. 67강에서 첨가행렬을 소거할 때 상수항 열이 변해 가던 그 값과 같습니다.
실제로 문제 1의 소거를 상수항 에 적용해 보면
로 가 나옵니다. LU 분해는 그 과정을 미리 해 두고 에 기록해 둔 것입니다.
바로 확인 2.
확인 2-1. 를 두 단계로 쓰세요.
답. 를 풀고 를 풉니다.
확인 2-2. 전진대입의 방향을 쓰세요.
답. 위에서 아래로 내려갑니다.
확인 2-3. 두 대입의 총 계산량을 쓰세요.
답. 약 입니다.
문제. 같은 에 대해 상수항 가 개 주어졌습니다.
(1) 매번 소거하면 계산량이 얼마입니까?
(2) LU를 한 번 하고 재사용하면 얼마입니까?
(3) , 에서 비교하세요.
생각의 실마리. (2)에서 분해는 상수항과 무관하므로 한 번이면 됩니다. 상수항마다 드는 것은 문제 2의 두 대입뿐입니다.
풀이. (1) 소거가 이고 그것을 번 합니다.
(2) 분해 한 번에 , 상수항마다 입니다.
(3) , 을 넣습니다.
| 방법 | 연산 횟수 |
|---|---|
| 매번 소거 | 1.667\times10^ |
| LU 재사용 | 3.833\times10^ |
약 배 차이입니다. 검산에서 세 크기에 대해 확인합니다.
이 문제에서 배우는 것: 분해의 값어치.
원칙. 비싼 계산은 상수항과 무관한 부분에 몰려 있습니다. 그 부분을 한 번만 하고 저장합니다.
이 구조가 반복해서 나타납니다.
| 분해 | 비싼 부분 | 재사용 |
|---|---|---|
| LU | 각 에 n^ | |
| QR (80강) | 최소제곱 문제 | |
| 고유분해 (84강) | 수준 | 거듭제곱, 미분방정식 |
| SVD (88강) | 수준 | 근사, 의사역행렬 |
**"한 번 분해하고 여러 번 쓴다"**가 수치선형대수의 기본 전략이며, 이 강의가 그 첫 사례입니다.
검산에서 상수항 세 개에 대해 같은 로 풀어 모두 맞는 것을 확인합니다. 분해는 손대지 않고 대입만 세 번 했습니다.
69강과 이어서 정리합니다.
| 목적 | 하지 말 것 | 할 것 |
|---|---|---|
| 하나 | A^{-1}\mathbf | 소거 |
| 여러 개 | 계산 | LU 재사용 |
| 여인수 전개 | LU의 대각 곱 (심화 2) |
셋째 줄이 새로 추가되었습니다. 78강에서 행렬식을 배우면 정의대로 계산하고 싶어지는데, 실제로는 언제나 LU를 씁니다.
바로 확인 3.
확인 3-1. LU 분해가 상수항과 무관한 이유를 쓰세요.
답. 소거 계수가 계수행렬만으로 정해지기 때문입니다.
확인 3-2. 가 개일 때 LU 방식의 계산량을 쓰세요.
답. 입니다.
확인 3-3. 가 클수록 이득이 커지는 이유를 쓰세요.
답. 추가 비용이 이 아니라 이기 때문입니다.
문제. 을 봅니다.
(1) 행 교환 없이 LU 분해가 됩니까?
(2) 는 가역입니까?
(3) 어떻게 고칩니까?
생각의 실마리. (1)에서 첫 피벗이 이므로 나눗셈이 불가능합니다. (2)와 대비되는 점이 중요합니다. 가역인데도 LU가 안 되는 것이므로, 이는 행렬의 결함이 아니라 분해 형식의 한계입니다.
풀이. (1) 되지 않습니다. 이 정의되지 않습니다.
(2) 가역입니다. 이고 실제로 입니다.
(3) 행을 바꾸면 됩니다.
이고 이므로 입니다. 검산에서 가 확인됩니다.
이 문제에서 배우는 것: .
순열 있는 LU 분해. 모든 정사각행렬 에 대해 순열행렬 가 존재해
가 성립합니다.
는 소거 중에 한 행 교환들을 모은 것이며, 67강 심화 4에서 예고한 대로입니다.
교환은 특이한 경우에만 필요한 것이 아닙니다. 67강 문제 5에서 본 대로 부분 피벗팅을 위해 늘 교환합니다. 실무 라이브러리는 언제나 를 계산하며, 순열은 정수 배열 하나로 저장하므로 비용이 거의 없습니다.
풀이 절차도 조금 바뀝니다.
상수항의 성분 순서를 대로 바꾼 뒤 두 대입을 하면 됩니다.
가역이면서 LU가 안 되는 다른 예도 봅니다.
첫 열을 소거하면 둘째 행이 이 되어 둘째 피벗이 입니다. 검산에서 교환 없는 분해가 실패하고, 부분 피벗팅을 하면 가 성립합니다.
두 가지를 구별하십시오.
| 상황 | 뜻 |
|---|---|
| 소거 중 피벗이 | 교환이 필요할 뿐입니다 |
| 교환해도 그 열에 뿐 | 계수가 부족하며 특이합니다 |
전자는 절차의 문제이고 후자는 행렬의 성질입니다. 와 는 전자이며 둘 다 가역입니다.
바로 확인 4.
확인 4-1. 모든 정사각행렬에 성립하는 분해를 쓰세요.
답. 입니다.
확인 4-2. 일 때 를 어떻게 풉니까?
답. 이므로 상수항 순서를 바꾼 뒤 두 대입을 합니다.
확인 4-3. 피벗이 이면 그 행렬은 특이합니까?
답. 아닙니다. 교환하면 되는 경우가 많습니다.
문제. 을 봅니다.
(1) 이 행렬의 특징 두 가지를 말하세요.
(2) 인 아래삼각 를 찾을 수 있습니까?
(3) 이득이 무엇입니까?
생각의 실마리. (1)에서 대칭임은 바로 보입니다. 또 하나는 **모든 에 대해 **인지 확인하는 것인데, 소거해서 피벗이 모두 양수면 그렇습니다.
풀이. (1) 로 대칭이고, 소거하면 피벗이 로 모두 양수입니다. 이런 행렬을 양정치라 합니다.
(2) 있습니다. 를 아래삼각으로 두고 를 성분별로 풀면 위에서부터 차례로 정해집니다.
계속하면
검산에서 가 확인됩니다.
(3) 저장과 계산이 절반입니다. 과 를 따로 두지 않고 하나만 있으면 되고, 계산량이 에서 으로 줄어듭니다.
이 문제에서 배우는 것: 콜레스키 분해.
콜레스키 분해. 가 대칭이고 양정치이면
인 아래삼각행렬 가 유일하게 존재합니다 (대각을 양수로 잡을 때).
LU와 비교합니다.
| LU | 콜레스키 | |
|---|---|---|
| 조건 | 정사각 (교환 허용) | 대칭 양정치 |
| 저장 | 하나 | |
| 계산량 | ||
| 피벗팅 | 필요합니다 | 필요 없습니다 |
넷째 줄이 중요합니다. 양정치이면 소거 중 피벗이 절대 이 되지 않고 크기도 잘 유지되므로, 교환 없이도 수치적으로 안전합니다. 심화 4에서 그 이유를 봅니다.
콜레스키가 실패하면 그것 자체가 정보입니다.
양정치 판정. 콜레스키 분해가 성공하면 양정치이고, 도중에 음수의 제곱근이 필요해지면 양정치가 아닙니다.
이것이 실무의 표준 판정법입니다. 87강에서 고유값으로 판정하는 법을 배우지만, 고유값 계산은 훨씬 비쌉니다.
응용도 많습니다.
| 분야 | 쓰임 |
|---|---|
| 최소제곱 | 가 대칭 양반정치입니다 (82강) |
| 확률 | 공분산 행렬이 대칭 양반정치입니다 |
| 표본 생성 | 상관 있는 정규 난수를 로 만듭니다 |
| 최적화 | 헤세 행렬이 양정치면 극소입니다 |
셋째 줄이 재미있습니다. 표준정규 벡터 에 를 곱하면 공분산이 인 벡터가 됩니다. 원하는 상관 구조를 만드는 표준 방법이며 141강에서 다시 봅니다.
로그행렬식도 안전하게 얻습니다. 69강 심화 6에서 언급한 대로
이며, 검산에서 두 값이 으로 일치합니다. 행렬식을 직접 계산하지 않으므로 넘침이 없습니다.
바로 확인 5.
확인 5-1. 콜레스키 분해의 조건을 쓰세요.
답. 대칭이고 양정치여야 합니다.
확인 5-2. 계산량이 LU의 몇 배입니까?
답. 절반인 입니다.
확인 5-3. 콜레스키가 실패하면 무엇을 알 수 있습니까?
답. 그 행렬이 양정치가 아닙니다.
| 분해 | 식 | 조건 |
|---|---|---|
| LU | 교환 없이 소거 가능 | |
| PLU | 모든 정사각행렬 | |
| 콜레스키 | S=CC^ | 대칭 양정치 |
| LDU | A=LDU_ | 심화 3 |
| 단계 | 내용 | 계산량 |
|---|---|---|
| 분해 | 소거 한 번 | |
| 전진대입 | L\mathbf{y}=\mathbf | |
| 후진대입 | U\mathbf{x}=\mathbf | |
| 개 상수항 | 합계 | n^{3}/3+kn^ |
| 의 정체 | 내용 |
|---|---|
| 대각 | 모두 |
| 성분 | 소거 계수 f_ |
| 저장 | 와 한 배열에 겹칩니다 |
| 자주 하는 실수 | 바로잡기 |
|---|---|
| 상수항마다 다시 분해합니다 | 분해는 한 번입니다 |
| 를 잊습니다 | 상수항도 같은 순서로 바꿉니다 |
| 피벗 을 특이로 봅니다 | 교환하면 되는 경우가 많습니다 |
| 대칭인데 LU를 씁니다 | 콜레스키가 절반입니다 |
문제 6. 을 LU 분해하세요.
답. 이므로 , 입니다.
문제 7. 의 대각 성분을 쓰세요.
답. 모두 입니다.
문제 8. 의 성분의 뜻을 쓰세요.
답. 행에서 행의 몇 배를 뺐는지를 나타내는 소거 계수입니다.
문제 9. 이고 일 때 를 구하세요.
답. 이고 입니다.
문제 10. 두 대입의 총 계산량을 쓰세요.
답. 약 입니다.
문제 11. 상수항이 개일 때 LU 방식의 총 계산량을 쓰세요.
답. 입니다.
문제 12. 모든 정사각행렬에 성립하는 분해를 쓰세요.
답. 입니다.
문제 13. 일 때 상수항을 어떻게 다룹니까?
답. 로 순서를 바꾼 뒤 두 대입을 합니다.
문제 14. 순열행렬의 역행렬을 쓰세요.
답. 입니다.
문제 15. 콜레스키 분해의 조건과 계산량을 쓰세요.
답. 대칭 양정치이며 입니다.
문제 16. 콜레스키에 피벗팅이 필요 없는 이유를 한 문장으로 쓰세요.
답. 양정치이면 피벗이 이 되지 않고 크기가 잘 유지되기 때문입니다.
문제 17. 를 콜레스키로 계산하는 식을 쓰세요.
답. 입니다.
문제 18. 삼각행렬의 방정식이 쉬운 이유를 쓰세요.
답. 미지수가 하나씩 차례로 결정되기 때문입니다.
심화 1. 소거 계수가 그대로 이 되는 이유를 정확히 밝히세요.
풀이. 소거 하나의 기본행렬과 그 역을 봅니다.
역이 저 모양인 것은 직접 곱해 보면 압니다.
**이므로 **이고 마지막 항이 사라집니다.
이제 을 계산합니다. 두 개를 곱해 봅니다.
마지막 항이 남으려면 여야 합니다.
소거 순서를 보면 그런 일이 없습니다. 열 를 처리할 때 쓰는 연산들은 모두 이고 입니다. 그다음 열 로 넘어가면 이므로 이며 절대 같지 않습니다. 같은 열 안에서도 이고 이므로 입니다.
따라서 교차항이 언제나 이고
이 됩니다. 이것이 곧 "소거 계수를 제자리에 넣는다"는 규칙입니다.
순서가 결정적임을 강조해 둡니다. 곱하는 순서를 바꾸면 교차항이 살아나 이 성질이 깨집니다. 의 순서, 즉 소거한 순서 그대로여야 합니다.
이 결과가 주는 실용적 이득이 큽니다. 을 따로 계산할 필요가 없습니다. 소거하면서 계수를 버리지 않고 이 된 자리에 적어 두면 그것이 입니다.
심화 2. LU 분해로 행렬식을 계산하는 방법을 유도하세요.
풀이. 78강에서 행렬식을 정식으로 다루지만, 두 가지 성질만 미리 씁니다.
| 성질 | 내용 |
|---|---|
| 곱 | |
| 삼각 | 삼각행렬의 행렬식은 대각의 곱입니다 |
이면
입니다. **의 대각이 모두 이므로 **입니다.
검산에서 문제 1의 에 대해 피벗의 곱이 이고 np.linalg.det가 입니다. 부동소수점 오차 정도만 다릅니다.
행 교환이 있으면 부호가 붙습니다. 에서
여기서 는 교환 횟수이고 입니다. 검산의 에서 이고 로 정확히 맞습니다.
이 방법의 가치를 봅니다. 정의대로 계산하면 개의 항이 필요하고, 여인수 전개도 입니다.
| 방법 | 계산량 | |
|---|---|---|
| 정의 | 2.4\times10^ | |
| 여인수 전개 | 같은 수준 | |
| LU |
차이가 압도적입니다. 그래서 모든 라이브러리가 행렬식을 LU로 계산합니다.
넘침 문제도 있습니다. 이고 피벗이 정도면 곱이 이 되어 표현할 수 없습니다. 그래서 행렬식이 아니라 로그행렬식을 구합니다.
부호는 따로 셉니다. 확률 모형의 우도 계산에서 언제나 이 형태를 씁니다.
심화 3. LDU 분해를 세우고 대칭행렬에서 무엇이 특별한지 밝히세요.
풀이. 의 대각을 따로 빼냅니다. 으로 두고 각 행을 그 값으로 나누면
이고 는 대각이 모두 인 위삼각행렬입니다. 따라서
입니다. 과 가 모두 대각이 이고 가 피벗을 담습니다.
이 형태의 이점은 유일성이 깔끔하다는 것입니다. 가 가역이고 교환 없이 분해되면 가 유일하게 정해집니다.
대칭행렬에서 특별한 일이 일어납니다. 이면
인데 왼쪽이 와 같습니다. 이 대각 인 아래삼각이고 이 대각 인 위삼각이므로, 유일성에 의해
입니다. 분해가 절반으로 줄었습니다. 하나와 만 저장하면 됩니다.
여기서 콜레스키가 나옵니다. 의 대각이 모두 양수이면 를 정의할 수 있으므로
입니다. ****이며 문제 5의 분해입니다.
세 분해의 관계를 정리합니다.
| 분해 | 조건 | 형태 |
|---|---|---|
| LDU_ | 일반 | 셋 다 다릅니다 |
| LDL^ | 대칭 | U_{0}=L^ |
| CC^ | 대칭 양정치 |
은 양정치가 아니어도 씁니다. 에 음수가 있어도 되므로, 대칭이지만 부정부호인 행렬에 유용합니다. 최적화에서 안장점 근처의 헤세 행렬이 그런 경우이며, 209강에서 다시 봅니다.
심화 4. 양정치 행렬에서 피벗팅이 필요 없는 이유를 밝히세요.
풀이. 문제 5에서 콜레스키에 피벗팅이 필요 없다고 했습니다. 근거를 봅니다.
주장. 가 대칭 양정치이면 소거 중 모든 피벗이 양수입니다.
첫 피벗. 을 양정치 조건에 넣으면
입니다.
다음 피벗. 첫 열을 소거한 뒤 남는 블록이 무엇인지 봅니다. 로 쓰면 소거 결과의 오른쪽 아래는
이며 69강 심화 3의 슈어 보수입니다.
이 슈어 보수도 대칭 양정치입니다. 임의의 에 대해 로 두고 를 넣으면
입니다. 를 그렇게 고른 것이 바로 제곱 완성이며, 2강에서 배운 조작입니다.
따라서 귀납적으로 모든 피벗이 양수이고, 소거가 절대 멈추지 않습니다.
수치적 안정성도 따라옵니다. 콜레스키에서
이므로 의 성분이 원래 행렬의 대각 성분으로 위에서 눌립니다. 소거 중에 값이 폭발할 수 없으므로 피벗팅 없이도 안전합니다.
일반 LU와 대비됩니다. 67강 문제 5에서 소거 계수가 까지 커졌는데, 그런 일이 양정치에서는 일어나지 않습니다.
| 일반 LU | 콜레스키 | |
|---|---|---|
| 성분 증가 | 제한 없습니다 | 로 제한 |
| 피벗팅 | 필수 | 불필요 |
| 실패 조건 | 특이할 때 | 양정치가 아닐 때 |
셋째 줄이 판정법이 되는 근거입니다. 실패가 곧 정보입니다.
심화 5. 블록 LU 분해를 세우고 슈어 보수와 잇습니다.
풀이. 66강 심화 3의 블록 곱셈으로 소거를 블록 단위로 합니다.
에서 가 가역이라 하고, 둘째 블록행에서 첫째의 배를 뺍니다. 기본행렬에 해당하는 것은
이고 적용하면
입니다. 왼쪽 행렬의 역을 오른쪽으로 넘기면
블록 LU 분해이며 가 슈어 보수입니다.
여기서 즉시 따라오는 결과가 있습니다.
행렬식이 두 조각으로 갈라집니다. 심화 2의 삼각 성질을 블록 버전으로 쓴 것입니다.
이 분해가 쓰이는 곳을 봅니다.
| 분야 | 무엇을 쪼개는가 |
|---|---|
| 영역 분할 | 격자를 나눠 병렬로 풉니다 |
| 제약 최적화 | 변수와 승수를 분리합니다 |
| 가우스 과정 | 관측과 예측 지점을 나눕니다 |
| 그래프 | 부분그래프와 경계를 나눕니다 |
넷째 줄이 흥미롭습니다. 그래프를 두 덩어리와 그 사이의 경계로 나누면 인접행렬이 블록 구조를 갖고, 경계가 작으면 슈어 보수가 작아 계산이 크게 줄어듭니다. 이것이 중첩 분할이며 희소 행렬 소거의 표준 재배열 전략입니다. 67강 심화 5에서 언급한 채움 줄이기가 이렇게 구현됩니다.
계산 순서의 이점도 있습니다. 가 대각 블록들로 이루어져 있으면 을 블록별로 병렬 계산할 수 있고, 슈어 보수만 순차 처리하면 됩니다. 문제의 대부분을 병렬화하고 작은 결합 부분만 남깁니다.
심화 6. LU 분해의 비용을 회계하고 실무에서 무엇을 결정하는지 논하세요.
풀이. 세 가지 자원을 봅니다.
연산. 분해 , 대입 입니다. 개의 상수항이면 이며, 가 을 넘으면 분해 비용이 대입 비용에 묻힙니다.
메모리. 과 를 원본 자리에 겹쳐 쓰면 추가 저장이 없습니다. 순열은 정수 배열 하나입니다. 역행렬을 만들면 별도의 이 필요하고 원본도 남겨야 하므로 두 배입니다.
시간. 실제 시간은 연산 횟수에 비례하지 않습니다. 메모리 접근이 병목이기 때문입니다.
| 요인 | 영향 |
|---|---|
| 캐시 적중 | 블록 알고리즘이 몇 배 빠릅니다 |
| 벡터화 | 연속 접근이 유리합니다 |
| 병렬화 | 블록 단위로 나눕니다 |
그래서 실무 라이브러리는 블록 LU를 씁니다. 심화 5의 블록 분해를 캐시 크기에 맞춰 재귀적으로 적용하며, 같은 연산을 훨씬 빠르게 끝냅니다.
무엇을 결정해야 하는지 정리합니다.
| 질문 | 판단 |
|---|---|
| 상수항이 여러 개인가 | 그러면 반드시 분해를 재사용합니다 |
| 대칭 양정치인가 | 그러면 콜레스키가 절반입니다 |
| 희소한가 | 재배열을 고려하거나 반복법을 씁니다 |
| 조건이 나쁜가 | 정칙화하거나 QR·SVD를 씁니다 |
| 가 자주 바뀌는가 | 계수 갱신이면 셔먼-모리슨입니다 |
마지막 줄이 69강 심화 4와 이어집니다. 가 조금씩 바뀌는 상황에서 매번 분해하면 낭비이므로 갱신 공식을 씁니다. 다만 갱신을 반복하면 오차가 쌓이므로, 일정 횟수마다 다시 분해하는 것이 보통입니다.
이 강의의 결론을 한 문장으로 하면 이렇습니다. 소거는 상수항과 무관한 작업이므로 한 번만 하고 결과를 저장하며, 행렬에 구조가 있으면 그 구조에 맞는 더 싼 분해를 씁니다. 이 원칙이 80강의 QR, 88강의 SVD까지 그대로 이어집니다.
이 강의에서는 numpy만 씁니다. LU 분해와 두 대입을 직접 구현하고, 순열이 필요한 경우와 콜레스키까지 확인합니다. 실행 시간은 환경마다 다르므로 재지 않고, 대신 연산 횟수를 계산해 비교합니다.
import numpy as np
def lu_nopiv(A):
"""행 교환 없이 A = LU. 피벗이 0이면 (None, None)."""
n = A.shape[0]; U = A.astype(float).copy(); L = np.eye(n)
for k in range(n):
if abs(U[k,k]) < 1e-12: return None, None
for i in range(k+1, n):
f = U[i,k]/U[k,k]; L[i,k] = f; U[i] -= f*U[k]
return L, U
def lu_piv(A):
"""부분 피벗팅으로 PA = LU."""
n = A.shape[0]; U = A.astype(float).copy()
L = np.zeros((n,n)); P = np.eye(n)
for k in range(n):
j = k + int(np.argmax(np.abs(U[k:,k])))
if j != k:
U[[k,j]] = U[[j,k]]; P[[k,j]] = P[[j,k]]; L[[k,j]] = L[[j,k]]
for i in range(k+1, n):
f = U[i,k]/U[k,k]; L[i,k] = f; U[i] -= f*U[k]
return P, L + np.eye(n), U
def fsub(L, b): # 전진대입: 위에서 아래로
n = len(b); y = np.zeros(n)
for i in range(n): y[i] = b[i] - L[i,:i] @ y[:i]
return y
def bsub(U, y): # 후진대입: 아래에서 위로
n = len(y); x = np.zeros(n)
for i in range(n-1, -1, -1): x[i] = (y[i] - U[i,i+1:] @ x[i+1:]) / U[i,i]
return x
# --- 문제 1: 소거 계수가 그대로 L이 됩니다 -------------------------------
A = np.array([[2.,1.,1.],[4.,3.,3.],[8.,7.,9.]])
L, U = lu_nopiv(A)
print(L.tolist()) # [[1.0, 0.0, 0.0], [2.0, 1.0, 0.0], [4.0, 3.0, 1.0]]
print(U.tolist()) # [[2.0, 1.0, 1.0], [0.0, 1.0, 1.0], [0.0, 0.0, 2.0]]
print(bool(np.allclose(L@U, A))) # True
# --- 문제 2: 두 번의 대입 -----------------------------------------------
b = np.array([4.,10.,26.])
y = fsub(L, b); x = bsub(U, y)
print(y.tolist(), x.tolist(), bool(np.allclose(A@x, b)))
# [4.0, 2.0, 4.0] [1.0, 0.0, 2.0] True
# --- 문제 3: 상수항이 바뀌어도 L, U는 그대로 ----------------------------
for bb in [np.array([1.,0.,0.]), np.array([0.,1.,0.]), np.array([3.,7.,19.])]:
xx = bsub(U, fsub(L, bb))
print(np.round(xx,10).tolist(), bool(np.allclose(A@xx, bb)))
# [1.5, -3.0, 1.0] True
# [-0.5, 2.5, -1.5] True
# [1.0, -1.0, 2.0] True
# --- 문제 4: 가역인데도 교환 없는 LU가 실패합니다 ------------------------
Z = np.array([[0.,1.],[1.,0.]])
print(lu_nopiv(Z)[0] is None) # True
P, Lz, Uz = lu_piv(Z)
print(P.tolist(), Lz.tolist(), Uz.tolist(), bool(np.allclose(P@Z, Lz@Uz)))
# [[0.0, 1.0], [1.0, 0.0]] [[1.0, 0.0], [0.0, 1.0]] [[1.0, 0.0], [0.0, 1.0]] True
W = np.array([[1.,2.,3.],[2.,4.,7.],[3.,5.,3.]]) # 둘째 피벗이 0이 됩니다
print(lu_nopiv(W)[0] is None) # True
Pw, Lw, Uw = lu_piv(W)
print(bool(np.allclose(Pw@W, Lw@Uw)), np.round(np.diag(Uw),10).tolist())
# True [3.0, 0.6666666667, -0.5]
# --- 문제 5: 대칭 양정치이면 콜레스키 -----------------------------------
S = np.array([[4.,2.,-2.],[2.,5.,1.],[-2.,1.,6.]])
C = np.linalg.cholesky(S)
print(C.tolist(), bool(np.allclose(C@C.T, S)))
# [[2.0, 0.0, 0.0], [1.0, 2.0, 0.0], [-1.0, 1.0, 2.0]] True
print("%.6f" % float(2*np.sum(np.log(np.diag(C)))),
"%.6f" % float(np.log(np.linalg.det(S)))) # 4.158883 4.158883
# --- 심화 2: 행렬식은 피벗의 곱 (교환이 있으면 부호가 붙습니다) ---------
print(float(np.prod(np.diag(U))), float(np.linalg.det(A)))
# 4.0 4.000000000000001
sign = float(np.linalg.det(Pw))
print(sign, "%.10f" % float(sign*np.prod(np.diag(Uw))),
"%.10f" % float(np.linalg.det(W)))
# -1.0 1.0000000000 1.0000000000
# --- 문제 3: 연산 횟수로 비교합니다 (상수항 50개) -----------------------
for n in [100, 500, 1000]:
k = 50
print(n, "%.3e" % (k*n**3/3), "%.3e" % (n**3/3 + k*n**2))
# 100 1.667e+07 8.333e+05
# 500 2.083e+09 5.417e+07
# 1000 1.667e+10 3.833e+08
실행하면 주석과 같은 값이 나옵니다. 다섯 곳을 짚어 둡니다.
첫째, 의 성분이 손으로 계산한 소거 계수 과 정확히 같습니다. 계수를 버리지 않고 제자리에 적어 두기만 하면 이 됩니다.
둘째, 두 대입이 답을 줍니다. 중간값 가 상수항에 소거를 적용한 결과이며, 67강에서 첨가행렬의 상수항 열이 변해 가던 값과 같습니다.
셋째가 이 강의의 요점입니다. 상수항 세 개를 서로 다른 값으로 바꿔 풀었는데 과 는 손대지 않았습니다. 분해가 상수항과 무관하다는 사실이 눈에 보입니다.
넷째, 와 가 모두 가역인데 교환 없는 LU가 실패합니다. 는 첫 열을 소거하면 둘째 행이 이 되어 둘째 피벗이 입니다. 피벗팅을 넣으면 가 성립하고, 을 곱해 이 정확히 나옵니다.
다섯째, 콜레스키가 로 깔끔하게 나오고, 로그행렬식 두 계산이 으로 일치합니다.
계산량 비교에서 , 이면 대 로 약 배입니다.
코드로 할 수 없는 일도 분명히 해 둡니다. 실행 시간은 재지 않았습니다. 같은 코드도 기계와 부하에 따라 다르게 나오므로 재현되지 않는 수치이며, 심화 6에서 본 대로 실제 시간은 연산 횟수보다 메모리 접근에 좌우됩니다. 여기서 확인한 것은 알고리즘의 연산 횟수이고, 그것은 결정적입니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 아래삼각 | 대각이 이고 소거 계수를 담습니다 | |
| 위삼각 | 소거 결과입니다 | |
| 순열행렬 | 행 교환을 모은 것입니다 | |
| 대각행렬 | 피벗을 담습니다 | |
| 콜레스키 인자 | 입니다 | |
| f_ | 소거 계수 | 의 성분입니다 |
| 전진대입 | forward | 입니다 |
| 후진대입 | back | 입니다 |
| 양정치 | positive definite | 입니다 |
이것으로 02단원을 마칩니다. 66강에서 행렬을 변환으로 읽기 시작해 67강에서 푸는 절차를 세우고, 68강에서 해의 구조를 밝히고, 69강에서 되돌리기의 조건을 찾고, 70강에서 계산을 저장했습니다.
다음 71강부터 시작하는 03단원은 관점을 한 단계 끌어올립니다. 지금까지 의 벡터만 다뤘는데, 62강에서 뽑아 둔 여덟 공리만 만족하면 다항식도 함수도 행렬도 같은 언어로 다룰 수 있습니다. 그러면 68강의 영공간과 해집합이 부분공간이라는 하나의 개념으로 묶이고, 계수와 차원의 관계가 정리로 정식화됩니다.