모든 단일 대칭 분해를 수행하여 많은 실제 대칭 50×50 행렬의 최대 고유 값을 계산하는 프로그램이 있습니다. SVD는 프로그램의 병목 현상입니다.
가장 큰 고유 값을 찾는 데 훨씬 더 빠른 알고리즘이 있습니까?
답변
최대 고유 값에 필요한 정밀도에 따라 Power Iteration을 사용해 볼 수 있습니다.
구체적인 예를 들어, 명시 적으로 작성하지는 않지만 각 반복에서 를 계산합니다. 계산 하려면 연산이 필요하지만 행렬-벡터 곱에는 만 필요합니다 . x ← X ( X T x ) A O ( n 3 ) O ( n 2 )
A=XXTx←X(XTx)
A
O(n3)
O(n2)
수렴 률은 가장 큰 두 고유 값 사이의 분리에 따라 다르므로 모든 경우에 좋은 해결책이 아닐 수 있습니다.
답변
5 개의 고유 값 만 매우 중요한 경우 행렬 벡터로 곱하는 를 사용하는 Lanczsos 알고리즘은 5 개의 초기 단계 후에 빠른 선형 수렴을 제공하므로 반복 횟수가 거의없는 상당히 정확한 고유 값입니다.
X(XTx)답변
와 같은 양의 반 정규 행렬의 경우 스펙트럼 시프트로 수렴을 가속화하는 노력이 필요합니다 . 즉, 적당한 스칼라 μ가 선택되고 전원 방법에 적용 – μ I 대신 .
A=XXT μA−μI
A
||Ax||/||x||
λ1
[0,56λ1]
A−512λ1I
712λ1
[−512λ1,512λ1]
A−μI
λ1
μ
A−μI
(A−μI)x=X(XTx)−μx
O(n2)