자코비 고유값 알고리즘

수치 선형대수에서 자코비 고유값 알고리즘은 실제 대칭 행렬의 고유값과 고유 벡터(대각화라고 하는 프로세스)를 계산하기 위한 반복적인 방법이다.1846년 이 방법을 처음 제안한 칼 구스타프 제이콥 자코비(Carl Gustav Jacobi Jacobi)^[2]의 이름을 따서 지었지만,^[1] 1950년대에야 컴퓨터의 등장으로 널리 쓰이게 되었다.

설명.

$S$ $S$ 을(를) 대칭 행렬로 하고 $S$ , $G=G(i,j,\theta )$ = $G=G(i,j,\theta )$ , $G=G(i,j,\theta )$ , $G=G(i,j,\theta )$ ) $G=G(i,j,\theta )$ 을(를) 기븐스 회전 행렬로 한다 $G=G(i,j,\theta )$ .다음:

S'=GSG^{\top }\,

$S$ 이며 S $S$ 과(와) 유사하다 $S$

또한 $′{\$ 에는 다음과 같은 항목이 있다 $S^{\prime }$ .

{\reasoned}S'_{i}&=c^{2}\,S_{i}-2\,sc\,S_{ij}+s^{2}\,S_{j}\S'_{jj}&=s^{2}\,S_{i}+2sc\,S_{ij}+c^{2}\,S_{jj}\\S'_{ij}&=S'_{ji}=(c^{2}-s^{2})\,S_{ij}+sc\,(S_{i}-S_{j})\\S'_{ik}&={ki}=c\,S_{ik}-s\,S_{jk}&k\neq i,j\\S'_{jk}&=S'_{kj}=s\,S_{ik}+c\,S_{jk}&k\neq i,j\\S'_{kl}&=S_{kl}&k,l\neq i,j\end{arged}}

여기서 $s=\sin(\theta )$ = $s=\sin(\theta )$ $s=\sin(\theta )$ ( $s=\sin(\theta )$ ) $s=\sin(\theta )$ 및 $s=\sin(\theta )$ $c=\cos(\theta )$ = $c=\cos(\theta )$ $c=\cos(\theta )$ ( $c=\cos(\theta )$ ${\displaystyle$ c $=\cos(\theta$ $c=\cos(\theta )$

Since $G$ is orthogonal, $S$ and $S^{\prime }$ have the same Frobenius norm $\cdot _{F}$ (the square-root sum of squares of all components), however we can choose $\theta$ such that $S_{ij}^{\prime }=0$ $S_{ij}^{\prime }=0$ $S_{ij}^{\prime }=0$ ${\displaystyle S_{ij}^{\premy }=0$ 이 경우 $S^{\prime }$ $S^{\prime }$ ${\$ 은 대각선에 더 큰 제곱합을 가진다 $S^{\prime }$ .

S'_{ij}=\cos(2\theta )S_{ij}+{\tfrac {1}{1}{1}:{2}}\sin(2\theta)(S_{i}-S_{j}}}}}}}

이 값을 0으로 설정하고 다시 정렬:

\tan(2\theta )={\frac {2S_{ij}}{{nij}}}}{S_{jj}-S_{ii}}}}

$S_{jj}=S_{ii}$ $S_{jj}=S_{ii}$ j $S_{jj}=S_{ii}$ = $S_{jj}=S_{ii}$ $S_{jj}=S_{ii}$ ${\$ 인 경우 $S_{{ii}}}$

\theta ={\frac {\pi }{4}}}

이러한 효과를 최적화하기 위해서는 S가_ij 피벗이라고 하는 가장 큰 절대값을 갖는 비대각 원소가 되어야 한다.

자코비 고유값 방법은 행렬이 거의 대각선이 될 때까지 회전을 반복한다.그러면 대각선의 원소들은 S의 (실제) 고유값의 근사치가 된다.

수렴

If $p=S_{kl}$ is a pivot element, then by definition $S_{ij} \leq p$ for $1\leq i,j\leq n,i\neq j$ . Let $\Gamma (S)^{2}$ denote the sum of squares of all off-diagonal entries of $S$ . Since $S$ has exactly $2N:=n(n-1)$ off-diagonal elements, we have $p^{2}\leq \Gamma (S)^{2}\leq 2Np^{2}$ or ${\displaystyle 2p^{2}\geq \Gamma (S)^{2}/$ $N}$ . Now $\Gamma (S^{J})^{2}=\Gamma (S)^{2}-2p^{2}$ . This implies $\Gamma (S^{J})^{2}\leq (1-1/N)\Gamma (S)^{2}$ or ${\displaystyle \Gamma (S^{$ $J}\leq (1-1/N)^{1/2}\감마 (S)},$ 즉, 자코비 회전 순서는 인자(1 $(1-1/N)^{1/2}$ - $(1-1/N)^{1/2}$ / $(1-1/N)^{1/2}$ ) 1 $(1-1/N)^{1/2}$ / $(1-1/N)^{1/2}$ ${\$ }} 대각 행렬에 의해 $(1-1/N)^{1/2}$ 최소한 선형적으로 수렴된다.

많은 $N$ $N$ 자코비 $N$ 회전을 스위프라고 하는데, $S^{\sigma }$ $S^{\sigma }$ ${\$ S $^{\sigma }}$ 은 결과를 $S^{\sigma }$ 나타낸다.이전 추정치 산출량

\Gamma (S^{\sigma })\leq \left(1-{\frac {1}{N}}\right)^{N/2}\Gamma (S)

(

\Gamma (S^{\sigma })\leq \left(1-{\frac {1}{N}}\right)^{N/2}\Gamma (S)

\Gamma (S^{\sigma })\leq \left(1-{\frac {1}{N}}\right)^{N/2}\Gamma (S)

)

\Gamma (S^{\sigma })\leq \left(1-{\frac {1}{N}}\right)^{N/2}\Gamma (S)

(

\Gamma (S^{\sigma })\leq \left(1-{\frac {1}{N}}\right)^{N/2}\Gamma (S)

-

\Gamma (S^{\sigma })\leq \left(1-{\frac {1}{N}}\right)^{N/2}\Gamma (S)

\Gamma (S^{\sigma })\leq \left(1-{\frac {1}{N}}\right)^{N/2}\Gamma (S)

)

\Gamma (S^{\sigma })\leq \left(1-{\frac {1}{N}}\right)^{N/2}\Gamma (S)

/

\Gamma (S^{\sigma })\leq \left(1-{\frac {1}{N}}\right)^{N/2}\Gamma (S)

\Gamma (S^{\sigma })\leq \left(1-{\frac {1}{N}}\right)^{N/2}\Gamma (S)

\Gamma (S^{\sigma })\leq \left(1-{\frac {1}{N}}\right)^{N/2}\Gamma (S)

\Gamma (S^{\sigma })\leq \left(1-{\frac {1}{N}}\right)^{N/2}\Gamma (S)

{\displaystyle \Gamma (S^{\sigma }}\leq \leq (1-{{{\frac {1}{N}\오른쪽)^{N/2}\Gamma (S

즉, 스위프의 순서는 linear $e^{1/2}$ $e^{1/2}$ / $e^{1/2}$ ${\$ 인자와 최소한 선형적으로 수렴한다. $e^{1/2}$

그러나 쇤네지의^[3] 다음 결과는 국지적으로 2차 정합성을 산출한다. $이$ 를 $\lambda_1, ... , \lambda_m$ $\nu_1, ... , \nu_m$ 위해 S는 m $\lambda _{1},...,\lambda _{m}$ 고유값 $\nu _{1},...,\nu _{m}$ $λ$ $1$ , $\lambda _{1},...,\lambda _{m}$ . $\lambda _{1},...,\lambda _{m}$ . $\lambda _{1},...,\lambda _{m}$ . . . $\lambda _{1},...,\lambda _{m}$ . . . . . . . . . . . $\nu _{1},...,\nu _{m}$ . . . . . $\nu _{1},...,\nu _{m}$ . $\nu _{1},...,\nu _{m}$ . . . . . . . . . . $.$ . . . . . . . . . . . . . . . $.$ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .몇 분만 전화합시다.

N_{S}={\frac {n(n-1)}{2}}-\sum _{\m}{\frac {1}{1}:{1}{1}:{1}{1}}\nu _{\mu _{\nu _{\mu }-1)\leq N

자코비는 쇤네게 스윗을 회전시킨다.S $S^{s}$ ${\$ 이(가) 결과를 나타내는 $S^{s}$ 경우

\Gamma (S^{s})\leq {\sqrt {{\frac {n}{2}}-1}}\left({\frac {\gamma ^{2}}{d-2\gamma }}\right),\quad \gamma :=\Gamma (S)

.

따라서 γ ( $\Gamma (S)<{\frac {d}{2+{\sqrt {{\frac {n}{2}}-1}}}}$ ) $\Gamma (S)<{\frac {d}{2+{\sqrt {{\frac {n}{2}}-1}}}}$ < $\Gamma (S)<{\frac {d}{2+{\sqrt {{\frac {n}{2}}-1}}}}$ d $\Gamma (S)<{\frac {d}{2+{\sqrt {{\frac {n}{2}}-1}}}}$ + $\Gamma (S)<{\frac {d}{2+{\sqrt {{\frac {n}{2}}-1}}}}$ $\Gamma (S)<{\frac {d}{2+{\sqrt {{\frac {n}{2}}-1}}}}$ - $\Gamma (S)<{\frac {d}{2+{\sqrt {{\frac {n}{2}}-1}}}}$ ${\$ }}- $1}}}}}}$ 과(와) 즉시 수렴이 2차적으로 된다.

비용

각 자코비 회전은 피벗 요소 p를 알 때 O(n) 단계로 수행할 수 있다.그러나 p를 검색하려면 모든 N ≈에 대한 검사가 필요하다. 1/2n² 오프더링 요소.m $m_{i}$ ${\$ 이 현재 S행 i에서 가장 큰 원소의 지수인 (i = 1, ..., n - 1)라는 속성으로 $m_{i}$ 추가 $m_{1},\,\dots \,,\,m_{n-1}$ $m_{1},\,\dots \,,\,m_{n-1}$ 어레이 m $m_{1},\,\dots \,,\,m_{n-1}$ , $m_{1},\,\dots \,,\,m_{n-1}$ … $m_{1},\,\dots \,,\,m_{n-1}$ , $m_{1},\,\dots \,,\,m_{n-1}$ - $m_{1},\,\dots \,,\,m_{n-1}$ ${\$ 을 도입하면 이것도 O(n) 복잡도로 줄일 수 있다.그러면 피벗(k, l)의 지수는 쌍( $(i,m_{i})$ , $(i,m_{i})$ m $(i,m_{i})$ ) $displaystyle(i,m_{i})$ 중 하나여야 한다. 또한 인덱스 배열의 업데이트는 O(n) 평균 사례 복잡도로 이루어질 수 있다 $(i,m_{i})$ 먼저 업데이트된 행 k와 l의 최대 입력은 O(n) 단계에서 찾을 수 있다.다른 i행에서는 k 열과 l 열의 항목만 변경된다.이러한 행을 반복하면서 $m_{i}$ $m_{i}$ ${\$ 이 k도 l도 아닌 $m_{i}$ 경우 $m_{i}$ $m_{i}$ ${\$ 의 이전 최대값을 새 항목과 $m_{i}$ 비교하고 필요한 $m_{i}$ $m_{i}$ m $m_{i}$ ${\$ 을(를) 업데이트하면 된다. $m_{i}$ $m_{i}$ ${\$ 이(가) k 또는 l와 같아야 $m_{i}$ 하고 업데이트 중에 해당 항목이 줄어들면 O(n) 복잡도에서 최대 오버 행을 처음부터 찾아야 한다.그러나, 이것은 회전당 평균 한 번만 발생할 것이다.따라서 각 회전은 O(n)와 1회의 스위프 O(n³) 평균 사례 복잡성을 가지며, 이는 하나의 행렬 곱셈에 해당한다.또한 프로세스가 시작되기 전에 m $m_{i}$ ${\$ 를 초기화해야 $m_{i}$ 하며, 이 작업은 n 단계로² 수행할 수 있다.

전형적으로 자코비 방법은 소수의 스위프 후에 수치의 정밀도로 수렴된다. $N_{S}<N$ $N_{S}<N$ 이 $N_{S}<N$ S $N_{S}<N$ < N {\ $displaystyle N_{S$ }<N $}$ 이후 반복 횟수를 줄인다는 점에 유의하십시오 $N_{S}<N$

알고리즘.

다음 알고리즘은 수학과 같은 표기법으로 자코비 방법을 기술한 것이다.고유값을 포함하는 벡터 e와 해당 고유 벡터를 포함하는 행렬 E를 계산한다. 즉 $e_{i}$ ${\$ 는 고유값이며 $e_{i}$ $e_{i}$ ${\$ i = 1, n.

절차 jacobi(S∈ Rn×n;e∈ Rn;E∈ Rn×n)에 분포한다 나는, k, l, m, 주 ∈ Ns, c, t, p, y, d, r∈ Rind ∈ Nn을 바꾸∈은 때때로 기능 maxind(kN∈)∈ N!지수의 큰 비대각 요소에서 행 km:=k+1에 나는:)k+2에 n 한다면│Ski│>│Skm│ 다음 m:=나는 endifendfor 반환 mendfunc 절차 update(kN는 R∈ ∈)!를 업데이트하 ek고. 상태는 y:=ek, ek만약 changedk과(y=ek) 다음 changedk::거짓, 상태:)state−1elsif( 아니changedk)과(y≠ek) 다음 changedk:사실, 상태:)state+1endifendproc 절차 rotate(k,l,i,j ∈ N)=!Sij, Skl의 회전을 수행하 ┌ ┐ ┌ ┐┌ ┐ │Skl│ │c −s││Skl││ │:)│ ││ │ │Sij│ │s c││Sij│ └ ┘ └ ┘└ ┘ = y+t =.   endproc!init e, E,그리고 배열, E를 바꾸었다:=나는, 상태:k에= n:=1nindk을 하기=maxind(k), ek:)Skk, changedk:진정한 endfor =는 동안 state≠0니!다음 회전 m:=1!k에 피벗 p의 지수(k,l)를 찾:=2~n−1 만약│Sk indk│하면, │Sm indm│ 다음 m:\kendifendfor k:=m, 내가:=indm, p:= Skl!ind를 산정하는 c)오리온 φ, s)sinφ는 y:=(el−ek)/2, d:=│y│+.√(p2+y2)r:=√(p2+d2), 요리:=d/r의:=p/r.:)p2/d 만약 y<0다음 s:=−s.:)−t endif Skl:=0.0, update(k,−t), update(l,t)!를 윤작하다 행과 나의 기둥 k와 나는:=1rotate(i,k,i,l)나는을 endfor 하k−1에:)k+1 l−1에 rotate(k,i,i,l)나는을 endfor.)l+1 n에 rotate(k,i,l,i)!나는을 회전 값 endfor.=1에 n 하┌ ┐┌ ┐┌ ┐.    │Eik││c -sinkingEndProc_ik_il_il. || | | | | | | | | | | | | | | | | | | | | | | | | | | | | | loop_k_l_k_l endproc.

메모들

1. 변경된 논리 배열은 각 고유값의 상태를 유지한다.반복하는 동안 e $e_{k}$ ${\$ 또는 $e_{k}$ $e_{l}$ $e_{l}$ ${\$ 의 숫자 값이 변경되면 $e_{l}$ 변경된 해당 구성요소는 true로, 그렇지 않으면 false로 설정된다.정수 상태는 값이 참인 변경된 성분의 수를 카운트한다.상태 = 0이 되면 반복이 중지된다.이는 근사 $e_{1},\,...\,,e_{n}$ $e_{1},\,...\,,e_{n}$ , $e_{1},\,...\,,e_{n}$ . $e_{1},\,...\,,e_{n}$ . . . $e_{1},\,...\,,e_{n}$ n ${\$ 중 최근에 값을 변경한 것이 없으므로 $e_{1},\,...\,,e_{n}$ 반복이 계속되면 이런 일이 일어날 가능성은 별로 없다는 것을 의미한다.여기서 부동소수 연산은 가장 가까운 부동소수 번호로 최적으로 반올림된다고 가정한다.

2. 행렬 S의 위쪽 삼각형은 파괴되는 반면 아래쪽 삼각형과 대각선은 변하지 않는다.따라서 필요에 따라 S의 복원이 가능하다.

k := 1 ~ n-1 do! matrix S for l :=k+1 to n do s :=s_kl_lk end for end를 복원한다.

3. 고유값이 반드시 내림차순인 것은 아니다.이것은 간단한 분류 알고리즘에 의해 달성될 수 있다.

k := 1 ~ n-1 do l :=k for k for l := k for k+1 to n do_l e_m > e > e > 그리고 m := l endiff for k m m이 스왑 e_m, e_k 스왑 E_m,E_k endiff endf for

4. 알고리즘은 행렬 표기법(0 based 대신 1 based arrays)을 사용하여 작성한다.

5. 알고리즘을 구현할 때 매트릭스 표기법을 사용하여 지정한 부분을 동시에 수행해야 한다.

6. 이 구현에서는 하나의 차원이 독립된 하위 공간인 경우를 올바르게 설명하지 않는다.예를 들어, 대각 행렬이 주어진다면, 위 구현은 결코 종료되지 않을 것이다. 왜냐하면 어떤 고유값도 변경되지 않을 것이기 때문이다.따라서 실제 구현에서는 이 경우를 설명하기 위해 추가적인 논리가 추가되어야 한다.

예

Let $S={\begin{pmatrix}4&-30&60&-35\\-30&300&-675&420\\60&-675&1620&-1050\\-35&420&-1050&700\end{pmatrix}}$

그 후 자코비는 3회 스위프(19회 반복) 후 다음과 같은 고유값과 고유 벡터를 생성한다.

$e_{1}=2585.25381092892231$

$E_{1}={\begin{pmatrix}0.02919332316478608\\-0.328712055763188997\\0.79141411583126331\-0.5145549997152907\end{pmatrix}}}}}}}$

$e_{2}=37.1014913651276582$

$E_{2}={\begin{pmatrix}-0.1791862905354826\0.741917790628453435\-0.100228136947199\-0.638252836892\end{pmatrix}}}}$

$e_{3}=1.4780548447781369$

$E_{3}={\begin{pmatrix}-0.582075699997237650\0.370502185067093058\\0.509578634501799626\\0.5140482722164294\end{pmatrix}}$

$e_{4}=0.206428611718905$

$E_{4}={\begin{pmatrix}0.792608291163763585\0.451923120901599794\\0.321639818992\0.2521666881933\end{pmatrix}}}}}}}$

실제 대칭 행렬을 위한 응용 프로그램

대칭 행렬의 고유값(및 고유 벡터)을 알면 다음과 같은 값을 쉽게 계산할 수 있다.

단수 값: The singular values of a (square) matrix A are the square roots of the (non-negative) eigenvalues of $A^{T}A$ . In case of a symmetric matrix S we have of $S^{T}S=S^{2}$ , hence the singular values of S are the absolute values of the eigenvalues of S

2-규범 및 스펙트럼 반지름: 매트릭스 A의 2-규격은 유클리드 벡토르놈에 기초한 표준으로, 즉 $\|Ax\|_{2}$ x x $\|Ax\|_{2}$ $\|x\|_{2}=1$ $\|x\|_{2}=1$ ${\$ \ $Ax\$ $_$ ${2$ }=1}가 $\|x\|_{2}=1$ x runs 2 $\|Ax\|_{2}$ $\|x\|_{2}=1$ = $\|x\|_{2}=1$ ${\displaystystyle \ \{2}=1}$ 로 모든 벡터를 통과할 때 가장 큰 값이다 $\|x\|_{2}=1$ 대칭 행렬의 경우 고유 벡터 중 가장 큰 절대값이므로 스펙트럼 반경과 동일하다.

조건번호: The condition number of a nonsingular matrix A is defined as ${\mbox{cond}}(A)=\ A\ _{2}\ A^{-1}\ _{2}$ . In case of a symmetric matrix it is the absolute value of the quotient of the largest and smallest eigenvalue.조건 숫자가 큰 행렬은 수치적으로 불안정한 결과를 초래할 수 있다: 작은 섭동은 큰 오류를 초래할 수 있다.힐버트 매트릭스는 가장 유명한 나쁜 조건의 매트릭스다.예를 들어, 4차 힐버트 매트릭스는 15514의 조건을 가지고 있는 반면, 주문 8의 경우 2.7 × 10이다⁸.

순위: 행렬 A는 r 열이 선형적으로 독립되어 있는 반면 나머지 열은 이에 선형적으로 종속되어 있는 경우 r 순위를 가진다.동등하게 r은 A의 범위의 치수다.또한 0이 아닌 단수 값의 수입니다.; 대칭 행렬의 경우 r은 0이 아닌 고유값 수입니다.유감스럽게도 반올림 오류로 인해 0 고유값의 숫자 근사치가 0이 아닐 수 있다(참 값이 아닌 반면 숫자 근사치가 0인 경우도 발생할 수 있다).따라서 고유값 중 어느 것이 0에 가까울지 결정해야만 숫자 순위를 계산할 수 있다.

의사 반전: 행렬 A의 유사 $X=A^{+}$ 은 AX와 XA가 대칭이고 AXA = A, XAX = X가 보유하는 고유한 $X=A^{+}$ 행렬 X $X=A^{+}$ = $X=A^{+}$ + ${\$ X $=A^{+}$ 이다.A가 비정형인 경우 ' $A^{+}=A^{-1}$ + $A^{+}=A^{-1}$ = A $A^{+}=A^{-1}$ - $A^{+}=A^{-1}$ ${\$ A $^{+}=A^{-1$; 프로시저 자코비(S, e, E)가 호출되면 $S=E^{T}{\mbox{Diag}}(e)E$ $S=E^{T}{\mbox{Diag}}(e)E$ = $S=E^{T}{\mbox{Diag}}(e)E$ $S=E^{T}{\mbox{Diag}}(e)E$ $S=E^{T}{\mbox{Diag}}(e)E$ ( $S=E^{T}{\mbox{Diag}}(e)E$ ) E ${\displaystyle S=E^{$ $T}{\mbox{Diag}(e)E}$ 이 $S = E^T \mbox{Diag} (e) E$ (가) 고정되어 있는 곳에서는 Diag(e)가 대각선에 벡터 e가 있는 대각 행렬을 가리킨다. $e_{i}\leq 0$ + ${\$ $^{+}}$ 은 $($ 는) e i {\displaystyle $e_$ ${$ $i$ $}$ 은 $1/e_{i}$ 는) 1 / e i {\ $displaystyle e_$ ${$ i $1/e_{i}$ $e_{i}\leq 0$ $e_{i}$ $}\$ $leq$ 0}이면 $1/e_{i}$ 으로 대체되는 $e_{i}$ 벡터를 나타낸다 $e^{+}$ .행렬 E는 직교하므로 S의 유사 역은 S $S^{+}=E^{T}{\mbox{Diag}}(e^{+})E$ + $S^{+}=E^{T}{\mbox{Diag}}(e^{+})E$ = $S^{+}=E^{T}{\mbox{Diag}}(e^{+})E$ $S^{+}=E^{T}{\mbox{Diag}}(e^{+})E$ $S^{+}=E^{T}{\mbox{Diag}}(e^{+})E$ + $S^{+}=E^{T}{\mbox{Diag}}(e^{+})E$ ) E ${\displaystyle S^{+}=E$ ^{{\displaystyle S^}에 의해 주어진다 $.$ $T}{\mbox{Diag}(e^{+})$ $E}$ $S^{+}=E^{T}{\mbox{Diag}}(e^{+})E$

최소 제곱법: 행렬 A에 전체 순위가 없는 경우 선형 시스템 Ax = b의 솔루션이 없을 수 있다. $\|Ax-b\|_{2}$ ‖ $\|Ax-b\|_{2}$ $\|Ax-b\|_{2}$ - $\|Ax-b\|_{2}$ $\|Ax-b\|_{2}$ 2 ${\$ \ $Ax-b\ _{2$ }가 최소인 $\|Ax-b\|_{2}$ 벡터 x를 찾을 수 있다.솔루션은 $x=A^{+}b$ = $x=A^{+}b$ + $x=A^{+}b$ $x=A^{+}b$ 입니다 $x=A^{+}b$ 전과 같이 대칭행렬 S의 경우, $x=S^{+}b=E^{T}{\mbox{Diag}}(e^{+})Eb$ = $x=S^{+}b=E^{T}{\mbox{Diag}}(e^{+})Eb$ + b $x=S^{+}b=E^{T}{\mbox{Diag}}(e^{+})Eb$ = $x=S^{+}b=E^{T}{\mbox{Diag}}(e^{+})Eb$ $x=S^{+}b=E^{T}{\mbox{Diag}}(e^{+})Eb$ $x=S^{+}b=E^{T}{\mbox{Diag}}(e^{+})Eb$ + $x=S^{+}b=E^{T}{\mbox{Diag}}(e^{+})Eb$ ) $x=S^{+}b=E^{T}{\mbox{Diag}}(e^{+})Eb$ $x=S^{+}b=E^{T}{\mbox{Diag}}(e^{+})Eb$ ${\displaystyle$ x $=S^{+}b=E^{$ $T}{\mbox{Diag}(e^{+})Eb}$ .

행렬 지수: From $S=E^{T}{\mbox{Diag}}(e)E$ = $S=E^{T}{\mbox{Diag}}(e)E$ $S=E^{T}{\mbox{Diag}}(e)E$ $S=E^{T}{\mbox{Diag}}(e)E$ ( $S=E^{T}{\mbox{Diag}}(e)E$ ) E ${\displaystyle S=E^{$ $T}{\mbox{Diag}(e)E$ $\exp S=E^{T}{\mbox{Diag}}(\exp e)E$ $\exp S=E^{T}{\mbox{Diag}}(\exp e)E$ = E $\exp S=E^{T}{\mbox{Diag}}(\exp e)E$ $\exp S=E^{T}{\mbox{Diag}}(\exp e)E$ ) E ${\displaystyle \exp S=E^{$ $T}{\mbox{Diag}}(\exp e)E}$ $e_{i}$ 서 $\exp S = E^T \mbox{Diag} (\exp e) E$ $e_{i}$ e는 e {\displaystyle $\exp e_{i}$ $e_{i}}$ 를 $e_i$ exp $\exp e_{i}$ e $\exp e_{i}$ i {\ $displaystyle$ \ $exp$ e_ ${i$ 로 대체하는 벡터. 같은 방법으로 f(분석적)를 어떤 (분석적) 함수 f에 대해서도 뻔한 방법으로 계산할 수 있다.

선형 미분 방정식: 미분방정식 x' = Ax, x(0) = a에 솔루션 x(t) = exp(t A) a가 있다.대칭 행렬 $x(t)=E^{T}{\mbox{Diag}}(\exp te)Ea$ 의 경우, x $x(t)=E^{T}{\mbox{Diag}}(\exp te)Ea$ ( t $x(t)=E^{T}{\mbox{Diag}}(\exp te)Ea$ ) $x(t)=E^{T}{\mbox{Diag}}(\exp te)Ea$ = $x(t)=E^{T}{\mbox{Diag}}(\exp te)Ea$ T $x(t)=E^{T}{\mbox{Diag}}(\exp te)Ea$ $x(t)=E^{T}{\mbox{Diag}}(\exp te)Ea$ $x(t)=E^{T}{\mbox{Diag}}(\exp te)Ea$ e $x(t)=E^{T}{\mbox{Diag}}(\exp te)Ea$ ) $x(t)=E^{T}{\mbox{Diag}}(\exp te)Ea$ a ${\displaystyle$ x $(t)=E^{$ $T}{\mbox{Diag}(\exp te)Ea$ a $a=\sum _{i=1}^{n}a_{i}E_{i}$ = $a=\sum _{i=1}^{n}a_{i}E_{i}$ ∑ $a=\sum _{i=1}^{n}a_{i}E_{i}$ = $a=\sum _{i=1}^{n}a_{i}E_{i}$ i ${\$ i} $E_{i}}$ 은(는) S의 고유 벡터에 의한 a의 확장이고, 그 다음은 $x(t)=\sum _{i=1}^{n}a_{i}\exp(te_{i})E_{i}$ ( $x(t)=\sum _{i=1}^{n}a_{i}\exp(te_{i})E_{i}$ ) $x(t)=\sum _{i=1}^{n}a_{i}\exp(te_{i})E_{i}$ = $x(t)=\sum _{i=1}^{n}a_{i}\exp(te_{i})E_{i}$ $x(t)=\sum _{i=1}^{n}a_{i}\exp(te_{i})E_{i}$ = $x(t)=\sum _{i=1}^{n}a_{i}\exp(te_{i})E_{i}$ a $x(t)=\sum _{i=1}^{n}a_{i}\exp(te_{i})E_{i}$ $x(t)=\sum _{i=1}^{n}a_{i}\exp(te_{i})E_{i}$ $x(t)=\sum _{i=1}^{n}a_{i}\exp(te_{i})E_{i}$ ( $x(t)=\sum _{i=1}^{n}a_{i}\exp(te_{i})E_{i}$ $x(t)=\sum _{i=1}^{n}a_{i}\exp(te_{i})E_{i}$ $x(t)=\sum _{i=1}^{n}a_{i}\exp(te_{i})E_{i}$ E $x(t)=\sum _{i=1}^{n}a_{i}\exp(te_{i})E_{i}$ ${\$ 이다 $a = \sum_{i = 1}^n a_i E_i$ . $E_{i$; W $W^{s}$ ${\$ 를 음의 고유값에 해당하는 S의 고유 벡터에 의해 확장되는 벡터 공간으로 하고 $W^{s}$ , $W^{u}$ ${\$ W $^{u}$ 를 양의 고유값에 대해 유사하게 $W^{u}$ 한다. $a\in W^{s}$ $a\in W^{s}$ ${\$ W $^{s}}}$ 이 $a \in W^s$ (가) ${\mbox{lim}}_{t\ \infty }x(t)=0$ ${\mbox{lim}}_{t\ \infty }x(t)=0$ ${\mbox{lim}}_{t\ \infty }x(t)=0$ x ${\mbox{lim}}_{t\ \infty }x(t)=0$ ( ${\mbox{lim}}_{t\ \infty }x(t)=0$ ) ${\mbox{lim}}_{t\ \infty }x(t)=0$ = 0 ${\displaystyle {\mbox{lim}_{t\\ \inft }x$ 즉, 평형점 0은 x(t)에 매력적이다. $a\in W^{u}$ $a\in W^{u}$ $a\in W^{u}$ ${\$ ${\mbox{lim}}_{t\ \infty }x(t)=\infty$ ${\mbox{lim}}_{t\ \infty }x(t)=\infty$ x ( t ) ${\mbox{lim}}_{t\ \infty }x(t)=\infty$ = ${\mbox{lim}}_{t\ \infty }x(t)=\infty$ ${\displaystyle {\mbox{lim}_{t\\\infty },$ 즉 $0$ 은 x(t)로 혐오된다 $a\in W^{u}$ . $W^{s}$ $W^{s}$ ${\$ 와 $W^s$ $W^{u}$ $W^{u}$ ${\$ 는 S에 $W^u$ 대해 안정적이고 불안정한 다지관이라고 불린다.의 구성 요소가 두 매니폴드에 모두 있는 경우, 한 구성 요소가 끌어당겨지고 한 구성 요소가 제거된다.따라서 x(t)는 $W^{u}$ $t\to \infty$ u ${\$ W $^{u}$ 에 $t\to \infty$ → $t\to \infty$ ∞ $t\\potto \inflt$ 으로 $W^u$ 접근한다 $t\to \infty$

일반화

자코비 방법은 복잡한 에르미트 행렬, 일반적인 비대칭 실제 및 복합 행렬, 블록 행렬로 일반화되었다.

실제 행렬의 단수값은 $S=A^{T}A$ 행렬 S $S=A^{T}A$ = $S=A^{T}A$ $S=A^{T}A$ $S=A^{T}A$ $S=A^{T}A$ 의 고유값의 제곱근이기 때문에 이러한 $S=A^{T}A$ 값을 계산하는 데도 사용할 수 있다.이 경우, S를 명시적으로 계산하여 반올림 오류의 위험을 줄이지 않도록 방법을 수정한다. $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ = J $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ = $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ = $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ ${\displaystyle JSJ^{T}=$ 에 유의하십시오. $JA^{T}AJ^{T}=$ $JA^{T}J^{T}$ $JAJ^{T}=B^{T}B},$ B $JSJ^{T}=JA^{T}AJ^{T}=JA^{T}J^{T}JAJ^{T}=B^{T}B$ $B\,:=JAJ^{T}$ $B\,:=JAJ^{T}$ $B\,:=JAJ^{T}$ $B\,:=JAJ^{T}$ $B\,:=JAJ^{T}$ ${\$ B $\,:=JAJ^{T}}.$

자코비법은 또한 평행주의에도 잘 맞는다.

참조

^ Jacobi, C.G.J. (1846). "Über ein leichtes Verfahren, die in der Theorie der Säkularstörungen vorkommenden Gleichungen numerisch aufzulösen". Crelle's Journal (in German). 1846 (30): 51–94. doi:10.1515/crll.1846.30.51.
^ Golub, G.H.; van der Vorst, H.A. (2000). "Eigenvalue computation in the 20th century". Journal of Computational and Applied Mathematics. 123 (1–2): 35–65. doi:10.1016/S0377-0427(00)00413-1.
^ Schönhage, A. (1964). "Zur quadratischen Konvergenz des Jacobi-Verfahrens". Numerische Mathematik (in German). 6 (1): 410–412. doi:10.1007/BF01386091. MR 0174171.

추가 읽기

Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 11.1. Jacobi Transformations of a Symmetric Matrix", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
Rutishauser, H. (1966). "Handbook Series Linear Algebra: The Jacobi method for real symmetric matrices". Numerische Mathematik. 9 (1): 1–10. doi:10.1007/BF02165223. MR 1553948.
Sameh, A.H. (1971). "On Jacobi and Jacobi-like algorithms for a parallel computer". Mathematics of Computation. 25 (115): 579–590. doi:10.1090/s0025-5718-1971-0297131-6. JSTOR 2005221. MR 0297131.
Shroff, Gautam M. (1991). "A parallel algorithm for the eigenvalues and eigenvectors of a general complex matrix". Numerische Mathematik. 58 (1): 779–805. CiteSeerX 10.1.1.134.3566. doi:10.1007/BF01385654. MR 1098865.
Veselić, K. (1979). "On a class of Jacobi-like procedures for diagonalising arbitrary real matrices". Numerische Mathematik. 33 (2): 157–172. doi:10.1007/BF01399551. MR 0549446.
Veselić, K.; Wenzel, H. J. (1979). "A quadratically convergent Jacobi-like method for real matrices with complex eigenvalues". Numerische Mathematik. 33 (4): 425–435. doi:10.1007/BF01399324. MR 0553351.

외부 링크

[1] Jacobi, C.G.J. (1846). "Über ein leichtes Verfahren, die in der Theorie der Säkularstörungen vorkommenden Gleichungen numerisch aufzulösen". Crelle's Journal (in German). 1846 (30): 51–94. doi:10.1515/crll.1846.30.51.

[2] Golub, G.H.; van der Vorst, H.A. (2000). "Eigenvalue computation in the 20th century". Journal of Computational and Applied Mathematics. 123 (1–2): 35–65. doi:10.1016/S0377-0427(00)00413-1.

[3] Schönhage, A. (1964). "Zur quadratischen Konvergenz des Jacobi-Verfahrens". Numerische Mathematik (in German). 6 (1): 410–412. doi:10.1007/BF01386091. MR 0174171.

[2]

[1]

[3]

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

Search

자코비 고유값 알고리즘

네임스페이스

더

목차

설명.

수렴

비용

알고리즘.

메모들

예

실제 대칭 행렬을 위한 응용 프로그램

일반화

참조

추가 읽기

외부 링크