N5 · 고윳값을 계산하는 반복과 검증#
1. 두 부문의 충격은 어떤 방향으로 남는가#
두 부문의 생산지수에서 기준값을 뺀 변화량을 \(x_k\)라 합시다. 각 지수는 무차원이며 한 단계는 한 기간입니다. 교육용 선형 모형
에서는 자기 부문의 변화가 절반, 다른 부문의 변화가 1/4만큼 다음 기간에 전달됩니다. 외부 충격은 처음에만 주어지고 이후의 규칙은 고정되어 있다고 가정합니다. \(q_+=(1,1)^T/\sqrt2\), \(q_-=(1,-1)^T/\sqrt2\)에 직접 곱하면 \(Hq_+=3q_+\), \(Hq_-=q_-\)입니다. 따라서 \(M\)의 두 감쇠율은 \(3/4,1/4\)입니다.
\(x_0=e_1=(q_++q_-)/\sqrt2\)이면
충격 크기는 0으로 가지만, 방향을 정규화하면 합 방향 \(q_+\)가 남습니다. 길이를 없애고 방향만 보는 반복이 멱방법입니다. \(M\) 대신 \(H\)를 곱해도 정규화한 방향은 같습니다. \(q_+\)와 이루는 예각을 \(\theta_k\)라 하면 \(\tan\theta_k=3^{-k}\)입니다. 이것은 구체적인 수렴률이며 마지막 절에서 일반 조건을 증명합니다.
이 예는 손으로 대각화할 수 있습니다. 큰 행렬에서는 고윳값을 미리 모르는 상태에서 같은 방향과 감쇠율을 찾아야 합니다. 계산 중에는 후보 단위벡터 \(v\)와 Rayleigh 몫 \(\mu=v^THv\)의 잔차 \(r=Hv-\mu v\)를 기록합니다. 방향이 거의 변하지 않는다는 관찰보다 원래 식을 얼마나 만족하는지가 직접적인 검증입니다.
2. 역반복과 Rayleigh 몫 반복#
3에 가까운 고윳값을 찾으려면 \((H-\mu I)y=v\)를 풀고 \(y\)를 정규화할 수 있습니다. \(\mu=2.8\)이면 \(q_+\) 방향의 증폭은 \(1/(3-2.8)=5\), \(q_-\) 방향은 \(1/(1-2.8)=-5/9\)입니다. 따라서 원하지 않는 방향과 원하는 방향의 비는 한 번에 \(1/9\)로 줄어듭니다. \(H\) 자체의 멱방법에서는 \(1/3\)이었던 비가 더 작아졌습니다.
이동을 목표 고윳값에 가까이 둘수록 역행렬은 커집니다. 그러나 해의 전체 길이를 정확히 구하는 것과 정규화한 방향을 구하는 것은 다른 문제입니다. 입력 \(v=c_+q_++c_-q_-\)에 작은 우변 오차 \(f=f_+q_++f_-q_-\)가 있으면 정규화 전 방향의 비는
목표 성분 \(c_++f_+\)가 충분히 크면 작은 \(|3-\mu|\)가 방향 오차를 줄일 수 있습니다. 이 계산은 우변오차에 대한 설명입니다. 실제 선형계의 계수오차, 목표 고윳값의 간극, 목표 성분이 0인 경우까지 무조건 안전하다는 정리는 아닙니다.
Rayleigh 몫 반복은 현재 \(v_k\)로 \(\mu_k=v_k^THv_k\)를 새로 정하고 역반복합니다. \(v=\cos\theta\,q_++\sin\theta\,q_-\)이면 \(\mu=3-2\sin^2\theta\)이고, 역반복 후 두 계수의 비는
목표 가까이에서는 각도 오차가 세제곱으로 작아집니다. 매번 행렬이 바뀌어 새 분해가 필요하므로 고정 이동의 역반복보다 한 단계 비용은 큽니다. \(H-\mu_kI\)가 특이하면 그대로 역을 계산할 수 없습니다. 잔차가 이미 0이면 종료하고, 그렇지 않으면 이동을 수정해야 합니다.
그림 100 세 방법의 같은 초기방향을 비교했다. 세로축은 목표 고유벡터와의 각도의 탄젠트이고 로그 눈금이다. 표시 하한에 도달한 결과는 무한한 정확도를 뜻하지 않는다.#
3. 특성다항식의 근을 구하면 안 되는 이유의 범위#
고윳값이 \(\det(zI-A)=0\)의 근이라는 대수적 정의는 맞습니다. 그러나 행렬에서 다항식 계수를 만든 뒤 다시 근을 구하면 중간 표현의 오차가 추가됩니다. 간격 1의 근 \(1,2,\ldots,20\)을 갖는 다항식은 계수 크기가 매우 다양합니다. 같은 고윳값을 갖는 대칭행렬은 작은 대칭 섭동에 대해 H6의 Weyl 상한을 만족하지만, 다항식 계수의 작은 상대변화가 그 행렬의 같은 크기 상대섭동을 뜻하지는 않습니다.
단순근 \(\lambda\)인 \(p\)의 계수에 \(\delta p\)를 더하면 1차식은
분모가 작거나 \(\delta p(\lambda)\)에 큰 계수들의 오차가 합쳐지면 근이 크게 움직일 수 있습니다. 중근에서는 \(p'(\lambda)=0\)이어서 이 1차식부터 적용되지 않습니다. 작은 차수의 잘 조건화된 다항식까지 계산을 금지한다는 뜻은 아닙니다.
그림 101 직교변환의 난수 시드는 고정했다. 세로축은 절대오차의 로그 눈금이다. 다항식 경로에서 복소수 근이 나오면 복소평면 거리로 오차를 계산한다. 이 한 행렬의 결과를 모든 다항식의 수치오차로 일반화하지 않는다.#
정확한 근을 유한 개의 사칙연산과 근호만으로 모든 차수에서 나타낼 수 있느냐는 별도 질문입니다. 동반행렬이 임의의 monic 다항식을 고유문제로 바꾸므로, 그러한 보편 공식은 Abel–Ruffini의 결과와 충돌합니다. 여기서는 그 대수학 정리를 외부 전제로 소개합니다. 임의의 정확한 고윳값에 대한 근호 공식의 부재는 허용오차까지 유한 시간에 근사하는 알고리즘의 부재를 뜻하지 않습니다. 대각행렬처럼 즉시 답을 읽는 특수한 경우도 있습니다.
4. 계산 목표는 Jordan 형식보다 Schur 형식#
H3의 Schur 정리는 복소행렬에 \(A=QTQ^*\), \(Q\) 유니터리, \(T\) 상삼각인 표현이 있음을 보였습니다. 직교·유니터리 좌표변환은 2-노름을 보존합니다. Jordan 기저를 얻으려고 거의 평행한 고유벡터들의 역행렬을 쓰지 않아도 됩니다.
일반 행렬에서 \(T\)는 대각일 필요가 없습니다. \(\begin{pmatrix}1&10\\0&2\end{pmatrix}\)는 이미 Schur 형이며 비대각 10을 남깁니다. 그 항을 버리면 원래 선형사상을 바꾼 것입니다. 실수 계산에서는 복소 켤레 고윳값을 \(2\times2\) 대각블록에 모으는 실 Schur 형을 씁니다. \(\begin{pmatrix}0&-1\\1&0\end{pmatrix}\)는 고윳값이 \(\pm i\)여서 실수 상삼각행렬이 될 수 없고, 전체가 한 블록입니다.
직교변환을 사용한다는 이유 하나만으로 어떤 구현이든 안정하다고 결론내리지는 않습니다. 각 변환의 생성·적용 오차가 제한되고, 반복 횟수와 스케일도 통제되어야 합니다. 그런 국소 상한을 직교 불변성으로 누적하는 논법은 N3과 같습니다. 계산 후에는 \(\|AQ-QT\|/\|A\|\)와 \(\|Q^*Q-I\|\)를 함께 확인합니다.
5. 반복 전에 Hessenberg로 줄인다#
상 Hessenberg 행렬은 주대각 바로 아래까지만 비영 성분을 허용합니다. 첫 열의 둘째 행 이하를 Householder로 축약하고, 같은 직교변환을 반대쪽에도 적용하면 닮음변환이 됩니다. 이를 남은 열에 반복하면 \(Q^TAQ=H\)이고 \(i>j+1\)이면 \(h_{ij}=0\)입니다.
왼쪽 곱만 하면 QR 축약처럼 일반적으로 고윳값이 바뀝니다. 닮음변환을 유지하려고 오른쪽 곱을 함께 하는 것입니다. 이미 없앤 앞 열의 아래 부분은 뒤 변환의 작용영역에서 0이므로 다시 생기지 않습니다. \(A\)가 대칭이면 \(H\)도 대칭이고 따라서 삼중대각입니다.
밀집 축약은 \(O(n^3)\)입니다. 이후 Hessenberg의 QR 한 스텝은 구조를 활용하면 \(O(n^2)\)이고 대칭 삼중대각의 암묵 스텝은 더 적은 비용으로 수행할 수 있습니다. 아래 교육용 코드는 구조와 수렴을 쉽게 검증하려고 작은 활성 블록의 밀집 QR을 사용합니다. 그 코드 한 스텝을 \(O(n^2)\) 구현이라고 주장하지 않습니다.
6. QR을 반복하면 무엇이 보존되는가#
\(A_0=A\)에서 \(A_{k-1}=Q_kR_k\), \(A_k=R_kQ_k\)로 둡니다. 그러면
각 단계가 직교 닮음이므로 고윳값을 보존합니다. \(Z_k=Q_1\cdots Q_k\)라 하면 \(A_k=Z_k^TAZ_k\)입니다. 또한 \(AZ_{k-1}=Z_kR_k\)이므로 \(Z_k\)는 앞 단계의 직교기저에 \(A\)를 곱하고 다시 직교화한 기저입니다. 이것이 QR 반복과 직교반복의 동치입니다.
아무 조건 없이 상삼각으로 수렴하지는 않습니다. \(F=\begin{pmatrix}0&1\\1&0\end{pmatrix}\)는 고윳값의 절댓값이 모두 1입니다. \(Q=F\), \(R=I\)로 QR을 택하면 다음도 \(F\)여서 소거할 성분이 줄지 않습니다. 또한 멱방법에서 목표 고유벡터 성분이 0이면 그 방향을 생성하지 못하듯, 블록 부분공간 반복에도 초기 부분공간의 조건이 필요합니다.
7. 이동과 수축을 실제로 적용하기#
이동 QR은 \(A_{k-1}-\mu_kI=Q_kR_k\), \(A_k=R_kQ_k+\mu_kI\)입니다. 이동 후에도 \(A_k=Q_k^TA_{k-1}Q_k\)여서 고윳값은 그대로입니다. 마지막 대각 근처의 고윳값을 이동으로 쓰면 그 방향의 분리를 빠르게 할 수 있습니다.
대칭 삼중대각의 마지막 \(2\times2\) 블록이 \(\begin{pmatrix}a&b\\b&d\end{pmatrix}\)이면 Wilkinson 이동은 그 블록의 두 고윳값 중 \(d\)에 가까운 것입니다. \(\delta=(a-d)/2\)에 대해 안정적인 식은
\(b=0\)이면 이미 분리되어 이동 없이 수축합니다. \(\delta=0\), \(b\ne0\)이면 두 고윳값까지 거리가 같아 위 식이 한쪽을 일관되게 선택합니다. \(F\)에서는 Rayleigh 이동 \(\mu=d=0\)이 정체를 그대로 두지만 Wilkinson 이동은 \(-1\)을 선택합니다.
마지막 아래 대각 \(\beta\)가 작으면 그것과 대칭 성분을 0으로 놓아 마지막 \(1\times1\) 블록을 분리합니다. 이를 수축(deflation)이라고 합니다. 이 조작의 행렬 2-노름 변화는 정확히 \(|\beta|\)입니다. 원래 문제의 규모와 허용오차에 비해 충분히 작을 때 수행하며, 단순히 절대값 \(10^{-6}\) 같은 고정 수를 모든 입력에 쓰지 않습니다.
import numpy as np
import scipy.linalg as la
def symmetric_shifted_qr(A, rtol=1e-13, limit=10000):
A = np.asarray(A, dtype=float)
if not np.allclose(A, A.T):
raise ValueError("대칭행렬이 필요합니다")
T, Z = la.hessenberg(A, calc_q=True)
n = len(A); active = n; history = []; steps = 0
scale = np.linalg.norm(A, 2)
while active > 1:
beta = abs(T[active-1, active-2])
history.append(beta)
local = abs(T[active-2, active-2])+abs(T[active-1, active-1])
threshold = rtol*max(local, np.finfo(float).eps*scale)
if beta <= threshold:
T[active-1, active-2] = T[active-2, active-1] = 0.
active -= 1; continue
if steps >= limit: raise RuntimeError("QR 반복 한도 초과")
a = T[active-2, active-2]; d = T[active-1, active-1]
b = T[active-1, active-2]; delta = (a-d)/2
shift = d-np.copysign(1., delta)*b*(b/(abs(delta)+np.hypot(delta,b)))
q, r = np.linalg.qr(T[:active, :active]-shift*np.eye(active))
T[:active, :active] = r@q+shift*np.eye(active)
T[:active, :active] = (T[:active, :active]+T[:active, :active].T)/2
Z[:, :active] = Z[:, :active]@q
steps += 1
return np.diag(T).copy(), Z, np.array(history), steps
A = np.diag(np.arange(1., 7.))+np.diag(np.ones(5),1)+np.diag(np.ones(5),-1)
values, Z, history, steps = symmetric_shifted_qr(A)
assert np.max(np.abs(np.sort(values)-la.eigvalsh(A))) < 1e-10
assert np.linalg.norm(A@Z-Z*values)/np.linalg.norm(A) < 1e-11
print("이동 QR 단계 수:", steps)
이동 QR 단계 수: 10
그림 102 수축 전 고정 크기 블록에서 이동 효과를 비교한다. 완성 솔버는 작은 아래 대각을 발견하면 활성 크기를 줄인다. 그림의 급감 구간만으로 일반 QR의 전역 3차 수렴을 주장하지 않는다.#
비대칭 실수 Hessenberg에서는 복소 켤레 이동을 둘씩 묶어 실수 연산으로 적용하는 Francis 이중이동을 사용합니다. 두 이동의 합과 곱은 실수이므로 \(p(H)=H^2-sH+tI\)의 첫 열로 출발해 생긴 작은 띠 밖 성분을 아래로 이동시키며 제거합니다. 이 암묵 구현의 전체 코드와 전역 수렴 분석은 전문 알고리즘의 조망이며, 위 대칭 솔버를 일반 비대칭 QR이라고 부르지 않습니다.
대칭 삼중대각의 고윳값을 구하는 다른 방법으로 이분법, 분할정복, MRRR, Jacobi 계열이 있습니다. 모든 벡터가 필요한지, 구간 안의 값만 필요한지에 따라 비용·저장·상대정확도 요구가 달라집니다. 구체적인 라이브러리 호출에서는 SciPy의 eigh 드라이버 문서의 적용 범위를 확인합니다.
8. B가 특이한 일반화 문제는 비율 두 개로 기록한다#
\(Ax=\lambda Bx\)에서 \(B^{-1}A\)를 만들면 \(B\)가 특이한 모형을 버리게 됩니다. \(A=\operatorname{diag}(1/2,2,1)\), \(B=\operatorname{diag}(1,1,0)\)는 \(\det(A-\lambda B)=(1/2-\lambda)(2-\lambda)\)인 정칙 펜슬입니다. 유한 고윳값은 \(1/2,2\)이고 세 번째 방향은 무한 고윳값입니다.
QZ는 \(Q^*AZ=S\), \(Q^*BZ=T\)를 삼각 또는 실 준삼각으로 만듭니다. 복소 삼각형에서는 \((\alpha_i,\beta_i)=(s_{ii},t_{ii})\)를 보관하고 \(\beta_i\ne0\)일 때 \(\lambda_i=\alpha_i/\beta_i\)라고 읽습니다. \(\beta_i=0\), \(\alpha_i\ne0\)이면 무한 고윳값입니다. \((0,0)\)은 정칙 펜슬의 정상적인 무한 고윳값이 아니므로 별도 진단이 필요합니다. LAPACK의 일반화 고유문제 설명도 두 수와 정칙성 조건을 구분합니다.
이 예에서 단위원 안의 방향만 앞으로 옮기면 \(e_1\)입니다. 그러나 일반 \(Z\)의 열들은 오른쪽 감소부분공간(deflating subspace)을 나타내며, 동시에 왼쪽 공간 \(Q\)도 관계에 들어갑니다. 고윳값 개수만으로 경제모형의 정책함수 존재·유일성을 판정할 수는 없고 변수 분할과 해당 블록의 계수 조건을 확인해야 합니다. 확률적 기대모형의 추가 조건은 후속 응용 단원에서 다룹니다.
9. 연습과 전체 풀이#
1. \(H\)의 멱방법을 \(v_0=q_-\)에서 시작하면 어떻게 되나요?
풀이. \(Hq_-=q_-\)이므로 모든 정규화 반복이 \(q_-\)입니다. 최대 고윳값이 단순하고 절댓값이 크다는 조건만으로 충분하지 않습니다. 초기벡터의 목표 성분도 비영이어야 합니다.
2. \(p(z)=(z-1)(z-2)(z-3)\)의 상수항에 \(\eta\)를 더할 때 근 2의 1차 변화를 구하세요.
풀이. \(p'(2)=(2-1)(2-3)=-1\)이고 \(\delta p(2)=\eta\)이므로 \(\delta\lambda=\eta\)입니다. 이는 충분히 작은 \(\eta\)의 1차식이며 유한한 변화에서의 정확한 등식은 아닙니다.
3. \(p(z)=z^3-6z^2+11z-6\)의 동반행렬을 쓰고 특성다항식을 확인하세요.
풀이. \(C=\begin{pmatrix}0&0&6\\1&0&-11\\0&1&6\end{pmatrix}\)입니다. \(\det(zI-C)=\det\begin{pmatrix}z&0&-6\\-1&z&11\\0&-1&z-6\end{pmatrix}=z(z(z-6)+11)-6=p(z)\)입니다.
4. 대칭 삼중대각의 마지막 \(\beta\)를 0으로 놓는 변화의 스펙트럼노름을 구하세요.
풀이. 변화는 마지막 두 좌표의 \(\begin{pmatrix}0&-\beta\\-\beta&0\end{pmatrix}\) 블록이고 다른 성분은 0입니다. 그 고윳값은 \(\pm|\beta|\)이므로 2-노름은 \(|\beta|\)입니다. 대칭 Weyl 정리에서 정렬된 모든 고윳값의 변화가 이 값 이하입니다.
5. \(A=\begin{pmatrix}1&M\\0&1+g\end{pmatrix}\)에 \(\eta E_{21}\)을 더한 고윳값을 구하세요.
풀이. 특성식은 \((\lambda-1)(\lambda-1-g)-M\eta=0\)입니다. 완전제곱을 만들면 \(\lambda=1+g/2\pm\sqrt{g^2/4+M\eta}\)입니다. \(M\eta\)가 \(g^2\)에 비해 작을 때만 제곱근을 1차 전개할 수 있습니다. \(M=10^8\), \(g=10^{-8}\), \(\eta=10^{-16}\)에서는 \(M\eta=10^{-8}\gg g^2\)여서 이동 규모는 \(10^{-4}\)이며 1차 조건수 예측의 적용 영역을 벗어납니다.
6. 위 일반화 대각 펜슬의 유한 고유쌍 잔차를 나눗셈 없이 쓰세요.
풀이. 후보 \((\alpha,\beta,v)\)에 대해 \(r=\beta Av-\alpha Bv\)입니다. 첫 방향은 \((\alpha,\beta,v)=(1/2,1,e_1)\), 셋째 무한 방향은 \((1,0,e_3)\)이고 둘 다 잔차 0입니다. 분모가 0인 비율을 먼저 만들어 무한대와 벡터를 곱할 필요가 없습니다.
7. 대칭행렬에서 Rayleigh 몫의 방향 도함수를 구하세요.
풀이. \(\rho(x)=x^TAx/(x^Tx)\)에 몫의 미분을 쓰면 \(d\rho(x)[h]=2h^T(Ax-\rho(x)x)/(x^Tx)\)입니다. 모든 \(h\)에서 0일 필요충분조건은 \(Ax=\rho(x)x\)입니다. 대칭성이 없으면 분자의 미분에 \(A+A^T\)가 나타나므로 같은 결론을 그대로 쓸 수 없습니다.
10. 지금까지의 내용을 수학의 언어로 정리해 봅시다#
존재 정리, 반복의 수렴, 계산 잔차의 의미는 서로 다른 층입니다. 아래 정리에는 각각 필요한 조건을 붙입니다. 알고리즘의 구체적인 부동소수점 동작은 실행 코드와 함께 읽습니다.
정리 1. 대칭행렬의 멱방법과 국소 Rayleigh 반복#
실 대칭 \(A\)의 고윳값이 \(|\lambda_1|>|\lambda_2|\ge\cdots\)이고 초기벡터의 \(q_1\) 성분이 비영이면 정규화한 멱방법의 고유직선까지 각도는 \(O(|\lambda_2/\lambda_1|^k)\)로 작아집니다. 단순 고윳값 \(\lambda_1\) 근처의 Rayleigh 몫 역반복은 역이 존재하는 단계들에서 국소 3차 수렴합니다.
증명. \(v_0=\sum c_iq_i\), \(c_1\ne0\)이면 \(A^kv_0=\lambda_1^kc_1(q_1+\sum_{i>1}(c_i/c_1)(\lambda_i/\lambda_1)^kq_i)\)입니다. 직교성에서 각도의 탄젠트는 뒤 계수들의 제곱합 제곱근이며 \(\sqrt{\sum_{i>1}|c_i/c_1|^2}|\lambda_2/\lambda_1|^k\) 이하입니다. 부호가 교대할 수 있으므로 벡터 자체가 아니라 직선을 말합니다.
Rayleigh 반복에는 목표와 나머지의 간극 \(g=\min_{i>1}|\lambda_i-\lambda_1|>0\), \(L=\max_{i>1}|\lambda_i-\lambda_1|\)를 둡니다. 단위벡터 \(v=c_1q_1+\sum_{i>1}c_iq_i\)에서 \(\sin^2\theta=\sum_{i>1}|c_i|^2\)이고 \(|\mu-\lambda_1|=|\sum_{i>1}(\lambda_i-\lambda_1)|c_i|^2|\le L\sin^2\theta\)입니다. 이 값이 \(g/2\) 미만이면 모든 \(i>1\)에서 \(|\lambda_i-\mu|\ge g/2\)입니다. 역반복한 계수의 비를 제곱합하면
충분히 작은 초기각에서는 이것이 다음 각을 더 작게 하므로 같은 영역에 머뭅니다. 역이 없는 단계는 이 명제의 가정 밖이며 잔차 검사와 이동 수정이 필요합니다. ∎
정리 2. 실 Schur와 Hessenberg 축약의 존재#
모든 실수 정사각행렬은 실 직교 닮음으로 \(1\times1\), \(2\times2\) 대각블록의 준상삼각형이 됩니다. 또한 고윳값을 구하지 않고 유한 번의 Householder 닮음으로 Hessenberg형을 얻습니다.
증명. 실 고윳값이 있으면 그 실 고유벡터를 첫 직교기저벡터로 잡아 첫 열 아래를 0으로 만들고 남은 차수에 귀납합니다. 실 고윳값이 없으면 복소 고유쌍 \(A(u+iv)=(a+ib)(u+iv)\), \(b\ne0\)를 택합니다. 실·허수부를 나누면 \(Au=au-bv\), \(Av=bu+av\)이므로 \(\operatorname{span}_{\mathbb R}(u,v)\)가 불변입니다. \(u,v\)가 종속이면 실 직선 위에 비실수 고윳값이 작용해야 하므로 모순이며 둘은 독립입니다. 이 평면의 직교기저를 전체로 확장하면 좌하단이 0인 \(2\times2\) 블록을 얻습니다. 나머지 실 정사각 블록에 귀납하면 됩니다.
Hessenberg 축약의 \(k\)번째 단계에서는 좌표 \(k+1,\ldots,n\)에서만 작용하는 Householder를 택해 \(k\)번째 열의 \(k+2\)행 이하를 없앱니다. 같은 변환을 오른쪽에도 곱합니다. 오른쪽 곱은 앞 \(k\)열을 건드리지 않으며, 왼쪽 곱의 작용영역에서 이전 열들은 모두 0이므로 그 0을 보존합니다. 귀납적으로 구조가 완성됩니다. 대칭은 직교 닮음으로 보존되므로 대칭 Hessenberg는 삼중대각입니다. ∎
정리 3. QR와 직교반복의 동치 및 부분공간 수렴#
가역 \(A\)의 무이동 QR을 양의 \(R\) 대각 규약으로 수행하면
특히 \(Z_k\)의 첫 \(p\)열은 \(A^k[e_1,\ldots,e_p]\)와 같은 열공간입니다. 대칭 \(A\)에서 고윳값을 절댓값 내림차순으로 정렬하고 \(|\lambda_p|>|\lambda_{p+1}|\)이며 \(Q_1^T[e_1,\ldots,e_p]\)가 가역이면 이 부분공간은 상위 고유공간으로 수렴합니다.
증명. 첫 등식은 매 단계의 닮음식을 이어 곱한 것입니다. \(A Z_{k-1}=Z_{k-1}A_{k-1}=Z_{k-1}Q_kR_k=Z_kR_k\)입니다. 이 관계에 귀납을 적용하면 거듭제곱 식을 얻습니다. 오른쪽 삼각곱의 선행 \(p\times p\) 블록이 가역이고 첫 \(p\)열 아래가 0이므로 열공간도 같습니다.
대칭 분해 \(A=[Q_1,Q_2]\operatorname{diag}(\Lambda_1,\Lambda_2)[Q_1,Q_2]^T\)를 쓰겠습니다. \(E_p=[e_1,\ldots,e_p]\)에 대해 \(C_1=Q_1^TE_p\)가 가역이라는 가정 아래, \(A^kE_p\)에 오른쪽 가역행렬 \(C_1^{-1}\Lambda_1^{-k}\)를 곱하면 같은 공간의 기저
를 얻습니다. \(\|F_k\|_2\le\|(Q_2^TE_p)C_1^{-1}\|_2|\lambda_{p+1}/\lambda_p|^k\to0\)입니다. 이 그래프 기저의 각 벡터는 상위 공간 성분에 비해 수직 성분이 이 값 이하이므로 최대 주각의 탄젠트도 같은 상한을 만족합니다. 이로써 수렴 조건과 비율을 함께 확인했습니다. 모든 \(p\)에서 가정이 성립하면 기저가 고유직선들에 가까워져 아래 대각 성분들이 사라집니다. ∎
정리 4. 고유쌍 잔차의 후진오차와 대칭 오차 인증#
\(\|v\|_2=1\), \(r=Av-\mu v\)이면 \(E=-rv^*\)에 대해 \((A+E)v=\mu v\), \(\|E\|_2=\|r\|_2\)입니다. \(A\)가 자기수반이면 어떤 고윳값 \(\lambda\)에 대해 \(|\lambda-\mu|\le\|r\|_2\)입니다. 목표 \(\lambda_j\) 외의 모든 고윳값과 \(\mu\) 사이 거리가 \(g>0\)이면 그 고유공간 밖 성분의 노름은 \(\|r\|/g\) 이하입니다.
증명. \(Ev=-r(v^*v)=-r\)이므로 첫 식이고 rank-one 노름은 두 벡터 노름의 곱입니다. 자기수반 고유기저에서 \(v=\sum c_iq_i\)이면 \(\|r\|^2=\sum|\lambda_i-\mu|^2|c_i|^2\ge\min_i|\lambda_i-\mu|^2\)입니다. 마지막 주장은 목표 밖의 항들만 남겨 \(\|r\|^2\ge g^2\sum_{i\ne j}|c_i|^2\)로 얻습니다. 중복 목표 고윳값에서는 그 전체 고유공간 밖을 합합니다. ∎
정리 5. 정칙 펜슬의 QZ 비율#
정칙 \((A,B)\)의 복소 일반화 Schur 형 \(Q^*AZ=S\), \(Q^*BZ=T\)에서 유한 고윳값은 \(s_{ii}/t_{ii}\) (\(t_{ii}\ne0\))이고 \(t_{ii}=0\)이면 반드시 \(s_{ii}\ne0\)입니다.
증명. H7의 일반화 Schur 정리로 분해가 존재합니다. 행렬식에 가역 좌우 인자를 적용하면 \(\det(A-\lambda B)\)는 비영 상수에 \(\prod_i(s_{ii}-\lambda t_{ii})\)를 곱한 것입니다. \((s_{ii},t_{ii})=(0,0)\)이면 이 다항식이 항등적으로 0이 되어 정칙성에 모순입니다. 비영 \(t_{ii}\)는 일차인자 하나를, 영 \(t_{ii}\)는 상수인자를 만듭니다. 따라서 유한 근과 \(n-\deg\det(A-\lambda B)\)개의 무한 고윳값을 얻습니다. ∎
고유문제의 반복은 불변부분공간을 근사하며 잔차로 결과를 점검합니다. 다음 장에서는 같은 분해와 축약의 원리를 SVD, 행렬지수, 행렬방정식에 적용합니다. N6로 이어 읽기.