1 QR 法 定義 1.1. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 A ∈ R n × n A\in\R^{n\times n} A ∈ R n × n
A 0 : = A A_0:=A A 0 := A k ≥ 0 k\ge0 k ≥ 0 A k A_k A k σ k \sigma_k σ k A k − σ k I A_k-\sigma_kI A k − σ k I §D3.17 定理 1.2 によるA k − σ k I A_k-\sigma_kI A k − σ k I A k − σ k I = Q k R k A_k-\sigma_kI=Q_kR_k A k − σ k I = Q k R k Q k Q_k Q k R k R_k R k A k + 1 : = R k Q k + σ k I A_{k+1}:=R_kQ_k+\sigma_kI A k + 1 := R k Q k + σ k I ( A k ) (A_k) ( A k ) A A A ( σ k ) (\sigma_k) ( σ k ) QR 法 (QR algorithm )k k k σ k = 0 \sigma_k=0 σ k = 0 シフトなしの QR 法 (unshifted QR algorithm )σ \sigma σ k k k σ k = σ \sigma_k=\sigma σ k = σ σ \sigma σ 固定シフト (fixed shift )i > j + 1 i>j+1 i > j + 1 ( i , j ) (i,j) ( i , j ) ( i , j ) (i,j) ( i , j ) 0 0 0 n n n 上 Hessenberg 行列 (upper Hessenberg matrix )H H H ( j + 1 , j ) (j+1,j) ( j + 1 , j ) 1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 0 0 0 H H H 非簡約 (unreduced ) 命題 1.2. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 A ∈ R n × n A\in\R^{n\times n} A ∈ R n × n ( A k ) (A_k) ( A k ) A A A ( σ k ) (\sigma_k) ( σ k ) A k A_k A k k ≥ 0 k\ge0 k ≥ 0 P k : = Q 0 Q 1 ⋯ Q k − 1 P_k:=Q_0Q_1\cdots Q_{k-1} P k := Q 0 Q 1 ⋯ Q k − 1 P 0 : = I P_0:=I P 0 := I
A k A_k A k k k k P k P_k P k A k = P k T A P k A_k=P_k^{\mathsf T}AP_k A k = P k T A P k det ( t I − A k ) = det ( t I − A ) \det(tI-A_k)=\det(tI-A) det ( t I − A k ) = det ( t I − A ) A k − σ k I A_k-\sigma_kI A k − σ k I A k + 1 A_{k+1} A k + 1 A k + 1 = Q k T A k Q k A_{k+1}=Q_k^{\mathsf T}A_kQ_k A k + 1 = Q k T A k Q k A T = A A^{\mathsf T}=A A T = A A k A_k A k k k k A k T = A k A_k^{\mathsf T}=A_k A k T = A k A A A A k A_k A k k k k A k A_k A k A A A A k A_k A k k k k A k A_k A k ∣ i − j ∣ > 1 \lvert i-j\rvert>1 ∣ i − j ∣ > 1 ( i , j ) (i,j) ( i , j ) 0 0 0 すべてのk ≥ 0 k\ge0 k ≥ 0 A k A_k A k det ( t I − A ) \det(tI-A) det ( t I − A ) ( A k ) (A_k) ( A k )
証明. (1) を示す。A k − σ k I A_k-\sigma_kI A k − σ k I A k + 1 A_{k+1} A k + 1 Q k Q_k Q k R k = Q k T ( A k − σ k I ) R_k=Q_k^{\mathsf T}(A_k-\sigma_kI) R k = Q k T ( A k − σ k I )
A k + 1 = Q k T ( A k − σ k I ) Q k + σ k I = Q k T A k Q k A_{k+1}=Q_k^{\mathsf T}(A_k-\sigma_kI)Q_k+\sigma_kI=Q_k^{\mathsf T}A_kQ_k A k + 1 = Q k T ( A k − σ k I ) Q k + σ k I = Q k T A k Q k である。A 0 = P 0 T A P 0 A_0=P_0^{\mathsf T}AP_0 A 0 = P 0 T A P 0 A k = P k T A P k A_k=P_k^{\mathsf T}AP_k A k = P k T A P k A k + 1 = Q k T P k T A P k Q k = P k + 1 T A P k + 1 A_{k+1}=Q_k^{\mathsf T}P_k^{\mathsf T}AP_kQ_k=P_{k+1}^{\mathsf T}AP_{k+1} A k + 1 = Q k T P k T A P k Q k = P k + 1 T A P k + 1 k k k A k = P k T A P k A_k=P_k^{\mathsf T}AP_k A k = P k T A P k P k P_k P k det ( t I − A k ) = det ( P k T ( t I − A ) P k ) = det ( t I − A ) \det(tI-A_k)=\det\bigl(P_k^{\mathsf T}(tI-A)P_k\bigr)=\det(tI-A) det ( t I − A k ) = det ( P k T ( t I − A ) P k ) = det ( t I − A )
(2) を示す。(1) によりA k T = P k T A T P k = P k T A P k = A k A_k^{\mathsf T}=P_k^{\mathsf T}A^{\mathsf T}P_k=P_k^{\mathsf T}AP_k=A_k A k T = P k T A T P k = P k T A P k = A k
(3) を示す。H H H U U U ( H U ) i j = ∑ l h i l u l j (HU)_{ij}=\sum_lh_{il}u_{lj} ( H U ) ij = ∑ l h i l u l j 0 0 0 l ≥ i − 1 l\ge i-1 l ≥ i − 1 l ≤ j l\le j l ≤ j ( U H ) i j = ∑ l u i l h l j (UH)_{ij}=\sum_lu_{il}h_{lj} ( U H ) ij = ∑ l u i l h l j 0 0 0 l ≥ i l\ge i l ≥ i l ≤ j + 1 l\le j+1 l ≤ j + 1 i > j + 1 i>j+1 i > j + 1 ( H U ) i j = ( U H ) i j = 0 (HU)_{ij}=(UH)_{ij}=0 ( H U ) ij = ( U H ) ij = 0 H U HU H U U H UH U H A k A_k A k A k + 1 A_{k+1} A k + 1 A k − σ k I A_k-\sigma_kI A k − σ k I R k R_k R k R k − 1 R_k^{-1} R k − 1 Q k = ( A k − σ k I ) R k − 1 Q_k=(A_k-\sigma_kI)R_k^{-1} Q k = ( A k − σ k I ) R k − 1 R k Q k R_kQ_k R k Q k A k + 1 = R k Q k + σ k I A_{k+1}=R_kQ_k+\sigma_kI A k + 1 = R k Q k + σ k I k k k A A A (2) によりA k A_k A k i > j + 1 i>j+1 i > j + 1 ( A k ) i j = 0 (A_k)_{ij}=0 ( A k ) ij = 0 ( A k ) j i = ( A k ) i j = 0 (A_k)_{ji}=(A_k)_{ij}=0 ( A k ) j i = ( A k ) ij = 0
(4) を示す。( A k ) (A_k) ( A k ) T T T A k A_k A k T T T det ( t I − X ) \det(tI-X) det ( t I − X ) X X X (1) によりdet ( t I − T ) \det(tI-T) det ( t I − T ) det ( t I − A ) \det(tI-A) det ( t I − A ) T T T det ( t I − T ) = ∏ i ( t − t i i ) \det(tI-T)=\prod_i(t-t_{ii}) det ( t I − T ) = ∏ i ( t − t ii ) t 11 , … , t n n t_{11},\dots,t_{nn} t 11 , … , t nn det ( t I − T ) = det ( t I − A ) \det(tI-T)=\det(tI-A) det ( t I − T ) = det ( t I − A ) ▨
2 三重対角化と一段の費用 定理 2.1. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 A ∈ R n × n A\in\R^{n\times n} A ∈ R n × n H v H_v H v §E20.6 定義 3.1 ）を用いてdiag ( I k , H v ) \operatorname{diag}(I_k,H_v) diag ( I k , H v ) max { n − 2 , 0 } \max\{n-2,0\} max { n − 2 , 0 } P P P P T A P P^{\mathsf T}AP P T A P A T = A A^{\mathsf T}=A A T = A P P P P T A P P^{\mathsf T}AP P T A P
証明. n ≤ 2 n\le2 n ≤ 2 A A A 0 0 0 P : = I P:=I P := I n ≥ 3 n\ge3 n ≥ 3 B ( 0 ) : = A B^{(0)}:=A B ( 0 ) := A 1 ≤ k ≤ n − 2 1\le k\le n-2 1 ≤ k ≤ n − 2 B ( k − 1 ) B^{(k-1)} B ( k − 1 ) ( i , j ) (i,j) ( i , j ) j ≤ k − 1 j\le k-1 j ≤ k − 1 i > j + 1 i>j+1 i > j + 1 0 0 0 B ( k − 1 ) B^{(k-1)} B ( k − 1 ) k k k k + 1 k+1 k + 1 n n n x ∈ R n − k x\in\R^{n-k} x ∈ R n − k x = 0 x=0 x = 0 H k : = I n H_k:=I_n H k := I n x ≠ 0 x\ne0 x = 0 §E20.6 補題 3.2 (2) のv ∈ R n − k v\in\R^{n-k} v ∈ R n − k H k : = diag ( I k , H v ) H_k:=\operatorname{diag}(I_k,H_v) H k := diag ( I k , H v ) B ( k ) : = H k B ( k − 1 ) H k B^{(k)}:=H_kB^{(k-1)}H_k B ( k ) := H k B ( k − 1 ) H k §E20.6 補題 3.2 (1) によりH k H_k H k
x = 0 x=0 x = 0 B ( k ) = B ( k − 1 ) B^{(k)}=B^{(k-1)} B ( k ) = B ( k − 1 ) k k k k + 2 k+2 k + 2 n n n 0 0 0 x ≠ 0 x\ne0 x = 0 H k B ( k − 1 ) H_kB^{(k-1)} H k B ( k − 1 ) B ( k − 1 ) B^{(k-1)} B ( k − 1 ) 1 1 1 k k k k + 1 k+1 k + 1 n n n y y y H v y H_vy H v y j < k j<k j < k k + 1 > j + 1 k+1>j+1 k + 1 > j + 1 B ( k − 1 ) B^{(k-1)} B ( k − 1 ) j j j y y y 0 0 0 H v 0 = 0 H_v0=0 H v 0 = 0 k k k y y y x x x §E20.6 補題 3.2 (2) によりH v x = − s α e 1 H_vx=-s\alpha e_1 H v x = − s α e 1 k + 2 k+2 k + 2 n n n 0 0 0 H k H_k H k 1 1 1 k k k B ( k ) B^{(k)} B ( k ) ( i , j ) (i,j) ( i , j ) j ≤ k j\le k j ≤ k i > j + 1 i>j+1 i > j + 1 0 0 0
k k k B ( n − 2 ) B^{(n-2)} B ( n − 2 ) ( i , j ) (i,j) ( i , j ) j ≤ n − 2 j\le n-2 j ≤ n − 2 i > j + 1 i>j+1 i > j + 1 0 0 0 j ≥ n − 1 j\ge n-1 j ≥ n − 1 i > j + 1 i>j+1 i > j + 1 i ≤ n i\le n i ≤ n B ( n − 2 ) B^{(n-2)} B ( n − 2 ) P : = H 1 ⋯ H n − 2 P:=H_1\cdots H_{n-2} P := H 1 ⋯ H n − 2 H k T = H k H_k^{\mathsf T}=H_k H k T = H k B ( n − 2 ) = P T A P B^{(n-2)}=P^{\mathsf T}AP B ( n − 2 ) = P T A P A T = A A^{\mathsf T}=A A T = A P T A P P^{\mathsf T}AP P T A P i > j + 1 i>j+1 i > j + 1 ( i , j ) (i,j) ( i , j ) ( j , i ) (j,i) ( j , i ) 0 0 0 ▨
定義 2.2. n ≥ 2 n\ge2 n ≥ 2 1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 c , s ∈ R c,s\in\R c , s ∈ R c 2 + s 2 = 1 c^2+s^2=1 c 2 + s 2 = 1 n n n ( j , j ) (j,j) ( j , j ) ( j , j + 1 ) (j,j+1) ( j , j + 1 ) ( j + 1 , j ) (j+1,j) ( j + 1 , j ) ( j + 1 , j + 1 ) (j+1,j+1) ( j + 1 , j + 1 ) c c c − s -s − s s s s c c c G ( j ; c , s ) G(j;c,s) G ( j ; c , s ) Givens 回転 (Givens rotation )c 2 + s 2 = 1 c^2+s^2=1 c 2 + s 2 = 1 G ( j ; c , s ) T G ( j ; c , s ) = I G(j;c,s)^{\mathsf T}G(j;c,s)=I G ( j ; c , s ) T G ( j ; c , s ) = I G ( j ; c , s ) G(j;c,s) G ( j ; c , s )
命題 2.3. n ≥ 2 n\ge2 n ≥ 2 H ∈ R n × n H\in\R^{n\times n} H ∈ R n × n W ( 0 ) : = H W^{(0)}:=H W ( 0 ) := H j = 1 , … , n − 1 j=1,\dots,n-1 j = 1 , … , n − 1 W ( j − 1 ) W^{(j-1)} W ( j − 1 ) ( j , j ) (j,j) ( j , j ) a a a ( j + 1 , j ) (j+1,j) ( j + 1 , j ) b b b
r j : = a 2 + b 2 , c j : = a r j , s j : = b r j , G j : = G ( j ; c j , s j ) , W ( j ) : = G j T W ( j − 1 ) r_j:=\sqrt{a^2+b^2},\qquad c_j:=\frac{a}{r_j},\qquad s_j:=\frac{b}{r_j},\qquad G_j:=G(j;c_j,s_j),\qquad W^{(j)}:=G_j^{\mathsf T}W^{(j-1)} r j := a 2 + b 2 , c j := r j a , s j := r j b , G j := G ( j ; c j , s j ) , W ( j ) := G j T W ( j − 1 ) と置く。
各j j j r j > 0 r_j>0 r j > 0 W ( n − 1 ) W^{(n-1)} W ( n − 1 ) ( j , j ) (j,j) ( j , j ) r j r_j r j 1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 ( n , n ) (n,n) ( n , n ) w w w 0 0 0
w > 0 w>0 w > 0 S : = I S:=I S := I w < 0 w<0 w < 0 S : = diag ( 1 , … , 1 , − 1 ) S:=\operatorname{diag}(1,\dots,1,-1) S := diag ( 1 , … , 1 , − 1 ) Q : = G 1 ⋯ G n − 1 S Q:=G_1\cdots G_{n-1}S Q := G 1 ⋯ G n − 1 S R : = S W ( n − 1 ) R:=SW^{(n-1)} R := S W ( n − 1 ) H = Q R H=QR H = QR H H H R Q = S W ( n − 1 ) G 1 ⋯ G n − 1 S RQ=SW^{(n-1)}G_1\cdots G_{n-1}S R Q = S W ( n − 1 ) G 1 ⋯ G n − 1 S X ( 0 ) : = R X^{(0)}:=R X ( 0 ) := R X ( j ) : = X ( j − 1 ) G j X^{(j)}:=X^{(j-1)}G_j X ( j ) := X ( j − 1 ) G j 1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 W ( j ) W^{(j)} W ( j ) W ( j − 1 ) W^{(j-1)} W ( j − 1 ) j j j j + 1 j+1 j + 1 j j j n n n W ( j ) W^{(j)} W ( j ) ( j , j ) (j,j) ( j , j ) r j r_j r j ( j + 1 , j ) (j+1,j) ( j + 1 , j ) 0 0 0 X ( j ) X^{(j)} X ( j ) X ( j − 1 ) X^{(j-1)} X ( j − 1 ) 1 1 1 j + 1 j+1 j + 1 j j j j + 1 j+1 j + 1 X ( j − 1 ) X^{(j-1)} X ( j − 1 ) ( j + 1 , j ) (j+1,j) ( j + 1 , j ) 0 0 0 r j , c j , s j r_j,c_j,s_j r j , c j , s j a 2 a^2 a 2 b 2 b^2 b 2 W ( j ) W^{(j)} W ( j ) j + 1 j+1 j + 1 n n n j j j j + 1 j+1 j + 1 X ( j ) X^{(j)} X ( j ) 1 1 1 j j j j j j j + 1 j+1 j + 1 ( x , y ) (x,y) ( x , y ) c j x + s j y c_jx+s_jy c j x + s j y c j y − s j x c_jy-s_jx c j y − s j x X ( j ) X^{(j)} X ( j ) j + 1 j+1 j + 1 j j j j + 1 j+1 j + 1 ( j + 1 , j + 1 ) (j+1,j+1) ( j + 1 , j + 1 ) y y y s j y s_jy s j y c j y c_jy c j y R R R R Q = X ( n − 1 ) S RQ=X^{(n-1)}S R Q = X ( n − 1 ) S c j , s j c_j,s_j c j , s j 1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 R R R R Q RQ R Q ( n − 1 ) ( 6 n + 8 ) (n-1)(6n+8) ( n − 1 ) ( 6 n + 8 ) 6 ( n − 1 ) ( n + 3 ) 6(n-1)(n+3) 6 ( n − 1 ) ( n + 3 ) 証明. G j T G_j^{\mathsf T} G j T j j j j + 1 j+1 j + 1 ( x , y ) (x,y) ( x , y ) ( c j x + s j y , c j y − s j x ) (c_jx+s_jy,\,c_jy-s_jx) ( c j x + s j y , c j y − s j x ) G j G_j G j j j j j + 1 j+1 j + 1 ( x , y ) (x,y) ( x , y ) ( c j x + s j y , c j y − s j x ) (c_jx+s_jy,\,c_jy-s_jx) ( c j x + s j y , c j y − s j x )
(1) を示す。1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 W ( j − 1 ) W^{(j-1)} W ( j − 1 ) i < j i<j i < j ( i + 1 , i ) (i+1,i) ( i + 1 , i ) 0 0 0 j = 1 j=1 j = 1 H H H W ( j − 1 ) = G j − 1 T ⋯ G 1 T H W^{(j-1)}=G_{j-1}^{\mathsf T}\cdots G_1^{\mathsf T}H W ( j − 1 ) = G j − 1 T ⋯ G 1 T H l < j l<j l < j W ( j − 1 ) W^{(j-1)} W ( j − 1 ) l l l l l l 0 0 0 j j j j + 1 j+1 j + 1 0 0 0 a = b = 0 a=b=0 a = b = 0 1 1 1 j j j span { e 1 , … , e j − 1 } \operatorname{span}\{e_1,\dots,e_{j-1}\} span { e 1 , … , e j − 1 } r j > 0 r_j>0 r j > 0 j j j ( a , b ) (a,b) ( a , b ) ( c j a + s j b , c j b − s j a ) = ( r j , 0 ) (c_ja+s_jb,\,c_jb-s_ja)=(r_j,0) ( c j a + s j b , c j b − s j a ) = ( r j , 0 ) l < j l<j l < j W ( j − 1 ) W^{(j-1)} W ( j − 1 ) ( j , l ) (j,l) ( j , l ) l = j − 1 l=j-1 l = j − 1 0 0 0 l < j − 1 l<j-1 l < j − 1 0 0 0 ( j + 1 , l ) (j+1,l) ( j + 1 , l ) 0 0 0 l l l l > j l>j l > j j j j j + 1 j+1 j + 1 ( i , l ) (i,l) ( i , l ) i ≤ l + 1 i\le l+1 i ≤ l + 1 W ( j ) W^{(j)} W ( j ) i ≤ j i\le j i ≤ j ( i + 1 , i ) (i+1,i) ( i + 1 , i ) 0 0 0 j j j W ( n − 1 ) W^{(n-1)} W ( n − 1 ) G j ′ T G_{j'}^{\mathsf T} G j ′ T j ′ > j j'>j j ′ > j j j j W ( n − 1 ) W^{(n-1)} W ( n − 1 ) ( j , j ) (j,j) ( j , j ) r j r_j r j W ( n − 1 ) W^{(n-1)} W ( n − 1 ) w ≠ 0 w\ne0 w = 0
(2) を示す。S 2 = I S^2=I S 2 = I Q R = G 1 ⋯ G n − 1 W ( n − 1 ) = G 1 ⋯ G n − 1 G n − 1 T ⋯ G 1 T H = H QR=G_1\cdots G_{n-1}W^{(n-1)}=G_1\cdots G_{n-1}G_{n-1}^{\mathsf T}\cdots G_1^{\mathsf T}H=H QR = G 1 ⋯ G n − 1 W ( n − 1 ) = G 1 ⋯ G n − 1 G n − 1 T ⋯ G 1 T H = H Q Q Q R R R r 1 , … , r n − 1 , ∣ w ∣ r_1,\dots,r_{n-1},\lvert w\rvert r 1 , … , r n − 1 , ∣ w ∣ H = Q R H=QR H = QR H H H §D3.17 定理 1.2 によりただ一つの QR 分解である。命題 1.2 (3) をH H H A 1 = R Q A_1=RQ A 1 = R Q
(3) を示す。W ( j ) W^{(j)} W ( j ) G j T G_j^{\mathsf T} G j T W ( j − 1 ) W^{(j-1)} W ( j − 1 ) l l l l < j l<j l < j X ( j − 1 ) X^{(j-1)} X ( j − 1 ) j j j j j j 0 0 0 j + 1 j+1 j + 1 R R R j + 1 j+1 j + 1 j = 1 j=1 j = 1 X ( 0 ) = R X^{(0)}=R X ( 0 ) = R j + 1 j+1 j + 1 j j j j + 1 j+1 j + 1 0 0 0 G j G_j G j j + 1 j+1 j + 1 ( 0 , y ) (0,y) ( 0 , y ) ( s j y , c j y ) (s_jy,c_jy) ( s j y , c j y ) j + 1 j+1 j + 1 j + 1 j+1 j + 1 0 0 0 j + 2 j+2 j + 2 R R R j + 2 j+2 j + 2 j + 1 j+1 j + 1
演算を数える。段j j j r j , c j , s j r_j,c_j,s_j r j , c j , s j 6 6 6 W ( j ) W^{(j)} W ( j ) l l l j < l ≤ n j<l\le n j < l ≤ n 4 4 4 2 2 2 6 6 6 6 ( n − j ) 6(n-j) 6 ( n − j ) X ( j ) X^{(j)} X ( j ) 1 1 1 j j j 6 6 6 j + 1 j+1 j + 1 2 2 2 6 j + 2 6j+2 6 j + 2 S S S W ( n − 1 ) W^{(n-1)} W ( n − 1 ) n n n X ( n − 1 ) X^{(n-1)} X ( n − 1 ) n n n
∑ j = 1 n − 1 ( 6 + 6 ( n − j ) + 6 j + 2 ) = ( n − 1 ) ( 6 n + 8 ) \sum_{j=1}^{n-1}\bigl(6+6(n-j)+6j+2\bigr)=(n-1)(6n+8) j = 1 ∑ n − 1 ( 6 + 6 ( n − j ) + 6 j + 2 ) = ( n − 1 ) ( 6 n + 8 ) であり、6 n + 8 ≤ 6 n + 18 = 6 ( n + 3 ) 6n+8\le6n+18=6(n+3) 6 n + 8 ≤ 6 n + 18 = 6 ( n + 3 ) 6 ( n − 1 ) ( n + 3 ) 6(n-1)(n+3) 6 ( n − 1 ) ( n + 3 ) ▨
3 べき乗法との対応と固定シフトの収束 補題 3.1. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 A ∈ R n × n A\in\R^{n\times n} A ∈ R n × n ( A k ) (A_k) ( A k ) A A A ( σ k ) (\sigma_k) ( σ k ) P k P_k P k 命題 1.2 の直交行列とする。k ≥ 0 k\ge0 k ≥ 0 A k A_k A k U k : = R k − 1 ⋯ R 1 R 0 U_k:=R_{k-1}\cdots R_1R_0 U k := R k − 1 ⋯ R 1 R 0 Φ k : = ( A − σ k − 1 I ) ⋯ ( A − σ 1 I ) ( A − σ 0 I ) \Phi_k:=(A-\sigma_{k-1}I)\cdots(A-\sigma_1I)(A-\sigma_0I) Φ k := ( A − σ k − 1 I ) ⋯ ( A − σ 1 I ) ( A − σ 0 I ) U 0 : = Φ 0 : = I U_0:=\Phi_0:=I U 0 := Φ 0 := I
U k U_k U k Φ k = P k U k \Phi_k=P_kU_k Φ k = P k U k Φ k \Phi_k Φ k 1 ≤ j ≤ n 1\le j\le n 1 ≤ j ≤ n P k P_k P k 1 1 1 j j j Φ k ( span { e 1 , … , e j } ) \Phi_k(\operatorname{span}\{e_1,\dots,e_j\}) Φ k ( span { e 1 , … , e j }) すべてのi < k i<k i < k σ i = σ \sigma_i=\sigma σ i = σ P k P_k P k 1 1 1 A − σ I A-\sigma I A − σ I e 1 e_1 e 1 §E20.7 定義 1.1 ）の第k k k
証明. (1) を示す。i < k i<k i < k A i + 1 A_{i+1} A i + 1 A i − σ i I = Q i R i A_i-\sigma_iI=Q_iR_i A i − σ i I = Q i R i 命題 1.2 (1) によりA − σ i I = P i ( A i − σ i I ) P i T = P i Q i R i P i T A-\sigma_iI=P_i(A_i-\sigma_iI)P_i^{\mathsf T}=P_iQ_iR_iP_i^{\mathsf T} A − σ i I = P i ( A i − σ i I ) P i T = P i Q i R i P i T ( A − σ i I ) P i = P i + 1 R i (A-\sigma_iI)P_i=P_{i+1}R_i ( A − σ i I ) P i = P i + 1 R i Φ 0 = P 0 U 0 \Phi_0=P_0U_0 Φ 0 = P 0 U 0 Φ i = P i U i \Phi_i=P_iU_i Φ i = P i U i Φ i + 1 = ( A − σ i I ) P i U i = P i + 1 R i U i = P i + 1 U i + 1 \Phi_{i+1}=(A-\sigma_iI)P_iU_i=P_{i+1}R_iU_i=P_{i+1}U_{i+1} Φ i + 1 = ( A − σ i I ) P i U i = P i + 1 R i U i = P i + 1 U i + 1 i i i Φ k = P k U k \Phi_k=P_kU_k Φ k = P k U k U k U_k U k P k P_k P k Φ k = P k U k \Phi_k=P_kU_k Φ k = P k U k Φ k \Phi_k Φ k
(2) を示す。E j : = ( e 1 ⋯ e j ) ∈ R n × j E_j:=(e_1\ \cdots\ e_j)\in\R^{n\times j} E j := ( e 1 ⋯ e j ) ∈ R n × j P k P_k P k 1 1 1 j j j P ′ P' P ′ U k U_k U k j × j j\times j j × j U ′ U' U ′ U k U_k U k Φ k E j = P k U k E j = P ′ U ′ \Phi_kE_j=P_kU_kE_j=P'U' Φ k E j = P k U k E j = P ′ U ′ U ′ U' U ′ P ′ P' P ′ Φ k E j \Phi_kE_j Φ k E j
(3) を示す。B : = A − σ I B:=A-\sigma I B := A − σ I k ≥ 1 k\ge1 k ≥ 1 A 1 A_1 A 1 B = A 0 − σ 0 I B=A_0-\sigma_0I B = A 0 − σ 0 I ( y i ) (y_i) ( y i ) B B B e 1 e_1 e 1 y 0 = e 1 y_0=e_1 y 0 = e 1 y i = B i e 1 / ∥ B i e 1 ∥ 2 y_i=B^ie_1/\lVert B^ie_1\rVert_2 y i = B i e 1 / ∥ B i e 1 ∥ 2 B y i ≠ 0 By_i\ne0 B y i = 0 y i + 1 = B i + 1 e 1 / ∥ B i + 1 e 1 ∥ 2 y_{i+1}=B^{i+1}e_1/\lVert B^{i+1}e_1\rVert_2 y i + 1 = B i + 1 e 1 / ∥ B i + 1 e 1 ∥ 2 y k = B k e 1 / ∥ B k e 1 ∥ 2 y_k=B^ke_1/\lVert B^ke_1\rVert_2 y k = B k e 1 / ∥ B k e 1 ∥ 2 P k P_k P k 1 1 1 p p p (1) によりB k e 1 = Φ k e 1 = ( U k ) 11 p B^ke_1=\Phi_ke_1=(U_k)_{11}p B k e 1 = Φ k e 1 = ( U k ) 11 p ( U k ) 11 > 0 (U_k)_{11}>0 ( U k ) 11 > 0 ∥ p ∥ 2 = 1 \lVert p\rVert_2=1 ∥ p ∥ 2 = 1 p = y k p=y_k p = y k ▨
補題 3.2. n ≥ 2 n\ge2 n ≥ 2 1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 M M M ∥ M ∥ 2 \lVert M\rVert_2 ∥ M ∥ 2 Z ∈ R n × n Z\in\R^{n\times n} Z ∈ R n × n
Z = ( X 1 Y 1 X 2 Y 2 ) , X 1 ∈ R j × j , Y 2 ∈ R ( n − j ) × ( n − j ) Z=\begin{pmatrix}X_1&Y_1\\X_2&Y_2\end{pmatrix},\qquad X_1\in\R^{j\times j},\quad Y_2\in\R^{(n-j)\times(n-j)} Z = ( X 1 X 2 Y 1 Y 2 ) , X 1 ∈ R j × j , Y 2 ∈ R ( n − j ) × ( n − j ) と区分し、F ∈ R ( n − j ) × j F\in\R^{(n-j)\times j} F ∈ R ( n − j ) × j X 2 = F X 1 X_2=FX_1 X 2 = F X 1
X 1 X_1 X 1 Y 1 = − F T Y 2 Y_1=-F^{\mathsf T}Y_2 Y 1 = − F T Y 2 ∥ X 2 ∥ 2 ≤ ∥ F ∥ 2 \lVert X_2\rVert_2\le\lVert F\rVert_2 ∥ X 2 ∥ 2 ≤ ∥ F ∥ 2 ∥ Y 1 ∥ 2 ≤ ∥ F ∥ 2 \lVert Y_1\rVert_2\le\lVert F\rVert_2 ∥ Y 1 ∥ 2 ≤ ∥ F ∥ 2 D 1 ∈ R j × j D_1\in\R^{j\times j} D 1 ∈ R j × j D 2 ∈ R ( n − j ) × ( n − j ) D_2\in\R^{(n-j)\times(n-j)} D 2 ∈ R ( n − j ) × ( n − j ) ( Y 1 Y 2 ) T ( D 1 0 0 D 2 ) ( X 1 X 2 ) = Y 2 T ( D 2 F − F D 1 ) X 1 \begin{pmatrix}Y_1\\Y_2\end{pmatrix}^{\mathsf T}\begin{pmatrix}D_1&0\\0&D_2\end{pmatrix}\begin{pmatrix}X_1\\X_2\end{pmatrix}=Y_2^{\mathsf T}(D_2F-FD_1)X_1 ( Y 1 Y 2 ) T ( D 1 0 0 D 2 ) ( X 1 X 2 ) = Y 2 T ( D 2 F − F D 1 ) X 1 ∥ ⋅ ∥ 2 \lVert\cdot\rVert_2 ∥ ⋅ ∥ 2 ( ∥ D 1 ∥ 2 + ∥ D 2 ∥ 2 ) ∥ F ∥ 2 (\lVert D_1\rVert_2+\lVert D_2\rVert_2)\lVert F\rVert_2 (∥ D 1 ∥ 2 + ∥ D 2 ∥ 2 ) ∥ F ∥ 2 証明. 実行列M M M ∥ M ∥ 2 \lVert M\rVert_2 ∥ M ∥ 2 §E20.6 補題 2.1 (1) により有限であり、作用素ノルムの定義により∥ M h ∥ 2 ≤ ∥ M ∥ 2 ∥ h ∥ 2 \lVert Mh\rVert_2\le\lVert M\rVert_2\lVert h\rVert_2 ∥ M h ∥ 2 ≤ ∥ M ∥ 2 ∥ h ∥ 2 M N MN M N M , N M,N M , N h h h ∥ M N h ∥ 2 ≤ ∥ M ∥ 2 ∥ N ∥ 2 ∥ h ∥ 2 \lVert MNh\rVert_2\le\lVert M\rVert_2\lVert N\rVert_2\lVert h\rVert_2 ∥ M N h ∥ 2 ≤ ∥ M ∥ 2 ∥ N ∥ 2 ∥ h ∥ 2 ∥ M N ∥ 2 ≤ ∥ M ∥ 2 ∥ N ∥ 2 \lVert MN\rVert_2\le\lVert M\rVert_2\lVert N\rVert_2 ∥ M N ∥ 2 ≤ ∥ M ∥ 2 ∥ N ∥ 2 Z Z Z h ∈ R j h\in\R^j h ∈ R j ∥ X 1 h ∥ 2 2 ≤ ∥ X 1 h ∥ 2 2 + ∥ X 2 h ∥ 2 2 = ∥ h ∥ 2 2 \lVert X_1h\rVert_2^2\le\lVert X_1h\rVert_2^2+\lVert X_2h\rVert_2^2=\lVert h\rVert_2^2 ∥ X 1 h ∥ 2 2 ≤ ∥ X 1 h ∥ 2 2 + ∥ X 2 h ∥ 2 2 = ∥ h ∥ 2 2 ∥ X 1 ∥ 2 ≤ 1 \lVert X_1\rVert_2\le1 ∥ X 1 ∥ 2 ≤ 1 ∥ Y 2 ∥ 2 ≤ 1 \lVert Y_2\rVert_2\le1 ∥ Y 2 ∥ 2 ≤ 1 §E20.6 補題 2.1 (1) により、任意の実行列M M M ∥ M T ∥ 2 = ∥ M ∥ 2 \lVert M^{\mathsf T}\rVert_2=\lVert M\rVert_2 ∥ M T ∥ 2 = ∥ M ∥ 2
(1) を示す。Z T Z = I Z^{\mathsf T}Z=I Z T Z = I j × j j\times j j × j j × ( n − j ) j\times(n-j) j × ( n − j )
X 1 T X 1 + X 2 T X 2 = I j , X 1 T Y 1 + X 2 T Y 2 = 0 X_1^{\mathsf T}X_1+X_2^{\mathsf T}X_2=I_j,\qquad X_1^{\mathsf T}Y_1+X_2^{\mathsf T}Y_2=0 X 1 T X 1 + X 2 T X 2 = I j , X 1 T Y 1 + X 2 T Y 2 = 0 である。第一式にX 2 = F X 1 X_2=FX_1 X 2 = F X 1 X 1 T ( I j + F T F ) X 1 = I j X_1^{\mathsf T}(I_j+F^{\mathsf T}F)X_1=I_j X 1 T ( I j + F T F ) X 1 = I j X 1 X_1 X 1 X 1 T ( Y 1 + F T Y 2 ) = 0 X_1^{\mathsf T}(Y_1+F^{\mathsf T}Y_2)=0 X 1 T ( Y 1 + F T Y 2 ) = 0 X 1 T X_1^{\mathsf T} X 1 T Y 1 = − F T Y 2 Y_1=-F^{\mathsf T}Y_2 Y 1 = − F T Y 2 ∥ X 2 ∥ 2 ≤ ∥ F ∥ 2 ∥ X 1 ∥ 2 ≤ ∥ F ∥ 2 \lVert X_2\rVert_2\le\lVert F\rVert_2\lVert X_1\rVert_2\le\lVert F\rVert_2 ∥ X 2 ∥ 2 ≤ ∥ F ∥ 2 ∥ X 1 ∥ 2 ≤ ∥ F ∥ 2 ∥ Y 1 ∥ 2 ≤ ∥ F T ∥ 2 ∥ Y 2 ∥ 2 ≤ ∥ F ∥ 2 \lVert Y_1\rVert_2\le\lVert F^{\mathsf T}\rVert_2\lVert Y_2\rVert_2\le\lVert F\rVert_2 ∥ Y 1 ∥ 2 ≤ ∥ F T ∥ 2 ∥ Y 2 ∥ 2 ≤ ∥ F ∥ 2
(2) を示す。左辺はY 1 T D 1 X 1 + Y 2 T D 2 X 2 Y_1^{\mathsf T}D_1X_1+Y_2^{\mathsf T}D_2X_2 Y 1 T D 1 X 1 + Y 2 T D 2 X 2 (1) のY 1 T = − Y 2 T F Y_1^{\mathsf T}=-Y_2^{\mathsf T}F Y 1 T = − Y 2 T F X 2 = F X 1 X_2=FX_1 X 2 = F X 1 ∥ Y 2 T ∥ 2 ≤ 1 \lVert Y_2^{\mathsf T}\rVert_2\le1 ∥ Y 2 T ∥ 2 ≤ 1 ∥ X 1 ∥ 2 ≤ 1 \lVert X_1\rVert_2\le1 ∥ X 1 ∥ 2 ≤ 1 ∥ ⋅ ∥ 2 \lVert\cdot\rVert_2 ∥ ⋅ ∥ 2 ∥ D 2 F − F D 1 ∥ 2 ≤ ( ∥ D 2 ∥ 2 + ∥ D 1 ∥ 2 ) ∥ F ∥ 2 \lVert D_2F-FD_1\rVert_2\le(\lVert D_2\rVert_2+\lVert D_1\rVert_2)\lVert F\rVert_2 ∥ D 2 F − F D 1 ∥ 2 ≤ (∥ D 2 ∥ 2 + ∥ D 1 ∥ 2 ) ∥ F ∥ 2 ▨
定理 3.3. n ≥ 2 n\ge2 n ≥ 2 A ∈ R n × n A\in\R^{n\times n} A ∈ R n × n A T = A A^{\mathsf T}=A A T = A σ ∈ R \sigma\in\R σ ∈ R V = ( v 1 ⋯ v n ) V=(v_1\ \cdots\ v_n) V = ( v 1 ⋯ v n ) λ 1 , … , λ n \lambda_1,\dots,\lambda_n λ 1 , … , λ n A v i = λ i v i Av_i=\lambda_iv_i A v i = λ i v i 1 ≤ i ≤ n 1\le i\le n 1 ≤ i ≤ n
∣ λ 1 − σ ∣ > ∣ λ 2 − σ ∣ > ⋯ > ∣ λ n − σ ∣ > 0 \lvert\lambda_1-\sigma\rvert>\lvert\lambda_2-\sigma\rvert>\dots>\lvert\lambda_n-\sigma\rvert>0 ∣ λ 1 − σ ∣ > ∣ λ 2 − σ ∣ > ⋯ > ∣ λ n − σ ∣ > 0 を満たすとする。1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 V T V^{\mathsf T} V T 1 1 1 j j j 1 1 1 j j j M j ∈ R j × j M_j\in\R^{j\times j} M j ∈ R j × j j + 1 j+1 j + 1 n n n 1 1 1 j j j N j ∈ R ( n − j ) × j N_j\in\R^{(n-j)\times j} N j ∈ R ( n − j ) × j M j M_j M j ∥ ⋅ ∥ 2 \lVert\cdot\rVert_2 ∥ ⋅ ∥ 2 1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 k ≥ 0 k\ge0 k ≥ 0
t j : = ∥ N j M j − 1 ∥ 2 , q j : = ∣ λ j + 1 − σ ∣ ∣ λ j − σ ∣ , ε j , k : = t j q j k t_j:=\lVert N_jM_j^{-1}\rVert_2,\qquad q_j:=\frac{\lvert\lambda_{j+1}-\sigma\rvert}{\lvert\lambda_j-\sigma\rvert},\qquad\varepsilon_{j,k}:=t_jq_j^k t j := ∥ N j M j − 1 ∥ 2 , q j := ∣ λ j − σ ∣ ∣ λ j + 1 − σ ∣ , ε j , k := t j q j k と置き、ε 0 , k : = ε n , k : = 0 \varepsilon_{0,k}:=\varepsilon_{n,k}:=0 ε 0 , k := ε n , k := 0 ( A k ) (A_k) ( A k ) A A A σ \sigma σ P k P_k P k 命題 1.2 の直交行列とする。
すべてのk ≥ 0 k\ge0 k ≥ 0 A k A_k A k A k − σ I A_k-\sigma I A k − σ I
1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 k ≥ 0 k\ge0 k ≥ 0 P k P_k P k 1 1 1 j j j y y y dist ( y , span { v 1 , … , v j } ) ≤ ε j , k \operatorname{dist}(y,\operatorname{span}\{v_1,\dots,v_j\})\le\varepsilon_{j,k} dist ( y , span { v 1 , … , v j }) ≤ ε j , k 1 ≤ l ≤ j < i ≤ n 1\le l\le j<i\le n 1 ≤ l ≤ j < i ≤ n k ≥ 0 k\ge0 k ≥ 0 ∣ ( A k ) i l ∣ = ∣ ( A k ) l i ∣ ≤ 2 ∣ λ 1 − σ ∣ ε j , k \lvert(A_k)_{il}\rvert=\lvert(A_k)_{li}\rvert\le2\lvert\lambda_1-\sigma\rvert\varepsilon_{j,k} ∣( A k ) i l ∣ = ∣( A k ) l i ∣ ≤ 2 ∣ λ 1 − σ ∣ ε j , k ∣ ( A k ) j + 1 , j ∣ ≤ 2 ∣ λ 1 − σ ∣ t j q j k \lvert(A_k)_{j+1,j}\rvert\le2\lvert\lambda_1-\sigma\rvert t_jq_j^k ∣( A k ) j + 1 , j ∣ ≤ 2 ∣ λ 1 − σ ∣ t j q j k A k A_k A k k → ∞ k\to\infty k → ∞ 0 0 0 1 ≤ j ≤ n 1\le j\le n 1 ≤ j ≤ n k ≥ 0 k\ge0 k ≥ 0 δ j : = max i ∣ λ i − λ j ∣ \delta_j:=\max_i\lvert\lambda_i-\lambda_j\rvert δ j := max i ∣ λ i − λ j ∣ ∣ ( A k ) j j − λ j ∣ ≤ δ j ( ε j − 1 , k 2 + ε j , k 2 ) \lvert(A_k)_{jj}-\lambda_j\rvert\le\delta_j(\varepsilon_{j-1,k}^2+\varepsilon_{j,k}^2) ∣( A k ) j j − λ j ∣ ≤ δ j ( ε j − 1 , k 2 + ε j , k 2 ) 証明. (1) を示す。∣ λ n − σ ∣ > 0 \lvert\lambda_n-\sigma\rvert>0 ∣ λ n − σ ∣ > 0 λ 1 , … , λ n \lambda_1,\dots,\lambda_n λ 1 , … , λ n σ \sigma σ A − σ I = V diag ( λ i − σ ) V T A-\sigma I=V\operatorname{diag}(\lambda_i-\sigma)V^{\mathsf T} A − σ I = V diag ( λ i − σ ) V T A k A_k A k 命題 1.2 (1) によりA k − σ I = P k T ( A − σ I ) P k A_k-\sigma I=P_k^{\mathsf T}(A-\sigma I)P_k A k − σ I = P k T ( A − σ I ) P k A k + 1 A_{k+1} A k + 1 k k k (1) が従う。
Λ : = diag ( λ 1 − σ , … , λ n − σ ) \Lambda:=\operatorname{diag}(\lambda_1-\sigma,\dots,\lambda_n-\sigma) Λ := diag ( λ 1 − σ , … , λ n − σ ) A V = V diag ( λ i ) AV=V\operatorname{diag}(\lambda_i) A V = V diag ( λ i ) A − σ I = V Λ V T A-\sigma I=V\Lambda V^{\mathsf T} A − σ I = V Λ V T V T ( A − σ I ) k = Λ k V T V^{\mathsf T}(A-\sigma I)^k=\Lambda^kV^{\mathsf T} V T ( A − σ I ) k = Λ k V T k ≥ 0 k\ge0 k ≥ 0 Z k : = V T P k Z_k:=V^{\mathsf T}P_k Z k := V T P k
主張 3.3.1. 1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 k ≥ 0 k\ge0 k ≥ 0 Z k Z_k Z k 補題 3.2 のようにX 1 , X 2 , Y 1 , Y 2 X_1,X_2,Y_1,Y_2 X 1 , X 2 , Y 1 , Y 2 Λ \Lambda Λ j × j j\times j j × j Λ 1 \Lambda_1 Λ 1 ( n − j ) × ( n − j ) (n-j)\times(n-j) ( n − j ) × ( n − j ) Λ 2 \Lambda_2 Λ 2 F : = Λ 2 k N j M j − 1 Λ 1 − k F:=\Lambda_2^kN_jM_j^{-1}\Lambda_1^{-k} F := Λ 2 k N j M j − 1 Λ 1 − k X 2 = F X 1 X_2=FX_1 X 2 = F X 1 ∥ F ∥ 2 ≤ ε j , k \lVert F\rVert_2\le\varepsilon_{j,k} ∥ F ∥ 2 ≤ ε j , k ∥ Λ 1 ∥ 2 ≤ ∣ λ 1 − σ ∣ \lVert\Lambda_1\rVert_2\le\lvert\lambda_1-\sigma\rvert ∥ Λ 1 ∥ 2 ≤ ∣ λ 1 − σ ∣ ∥ Λ 2 ∥ 2 ≤ ∣ λ 1 − σ ∣ \lVert\Lambda_2\rVert_2\le\lvert\lambda_1-\sigma\rvert ∥ Λ 2 ∥ 2 ≤ ∣ λ 1 − σ ∣
証明. E j : = ( e 1 ⋯ e j ) E_j:=(e_1\ \cdots\ e_j) E j := ( e 1 ⋯ e j ) P k P_k P k 1 1 1 j j j P ′ P' P ′ 補題 3.1 のU k U_k U k j × j j\times j j × j U ′ U' U ′ Φ k = ( A − σ I ) k \Phi_k=(A-\sigma I)^k Φ k = ( A − σ I ) k 補題 3.1 (1) とU k U_k U k ( A − σ I ) k E j = P k U k E j = P ′ U ′ (A-\sigma I)^kE_j=P_kU_kE_j=P'U' ( A − σ I ) k E j = P k U k E j = P ′ U ′ V T P ′ V^{\mathsf T}P' V T P ′ X 1 X_1 X 1 X 2 X_2 X 2 V T E j V^{\mathsf T}E_j V T E j M j M_j M j N j N_j N j
( X 1 X 2 ) U ′ = V T ( A − σ I ) k E j = Λ k ( M j N j ) \begin{pmatrix}X_1\\X_2\end{pmatrix}U'=V^{\mathsf T}(A-\sigma I)^kE_j=\Lambda^k\begin{pmatrix}M_j\\N_j\end{pmatrix} ( X 1 X 2 ) U ′ = V T ( A − σ I ) k E j = Λ k ( M j N j ) である。U ′ U' U ′ X 1 = Λ 1 k M j U ′ − 1 X_1=\Lambda_1^kM_jU'^{-1} X 1 = Λ 1 k M j U ′ − 1 X 2 = Λ 2 k N j U ′ − 1 X_2=\Lambda_2^kN_jU'^{-1} X 2 = Λ 2 k N j U ′ − 1 Λ 1 \Lambda_1 Λ 1 M j M_j M j U ′ − 1 = M j − 1 Λ 1 − k X 1 U'^{-1}=M_j^{-1}\Lambda_1^{-k}X_1 U ′ − 1 = M j − 1 Λ 1 − k X 1 X 2 = F X 1 X_2=FX_1 X 2 = F X 1 diag ( μ 1 , … , μ m ) \operatorname{diag}(\mu_1,\dots,\mu_m) diag ( μ 1 , … , μ m ) h ∈ R m h\in\R^m h ∈ R m ∥ diag ( μ i ) h ∥ 2 2 = ∑ i μ i 2 h i 2 ≤ max i μ i 2 ∥ h ∥ 2 2 \lVert\operatorname{diag}(\mu_i)h\rVert_2^2=\sum_i\mu_i^2h_i^2\le\max_i\mu_i^2\lVert h\rVert_2^2 ∥ diag ( μ i ) h ∥ 2 2 = ∑ i μ i 2 h i 2 ≤ max i μ i 2 ∥ h ∥ 2 2 ∣ λ i − σ ∣ \lvert\lambda_i-\sigma\rvert ∣ λ i − σ ∣ i i i ∥ Λ 2 k ∥ 2 ≤ ∣ λ j + 1 − σ ∣ k \lVert\Lambda_2^k\rVert_2\le\lvert\lambda_{j+1}-\sigma\rvert^k ∥ Λ 2 k ∥ 2 ≤ ∣ λ j + 1 − σ ∣ k ∥ Λ 1 − k ∥ 2 ≤ ∣ λ j − σ ∣ − k \lVert\Lambda_1^{-k}\rVert_2\le\lvert\lambda_j-\sigma\rvert^{-k} ∥ Λ 1 − k ∥ 2 ≤ ∣ λ j − σ ∣ − k ∥ Λ 1 ∥ 2 ≤ ∣ λ 1 − σ ∣ \lVert\Lambda_1\rVert_2\le\lvert\lambda_1-\sigma\rvert ∥ Λ 1 ∥ 2 ≤ ∣ λ 1 − σ ∣ ∥ Λ 2 ∥ 2 ≤ ∣ λ 1 − σ ∣ \lVert\Lambda_2\rVert_2\le\lvert\lambda_1-\sigma\rvert ∥ Λ 2 ∥ 2 ≤ ∣ λ 1 − σ ∣ M , N M,N M , N ∥ M N ∥ 2 ≤ ∥ M ∥ 2 ∥ N ∥ 2 \lVert MN\rVert_2\le\lVert M\rVert_2\lVert N\rVert_2 ∥ M N ∥ 2 ≤ ∥ M ∥ 2 ∥ N ∥ 2
∥ F ∥ 2 ≤ ∣ λ j + 1 − σ ∣ k t j ∣ λ j − σ ∣ − k = ε j , k \lVert F\rVert_2\le\lvert\lambda_{j+1}-\sigma\rvert^k\,t_j\,\lvert\lambda_j-\sigma\rvert^{-k}=\varepsilon_{j,k} ∥ F ∥ 2 ≤ ∣ λ j + 1 − σ ∣ k t j ∣ λ j − σ ∣ − k = ε j , k である。▨
(2) を示す。主張 3.3.1 の区分をとる。P k P_k P k 1 1 1 j j j y = P k E j z y=P_kE_jz y = P k E j z ∥ z ∥ 2 = 1 \lVert z\rVert_2=1 ∥ z ∥ 2 = 1 z ∈ R j z\in\R^j z ∈ R j v i T y v_i^{\mathsf T}y v i T y V T y V^{\mathsf T}y V T y i i i V T y V^{\mathsf T}y V T y X 1 z X_1z X 1 z X 2 z X_2z X 2 z §E20.7 補題 2.1 (2) をJ = { 1 , … , j } J=\{1,\dots,j\} J = { 1 , … , j } 補題 3.2 (1) と主張 3.3.1 を用いると
dist ( y , span { v 1 , … , v j } ) = ∥ X 2 z ∥ 2 ≤ ∥ X 2 ∥ 2 ≤ ∥ F ∥ 2 ≤ ε j , k \operatorname{dist}(y,\operatorname{span}\{v_1,\dots,v_j\})=\lVert X_2z\rVert_2\le\lVert X_2\rVert_2\le\lVert F\rVert_2\le\varepsilon_{j,k} dist ( y , span { v 1 , … , v j }) = ∥ X 2 z ∥ 2 ≤ ∥ X 2 ∥ 2 ≤ ∥ F ∥ 2 ≤ ε j , k である。
(3) を示す。主張 3.3.1 の区分をとり、P k P_k P k 1 1 1 j j j P ′ P' P ′ j + 1 j+1 j + 1 n n n P ′ ′ P'' P ′′ A k = P k T A P k A_k=P_k^{\mathsf T}AP_k A k = P k T A P k 命題 1.2 (1) ）の第j + 1 j+1 j + 1 n n n 1 1 1 j j j B B B P ′ ′ T P ′ = 0 P''^{\mathsf T}P'=0 P ′′ T P ′ = 0
B = P ′ ′ T A P ′ = P ′ ′ T ( A − σ I ) P ′ = ( V T P ′ ′ ) T Λ ( V T P ′ ) B=P''^{\mathsf T}AP'=P''^{\mathsf T}(A-\sigma I)P'=(V^{\mathsf T}P'')^{\mathsf T}\,\Lambda\,(V^{\mathsf T}P') B = P ′′ T A P ′ = P ′′ T ( A − σ I ) P ′ = ( V T P ′′ ) T Λ ( V T P ′ ) である。V T P ′ V^{\mathsf T}P' V T P ′ X 1 X_1 X 1 X 2 X_2 X 2 V T P ′ ′ V^{\mathsf T}P'' V T P ′′ Y 1 Y_1 Y 1 Y 2 Y_2 Y 2 補題 3.2 (2) をD 1 = Λ 1 D_1=\Lambda_1 D 1 = Λ 1 D 2 = Λ 2 D_2=\Lambda_2 D 2 = Λ 2 主張 3.3.1 を用いて∥ B ∥ 2 ≤ 2 ∣ λ 1 − σ ∣ ε j , k \lVert B\rVert_2\le2\lvert\lambda_1-\sigma\rvert\varepsilon_{j,k} ∥ B ∥ 2 ≤ 2 ∣ λ 1 − σ ∣ ε j , k 1 ≤ l ≤ j < i ≤ n 1\le l\le j<i\le n 1 ≤ l ≤ j < i ≤ n ( A k ) i l (A_k)_{il} ( A k ) i l B B B ( i − j , l ) (i-j,l) ( i − j , l ) ∣ ( A k ) i l ∣ = ∣ e i − j T B e l ∣ ≤ ∥ B e l ∥ 2 ≤ ∥ B ∥ 2 \lvert(A_k)_{il}\rvert=\lvert e_{i-j}^{\mathsf T}Be_l\rvert\le\lVert Be_l\rVert_2\le\lVert B\rVert_2 ∣( A k ) i l ∣ = ∣ e i − j T B e l ∣ ≤ ∥ B e l ∥ 2 ≤ ∥ B ∥ 2 命題 1.2 (2) により( A k ) l i = ( A k ) i l (A_k)_{li}=(A_k)_{il} ( A k ) l i = ( A k ) i l 0 ≤ q j < 1 0\le q_j<1 0 ≤ q j < 1 ε j , k → 0 \varepsilon_{j,k}\to0 ε j , k → 0 k → ∞ k\to\infty k → ∞ i > l i>l i > l ( i , l ) (i,l) ( i , l ) j : = l j:=l j := l
(4) を示す。p : = P k e j p:=P_ke_j p := P k e j c i : = v i T p c_i:=v_i^{\mathsf T}p c i := v i T p 命題 1.2 (1) により( A k ) j j = p T A p (A_k)_{jj}=p^{\mathsf T}Ap ( A k ) j j = p T A p j ≤ n − 1 j\le n-1 j ≤ n − 1 主張 3.3.1 のj j j p p p P k E j P_kE_j P k E j j j j ( c j + 1 , … , c n ) T = X 2 e j (c_{j+1},\dots,c_n)^{\mathsf T}=X_2e_j ( c j + 1 , … , c n ) T = X 2 e j 補題 3.2 (1) と主張 3.3.1 により∑ i > j c i 2 ≤ ∥ X 2 ∥ 2 2 ≤ ε j , k 2 \sum_{i>j}c_i^2\le\lVert X_2\rVert_2^2\le\varepsilon_{j,k}^2 ∑ i > j c i 2 ≤ ∥ X 2 ∥ 2 2 ≤ ε j , k 2 j ≥ 2 j\ge2 j ≥ 2 主張 3.3.1 のj − 1 j-1 j − 1 p p p P k P_k P k j j j n n n 1 1 1 ( c 1 , … , c j − 1 ) T = Y 1 e 1 (c_1,\dots,c_{j-1})^{\mathsf T}=Y_1e_1 ( c 1 , … , c j − 1 ) T = Y 1 e 1 補題 3.2 (1) と主張 3.3.1 により∑ i < j c i 2 ≤ ∥ Y 1 ∥ 2 2 ≤ ε j − 1 , k 2 \sum_{i<j}c_i^2\le\lVert Y_1\rVert_2^2\le\varepsilon_{j-1,k}^2 ∑ i < j c i 2 ≤ ∥ Y 1 ∥ 2 2 ≤ ε j − 1 , k 2 λ 1 , … , λ n \lambda_1,\dots,\lambda_n λ 1 , … , λ n §E20.7 命題 2.2 (1) をd = 1 d=1 d = 1 λ = λ j \lambda=\lambda_j λ = λ j E = span { v j } E=\operatorname{span}\{v_j\} E = span { v j } §E20.7 補題 2.1 (2) を用いると
∣ ( A k ) j j − λ j ∣ ≤ δ j dist ( p , span { v j } ) 2 = δ j ∑ i ≠ j c i 2 ≤ δ j ( ε j − 1 , k 2 + ε j , k 2 ) \lvert(A_k)_{jj}-\lambda_j\rvert\le\delta_j\operatorname{dist}(p,\operatorname{span}\{v_j\})^2=\delta_j\sum_{i\ne j}c_i^2\le\delta_j(\varepsilon_{j-1,k}^2+\varepsilon_{j,k}^2) ∣( A k ) j j − λ j ∣ ≤ δ j dist ( p , span { v j } ) 2 = δ j i = j ∑ c i 2 ≤ δ j ( ε j − 1 , k 2 + ε j , k 2 ) である。▨
命題 3.4. n ≥ 2 n\ge2 n ≥ 2 T ∈ R n × n T\in\R^{n\times n} T ∈ R n × n
0 ≤ m ≤ n − 1 0\le m\le n-1 0 ≤ m ≤ n − 1 span { e 1 , T e 1 , … , T m e 1 } = span { e 1 , … , e m + 1 } \operatorname{span}\{e_1,Te_1,\dots,T^me_1\}=\operatorname{span}\{e_1,\dots,e_{m+1}\} span { e 1 , T e 1 , … , T m e 1 } = span { e 1 , … , e m + 1 } det ( t I − T ) \det(tI-T) det ( t I − T ) λ ∈ R \lambda\in\R λ ∈ R v ∈ R n ∖ { 0 } v\in\R^n\setminus\{0\} v ∈ R n ∖ { 0 } T v = λ v Tv=\lambda v T v = λ v v T e 1 ≠ 0 v^{\mathsf T}e_1\ne0 v T e 1 = 0 直交行列V = ( v 1 ⋯ v n ) V=(v_1\ \cdots\ v_n) V = ( v 1 ⋯ v n ) λ 1 , … , λ n \lambda_1,\dots,\lambda_n λ 1 , … , λ n T v i = λ i v i Tv_i=\lambda_iv_i T v i = λ i v i 1 ≤ i ≤ n 1\le i\le n 1 ≤ i ≤ n 1 ≤ j ≤ n 1\le j\le n 1 ≤ j ≤ n V T V^{\mathsf T} V T 1 1 1 j j j 1 1 1 j j j
証明. (1) を示す。τ 0 : = 1 \tau_0:=1 τ 0 := 1 τ m : = t 21 t 32 ⋯ t m + 1 , m \tau_m:=t_{21}t_{32}\cdots t_{m+1,m} τ m := t 21 t 32 ⋯ t m + 1 , m m ≥ 1 m\ge1 m ≥ 1 T T T τ m ≠ 0 \tau_m\ne0 τ m = 0 x ∈ span { e 1 , … , e m + 1 } x\in\operatorname{span}\{e_1,\dots,e_{m+1}\} x ∈ span { e 1 , … , e m + 1 } m ≤ n − 2 m\le n-2 m ≤ n − 2 T T T T x ∈ span { e 1 , … , e m + 2 } Tx\in\operatorname{span}\{e_1,\dots,e_{m+2}\} T x ∈ span { e 1 , … , e m + 2 } T x Tx T x m + 2 m+2 m + 2 t m + 2 , m + 1 x m + 1 t_{m+2,m+1}x_{m+1} t m + 2 , m + 1 x m + 1 m m m T m e 1 ∈ span { e 1 , … , e m + 1 } T^me_1\in\operatorname{span}\{e_1,\dots,e_{m+1}\} T m e 1 ∈ span { e 1 , … , e m + 1 } m + 1 m+1 m + 1 τ m \tau_m τ m e 1 , T e 1 , … , T m e 1 e_1,Te_1,\dots,T^me_1 e 1 , T e 1 , … , T m e 1 span { e 1 , … , e m + 1 } \operatorname{span}\{e_1,\dots,e_{m+1}\} span { e 1 , … , e m + 1 } span { e 1 , … , e m + 1 } \operatorname{span}\{e_1,\dots,e_{m+1}\} span { e 1 , … , e m + 1 }
(2) を示す。λ \lambda λ det ( t I − T ) \det(tI-T) det ( t I − T ) T − λ I T-\lambda I T − λ I 2 2 2 n n n 1 1 1 n − 1 n-1 n − 1 ( i , l ) (i,l) ( i , l ) 1 ≤ i , l ≤ n − 1 1\le i,l\le n-1 1 ≤ i , l ≤ n − 1 T − λ I T-\lambda I T − λ I ( i + 1 , l ) (i+1,l) ( i + 1 , l ) i > l i>l i > l i + 1 > l + 1 i+1>l+1 i + 1 > l + 1 0 0 0 i = l i=l i = l t i + 1 , i ≠ 0 t_{i+1,i}\ne0 t i + 1 , i = 0 T − λ I T-\lambda I T − λ I n − 1 n-1 n − 1 dim ker ( T − λ I ) ≤ 1 \dim\ker(T-\lambda I)\le1 dim ker ( T − λ I ) ≤ 1 §E20.7 補題 2.1 (3) の正規直交基底q 1 , … , q n q_1,\dots,q_n q 1 , … , q n λ 1 ′ ≤ ⋯ ≤ λ n ′ \lambda'_1\le\dots\le\lambda'_n λ 1 ′ ≤ ⋯ ≤ λ n ′ §E20.7 補題 2.1 (1) により∥ ( T − λ I ) y ∥ 2 2 = ∑ i ( λ i ′ − λ ) 2 ( q i T y ) 2 \lVert(T-\lambda I)y\rVert_2^2=\sum_i(\lambda'_i-\lambda)^2(q_i^{\mathsf T}y)^2 ∥( T − λ I ) y ∥ 2 2 = ∑ i ( λ i ′ − λ ) 2 ( q i T y ) 2 ker ( T − λ I ) = span { q i ∣ λ i ′ = λ } \ker(T-\lambda I)=\operatorname{span}\{q_i\mid\lambda'_i=\lambda\} ker ( T − λ I ) = span { q i ∣ λ i ′ = λ } det ( t I − T ) = ∏ i ( t − λ i ′ ) \det(tI-T)=\prod_i(t-\lambda'_i) det ( t I − T ) = ∏ i ( t − λ i ′ ) λ \lambda λ λ i ′ = λ \lambda'_i=\lambda λ i ′ = λ i i i dim ker ( T − λ I ) ≤ 1 \dim\ker(T-\lambda I)\le1 dim ker ( T − λ I ) ≤ 1
(3) を示す。v T e 1 = 0 v^{\mathsf T}e_1=0 v T e 1 = 0 T T T m ≥ 0 m\ge0 m ≥ 0 v T T m e 1 = ( T m v ) T e 1 = λ m v T e 1 = 0 v^{\mathsf T}T^me_1=(T^mv)^{\mathsf T}e_1=\lambda^mv^{\mathsf T}e_1=0 v T T m e 1 = ( T m v ) T e 1 = λ m v T e 1 = 0 (1) をm = n − 1 m=n-1 m = n − 1 v v v R n \R^n R n v = 0 v=0 v = 0 v = 0 v=0 v = 0 v ≠ 0 v\ne0 v = 0
(4) を示す。V T V^{\mathsf T} V T M M M z ∈ R j z\in\R^j z ∈ R j M z = 0 Mz=0 M z = 0 x : = ∑ i ≤ j z i e i x:=\sum_{i\le j}z_ie_i x := ∑ i ≤ j z i e i i ≤ j i\le j i ≤ j M z Mz M z i i i v i T x v_i^{\mathsf T}x v i T x v i T x = 0 v_i^{\mathsf T}x=0 v i T x = 0 (1) をm = j − 1 m=j-1 m = j − 1 j − 1 j-1 j − 1 p p p x = p ( T ) e 1 x=p(T)e_1 x = p ( T ) e 1 v i T T m = λ i m v i T v_i^{\mathsf T}T^m=\lambda_i^mv_i^{\mathsf T} v i T T m = λ i m v i T v i T x = p ( λ i ) v i T e 1 v_i^{\mathsf T}x=p(\lambda_i)v_i^{\mathsf T}e_1 v i T x = p ( λ i ) v i T e 1 (3) によりp ( λ i ) = 0 p(\lambda_i)=0 p ( λ i ) = 0 1 ≤ i ≤ j 1\le i\le j 1 ≤ i ≤ j V V V det ( t I − T ) = det ( t I − diag ( λ i ) ) = ∏ i ( t − λ i ) \det(tI-T)=\det(tI-\operatorname{diag}(\lambda_i))=\prod_i(t-\lambda_i) det ( t I − T ) = det ( t I − diag ( λ i )) = ∏ i ( t − λ i ) (2) によりλ 1 , … , λ j \lambda_1,\dots,\lambda_j λ 1 , … , λ j j − 1 j-1 j − 1 p p p j j j p = 0 p=0 p = 0 x = 0 x=0 x = 0 z = 0 z=0 z = 0 ▨
例 3.5. A : = diag ( 1 , 2 ) A:=\operatorname{diag}(1,2) A := diag ( 1 , 2 ) σ : = 0 \sigma:=0 σ := 0 ∣ 2 ∣ > ∣ 1 ∣ \lvert2\rvert>\lvert1\rvert ∣ 2 ∣ > ∣ 1 ∣ 定理 3.3 の番号付けはλ 1 = 2 \lambda_1=2 λ 1 = 2 λ 2 = 1 \lambda_2=1 λ 2 = 1 v 1 = ± e 2 v_1=\pm e_2 v 1 = ± e 2 v 2 = ± e 1 v_2=\pm e_1 v 2 = ± e 1 M 1 M_1 M 1 V T V^{\mathsf T} V T ( 1 , 1 ) (1,1) ( 1 , 1 ) 0 0 0 A = I ⋅ A A=I\cdot A A = I ⋅ A A A A §D3.17 定理 1.2 の一意性によりQ 0 = I Q_0=I Q 0 = I R 0 = A R_0=A R 0 = A A 1 = A A_1=A A 1 = A k k k A k = A A_k=A A k = A P k = I P_k=I P k = I ( A k ) 21 = 0 (A_k)_{21}=0 ( A k ) 21 = 0 ( A k ) 11 = 1 ≠ λ 1 (A_k)_{11}=1\ne\lambda_1 ( A k ) 11 = 1 = λ 1 P k P_k P k 1 1 1 span { e 1 } \operatorname{span}\{e_1\} span { e 1 } e 1 e_1 e 1 dist ( e 1 , span { v 1 } ) = 1 \operatorname{dist}(e_1,\operatorname{span}\{v_1\})=1 dist ( e 1 , span { v 1 }) = 1 0 < ∣ η ∣ < 2 0<\lvert\eta\rvert<\sqrt2 0 < ∣ η ∣ < 2 A η : = ( 1 η η 2 ) A_\eta:=\begin{pmatrix}1&\eta\\\eta&2\end{pmatrix} A η := ( 1 η η 2 ) A η A_\eta A η μ ± : = ( 3 ± 1 + 4 η 2 ) / 2 \mu_\pm:=\bigl(3\pm\sqrt{1+4\eta^2}\bigr)/2 μ ± := ( 3 ± 1 + 4 η 2 ) /2 1 + 4 η 2 < 9 1+4\eta^2<9 1 + 4 η 2 < 9 μ − > 0 \mu_->0 μ − > 0 μ + > μ − > 0 \mu_+>\mu_->0 μ + > μ − > 0 σ = 0 \sigma=0 σ = 0 λ 1 = μ + \lambda_1=\mu_+ λ 1 = μ + λ 2 = μ − \lambda_2=\mu_- λ 2 = μ − v 1 v_1 v 1 v 2 v_2 v 2 §D3.15 定理 3.1 によりv 1 v_1 v 1 v 2 v_2 v 2 V = ( v 1 v 2 ) V=(v_1\ v_2) V = ( v 1 v 2 ) 定理 3.3 の固有値の条件が成り立ち、命題 3.4 (4) によりM 1 M_1 M 1 定理 3.3 (4) により、A η A_\eta A η ( 1 , 1 ) (1,1) ( 1 , 1 ) μ + \mu_+ μ + 1 + 4 η 2 > 1 \sqrt{1+4\eta^2}>1 1 + 4 η 2 > 1 μ + > 2 \mu_+>2 μ + > 2 η → 0 \eta\to0 η → 0 μ + → 2 \mu_+\to2 μ + → 2 η = 0 \eta=0 η = 0 ( 1 , 1 ) (1,1) ( 1 , 1 ) 1 1 1
4 Gershgorin の包含定理と固有値の摂動 定理 4.1 (Gershgorin の包含定理). n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 A = ( a i j ) ∈ C n × n A=(a_{ij})\in\C^{n\times n} A = ( a ij ) ∈ C n × n 1 ≤ i ≤ n 1\le i\le n 1 ≤ i ≤ n r i : = ∑ j ≠ i ∣ a i j ∣ r_i:=\sum_{j\ne i}\lvert a_{ij}\rvert r i := ∑ j = i ∣ a ij ∣ D i : = { z ∈ C ∣ ∣ z − a i i ∣ ≤ r i } \mathcal D_i:=\{z\in\C\mid\lvert z-a_{ii}\rvert\le r_i\} D i := { z ∈ C ∣ ∣ z − a ii ∣ ≤ r i } det ( λ I − A ) = 0 \det(\lambda I-A)=0 det ( λ I − A ) = 0 λ ∈ C \lambda\in\C λ ∈ C D 1 ∪ ⋯ ∪ D n \mathcal D_1\cup\dots\cup\mathcal D_n D 1 ∪ ⋯ ∪ D n
証明. A x = λ x Ax=\lambda x A x = λ x x ∈ C n ∖ { 0 } x\in\C^n\setminus\{0\} x ∈ C n ∖ { 0 } ∣ x i ∣ = max j ∣ x j ∣ \lvert x_i\rvert=\max_j\lvert x_j\rvert ∣ x i ∣ = max j ∣ x j ∣ i i i x ≠ 0 x\ne0 x = 0 ∣ x i ∣ > 0 \lvert x_i\rvert>0 ∣ x i ∣ > 0 A x = λ x Ax=\lambda x A x = λ x i i i ( λ − a i i ) x i = ∑ j ≠ i a i j x j (\lambda-a_{ii})x_i=\sum_{j\ne i}a_{ij}x_j ( λ − a ii ) x i = ∑ j = i a ij x j
∣ λ − a i i ∣ ∣ x i ∣ ≤ ∑ j ≠ i ∣ a i j ∣ ∣ x j ∣ ≤ r i ∣ x i ∣ \lvert\lambda-a_{ii}\rvert\lvert x_i\rvert\le\sum_{j\ne i}\lvert a_{ij}\rvert\lvert x_j\rvert\le r_i\lvert x_i\rvert ∣ λ − a ii ∣ ∣ x i ∣ ≤ j = i ∑ ∣ a ij ∣ ∣ x j ∣ ≤ r i ∣ x i ∣ である。両辺を∣ x i ∣ \lvert x_i\rvert ∣ x i ∣ λ ∈ D i \lambda\in\mathcal D_i λ ∈ D i ▨
系 4.2. n ≥ 2 n\ge2 n ≥ 2 A = ( a i j ) ∈ R n × n A=(a_{ij})\in\R^{n\times n} A = ( a ij ) ∈ R n × n A T = A A^{\mathsf T}=A A T = A r i : = ∑ j ≠ i ∣ a i j ∣ r_i:=\sum_{j\ne i}\lvert a_{ij}\rvert r i := ∑ j = i ∣ a ij ∣ ℓ : = min i ( a i i − r i ) \ell:=\min_i(a_{ii}-r_i) ℓ := min i ( a ii − r i ) u : = max i ( a i i + r i ) u:=\max_i(a_{ii}+r_i) u := max i ( a ii + r i )
det ( t I − A ) \det(tI-A) det ( t I − A ) [ ℓ , u ] [\ell,u] [ ℓ , u ] A A A σ < ℓ \sigma<\ell σ < ℓ det ( t I − A ) \det(tI-A) det ( t I − A ) λ 1 > λ 2 > ⋯ > λ n \lambda_1>\lambda_2>\dots>\lambda_n λ 1 > λ 2 > ⋯ > λ n V = ( v 1 ⋯ v n ) V=(v_1\ \cdots\ v_n) V = ( v 1 ⋯ v n ) A v i = λ i v i Av_i=\lambda_iv_i A v i = λ i v i V V V A A A σ \sigma σ V V V λ 1 , … , λ n \lambda_1,\dots,\lambda_n λ 1 , … , λ n 定理 3.3 の仮定をすべて満たし、同定理のq j q_j q j ( λ j + 1 − σ ) / ( λ j − σ ) (\lambda_{j+1}-\sigma)/(\lambda_j-\sigma) ( λ j + 1 − σ ) / ( λ j − σ ) (2) の仮定の下で、σ < σ ′ < ℓ \sigma<\sigma'<\ell σ < σ ′ < ℓ 1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 ( λ j + 1 − σ ′ ) / ( λ j − σ ′ ) < ( λ j + 1 − σ ) / ( λ j − σ ) (\lambda_{j+1}-\sigma')/(\lambda_j-\sigma')<(\lambda_{j+1}-\sigma)/(\lambda_j-\sigma) ( λ j + 1 − σ ′ ) / ( λ j − σ ′ ) < ( λ j + 1 − σ ) / ( λ j − σ ) 証明. (1) を示す。§E20.7 補題 2.1 (3) によりdet ( t I − A ) \det(tI-A) det ( t I − A ) λ \lambda λ 定理 4.1 によりあるi i i ∣ λ − a i i ∣ ≤ r i \lvert\lambda-a_{ii}\rvert\le r_i ∣ λ − a ii ∣ ≤ r i ℓ ≤ a i i − r i ≤ λ ≤ a i i + r i ≤ u \ell\le a_{ii}-r_i\le\lambda\le a_{ii}+r_i\le u ℓ ≤ a ii − r i ≤ λ ≤ a ii + r i ≤ u
(2) を示す。命題 3.4 (2) により根は相異なる。§E20.7 補題 2.1 (3) の正規直交基底q 1 , … , q n q_1,\dots,q_n q 1 , … , q n λ 1 ′ < ⋯ < λ n ′ \lambda'_1<\dots<\lambda'_n λ 1 ′ < ⋯ < λ n ′ v i : = q n + 1 − i v_i:=q_{n+1-i} v i := q n + 1 − i V V V A v i = λ i v i Av_i=\lambda_iv_i A v i = λ i v i (1) によりλ i ≥ ℓ > σ \lambda_i\ge\ell>\sigma λ i ≥ ℓ > σ λ 1 − σ > ⋯ > λ n − σ > 0 \lambda_1-\sigma>\dots>\lambda_n-\sigma>0 λ 1 − σ > ⋯ > λ n − σ > 0 ∣ λ i − σ ∣ = λ i − σ \lvert\lambda_i-\sigma\rvert=\lambda_i-\sigma ∣ λ i − σ ∣ = λ i − σ 命題 3.4 (4) によりM j M_j M j
(3) を示す。( λ j + 1 − σ ) / ( λ j − σ ) = 1 − ( λ j − λ j + 1 ) / ( λ j − σ ) (\lambda_{j+1}-\sigma)/(\lambda_j-\sigma)=1-(\lambda_j-\lambda_{j+1})/(\lambda_j-\sigma) ( λ j + 1 − σ ) / ( λ j − σ ) = 1 − ( λ j − λ j + 1 ) / ( λ j − σ ) λ j − λ j + 1 > 0 \lambda_j-\lambda_{j+1}>0 λ j − λ j + 1 > 0 0 < λ j − σ ′ < λ j − σ 0<\lambda_j-\sigma'<\lambda_j-\sigma 0 < λ j − σ ′ < λ j − σ σ ′ \sigma' σ ′ ▨
定理 4.3 (Weyl の不等式). n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 X T = X X^{\mathsf T}=X X T = X X ∈ R n × n X\in\R^{n\times n} X ∈ R n × n det ( t I − X ) \det(tI-X) det ( t I − X ) §E20.7 補題 2.1 (3) によりすべて実数である）を重複度を込めてλ 1 ( X ) ≤ ⋯ ≤ λ n ( X ) \lambda_1(X)\le\dots\le\lambda_n(X) λ 1 ( X ) ≤ ⋯ ≤ λ n ( X ) A , E ∈ R n × n A,E\in\R^{n\times n} A , E ∈ R n × n A T = A A^{\mathsf T}=A A T = A E T = E E^{\mathsf T}=E E T = E E E E ∥ E ∥ 2 \lVert E\rVert_2 ∥ E ∥ 2
∣ λ k ( A + E ) − λ k ( A ) ∣ ≤ ∥ E ∥ 2 ( 1 ≤ k ≤ n ) \lvert\lambda_k(A+E)-\lambda_k(A)\rvert\le\lVert E\rVert_2\qquad(1\le k\le n) ∣ λ k ( A + E ) − λ k ( A )∣ ≤ ∥ E ∥ 2 ( 1 ≤ k ≤ n ) が成り立つ。
証明. 単位ベクトルx ∈ R n x\in\R^n x ∈ R n §E20.6 補題 2.1 (1) による）により∣ x T E x ∣ ≤ ∥ x ∥ 2 ∥ E x ∥ 2 ≤ ∥ E ∥ 2 \lvert x^{\mathsf T}Ex\rvert\le\lVert x\rVert_2\lVert Ex\rVert_2\le\lVert E\rVert_2 ∣ x T E x ∣ ≤ ∥ x ∥ 2 ∥ E x ∥ 2 ≤ ∥ E ∥ 2 S ⊂ R n S\subset\R^n S ⊂ R n dim S = k \dim S=k dim S = k S S S x x x
x T ( A + E ) x ≤ x T A x + ∥ E ∥ 2 ≤ max y ∈ S , ∥ y ∥ 2 = 1 y T A y + ∥ E ∥ 2 x^{\mathsf T}(A+E)x\le x^{\mathsf T}Ax+\lVert E\rVert_2\le\max_{y\in S,\ \lVert y\rVert_2=1}y^{\mathsf T}Ay+\lVert E\rVert_2 x T ( A + E ) x ≤ x T A x + ∥ E ∥ 2 ≤ y ∈ S , ∥ y ∥ 2 = 1 max y T A y + ∥ E ∥ 2 である。§E20.7 定理 4.2 により、max y ∈ S , ∥ y ∥ 2 = 1 y T A y = λ k ( A ) \max_{y\in S,\ \lVert y\rVert_2=1}y^{\mathsf T}Ay=\lambda_k(A) max y ∈ S , ∥ y ∥ 2 = 1 y T A y = λ k ( A ) k k k S S S S S S λ k ( A + E ) \lambda_k(A+E) λ k ( A + E ) λ k ( A + E ) ≤ λ k ( A ) + ∥ E ∥ 2 \lambda_k(A+E)\le\lambda_k(A)+\lVert E\rVert_2 λ k ( A + E ) ≤ λ k ( A ) + ∥ E ∥ 2 A + E A+E A + E − E -E − E ∥ − E ∥ 2 = ∥ E ∥ 2 \lVert-E\rVert_2=\lVert E\rVert_2 ∥ − E ∥ 2 = ∥ E ∥ 2 λ k ( A ) ≤ λ k ( A + E ) + ∥ E ∥ 2 \lambda_k(A)\le\lambda_k(A+E)+\lVert E\rVert_2 λ k ( A ) ≤ λ k ( A + E ) + ∥ E ∥ 2 ▨
5 デフレーション 定義 5.1. n ≥ 2 n\ge2 n ≥ 2 T ∈ R n × n T\in\R^{n\times n} T ∈ R n × n 1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 T T T ( j + 1 , j ) (j+1,j) ( j + 1 , j ) ( j , j + 1 ) (j,j+1) ( j , j + 1 ) 0 0 0 T ′ T' T ′ T T T j j j デフレーション (deflation )T ′ T' T ′ j × j j\times j j × j T 1 T_1 T 1 ( n − j ) × ( n − j ) (n-j)\times(n-j) ( n − j ) × ( n − j ) T 2 T_2 T 2 T 1 T_1 T 1 T 2 T_2 T 2 T ′ = diag ( T 1 , T 2 ) T'=\operatorname{diag}(T_1,T_2) T ′ = diag ( T 1 , T 2 )
命題 5.2. n ≥ 2 n\ge2 n ≥ 2 T ∈ R n × n T\in\R^{n\times n} T ∈ R n × n 1 ≤ j ≤ n − 1 1\le j\le n-1 1 ≤ j ≤ n − 1 β : = t j + 1 , j \beta:=t_{j+1,j} β := t j + 1 , j T ′ T' T ′ T 1 T_1 T 1 T 2 T_2 T 2 定義 5.1 のとおりとする。λ k ( ⋅ ) \lambda_k(\cdot) λ k ( ⋅ ) 定理 4.3 の記号とする。
Euclid ノルムに関する作用素ノルムについて∥ T − T ′ ∥ 2 = ∣ β ∣ \lVert T-T'\rVert_2=\lvert\beta\rvert ∥ T − T ′ ∥ 2 = ∣ β ∣
det ( t I − T ′ ) = det ( t I j − T 1 ) det ( t I n − j − T 2 ) \det(tI-T')=\det(tI_j-T_1)\det(tI_{n-j}-T_2) det ( t I − T ′ ) = det ( t I j − T 1 ) det ( t I n − j − T 2 ) 1 ≤ k ≤ n 1\le k\le n 1 ≤ k ≤ n ∣ λ k ( T ′ ) − λ k ( T ) ∣ ≤ ∣ β ∣ \lvert\lambda_k(T')-\lambda_k(T)\rvert\le\lvert\beta\rvert ∣ λ k ( T ′ ) − λ k ( T )∣ ≤ ∣ β ∣ A ∈ R n × n A\in\R^{n\times n} A ∈ R n × n ( A k ) (A_k) ( A k ) A A A ( σ k ) (\sigma_k) ( σ k ) τ ≥ 0 \tau\ge0 τ ≥ 0 A k A_k A k ∣ ( A k ) j + 1 , j ∣ ≤ τ \lvert(A_k)_{j+1,j}\rvert\le\tau ∣( A k ) j + 1 , j ∣ ≤ τ A k A_k A k j j j j × j j\times j j × j ( n − j ) × ( n − j ) (n-j)\times(n-j) ( n − j ) × ( n − j ) μ 1 ≤ ⋯ ≤ μ n \mu_1\le\dots\le\mu_n μ 1 ≤ ⋯ ≤ μ n ∣ μ k − λ k ( A ) ∣ ≤ τ \lvert\mu_k-\lambda_k(A)\rvert\le\tau ∣ μ k − λ k ( A )∣ ≤ τ 1 ≤ k ≤ n 1\le k\le n 1 ≤ k ≤ n 証明. (1) を示す。T − T ′ = β ( e j + 1 e j T + e j e j + 1 T ) T-T'=\beta(e_{j+1}e_j^{\mathsf T}+e_je_{j+1}^{\mathsf T}) T − T ′ = β ( e j + 1 e j T + e j e j + 1 T ) h ∈ R n h\in\R^n h ∈ R n ( T − T ′ ) h = β ( h j e j + 1 + h j + 1 e j ) (T-T')h=\beta(h_je_{j+1}+h_{j+1}e_j) ( T − T ′ ) h = β ( h j e j + 1 + h j + 1 e j ) ∥ ( T − T ′ ) h ∥ 2 = ∣ β ∣ ( h j 2 + h j + 1 2 ) 1 / 2 ≤ ∣ β ∣ ∥ h ∥ 2 \lVert(T-T')h\rVert_2=\lvert\beta\rvert(h_j^2+h_{j+1}^2)^{1/2}\le\lvert\beta\rvert\lVert h\rVert_2 ∥( T − T ′ ) h ∥ 2 = ∣ β ∣ ( h j 2 + h j + 1 2 ) 1/2 ≤ ∣ β ∣ ∥ h ∥ 2 h = e j h=e_j h = e j
(2) を示す。t I − T ′ = diag ( t I j − T 1 , t I n − j − T 2 ) tI-T'=\operatorname{diag}(tI_j-T_1,\,tI_{n-j}-T_2) t I − T ′ = diag ( t I j − T 1 , t I n − j − T 2 )
(3) を示す。E : = T ′ − T E:=T'-T E := T ′ − T (1) により∥ E ∥ 2 = ∣ β ∣ \lVert E\rVert_2=\lvert\beta\rvert ∥ E ∥ 2 = ∣ β ∣ 定理 4.3 をT T T E E E
(4) を示す。命題 1.2 (3) によりA k A_k A k A k ′ A_k' A k ′ A k A_k A k j j j (2) によりμ k = λ k ( A k ′ ) \mu_k=\lambda_k(A_k') μ k = λ k ( A k ′ ) (3) により∣ μ k − λ k ( A k ) ∣ ≤ ∣ ( A k ) j + 1 , j ∣ ≤ τ \lvert\mu_k-\lambda_k(A_k)\rvert\le\lvert(A_k)_{j+1,j}\rvert\le\tau ∣ μ k − λ k ( A k )∣ ≤ ∣( A k ) j + 1 , j ∣ ≤ τ 命題 1.2 (1) によりdet ( t I − A k ) = det ( t I − A ) \det(tI-A_k)=\det(tI-A) det ( t I − A k ) = det ( t I − A ) λ k ( A k ) = λ k ( A ) \lambda_k(A_k)=\lambda_k(A) λ k ( A k ) = λ k ( A ) ▨
定義 5.3. n ≥ 2 n\ge2 n ≥ 2 A ∈ R n × n A\in\R^{n\times n} A ∈ R n × n A A A ( σ k ) (\sigma_k) ( σ k ) A k A_k A k A k A_k A k e n e_n e n σ k : = e n T A k e n = ( A k ) n n \sigma_k:=e_n^{\mathsf T}A_ke_n=(A_k)_{nn} σ k := e n T A k e n = ( A k ) nn Rayleigh シフト (Rayleigh quotient shift )A k A_k A k 2 × 2 2\times2 2 × 2 ( a b b c ) \begin{pmatrix}a&b\\b&c\end{pmatrix} ( a b b c ) a + c 2 ± ( a − c 2 ) 2 + b 2 \frac{a+c}{2}\pm\sqrt{\bigl(\frac{a-c}{2}\bigr)^2+b^2} 2 a + c ± ( 2 a − c ) 2 + b 2 c c c σ k \sigma_k σ k Wilkinson シフト (Wilkinson shift )A k − σ k I A_k-\sigma_kI A k − σ k I A k + 1 A_{k+1} A k + 1
例 5.4. n = 2 n=2 n = 2 A k = ( a b b c ) A_k=\begin{pmatrix}a&b\\b&c\end{pmatrix} A k = ( a b b c ) h : = ( a − c ) / 2 h:=(a-c)/2 h := ( a − c ) /2 s : = h 2 + b 2 s:=\sqrt{h^2+b^2} s := h 2 + b 2 σ k = ( a + c ) / 2 + ϵ s \sigma_k=(a+c)/2+\epsilon s σ k = ( a + c ) /2 + ϵs ϵ ∈ { 1 , − 1 } \epsilon\in\{1,-1\} ϵ ∈ { 1 , − 1 } σ k − a = ϵ s − h \sigma_k-a=\epsilon s-h σ k − a = ϵs − h σ k − c = ϵ s + h \sigma_k-c=\epsilon s+h σ k − c = ϵs + h
det ( A k − σ k I ) = ( σ k − a ) ( σ k − c ) − b 2 = s 2 − h 2 − b 2 = 0 \det(A_k-\sigma_kI)=(\sigma_k-a)(\sigma_k-c)-b^2=s^2-h^2-b^2=0 det ( A k − σ k I ) = ( σ k − a ) ( σ k − c ) − b 2 = s 2 − h 2 − b 2 = 0 である。したがってA k − σ k I A_k-\sigma_kI A k − σ k I 定義 1.1 (1) はA k + 1 A_{k+1} A k + 1 J : = ( 0 1 1 0 ) J:=\begin{pmatrix}0&1\\1&0\end{pmatrix} J := ( 0 1 1 0 ) A 0 = J A_0=J A 0 = J σ 0 = ( J ) 22 = 0 \sigma_0=(J)_{22}=0 σ 0 = ( J ) 22 = 0 J − σ 0 I = J J-\sigma_0I=J J − σ 0 I = J J T J = I J^{\mathsf T}J=I J T J = I J = J ⋅ I J=J\cdot I J = J ⋅ I J J J §D3.17 定理 1.2 の一意性によりQ 0 = J Q_0=J Q 0 = J R 0 = I R_0=I R 0 = I A 1 = R 0 Q 0 + 0 ⋅ I = J A_1=R_0Q_0+0\cdot I=J A 1 = R 0 Q 0 + 0 ⋅ I = J k k k k k k σ k = 0 \sigma_k=0 σ k = 0 A k = J A_k=J A k = J J J J ( A k ) 21 = 1 (A_k)_{21}=1 ( A k ) 21 = 1 0 0 0
例 5.5.
T : = ( 2 1 0 1 3 1 0 1 4 ) T:=\begin{pmatrix}2&1&0\\1&3&1\\0&1&4\end{pmatrix} T := 2 1 0 1 3 1 0 1 4 とする。det ( t I − T ) = t 3 − 9 t 2 + 24 t − 18 = ( t − 3 ) ( t 2 − 6 t + 6 ) \det(tI-T)=t^3-9t^2+24t-18=(t-3)(t^2-6t+6) det ( t I − T ) = t 3 − 9 t 2 + 24 t − 18 = ( t − 3 ) ( t 2 − 6 t + 6 ) 3 + 3 3+\sqrt3 3 + 3 3 3 3 3 − 3 3-\sqrt3 3 − 3 ( 1 , 1 + 3 , 2 + 3 ) T (1,1+\sqrt3,2+\sqrt3)^{\mathsf T} ( 1 , 1 + 3 , 2 + 3 ) T ( 1 , 1 , − 1 ) T (1,1,-1)^{\mathsf T} ( 1 , 1 , − 1 ) T ( 1 , 1 − 3 , 2 − 3 ) T (1,1-\sqrt3,2-\sqrt3)^{\mathsf T} ( 1 , 1 − 3 , 2 − 3 ) T 系 4.2 のℓ \ell ℓ min { 2 − 1 , 3 − 2 , 4 − 1 } = 1 \min\{2-1,3-2,4-1\}=1 min { 2 − 1 , 3 − 2 , 4 − 1 } = 1 T T T 系 4.2 (2) により、σ < 1 \sigma<1 σ < 1 定理 3.3 がλ 1 = 3 + 3 \lambda_1=3+\sqrt3 λ 1 = 3 + 3 λ 2 = 3 \lambda_2=3 λ 2 = 3 λ 3 = 3 − 3 \lambda_3=3-\sqrt3 λ 3 = 3 − 3 V V V t 2 = 4.6252 … t_2=4.6252\ldots t 2 = 4.6252 …
T T T σ = 0 \sigma=0 σ = 0 σ = 9 / 10 \sigma=9/10 σ = 9/10 60 60 60 ∣ ( A k ) 32 ∣ ≤ 10 − 10 \lvert(A_k)_{32}\rvert\le10^{-10} ∣( A k ) 32 ∣ ≤ 1 0 − 10 k k k 3 3 3
σ = 0 \sigma=0 σ = 0 q 2 = ( 3 − 3 ) / 3 = 0.4226 … q_2=(3-\sqrt3)/3=0.4226\ldots q 2 = ( 3 − 3 ) /3 = 0.4226 … k = 29 k=29 k = 29 ∣ ( A 29 ) 32 ∣ = 6.74 × 10 − 11 \lvert(A_{29})_{32}\rvert=6.74\times10^{-11} ∣( A 29 ) 32 ∣ = 6.74 × 1 0 − 11 定理 3.3 (3) の上界2 λ 1 t 2 q 2 29 2\lambda_1t_2q_2^{29} 2 λ 1 t 2 q 2 29 6.23 × 10 − 10 6.23\times10^{-10} 6.23 × 1 0 − 10 σ = 9 / 10 \sigma=9/10 σ = 9/10 q 2 = ( 2.1 − 3 ) / 2.1 = 0.1752 … q_2=(2.1-\sqrt3)/2.1=0.1752\ldots q 2 = ( 2.1 − 3 ) /2.1 = 0.1752 … 系 4.2 (3) のとおりσ = 0 \sigma=0 σ = 0 k = 15 k=15 k = 15 ∣ ( A 15 ) 32 ∣ = 2.13 × 10 − 11 \lvert(A_{15})_{32}\rvert=2.13\times10^{-11} ∣( A 15 ) 32 ∣ = 2.13 × 1 0 − 11 2 ( λ 1 − 9 10 ) t 2 q 2 15 2(\lambda_1-\tfrac9{10})t_2q_2^{15} 2 ( λ 1 − 10 9 ) t 2 q 2 15 1.60 × 10 − 10 1.60\times10^{-10} 1.60 × 1 0 − 10 k k k ∣ ( A k ) 32 ∣ \lvert(A_k)_{32}\rvert ∣( A k ) 32 ∣ ∣ ( A k ) 21 ∣ \lvert(A_k)_{21}\rvert ∣( A k ) 21 ∣ 定理 3.3 (3) の上界以下であった。Rayleigh シフトでは、k = 1 , … , 5 k=1,\dots,5 k = 1 , … , 5 ∣ ( A k ) 32 ∣ \lvert(A_k)_{32}\rvert ∣( A k ) 32 ∣ 7.45 × 10 − 1 7.45\times10^{-1} 7.45 × 1 0 − 1 2.72 × 10 − 1 2.72\times10^{-1} 2.72 × 1 0 − 1 7.19 × 10 − 3 7.19\times10^{-3} 7.19 × 1 0 − 3 1.24 × 10 − 7 1.24\times10^{-7} 1.24 × 1 0 − 7 6.27 × 10 − 22 6.27\times10^{-22} 6.27 × 1 0 − 22 k = 3 , 4 k=3,4 k = 3 , 4 ∣ ( A k + 1 ) 32 ∣ / ∣ ( A k ) 32 ∣ 3 \lvert(A_{k+1})_{32}\rvert/\lvert(A_k)_{32}\rvert^3 ∣( A k + 1 ) 32 ∣ / ∣( A k ) 32 ∣ 3 0.332 0.332 0.332 0.333 0.333 0.333 ( A 5 ) 33 (A_5)_{33} ( A 5 ) 33 3 + 3 3+\sqrt3 3 + 3 10 − 40 10^{-40} 1 0 − 40
Wilkinson シフトでは、k = 1 , 2 , 3 k=1,2,3 k = 1 , 2 , 3 ∣ ( A k ) 32 ∣ \lvert(A_k)_{32}\rvert ∣( A k ) 32 ∣ 9.45 × 10 − 2 9.45\times10^{-2} 9.45 × 1 0 − 2 1.21 × 10 − 5 1.21\times10^{-5} 1.21 × 1 0 − 5 8.27 × 10 − 18 8.27\times10^{-18} 8.27 × 1 0 − 18 ( A 3 ) 33 (A_3)_{33} ( A 3 ) 33 3 + 3 3+\sqrt3 3 + 3 10 − 30 10^{-30} 1 0 − 30
命題 5.2 (4) をj = 2 j=2 j = 2 τ = 10 − 10 \tau=10^{-10} τ = 1 0 − 10 A k A_k A k ∣ ( A k ) 32 ∣ ≤ 10 − 10 \lvert(A_k)_{32}\rvert\le10^{-10} ∣( A k ) 32 ∣ ≤ 1 0 − 10 ( A k ) 33 (A_k)_{33} ( A k ) 33 A k A_k A k 2 × 2 2\times2 2 × 2 T T T 10 − 10 10^{-10} 1 0 − 10 A k A_k A k 60 60 60 k k k T T T 10 − 20 10^{-20} 1 0 − 20 ( A k ) 33 (A_k)_{33} ( A k ) 33 T T T 定理 3.3 (4) と整合して最小の固有値3 − 3 3-\sqrt3 3 − 3 3 + 3 3+\sqrt3 3 + 3
6 一般の実行列 例 6.1. J : = ( 0 1 1 0 ) J:=\begin{pmatrix}0&1\\1&0\end{pmatrix} J := ( 0 1 1 0 ) J = J ⋅ I J=J\cdot I J = J ⋅ I J J J §D3.17 定理 1.2 の一意性により、J J J Q 0 = J Q_0=J Q 0 = J R 0 = I R_0=I R 0 = I A 1 = R 0 Q 0 = J A_1=R_0Q_0=J A 1 = R 0 Q 0 = J k k k A k = J A_k=J A k = J J J J 1 1 1 − 1 -1 − 1 σ = 0 \sigma=0 σ = 0 定理 3.3 の仮定∣ λ 1 − σ ∣ > ∣ λ 2 − σ ∣ \lvert\lambda_1-\sigma\rvert>\lvert\lambda_2-\sigma\rvert ∣ λ 1 − σ ∣ > ∣ λ 2 − σ ∣ σ ∉ { − 1 , 0 , 1 } \sigma\notin\{-1,0,1\} σ ∈ / { − 1 , 0 , 1 } ∣ 1 − σ ∣ ≠ ∣ − 1 − σ ∣ \lvert1-\sigma\rvert\ne\lvert-1-\sigma\rvert ∣ 1 − σ ∣ = ∣ − 1 − σ ∣ J J J 命題 3.4 (4) により同定理の仮定が満たされ、非対角成分は0 0 0 K : = ( 0 − 1 1 0 ) K:=\begin{pmatrix}0&-1\\1&0\end{pmatrix} K := ( 0 1 − 1 0 ) K K K k k k A k = K A_k=K A k = K det ( t I − K ) = t 2 + 1 \det(tI-K)=t^2+1 det ( t I − K ) = t 2 + 1 ± i \pm\mathrm i ± i 命題 1.2 (4) により、どのシフト( σ k ) (\sigma_k) ( σ k ) A k A_k A k ( A k ) (A_k) ( A k )
7 演習 問題 7.1. a , b , c ∈ R a,b,c\in\R a , b , c ∈ R b ≠ 0 b\ne0 b = 0 A : = ( a b b c ) A:=\begin{pmatrix}a&b\\b&c\end{pmatrix} A := ( a b b c ) d : = a − c d:=a-c d := a − c A A A σ 0 = c \sigma_0=c σ 0 = c A − c I A-cI A − c I
A 1 = ( a + d b 2 d 2 + b 2 b 3 d 2 + b 2 b 3 d 2 + b 2 c − d b 2 d 2 + b 2 ) A_1=\begin{pmatrix}a+\dfrac{db^2}{d^2+b^2}&\dfrac{b^3}{d^2+b^2}\\[2mm]\dfrac{b^3}{d^2+b^2}&c-\dfrac{db^2}{d^2+b^2}\end{pmatrix} A 1 = a + d 2 + b 2 d b 2 d 2 + b 2 b 3 d 2 + b 2 b 3 c − d 2 + b 2 d b 2 であることを示せ。またd ≠ 0 d\ne0 d = 0 ∣ ( A 1 ) 21 ∣ ≤ ∣ b ∣ 3 / d 2 \lvert(A_1)_{21}\rvert\le\lvert b\rvert^3/d^2 ∣( A 1 ) 21 ∣ ≤ ∣ b ∣ 3 / d 2
解答. det ( A − c I ) = d ⋅ 0 − b 2 = − b 2 ≠ 0 \det(A-cI)=d\cdot0-b^2=-b^2\ne0 det ( A − c I ) = d ⋅ 0 − b 2 = − b 2 = 0 A − c I A-cI A − c I A − c I = ( d b b 0 ) A-cI=\begin{pmatrix}d&b\\b&0\end{pmatrix} A − c I = ( d b b 0 ) 命題 2.3 をn = 2 n=2 n = 2 r : = r 1 = d 2 + b 2 > 0 r:=r_1=\sqrt{d^2+b^2}>0 r := r 1 = d 2 + b 2 > 0 c 1 = d / r c_1=d/r c 1 = d / r s 1 = b / r s_1=b/r s 1 = b / r
W ( 1 ) = G 1 T ( A − c I ) = ( d / r b / r − b / r d / r ) ( d b b 0 ) = ( r d b / r 0 − b 2 / r ) W^{(1)}=G_1^{\mathsf T}(A-cI)=\begin{pmatrix}d/r&b/r\\-b/r&d/r\end{pmatrix}\begin{pmatrix}d&b\\b&0\end{pmatrix}=\begin{pmatrix}r&db/r\\0&-b^2/r\end{pmatrix} W ( 1 ) = G 1 T ( A − c I ) = ( d / r − b / r b / r d / r ) ( d b b 0 ) = ( r 0 d b / r − b 2 / r ) である。w = − b 2 / r < 0 w=-b^2/r<0 w = − b 2 / r < 0 S = diag ( 1 , − 1 ) S=\operatorname{diag}(1,-1) S = diag ( 1 , − 1 ) 命題 2.3 (2) により
R 0 = ( r d b / r 0 b 2 / r ) , Q 0 = G 1 S = ( d / r b / r b / r − d / r ) R_0=\begin{pmatrix}r&db/r\\0&b^2/r\end{pmatrix},\qquad Q_0=G_1S=\begin{pmatrix}d/r&b/r\\b/r&-d/r\end{pmatrix} R 0 = ( r 0 d b / r b 2 / r ) , Q 0 = G 1 S = ( d / r b / r b / r − d / r ) である。
R 0 Q 0 = ( d + d b 2 / r 2 b − d 2 b / r 2 b 3 / r 2 − d b 2 / r 2 ) R_0Q_0=\begin{pmatrix}d+db^2/r^2&b-d^2b/r^2\\b^3/r^2&-db^2/r^2\end{pmatrix} R 0 Q 0 = ( d + d b 2 / r 2 b 3 / r 2 b − d 2 b / r 2 − d b 2 / r 2 ) であり、b − d 2 b / r 2 = b ( r 2 − d 2 ) / r 2 = b 3 / r 2 b-d^2b/r^2=b(r^2-d^2)/r^2=b^3/r^2 b − d 2 b / r 2 = b ( r 2 − d 2 ) / r 2 = b 3 / r 2 A 1 = R 0 Q 0 + c I A_1=R_0Q_0+cI A 1 = R 0 Q 0 + c I d + c = a d+c=a d + c = a d ≠ 0 d\ne0 d = 0 r 2 ≥ d 2 r^2\ge d^2 r 2 ≥ d 2 ∣ ( A 1 ) 21 ∣ = ∣ b ∣ 3 / r 2 ≤ ∣ b ∣ 3 / d 2 \lvert(A_1)_{21}\rvert=\lvert b\rvert^3/r^2\le\lvert b\rvert^3/d^2 ∣( A 1 ) 21 ∣ = ∣ b ∣ 3 / r 2 ≤ ∣ b ∣ 3 / d 2 ▨
問題 7.2. a , c , β ∈ R a,c,\beta\in\R a , c , β ∈ R a ≤ c a\le c a ≤ c T : = ( a β β c ) T:=\begin{pmatrix}a&\beta\\\beta&c\end{pmatrix} T := ( a β β c ) T ′ : = diag ( a , c ) T':=\operatorname{diag}(a,c) T ′ := diag ( a , c ) λ k ( ⋅ ) \lambda_k(\cdot) λ k ( ⋅ ) 定理 4.3 の記号とする。a = c a=c a = c ∣ λ k ( T ) − λ k ( T ′ ) ∣ = ∣ β ∣ \lvert\lambda_k(T)-\lambda_k(T')\rvert=\lvert\beta\rvert ∣ λ k ( T ) − λ k ( T ′ )∣ = ∣ β ∣ k = 1 , 2 k=1,2 k = 1 , 2 a < c a<c a < c ∣ λ k ( T ) − λ k ( T ′ ) ∣ ≤ β 2 / ( c − a ) \lvert\lambda_k(T)-\lambda_k(T')\rvert\le\beta^2/(c-a) ∣ λ k ( T ) − λ k ( T ′ )∣ ≤ β 2 / ( c − a ) k = 1 , 2 k=1,2 k = 1 , 2
解答. g : = ( c − a ) / 2 ≥ 0 g:=(c-a)/2\ge0 g := ( c − a ) /2 ≥ 0 m : = ( a + c ) / 2 m:=(a+c)/2 m := ( a + c ) /2 det ( t I − T ) = ( t − m ) 2 − g 2 − β 2 \det(tI-T)=(t-m)^2-g^2-\beta^2 det ( t I − T ) = ( t − m ) 2 − g 2 − β 2 λ 1 ( T ) = m − g 2 + β 2 \lambda_1(T)=m-\sqrt{g^2+\beta^2} λ 1 ( T ) = m − g 2 + β 2 λ 2 ( T ) = m + g 2 + β 2 \lambda_2(T)=m+\sqrt{g^2+\beta^2} λ 2 ( T ) = m + g 2 + β 2 λ 1 ( T ′ ) = a = m − g \lambda_1(T')=a=m-g λ 1 ( T ′ ) = a = m − g λ 2 ( T ′ ) = c = m + g \lambda_2(T')=c=m+g λ 2 ( T ′ ) = c = m + g k = 1 , 2 k=1,2 k = 1 , 2
∣ λ k ( T ) − λ k ( T ′ ) ∣ = g 2 + β 2 − g \lvert\lambda_k(T)-\lambda_k(T')\rvert=\sqrt{g^2+\beta^2}-g ∣ λ k ( T ) − λ k ( T ′ )∣ = g 2 + β 2 − g である。a = c a=c a = c g = 0 g=0 g = 0 ∣ β ∣ \lvert\beta\rvert ∣ β ∣ a < c a<c a < c g > 0 g>0 g > 0 β 2 / ( g 2 + β 2 + g ) ≤ β 2 / ( 2 g ) = β 2 / ( c − a ) \beta^2/\bigl(\sqrt{g^2+\beta^2}+g\bigr)\le\beta^2/(2g)=\beta^2/(c-a) β 2 / ( g 2 + β 2 + g ) ≤ β 2 / ( 2 g ) = β 2 / ( c − a ) ▨