84강에서 방향이 바뀌지 않는 벡터를 찾았습니다. 그 방향에서 는 그저 상수배입니다.
그러면 자연스러운 다음 질문이 나옵니다.
그런 방향들로 기저를 만들 수 있는가.
만들 수 있다면 그 좌표계에서 가 대각행렬이 됩니다. 좌표들이 서로 섞이지 않으므로 차원 문제가 일차원 문제 개로 갈라집니다.
75강 문제 5에서 이것이 좌표 변환의 목적이라고 했습니다.
그런데 언제나 되는 것은 아닙니다. 77강 문제 4에서 이 대각화되지 않음을 보았고, 84강 문제 5에서 그 이유가 중복도의 어긋남임을 확인했습니다.
이 강의는 정확한 조건을 세우고, 되면 무엇을 얻는지 봅니다. 거듭제곱, 행렬함수, 미분방정식이 모두 쉬워집니다.
문제. 의 고유벡터를 열로 놓아 를 만듭니다.
(1) 를 계산하세요.
(2) 왜 그렇게 되는지 설명하세요.
(3) 를 와 대각행렬로 표현하세요.
생각의 실마리. 77강 문제 1에서 였습니다. 기저를 고유벡터로 잡으면 각 기저벡터의 상이 자기 자신의 상수배이므로 좌표가 단순합니다.
풀이. (1) 84강에서 고유값이 이고 고유벡터가 입니다. 검산에서
(2) 의 번째 열이 이므로
66강 심화 1의 둘째 관점을 썼습니다. 양변에 을 곱하면 됩니다.
(3) 옮겨 쓰면
검산에서 확인됩니다.
이 문제에서 배우는 것: 대각화.
대각화. 고유벡터로 의 기저를 만들 수 있으면
로 쓸 수 있고, 를 대각화 가능하다고 합니다.
**핵심 등식은 **입니다. 양변을 열별로 보면 이므로, 이 식이 고유값 방정식을 한꺼번에 적은 것입니다.
가 가역이려면 고유벡터들이 일차독립이어야 합니다. 69강의 가역 조건입니다. 그것이 되는지가 문제 2의 주제입니다.
순서는 자유입니다. 와 의 짝만 맞으면 어떤 순서로 놓아도 됩니다. 의 순서를 바꾸면 의 열 순서도 같이 바꿔야 합니다.
75강 문제 4와 77강에서 미리 본 것이 이제 정식화되었습니다.
77강 심화 4에서 "가장 단순한 표현"을 물었는데, 대각이 그 답입니다. 다만 언제나 도달할 수 있는 것은 아닙니다.
바로 확인 1.
확인 1-1. 대각화의 정의를 쓰세요.
답. 로 쓸 수 있는 것입니다.
확인 1-2. 가 무엇을 한꺼번에 적은 것입니까?
답. 각 열의 고유값 방정식 입니다.
확인 1-3. 가 가역이려면 무엇이 필요합니까?
답. 고유벡터들이 일차독립이어야 합니다.
문제. 네 행렬을 봅니다.
(1) 각각의 고유값과 서로 다른 개수를 세세요.
(2) 기하적 중복도의 합을 구하세요.
(3) 대각화 가능 여부를 판정하세요.
생각의 실마리. 84강 문제 3에서 두 중복도를 정의했습니다. 기하적 중복도의 합이 이어야 고유벡터로 기저를 만들 수 있습니다.
풀이. 검산에서 계산합니다.
| 행렬 | 고유값 | 서로 다른 개수 | 기하적 합 | 대각화 |
|---|---|---|---|---|
| \begin{pmatrix}3&1\\ 0&1\end | 예 | |||
| \begin{pmatrix}2&0\\ 0&2\end | 예 | |||
| \begin{pmatrix}2&1\\ 0&2\end | 아니오 | |||
| \begin{pmatrix}4&1\\ 1&3\end | 예 |
둘째와 셋째가 고유값이 같은데 갈립니다. 차이는 기하적 중복도입니다.
이 문제에서 배우는 것: 대각화 가능 조건.
정리. 가 대각화 가능한 것과 다음이 같습니다.
즉 모든 고유값에서 기하적 중복도와 대수적 중복도가 같습니다.
84강 문제 3에서 기하적 대수적이었고, 대수적의 합은 언제나 입니다(복소수 범위). 따라서 하나라도 부족하면 합이 에 못 미칩니다.
이런 행렬을 결손이라 합니다.
충분조건 몇 가지를 정리합니다.
| 조건 | 대각화 |
|---|---|
| 고유값이 모두 다름 | 예 (84강 심화 1) |
| 대칭 | 예 (86강) |
| 정사영 | 예 |
| 직교 | 예 (복소수 범위) |
| 멱영이면서 | 아니오 |
첫째 줄은 충분조건이지 필요조건이 아닙니다. 둘째 예 는 고유값이 중복인데 대각화되어 있습니다.
다섯째 줄의 이유를 봅니다. 멱영이면 고유값이 뿐인데, 대각화되면 이므로 입니다. 이면 모순입니다.
77강 문제 4에서 계수로 구별한 것과 같은 결론입니다.
수치적 판정의 어려움도 짚어 둡니다. 검산에서 기하적 중복도를 세려면 의 작은 특이값을 세는데, 문턱을 정해야 합니다.
실제로 이 검산을 처음 짤 때 고유값을 소수 열째 자리로 반올림했더니 오차가 생겼고, 그것이 문턱을 넘어 대칭행렬이 대각화 불가능으로 잘못 판정되었습니다. 고유값을 반올림하지 않고 문턱을 명시해야 합니다.
심화 5에서 이 어려움을 자세히 봅니다.
바로 확인 2.
확인 2-1. 대각화 가능 조건을 쓰세요.
답. 기하적 중복도의 합이 입니다.
확인 2-2. 고유값이 모두 다르면 대각화됩니까?
답. 됩니다. 다만 필요조건은 아닙니다.
확인 2-3. 멱영이면서 영행렬이 아니면 왜 대각화가 안 됩니까?
답. 대각화되면 이라 이 되어 모순입니다.
문제. 에 대해
(1) 과 을 두 방법으로 계산하세요.
(2) 피보나치 행렬 의 고유값을 구하세요.
(3) 에서 피보나치 수의 공식을 얻으세요.
생각의 실마리. 이면 거듭제곱에서 가운데가 지워집니다. 75강 문제 4에서 이미 썼습니다.
풀이. (1) 검산에서
이고 과 일치합니다.
(2) , 이므로
검산에서 와 입니다. 황금비입니다.
(3) 의 성분이 이고, 대각화로 계산하면
검산에서 이면 이고 이면 로, 행렬 거듭제곱과 공식이 일치합니다.
이 문제에서 배우는 것: 대각화의 첫 이득.
거듭제곱.
중간의 가 모두 지워지기 때문입니다.
32강과 66강 심화 4의 이야기가 여기서 닫힙니다. 32강에서 피보나치를 특성방정식으로 풀었고, 66강에서 행렬 거듭제곱으로 옮겼으며, 이제 그 특성방정식의 근이 실은 행렬의 고유값임이 드러났습니다.
32강의 특성방정식과 84강의 특성방정식이 같은 식입니다. 우연이 아니라 같은 대상을 두 언어로 적은 것입니다.
비네 공식이라 불리는 이 결과는 놀랍습니다. 정수만 나오는 수열이 무리수 로 표현됩니다. 이므로 가 커지면 이 사라지고
로 황금비의 거듭제곱에 비례합니다.
일반적으로 가 클 때 가장 큰 고유값이 지배합니다.
84강 심화 5의 거듭제곱법이 이 사실을 이용한 것이었습니다.
거동도 고유값의 크기로 갈립니다.
| $\max\lvert \lambda_{i}\rvert $ | 의 거동 |
|---|---|
| 으로 수렴 | |
| 유계 | |
| 발산 |
심화 6의 마르코프 연쇄에서 이 판정을 씁니다.
바로 확인 3.
확인 3-1. 를 대각화로 쓰세요.
답. 입니다.
확인 3-2. 왜 가운데가 지워집니까?
답. 이기 때문입니다.
확인 3-3. 피보나치 행렬의 고유값을 쓰세요.
답. 이며 황금비입니다.
문제. 를 정의하려 합니다.
(1) 급수로 정의하고 계산하세요.
(2) 대각화로 계산하세요.
(3) 도 구해 보세요.
생각의 실마리. 55강에서 였습니다. 자리에 행렬을 넣으면 거듭제곱만 필요하므로 정의가 됩니다.
풀이. (1) 정의합니다.
검산에서 항까지 더하면
(2) 대각화로 계산합니다.
이므로 즉시 나오고, 검산에서 급수와 소수 여덟 자리까지 일치합니다.
(3) 같은 방식입니다.
검산에서 가 확인됩니다.
이 문제에서 배우는 것: 행렬함수.
행렬함수. 이고 가 고유값에서 정의되면
고유값에 를 적용하고 고유벡터는 그대로 둡니다. 84강 심화 2에서 다항식에 대해 본 것이 임의의 함수로 확장됩니다.
왜 잘 정의되는가. 다항식이면 대각화 정의와 급수 정의가 일치하고, 일반 함수는 다항식 근사의 극한으로 정당화됩니다.
주의할 점이 있습니다. 가 모든 고유값에서 정의되어야 합니다.
| 함수 | 필요한 조건 |
|---|---|
| e^ | 없습니다 (언제나) |
| 고유값이 음이 아니어야 실수 | |
| 고유값이 양수여야 실수 | |
| A^ | 고유값에 이 없어야 |
넷째 줄이 69강의 가역 조건입니다. 가 에서 정의되지 않는 것과 같습니다.
제곱근이 유일하지 않다는 점도 중요합니다. 각 에 부호 선택이 있으므로 가지가 나오고, 결손 행렬에서는 아예 없을 수도 있습니다.
응용이 많습니다.
| 응용 | 쓰는 함수 |
|---|---|
| 선형미분방정식 | e^ |
| 마르코프 연속시간 | e^ |
| 백색화 | \Sigma^ |
| 가우스 표본 생성 | \Sigma^ |
첫째 줄이 가장 중요합니다. 의 해가
이므로, 각 고유방향이 독립적으로 로 변합니다. 79강 심화 3에서 본 도 이 표현에서 즉시 나옵니다.
셋째와 넷째 줄은 70강의 콜레스키와 겹칩니다. 콜레스키가 더 싸지만, 은 대칭이라 해석이 다릅니다. 86강에서 대칭행렬의 제곱근을 다룹니다.
바로 확인 4.
확인 4-1. 의 정의를 쓰세요.
답. 이며 고유값에 를 적용합니다.
확인 4-2. 가 실수이려면 무엇이 필요합니까?
답. 고유값이 음이 아니어야 합니다.
확인 4-3. 의 해를 쓰세요.
답. 입니다.
문제. 를 봅니다.
(1) 고유값과 고유공간의 차원을 구하세요.
(2) 를 계산해 규칙을 찾으세요.
(3) 성분을 조금 흔들면 어떻게 됩니까?
생각의 실마리. 문제 2에서 이 행렬이 결손이었습니다. 대각화가 안 되면 거듭제곱이 어떻게 되는지 봅니다.
풀이. (1) 고유값이 이고 입니다. 대수적 , 기하적 입니다.
(2) 검산에서
규칙이 보입니다.
대각은 인데 위쪽에 가 붙습니다.
(3) 검산에서 를 봅니다.
| 고유값 | ||
|---|---|---|
| 10^ | 1.0000\times10^ | |
| 10^ | 1.0000\times10^ |
고유값이 갈라져 대각화가 가능해집니다. 그런데 고유벡터 행렬의 조건수가 로 커집니다.
이 문제에서 배우는 것: 결손과 조르당 형.
조르당 블록. 대각화가 안 되는 경우 다음 형태까지는 갈 수 있습니다.
77강 심화 2에서 소개한 조르당 표준형입니다.
거듭제곱에 다항식이 붙습니다.
대각화되면 순수한 지수인데, 결손이면 항이 생깁니다.
| 상황 | 의 성장 |
|---|---|
| 대각화 가능 | \lambda^ |
| 조르당 블록 크기 | k^{m-1}\lambda^ |
미분방정식에서도 같습니다. 해가 가 아니라 가 됩니다. 중근일 때 가 나오는 이유이며, 100강대에서 다시 봅니다.
(3)의 결과가 실무적으로 중요합니다. 성분을 아주 조금 흔들면 대각화가 가능해집니다.
무작위 행렬은 거의 확실히 고유값이 모두 달라 대각화됩니다. 그런데 그것이 위안이 되지 않습니다. 조건수가 로 커지므로, 대각화는 되지만 쓸모없습니다.
을 곱하는 계산에서 오차가 배로 증폭됩니다. 75강 심화 4와 77강 심화 5에서 경고한 상황입니다.
그래서 실무에서는 대각화를 쓰지 않습니다.
| 목적 | 실무의 방법 |
|---|---|
| 고유값 | QR 알고리즘 |
| 행렬함수 | 슈어 분해 + 삼각 알고리즘 |
| 대칭행렬 | 스펙트럼 분해 (86강) |
| 일반 근사 | SVD (88강) |
대각화는 이해를 위한 도구이고, 계산은 직교 변환에 기반한 방법으로 합니다. 69강, 70강, 78강, 81강에 이어 여섯 번째로 같은 교훈입니다.
바로 확인 5.
확인 5-1. 결손 행렬의 거듭제곱이 어떻게 됩니까?
답. 에 의 다항식이 곱해집니다.
확인 5-2. 성분을 흔들면 대각화가 됩니까?
답. 됩니다. 다만 의 조건수가 폭발합니다.
확인 5-3. 실무에서 행렬함수를 어떻게 계산합니까?
답. 슈어 분해 같은 직교 변환 기반 방법을 씁니다.
| 개념 | 식 |
|---|---|
| 대각화 | A=V\Lambda V^ |
| 핵심 등식 | |
| 가능 조건 | |
| 거듭제곱 | A^{k}=V\Lambda^{k}V^ |
| 행렬함수 | f(A)=Vf(\Lambda)V^ |
| 미분방정식 | \mathbf{x}(t)=e^{tA}\mathbf{x}_ |
| 충분조건 | 대각화 |
|---|---|
| 고유값이 모두 다름 | 예 |
| 대칭 | 예 |
| 정사영 | 예 |
| 멱영이고 | 아니오 |
| 결손이면 | 결과 |
|---|---|
| 조르당 블록 | 위에 |
| 거듭제곱 | k^{m-1}\lambda^ |
| 미분방정식 | t^{j}e^ |
| 섭동 | 대각화되지만 폭발 |
| 자주 하는 실수 | 바로잡기 |
|---|---|
| 고유값이 중복이면 불가능이라 봅니다 | 기하적 중복도를 봐야 합니다 |
| 순서만 바꿉니다 | 의 열도 같이 바꿉니다 |
| 실무에서 대각화로 계산합니다 | 슈어나 SVD를 씁니다 |
| 가 유일하다고 봅니다 | 부호 선택이 있습니다 |
문제 6. 대각화의 정의를 쓰세요.
답. 로 쓸 수 있는 것입니다.
문제 7. 가 무엇을 뜻합니까?
답. 각 열이 고유값 방정식을 만족한다는 뜻입니다.
문제 8. 대각화 가능 조건을 쓰세요.
답. 기하적 중복도의 합이 입니다.
문제 9. 고유값이 모두 다르면 대각화됩니까?
답. 됩니다. 다만 필요조건은 아닙니다.
문제 10. 가 대각화됩니까?
답. 되지 않습니다. 기하적 중복도가 입니다.
문제 11. 를 대각화로 쓰세요.
답. 입니다.
문제 12. 피보나치 행렬의 고유값을 쓰세요.
답. 입니다.
문제 13. 의 정의를 쓰세요.
답. 입니다.
문제 14. 를 두 가지로 정의하세요.
답. 급수 과 입니다.
문제 15. 의 해를 쓰세요.
답. 입니다.
문제 16. 결손 행렬의 거듭제곱 성장을 쓰세요.
답. 블록 크기가 이면 입니다.
문제 17. 일 조건을 쓰세요.
답. 모든 고유값의 크기가 보다 작아야 합니다.
문제 18. 실무에서 대각화를 쓰지 않는 이유를 쓰세요.
답. 의 조건수가 클 수 있어 오차가 증폭되기 때문입니다.
심화 1. 대각화 가능 조건을 증명하세요.
풀이. 문제 2의 정리를 정확히 보입니다.
() 기하적 중복도의 합이 이라 하고, 각 고유공간의 기저를 모읍니다. 그 합집합이 독립임을 보이면 됩니다.
서로 다른 고유값 에 대해 관계식을 봅니다.
각 가 임을 보이면 각 고유공간 안에서 기저가 독립이므로 전체가 독립입니다.
가 모두 은 아니라고 하면, 이 아닌 것들이 서로 다른 고유값의 고유벡터이므로 84강 심화 1에서 독립입니다. 그런데 합이 이므로 모순입니다.
따라서 개의 독립인 고유벡터가 모이고 가 가역이 되어 대각화됩니다.
() 이면 의 열이 고유벡터이고 독립이므로, 각 고유값의 고유공간에 속하는 것들을 세면 합이 입니다.
따름정리도 얻습니다.
73강의 직합입니다. 대각화는 공간을 고유공간들의 직합으로 쪼개는 일이며, 각 조각에서 가 상수배로 작용합니다.
이것이 대각화의 기하적 내용입니다. 86강에서 대칭행렬이면 그 직합이 직교 직합이 되어 더 좋아집니다.
심화 2. 동시 대각화가 언제 가능한지 논하세요.
풀이. 두 행렬을 같은 로 대각화할 수 있는지 묻습니다.
정리. 가 각각 대각화 가능할 때, 동시에 대각화 가능한 것과 인 것이 같습니다.
() , 이면
대각행렬끼리는 교환되기 때문입니다.
() 이면 가 의 고유공간을 보존합니다. 일 때
이므로 입니다. 각 고유공간 안에서 를 대각화하면 됩니다.
66강 문제 3에서 곱셈이 교환적이지 않다고 했는데, 교환되는 경우가 특별한 이유가 이것입니다.
응용이 많습니다.
| 분야 | 내용 |
|---|---|
| 양자역학 | 교환되는 관측량은 동시에 측정 가능 |
| 신호처리 | 순환행렬들이 푸리에 기저를 공유 |
| 그래프 | 인접행렬과 라플라시안 |
첫째 줄이 불확정성 원리의 배경입니다. 위치와 운동량 연산자가 교환되지 않으므로 공통 고유벡터가 없고, 따라서 동시에 확정값을 가질 수 없습니다.
둘째 줄도 중요합니다. 순환행렬(합성곱 연산)은 모두 푸리에 기저에서 대각이 됩니다. 그래서 60강의 합성곱 정리가 성립하며, FFT가 그 대각화를 빠르게 수행합니다.
60강에서 배운 것이 "동시 대각화"였습니다.
심화 3. 대칭이 아닌 행렬의 스펙트럼 분해를 논하세요.
풀이. 을 다르게 써 봅니다. 의 행을 이라 하면
**66강 심화 1의 다섯째 관점(외적의 합)**입니다.
로 두면 성질이 있습니다.
**에서 **이기 때문입니다.
스펙트럼 분해라 하며, 가 로의 사영입니다.
다만 직교 사영이 아닙니다. 가 와 다르므로 입니다. 80강 심화 2에서 본 비스듬한 사영입니다.
의 정체도 봅니다. 이므로
의 고유벡터이며, 84강 심화 2에서 언급한 왼쪽 고유벡터입니다.
두 종류가 쌍직교합니다.
대칭행렬에서는 둘이 같아집니다. 이면 왼쪽과 오른쪽 고유벡터가 일치하고, 사영이 직교가 됩니다. 86강에서 그 결과가 스펙트럼 정리입니다.
이 차이가 조건수에도 나타납니다. 고유값 의 민감도가
에 비례하는데(정규화했을 때), **대칭이면 이 값이 **이라 가장 안전합니다. 84강 심화 4에서 대칭행렬이 안전하다고 한 근거입니다.
심화 4. 케일리-해밀턴 정리를 소개하고 쓰임을 밝히세요.
풀이. 놀라운 정리가 있습니다.
케일리-해밀턴 정리. 모든 정사각행렬은 자기 특성다항식을 만족합니다.
에서 확인합니다. 이므로
에서 이고
맞습니다.
대각화 가능하면 증명이 쉽습니다. 이고 의 대각이 이므로 영행렬입니다. 결손인 경우는 극한이나 조르당 형으로 처리합니다.
"에 를 대입한다"는 설명은 틀렸습니다. 스칼라 자리에 행렬을 넣을 수 없기 때문입니다. 다항식을 먼저 전개한 뒤 계수에 를 곱해야 합니다.
쓰임이 있습니다.
역행렬 표현. 이면
역행렬이 의 다항식입니다. 이론적으로 유용하며, 78강 심화 2의 여인수 공식과 이어집니다.
거듭제곱의 축약. 을 낮은 차수로 줄일 수 있습니다. 에서
모든 거듭제곱이 와 의 결합입니다. 대각화 없이도 를 계산할 수 있습니다.
최소다항식. 보다 낮은 차수로도 일 수 있으며, 그런 것 중 최소 차수를 최소다항식이라 합니다.
대각화 가능한 것과 최소다항식이 중근을 갖지 않는 것이 같습니다. 문제 2의 조건을 다르게 표현한 것입니다.
| 행렬 | p_ | q_ | 대각화 |
|---|---|---|---|
| (\lambda-2)^ | 예 | ||
| \begin{pmatrix}2&1\\ 0&2\end | (\lambda-2)^ | (\lambda-2)^ | 아니오 |
특성다항식이 같은데 최소다항식이 다릅니다. 77강 문제 4에서 계수로 구별한 것을 다항식으로 구별한 셈입니다.
심화 5. 대각화의 수치적 문제를 정리하세요.
풀이. 문제 5에서 조건수가 폭발하는 것을 보았습니다. 정리합니다.
첫째, 결손 판정이 불가능에 가깝습니다.
부동소수점에서 고유값이 정확히 같은 일은 거의 없습니다. 그래서 "중복인가"를 묻는 것 자체가 잘못된 질문이고, "얼마나 가까운가"를 물어야 합니다.
이 강의의 검산을 짤 때 실제로 그 함정에 걸렸습니다. 고유값을 소수 열째 자리로 반올림했더니 오차가 생겼고, 의 최소 특이값이 그만큼 되어 대칭행렬이 결손으로 잘못 판정되었습니다. 반올림을 없애고 문턱을 명시해야 했습니다.
둘째, 고유벡터가 고유값보다 훨씬 민감합니다.
고유값이 가까우면 그 고유벡터들이 거의 평행해집니다. 그러면 개별 고유벡터는 못 믿어도 그들이 만드는 부분공간은 안정합니다.
주성분분석에서 두 주성분의 분산이 비슷하면 각각의 방향을 해석하면 안 되고, 그 둘이 만드는 평면만 의미가 있습니다. 89강에서 다시 봅니다.
셋째, 이 문제입니다.
에서 의 조건수가 오차를 증폭합니다.
**대칭행렬은 가 직교라 **입니다. 그래서 86강의 스펙트럼 분해가 수치적으로 완벽합니다.
실무의 대안을 정리합니다.
| 목적 | 방법 | 왜 |
|---|---|---|
| 고유값 | QR 알고리즘 | 직교 변환만 |
| 대칭 고유분해 | 야코비, 분할정복 | 직교 변환 |
| 행렬함수 | 슈어 + 삼각 알고리즘 | 대신 직교 |
| e^ | 축척 후 제곱, 파데 근사 | 급수가 위험 |
| 계수, 근사 | SVD | 가장 안정 |
넷째 줄이 흥미롭습니다. 를 급수로 계산하면 의 노름이 클 때 큰 항들이 상쇄되어 파국적 상쇄가 납니다. 그래서 로 줄여 계산한 뒤 번 제곱합니다.
45강의 자릿수 손실을 피하는 표준 기법입니다.
심화 6. 마르코프 연쇄를 대각화로 분석하세요.
풀이. 대각화의 대표적 응용입니다.
전이행렬 의 열이 확률분포이고 합이 입니다.
고유값 이 언제나 있습니다. 열의 합이 이므로 이고, 84강 심화 2에서 의 고유값이 와 같으므로 이 고유값입니다.
검산에서 고유값이 과 입니다.
고유값 의 고유벡터가 정상분포입니다.
장기 거동을 봅니다. 로 전개하면
둘째 항이 로 사라집니다.
검산에서 일 때
| T^{k}\mathbf{x}_ | |
|---|---|
정상분포로 수렴합니다.
수렴 속도가 둘째 고유값으로 정해집니다.
이므로 이면 이고, 표의 오차 와 같은 규모입니다.
를 스펙트럼 간극이라 하며, 클수록 빨리 섞입니다.
| 간극 | 수렴 |
|---|---|
| 큼 | 빠릅니다 |
| 작음 | 느립니다 (거의 분리된 덩어리) |
응용이 많습니다.
| 분야 | 내용 |
|---|---|
| 페이지랭크 | 정상분포가 중요도 |
| MCMC | 간극이 표본 상관을 정합니다 |
| 그래프 군집 | 간극이 작으면 덩어리가 있습니다 |
| 언어 모형 | 상태 전이의 장기 통계 |
둘째 줄이 통계 계산의 핵심입니다. 마르코프 연쇄 몬테카를로에서 표본이 독립에 가까워지는 데 걸리는 시간이 규모이며, 이것을 혼합 시간이라 합니다. 190강대에서 다시 봅니다.
이 강의에서는 numpy만 씁니다. 대각화를 직접 확인하고, 거듭제곱과 행렬함수를 두 방법으로 계산해 맞추며, 결손 행렬에서 무슨 일이 일어나는지 봅니다.
import numpy as np, math
# --- 문제 1: 고유벡터 기저에서 대각이 됩니다 ----------------------------
A = np.array([[2.,1.],[1.,2.]])
w, V = np.linalg.eig(A)
idx = np.argsort(w)[::-1]; w = w[idx].real; V = V[:,idx].real
print(np.round(w,8).tolist()) # [3.0, 1.0]
D = np.linalg.solve(V, A@V)
print((np.round(D,10)+0.0).tolist()) # [[3.0, 0.0], [0.0, 1.0]]
print(bool(np.allclose(V@np.diag(w)@np.linalg.inv(V), A))) # True
# --- 문제 2: 대각화 가능 조건 --------------------------------------------
tests = {
"서로 다른 고유값": np.array([[3.,1.],[0.,1.]]),
"중복이지만 대각": np.array([[2.,0.],[0.,2.]]),
"중복이고 결손": np.array([[2.,1.],[0.,2.]]),
"대칭": np.array([[4.,1.],[1.,3.]]),
}
def geo_mult(M, tol=1e-8):
"""서로 다른 고유값마다 기하적 중복도를 세어 합칩니다."""
n = M.shape[0]; ev = np.linalg.eigvals(M).real
uniq = []
for l in ev:
if not any(abs(l-u) < tol for u in uniq): uniq.append(l)
tot = 0
for l in uniq:
s = np.linalg.svd(M - l*np.eye(n), compute_uv=False)
tot += int(np.sum(s < tol*max(1.0, s[0]))) # 문턱을 명시합니다
return tot, len(uniq)
for name, M in tests.items():
ev = np.linalg.eigvals(M).real
geo, nd = geo_mult(M)
print(name, np.round(np.sort(ev)[::-1],8).tolist(), nd, geo, geo == M.shape[0])
# 서로 다른 고유값 [3.0, 1.0] 2 2 True
# 중복이지만 대각 [2.0, 2.0] 1 2 True
# 중복이고 결손 [2.0, 2.0] 1 1 False
# 대칭 [4.61803399, 2.38196601] 2 2 True
# --- 문제 3: 거듭제곱과 피보나치 ----------------------------------------
for k in [5,10]:
direct = np.linalg.matrix_power(A,k)
print(k, np.round(direct,6).tolist(),
bool(np.allclose(direct, V@np.diag(w**k)@np.linalg.inv(V))))
# 5 [[122.0, 121.0], [121.0, 122.0]] True
# 10 [[29525.0, 29524.0], [29524.0, 29525.0]] True
F = np.array([[1.,1.],[1.,0.]])
wf, Vf = np.linalg.eig(F)
print(np.round(np.sort(wf)[::-1],8).tolist(),
"%.8f %.8f" % ((1+np.sqrt(5))/2, (1-np.sqrt(5))/2))
# [1.61803399, -0.61803399] 1.61803399 -0.61803399
for k in [10,20]:
print(k, int(round(np.linalg.matrix_power(F,k)[0,1])),
int(round((((1+np.sqrt(5))/2)**k - ((1-np.sqrt(5))/2)**k)/np.sqrt(5))))
# 10 55 55
# 20 6765 6765
# --- 문제 4: 행렬함수 ----------------------------------------------------
expA = V@np.diag(np.exp(w))@np.linalg.inv(V)
S = np.eye(2)
for k in range(1,30): S = S + np.linalg.matrix_power(A,k)/math.factorial(k)
print(np.round(expA,8).tolist())
# [[11.40190938, 8.68362755], [8.68362755, 11.40190938]]
print(np.round(S,8).tolist()) # 급수와 같습니다
sqA = V@np.diag(np.sqrt(w))@np.linalg.inv(V)
print(np.round(sqA,8).tolist(), bool(np.allclose(sqA@sqA, A)))
# [[1.3660254, 0.3660254], [0.3660254, 1.3660254]] True
# --- 문제 5: 결손 행렬 ---------------------------------------------------
J = np.array([[2.,1.],[0.,2.]])
print(np.round(np.linalg.eigvals(J).real,8).tolist(),
2-int(np.linalg.matrix_rank(J-2*np.eye(2)))) # [2.0, 2.0] 1
for k in [2,3,5]:
print(k, np.linalg.matrix_power(J,k).tolist())
# 2 [[4.0, 4.0], [0.0, 4.0]]
# 3 [[8.0, 12.0], [0.0, 8.0]]
# 5 [[32.0, 80.0], [0.0, 32.0]] <- 위쪽에 k*2^(k-1) 이 붙습니다
for e in [1e-4, 1e-8]: # 섭동하면 대각화되지만 V 가 나빠집니다
Je = np.array([[2.,1.],[e,2.]])
_, Ve = np.linalg.eig(Je)
print("%.0e" % e, np.round(np.sort(np.linalg.eigvals(Je).real)[::-1],8).tolist(),
"%.4e" % np.linalg.cond(Ve.real))
# 1e-04 [2.01, 1.99] 1.0000e+02
# 1e-08 [2.0001, 1.9999] 1.0000e+04
# --- 심화 6: 마르코프 연쇄 ----------------------------------------------
T = np.array([[0.9,0.2],[0.1,0.8]])
wt, Vt = np.linalg.eig(T)
print(np.round(np.sort(wt.real)[::-1],8).tolist()) # [1.0, 0.7]
pi = Vt[:, int(np.argmax(wt.real))].real; pi = pi/pi.sum()
print(np.round(pi,8).tolist(), np.round(T@pi,8).tolist())
# [0.66666667, 0.33333333] [0.66666667, 0.33333333]
x = np.array([1.,0.])
for k in [1,5,20,60]:
print(k, np.round(np.linalg.matrix_power(T,k)@x, 8).tolist())
# 1 [0.9, 0.1]
# 5 [0.72269, 0.27731]
# 20 [0.66693264, 0.33306736]
# 60 [0.66666667, 0.33333333]
실행하면 주석과 같은 값이 나옵니다. 다섯 곳을 짚어 둡니다.
첫째, 고유벡터를 열로 놓아 만든 에 대해 가 정확히 입니다.
둘째, 네 경우의 판정이 갈립니다. 둘째와 셋째가 고유값이 똑같이 인데 기하적 중복도가 와 로 다릅니다. 그래서 하나는 되고 하나는 안 됩니다.
이 판정을 짤 때 함정에 걸렸습니다. 고유값을 소수 열째 자리로 반올림했더니 오차가 생겨 대칭행렬이 결손으로 잘못 나왔습니다. 반올림을 없애고 문턱을 명시해서 고쳤으며, 심화 5의 주제가 이것입니다.
셋째, 피보나치 행렬의 고유값이 황금비 이고, 비네 공식이 에서 행렬 거듭제곱과 정확히 일치합니다. 32강의 특성방정식이 실은 고유값 방정식이었습니다.
넷째, 를 급수와 대각화로 계산한 결과가 소수 여덟 자리까지 같습니다. 제곱근도 제곱하면 로 돌아옵니다.
다섯째가 이 강의의 경고입니다. 결손 행렬의 거듭제곱에서 위쪽 성분이 으로 입니다. 지수에 다항식이 곱해집니다. 그리고 섭동하면 대각화는 되지만 가 로 커져 , 가 됩니다.
코드로 할 수 없는 일도 분명히 해 둡니다. 대각화 가능 조건의 증명은 예로 되지 않습니다. 심화 1이 그 자리를 맡습니다. 그리고 결손 여부의 수치 판정은 원칙적으로 불안정합니다. 여기서는 정수 성분이라 문턱이 잘 통했지만, 실제 데이터에서는 "얼마나 결손에 가까운가"만 물을 수 있습니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| A=V\Lambda V^ | 대각화 | 고유벡터 기저에서 대각입니다 |
| 대각행렬 | 고유값이 놓입니다 | |
| 결손 | defective | 대각화되지 않습니다 |
| 조르당 블록 | 대각 위에 이 붙습니다 | |
| 행렬함수 | 고유값에 를 적용합니다 | |
| e^ | 행렬지수 | 미분방정식의 해입니다 |
| 최소다항식 | minimal polynomial | 인 최소 차수입니다 |
| 스펙트럼 간극 | spectral gap | $1-\lvert \lambda_{2}\rvert $입니다 |
다음 86강에서는 대칭행렬을 다룹니다. 이 강의에서 대각화가 안 되는 경우와 되어도 가 나쁜 경우를 보았는데, 대칭이면 두 문제가 모두 사라집니다. 언제나 대각화되고 가 직교라 조건수가 입니다. 이 과목에서 가장 중요한 정리이며, 87강의 이차형식과 88강의 특이값 분해가 그 위에 세워집니다.