이 과목 내내 "조건수가 크면 위험하다"고 경고했습니다. 여덟 번쯤 나왔습니다.
67강 심화 6에서 처음 언급하며 **"안정성은 알고리즘의 성질이고 조건은 문제의 성질"**이라 구별했습니다. 79강 심화 4에서 행렬식과 다르다고 했고, 81강 문제 5에서 정규방정식이 조건수를 제곱한다고 했으며, 88강 문제 5에서 로 썼습니다.
그런데 정의도 증명도 미뤘습니다.
이 강의에서 답합니다. 물음은 이렇습니다.
입력이 조금 틀리면 답이 얼마나 틀리는가.
답은 조건수 하나로 정리됩니다.
그리고 이 상한이 실제로 달성됩니다. 검산에서 증폭비가 이고 입니다.
마지막에 가장 중요한 경고를 답니다. 잔차가 작다고 해가 정확한 것이 아닙니다.
문제. , 을 봅니다.
(1) 해를 구하세요.
(2) 의 둘째 성분을 만큼 늘려 다시 푸세요.
(3) 상대오차를 비교하세요.
생각의 실마리. 두 방정식이 거의 같습니다. 두 직선이 거의 평행하므로 교점이 뚜렷하지 않습니다.
풀이. (1) 검산에서 입니다.
(2) 로 바꾸면 입니다.
해가 완전히 달라졌습니다.
(3) 상대오차를 잽니다.
| 항목 | 값 |
|---|---|
| 입력 상대오차 | 3.535446\times10^ |
| 출력 상대오차 | 1.000000\times10^ |
| 증폭비 | |
입력이 틀렸는데 출력이 틀렸습니다.
이 문제에서 배우는 것: 나쁜 조건.
관찰. 어떤 문제는 입력의 작은 오차가 출력의 큰 오차를 낳습니다. 알고리즘과 무관하게 그렇습니다.
이 예에서 알고리즘은 잘못이 없습니다. solve가 정확히 계산했고, 두 답 모두 각자의 방정식을 만족합니다. 문제 자체가 그런 성질입니다.
기하로 보면 분명합니다.
두 직선이 거의 평행합니다. 기울기가 과 입니다. 그러면 교점이 어디인지 정하기 어렵고, 한 직선을 조금만 옮겨도 교점이 크게 움직입니다.
69강 문제 3에서 특이행렬이 두 열이 평행할 때라 했는데, 여기서는 거의 평행합니다. 완전히 특이하지는 않아 해가 유일하지만, 특이에 가까워 불안정합니다.
행렬식이 작지만 그것이 이유는 아닙니다. 79강 심화 4에서 본 대로 행렬식의 크기와 조건수는 다른 양입니다. 문제 2에서 정확한 척도를 세웁니다.
바로 확인 1.
확인 1-1. 이 예에서 알고리즘의 잘못이 있습니까?
답. 없습니다. 문제 자체가 민감합니다.
확인 1-2. 기하적으로 무엇이 문제입니까?
답. 두 직선이 거의 평행해 교점이 불안정합니다.
확인 1-3. 행렬식이 작은 것이 원인입니까?
답. 아닙니다. 행렬식과 조건수는 다른 양입니다.
문제. 조건수를 정의합니다.
(1) 를 계산하세요.
(2) 과 비교하세요.
(3) 세 행렬의 조건수를 구하세요.
생각의 실마리. 90강 심화 4에서 오차 전파를 유도하며 이 양이 나왔습니다. 정의로 삼습니다.
풀이. (1) 검산에서 입니다.
(2) 도 로 같습니다. 마지막 자리의 차이는 반올림입니다.
(3) 세 예를 봅니다.
| 행렬 | \kappa_ |
|---|---|
| I_ | 1.000000\times10^ |
| 10^{-4}I_ | 1.000000\times10^ |
| 1.000000\times10^ |
둘째 줄이 79강 심화 4의 예입니다. 행렬식이 인데 조건수가 입니다.
이 문제에서 배우는 것: 조건수.
조건수.
이며 노름에서는
입니다.
88강 심화의 식이 여기서 정의가 됩니다.
둘째 식은 이고 의 최대 성분이 이기 때문입니다.
기하적 뜻이 분명합니다.
88강 문제 3에서 단위구가 타원체로 간다고 했는데, 조건수가 그 타원체의 찌그러진 정도입니다.
성질을 정리합니다.
| 성질 | 내용 |
|---|---|
| 언제나 | |
| 척도에 무관 | |
| 역과 같습니다 | |
| 직교행렬 | |
| \kappa(A^{\top}A)=\kappa(A)^ | 제곱됩니다 |
첫 줄의 증명은 90강 심화 4에서 준곱셈성으로 했습니다.
둘째 줄이 행렬식과의 결정적 차이입니다. 인데 조건수는 변하지 않습니다.
**그래서 의 조건수가 **입니다. 크기만 줄었지 모양은 그대로입니다.
다섯째 줄이 81강과 82강의 근거입니다. 의 특이값이 이므로 비가 제곱됩니다.
바로 확인 2.
확인 2-1. 조건수의 정의를 두 가지로 쓰세요.
답. 이고 에서는 입니다.
확인 2-2. 를 쓰세요.
답. 로 척도에 무관합니다.
확인 2-3. 기하적 뜻을 한 문장으로 쓰세요.
답. 단위구가 옮겨간 타원체의 찌그러진 정도입니다.
문제. 상한을 유도하고 확인합니다.
(1) 오차 전파 부등식을 유도하세요.
(2) 등호가 되는 방향을 찾으세요.
(3) 수치로 확인하세요.
생각의 실마리. 두 번의 부등식을 씁니다. 각각이 언제 등호인지 보면 극단 방향이 나옵니다.
풀이. (1) 이고 이면 입니다.
또 이므로
곱하면
(2) 두 부등식이 동시에 등호여야 합니다.
| 부등식 | 등호 조건 |
|---|---|
| 가 방향 | |
| 가 방향 |
는 최대 특이값 방향, 섭동은 최소 특이값 방향입니다.
(3) 검산에서 그렇게 잡으면
| 항목 | 값 |
|---|---|
| 입력 상대오차 | 4.999875\times10^ |
| 출력 상대오차 | 2.000050\times10^ |
| 증폭비 | |
소수 넷째 자리까지 일치합니다.
이 문제에서 배우는 것: 상한이 최선입니다.
정리. 조건수는 달성 가능한 최악의 증폭입니다. 더 나은 상한은 없습니다.
문제 1에서는 증폭비가 로 에 못 미쳤습니다. 방향이 최악이 아니었기 때문입니다. 최악을 골라야 상한에 닿습니다.
실무적 함의가 큽니다. 오차의 방향을 통제할 수 없으므로, 최악을 가정하고 설계해야 합니다.
주의할 점도 있습니다. 이 부등식은 정확한 산술에서의 것입니다. 부동소수점 오차는 아직 고려하지 않았습니다. 그것은 문제 4와 92강의 내용입니다.
67강 심화 6에서 구별한 것이 이제 정확해졌습니다.
바로 확인 3.
확인 3-1. 오차 전파 부등식을 쓰세요.
답. 입니다.
확인 3-2. 등호가 되는 두 방향을 쓰세요.
답. 가 , 섭동이 방향입니다.
확인 3-3. 이 상한이 최선인 이유를 쓰세요.
답. 실제로 달성되므로 더 줄일 수 없습니다.
문제. 이번에는 에 오차가 있습니다.
(1) 로 풀었을 때의 상대오차를 재세요.
(2) 와 비교하세요.
(3) 상한을 진술하세요.
생각의 실마리. 문제 3에서는 만 틀렸습니다. 행렬이 틀리는 경우가 실무에서 더 흔합니다. 측정 오차나 반올림이 계수에 들어가기 때문입니다.
풀이. 검산에서 두 크기의 섭동을 줍니다.
| 실제 상대오차 | ||
|---|---|---|
| 10^ | 1.815329\times10^ | 2.000050\times10^ |
| 10^ | 1.369720\times10^ | 2.000050\times10^ |
실제 오차가 상한 아래에 있고 같은 규모입니다.
이 문제에서 배우는 것: 행렬 섭동.
정리. 이면
같은 조건수가 나타납니다. 상수항이 틀리든 행렬이 틀리든 증폭이 같은 양으로 결정됩니다.
**조건 **이 중요합니다. 이것이 깨지면 가 특이할 수 있습니다.
최소 특이값이 특이까지의 거리입니다.
정리. 에서 가장 가까운 특이행렬까지의 거리가 입니다.
88강 심화 2의 에카르트-영입니다. 인 경우이며, 오차가 입니다.
상대적으로 보면 조건수의 역수입니다.
79강 심화 4의 질문에 답이 나왔습니다. "얼마나 특이에 가까운가"를 재는 것은 행렬식이 아니라 이고, 상대적으로는 입니다.
두 종류의 오차를 합치면 이렇습니다.
입력의 모든 상대오차가 배로 증폭됩니다.
바로 확인 4.
확인 4-1. 행렬 섭동의 상한을 쓰세요.
답. 같은 에 를 곱한 것입니다.
확인 4-2. 특이까지의 거리를 쓰세요.
답. 이며 상대적으로는 입니다.
확인 4-3. "특이에 가깝다"를 무엇으로 잽니까?
답. 행렬식이 아니라 또는 입니다.
문제. 을 문제 1의 계에 넣습니다.
(1) 잔차의 상대 크기를 재세요.
(2) 해의 상대오차를 재세요.
(3) 힐베르트 행렬에서도 확인하세요.
생각의 실마리. 는 참해 과 완전히 다릅니다. 그런데 잔차는 어떨지 봅니다.
풀이. (1) 검산에서 잔차의 상대 크기가 입니다.
(2) 해의 상대오차가 입니다.
잔차가 인데 해가 틀렸습니다.
(3) 힐베르트 행렬에서
| 항목 | 값 |
|---|---|
| 1.6025\times10^ | |
| 잔차 상대 크기 | 1.1056\times10^ |
| 해의 상대오차 | 4.3368\times10^ |
잔차가 기계 정밀도 수준인데 해가 틀렸습니다.
이 문제에서 배우는 것: 잔차와 오차는 다릅니다.
경고. 잔차가 작다고 해가 정확한 것이 아닙니다. 관계는
이며 배의 여유가 있습니다.
69강 문제 5에서 이미 언급했습니다. 거기서 힐베르트 행렬로 inv와 solve를 비교하며 "잔차가 작다고 해가 정확한 것은 아니다"라고 했는데, 그 관계가 이제 정량화되었습니다.
두 개념을 구별합니다.
| 이름 | 재는 것 |
|---|---|
| 잔차 | 가 에 얼마나 가까운가 |
| 오차 | 가 참해에 얼마나 가까운가 |
잔차는 잴 수 있고 오차는 못 잽니다. 참해를 모르기 때문입니다. 그래서 잔차로 오차를 추정하는데, 를 곱해야 합니다.
후방 오차 해석이라는 관점이 여기서 나옵니다.
후방 오차. 계산된 가 어떤 섭동된 문제의 정확한 해인지 묻습니다.
좋은 알고리즘은 후방 오차가 작습니다. 잔차가 작다는 것이 곧 그 뜻입니다.
그런데 전방 오차(실제 오차)는 후방 오차에 를 곱한 것입니다.
이 관계가 수치해석의 중심 등식입니다.
힐베르트 예에서 확인됩니다. solve가 후방 안정해 잔차가 인데, 을 곱하면 수준이고 실제 오차 와 맞습니다.
바로 확인 5.
확인 5-1. 잔차와 오차의 차이를 쓰세요.
답. 잔차는 방정식을 얼마나 만족하는지이고 오차는 참해와 얼마나 다른지입니다.
확인 5-2. 둘의 관계를 쓰세요.
답. 오차가 잔차의 배 이내입니다.
확인 5-3. 후방 안정이 뜻하는 것을 쓰세요.
답. 계산 결과가 조금 섭동된 문제의 정확한 해라는 뜻입니다.
| 개념 | 식 |
|---|---|
| 조건수 | |
| \ell^ | \kappa_{2}=\sigma_{1}/\sigma_ |
| 상수항 섭동 | |
| 행렬 섭동 | 같은 에 |
| 잔차와 오차 | 오차 잔차 |
| 특이까지 거리 | , 상대적으로 |
| 성질 | 값 |
|---|---|
| 언제나 | |
| \kappa(A)^ |
| 구별 | 무엇의 성질 | 고칠 수 있는가 |
|---|---|---|
| 조건 | 문제 | 아닙니다 |
| 안정성 | 알고리즘 | 예 |
| 자주 하는 실수 | 바로잡기 |
|---|---|
| 행렬식으로 조건을 판단합니다 | 조건수를 봅니다 |
| 잔차가 작으면 안심합니다 | 배 여유가 있습니다 |
| 조건수를 알고리즘 탓으로 봅니다 | 문제의 성질입니다 |
| 정규방정식을 씁니다 | 가 제곱됩니다 |
문제 6. 조건수의 정의를 두 가지로 쓰세요.
답. 이고 에서는 입니다.
문제 7. 인 이유를 쓰세요.
답. 준곱셈성에서 입니다.
문제 8. 를 쓰세요.
답. 입니다.
문제 9. 를 쓰세요.
답. 직교행렬이면 입니다.
문제 10. 조건수의 기하적 뜻을 쓰세요.
답. 단위구가 옮겨간 타원체의 찌그러진 정도입니다.
문제 11. 오차 전파 부등식을 쓰세요.
답. 입니다.
문제 12. 등호가 되는 두 방향을 쓰세요.
답. 가 , 섭동이 방향입니다.
문제 13. 특이까지의 거리를 쓰세요.
답. 입니다.
문제 14. 잔차와 오차의 관계를 쓰세요.
답. 오차가 잔차의 배 이내입니다.
문제 15. 후방 오차가 무엇입니까?
답. 계산 결과를 정확한 해로 갖는 섭동 문제의 크기입니다.
문제 16. 조건과 안정성을 구별하세요.
답. 조건은 문제의 성질이고 안정성은 알고리즘의 성질입니다.
문제 17. 이면 배정밀도에서 몇 자리가 남습니까?
답. 약 자리입니다.
문제 18. 를 쓰고 함의를 쓰세요.
답. 이며 정규방정식을 피해야 하는 이유입니다.
심화 1. 유효 자릿수를 조건수로 어림하세요.
풀이. 배정밀도에서 상대 반올림 오차가
입니다. 검산에서 확인됩니다.
후방 안정한 알고리즘은 후방 오차를 수준으로 유지합니다. 그러면 문제 5의 관계에서
유효 자릿수를 세면 이렇습니다.
검산에서 계산합니다.
| 남는 자릿수 | |
|---|---|
| 10^ | |
| 10^ | |
| 10^ | |
| 10^ | |
| 10^ |
가 배가 되면 자릿수 하나를 잃습니다.
실무의 기준을 정리합니다.
| 판단 | |
|---|---|
| <10^ | 안전합니다 |
| 10^{3}\sim10^ | 주의합니다 |
| 10^{8}\sim10^ | 위험합니다 |
| >10^ | 배정밀도로는 못 풉니다 |
넷째 줄에 힐베르트 행렬이 있습니다. 에서 이라 겨우 두세 자리가 남고, 이면 을 넘어 유효 자릿수가 없습니다. 69강 문제 5에서 본 상황입니다.
대응책도 정리합니다.
| 방법 | 내용 |
|---|---|
| 정밀도 상향 | 4배 정밀도로 자릿수를 벌어 봅니다 |
| 재정식화 | 조건이 좋은 다른 식을 세웁니다 |
| 정칙화 | 조건수를 낮춥니다 (심화 4) |
| 반복 개선 | 잔차로 보정을 반복합니다 |
넷째 줄이 저렴한 방법입니다. 잔차를 높은 정밀도로 계산하고 그것으로 보정하면, 낮은 정밀도의 분해로도 정확도를 회복할 수 있습니다.
분해를 재사용하므로 한 번에 이며, 70강의 전략입니다.
심화 2. 조건과 안정성을 정확히 구별하세요.
풀이. 67강 심화 6에서 구별했고 여러 번 언급했습니다. 정확히 정의합니다.
문제의 조건. 입력이 바뀔 때 참값이 얼마나 바뀌는지입니다. 알고리즘과 무관합니다.
알고리즘의 안정성. 계산된 답이 참값에서 얼마나 벗어나는지인데, 후방 오차로 잽니다.
후방 안정. 계산 결과 가 인 섭동 문제의 정확한 해이면 후방 안정하다고 합니다.
둘을 곱하면 실제 오차가 나옵니다.
네 경우를 표로 정리합니다.
| 문제의 조건 | 알고리즘 | 결과 |
|---|---|---|
| 좋음 | 안정 | 정확합니다 |
| 좋음 | 불안정 | 고칠 수 있습니다 |
| 나쁨 | 안정 | 부정확하지만 최선입니다 |
| 나쁨 | 불안정 | 최악입니다 |
둘째 줄이 이 과목에서 여러 번 나온 상황입니다.
| 강의 | 불안정한 알고리즘 | 대안 |
|---|---|---|
| 67 | 피벗팅 없는 소거 | 부분 피벗팅 |
| 69 | inv(A)@b |
solve |
| 80 | 고전 그람슈미트 | 하우스홀더 |
| 81 | 정규방정식 | QR |
| 88 | 의 고유분해 | 직접 SVD |
다섯 번 모두 문제는 그대로이고 알고리즘만 바꿨습니다.
검산에서 확인합니다. 두 조건수에서 정규방정식과 QR을 비교합니다.
| 정규방정식 오차 | QR 오차 | ||
|---|---|---|---|
| 10^ | 1.414\times10^ | 1.014\times10^ | 2.220\times10^ |
| 10^ | 1.414\times10^ | 1.257\times10^ | 2.483\times10^ |
같은 문제인데 오차가 배 다릅니다.
셋째 줄은 다릅니다. 알고리즘을 아무리 좋게 해도 한계가 있습니다.
그때는 문제를 바꿔야 합니다. 심화 4의 정칙화가 그 방법입니다.
진단 순서를 정리합니다.
| 단계 | 하는 일 |
|---|---|
| 1 | 조건수를 잽니다 |
| 2 | 나쁘면 문제를 의심합니다 |
| 3 | 좋은데 답이 이상하면 알고리즘을 의심합니다 |
| 4 | 잔차를 재서 후방 안정성을 확인합니다 |
넷째 줄이 실용적입니다. 잔차가 크면 알고리즘 문제이고, 잔차는 작은데 답이 이상하면 조건 문제입니다.
심화 3. 최소제곱의 조건수를 논하세요.
풀이. 82강의 문제에서 조건수가 어떻게 나타나는지 봅니다.
정사각계와 다릅니다. 가 이고 이면 인데, 오차 증폭이 더 복잡합니다.
정리. 최소제곱의 상대오차는
이며 는 와 사이의 각입니다.
가 잔차의 상대 크기입니다.
두 항의 뜻이 다릅니다.
| 항 | 언제 지배 |
|---|---|
| 잔차가 작을 때 (모형이 잘 맞음) | |
| 잔차가 클 때 |
잔차가 크면 이 나타납니다. 81강 문제 5에서 정규방정식이 이라 했는데, 잔차가 크면 QR을 써도 가 붙습니다.
다만 QR이 손해 보지는 않습니다. 정규방정식은 언제나 인데 QR은 잔차가 작으면 입니다.
| 상황 | 정규방정식 | QR |
|---|---|---|
| 잔차 작음 | \kappa^ | |
| 잔차 큼 | \kappa^ | \kappa^ |
모형이 잘 맞을 때 QR의 이득이 큽니다.
조건수를 줄이는 방법도 있습니다.
| 방법 | 효과 |
|---|---|
| 열 척도 조정 | 단위가 다른 변수를 맞춥니다 |
| 중심화 | 절편과 기울기의 상관을 줄입니다 |
| 직교 다항식 | 89강 심화 3의 방법 |
| 정칙화 | 심화 4 |
둘째 줄이 간단하고 효과적입니다. 다항 회귀에서 를 중심화하지 않으면 과 가 거의 평행해 조건수가 나쁩니다.
심화 4. 정칙화가 조건수를 어떻게 바꾸는지 계산하세요.
풀이. 82강 심화 2의 능형회귀를 조건수로 봅니다.
의 고유값이 이므로, 를 더하면
조건수가 이렇게 됩니다.
검산에서 확인합니다.
| 1.6002\times10^ | |
| 10^ | 3.9902\times10^ |
| 10^ | 4.0012\times10^ |
| 10^ | 4.1002\times10^ |
를 만 넣어도 조건수가 배 줄어듭니다.
극한을 봅니다.
가 크면 문제가 에 가까워져 완벽하게 조건이 좋아집니다. 물론 원래 문제와는 멀어집니다.
편향-분산 절충의 수치적 얼굴입니다. 82강 심화 2에서 통계적으로 본 것과 같은 현상입니다.
절단 SVD와 비교합니다.
| 방법 | 작은 처리 | 조건수 |
|---|---|---|
| 절단 | 면 버림 | |
| 능형 | 위 식 |
절단은 급격하고 능형은 부드럽습니다. 88강 심화 3에서 본 대비입니다.
를 고르는 기준도 있습니다.
| 기준 | 내용 |
|---|---|
| 교차검증 | 예측 오차 최소 |
| L-곡선 | 잔차와 해의 노름의 절충점 |
| 불일치 원리 | 잔차를 잡음 수준에 맞춥니다 |
셋째 줄이 원칙적입니다. 데이터의 잡음이 수준이면 잔차를 그보다 작게 만들 이유가 없으므로, 가 되게 를 고릅니다.
심화 5. 고유값과 특이값의 조건수를 논하세요.
풀이. 지금까지는 선형계의 조건수였습니다. 다른 문제에도 조건수가 있습니다.
특이값은 언제나 잘 조건되어 있습니다.
증폭이 없습니다. 86강 문제 4의 바일 부등식과 같은 형태이며, 의 고유값에 대한 결과에서 나옵니다.
고유값은 다릅니다. 84강 심화 4에서 봤습니다.
| 행렬 | 고유값 민감도 |
|---|---|
| 대칭 | (안전) |
| 정규 | 안전 |
| 일반 | |
| 결손 | \lVert E\rVert^ |
**셋째 줄의 **는 고유벡터 행렬의 조건수이며, 85강 문제 5에서 폭발하는 것을 봤습니다.
개별 고유값의 조건수도 정의됩니다. 85강 심화 3의 왼쪽·오른쪽 고유벡터로
정규화했을 때이며, 대칭이면 라 값이 입니다.
고유벡터는 고유값보다 나쁩니다.
두 고유값이 가까우면 고유벡터가 못 믿을 값이 됩니다. 89강 심화 2에서 주성분 해석의 주의로 언급했습니다.
정리합니다.
| 계산 | 조건 |
|---|---|
| 특이값 | 언제나 좋습니다 |
| 대칭 고유값 | 언제나 좋습니다 |
| 일반 고유값 | 에 좌우 |
| 고유벡터 | 간격에 좌우 |
| 선형계 해 | 에 좌우 |
첫 두 줄이 SVD와 eigh를 선호하는 이유입니다. 이 과목의 후반부가 직교 분해에 집중한 근거이기도 합니다.
심화 6. 실무에서 조건수를 어떻게 다루는지 정리하세요.
풀이. 진단부터 대응까지 정리합니다.
진단. 조건수를 어떻게 아는가.
| 방법 | 비용 | 정확도 |
|---|---|---|
| SVD | , 상수 큼 | 정확 |
| LU + 노름 추정 | 추가 | 어림 |
| 반복 개선의 수렴 | 거의 공짜 | 간접 |
둘째 줄이 실무의 기본입니다. LAPACK의 gecon이 을 역행렬 없이 추정하며, 대개 참값의 몇 배 이내입니다.
대응. 조건수가 나쁘면 무엇을 하는가.
| 대응 | 내용 |
|---|---|
| 척도 조정 | 행과 열을 균형 있게 |
| 재정식화 | 다른 변수나 기저 |
| 정칙화 | 심화 4 |
| 정밀도 상향 | 임시방편 |
| 문제 자체를 의심 | 데이터가 부족한가 |
첫째 줄이 가장 싸고 효과적입니다. 단위가 크게 다른 변수가 섞여 있으면 그것만으로 조건수가 나빠집니다.
89강 문제 5의 표준화가 이 조작입니다.
다섯째 줄이 가장 근본적입니다. 조건이 나쁘다는 것은 흔히 데이터가 답을 결정하지 못한다는 뜻입니다.
| 증상 | 실제 원인 |
|---|---|
| 회귀 계수가 폭발 | 설명변수가 거의 종속 |
| 역문제가 불안정 | 측정이 부족 |
| 고유벡터가 흔들림 | 고유값이 가까움 |
세 경우 모두 수치 문제가 아니라 정보 부족입니다. 더 나은 알고리즘이 아니라 더 나은 데이터나 더 강한 가정이 필요합니다.
67강 심화 6, 69강 심화 5, 82강 심화 2에서 반복한 결론입니다.
마지막으로 습관을 정리합니다.
| 습관 | 이유 |
|---|---|
| 조건수를 늘 확인합니다 | 답을 믿을지 판단합니다 |
| 잔차만 보지 않습니다 | 배 여유가 있습니다 |
| 직교 변환 기반 알고리즘을 씁니다 | 안정성을 확보합니다 |
| 를 만들지 않습니다 | 조건수를 제곱합니다 |
| 정규화와 척도를 신경 씁니다 | 싼 개선입니다 |
이 강의에서는 numpy만 씁니다. 조건수를 두 방법으로 계산하고, 오차 증폭의 상한이 달성됨을 확인하며, 잔차와 오차가 다름을 힐베르트 행렬로 봅니다.
import numpy as np
rng = np.random.default_rng(91)
# --- 문제 1: 입력을 조금 바꾸면 답이 크게 달라집니다 --------------------
A = np.array([[1.,1.],[1.,1.0001]])
b = np.array([2., 2.0001])
x = np.linalg.solve(A,b); print(np.round(x,8).tolist()) # [1.0, 1.0]
db = np.array([0., 0.0001])
x2 = np.linalg.solve(A, b+db); print((np.round(x2,8)+0.0).tolist()) # [0.0, 2.0]
rel_in = np.linalg.norm(db)/np.linalg.norm(b)
rel_out = np.linalg.norm(x2-x)/np.linalg.norm(x)
print("%.6e %.6e %.4f" % (rel_in, rel_out, rel_out/rel_in))
# 3.535446e-05 1.000000e+00 28284.9784
print("%.4f" % np.linalg.cond(A)) # 40002.0001
# --- 문제 2: 조건수의 두 표현 -------------------------------------------
print("%.8f %.8f" % (np.linalg.norm(A,2)*np.linalg.norm(np.linalg.inv(A),2),
np.linalg.cond(A)))
# 40002.00007501 40002.00007495
s = np.linalg.svd(A, compute_uv=False)
print("%.8f %.8f" % (s[0]/s[-1], np.linalg.cond(A)))
# 40002.00007495 40002.00007495
for M in [np.eye(3), np.diag([1e-4]*5), np.array([[1.,0.],[0.,1e-6]])]:
print("%.6e" % np.linalg.cond(M))
# 1.000000e+00
# 1.000000e+00 <- det = 1e-20 인데 조건수는 1 입니다
# 1.000000e+06
# --- 문제 3: 상한이 실제로 달성됩니다 -----------------------------------
U, sv, Vt = np.linalg.svd(A)
xb = Vt[0] # x 를 최대 특이값 방향으로
bb = A@xb
dbb = 1e-8*U[:,-1] # 섭동은 최소 특이값 방향으로
xx = np.linalg.solve(A, bb+dbb)
ri = np.linalg.norm(dbb)/np.linalg.norm(bb)
ro = np.linalg.norm(xx-xb)/np.linalg.norm(xb)
print("%.6e %.6e %.6f %.6f" % (ri, ro, ro/ri, np.linalg.cond(A)))
# 4.999875e-09 2.000050e-04 40001.999833 40002.000075
# --- 문제 4: 행렬이 틀린 경우 -------------------------------------------
for e in [1e-6, 1e-8]:
E = rng.standard_normal((2,2)); E = e*E/np.linalg.norm(E,2)
xe = np.linalg.solve(A+E, b)
print("%.0e" % e, "%.6e %.6e" % (np.linalg.norm(xe-x)/np.linalg.norm(x),
np.linalg.cond(A)*np.linalg.norm(E,2)/np.linalg.norm(A,2)))
# 1e-06 1.815329e-02 2.000050e-02
# 1e-08 1.369720e-04 2.000050e-04
# --- 문제 5: 잔차가 작아도 해는 틀릴 수 있습니다 ------------------------
xw = np.array([2.0, 0.0]) # 참해 (1,1) 과 완전히 다릅니다
print("%.6e %.6e" % (np.linalg.norm(A@xw-b)/np.linalg.norm(b),
np.linalg.norm(xw-x)/np.linalg.norm(x)))
# 3.535446e-05 1.000000e+00 <- 잔차 0.0035%, 오차 100%
H = np.array([[1/(i+j+1) for j in range(10)] for i in range(10)]) # 힐베르트
xt = np.ones(10); bh = H@xt
xh = np.linalg.solve(H, bh)
print("%.4e" % np.linalg.cond(H)) # 1.6025e+13
print("%.4e %.4e" % (np.linalg.norm(H@xh-bh)/np.linalg.norm(bh),
np.linalg.norm(xh-xt)/np.linalg.norm(xt)))
# 1.1056e-16 4.3368e-04 <- 잔차는 기계 정밀도, 오차는 0.04%
# --- 심화 1: 유효 자릿수 ------------------------------------------------
print("%.4e" % np.finfo(float).eps) # 2.2204e-16
for k in [1e2, 1e6, 1e10, 1e14, 1e18]:
print("%.0e" % k, "%.2f" % max(0, 16 - np.log10(k)))
# 1e+02 14.00
# 1e+06 10.00
# 1e+10 6.00
# 1e+14 2.00
# 1e+18 0.00
# --- 심화 2: 같은 문제, 다른 알고리즘 -----------------------------------
for e in [1e-3, 1e-6]:
X = np.array([[1.,1.],[e,0.],[0.,e]])
xt2 = np.array([1.,-1.]); bb2 = X@xt2
xn = np.linalg.solve(X.T@X, X.T@bb2) # 정규방정식
Q, R = np.linalg.qr(X); xq = np.linalg.solve(R, Q.T@bb2) # QR
print("%.0e %.3e" % (e, np.linalg.cond(X)),
"%.3e %.3e" % (np.linalg.norm(xn-xt2), np.linalg.norm(xq-xt2)))
# 1e-03 1.414e+03 1.014e-10 2.220e-16
# 1e-06 1.414e+06 1.257e-04 2.483e-16
# --- 심화 4: 능형이 조건수를 낮춥니다 -----------------------------------
G = np.array([[1.,1.],[1.,1.0001]])
GtG = G.T@G
for lam in [0.0, 1e-6, 1e-3, 1e-1]:
print("%.0e" % lam, "%.4e" % np.linalg.cond(GtG + lam*np.eye(2)))
# 0e+00 1.6002e+09
# 1e-06 3.9902e+06
# 1e-03 4.0012e+03
# 1e-01 4.1002e+01
실행하면 주석과 같은 값이 나옵니다. 다섯 곳을 짚어 둡니다.
첫째, 입력이 바뀌었는데 해가 에서 로 완전히 달라집니다. 증폭비가 이고 입니다.
둘째, 조건수의 두 표현이 일치합니다. 그리고 **의 조건수가 **입니다. 행렬식이 인데도 그렇습니다. 79강 심화 4에서 지적한 대비가 여기서 확인됩니다.
셋째가 이 강의의 핵심입니다. 극단 방향을 골랐더니 **증폭비가 이고 **입니다. 소수 넷째 자리까지 맞습니다. 상한이 최선임을 보인 것이며, 이 방향을 잡을 때 과 을 각각 써야 합니다.
넷째, 행렬 섭동에서도 실제 오차가 상한과 같은 규모입니다.
다섯째가 실무의 경고입니다. 은 참해와 다른데 **잔차가 **입니다. 힐베르트 행렬에서는 더 극적입니다. 잔차가 으로 기계 정밀도인데 해가 틀렸습니다. 을 곱하면 이라 오차와 규모가 맞습니다.
심화 2의 비교도 인상적입니다. 에서 정규방정식이 이고 QR이 입니다. 같은 문제인데 배 차이입니다.
코드로 할 수 없는 일도 분명히 해 둡니다. 부등식의 증명은 예로 되지 않습니다. 문제 3의 유도가 그 자리를 맡습니다. 그리고 문제 3에서 상한에 닿은 것은 특이벡터 방향을 일부러 골랐기 때문이며, 무작위 섭동에서는 문제 1처럼 상한에 못 미칩니다. 조건수는 최악의 경우이지 전형적인 경우가 아닙니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 조건수 | 입니다 | |
| \kappa_ | 조건수 | 입니다 |
| 기계 엡실론 | 배정밀도에서 2.22\times10^ | |
| 전방 오차 | forward error | 참해와의 차이입니다 |
| 후방 오차 | backward error | 섭동 문제의 크기입니다 |
| 후방 안정 | backward stable | 후방 오차가 입니다 |
| 잔차 | residual | 입니다 |
| 반복 개선 | iterative refinement | 잔차로 보정을 반복합니다 |
다음 92강에서는 부동소수점 자체를 다룹니다. 이 강의에서 를 상수로 썼는데, 그것이 어디서 오는지와 어떤 계산이 위험한지를 봅니다. 45강의 파국적 상쇄가 정식으로 설명되며, S4의 마지막 강의입니다.