태그 보관물: eigensystem

eigensystem

50×50 행렬의 가장 큰 고유 값을 찾는 SVD – 상당한 시간을 낭비하고 있습니까? 모든 단일

모든 단일 대칭 분해를 수행하여 많은 실제 대칭 50×50 행렬의 최대 고유 값을 계산하는 프로그램이 있습니다. SVD는 프로그램의 병목 현상입니다.

가장 큰 고유 값을 찾는 데 훨씬 더 빠른 알고리즘이 있습니까?



답변

최대 고유 값에 필요한 정밀도에 따라 Power Iteration을 사용해 볼 수 있습니다.

구체적인 예를 들어, 명시 적으로 작성하지는 않지만 각 반복에서 를 계산합니다. 계산 하려면 연산이 필요하지만 행렬-벡터 곱에는 만 필요합니다 . x X ( X T x ) A O ( n 3 ) O ( n 2 )

A=XXT

xX(XTx)

A

O(n3)

O(n2)

수렴 률은 가장 큰 두 고유 값 사이의 분리에 따라 다르므로 모든 경우에 좋은 해결책이 아닐 수 있습니다.


답변

5 개의 고유 값 만 매우 중요한 경우 행렬 벡터로 곱하는 를 사용하는 Lanczsos 알고리즘은 5 개의 초기 단계 후에 빠른 선형 수렴을 제공하므로 반복 횟수가 거의없는 상당히 정확한 고유 값입니다.

X(XTx)


답변

와 같은 양의 반 정규 행렬의 경우 스펙트럼 시프트로 수렴을 가속화하는 노력이 필요합니다 . 즉, 적당한 스칼라 μ가 선택되고 전원 방법에 적용 μ I 대신 .

A=XXT

μ

AμI

A

||Ax||/||x||

λ1

[0,56λ1]

A512λ1I

712λ1

[512λ1,512λ1]

AμI

λ1

μ

AμI

(AμI)x=X(XTx)μx

O(n2)


답변