역반복

수치해석에서는 역반복(역동력법이라고도 함)이 반복적인 고유값 알고리즘이다.해당 고유값에 대한 근사가 이미 알려진 경우 대략적인 고유 벡터를 찾을 수 있다.그 방법은 개념적으로 동력법과 유사하다.그것은 원래 구조 역학 분야에서 공명 주파수를 계산하기 위해 개발된 것으로 보인다.^[1]

역출력 반복 알고리즘은 원하는 고유 벡터에 해당하는 고유값에 대한 $\mu$ 근사 $\mu$ $\mu$ 과(와) 벡터 $b_{0}$ $b_{0}$ ${\$ 임의로 선택된 벡터 또는 고유벡터에 대한 근사치로 시작한다.방법은 반복에 의해 설명된다.

b_{k+1}={\frac {(A-\mu I)^{-1b_{k}}{C_{k}}}

where $C_{k}$ are some constants usually chosen as $C_{k}=\ (A-\mu I)^{-1}b_{k}\ .$ Since eigenvectors are defined up to multiplication by constant, the choice of $C_{k}$ can be arbitrary in theory; practical aspects of the $C_{k}$ $C_{k}$ ${\$ 의 선택은 다음과 같다 $C_{k}$ .null

반복할 때마다 벡터 $b_{k}$ $b_{k}$ ${\$ 에 매트릭스 $(A-\mu I)^{-1}$ - $(A-\mu I)^{-1}$ $(A-\mu I)^{-1}$ ) $(A-\mu I)^{-1}$ - $(A-\mu I)^{-1}$ ${\$ 를 곱하고 $b_{k}$ $(A-\mu I)^{-1}$ 정규화한다.행렬 $A$ $A$ 을 $A$ $(A-\mu I)^{-1}.$ - $(A-\mu I)^{-1}.$ ) $(A-\mu I)^{-1}.$ - 1 $(A-\mu I)^{-1}.$ . $(A-\mu I)^{-1}.$ {\ $displaystyle(A-\mu$ I $)^{-1}}}$ 로 대체한 것을 제외하면 전원법과 정확히 같은 공식이지만 고유값에 근사치 $\mu$ ${\displaystyle \mu$ }을 $($ 를 $\mu$ )를 선택할수록 $(A-\mu I)^{-1}.$ 알고리즘의 수렴 속도가 빨라진다 $.$ $tyle \mu }$ 은(는) 느린 수렴 또는 원하는 고유 벡터 이외의 고유 벡터에 대한 수렴으로 이어질 수 있다 $\mu$ .실제로 이 방법은 고유값에 대한 좋은 근사치가 알려져 있을 때 사용되며, 따라서 몇 번(보통 단 한 번만) 반복하면 된다.null

이론과 수렴

동력 반복의 기본 개념은 초기 벡터 $b$ ${\displaystyle$ b $}($ 유전 벡터 근사치 또는 무작위 벡터)를 선택하고 반복적으로 A $Ab,A^{2}b,A^{3}b,...$ $Ab,A^{2}b,A^{3}b,...$ $Ab,A^{2}b,A^{3}b,...$ $Ab,A^{2}b,A^{3}b,...$ A $Ab,A^{2}b,A^{3}b,...$ $Ab,A^{2}b,A^{3}b,...$ . $Ab,A^{2}b,A^{3}b,...$ . . ${\displaysty Ab,$ $A^{2}b, A^{3}b,...$ $Ab,A^{2}b,A^{3}b,...$ 0 측정의 집합을 제외하고, 어떤 초기 벡터에 대해서도 결과는 지배적인 고유값에 해당하는 고유 벡터로 수렴된다.null

The inverse iteration does the same for the matrix $(A-\mu I)^{-1}$ , so it converges to the eigenvector corresponding to the dominant eigenvalue of the matrix $(A-\mu I)^{-1}$ . Eigenvalues of this matrix are $(\lambda _{1}-\mu )^{-1},...,(\lambda _{n}-\mu )^{-1},$ $(\lambda _{1}-\mu )^{-1},...,(\lambda _{n}-\mu )^{-1},$ $(\lambda _{1}-\mu )^{-1},...,(\lambda _{n}-\mu )^{-1},$ , ${\displaystyle (\lambda _{1}-\mu )^{-1$ }, $...,$ (\ $lambda _{n$ $}-\mu )^{1},$ 여기서 $(\lambda _{1}-\mu )^{{-1}},...,(\lambda _{n}-\mu )^{{-1}},$ $\lambda _{i}$ λ $\lambda _{i}$ 는 $A$ $A$ 의 고유값이다 $A$ 이 숫자 중 가장 큰 숫자는 가장 작은 ( $(\lambda _{1}-\mu ),...,(\lambda _{n}-\mu ).$ 1 $(\lambda _{1}-\mu ),...,(\lambda _{n}-\mu ).$ - $(\lambda _{1}-\mu ),...,(\lambda _{n}-\mu ).$ ) $(\lambda _{1}-\mu ),...,(\lambda _{n}-\mu ).$ , $(\lambda _{1}-\mu ),...,(\lambda _{n}-\mu ).$ . . . . $(\lambda _{1}-\mu ),...,(\lambda _{n}-\mu ).$ . . . . . . $(\lambda _{1}-\mu ),...,(\lambda _{n}-\mu ).$ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . $.\displaystyle (\lambda _{1}-\mu$ ) . . . . $(\lambda _{1}-\mu ),...,(\lambda _{n}-\mu ).$ . . . . . . . . . . . . . . . . . . . . . . . . $(\lambda _{1}-\mu ),...,(\lambda _{n}-\mu ).$ $A$ $A$ 과 $A$ $(A-\mu I)^{-1}$ - $(A-\mu I)^{-1}$ ) $(A-\mu I)^{-1}$ - $(A-\mu I)^{-1}$ 의 고유 벡터 $(A-\mu$ I $)^{-1}$ 는 동일하므로 $(A-\mu I)^{-1}$

$Av=\lambda v\leftrightarrow (A-\mu I)v=\lambda v-\mu v\leftrightarrow (\lambda -\mu )^{-1}v=(A-\mu I)^{-1v$

결론:메소드는 μ에 가장 가까운 $A$ 고유값에 $A$ 하는매트릭스 A {\ $displaystyle$ A}의 고유 벡터로 수렴된다 $\mu .$ $\mu .$

In particular, taking $\mu =0$ we see that $(A)^{-1}b_{k}$ converges to the eigenvector corresponding to the eigenvalue of $A^{-1}$ with the largest magnitude ${\frac {1}{\lambda _{N}}}$ and thus can be used to 반비례하므로 $A$ $A$ {\ $displaystyle A}$ 의 최소 크기 고유값을 결정한다.null

수렴 속도

그 방법의 수렴 속도를 분석해보자.null

동력법은 한계에 선형적으로 수렴하는 것으로 알려져 있으며, 보다 정밀하게 다음과 같다.

$\mathrm {Distance}(b^{\mathrm {ideal} },b_{\mathrm {Power~Method} }^{k})=O\왼쪽(\왼쪽 {\frac {\lambda _{\mathrm {subdominant}}{\lambda }}{\mathrm {dominant}}}}}}오른쪽 ^{k}\right),}$

따라서 역반복법의 경우 유사한 결과가 다음과 같이 들린다.

$\mathrm {Distance}(b^{\mathrm {ideal} },b_{\mathrm {Inverse~반복} }^{k})=O\왼쪽(\frac {\mu -\lambda _{\mathrm {closest~to~} \mathrm }{{\mu -\lambda _}{\mathrm {seconds~closest~}\}\right ^{k}\rig}\rig}\right)$

이것은 방법의 정합성을 이해하는 핵심 공식이다.It shows that if $\mu$ is chosen close enough to some eigenvalue $\lambda$ , for example $\mu -\lambda =\epsilon$ each iteration will improve the accuracy ${\displaystyle \epsilon / \lambda +\epsi$ $lon$ - $\bodda _{\mathrm$ { ${~to~} \lambda }}$ 번 $|\epsilon |/|\lambda +\epsilon -\lambda _{\mathrm {closest~to~} \lambda }|$ . $({\displaystyle \epsilon }$ $\epsilon$ "closest to $\mu$ ${\displaystyle \mu$ $\mu$ 및 "closest to $\lambda$ ${\displaystyle \lambda$ $\lambda$ 에 대해 이 값을 $\epsilon$ 한다.)For small enough $\epsilon$ it is approximately the same as $\epsilon / \lambda -\lambda _{\mathrm {closest~to~} \lambda }$ . Hence if one is able to find $\mu$ , such that the ${\displaystyle \epsi$ $lon }$ 은(는) 충분히 작을 것이고 $\epsilon$ , 그러면 아주 적은 반복이 만족스러울 것이다.null

복잡성

역반복 알고리즘은 선형 시스템을 풀거나 역행렬을 계산해야 한다.구조화되지 않은 매트릭스(Toeplitz가 아닌 경우...)의 경우 $O(n^{3})$ O ( $O(n^{3})$ 3 ) ${\displaystyle O(n^{3})$ 연산이 $O(n^{3})$ 필요하다.null

구현 옵션

방법은 다음 공식으로 정의된다.

b_{k+1}={\frac {(A-\mu I)^{-1b_{k}}{C_{k}}}

그러나 그것의 구현에는 여러 가지 옵션이 있다.null

역행렬 계산 또는 선형 방정식 해결

공식을 다음과 같은 방법으로 다시 쓸 수 있다.

(A-\mu I)b_{k+1}={\frac {b_{k}}{C_{k}}}

다음 근사 b $b_{k+1}$ + $b_{k+1}$ ${\$ 를 찾기 위해 선형 $b_{k+1}$ 방정식의 시스템을 해결할 수 있음을 강조한다.두 가지 옵션이 있는데, 하나는 선형 시스템을 해결하는 알고리즘을 선택할 수도 있고, 하나는 역 $(A-\mu I)^{-1}$ - $(A-\mu I)^{-1}$ I $(A-\mu I)^{-1}$ ) $(A-\mu I)^{-1}$ - $(A-\mu I)^{-1}$ ${\$ 를 계산하여 $(A-\mu I)^{-1}$ 벡터에 적용할 수도 있다.두 옵션 모두 복잡성 O(n³)를 가지며, 정확한 숫자는 선택한 방법에 따라 달라진다.null

선택은 또한 반복 횟수에 따라 달라진다.순진하게, 각 반복에서 선형 시스템을 해결할 경우 복잡성은 k*O(n³)가 될 것이며, 여기서 k는 반복의 수입니다. 마찬가지로 역행렬을 계산하여 각 반복에 적용하는 것은 복잡성 k*O(n³)이다.그러나 고유값 추정 $\mu$ $\mu$ 이(가) 일정하게 유지되면 $\mu$ 두 방법 중 하나를 사용하여 복잡성을 O(n³) + k*O(n²)로 줄일 수 있다는 점에 유의하십시오.역행렬을 한 번 계산하여 각 반복에 적용하기 위해 저장하는 것은 복잡성 O(n³) + k*O(n²)이다. $(A-\mu I)$ - $(A-\mu I)$ I $(A-\mu I)$ ) ${\displaystyle (A-\mu$ I $)}$ 의 LU 분해물을 저장하고 $(A-\mu I)$ 각 반복에서 방정식 시스템을 해결하기 위해 전방과 후방 치환법을 사용하는 것도 복잡성 O(n³) + k*O(n²)이다.null

매트릭스를 뒤집는 것은 일반적으로 초기 비용이 더 크지만 각 반복에서 비용이 더 낮다.반대로, 선형 방정식의 시스템 해결은 일반적으로 초기 비용이 덜 들지만, 각 반복에 더 많은 연산이 필요하다.null

트리디각형화, 헤센베르크 형태

만일 많은 반복(또는 몇 번의 반복이 필요하지만, 많은 고유 벡터의 경우)을 수행해야 한다면, 먼저 행렬을 위쪽 헤센베르크 양식으로 가져오는 것이 현명할 수 있다(대칭 행렬의 경우 이것은 삼지각형 형태일 것이다).어느 O(n2){\displaystyle{\begin{행렬}{\frac{10}{3}}\end{매트릭스}}n^ᆮ+O(n^{2})}산술 연산자, 직교 유사성 변환의 양면 QR분해 다소 유사한 유한 수열과 기술 하우스 홀더 감축에)을 이용하여+103n3비용이 든다.[2][3](QR분해의 경우, Househol.데르 회전은 왼쪽에만 곱하지만, 헤센베르크의 경우에는 왼쪽과 오른쪽 모두에 곱한다.)대칭 행렬의 경우 이 절차는 4 ${\begin{matrix}{\frac {4}{3}}\end{matrix}}n^{3}+O(n^{2})$ 3 ${\begin{matrix}{\frac {4}{3}}\end{matrix}}n^{3}+O(n^{2})$ + O ${\begin{matrix}{\frac {4}{3}}\end{matrix}}n^{3}+O(n^{2})$ ${\begin{matrix}{\frac {4}{3}}\end{matrix}}n^{3}+O(n^{2})$ ) ${\displaystyle {\begin{matrix}{4}{3}}\end{matrix}}{3}+O(n^{2})$ 의 산술 ${\begin{matrix}{\frac {4}{3}}\end{matrix}}n^{3}+O(n^{2})$ 연산이 필요하다.^[2]^[3]null

3각형 매트릭스에 대한 선형 방정식 시스템의 $O(n)$ 은 $O(n)$ O ( $O(n)$ ) $O(n)$ {\ $displaystyle$ O( $n)}$ 연산 비용이 $O(n)$ 들기 때문에 $O(n^{3})+kO(n)$ 은 $O(n^{3})+kO(n)$ O ( $O(n^{3})+kO(n)$ 3 $O(n^{3})+kO(n)$ ) + $O(n^{3})+kO(n)$ ( $O(n^{3})+kO(n)$ ${\displaystyle O(n$ ^{ $3})+kO(n)}$ 처럼 $O(n^{3})+kO(n)$ 커지는데 $k$ 서 k{\ $displaystysty k}$ 은 $k$ 직접 반전보다 낫다.그러나 그러한 변환은 거의 반복되지 않을 수 있다.null

또한 헤센베르크 양식으로의 변환은 정사각형의 뿌리와 분업작전을 수반하는데, 이는 하드웨어에 의해 보편적으로 지지되지 않는다.null

정규화 상수 $C_{k}$ $C_{k}$ ${\$ 선택

범용 프로세서(예: Intel에서 생산)에서 추가, 곱하기 및 나누기의 실행 시간은 대략 동일하다.그러나 임베디드 및/또는 저에너지 소비 하드웨어(디지털 신호 프로세서, FPGA, ASIC) 부문은 하드웨어에서 지원되지 않을 수 있으므로 이를 피해야 한다. $C_{k}=2^{n_{k}}$ $C_{k}=2^{n_{k}}$ = $C_{k}=2^{n_{k}}$ ${\$ 을 선택하면 명시적인 하드웨어 지원 없이 빠르게 분할할 수 있는데 $C_{k}=2^{n_{k}}$ , 2의 힘으로 분할하면 (고정점 산술의 경우) 지수에서 $k$ $k$ $k$ 의 뺄셈으로 구현될 수 있기 때문이다.null

고정점 산술법을 사용하여 알고리즘을 구현할 때는 상수 $C_{k}$ k ${\$ 의 선택이 특히 중요하다 $C_{k}$ .값이 작으면 $b_{k}$ $b_{k}$ ${\$ 의 규범이 빠르게 성장하고 $b_{k}$ 오버플로가 발생하며 $C_{k}$ , $C_{k}$ $C_{k}$ ${\$ 의 큰 값은 벡터 $b_{k}$ ${\$ 을 0으로 향하게 $b_{k}$ 된다.null

사용법

이 방법의 주된 적용은 고유값에 대한 근사치가 발견되고 그에 상응하는 근사치 고유벡터를 찾아야 하는 상황이다.그러한 상황에서 역반복은 주된 방법이며 아마도 유일한 방법일 것이다.null

대략적인 고유값을 찾는 방법

일반적으로 이 방법은 대략적인 고유값을 찾는 다른 방법과 조합하여 사용된다. 표준 예는 이분법 고유값 알고리즘이고, 다른 예는 Rayleigh quotient iteration이며, 이는 실제로 Rayleigh quotient의 선택과 그에 상응하는 Rayleigh quotient의 선택과 동일한 역반복이다.반복의 전 단계에서 얻은 벡터null

그 방법을 스스로 사용할 수 있는 상황도 있지만, 상당히 한계적이다.null

지배적 고유값에 대한 근사값으로서의 행렬의 정규

지배적인 고유값은 모든 행렬에 대해 쉽게 추정할 수 있다.유도된 규범에 대해 $\left\|A\right\|\geq |\lambda |,$ $\left\|A\right\|\geq |\lambda |,$ $\left\|A\right\|\geq |\lambda |,$ $\left\|A\right\|\geq |\lambda |,$ λ $\left\|A\right\|\geq |\lambda |,$ ${\displaystyle$ $\left\A\right\\\geq$ $\lambda$ $\left\|A\right\|\geq |\lambda |,$ $}}.$ 따라서 행렬의 규범을 근사치 $\lambda$ 으로 보면 방법이 지배적인 고유 벡터에 수렴한다는 것을 알 수 있다 $\lambda$ null

통계에 기반한 추정치

일부 실시간 애플리케이션에서는 초당 수백만 개의 행렬 속도를 가진 행렬에 대한 고유 벡터를 찾아야 한다.그러한 응용 프로그램에서는 일반적으로 행렬의 통계가 미리 알려져 있으며, 일부 큰 행렬 표본의 평균 고유값을 대략적인 고유값으로 취할 수 있다.더 나은 것은 추적 또는 행렬의 규범에 대한 고유값의 평균 비율을 계산하고 추적 또는 규범에 해당 비율의 평균 값을 곱한 평균 고유값을 추정할 수 있다.분명히 그러한 방법은 재량적으로만 사용할 수 있고, 높은 정밀도가 중요하지 않은 경우에만 사용할 수 있다.평균 고유값을 추정하는 이 접근법은 지나치게 큰 오차를 피하기 위해 다른 방법과 결합할 수 있다.null

참고 항목

참조

^ Ernst Pohlhausen, Berechnung der Eigenschwingungen-bestimt Fachwerke, ZAMM - Zeitschrift für Angelwandte Mathik 1, 28-42 (1921)
^ ^a ^b Demmel, James W. (1997), Applied Numerical Linear Algebra, Philadelphia, PA: Society for Industrial and Applied Mathematics, ISBN 0-89871-389-7, MR 1463942.
^ ^a ^b 로이드 N.Trefethen과 David Bau, 수치 선형 대수(SIAM, 1997).

[Pohlhausen-1] Ernst Pohlhausen, Berechnung der Eigenschwingungen-bestimt Fachwerke, ZAMM - Zeitschrift für Angelwandte Mathik 1, 28-42 (1921)

[Demmel-2] Demmel, James W. (1997), Applied Numerical Linear Algebra, Philadelphia, PA: Society for Industrial and Applied Mathematics, ISBN 0-89871-389-7, MR 1463942.

[Trefethen-3] 로이드 N.Trefethen과 David Bau, 수치 선형 대수(SIAM, 1997).

[1]

[2]

[3]

v t 수치 선형대수학
주요개념	부동소수점 수치안정성
문제	선형 방정식 체계 매트릭스 분해 행렬 곱하기(알고리즘) 행렬 분할 희소성 문제
하드웨어	CPU 캐시 TLB 캐시-관심 알고리즘 심드 다중 처리
소프트웨어	매트랩 기본 선형 대수 하위 프로그램(BLAS) 라팩 전문 라이브러리 범용 소프트웨어

Search

역반복

네임스페이스

더

목차