1 浮動小数点算術と三角系の代入 定義 1.1. 加算・減算・乗算・除算を定められた順序で有限回行って値を定める計算式について、各演算で二つの被演算数に対するその演算の実数としての値を計算することを、計算式を 厳密算術 (exact arithmetic )F F F fl \operatorname{fl} fl F F F F F F x ∘ y x\circ y x ∘ y ∘ ∈ { + , − , × , / } \circ\in\{+,-,\times,/\} ∘ ∈ { + , − , × , / } fl ( x ∘ y ) \operatorname{fl}(x\circ y) fl ( x ∘ y ) F F F fl \operatorname{fl} fl 浮動小数点算術 (floating-point arithmetic )x ∘ y x\circ y x ∘ y 範囲条件 (range condition )
各乗算と各除算の厳密な結果は、0 0 0 F F F
各加算と各減算の厳密な結果の絶対値は、F F F N max N_{\max} N m a x
定義 1.2. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 T = ( t i j ) ∈ M n ( R ) T=(t_{ij})\in M_n(\R) T = ( t ij ) ∈ M n ( R ) 0 0 0 c = ( c 1 , … , c n ) ∈ R n c=(c_1,\dots,c_n)\in\R^n c = ( c 1 , … , c n ) ∈ R n
T T T i = 1 , … , n i=1,\dots,n i = 1 , … , n T y = c Ty=c T y = c 前進代入 (forward substitution )s : = c i s:=c_i s := c i m = 1 , … , i − 1 m=1,\dots,i-1 m = 1 , … , i − 1 t i m y m t_{im}y_m t im y m s s s s − t i m y m s-t_{im}y_m s − t im y m s s s y i : = s / t i i y_i:=s/t_{ii} y i := s / t ii T T T 1 1 1 y i : = s y_i:=s y i := s T T T i = n , n − 1 , … , 1 i=n,n-1,\dots,1 i = n , n − 1 , … , 1 T y = c Ty=c T y = c 後退代入 (back substitution )s : = c i s:=c_i s := c i m = i + 1 , … , n m=i+1,\dots,n m = i + 1 , … , n t i m y m t_{im}y_m t im y m s s s s − t i m y m s-t_{im}y_m s − t im y m s s s y i : = s / t i i y_i:=s/t_{ii} y i := s / t ii 2 LU 分解 定義 2.1. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 B ∈ M n ( R ) B\in M_n(\R) B ∈ M n ( R ) 1 1 1 L L L U U U B = L U B=LU B = LU ( L , U ) (L,U) ( L , U ) B B B LU 分解 (LU factorization )P P P ( L , U ) (L,U) ( L , U ) P B PB P B ( P , L , U ) (P,L,U) ( P , L , U ) B B B ピボット付き LU 分解 (pivoted LU factorization )
定義 2.2. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 A ∈ M n ( R ) A\in M_n(\R) A ∈ M n ( R ) 1 ≤ k ≤ r ≤ n 1\le k\le r\le n 1 ≤ k ≤ r ≤ n k k k r r r T k r T_{kr} T k r T k k = I T_{kk}=I T k k = I W ( 1 ) : = A W^{(1)}:=A W ( 1 ) := A k = 1 , … , n k=1,\dots,n k = 1 , … , n k k k A A A 部分ピボット付き消去 (Gaussian elimination with partial pivoting )
∣ w r k ( k ) ∣ = max k ≤ i ≤ n ∣ w i k ( k ) ∣ \lvert w^{(k)}_{rk}\rvert=\max_{k\le i\le n}\lvert w^{(k)}_{ik}\rvert ∣ w r k ( k ) ∣ = max k ≤ i ≤ n ∣ w ik ( k ) ∣ r ∈ { k , … , n } r\in\{k,\dots,n\} r ∈ { k , … , n } r k r_k r k V ( k ) : = T k r k W ( k ) V^{(k)}:=T_{kr_k}W^{(k)} V ( k ) := T k r k W ( k ) 1 1 1 n n n v k k ( k ) v^{(k)}_{kk} v k k ( k ) k k k ピボット (pivot )v k k ( k ) = 0 v^{(k)}_{kk}=0 v k k ( k ) = 0 k k k 失敗 (breakdown )k < n k<n k < n W ( k + 1 ) W^{(k+1)} W ( k + 1 ) i i i i ≤ k i\le k i ≤ k V ( k ) V^{(k)} V ( k ) i i i i > k i>k i > k w i j ( k + 1 ) : = v i j ( k ) ( j < k ) , w i k ( k + 1 ) : = v i k ( k ) v k k ( k ) , w i j ( k + 1 ) : = v i j ( k ) − w i k ( k + 1 ) v k j ( k ) ( j > k ) w^{(k+1)}_{ij}:=v^{(k)}_{ij}\ (j<k),\qquad w^{(k+1)}_{ik}:=\frac{v^{(k)}_{ik}}{v^{(k)}_{kk}},\qquad w^{(k+1)}_{ij}:=v^{(k)}_{ij}-w^{(k+1)}_{ik}v^{(k)}_{kj}\ (j>k) w ij ( k + 1 ) := v ij ( k ) ( j < k ) , w ik ( k + 1 ) := v k k ( k ) v ik ( k ) , w ij ( k + 1 ) := v ij ( k ) − w ik ( k + 1 ) v k j ( k ) ( j > k ) w i k ( k + 1 ) v k j ( k ) w^{(k+1)}_{ik}v^{(k)}_{kj} w ik ( k + 1 ) v k j ( k ) w i k ( k + 1 ) w^{(k+1)}_{ik} w ik ( k + 1 ) i > k i>k i > k k k k 乗数 (multiplier ) どの段でも失敗しないとき、消去は完了するという。このときW : = V ( n ) W:=V^{(n)} W := V ( n ) i > j i>j i > j w i j w_{ij} w ij 1 1 1 0 0 0 L L L i ≤ j i\le j i ≤ j w i j w_{ij} w ij 0 0 0 U U U P : = T n r n T n − 1 , r n − 1 ⋯ T 1 r 1 P:=T_{nr_n}T_{n-1,r_{n-1}}\cdots T_{1r_1} P := T n r n T n − 1 , r n − 1 ⋯ T 1 r 1 ( P , L , U ) (P,L,U) ( P , L , U ) (1) で常にr k : = k r_k:=k r k := k A A A ピボット選択なしの消去 (Gaussian elimination without pivoting )( L , U ) (L,U) ( L , U )
補題 2.3. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 B ∈ M n ( R ) B\in M_n(\R) B ∈ M n ( R ) 1 ≤ k ≤ n 1\le k\le n 1 ≤ k ≤ n B B B 1 , … , k − 1 1,\dots,k-1 1 , … , k − 1 k k k W ( k ) W^{(k)} W ( k ) 1 1 1 j < k j<k j < k i > j i>j i > j ( i , j ) (i,j) ( i , j ) w i j ( k ) w^{(k)}_{ij} w ij ( k ) 0 0 0 L ( k ) L^{(k)} L ( k ) i < k i<k i < k i ≤ j i\le j i ≤ j ( i , j ) (i,j) ( i , j ) i , j ≥ k i,j\ge k i , j ≥ k ( i , j ) (i,j) ( i , j ) w i j ( k ) w^{(k)}_{ij} w ij ( k ) 0 0 0 R ( k ) R^{(k)} R ( k ) B = L ( k ) R ( k ) B=L^{(k)}R^{(k)} B = L ( k ) R ( k ) ( L , U ) (L,U) ( L , U ) B B B
証明. k = 1 k=1 k = 1 L ( 1 ) = I L^{(1)}=I L ( 1 ) = I R ( 1 ) = W ( 1 ) = B R^{(1)}=W^{(1)}=B R ( 1 ) = W ( 1 ) = B k < n k<n k < n B = L ( k ) R ( k ) B=L^{(k)}R^{(k)} B = L ( k ) R ( k ) k k k V ( k ) = W ( k ) V^{(k)}=W^{(k)} V ( k ) = W ( k ) ℓ ∈ R n \ell\in\R^n ℓ ∈ R n i > k i>k i > k k k k w i k ( k + 1 ) w^{(k+1)}_{ik} w ik ( k + 1 ) 0 0 0 e k e_k e k k k k G : = I + ℓ e k T G:=I+\ell e_k^{\mathsf T} G := I + ℓ e k T G R ( k + 1 ) GR^{(k+1)} G R ( k + 1 ) i i i i ≤ k i\le k i ≤ k R ( k + 1 ) R^{(k+1)} R ( k + 1 ) i i i i > k i>k i > k R ( k + 1 ) R^{(k+1)} R ( k + 1 ) i i i k k k w i k ( k + 1 ) w^{(k+1)}_{ik} w ik ( k + 1 ) W ( k + 1 ) W^{(k+1)} W ( k + 1 ) 1 1 1 k k k W ( k ) W^{(k)} W ( k ) i ≤ k i\le k i ≤ k R ( k + 1 ) R^{(k+1)} R ( k + 1 ) R ( k ) R^{(k)} R ( k ) i i i R ( k + 1 ) R^{(k+1)} R ( k + 1 ) k k k ( 0 , … , 0 , w k k ( k ) , … , w k n ( k ) ) (0,\dots,0,w^{(k)}_{kk},\dots,w^{(k)}_{kn}) ( 0 , … , 0 , w k k ( k ) , … , w k n ( k ) ) i > k i>k i > k G R ( k + 1 ) GR^{(k+1)} G R ( k + 1 ) ( i , j ) (i,j) ( i , j ) j < k j<k j < k 0 0 0 j = k j=k j = k w i k ( k + 1 ) w k k ( k ) = w i k ( k ) w^{(k+1)}_{ik}w^{(k)}_{kk}=w^{(k)}_{ik} w ik ( k + 1 ) w k k ( k ) = w ik ( k ) j > k j>k j > k w i j ( k + 1 ) + w i k ( k + 1 ) w k j ( k ) = w i j ( k ) w^{(k+1)}_{ij}+w^{(k+1)}_{ik}w^{(k)}_{kj}=w^{(k)}_{ij} w ij ( k + 1 ) + w ik ( k + 1 ) w k j ( k ) = w ij ( k ) R ( k ) R^{(k)} R ( k ) ( i , j ) (i,j) ( i , j ) R ( k ) = G R ( k + 1 ) R^{(k)}=GR^{(k+1)} R ( k ) = G R ( k + 1 ) L ( k ) L^{(k)} L ( k ) k k k n n n ℓ \ell ℓ 1 1 1 k k k 0 0 0 L ( k ) ℓ = ℓ L^{(k)}\ell=\ell L ( k ) ℓ = ℓ W ( k + 1 ) W^{(k+1)} W ( k + 1 ) W ( k ) W^{(k)} W ( k ) j < k j<k j < k L ( k ) G = L ( k ) + ℓ e k T = L ( k + 1 ) L^{(k)}G=L^{(k)}+\ell e_k^{\mathsf T}=L^{(k+1)} L ( k ) G = L ( k ) + ℓ e k T = L ( k + 1 ) B = L ( k ) G R ( k + 1 ) = L ( k + 1 ) R ( k + 1 ) B=L^{(k)}GR^{(k+1)}=L^{(k+1)}R^{(k+1)} B = L ( k ) G R ( k + 1 ) = L ( k + 1 ) R ( k + 1 ) k k k W = V ( n ) = W ( n ) W=V^{(n)}=W^{(n)} W = V ( n ) = W ( n ) L ( n ) = L L^{(n)}=L L ( n ) = L R ( n ) = U R^{(n)}=U R ( n ) = U ▨
補題 2.4. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 A ∈ M n ( R ) A\in M_n(\R) A ∈ M n ( R ) 1 ≤ k ≤ n 1\le k\le n 1 ≤ k ≤ n A A A 1 , … , k − 1 1,\dots,k-1 1 , … , k − 1 j j j r j r_j r j Π k : = T k − 1 , r k − 1 ⋯ T 1 r 1 \Pi_k:=T_{k-1,r_{k-1}}\cdots T_{1r_1} Π k := T k − 1 , r k − 1 ⋯ T 1 r 1 Π 1 : = I \Pi_1:=I Π 1 := I Π k A \Pi_kA Π k A
段1 , … , k − 1 1,\dots,k-1 1 , … , k − 1 j ≤ k − 1 j\le k-1 j ≤ k − 1 j j j k k k k k k W ( k ) W^{(k)} W ( k ) 1 , … , k − 1 1,\dots,k-1 1 , … , k − 1
部分ピボット付き消去が完了し、その出力が( P , L , U ) (P,L,U) ( P , L , U ) P A PA P A ( L , U ) (L,U) ( L , U )
証明. Π k A \Pi_kA Π k A j j j W ~ ( j ) \widetilde W^{(j)} W ( j ) 1 ≤ j ≤ k 1\le j\le k 1 ≤ j ≤ k Q j : = T k − 1 , r k − 1 ⋯ T j r j Q_j:=T_{k-1,r_{k-1}}\cdots T_{jr_j} Q j := T k − 1 , r k − 1 ⋯ T j r j Q k : = I Q_k:=I Q k := I j = 1 j=1 j = 1 W ~ ( 1 ) = Π k A = Q 1 W ( 1 ) \widetilde W^{(1)}=\Pi_kA=Q_1W^{(1)} W ( 1 ) = Π k A = Q 1 W ( 1 ) j < k j<k j < k W ~ ( j ) = Q j W ( j ) \widetilde W^{(j)}=Q_jW^{(j)} W ( j ) = Q j W ( j ) Q j = Q j + 1 T j r j Q_j=Q_{j+1}T_{jr_j} Q j = Q j + 1 T j r j W ~ ( j ) = Q j + 1 V ( j ) \widetilde W^{(j)}=Q_{j+1}V^{(j)} W ( j ) = Q j + 1 V ( j ) Q j + 1 Q_{j+1} Q j + 1 m ≥ j + 1 m\ge j+1 m ≥ j + 1 r m ≥ m r_m\ge m r m ≥ m T m r m T_{mr_m} T m r m { j + 1 , … , n } \{j+1,\dots,n\} { j + 1 , … , n } σ \sigma σ X ∈ M n ( R ) X\in M_n(\R) X ∈ M n ( R ) Q j + 1 X Q_{j+1}X Q j + 1 X i i i i ≤ j i\le j i ≤ j X X X i i i i > j i>j i > j X X X σ ( i ) \sigma(i) σ ( i ) W ~ ( j ) \widetilde W^{(j)} W ( j ) j j j V ( j ) V^{(j)} V ( j ) j j j j j j v j j ( j ) ≠ 0 v^{(j)}_{jj}\ne0 v j j ( j ) = 0 定義 2.2 (3) により、段j j j i i i i > j i>j i > j i i i j j j W ~ ( j ) \widetilde W^{(j)} W ( j ) i i i V ( j ) V^{(j)} V ( j ) σ ( i ) \sigma(i) σ ( i ) W ~ ( j + 1 ) \widetilde W^{(j+1)} W ( j + 1 ) i i i W ( j + 1 ) W^{(j+1)} W ( j + 1 ) σ ( i ) \sigma(i) σ ( i ) 1 1 1 j j j W ~ ( j + 1 ) = Q j + 1 W ( j + 1 ) \widetilde W^{(j+1)}=Q_{j+1}W^{(j+1)} W ( j + 1 ) = Q j + 1 W ( j + 1 ) j j j 1 ≤ j ≤ k 1\le j\le k 1 ≤ j ≤ k W ~ ( j ) = Q j W ( j ) \widetilde W^{(j)}=Q_jW^{(j)} W ( j ) = Q j W ( j ) j = k j=k j = k W ~ ( k ) = W ( k ) \widetilde W^{(k)}=W^{(k)} W ( k ) = W ( k ) (1) は示された。
(2) を示す。(1) をk = n k=n k = n n n n r n = n r_n=n r n = n P = Π n P=\Pi_n P = Π n n n n w n n ( n ) ≠ 0 w^{(n)}_{nn}\ne0 w nn ( n ) = 0 W ( n ) W^{(n)} W ( n ) ▨
定理 2.5. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 A ∈ M n ( R ) A\in M_n(\R) A ∈ M n ( R )
A A A ( P , L , U ) (P,L,U) ( P , L , U ) A A A L L L 1 1 1 U U U 0 0 0 任意のb ∈ R n b\in\R^n b ∈ R n L y = P b Ly=Pb L y = P b U x = y Ux=y U x = y x x x A x = b Ax=b A x = b
(1) の消去は、n ( n − 1 ) / 2 n(n-1)/2 n ( n − 1 ) /2 ( n − 1 ) n ( 2 n − 1 ) / 6 (n-1)n(2n-1)/6 ( n − 1 ) n ( 2 n − 1 ) /6 2 n 3 / 3 − n 2 / 2 − n / 6 2n^3/3-n^2/2-n/6 2 n 3 /3 − n 2 /2 − n /6 (2) の二つの代入は、合計2 n 2 − n 2n^2-n 2 n 2 − n 証明. (1) を示す。1 ≤ k ≤ n 1\le k\le n 1 ≤ k ≤ n 1 , … , k − 1 1,\dots,k-1 1 , … , k − 1 補題 2.4 (1) により、Π k A \Pi_kA Π k A 1 , … , k − 1 1,\dots,k-1 1 , … , k − 1 k k k W ( k ) W^{(k)} W ( k ) 補題 2.3 によりΠ k A = L ( k ) R ( k ) \Pi_kA=L^{(k)}R^{(k)} Π k A = L ( k ) R ( k ) i < k i<k i < k i i i i i i R ( k ) R^{(k)} R ( k ) ( i , i ) (i,i) ( i , i ) i i i 0 0 0 R ( k ) R^{(k)} R ( k ) i ≥ k > j i\ge k>j i ≥ k > j 0 0 0 S : = ( w i j ( k ) ) k ≤ i , j ≤ n S:=(w^{(k)}_{ij})_{k\le i,j\le n} S := ( w ij ( k ) ) k ≤ i , j ≤ n det R ( k ) \det R^{(k)} det R ( k ) 1 , … , k − 1 1,\dots,k-1 1 , … , k − 1 det S \det S det S det ( Π k A ) = ± det A ≠ 0 \det(\Pi_kA)=\pm\det A\ne0 det ( Π k A ) = ± det A = 0 det L ( k ) = 1 \det L^{(k)}=1 det L ( k ) = 1 det S ≠ 0 \det S\ne0 det S = 0 S S S 1 1 1 max k ≤ i ≤ n ∣ w i k ( k ) ∣ > 0 \max_{k\le i\le n}\lvert w^{(k)}_{ik}\rvert>0 max k ≤ i ≤ n ∣ w ik ( k ) ∣ > 0 k k k v k k ( k ) v^{(k)}_{kk} v k k ( k ) 0 0 0 k k k 補題 2.4 (2) によりP A PA P A ( L , U ) (L,U) ( L , U ) 補題 2.3 により( L , U ) (L,U) ( L , U ) P A PA P A L L L i > j i>j i > j j j j v i ′ j ( j ) / v j j ( j ) v^{(j)}_{i'j}/v^{(j)}_{jj} v i ′ j ( j ) / v j j ( j ) i ′ > j i'>j i ′ > j 定義 2.2 (1) により∣ v i ′ j ( j ) ∣ ≤ ∣ v j j ( j ) ∣ \lvert v^{(j)}_{i'j}\rvert\le\lvert v^{(j)}_{jj}\rvert ∣ v i ′ j ( j ) ∣ ≤ ∣ v j j ( j ) ∣ 1 1 1 U U U ( k , k ) (k,k) ( k , k ) k k k
(2) を示す。前進代入は各i i i y i = ( P b ) i − ∑ m < i l i m y m y_i=(Pb)_i-\sum_{m<i}l_{im}y_m y i = ( P b ) i − ∑ m < i l im y m L y = P b Ly=Pb L y = P b i i i x i = ( y i − ∑ m > i u i m x m ) / u i i x_i=(y_i-\sum_{m>i}u_{im}x_m)/u_{ii} x i = ( y i − ∑ m > i u im x m ) / u ii U x = y Ux=y U x = y P A x = L U x = P b PAx=LUx=Pb P A x = LU x = P b P P P A x = b Ax=b A x = b A A A
(3) の証明は演習とする（問題 8.1 ）。▨
3 浮動小数点算術での LU 分解 補題 3.2. F F F u u u fl \operatorname{fl} fl F F F k ≥ 0 k\ge0 k ≥ 0 c , x 1 , … , x k , y 1 , … , y k ∈ F c,x_1,\dots,x_k,y_1,\dots,y_k\in F c , x 1 , … , x k , y 1 , … , y k ∈ F s 0 : = c s_0:=c s 0 := c s m : = fl ( s m − 1 − fl ( x m y m ) ) s_m:=\operatorname{fl}\bigl(s_{m-1}-\operatorname{fl}(x_my_m)\bigr) s m := fl ( s m − 1 − fl ( x m y m ) ) 1 ≤ m ≤ k 1\le m\le k 1 ≤ m ≤ k m m m x m y m x_my_m x m y m 0 0 0 s m − 1 − fl ( x m y m ) s_{m-1}-\operatorname{fl}(x_my_m) s m − 1 − fl ( x m y m ) N max N_{\max} N m a x j ≥ 0 j\ge0 j ≥ 0 j u < 1 ju<1 j u < 1 γ j : = j u / ( 1 − j u ) \gamma_j:=ju/(1-ju) γ j := j u / ( 1 − j u )
k u < 1 ku<1 k u < 1 ∣ θ m ∣ ≤ γ m \lvert\theta_m\rvert\le\gamma_m ∣ θ m ∣ ≤ γ m 1 ≤ m ≤ k 1\le m\le k 1 ≤ m ≤ k ∣ θ ′ ∣ ≤ γ k \lvert\theta'\rvert\le\gamma_k ∣ θ ′ ∣ ≤ γ k θ 1 , … , θ k , θ ′ \theta_1,\dots,\theta_k,\theta' θ 1 , … , θ k , θ ′ c = ∑ m = 1 k x m y m ( 1 + θ m ) + s k ( 1 + θ ′ ) c=\sum_{m=1}^kx_my_m(1+\theta_m)+s_k(1+\theta') c = m = 1 ∑ k x m y m ( 1 + θ m ) + s k ( 1 + θ ′ ) ( k + 1 ) u < 1 (k+1)u<1 ( k + 1 ) u < 1 d ∈ F d\in F d ∈ F d ≠ 0 d\ne0 d = 0 s k / d s_k/d s k / d 0 0 0 z : = fl ( s k / d ) z:=\operatorname{fl}(s_k/d) z := fl ( s k / d ) ∣ θ m ∣ ≤ γ m \lvert\theta_m\rvert\le\gamma_m ∣ θ m ∣ ≤ γ m 1 ≤ m ≤ k 1\le m\le k 1 ≤ m ≤ k ∣ θ ′ ′ ∣ ≤ γ k + 1 \lvert\theta''\rvert\le\gamma_{k+1} ∣ θ ′′ ∣ ≤ γ k + 1 θ 1 , … , θ k , θ ′ ′ \theta_1,\dots,\theta_k,\theta'' θ 1 , … , θ k , θ ′′ c = ∑ m = 1 k x m y m ( 1 + θ m ) + z d ( 1 + θ ′ ′ ) c=\sum_{m=1}^kx_my_m(1+\theta_m)+zd(1+\theta'') c = m = 1 ∑ k x m y m ( 1 + θ m ) + z d ( 1 + θ ′′ ) 証明. (1) を示す。k = 0 k=0 k = 0 c = s 0 c=s_0 c = s 0 θ ′ : = 0 \theta':=0 θ ′ := 0 k ≥ 1 k\ge1 k ≥ 1 k u < 1 ku<1 k u < 1 u < 1 u<1 u < 1 m m m §E20.1 系 3.2 (1) または§E20.1 系 3.2 (2) により∣ μ m ∣ ≤ u \lvert\mu_m\rvert\le u ∣ μ m ∣ ≤ u μ m \mu_m μ m fl ( x m y m ) = x m y m ( 1 + μ m ) \operatorname{fl}(x_my_m)=x_my_m(1+\mu_m) fl ( x m y m ) = x m y m ( 1 + μ m ) − fl ( x m y m ) ∈ F -\operatorname{fl}(x_my_m)\in F − fl ( x m y m ) ∈ F s m − 1 s_{m-1} s m − 1 §E20.1 系 3.3 を適用すると、∣ α m ∣ ≤ u \lvert\alpha_m\rvert\le u ∣ α m ∣ ≤ u α m \alpha_m α m s m = ( s m − 1 − x m y m ( 1 + μ m ) ) ( 1 + α m ) s_m=\bigl(s_{m-1}-x_my_m(1+\mu_m)\bigr)(1+\alpha_m) s m = ( s m − 1 − x m y m ( 1 + μ m ) ) ( 1 + α m ) 1 + α m ≥ 1 − u > 0 1+\alpha_m\ge1-u>0 1 + α m ≥ 1 − u > 0
s m − 1 = s m ( 1 + α m ) − 1 + x m y m ( 1 + μ m ) s_{m-1}=s_m(1+\alpha_m)^{-1}+x_my_m(1+\mu_m) s m − 1 = s m ( 1 + α m ) − 1 + x m y m ( 1 + μ m ) が成り立つ。m = 1 m=1 m = 1 c = s 1 ( 1 + α 1 ) − 1 + x 1 y 1 ( 1 + μ 1 ) c=s_1(1+\alpha_1)^{-1}+x_1y_1(1+\mu_1) c = s 1 ( 1 + α 1 ) − 1 + x 1 y 1 ( 1 + μ 1 ) 2 ≤ j ≤ k 2\le j\le k 2 ≤ j ≤ k c = s j − 1 ∏ q = 1 j − 1 ( 1 + α q ) − 1 + ∑ m = 1 j − 1 x m y m ( 1 + μ m ) ∏ q = 1 m − 1 ( 1 + α q ) − 1 c=s_{j-1}\prod_{q=1}^{j-1}(1+\alpha_q)^{-1}+\sum_{m=1}^{j-1}x_my_m(1+\mu_m)\prod_{q=1}^{m-1}(1+\alpha_q)^{-1} c = s j − 1 ∏ q = 1 j − 1 ( 1 + α q ) − 1 + ∑ m = 1 j − 1 x m y m ( 1 + μ m ) ∏ q = 1 m − 1 ( 1 + α q ) − 1 s j − 1 = s j ( 1 + α j ) − 1 + x j y j ( 1 + μ j ) s_{j-1}=s_j(1+\alpha_j)^{-1}+x_jy_j(1+\mu_j) s j − 1 = s j ( 1 + α j ) − 1 + x j y j ( 1 + μ j ) j j j j j j
c = s k ∏ q = 1 k ( 1 + α q ) − 1 + ∑ m = 1 k x m y m ( 1 + μ m ) ∏ q = 1 m − 1 ( 1 + α q ) − 1 c=s_k\prod_{q=1}^k(1+\alpha_q)^{-1}+\sum_{m=1}^kx_my_m(1+\mu_m)\prod_{q=1}^{m-1}(1+\alpha_q)^{-1} c = s k q = 1 ∏ k ( 1 + α q ) − 1 + m = 1 ∑ k x m y m ( 1 + μ m ) q = 1 ∏ m − 1 ( 1 + α q ) − 1 が成り立つ。第m m m m m m s k s_k s k k k k m u ≤ k u < 1 mu\le ku<1 m u ≤ k u < 1 §E20.1 補題 4.1 をそれぞれの積に適用して、∣ θ m ∣ ≤ γ m \lvert\theta_m\rvert\le\gamma_m ∣ θ m ∣ ≤ γ m θ m \theta_m θ m ∣ θ ′ ∣ ≤ γ k \lvert\theta'\rvert\le\gamma_k ∣ θ ′ ∣ ≤ γ k θ ′ \theta' θ ′
(2) を示す。( k + 1 ) u < 1 (k+1)u<1 ( k + 1 ) u < 1 k u < 1 ku<1 k u < 1 u < 1 u<1 u < 1 §E20.1 系 3.2 (1) または§E20.1 系 3.2 (2) により∣ φ ∣ ≤ u \lvert\varphi\rvert\le u ∣ φ ∣ ≤ u φ \varphi φ z = ( s k / d ) ( 1 + φ ) z=(s_k/d)(1+\varphi) z = ( s k / d ) ( 1 + φ ) s k = z d ( 1 + φ ) − 1 s_k=zd(1+\varphi)^{-1} s k = z d ( 1 + φ ) − 1 s k s_k s k z d zd z d k + 1 k+1 k + 1 §E20.1 補題 4.1 を適用して∣ θ ′ ′ ∣ ≤ γ k + 1 \lvert\theta''\rvert\le\gamma_{k+1} ∣ θ ′′ ∣ ≤ γ k + 1 θ ′ ′ \theta'' θ ′′ θ m \theta_m θ m (1) と同じにとる。▨
定理 3.3. F F F u u u fl \operatorname{fl} fl F F F n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 ( n − 1 ) u < 1 (n-1)u<1 ( n − 1 ) u < 1 0 ≤ j ≤ n − 1 0\le j\le n-1 0 ≤ j ≤ n − 1 γ j : = j u / ( 1 − j u ) \gamma_j:=ju/(1-ju) γ j := j u / ( 1 − j u ) X X X ∣ X ∣ \lvert X\rvert ∣ X ∣ A ∈ M n ( F ) A\in M_n(F) A ∈ M n ( F ) F F F fl \operatorname{fl} fl ( P , L ^ , U ^ ) (P,\widehat L,\widehat U) ( P , L , U ) Δ A : = L ^ U ^ − P A \Delta A:=\widehat L\widehat U-PA Δ A := L U − P A P A + Δ A = L ^ U ^ PA+\Delta A=\widehat L\widehat U P A + Δ A = L U 1 ≤ i , j ≤ n 1\le i,j\le n 1 ≤ i , j ≤ n
∣ Δ a i j ∣ ≤ γ min { i − 1 , j } ∑ m = 1 min { i , j } ∣ l ^ i m ∣ ∣ u ^ m j ∣ \lvert\Delta a_{ij}\rvert\le\gamma_{\min\{i-1,j\}}\sum_{m=1}^{\min\{i,j\}}\lvert\widehat l_{im}\rvert\lvert\widehat u_{mj}\rvert ∣ Δ a ij ∣ ≤ γ m i n { i − 1 , j } m = 1 ∑ m i n { i , j } ∣ l im ∣ ∣ u mj ∣ が成り立つ。特に∣ Δ A ∣ ≤ γ n − 1 ∣ L ^ ∣ ∣ U ^ ∣ \lvert\Delta A\rvert\le\gamma_{n-1}\lvert\widehat L\rvert\lvert\widehat U\rvert ∣ Δ A ∣ ≤ γ n − 1 ∣ L ∣ ∣ U ∣ A A A ( L ^ , U ^ ) (\widehat L,\widehat U) ( L , U ) P = I P=I P = I
証明. B : = P A B:=PA B := P A 補題 2.4 (2) により、B B B ( L ^ , U ^ ) (\widehat L,\widehat U) ( L , U ) 補題 2.4 (1) によりその演算は部分ピボット付き消去の演算と被演算数ごとに一致するので、この実行も範囲条件を満たす。ピボット選択なしの消去の場合はB : = A B:=A B := A W ( m ) W^{(m)} W ( m ) B B B 1 ≤ i , j ≤ n 1\le i,j\le n 1 ≤ i , j ≤ n 定義 2.2 (3) により、作業行列の第1 1 1 m m m m m m i > m i>m i > m m m m m m m u ^ m j = w m j ( m ) \widehat u_{mj}=w^{(m)}_{mj} u mj = w mj ( m ) m ≤ j m\le j m ≤ j l ^ i m = w i m ( m + 1 ) \widehat l_{im}=w^{(m+1)}_{im} l im = w im ( m + 1 ) m < i m<i m < i ( i , j ) (i,j) ( i , j )
w i j ( 1 ) = b i j , w i j ( m + 1 ) = fl ( w i j ( m ) − fl ( l ^ i m u ^ m j ) ) ( 1 ≤ m < min { i , j } ) w^{(1)}_{ij}=b_{ij},\qquad w^{(m+1)}_{ij}=\operatorname{fl}\bigl(w^{(m)}_{ij}-\operatorname{fl}(\widehat l_{im}\widehat u_{mj})\bigr)\quad(1\le m<\min\{i,j\}) w ij ( 1 ) = b ij , w ij ( m + 1 ) = fl ( w ij ( m ) − fl ( l im u mj ) ) ( 1 ≤ m < min { i , j }) を満たす。さらにi ≤ j i\le j i ≤ j u ^ i j = w i j ( i ) \widehat u_{ij}=w^{(i)}_{ij} u ij = w ij ( i ) i > j i>j i > j l ^ i j = fl ( w i j ( j ) / u ^ j j ) \widehat l_{ij}=\operatorname{fl}(w^{(j)}_{ij}/\widehat u_{jj}) l ij = fl ( w ij ( j ) / u j j ) L ^ \widehat L L U ^ \widehat U U Δ A \Delta A Δ A ( i , j ) (i,j) ( i , j ) Δ b i j : = ∑ m = 1 min { i , j } l ^ i m u ^ m j − b i j \Delta b_{ij}:=\sum_{m=1}^{\min\{i,j\}}\widehat l_{im}\widehat u_{mj}-b_{ij} Δ b ij := ∑ m = 1 m i n { i , j } l im u mj − b ij
i ≤ j i\le j i ≤ j 補題 3.2 (1) をk = i − 1 k=i-1 k = i − 1 c = b i j c=b_{ij} c = b ij ( x m , y m ) = ( l ^ i m , u ^ m j ) (x_m,y_m)=(\widehat l_{im},\widehat u_{mj}) ( x m , y m ) = ( l im , u mj ) ( i − 1 ) u ≤ ( n − 1 ) u < 1 (i-1)u\le(n-1)u<1 ( i − 1 ) u ≤ ( n − 1 ) u < 1 s i − 1 = u ^ i j s_{i-1}=\widehat u_{ij} s i − 1 = u ij l ^ i i = 1 \widehat l_{ii}=1 l ii = 1
Δ b i j = − ∑ m = 1 i − 1 l ^ i m u ^ m j θ m − l ^ i i u ^ i j θ ′ \Delta b_{ij}=-\sum_{m=1}^{i-1}\widehat l_{im}\widehat u_{mj}\theta_m-\widehat l_{ii}\widehat u_{ij}\theta' Δ b ij = − m = 1 ∑ i − 1 l im u mj θ m − l ii u ij θ ′ である。m ≤ i − 1 m\le i-1 m ≤ i − 1 γ m ≤ γ i − 1 \gamma_m\le\gamma_{i-1} γ m ≤ γ i − 1 ∣ Δ b i j ∣ ≤ γ i − 1 ∑ m = 1 i ∣ l ^ i m ∣ ∣ u ^ m j ∣ \lvert\Delta b_{ij}\rvert\le\gamma_{i-1}\sum_{m=1}^{i}\lvert\widehat l_{im}\rvert\lvert\widehat u_{mj}\rvert ∣ Δ b ij ∣ ≤ γ i − 1 ∑ m = 1 i ∣ l im ∣ ∣ u mj ∣
i > j i>j i > j 補題 3.2 (2) をk = j − 1 k=j-1 k = j − 1 c = b i j c=b_{ij} c = b ij ( x m , y m ) = ( l ^ i m , u ^ m j ) (x_m,y_m)=(\widehat l_{im},\widehat u_{mj}) ( x m , y m ) = ( l im , u mj ) d = u ^ j j d=\widehat u_{jj} d = u j j j u ≤ ( n − 1 ) u < 1 ju\le(n-1)u<1 j u ≤ ( n − 1 ) u < 1 z = l ^ i j z=\widehat l_{ij} z = l ij
Δ b i j = − ∑ m = 1 j − 1 l ^ i m u ^ m j θ m − l ^ i j u ^ j j θ ′ ′ \Delta b_{ij}=-\sum_{m=1}^{j-1}\widehat l_{im}\widehat u_{mj}\theta_m-\widehat l_{ij}\widehat u_{jj}\theta'' Δ b ij = − m = 1 ∑ j − 1 l im u mj θ m − l ij u j j θ ′′ であり、∣ Δ b i j ∣ ≤ γ j ∑ m = 1 j ∣ l ^ i m ∣ ∣ u ^ m j ∣ \lvert\Delta b_{ij}\rvert\le\gamma_j\sum_{m=1}^{j}\lvert\widehat l_{im}\rvert\lvert\widehat u_{mj}\rvert ∣ Δ b ij ∣ ≤ γ j ∑ m = 1 j ∣ l im ∣ ∣ u mj ∣
i ≤ j i\le j i ≤ j min { i − 1 , j } = i − 1 \min\{i-1,j\}=i-1 min { i − 1 , j } = i − 1 i > j i>j i > j min { i − 1 , j } = j \min\{i-1,j\}=j min { i − 1 , j } = j γ j \gamma_j γ j j j j min { i − 1 , j } ≤ n − 1 \min\{i-1,j\}\le n-1 min { i − 1 , j } ≤ n − 1 ∣ Δ A ∣ ≤ γ n − 1 ∣ L ^ ∣ ∣ U ^ ∣ \lvert\Delta A\rvert\le\gamma_{n-1}\lvert\widehat L\rvert\lvert\widehat U\rvert ∣ Δ A ∣ ≤ γ n − 1 ∣ L ∣ ∣ U ∣ ▨
定義 3.4. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 A ∈ M n ( R ) A\in M_n(\R) A ∈ M n ( R ) A ≠ 0 A\ne0 A = 0 A A A W ( 1 ) , … , W ( n ) W^{(1)},\dots,W^{(n)} W ( 1 ) , … , W ( n )
g : = max 1 ≤ k ≤ n max k ≤ i , j ≤ n ∣ w i j ( k ) ∣ max 1 ≤ i , j ≤ n ∣ a i j ∣ g:=\frac{\max_{1\le k\le n}\max_{k\le i,j\le n}\lvert w^{(k)}_{ij}\rvert}{\max_{1\le i,j\le n}\lvert a_{ij}\rvert} g := max 1 ≤ i , j ≤ n ∣ a ij ∣ max 1 ≤ k ≤ n max k ≤ i , j ≤ n ∣ w ij ( k ) ∣ をその実行の 成長因子 (growth factor )k k k k k k n n n k k k n n n
補題 3.5. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 R n \R^n R n ∥ h ∥ ∞ : = max 1 ≤ i ≤ n ∣ h i ∣ \lVert h\rVert_\infty:=\max_{1\le i\le n}\lvert h_i\rvert ∥ h ∥ ∞ := max 1 ≤ i ≤ n ∣ h i ∣ X ∈ M n ( R ) X\in M_n(\R) X ∈ M n ( R ) §E20.2 定義 1.1 ）を∥ X ∥ ∞ \lVert X\rVert_\infty ∥ X ∥ ∞
∥ X ∥ ∞ = max 1 ≤ i ≤ n ∑ j = 1 n ∣ x i j ∣ \lVert X\rVert_\infty=\max_{1\le i\le n}\sum_{j=1}^n\lvert x_{ij}\rvert ∥ X ∥ ∞ = max 1 ≤ i ≤ n ∑ j = 1 n ∣ x ij ∣ X , Y ∈ M n ( R ) X,Y\in M_n(\R) X , Y ∈ M n ( R ) i , j i,j i , j ∣ x i j ∣ ≤ y i j \lvert x_{ij}\rvert\le y_{ij} ∣ x ij ∣ ≤ y ij ∥ X ∥ ∞ ≤ ∥ Y ∥ ∞ \lVert X\rVert_\infty\le\lVert Y\rVert_\infty ∥ X ∥ ∞ ≤ ∥ Y ∥ ∞ 任意の置換行列Q Q Q ∥ Q X ∥ ∞ = ∥ X ∥ ∞ \lVert QX\rVert_\infty=\lVert X\rVert_\infty ∥ QX ∥ ∞ = ∥ X ∥ ∞
証明. (1) を示す。∥ h ∥ ∞ = 1 \lVert h\rVert_\infty=1 ∥ h ∥ ∞ = 1 i i i ∣ ( X h ) i ∣ ≤ ∑ j ∣ x i j ∣ \lvert(Xh)_i\rvert\le\sum_j\lvert x_{ij}\rvert ∣( X h ) i ∣ ≤ ∑ j ∣ x ij ∣ ∥ X ∥ ∞ \lVert X\rVert_\infty ∥ X ∥ ∞ i i i x i j ≥ 0 x_{ij}\ge0 x ij ≥ 0 h j : = 1 h_j:=1 h j := 1 x i j < 0 x_{ij}<0 x ij < 0 h j : = − 1 h_j:=-1 h j := − 1 ∥ h ∥ ∞ = 1 \lVert h\rVert_\infty=1 ∥ h ∥ ∞ = 1 ( X h ) i = ∑ j ∣ x i j ∣ (Xh)_i=\sum_j\lvert x_{ij}\rvert ( X h ) i = ∑ j ∣ x ij ∣ X X X Y Y Y Q X QX QX X X X (1) により(2) と(3) が成り立つ。▨
命題 3.6. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 A ∈ M n ( R ) A\in M_n(\R) A ∈ M n ( R ) A ≠ 0 A\ne0 A = 0 a max : = max 1 ≤ i , j ≤ n ∣ a i j ∣ a_{\max}:=\max_{1\le i,j\le n}\lvert a_{ij}\rvert a m a x := max 1 ≤ i , j ≤ n ∣ a ij ∣
A A A U U U g g g i , j i,j i , j ∣ u i j ∣ ≤ g a max \lvert u_{ij}\rvert\le ga_{\max} ∣ u ij ∣ ≤ g a m a x A A A A A A 2 n − 1 2^{n-1} 2 n − 1 F = F ( β , p , e min , e max ) F=F(\beta,p,e_{\min},e_{\max}) F = F ( β , p , e m i n , e m a x ) e min ≤ 0 ≤ e max e_{\min}\le0\le e_{\max} e m i n ≤ 0 ≤ e m a x u u u fl \operatorname{fl} fl F F F A ∈ M n ( F ) A\in M_n(F) A ∈ M n ( F ) A A A F F F fl \operatorname{fl} fl 1 1 1 [ ( 1 + u ) ( 2 + u ) ] n − 1 [(1+u)(2+u)]^{n-1} [( 1 + u ) ( 2 + u ) ] n − 1 (3) の仮定に加えて( n − 1 ) u < 1 (n-1)u<1 ( n − 1 ) u < 1 γ n − 1 : = ( n − 1 ) u / ( 1 − ( n − 1 ) u ) \gamma_{n-1}:=(n-1)u/(1-(n-1)u) γ n − 1 := ( n − 1 ) u / ( 1 − ( n − 1 ) u ) ( P , L ^ , U ^ ) (P,\widehat L,\widehat U) ( P , L , U ) g g g Δ A : = L ^ U ^ − P A \Delta A:=\widehat L\widehat U-PA Δ A := L U − P A ∥ Δ A ∥ ∞ ≤ n 2 γ n − 1 g ∥ A ∥ ∞ \lVert\Delta A\rVert_\infty\le n^2\gamma_{n-1}g\lVert A\rVert_\infty ∥ Δ A ∥ ∞ ≤ n 2 γ n − 1 g ∥ A ∥ ∞ 証明. 各実行についてg k : = max k ≤ i , j ≤ n ∣ w i j ( k ) ∣ g_k:=\max_{k\le i,j\le n}\lvert w^{(k)}_{ij}\rvert g k := max k ≤ i , j ≤ n ∣ w ij ( k ) ∣ g 1 = a max g_1=a_{\max} g 1 = a m a x max k g k / a max \max_kg_k/a_{\max} max k g k / a m a x V ( k ) V^{(k)} V ( k ) W ( k ) W^{(k)} W ( k ) k k k max k ≤ i , j ≤ n ∣ v i j ( k ) ∣ = g k \max_{k\le i,j\le n}\lvert v^{(k)}_{ij}\rvert=g_k max k ≤ i , j ≤ n ∣ v ij ( k ) ∣ = g k
(1) を示す。第k k k k k k j ≥ k j\ge k j ≥ k u k j = v k j ( k ) u_{kj}=v^{(k)}_{kj} u k j = v k j ( k ) ∣ u k j ∣ ≤ g k ≤ g a max \lvert u_{kj}\rvert\le g_k\le ga_{\max} ∣ u k j ∣ ≤ g k ≤ g a m a x
(2) を示す。定理 2.5 (1) により消去は完了する。定義 2.2 (1) によりi > k i>k i > k ∣ v i k ( k ) ∣ ≤ ∣ v k k ( k ) ∣ \lvert v^{(k)}_{ik}\rvert\le\lvert v^{(k)}_{kk}\rvert ∣ v ik ( k ) ∣ ≤ ∣ v k k ( k ) ∣ k k k 1 1 1 i , j > k i,j>k i , j > k ∣ w i j ( k + 1 ) ∣ ≤ ∣ v i j ( k ) ∣ + ∣ v k j ( k ) ∣ ≤ 2 g k \lvert w^{(k+1)}_{ij}\rvert\le\lvert v^{(k)}_{ij}\rvert+\lvert v^{(k)}_{kj}\rvert\le2g_k ∣ w ij ( k + 1 ) ∣ ≤ ∣ v ij ( k ) ∣ + ∣ v k j ( k ) ∣ ≤ 2 g k g k + 1 ≤ 2 g k g_{k+1}\le2g_k g k + 1 ≤ 2 g k g k ≤ 2 k − 1 g 1 g_k\le2^{k-1}g_1 g k ≤ 2 k − 1 g 1 2 n − 1 2^{n-1} 2 n − 1
(3) を示す。e min ≤ 0 ≤ e max e_{\min}\le0\le e_{\max} e m i n ≤ 0 ≤ e m a x 1 = β p − 1 s 0 1=\beta^{p-1}s_0 1 = β p − 1 s 0 F F F F = − F F=-F F = − F − 1 ∈ F -1\in F − 1 ∈ F z z z ∣ z ∣ ≤ 1 \lvert z\rvert\le1 ∣ z ∣ ≤ 1 fl ( z ) > 1 \operatorname{fl}(z)>1 fl ( z ) > 1 z ≤ 1 < fl ( z ) z\le1<\operatorname{fl}(z) z ≤ 1 < fl ( z ) ∣ 1 − z ∣ < ∣ fl ( z ) − z ∣ \lvert1-z\rvert<\lvert\operatorname{fl}(z)-z\rvert ∣ 1 − z ∣ < ∣ fl ( z ) − z ∣ fl ( z ) \operatorname{fl}(z) fl ( z ) z z z fl ( z ) ≥ − 1 \operatorname{fl}(z)\ge-1 fl ( z ) ≥ − 1 k k k z = v i k ( k ) / v k k ( k ) z=v^{(k)}_{ik}/v^{(k)}_{kk} z = v ik ( k ) / v k k ( k ) ∣ z ∣ ≤ 1 \lvert z\rvert\le1 ∣ z ∣ ≤ 1 fl ( z ) \operatorname{fl}(z) fl ( z ) 1 1 1 1 1 1 i , j > k i,j>k i , j > k l ^ \widehat l l §E20.1 系 3.2 (1) または§E20.1 系 3.2 (2) により∣ fl ( l ^ v k j ( k ) ) ∣ ≤ ( 1 + u ) ∣ l ^ ∣ ∣ v k j ( k ) ∣ ≤ ( 1 + u ) g k \lvert\operatorname{fl}(\widehat lv^{(k)}_{kj})\rvert\le(1+u)\lvert\widehat l\rvert\lvert v^{(k)}_{kj}\rvert\le(1+u)g_k ∣ fl ( l v k j ( k ) )∣ ≤ ( 1 + u ) ∣ l ∣ ∣ v k j ( k ) ∣ ≤ ( 1 + u ) g k §E20.1 系 3.3 により
∣ w i j ( k + 1 ) ∣ ≤ ( 1 + u ) ( ∣ v i j ( k ) ∣ + ∣ fl ( l ^ v k j ( k ) ) ∣ ) ≤ ( 1 + u ) ( 2 + u ) g k \lvert w^{(k+1)}_{ij}\rvert\le(1+u)\bigl(\lvert v^{(k)}_{ij}\rvert+\lvert\operatorname{fl}(\widehat lv^{(k)}_{kj})\rvert\bigr)\le(1+u)(2+u)g_k ∣ w ij ( k + 1 ) ∣ ≤ ( 1 + u ) ( ∣ v ij ( k ) ∣ + ∣ fl ( l v k j ( k ) )∣ ) ≤ ( 1 + u ) ( 2 + u ) g k である。k k k g k ≤ [ ( 1 + u ) ( 2 + u ) ] k − 1 g 1 g_k\le[(1+u)(2+u)]^{k-1}g_1 g k ≤ [( 1 + u ) ( 2 + u ) ] k − 1 g 1 [ ( 1 + u ) ( 2 + u ) ] n − 1 [(1+u)(2+u)]^{n-1} [( 1 + u ) ( 2 + u ) ] n − 1
(4) を示す。定理 3.3 により∣ Δ A ∣ ≤ γ n − 1 ∣ L ^ ∣ ∣ U ^ ∣ \lvert\Delta A\rvert\le\gamma_{n-1}\lvert\widehat L\rvert\lvert\widehat U\rvert ∣ Δ A ∣ ≤ γ n − 1 ∣ L ∣ ∣ U ∣ (3) と(1) により、( ∣ L ^ ∣ ∣ U ^ ∣ ) i j = ∑ m ≤ min { i , j } ∣ l ^ i m ∣ ∣ u ^ m j ∣ ≤ n g a max (\lvert\widehat L\rvert\lvert\widehat U\rvert)_{ij}=\sum_{m\le\min\{i,j\}}\lvert\widehat l_{im}\rvert\lvert\widehat u_{mj}\rvert\le nga_{\max} (∣ L ∣ ∣ U ∣ ) ij = ∑ m ≤ m i n { i , j } ∣ l im ∣ ∣ u mj ∣ ≤ n g a m a x γ n − 1 ∣ L ^ ∣ ∣ U ^ ∣ \gamma_{n-1}\lvert\widehat L\rvert\lvert\widehat U\rvert γ n − 1 ∣ L ∣ ∣ U ∣ n 2 γ n − 1 g a max n^2\gamma_{n-1}ga_{\max} n 2 γ n − 1 g a m a x a max a_{\max} a m a x A A A 補題 3.5 (1) と補題 3.5 (2) により∥ Δ A ∥ ∞ ≤ n 2 γ n − 1 g a max ≤ n 2 γ n − 1 g ∥ A ∥ ∞ \lVert\Delta A\rVert_\infty\le n^2\gamma_{n-1}ga_{\max}\le n^2\gamma_{n-1}g\lVert A\rVert_\infty ∥ Δ A ∥ ∞ ≤ n 2 γ n − 1 g a m a x ≤ n 2 γ n − 1 g ∥ A ∥ ∞ ▨
例 3.7. n ≥ 2 n\ge2 n ≥ 2 W n ∈ M n ( R ) W_n\in M_n(\R) W n ∈ M n ( R ) n n n 1 1 1 − 1 -1 − 1 0 0 0
W n W_n W n 1 ≤ k < n 1\le k<n 1 ≤ k < n k k k i , j ≥ k i,j\ge k i , j ≥ k
w i j ( k ) = { 2 k − 1 ( j = n ) , 1 ( i = j < n ) , − 1 ( j < i , j < n ) , 0 ( i < j < n ) w^{(k)}_{ij}=\begin{cases}2^{k-1}&(j=n),\\1&(i=j<n),\\-1&(j<i,\ j<n),\\0&(i<j<n)\end{cases} w ij ( k ) = ⎩ ⎨ ⎧ 2 k − 1 1 − 1 0 ( j = n ) , ( i = j < n ) , ( j < i , j < n ) , ( i < j < n ) で与えられるとする。第k k k i ≥ k i\ge k i ≥ k 1 1 1 r k = k r_k=k r k = k 1 1 1 − 1 -1 − 1 i , j > k i,j>k i , j > k w i j ( k + 1 ) = w i j ( k ) + w k j ( k ) w^{(k+1)}_{ij}=w^{(k)}_{ij}+w^{(k)}_{kj} w ij ( k + 1 ) = w ij ( k ) + w k j ( k ) w k j ( k ) w^{(k)}_{kj} w k j ( k ) k < j < n k<j<n k < j < n 0 0 0 j = n j=n j = n 2 k − 1 2^{k-1} 2 k − 1 n n n 2 k − 1 + 2 k − 1 = 2 k 2^{k-1}+2^{k-1}=2^k 2 k − 1 + 2 k − 1 = 2 k k + 1 k+1 k + 1 i , j ≥ k + 1 i,j\ge k+1 i , j ≥ k + 1 k k k k + 1 k+1 k + 1 W ( 1 ) = W n W^{(1)}=W_n W ( 1 ) = W n k = 1 k=1 k = 1 k k k k k k k k k 2 k − 1 2^{k-1} 2 k − 1 u n n = 2 n − 1 u_{nn}=2^{n-1} u nn = 2 n − 1 2 n − 1 2^{n-1} 2 n − 1 補題 2.3 によりW n = L U W_n=LU W n = LU det W n = 2 n − 1 ≠ 0 \det W_n=2^{n-1}\ne0 det W n = 2 n − 1 = 0 W n W_n W n 命題 3.6 (2) の上界は等号で成り立つ。
F = F ( 2 , p , e min , e max ) F=F(2,p,e_{\min},e_{\max}) F = F ( 2 , p , e m i n , e m a x ) e min ≤ 0 e_{\min}\le0 e m i n ≤ 0 n − 1 ≤ e max n-1\le e_{\max} n − 1 ≤ e m a x fl \operatorname{fl} fl F F F − 1 / 1 = − 1 -1/1=-1 − 1/1 = − 1 ( − 1 ) ⋅ 0 = 0 (-1)\cdot0=0 ( − 1 ) ⋅ 0 = 0 ( − 1 ) ⋅ 2 k − 1 (-1)\cdot2^{k-1} ( − 1 ) ⋅ 2 k − 1 w i j ( k ) − 0 ∈ { − 1 , 0 , 1 } w^{(k)}_{ij}-0\in\{-1,0,1\} w ij ( k ) − 0 ∈ { − 1 , 0 , 1 } 2 k − 1 − ( − 2 k − 1 ) = 2 k 2^{k-1}-(-2^{k-1})=2^k 2 k − 1 − ( − 2 k − 1 ) = 2 k 1 ≤ k ≤ n − 1 1\le k\le n-1 1 ≤ k ≤ n − 1 0 ≤ j ≤ n − 1 0\le j\le n-1 0 ≤ j ≤ n − 1 2 j = 2 p − 1 s j 2^j=2^{p-1}s_j 2 j = 2 p − 1 s j F F F F F F §E20.1 系 3.2 (1) により浮動小数点算術の各演算は厳密であり、実行は範囲条件を満たし、ピボットの選択も厳密算術と同じである。したがって浮動小数点算術の出力は厳密算術の出力に等しく、補題 2.3 によりΔ A = L ^ U ^ − W n = 0 \Delta A=\widehat L\widehat U-W_n=0 Δ A = L U − W n = 0 F F F u u u ( n − 1 ) u < 1 (n-1)u<1 ( n − 1 ) u < 1 命題 3.6 (4) の右辺は、g = 2 n − 1 g=2^{n-1} g = 2 n − 1 ∥ W n ∥ ∞ = n \lVert W_n\rVert_\infty=n ∥ W n ∥ ∞ = n n 3 γ n − 1 2 n − 1 n^3\gamma_{n-1}2^{n-1} n 3 γ n − 1 2 n − 1
定理 3.8. F F F u u u fl \operatorname{fl} fl F F F n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 n u < 1 nu<1 n u < 1 0 ≤ j ≤ n 0\le j\le n 0 ≤ j ≤ n γ j : = j u / ( 1 − j u ) \gamma_j:=ju/(1-ju) γ j := j u / ( 1 − j u )
T ∈ M n ( F ) T\in M_n(F) T ∈ M n ( F ) 0 0 0 c ∈ F n c\in F^n c ∈ F n T y = c Ty=c T y = c F F F fl \operatorname{fl} fl y ^ \widehat y y ∣ E ∣ ≤ γ n ∣ T ∣ \lvert E\rvert\le\gamma_n\lvert T\rvert ∣ E ∣ ≤ γ n ∣ T ∣ E ∈ M n ( R ) E\in M_n(\R) E ∈ M n ( R ) ( T + E ) y ^ = c (T+E)\widehat y=c ( T + E ) y = c A ∈ M n ( F ) A\in M_n(F) A ∈ M n ( F ) ( P , L ^ , U ^ ) (P,\widehat L,\widehat U) ( P , L , U ) 定理 3.3 の仮定を満たすとし、b ∈ F n b\in F^n b ∈ F n L ^ y = P b \widehat Ly=Pb L y = P b y ^ \widehat y y U ^ x = y ^ \widehat Ux=\widehat y U x = y x ^ \widehat x x F F F fl \operatorname{fl} fl ∣ E ∣ ≤ ( 3 γ n + γ n 2 ) ∣ L ^ ∣ ∣ U ^ ∣ \lvert E\rvert\le(3\gamma_n+\gamma_n^2)\lvert\widehat L\rvert\lvert\widehat U\rvert ∣ E ∣ ≤ ( 3 γ n + γ n 2 ) ∣ L ∣ ∣ U ∣ E ∈ M n ( R ) E\in M_n(\R) E ∈ M n ( R ) ( P A + E ) x ^ = P b (PA+E)\widehat x=Pb ( P A + E ) x = P b 証明. (1) を示す。T T T 1 ≤ i ≤ n 1\le i\le n 1 ≤ i ≤ n i i i 補題 3.2 の漸化式をk = i − 1 k=i-1 k = i − 1 c = c i c=c_i c = c i ( x m , y m ) = ( t i m , y ^ m ) (x_m,y_m)=(t_{im},\widehat y_m) ( x m , y m ) = ( t im , y m ) y ^ i = fl ( s i − 1 / t i i ) \widehat y_i=\operatorname{fl}(s_{i-1}/t_{ii}) y i = fl ( s i − 1 / t ii ) 1 1 1 y ^ i = s i − 1 \widehat y_i=s_{i-1} y i = s i − 1 補題 3.2 (2) （対角成分がすべて1 1 1 補題 3.2 (1) ）をd = t i i d=t_{ii} d = t ii ∣ θ i m ∣ ≤ γ m \lvert\theta_{im}\rvert\le\gamma_m ∣ θ im ∣ ≤ γ m ∣ θ i i ∣ ≤ γ i \lvert\theta_{ii}\rvert\le\gamma_i ∣ θ ii ∣ ≤ γ i
c i = ∑ m = 1 i − 1 t i m y ^ m ( 1 + θ i m ) + t i i y ^ i ( 1 + θ i i ) c_i=\sum_{m=1}^{i-1}t_{im}\widehat y_m(1+\theta_{im})+t_{ii}\widehat y_i(1+\theta_{ii}) c i = m = 1 ∑ i − 1 t im y m ( 1 + θ im ) + t ii y i ( 1 + θ ii ) が成り立つ。m ≤ i m\le i m ≤ i e i m : = t i m θ i m e_{im}:=t_{im}\theta_{im} e im := t im θ im m > i m>i m > i e i m : = 0 e_{im}:=0 e im := 0 ( T + E ) y ^ = c (T+E)\widehat y=c ( T + E ) y = c γ m ≤ γ i ≤ γ n \gamma_m\le\gamma_i\le\gamma_n γ m ≤ γ i ≤ γ n ∣ E ∣ ≤ γ n ∣ T ∣ \lvert E\rvert\le\gamma_n\lvert T\rvert ∣ E ∣ ≤ γ n ∣ T ∣ T T T i i i k = n − i k=n-i k = n − i ( x 1 , y 1 ) , … , ( x n − i , y n − i ) = ( t i , i + 1 , y ^ i + 1 ) , … , ( t i n , y ^ n ) (x_1,y_1),\dots,(x_{n-i},y_{n-i})=(t_{i,i+1},\widehat y_{i+1}),\dots,(t_{in},\widehat y_n) ( x 1 , y 1 ) , … , ( x n − i , y n − i ) = ( t i , i + 1 , y i + 1 ) , … , ( t in , y n ) n − i + 1 n-i+1 n − i + 1 n − i + 1 ≤ n n-i+1\le n n − i + 1 ≤ n
(2) を示す。P b ∈ F n Pb\in F^n P b ∈ F n y ^ ∈ F n \widehat y\in F^n y ∈ F n (1) を適用すると、∣ E 1 ∣ ≤ γ n ∣ L ^ ∣ \lvert E_1\rvert\le\gamma_n\lvert\widehat L\rvert ∣ E 1 ∣ ≤ γ n ∣ L ∣ ∣ E 2 ∣ ≤ γ n ∣ U ^ ∣ \lvert E_2\rvert\le\gamma_n\lvert\widehat U\rvert ∣ E 2 ∣ ≤ γ n ∣ U ∣ E 1 , E 2 E_1,E_2 E 1 , E 2 ( L ^ + E 1 ) y ^ = P b (\widehat L+E_1)\widehat y=Pb ( L + E 1 ) y = P b ( U ^ + E 2 ) x ^ = y ^ (\widehat U+E_2)\widehat x=\widehat y ( U + E 2 ) x = y 定理 3.3 のΔ A \Delta A Δ A
P b = ( L ^ + E 1 ) ( U ^ + E 2 ) x ^ = ( P A + Δ A + E 1 U ^ + L ^ E 2 + E 1 E 2 ) x ^ Pb=(\widehat L+E_1)(\widehat U+E_2)\widehat x=(PA+\Delta A+E_1\widehat U+\widehat LE_2+E_1E_2)\widehat x P b = ( L + E 1 ) ( U + E 2 ) x = ( P A + Δ A + E 1 U + L E 2 + E 1 E 2 ) x である。E : = Δ A + E 1 U ^ + L ^ E 2 + E 1 E 2 E:=\Delta A+E_1\widehat U+\widehat LE_2+E_1E_2 E := Δ A + E 1 U + L E 2 + E 1 E 2 ∣ X Y ∣ ≤ ∣ X ∣ ∣ Y ∣ \lvert XY\rvert\le\lvert X\rvert\lvert Y\rvert ∣ X Y ∣ ≤ ∣ X ∣ ∣ Y ∣ γ n − 1 ≤ γ n \gamma_{n-1}\le\gamma_n γ n − 1 ≤ γ n ∣ E ∣ ≤ ( γ n − 1 + 2 γ n + γ n 2 ) ∣ L ^ ∣ ∣ U ^ ∣ ≤ ( 3 γ n + γ n 2 ) ∣ L ^ ∣ ∣ U ^ ∣ \lvert E\rvert\le(\gamma_{n-1}+2\gamma_n+\gamma_n^2)\lvert\widehat L\rvert\lvert\widehat U\rvert\le(3\gamma_n+\gamma_n^2)\lvert\widehat L\rvert\lvert\widehat U\rvert ∣ E ∣ ≤ ( γ n − 1 + 2 γ n + γ n 2 ) ∣ L ∣ ∣ U ∣ ≤ ( 3 γ n + γ n 2 ) ∣ L ∣ ∣ U ∣ ▨
4 行列の条件数と残差 定義 4.1. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 T ∈ M n ( C ) T\in M_n(\C) T ∈ M n ( C ) det ( λ I − T ) = 0 \det(\lambda I-T)=0 det ( λ I − T ) = 0 λ \lambda λ ρ ( T ) \rho(T) ρ ( T ) T T T スペクトル半径 (spectral radius )A ∈ M n ( R ) A\in M_n(\R) A ∈ M n ( R ) M n ( C ) M_n(\C) M n ( C ) ρ ( A ) \rho(A) ρ ( A )
定義 4.2. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 T ∈ C n × n T\in\C^{n\times n} T ∈ C n × n C n \C^n C n ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ ∥ T ∥ : = sup { ∥ T h ∥ ∣ h ∈ C n , ∥ h ∥ = 1 } \lVert T\rVert:=\sup\{\lVert Th\rVert\mid h\in\C^n,\ \lVert h\rVert=1\} ∥ T ∥ := sup {∥ T h ∥ ∣ h ∈ C n , ∥ h ∥ = 1 } T T T ∥ T ∥ < ∞ \lVert T\rVert<\infty ∥ T ∥ < ∞ h ∈ C n h\in\C^n h ∈ C n ∥ T h ∥ ≤ ∥ T ∥ ∥ h ∥ \lVert Th\rVert\le\lVert T\rVert\lVert h\rVert ∥ T h ∥ ≤ ∥ T ∥ ∥ h ∥ T ∈ R n × n T\in\R^{n\times n} T ∈ R n × n C n × n \C^{n\times n} C n × n
定義 4.3. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 R n \R^n R n ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ A ∈ M n ( R ) A\in M_n(\R) A ∈ M n ( R ) ∥ A ∥ \lVert A\rVert ∥ A ∥ A A A κ ( A ) : = ∥ A ∥ ∥ A − 1 ∥ \kappa(A):=\lVert A\rVert\lVert A^{-1}\rVert κ ( A ) := ∥ A ∥ ∥ A − 1 ∥ A A A κ ( A ) : = + ∞ \kappa(A):=+\infty κ ( A ) := + ∞ κ ( A ) \kappa(A) κ ( A ) A A A 条件数 (condition number of a matrix )R n \R^n R n ∥ h ∥ ∞ = max i ∣ h i ∣ \lVert h\rVert_\infty=\max_i\lvert h_i\rvert ∥ h ∥ ∞ = max i ∣ h i ∣ ∥ h ∥ 2 \lVert h\rVert_2 ∥ h ∥ 2 κ ( A ) \kappa(A) κ ( A ) κ ∞ ( A ) \kappa_\infty(A) κ ∞ ( A ) κ 2 ( A ) \kappa_2(A) κ 2 ( A )
命題 4.4. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 R n \R^n R n ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ A ∈ M n ( R ) A\in M_n(\R) A ∈ M n ( R )
ρ ( A ) ≤ ∥ A ∥ \rho(A)\le\lVert A\rVert ρ ( A ) ≤ ∥ A ∥ κ ( A ) ≥ 1 \kappa(A)\ge1 κ ( A ) ≥ 1 A A A S A : R n → R n S_A\colon\R^n\to\R^n S A : R n → R n S A ( b ) : = A − 1 b S_A(b):=A^{-1}b S A ( b ) := A − 1 b b ≠ 0 b\ne0 b = 0 κ r e l ( S A , b ) = ∥ A − 1 ∥ ∥ b ∥ / ∥ A − 1 b ∥ ≤ κ ( A ) \kappa_{\mathrm{rel}}(S_A,b)=\lVert A^{-1}\rVert\lVert b\rVert/\lVert A^{-1}b\rVert\le\kappa(A) κ rel ( S A , b ) = ∥ A − 1 ∥ ∥ b ∥ / ∥ A − 1 b ∥ ≤ κ ( A ) max b ≠ 0 κ r e l ( S A , b ) = κ ( A ) \max_{b\ne0}\kappa_{\mathrm{rel}}(S_A,b)=\kappa(A) max b = 0 κ rel ( S A , b ) = κ ( A ) A A A σ 1 ≥ ⋯ ≥ σ n \sigma_1\ge\dots\ge\sigma_n σ 1 ≥ ⋯ ≥ σ n A A A σ n > 0 \sigma_n>0 σ n > 0 κ 2 ( A ) = σ 1 / σ n \kappa_2(A)=\sigma_1/\sigma_n κ 2 ( A ) = σ 1 / σ n A A A λ max \lambda_{\max} λ m a x λ min \lambda_{\min} λ m i n A A A λ min > 0 \lambda_{\min}>0 λ m i n > 0 κ 2 ( A ) = λ max / λ min \kappa_2(A)=\lambda_{\max}/\lambda_{\min} κ 2 ( A ) = λ m a x / λ m i n 証明. (1) を示す。λ ∈ C \lambda\in\C λ ∈ C det ( λ I − A ) = 0 \det(\lambda I-A)=0 det ( λ I − A ) = 0 z ∈ C n ∖ { 0 } z\in\C^n\setminus\{0\} z ∈ C n ∖ { 0 } A z = λ z Az=\lambda z A z = λ z w ∈ C n w\in\C^n w ∈ C n Re w ∈ R n \operatorname{Re}w\in\R^n Re w ∈ R n N ( w ) : = sup θ ∈ R ∥ Re ( e i θ w ) ∥ N(w):=\sup_{\theta\in\R}\lVert\operatorname{Re}(e^{i\theta}w)\rVert N ( w ) := sup θ ∈ R ∥ Re ( e i θ w )∥ w = x + i y w=x+iy w = x + i y x , y ∈ R n x,y\in\R^n x , y ∈ R n Re ( e i θ w ) = x cos θ − y sin θ \operatorname{Re}(e^{i\theta}w)=x\cos\theta-y\sin\theta Re ( e i θ w ) = x cos θ − y sin θ N ( w ) ≤ ∥ x ∥ + ∥ y ∥ N(w)\le\lVert x\rVert+\lVert y\rVert N ( w ) ≤ ∥ x ∥ + ∥ y ∥ θ = 0 \theta=0 θ = 0 θ = − π / 2 \theta=-\pi/2 θ = − π /2 N ( w ) ≥ max { ∥ x ∥ , ∥ y ∥ } N(w)\ge\max\{\lVert x\rVert,\lVert y\rVert\} N ( w ) ≥ max {∥ x ∥ , ∥ y ∥} N ( z ) > 0 N(z)>0 N ( z ) > 0 A A A Re ( e i θ A w ) = A Re ( e i θ w ) \operatorname{Re}(e^{i\theta}Aw)=A\operatorname{Re}(e^{i\theta}w) Re ( e i θ A w ) = A Re ( e i θ w ) §E20.2 補題 1.2 (1) によりN ( A w ) ≤ ∥ A ∥ N ( w ) N(Aw)\le\lVert A\rVert N(w) N ( A w ) ≤ ∥ A ∥ N ( w ) λ = ∣ λ ∣ e i φ \lambda=\lvert\lambda\rvert e^{i\varphi} λ = ∣ λ ∣ e i φ Re ( e i θ λ w ) = ∣ λ ∣ Re ( e i ( θ + φ ) w ) \operatorname{Re}(e^{i\theta}\lambda w)=\lvert\lambda\rvert\operatorname{Re}(e^{i(\theta+\varphi)}w) Re ( e i θ λ w ) = ∣ λ ∣ Re ( e i ( θ + φ ) w ) N ( λ w ) = ∣ λ ∣ N ( w ) N(\lambda w)=\lvert\lambda\rvert N(w) N ( λ w ) = ∣ λ ∣ N ( w ) ∣ λ ∣ N ( z ) = N ( A z ) ≤ ∥ A ∥ N ( z ) \lvert\lambda\rvert N(z)=N(Az)\le\lVert A\rVert N(z) ∣ λ ∣ N ( z ) = N ( A z ) ≤ ∥ A ∥ N ( z ) ∣ λ ∣ ≤ ∥ A ∥ \lvert\lambda\rvert\le\lVert A\rVert ∣ λ ∣ ≤ ∥ A ∥
(2) を示す。A A A κ ( A ) = + ∞ \kappa(A)=+\infty κ ( A ) = + ∞ A A A X , Y ∈ M n ( R ) X,Y\in M_n(\R) X , Y ∈ M n ( R ) h ∈ R n h\in\R^n h ∈ R n §E20.2 補題 1.2 (1) により∥ X Y h ∥ ≤ ∥ X ∥ ∥ Y ∥ ∥ h ∥ \lVert XYh\rVert\le\lVert X\rVert\lVert Y\rVert\lVert h\rVert ∥ X Y h ∥ ≤ ∥ X ∥ ∥ Y ∥ ∥ h ∥ ∥ X Y ∥ ≤ ∥ X ∥ ∥ Y ∥ \lVert XY\rVert\le\lVert X\rVert\lVert Y\rVert ∥ X Y ∥ ≤ ∥ X ∥ ∥ Y ∥ ∥ I ∥ = 1 \lVert I\rVert=1 ∥ I ∥ = 1 1 = ∥ A A − 1 ∥ ≤ ∥ A ∥ ∥ A − 1 ∥ 1=\lVert AA^{-1}\rVert\le\lVert A\rVert\lVert A^{-1}\rVert 1 = ∥ A A − 1 ∥ ≤ ∥ A ∥ ∥ A − 1 ∥
(3) を示す。S A S_A S A S A − 1 ( h ) = A h S_A^{-1}(h)=Ah S A − 1 ( h ) = A h §E20.2 定理 3.5 (1) をS A S_A S A b ≠ 0 b\ne0 b = 0 κ r e l ( S A , b ) = ∥ A − 1 ∥ ∥ b ∥ / ∥ A − 1 b ∥ \kappa_{\mathrm{rel}}(S_A,b)=\lVert A^{-1}\rVert\lVert b\rVert/\lVert A^{-1}b\rVert κ rel ( S A , b ) = ∥ A − 1 ∥ ∥ b ∥ / ∥ A − 1 b ∥ §E20.2 定理 3.5 (2) により、これは∥ S A ∥ ∥ S A − 1 ∥ = ∥ A − 1 ∥ ∥ A ∥ \lVert S_A\rVert\lVert S_A^{-1}\rVert=\lVert A^{-1}\rVert\lVert A\rVert ∥ S A ∥ ∥ S A − 1 ∥ = ∥ A − 1 ∥ ∥ A ∥ ∥ A − 1 ∥ ∥ A ∥ \lVert A^{-1}\rVert\lVert A\rVert ∥ A − 1 ∥ ∥ A ∥ b ≠ 0 b\ne0 b = 0
(4) を示す。§D3.18 定理 1.2 により、直交行列U , V U,V U , V Σ = diag ( σ 1 , … , σ n ) \Sigma=\operatorname{diag}(\sigma_1,\dots,\sigma_n) Σ = diag ( σ 1 , … , σ n ) A = U Σ V T A=U\Sigma V^{\mathsf T} A = U Σ V T §D3.18 命題 2.1 によりσ 1 , … , σ n \sigma_1,\dots,\sigma_n σ 1 , … , σ n A A A n n n σ n > 0 \sigma_n>0 σ n > 0 ∥ ⋅ ∥ 2 \lVert\cdot\rVert_2 ∥ ⋅ ∥ 2 ∥ A h ∥ 2 = ∥ Σ V T h ∥ 2 \lVert Ah\rVert_2=\lVert\Sigma V^{\mathsf T}h\rVert_2 ∥ A h ∥ 2 = ∥ Σ V T h ∥ 2 ∥ V T h ∥ 2 = ∥ h ∥ 2 \lVert V^{\mathsf T}h\rVert_2=\lVert h\rVert_2 ∥ V T h ∥ 2 = ∥ h ∥ 2 ∥ A ∥ 2 = ∥ Σ ∥ 2 \lVert A\rVert_2=\lVert\Sigma\rVert_2 ∥ A ∥ 2 = ∥ Σ ∥ 2 ∥ Σ k ∥ 2 2 = ∑ i σ i 2 k i 2 ≤ σ 1 2 ∥ k ∥ 2 2 \lVert\Sigma k\rVert_2^2=\sum_i\sigma_i^2k_i^2\le\sigma_1^2\lVert k\rVert_2^2 ∥ Σ k ∥ 2 2 = ∑ i σ i 2 k i 2 ≤ σ 1 2 ∥ k ∥ 2 2 k k k 1 1 1 ∥ Σ ∥ 2 = σ 1 \lVert\Sigma\rVert_2=\sigma_1 ∥ Σ ∥ 2 = σ 1 A − 1 = V Σ − 1 U T A^{-1}=V\Sigma^{-1}U^{\mathsf T} A − 1 = V Σ − 1 U T Σ − 1 = diag ( 1 / σ 1 , … , 1 / σ n ) \Sigma^{-1}=\operatorname{diag}(1/\sigma_1,\dots,1/\sigma_n) Σ − 1 = diag ( 1/ σ 1 , … , 1/ σ n ) ∥ A − 1 ∥ 2 = 1 / σ n \lVert A^{-1}\rVert_2=1/\sigma_n ∥ A − 1 ∥ 2 = 1/ σ n
(5) を示す。§D3.15 定理 3.1 により、直交行列Q Q Q λ 1 ≥ ⋯ ≥ λ n \lambda_1\ge\dots\ge\lambda_n λ 1 ≥ ⋯ ≥ λ n A = Q diag ( λ 1 , … , λ n ) Q T A=Q\operatorname{diag}(\lambda_1,\dots,\lambda_n)Q^{\mathsf T} A = Q diag ( λ 1 , … , λ n ) Q T Q Q Q i i i q i q_i q i λ i = q i T A q i > 0 \lambda_i=q_i^{\mathsf T}Aq_i>0 λ i = q i T A q i > 0 λ min = λ n > 0 \lambda_{\min}=\lambda_n>0 λ m i n = λ n > 0 A = ∑ i λ i q i q i T A=\sum_i\lambda_iq_iq_i^{\mathsf T} A = ∑ i λ i q i q i T §D3.18 定理 1.2 の形の分解であるから、§D3.18 命題 2.1 によりA A A λ 1 , … , λ n \lambda_1,\dots,\lambda_n λ 1 , … , λ n (4) によりκ 2 ( A ) = λ 1 / λ n \kappa_2(A)=\lambda_1/\lambda_n κ 2 ( A ) = λ 1 / λ n ▨
命題 4.5. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 R n \R^n R n ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ A ∈ M n ( R ) A\in M_n(\R) A ∈ M n ( R ) b ∈ R n b\in\R^n b ∈ R n b ≠ 0 b\ne0 b = 0 x : = A − 1 b x:=A^{-1}b x := A − 1 b x ^ ∈ R n \widehat x\in\R^n x ∈ R n r : = b − A x ^ r:=b-A\widehat x r := b − A x
∥ x − x ^ ∥ ∥ x ∥ ≤ κ ( A ) ∥ r ∥ ∥ b ∥ \frac{\lVert x-\widehat x\rVert}{\lVert x\rVert}\le\kappa(A)\frac{\lVert r\rVert}{\lVert b\rVert} ∥ x ∥ ∥ x − x ∥ ≤ κ ( A ) ∥ b ∥ ∥ r ∥ が成り立つ。
証明. b ≠ 0 b\ne0 b = 0 x ≠ 0 x\ne0 x = 0 x − x ^ = A − 1 ( b − A x ^ ) = A − 1 r x-\widehat x=A^{-1}(b-A\widehat x)=A^{-1}r x − x = A − 1 ( b − A x ) = A − 1 r §E20.2 補題 1.2 (1) により∥ x − x ^ ∥ ≤ ∥ A − 1 ∥ ∥ r ∥ \lVert x-\widehat x\rVert\le\lVert A^{-1}\rVert\lVert r\rVert ∥ x − x ∥ ≤ ∥ A − 1 ∥ ∥ r ∥ ∥ b ∥ = ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥ \lVert b\rVert=\lVert Ax\rVert\le\lVert A\rVert\lVert x\rVert ∥ b ∥ = ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥ ∥ x − x ^ ∥ / ∥ x ∥ ≤ ∥ A − 1 ∥ ∥ A ∥ ∥ r ∥ / ∥ b ∥ \lVert x-\widehat x\rVert/\lVert x\rVert\le\lVert A^{-1}\rVert\lVert A\rVert\lVert r\rVert/\lVert b\rVert ∥ x − x ∥ / ∥ x ∥ ≤ ∥ A − 1 ∥ ∥ A ∥ ∥ r ∥ / ∥ b ∥ ▨
5 Cholesky 分解 定義 5.1. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 A ∈ M n ( R ) A\in M_n(\R) A ∈ M n ( R )
対角成分がすべて1 1 1 L L L D D D A = L D L T A=LDL^{\mathsf T} A = L D L T ( L , D ) (L,D) ( L , D ) A A A L D L T LDL^{\mathsf T} L D L T LDLT factorization )
対角成分がすべて正の下三角行列C C C A = C C T A=CC^{\mathsf T} A = C C T C C C A A A Cholesky 因子 (Cholesky factor )A = C C T A=CC^{\mathsf T} A = C C T A A A Cholesky 分解 (Cholesky factorization )
定理 5.2. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 A ∈ M n ( R ) A\in M_n(\R) A ∈ M n ( R ) 1 ≤ k ≤ n 1\le k\le n 1 ≤ k ≤ n A A A k × k k\times k k × k Δ k \Delta_k Δ k Δ 0 : = 1 \Delta_0:=1 Δ 0 := 1
A A A A A A k k k d k = Δ k / Δ k − 1 > 0 d_k=\Delta_k/\Delta_{k-1}>0 d k = Δ k / Δ k − 1 > 0 A A A (1) の消去の出力( L , U ) (L,U) ( L , U ) D : = diag ( d 1 , … , d n ) D:=\operatorname{diag}(d_1,\dots,d_n) D := diag ( d 1 , … , d n ) U = D L T U=DL^{\mathsf T} U = D L T ( L , D ) (L,D) ( L , D ) A A A L D L T LDL^{\mathsf T} L D L T A A A C : = L diag ( d 1 , … , d n ) C:=L\operatorname{diag}(\sqrt{d_1},\dots,\sqrt{d_n}) C := L diag ( d 1 , … , d n ) A A A A A A C C C A A A A A A A A A A A A C C C j = 1 , … , n j=1,\dots,n j = 1 , … , n c j j = ( a j j − ∑ m = 1 j − 1 c j m 2 ) 1 / 2 , c i j = 1 c j j ( a i j − ∑ m = 1 j − 1 c i m c j m ) ( i > j ) c_{jj}=\Bigl(a_{jj}-\sum_{m=1}^{j-1}c_{jm}^2\Bigr)^{1/2},\qquad c_{ij}=\frac{1}{c_{jj}}\Bigl(a_{ij}-\sum_{m=1}^{j-1}c_{im}c_{jm}\Bigr)\quad(i>j) c j j = ( a j j − m = 1 ∑ j − 1 c j m 2 ) 1/2 , c ij = c j j 1 ( a ij − m = 1 ∑ j − 1 c im c j m ) ( i > j ) n 3 / 3 + n 2 / 2 − 5 n / 6 n^3/3+n^2/2-5n/6 n 3 /3 + n 2 /2 − 5 n /6 n n n 証明. (1) を示す。§E3.40 定理 3.1 によりΔ k > 0 \Delta_k>0 Δ k > 0 1 ≤ k ≤ n 1\le k\le n 1 ≤ k ≤ n 1 ≤ k ≤ n 1\le k\le n 1 ≤ k ≤ n 1 , … , k − 1 1,\dots,k-1 1 , … , k − 1 m < k m<k m < k d m = Δ m / Δ m − 1 d_m=\Delta_m/\Delta_{m-1} d m = Δ m / Δ m − 1 補題 2.3 によりA = L ( k ) R ( k ) A=L^{(k)}R^{(k)} A = L ( k ) R ( k ) L ( k ) L^{(k)} L ( k ) A A A k × k k\times k k × k L ( k ) L^{(k)} L ( k ) R ( k ) R^{(k)} R ( k ) k × k k\times k k × k 1 1 1 d 1 , … , d k − 1 , w k k ( k ) d_1,\dots,d_{k-1},w^{(k)}_{kk} d 1 , … , d k − 1 , w k k ( k )
Δ k = d 1 ⋯ d k − 1 w k k ( k ) = Δ k − 1 w k k ( k ) \Delta_k=d_1\cdots d_{k-1}w^{(k)}_{kk}=\Delta_{k-1}w^{(k)}_{kk} Δ k = d 1 ⋯ d k − 1 w k k ( k ) = Δ k − 1 w k k ( k ) である。したがって段k k k w k k ( k ) = Δ k / Δ k − 1 > 0 w^{(k)}_{kk}=\Delta_k/\Delta_{k-1}>0 w k k ( k ) = Δ k / Δ k − 1 > 0 k k k
(2) を示す。
主張 5.2.1. L 1 , L 2 L_1,L_2 L 1 , L 2 1 1 1 U 1 , U 2 U_1,U_2 U 1 , U 2 1 1 1 D 1 , D 2 D_1,D_2 D 1 , D 2 L 1 D 1 U 1 = L 2 D 2 U 2 L_1D_1U_1=L_2D_2U_2 L 1 D 1 U 1 = L 2 D 2 U 2 L 1 = L 2 L_1=L_2 L 1 = L 2 D 1 = D 2 D_1=D_2 D 1 = D 2 U 1 = U 2 U_1=U_2 U 1 = U 2
証明. L 1 D 1 U 1 = L 2 D 2 U 2 L_1D_1U_1=L_2D_2U_2 L 1 D 1 U 1 = L 2 D 2 U 2 L 2 − 1 L_2^{-1} L 2 − 1 U 1 − 1 U_1^{-1} U 1 − 1 L 2 − 1 L 1 D 1 = D 2 U 2 U 1 − 1 L_2^{-1}L_1D_1=D_2U_2U_1^{-1} L 2 − 1 L 1 D 1 = D 2 U 2 U 1 − 1 L 2 − 1 L 1 L_2^{-1}L_1 L 2 − 1 L 1 1 1 1 D 1 D_1 D 1 D 1 D_1 D 1 D 1 D_1 D 1 L 2 − 1 L 1 = I L_2^{-1}L_1=I L 2 − 1 L 1 = I D 2 D_2 D 2 D 2 U 2 U 1 − 1 = D 1 D_2U_2U_1^{-1}=D_1 D 2 U 2 U 1 − 1 = D 1 D 2 = D 1 D_2=D_1 D 2 = D 1 U 2 U 1 − 1 = I U_2U_1^{-1}=I U 2 U 1 − 1 = I ▨
(1) と補題 2.3 によりA = L U A=LU A = LU U U U d 1 , … , d n d_1,\dots,d_n d 1 , … , d n U 1 : = D − 1 U U_1:=D^{-1}U U 1 := D − 1 U 1 1 1 A = L D U 1 A=LDU_1 A = L D U 1 A T = A A^{\mathsf T}=A A T = A U 1 T D L T = L D U 1 U_1^{\mathsf T}DL^{\mathsf T}=LDU_1 U 1 T D L T = L D U 1 主張 5.2.1 によりU 1 = L T U_1=L^{\mathsf T} U 1 = L T U = D L T U=DL^{\mathsf T} U = D L T A = L D L T A=LDL^{\mathsf T} A = L D L T
(3) を示す。D 1 / 2 : = diag ( d 1 , … , d n ) D^{1/2}:=\operatorname{diag}(\sqrt{d_1},\dots,\sqrt{d_n}) D 1/2 := diag ( d 1 , … , d n ) C = L D 1 / 2 C=LD^{1/2} C = L D 1/2 d k > 0 \sqrt{d_k}>0 d k > 0 C C T = L D 1 / 2 D 1 / 2 L T = A CC^{\mathsf T}=LD^{1/2}D^{1/2}L^{\mathsf T}=A C C T = L D 1/2 D 1/2 L T = A C ′ C' C ′ A A A Γ : = diag ( c 11 ′ , … , c n n ′ ) \Gamma:=\operatorname{diag}(c'_{11},\dots,c'_{nn}) Γ := diag ( c 11 ′ , … , c nn ′ ) L ′ : = C ′ Γ − 1 L':=C'\Gamma^{-1} L ′ := C ′ Γ − 1 L ′ L' L ′ 1 1 1 A = L ′ Γ 2 L ′ T A=L'\Gamma^2L'^{\mathsf T} A = L ′ Γ 2 L ′ T 主張 5.2.1 をA = L D L T A=LDL^{\mathsf T} A = L D L T L ′ = L L'=L L ′ = L Γ 2 = D \Gamma^2=D Γ 2 = D c k k ′ > 0 c'_{kk}>0 c k k ′ > 0 Γ = D 1 / 2 \Gamma=D^{1/2} Γ = D 1/2 C ′ = C C'=C C ′ = C
(4) を示す。C C C A A A C T C^{\mathsf T} C T x ∈ R n ∖ { 0 } x\in\R^n\setminus\{0\} x ∈ R n ∖ { 0 } x T A x = ∥ C T x ∥ 2 2 > 0 x^{\mathsf T}Ax=\lVert C^{\mathsf T}x\rVert_2^2>0 x T A x = ∥ C T x ∥ 2 2 > 0
(5) を示す。A = C C T A=CC^{\mathsf T} A = C C T ( i , j ) (i,j) ( i , j ) i ≥ j i\ge j i ≥ j C C C a i j = ∑ m = 1 j c i m c j m a_{ij}=\sum_{m=1}^{j}c_{im}c_{jm} a ij = ∑ m = 1 j c im c j m i = j i=j i = j c j j 2 = a j j − ∑ m < j c j m 2 c_{jj}^2=a_{jj}-\sum_{m<j}c_{jm}^2 c j j 2 = a j j − ∑ m < j c j m 2 c j j > 0 c_{jj}>0 c j j > 0 i > j i>j i > j j j j C C C j = 1 , … , n j=1,\dots,n j = 1 , … , n 問題 8.2 ）。▨
6 三重対角行列 定理 6.1. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 A ∈ M n ( R ) A\in M_n(\R) A ∈ M n ( R ) ( i , i ) (i,i) ( i , i ) b i b_i b i ( i , i − 1 ) (i,i-1) ( i , i − 1 ) a i a_i a i 2 ≤ i ≤ n 2\le i\le n 2 ≤ i ≤ n ( i , i + 1 ) (i,i+1) ( i , i + 1 ) c i c_i c i 1 ≤ i ≤ n − 1 1\le i\le n-1 1 ≤ i ≤ n − 1 0 0 0 a 1 : = 0 a_1:=0 a 1 := 0 c n : = 0 c_n:=0 c n := 0 d 1 : = b 1 d_1:=b_1 d 1 := b 1 d i − 1 ≠ 0 d_{i-1}\ne0 d i − 1 = 0 d i : = b i − a i c i − 1 / d i − 1 d_i:=b_i-a_ic_{i-1}/d_{i-1} d i := b i − a i c i − 1 / d i − 1 2 ≤ i ≤ n 2\le i\le n 2 ≤ i ≤ n
A A A 1 , … , k − 1 1,\dots,k-1 1 , … , k − 1 k k k d k d_k d k d 1 , … , d n d_1,\dots,d_n d 1 , … , d n 0 0 0 ( L , U ) (L,U) ( L , U ) L L L 0 0 0 ( i , i − 1 ) (i,i-1) ( i , i − 1 ) l i : = a i / d i − 1 l_i:=a_i/d_{i-1} l i := a i / d i − 1 2 ≤ i ≤ n 2\le i\le n 2 ≤ i ≤ n U U U 0 0 0 ( i , i ) (i,i) ( i , i ) d i d_i d i ( i , i + 1 ) (i,i+1) ( i , i + 1 ) c i c_i c i A A A f ∈ R n f\in\R^n f ∈ R n y 1 : = f 1 , y i : = f i − l i y i − 1 ( 2 ≤ i ≤ n ) , x n : = y n d n , x i : = y i − c i x i + 1 d i ( i = n − 1 , … , 1 ) y_1:=f_1,\quad y_i:=f_i-l_iy_{i-1}\ (2\le i\le n),\qquad x_n:=\frac{y_n}{d_n},\quad x_i:=\frac{y_i-c_ix_{i+1}}{d_i}\ (i=n-1,\dots,1) y 1 := f 1 , y i := f i − l i y i − 1 ( 2 ≤ i ≤ n ) , x n := d n y n , x i := d i y i − c i x i + 1 ( i = n − 1 , … , 1 ) x x x A x = f Ax=f A x = f l i l_i l i d i d_i d i x x x 8 n − 7 8n-7 8 n − 7 任意のi i i ∣ b i ∣ > ∣ a i ∣ + ∣ c i ∣ \lvert b_i\rvert>\lvert a_i\rvert+\lvert c_i\rvert ∣ b i ∣ > ∣ a i ∣ + ∣ c i ∣ d 1 , … , d n d_1,\dots,d_n d 1 , … , d n i i i ∣ d i ∣ > ∣ c i ∣ \lvert d_i\rvert>\lvert c_i\rvert ∣ d i ∣ > ∣ c i ∣ d i ≠ 0 d_i\ne0 d i = 0 (1) の結論が成り立つ。
A A A d 1 , … , d n d_1,\dots,d_n d 1 , … , d n 定理 5.2 (1) のΔ k \Delta_k Δ k d k = Δ k / Δ k − 1 > 0 d_k=\Delta_k/\Delta_{k-1}>0 d k = Δ k / Δ k − 1 > 0 (1) の結論が成り立つ。 証明. (1) を示す。1 ≤ k < n 1\le k<n 1 ≤ k < n k k k i , j ≥ k i,j\ge k i , j ≥ k ( k , k ) (k,k) ( k , k ) d k d_k d k A A A k k k k k k i > k i>k i > k i = k + 1 i=k+1 i = k + 1 a k + 1 a_{k+1} a k + 1 i ≥ k + 2 i\ge k+2 i ≥ k + 2 0 0 0 k k k k + 1 k+1 k + 1 a k + 1 / d k a_{k+1}/d_k a k + 1 / d k 0 0 0 k k k j > k j>k j > k j = k + 1 j=k+1 j = k + 1 c k c_k c k j ≥ k + 2 j\ge k+2 j ≥ k + 2 0 0 0 i , j > k i,j>k i , j > k k k k ( k + 1 , k + 1 ) (k+1,k+1) ( k + 1 , k + 1 ) b k + 1 − a k + 1 c k / d k = d k + 1 b_{k+1}-a_{k+1}c_k/d_k=d_{k+1} b k + 1 − a k + 1 c k / d k = d k + 1 k + 1 k+1 k + 1 W ( 1 ) = A W^{(1)}=A W ( 1 ) = A d 1 = b 1 d_1=b_1 d 1 = b 1 k k k 1 , … , k − 1 1,\dots,k-1 1 , … , k − 1 k k k d k d_k d k m < k m<k m < k m + 1 m+1 m + 1 a m + 1 / d m a_{m+1}/d_m a m + 1 / d m 0 0 0 d 1 , … , d n d_1,\dots,d_n d 1 , … , d n 0 0 0 k k k k k k U U U k k k 0 0 0 d k d_k d k c k c_k c k L L L 補題 2.3 によりA = L U A=LU A = LU det A = d 1 ⋯ d n ≠ 0 \det A=d_1\cdots d_n\ne0 det A = d 1 ⋯ d n = 0 y y y L y = f Ly=f L y = f x x x U x = y Ux=y U x = y A x = L U x = f Ax=LUx=f A x = LU x = f A A A l i l_i l i d i d_i d i 2 ≤ i ≤ n 2\le i\le n 2 ≤ i ≤ n 3 ( n − 1 ) 3(n-1) 3 ( n − 1 ) y y y 2 ( n − 1 ) 2(n-1) 2 ( n − 1 ) x x x 3 ( n − 1 ) + 1 3(n-1)+1 3 ( n − 1 ) + 1 8 n − 7 8n-7 8 n − 7
(2) を示す。∣ d 1 ∣ = ∣ b 1 ∣ > ∣ c 1 ∣ \lvert d_1\rvert=\lvert b_1\rvert>\lvert c_1\rvert ∣ d 1 ∣ = ∣ b 1 ∣ > ∣ c 1 ∣ 2 ≤ i ≤ n 2\le i\le n 2 ≤ i ≤ n ∣ d i − 1 ∣ > ∣ c i − 1 ∣ \lvert d_{i-1}\rvert>\lvert c_{i-1}\rvert ∣ d i − 1 ∣ > ∣ c i − 1 ∣ d i − 1 ≠ 0 d_{i-1}\ne0 d i − 1 = 0 d i d_i d i ∣ c i − 1 ∣ / ∣ d i − 1 ∣ < 1 \lvert c_{i-1}\rvert/\lvert d_{i-1}\rvert<1 ∣ c i − 1 ∣ / ∣ d i − 1 ∣ < 1
∣ d i ∣ ≥ ∣ b i ∣ − ∣ a i ∣ ∣ c i − 1 ∣ ∣ d i − 1 ∣ ≥ ∣ b i ∣ − ∣ a i ∣ > ∣ c i ∣ \lvert d_i\rvert\ge\lvert b_i\rvert-\lvert a_i\rvert\frac{\lvert c_{i-1}\rvert}{\lvert d_{i-1}\rvert}\ge\lvert b_i\rvert-\lvert a_i\rvert>\lvert c_i\rvert ∣ d i ∣ ≥ ∣ b i ∣ − ∣ a i ∣ ∣ d i − 1 ∣ ∣ c i − 1 ∣ ≥ ∣ b i ∣ − ∣ a i ∣ > ∣ c i ∣ である。i i i
(3) を示す。定理 5.2 (1) により、A A A k k k Δ k / Δ k − 1 > 0 \Delta_k/\Delta_{k-1}>0 Δ k / Δ k − 1 > 0 (1) により、k k k d k d_k d k k k k ▨
命題 6.2. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 A = ( a i j ) ∈ M n ( R ) A=(a_{ij})\in M_n(\R) A = ( a ij ) ∈ M n ( R )
δ : = min 1 ≤ i ≤ n ( ∣ a i i ∣ − ∑ j ≠ i ∣ a i j ∣ ) > 0 \delta:=\min_{1\le i\le n}\Bigl(\lvert a_{ii}\rvert-\sum_{j\ne i}\lvert a_{ij}\rvert\Bigr)>0 δ := 1 ≤ i ≤ n min ( ∣ a ii ∣ − j = i ∑ ∣ a ij ∣ ) > 0 を満たすとする。このときA A A ∥ A − 1 ∥ ∞ ≤ 1 / δ \lVert A^{-1}\rVert_\infty\le1/\delta ∥ A − 1 ∥ ∞ ≤ 1/ δ b ∈ R n b\in\R^n b ∈ R n x : = A − 1 b x:=A^{-1}b x := A − 1 b x ^ ∈ R n \widehat x\in\R^n x ∈ R n ∥ x − x ^ ∥ ∞ ≤ ∥ b − A x ^ ∥ ∞ / δ \lVert x-\widehat x\rVert_\infty\le\lVert b-A\widehat x\rVert_\infty/\delta ∥ x − x ∥ ∞ ≤ ∥ b − A x ∥ ∞ / δ
証明. h ∈ R n h\in\R^n h ∈ R n ∣ h i ∣ = ∥ h ∥ ∞ \lvert h_i\rvert=\lVert h\rVert_\infty ∣ h i ∣ = ∥ h ∥ ∞ i i i
∣ ( A h ) i ∣ ≥ ∣ a i i ∣ ∣ h i ∣ − ∑ j ≠ i ∣ a i j ∣ ∣ h j ∣ ≥ ( ∣ a i i ∣ − ∑ j ≠ i ∣ a i j ∣ ) ∥ h ∥ ∞ ≥ δ ∥ h ∥ ∞ \lvert(Ah)_i\rvert\ge\lvert a_{ii}\rvert\lvert h_i\rvert-\sum_{j\ne i}\lvert a_{ij}\rvert\lvert h_j\rvert\ge\Bigl(\lvert a_{ii}\rvert-\sum_{j\ne i}\lvert a_{ij}\rvert\Bigr)\lVert h\rVert_\infty\ge\delta\lVert h\rVert_\infty ∣( A h ) i ∣ ≥ ∣ a ii ∣ ∣ h i ∣ − j = i ∑ ∣ a ij ∣ ∣ h j ∣ ≥ ( ∣ a ii ∣ − j = i ∑ ∣ a ij ∣ ) ∥ h ∥ ∞ ≥ δ ∥ h ∥ ∞ であるから、∥ A h ∥ ∞ ≥ δ ∥ h ∥ ∞ \lVert Ah\rVert_\infty\ge\delta\lVert h\rVert_\infty ∥ A h ∥ ∞ ≥ δ ∥ h ∥ ∞ δ > 0 \delta>0 δ > 0 A A A v ∈ R n v\in\R^n v ∈ R n h : = A − 1 v h:=A^{-1}v h := A − 1 v ∥ A − 1 v ∥ ∞ ≤ ∥ v ∥ ∞ / δ \lVert A^{-1}v\rVert_\infty\le\lVert v\rVert_\infty/\delta ∥ A − 1 v ∥ ∞ ≤ ∥ v ∥ ∞ / δ x − x ^ = A − 1 ( b − A x ^ ) x-\widehat x=A^{-1}(b-A\widehat x) x − x = A − 1 ( b − A x ) ▨
例 6.3. n ≥ 3 n\ge3 n ≥ 3 定理 6.1 でb i = 4 b_i=4 b i = 4 1 ≤ i ≤ n 1\le i\le n 1 ≤ i ≤ n a i = 1 a_i=1 a i = 1 2 ≤ i ≤ n 2\le i\le n 2 ≤ i ≤ n c i = 1 c_i=1 c i = 1 1 ≤ i ≤ n − 1 1\le i\le n-1 1 ≤ i ≤ n − 1 ∣ b i ∣ = 4 > 2 ≥ ∣ a i ∣ + ∣ c i ∣ \lvert b_i\rvert=4>2\ge\lvert a_i\rvert+\lvert c_i\rvert ∣ b i ∣ = 4 > 2 ≥ ∣ a i ∣ + ∣ c i ∣ 定理 6.1 (2) が適用される。n = 5 n=5 n = 5 d 1 , … , d 5 d_1,\dots,d_5 d 1 , … , d 5 4 , 15 / 4 , 56 / 15 , 209 / 56 , 780 / 209 4,\ 15/4,\ 56/15,\ 209/56,\ 780/209 4 , 15/4 , 56/15 , 209/56 , 780/209 1 1 1 命題 6.2 のδ \delta δ min { 4 − 1 , 4 − 2 } = 2 \min\{4-1,\ 4-2\}=2 min { 4 − 1 , 4 − 2 } = 2 ∥ A − 1 ∥ ∞ ≤ 1 / 2 \lVert A^{-1}\rVert_\infty\le1/2 ∥ A − 1 ∥ ∞ ≤ 1/2 f , x ^ ∈ R n f,\widehat x\in\R^n f , x ∈ R n x : = A − 1 f x:=A^{-1}f x := A − 1 f ∥ x − x ^ ∥ ∞ ≤ ∥ f − A x ^ ∥ ∞ / 2 \lVert x-\widehat x\rVert_\infty\le\lVert f-A\widehat x\rVert_\infty/2 ∥ x − x ∥ ∞ ≤ ∥ f − A x ∥ ∞ /2 補題 3.5 (1) により∥ A ∥ ∞ = 6 \lVert A\rVert_\infty=6 ∥ A ∥ ∞ = 6 κ ∞ ( A ) ≤ 3 \kappa_\infty(A)\le3 κ ∞ ( A ) ≤ 3 n = 1000 n=1000 n = 1000 定理 6.1 (1) の計算は8 n − 7 = 7993 8n-7=7993 8 n − 7 = 7993 A A A M n ( R ) M_n(\R) M n ( R ) 定理 2.5 の消去と二つの代入で解くと、定理 2.5 (3) により2 n 3 / 3 − n 2 / 2 − n / 6 + 2 n 2 − n = 668165500 2n^3/3-n^2/2-n/6+2n^2-n=668165500 2 n 3 /3 − n 2 /2 − n /6 + 2 n 2 − n = 668165500
7 残差による反復改良 命題 7.1. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 R n \R^n R n ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ M n ( R ) M_n(\R) M n ( R ) A ∈ M n ( R ) A\in M_n(\R) A ∈ M n ( R ) b ∈ R n b\in\R^n b ∈ R n x : = A − 1 b x:=A^{-1}b x := A − 1 b M ∈ M n ( R ) M\in M_n(\R) M ∈ M n ( R ) q : = ∥ I − M A ∥ q:=\lVert I-MA\rVert q := ∥ I − M A ∥
x 0 ∈ R n x_0\in\R^n x 0 ∈ R n k ≥ 0 k\ge0 k ≥ 0 x k + 1 : = x k + M ( b − A x k ) x_{k+1}:=x_k+M(b-Ax_k) x k + 1 := x k + M ( b − A x k ) e k : = x − x k e_k:=x-x_k e k := x − x k e k + 1 = ( I − M A ) e k e_{k+1}=(I-MA)e_k e k + 1 = ( I − M A ) e k ∥ e k ∥ ≤ q k ∥ e 0 ∥ \lVert e_k\rVert\le q^k\lVert e_0\rVert ∥ e k ∥ ≤ q k ∥ e 0 ∥ ( x k ) k ≥ 0 (x_k)_{k\ge0} ( x k ) k ≥ 0 ( r ^ k ) k ≥ 0 (\widehat r_k)_{k\ge0} ( r k ) k ≥ 0 R n \R^n R n e k : = x − x k e_k:=x-x_k e k := x − x k η k : = r ^ k − ( b − A x k ) \eta_k:=\widehat r_k-(b-Ax_k) η k := r k − ( b − A x k ) ρ k : = x k + 1 − x k − M r ^ k \rho_k:=x_{k+1}-x_k-M\widehat r_k ρ k := x k + 1 − x k − M r k e k + 1 = ( I − M A ) e k − M η k − ρ k e_{k+1}=(I-MA)e_k-M\eta_k-\rho_k e k + 1 = ( I − M A ) e k − M η k − ρ k ∥ e k + 1 ∥ ≤ q ∥ e k ∥ + ∥ M ∥ ∥ η k ∥ + ∥ ρ k ∥ \lVert e_{k+1}\rVert\le q\lVert e_k\rVert+\lVert M\rVert\lVert\eta_k\rVert+\lVert\rho_k\rVert ∥ e k + 1 ∥ ≤ q ∥ e k ∥ + ∥ M ∥ ∥ η k ∥ + ∥ ρ k ∥ (2) の記号で、q < 1 q<1 q < 1 τ ≥ 0 \tau\ge0 τ ≥ 0 k ≥ 0 k\ge0 k ≥ 0 ∥ M ∥ ∥ η k ∥ + ∥ ρ k ∥ ≤ τ \lVert M\rVert\lVert\eta_k\rVert+\lVert\rho_k\rVert\le\tau ∥ M ∥ ∥ η k ∥ + ∥ ρ k ∥ ≤ τ k ≥ 0 k\ge0 k ≥ 0 ∥ e k ∥ ≤ q k ∥ e 0 ∥ + τ / ( 1 − q ) \lVert e_k\rVert\le q^k\lVert e_0\rVert+\tau/(1-q) ∥ e k ∥ ≤ q k ∥ e 0 ∥ + τ / ( 1 − q ) 証明. (2) を示す。x k + 1 = x k + M r ^ k + ρ k = x k + M ( b − A x k ) + M η k + ρ k x_{k+1}=x_k+M\widehat r_k+\rho_k=x_k+M(b-Ax_k)+M\eta_k+\rho_k x k + 1 = x k + M r k + ρ k = x k + M ( b − A x k ) + M η k + ρ k b − A x k = A ( x − x k ) = A e k b-Ax_k=A(x-x_k)=Ae_k b − A x k = A ( x − x k ) = A e k e k + 1 = e k − M A e k − M η k − ρ k e_{k+1}=e_k-MAe_k-M\eta_k-\rho_k e k + 1 = e k − M A e k − M η k − ρ k §E20.2 補題 1.2 (1) と三角不等式により評価が成り立つ。
(1) を示す。(2) をr ^ k : = b − A x k \widehat r_k:=b-Ax_k r k := b − A x k η k = 0 \eta_k=0 η k = 0 ρ k = 0 \rho_k=0 ρ k = 0 e k + 1 = ( I − M A ) e k e_{k+1}=(I-MA)e_k e k + 1 = ( I − M A ) e k ∥ e k + 1 ∥ ≤ q ∥ e k ∥ \lVert e_{k+1}\rVert\le q\lVert e_k\rVert ∥ e k + 1 ∥ ≤ q ∥ e k ∥ k k k
(3) を示す。(2) により∥ e k + 1 ∥ ≤ q ∥ e k ∥ + τ \lVert e_{k+1}\rVert\le q\lVert e_k\rVert+\tau ∥ e k + 1 ∥ ≤ q ∥ e k ∥ + τ k k k ∥ e k ∥ ≤ q k ∥ e 0 ∥ + τ ∑ j = 0 k − 1 q j ≤ q k ∥ e 0 ∥ + τ / ( 1 − q ) \lVert e_k\rVert\le q^k\lVert e_0\rVert+\tau\sum_{j=0}^{k-1}q^j\le q^k\lVert e_0\rVert+\tau/(1-q) ∥ e k ∥ ≤ q k ∥ e 0 ∥ + τ ∑ j = 0 k − 1 q j ≤ q k ∥ e 0 ∥ + τ / ( 1 − q ) ▨
命題 7.2. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 R n \R^n R n ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ M n ( R ) M_n(\R) M n ( R ) A ∈ M n ( R ) A\in M_n(\R) A ∈ M n ( R ) P P P L ^ , U ^ ∈ M n ( R ) \widehat L,\widehat U\in M_n(\R) L , U ∈ M n ( R ) L ^ U ^ \widehat L\widehat U L U E : = P − 1 L ^ U ^ − A E:=P^{-1}\widehat L\widehat U-A E := P − 1 L U − A M : = ( L ^ U ^ ) − 1 P M:=(\widehat L\widehat U)^{-1}P M := ( L U ) − 1 P
A + E A+E A + E I − M A = ( A + E ) − 1 E I-MA=(A+E)^{-1}E I − M A = ( A + E ) − 1 E c : = ∥ A − 1 ∥ ∥ E ∥ < 1 c:=\lVert A^{-1}\rVert\lVert E\rVert<1 c := ∥ A − 1 ∥ ∥ E ∥ < 1 ∥ I − M A ∥ ≤ c / ( 1 − c ) \lVert I-MA\rVert\le c/(1-c) ∥ I − M A ∥ ≤ c / ( 1 − c ) R n \R^n R n ∥ ⋅ ∥ ∞ \lVert\cdot\rVert_\infty ∥ ⋅ ∥ ∞ A ∈ M n ( F ) A\in M_n(F) A ∈ M n ( F ) ( P , L ^ , U ^ ) (P,\widehat L,\widehat U) ( P , L , U ) 定理 3.3 の仮定と記号を満たすとする。ε : = γ n − 1 ∥ ∣ L ^ ∣ ∣ U ^ ∣ ∥ ∞ / ∥ A ∥ ∞ \varepsilon:=\gamma_{n-1}\bigl\lVert\lvert\widehat L\rvert\lvert\widehat U\rvert\bigr\rVert_\infty/\lVert A\rVert_\infty ε := γ n − 1 ∣ L ∣ ∣ U ∣ ∞ / ∥ A ∥ ∞ κ ∞ ( A ) ε < 1 \kappa_\infty(A)\varepsilon<1 κ ∞ ( A ) ε < 1 ∥ I − M A ∥ ∞ ≤ κ ∞ ( A ) ε / ( 1 − κ ∞ ( A ) ε ) \lVert I-MA\rVert_\infty\le\kappa_\infty(A)\varepsilon/(1-\kappa_\infty(A)\varepsilon) ∥ I − M A ∥ ∞ ≤ κ ∞ ( A ) ε / ( 1 − κ ∞ ( A ) ε ) v ∈ R n v\in\R^n v ∈ R n L ^ y = P v \widehat Ly=Pv L y = P v U ^ z = y \widehat Uz=y U z = y z z z M v Mv M v 証明. (1) を示す。A + E = P − 1 L ^ U ^ A+E=P^{-1}\widehat L\widehat U A + E = P − 1 L U I − M A = ( L ^ U ^ ) − 1 ( L ^ U ^ − P A ) = ( L ^ U ^ ) − 1 P E = ( P − 1 L ^ U ^ ) − 1 E = ( A + E ) − 1 E I-MA=(\widehat L\widehat U)^{-1}(\widehat L\widehat U-PA)=(\widehat L\widehat U)^{-1}PE=(P^{-1}\widehat L\widehat U)^{-1}E=(A+E)^{-1}E I − M A = ( L U ) − 1 ( L U − P A ) = ( L U ) − 1 P E = ( P − 1 L U ) − 1 E = ( A + E ) − 1 E
(2) を示す。v ∈ R n v\in\R^n v ∈ R n y : = ( I − M A ) v = ( A + E ) − 1 E v y:=(I-MA)v=(A+E)^{-1}Ev y := ( I − M A ) v = ( A + E ) − 1 E v ( A + E ) y = E v (A+E)y=Ev ( A + E ) y = E v y = A − 1 E ( v − y ) y=A^{-1}E(v-y) y = A − 1 E ( v − y ) §E20.2 補題 1.2 (1) により∥ y ∥ ≤ c ( ∥ v ∥ + ∥ y ∥ ) \lVert y\rVert\le c(\lVert v\rVert+\lVert y\rVert) ∥ y ∥ ≤ c (∥ v ∥ + ∥ y ∥) c < 1 c<1 c < 1 ∥ y ∥ ≤ c ∥ v ∥ / ( 1 − c ) \lVert y\rVert\le c\lVert v\rVert/(1-c) ∥ y ∥ ≤ c ∥ v ∥ / ( 1 − c )
(3) を示す。L ^ \widehat L L 1 1 1 U ^ \widehat U U 0 0 0 L ^ U ^ \widehat L\widehat U L U E = P − 1 Δ A E=P^{-1}\Delta A E = P − 1 Δ A ∣ E ∣ = P − 1 ∣ Δ A ∣ ≤ γ n − 1 P − 1 ∣ L ^ ∣ ∣ U ^ ∣ \lvert E\rvert=P^{-1}\lvert\Delta A\rvert\le\gamma_{n-1}P^{-1}\lvert\widehat L\rvert\lvert\widehat U\rvert ∣ E ∣ = P − 1 ∣ Δ A ∣ ≤ γ n − 1 P − 1 ∣ L ∣ ∣ U ∣ 補題 3.5 (2) と補題 3.5 (3) により∥ E ∥ ∞ ≤ ε ∥ A ∥ ∞ \lVert E\rVert_\infty\le\varepsilon\lVert A\rVert_\infty ∥ E ∥ ∞ ≤ ε ∥ A ∥ ∞ c ≤ κ ∞ ( A ) ε < 1 c\le\kappa_\infty(A)\varepsilon<1 c ≤ κ ∞ ( A ) ε < 1 t ↦ t / ( 1 − t ) t\mapsto t/(1-t) t ↦ t / ( 1 − t ) [ 0 , 1 ) [0,1) [ 0 , 1 ) (2) により評価が成り立つ。前進代入のy y y L ^ y = P v \widehat Ly=Pv L y = P v z z z U ^ z = y \widehat Uz=y U z = y z = ( L ^ U ^ ) − 1 P v = M v z=(\widehat L\widehat U)^{-1}Pv=Mv z = ( L U ) − 1 P v = M v ▨
系 7.3. F F F u u u fl \operatorname{fl} fl F F F n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 ( n + 1 ) u < 1 (n+1)u<1 ( n + 1 ) u < 1 γ n + 1 : = ( n + 1 ) u / ( 1 − ( n + 1 ) u ) \gamma_{n+1}:=(n+1)u/(1-(n+1)u) γ n + 1 := ( n + 1 ) u / ( 1 − ( n + 1 ) u ) A ∈ M n ( F ) A\in M_n(F) A ∈ M n ( F ) b , x ∈ F n b,x\in F^n b , x ∈ F n i i i b i b_i b i fl ( a i 1 ( − x 1 ) ) , … , fl ( a i n ( − x n ) ) \operatorname{fl}(a_{i1}(-x_1)),\dots,\operatorname{fl}(a_{in}(-x_n)) fl ( a i 1 ( − x 1 )) , … , fl ( a in ( − x n )) r ~ i \widetilde r_i r i 0 0 0 N max N_{\max} N m a x r : = b − A x r:=b-Ax r := b − A x i i i
∣ r ~ i − r i ∣ ≤ γ n + 1 ( ∣ b i ∣ + ∑ j = 1 n ∣ a i j ∣ ∣ x j ∣ ) \lvert\widetilde r_i-r_i\rvert\le\gamma_{n+1}\Bigl(\lvert b_i\rvert+\sum_{j=1}^n\lvert a_{ij}\rvert\lvert x_j\rvert\Bigr) ∣ r i − r i ∣ ≤ γ n + 1 ( ∣ b i ∣ + j = 1 ∑ n ∣ a ij ∣ ∣ x j ∣ ) が成り立ち、∥ r ~ − r ∥ ∞ ≤ γ n + 1 ( ∥ b ∥ ∞ + ∥ A ∥ ∞ ∥ x ∥ ∞ ) \lVert\widetilde r-r\rVert_\infty\le\gamma_{n+1}(\lVert b\rVert_\infty+\lVert A\rVert_\infty\lVert x\rVert_\infty) ∥ r − r ∥ ∞ ≤ γ n + 1 (∥ b ∥ ∞ + ∥ A ∥ ∞ ∥ x ∥ ∞ )
証明. F = − F F=-F F = − F − x j ∈ F -x_j\in F − x j ∈ F i i i j j j §E20.1 系 3.2 (1) または§E20.1 系 3.2 (2) により∣ ε j ∣ ≤ u \lvert\varepsilon_j\rvert\le u ∣ ε j ∣ ≤ u ε j \varepsilon_j ε j fl ( a i j ( − x j ) ) = − a i j x j ( 1 + ε j ) \operatorname{fl}(a_{ij}(-x_j))=-a_{ij}x_j(1+\varepsilon_j) fl ( a ij ( − x j )) = − a ij x j ( 1 + ε j ) r ~ i \widetilde r_i r i ( b i , fl ( a i 1 ( − x 1 ) ) , … , fl ( a i n ( − x n ) ) ) ∈ F n + 1 (b_i,\operatorname{fl}(a_{i1}(-x_1)),\dots,\operatorname{fl}(a_{in}(-x_n)))\in F^{n+1} ( b i , fl ( a i 1 ( − x 1 )) , … , fl ( a in ( − x n ))) ∈ F n + 1 §E20.3 系 1.4 (1) によりR n + 1 R_{n+1} R n + 1 1 1 1 n n n j + 1 j+1 j + 1 n − j + 1 n-j+1 n − j + 1 §E20.3 定理 1.3 (1) により、∣ δ j , l ∣ ≤ u \lvert\delta_{j,l}\rvert\le u ∣ δ j , l ∣ ≤ u δ j , l \delta_{j,l} δ j , l 0 ≤ j ≤ n 0\le j\le n 0 ≤ j ≤ n
r ~ i = b i ∏ l = 1 n ( 1 + δ 0 , l ) − ∑ j = 1 n a i j x j ( 1 + ε j ) ∏ l = 1 n − j + 1 ( 1 + δ j , l ) \widetilde r_i=b_i\prod_{l=1}^{n}(1+\delta_{0,l})-\sum_{j=1}^na_{ij}x_j(1+\varepsilon_j)\prod_{l=1}^{n-j+1}(1+\delta_{j,l}) r i = b i l = 1 ∏ n ( 1 + δ 0 , l ) − j = 1 ∑ n a ij x j ( 1 + ε j ) l = 1 ∏ n − j + 1 ( 1 + δ j , l ) である。b i b_i b i n n n a i j x j a_{ij}x_j a ij x j n − j + 2 ≤ n + 1 n-j+2\le n+1 n − j + 2 ≤ n + 1 ( n + 1 ) u < 1 (n+1)u<1 ( n + 1 ) u < 1 §E20.1 補題 4.1 とk ↦ k u / ( 1 − k u ) k\mapsto ku/(1-ku) k ↦ k u / ( 1 − k u ) ∣ θ j ∣ ≤ γ n + 1 \lvert\theta_j\rvert\le\gamma_{n+1} ∣ θ j ∣ ≤ γ n + 1 0 ≤ j ≤ n 0\le j\le n 0 ≤ j ≤ n θ 0 , … , θ n \theta_0,\dots,\theta_n θ 0 , … , θ n r ~ i = b i ( 1 + θ 0 ) − ∑ j = 1 n a i j x j ( 1 + θ j ) \widetilde r_i=b_i(1+\theta_0)-\sum_{j=1}^na_{ij}x_j(1+\theta_j) r i = b i ( 1 + θ 0 ) − ∑ j = 1 n a ij x j ( 1 + θ j ) r i = b i − ∑ j a i j x j r_i=b_i-\sum_ja_{ij}x_j r i = b i − ∑ j a ij x j ∣ r ~ i − r i ∣ ≤ γ n + 1 ( ∣ b i ∣ + ∑ j ∣ a i j ∣ ∣ x j ∣ ) \lvert\widetilde r_i-r_i\rvert\le\gamma_{n+1}(\lvert b_i\rvert+\sum_j\lvert a_{ij}\rvert\lvert x_j\rvert) ∣ r i − r i ∣ ≤ γ n + 1 (∣ b i ∣ + ∑ j ∣ a ij ∣ ∣ x j ∣) 補題 3.5 (1) によりmax i ∑ j ∣ a i j ∣ ∣ x j ∣ ≤ ∥ A ∥ ∞ ∥ x ∥ ∞ \max_i\sum_j\lvert a_{ij}\rvert\lvert x_j\rvert\le\lVert A\rVert_\infty\lVert x\rVert_\infty max i ∑ j ∣ a ij ∣ ∣ x j ∣ ≤ ∥ A ∥ ∞ ∥ x ∥ ∞ ▨
例 7.4. F ℓ : = F ( 2 , 24 , − 126 , 127 ) F_\ell:=F(2,24,-126,127) F ℓ := F ( 2 , 24 , − 126 , 127 ) F h : = F ( 2 , 53 , − 1022 , 1023 ) F_h:=F(2,53,-1022,1023) F h := F ( 2 , 53 , − 1022 , 1023 ) fl ℓ \operatorname{fl}_\ell fl ℓ fl h \operatorname{fl}_h fl h u ℓ = 2 − 24 ≈ 5.96 × 10 − 8 u_\ell=2^{-24}\approx5.96\times10^{-8} u ℓ = 2 − 24 ≈ 5.96 × 1 0 − 8 u h = 2 − 53 u_h=2^{-53} u h = 2 − 53 F ℓ F_\ell F ℓ 0 0 0 m 2 e m2^{e} m 2 e m , e ∈ Z m,e\in\Z m , e ∈ Z 1 ≤ ∣ m ∣ < 2 24 1\le\lvert m\rvert<2^{24} 1 ≤ ∣ m ∣ < 2 24 − 149 ≤ e ≤ 104 -149\le e\le104 − 149 ≤ e ≤ 104 F h F_h F h s e + 52 = 2 e s_{e+52}=2^{e} s e + 52 = 2 e §E20.1 補題 1.3 (1) を適用してF ℓ ⊂ F h F_\ell\subset F_h F ℓ ⊂ F h n ∈ { 4 , 6 , 8 } n\in\{4,6,8\} n ∈ { 4 , 6 , 8 } A : = ( fl ℓ ( 1 / ( i + j − 1 ) ) ) 1 ≤ i , j ≤ n ∈ M n ( F ℓ ) A:=\bigl(\operatorname{fl}_\ell(1/(i+j-1))\bigr)_{1\le i,j\le n}\in M_n(F_\ell) A := ( fl ℓ ( 1/ ( i + j − 1 )) ) 1 ≤ i , j ≤ n ∈ M n ( F ℓ ) b : = ( 1 , … , 1 ) ∈ F ℓ n b:=(1,\dots,1)\in F_\ell^n b := ( 1 , … , 1 ) ∈ F ℓ n x : = A − 1 b x:=A^{-1}b x := A − 1 b A A A F ℓ F_\ell F ℓ fl ℓ \operatorname{fl}_\ell fl ℓ ( P , L ^ , U ^ ) (P,\widehat L,\widehat U) ( P , L , U ) M : = ( L ^ U ^ ) − 1 P M:=(\widehat L\widehat U)^{-1}P M := ( L U ) − 1 P q : = ∥ I − M A ∥ ∞ q:=\lVert I-MA\rVert_\infty q := ∥ I − M A ∥ ∞ x 0 : = 0 x_0:=0 x 0 := 0 k ≥ 0 k\ge0 k ≥ 0
b b b A A A x k x_k x k 系 7.3 のr ~ \widetilde r r fl ℓ \operatorname{fl}_\ell fl ℓ r ^ k ∈ F ℓ n \widehat r_k\in F_\ell^n r k ∈ F ℓ n r ~ \widetilde r r F h F_h F h fl h \operatorname{fl}_h fl h F ℓ F_\ell F ℓ fl ℓ \operatorname{fl}_\ell fl ℓ L ^ y = P r ^ k \widehat Ly=P\widehat r_k L y = P r k U ^ z = y \widehat Uz=y U z = y F ℓ F_\ell F ℓ fl ℓ \operatorname{fl}_\ell fl ℓ d ^ k \widehat d_k d k x k + 1 : = ( fl ℓ ( x k , i + d ^ k , i ) ) 1 ≤ i ≤ n x_{k+1}:=\bigl(\operatorname{fl}_\ell(x_{k,i}+\widehat d_{k,i})\bigr)_{1\le i\le n} x k + 1 := ( fl ℓ ( x k , i + d k , i ) ) 1 ≤ i ≤ n 二通りの計算は残差の算法を実行する数系だけが異なり、P P P L ^ \widehat L L U ^ \widehat U U M M M q q q x 1 x_1 x 1 命題 7.2 (3) によりM r ^ k M\widehat r_k M r k (2) の代入を厳密算術で実行した値に等しい。命題 7.1 (2) をこのM M M ( x k ) (x_k) ( x k ) ( r ^ k ) (\widehat r_k) ( r k ) η k = r ^ k − ( b − A x k ) \eta_k=\widehat r_k-(b-Ax_k) η k = r k − ( b − A x k ) ρ k = x k + 1 − x k − M r ^ k \rho_k=x_{k+1}-x_k-M\widehat r_k ρ k = x k + 1 − x k − M r k (2) と(3) の丸めによる差である。
有理数による厳密な模擬計算で、すべての浮動小数点算術の実行が範囲条件を満たすことを確かめ、次の値を得た。κ ∞ ( A ) \kappa_\infty(A) κ ∞ ( A ) q q q n = 4 n=4 n = 4 2.84 × 10 4 2.84\times10^4 2.84 × 1 0 4 1.96 × 10 − 5 1.96\times10^{-5} 1.96 × 1 0 − 5 n = 6 n=6 n = 6 2.81 × 10 7 2.81\times10^7 2.81 × 1 0 7 7.72 × 10 − 2 7.72\times10^{-2} 7.72 × 1 0 − 2 n = 8 n=8 n = 8 3.30 × 10 9 3.30\times10^9 3.30 × 1 0 9 1.69 1.69 1.69 ∥ x − x k ∥ ∞ / ∥ x ∥ ∞ \lVert x-x_k\rVert_\infty/\lVert x\rVert_\infty ∥ x − x k ∥ ∞ / ∥ x ∥ ∞
n n n r ~ \widetilde r r k = 1 k=1 k = 1 k = 2 k=2 k = 2 k = 3 k=3 k = 3 k = 4 k=4 k = 4 k = 8 k=8 k = 8
4 4 4 F h F_h F h 1.7 × 10 − 5 1.7\times10^{-5} 1.7 × 1 0 − 5 7.8 × 10 − 9 7.8\times10^{-9} 7.8 × 1 0 − 9 7.8 × 10 − 9 7.8\times10^{-9} 7.8 × 1 0 − 9 7.8 × 10 − 9 7.8\times10^{-9} 7.8 × 1 0 − 9 7.8 × 10 − 9 7.8\times10^{-9} 7.8 × 1 0 − 9
4 4 4 F ℓ F_\ell F ℓ 1.7 × 10 − 5 1.7\times10^{-5} 1.7 × 1 0 − 5 4.6 × 10 − 5 4.6\times10^{-5} 4.6 × 1 0 − 5 2.2 × 10 − 5 2.2\times10^{-5} 2.2 × 1 0 − 5 4.6 × 10 − 5 4.6\times10^{-5} 4.6 × 1 0 − 5 4.6 × 10 − 5 4.6\times10^{-5} 4.6 × 1 0 − 5
6 6 6 F h F_h F h 1.4 × 10 − 2 1.4\times10^{-2} 1.4 × 1 0 − 2 1.7 × 10 − 4 1.7\times10^{-4} 1.7 × 1 0 − 4 2.1 × 10 − 6 2.1\times10^{-6} 2.1 × 1 0 − 6 3.0 × 10 − 8 3.0\times10^{-8} 3.0 × 1 0 − 8 3.0 × 10 − 8 3.0\times10^{-8} 3.0 × 1 0 − 8
6 6 6 F ℓ F_\ell F ℓ 1.4 × 10 − 2 1.4\times10^{-2} 1.4 × 1 0 − 2 5.4 × 10 − 2 5.4\times10^{-2} 5.4 × 1 0 − 2 1.6 × 10 − 2 1.6\times10^{-2} 1.6 × 1 0 − 2 8.6 × 10 − 3 8.6\times10^{-3} 8.6 × 1 0 − 3 3.6 × 10 − 2 3.6\times10^{-2} 3.6 × 1 0 − 2
8 8 8 F h F_h F h 5.5 × 10 − 1 5.5\times10^{-1} 5.5 × 1 0 − 1 5.9 × 10 − 1 5.9\times10^{-1} 5.9 × 1 0 − 1 4.6 × 10 − 1 4.6\times10^{-1} 4.6 × 1 0 − 1 4.3 × 10 − 1 4.3\times10^{-1} 4.3 × 1 0 − 1 2.4 × 10 − 1 2.4\times10^{-1} 2.4 × 1 0 − 1
8 8 8 F ℓ F_\ell F ℓ 5.5 × 10 − 1 5.5\times10^{-1} 5.5 × 1 0 − 1 8.3 × 10 − 1 8.3\times10^{-1} 8.3 × 1 0 − 1 5.6 × 10 − 1 5.6\times10^{-1} 5.6 × 1 0 − 1 3.2 × 10 − 1 3.2\times10^{-1} 3.2 × 1 0 − 1 5.6 × 10 − 1 5.6\times10^{-1} 5.6 × 1 0 − 1
n = 4 , 6 n=4,6 n = 4 , 6 q < 1 q<1 q < 1 1 ≤ k ≤ 7 1\le k\le7 1 ≤ k ≤ 7 r ~ \widetilde r r F h F_h F h ∥ M ∥ ∞ ∥ η k ∥ ∞ / ∥ x ∥ ∞ ≤ 9.0 × 10 − 10 \lVert M\rVert_\infty\lVert\eta_k\rVert_\infty/\lVert x\rVert_\infty\le9.0\times10^{-10} ∥ M ∥ ∞ ∥ η k ∥ ∞ / ∥ x ∥ ∞ ≤ 9.0 × 1 0 − 10 ∥ ρ k ∥ ∞ / ∥ x ∥ ∞ ≤ 3.2 × 10 − 8 \lVert\rho_k\rVert_\infty/\lVert x\rVert_\infty\le3.2\times10^{-8} ∥ ρ k ∥ ∞ / ∥ x ∥ ∞ ≤ 3.2 × 1 0 − 8 n = 4 n=4 n = 4 7.8 × 10 − 9 ≈ 0.13 u ℓ 7.8\times10^{-9}\approx0.13u_\ell 7.8 × 1 0 − 9 ≈ 0.13 u ℓ n = 6 n=6 n = 6 3.0 × 10 − 8 ≈ 0.50 u ℓ 3.0\times10^{-8}\approx0.50u_\ell 3.0 × 1 0 − 8 ≈ 0.50 u ℓ r ~ \widetilde r r F ℓ F_\ell F ℓ ∥ M ∥ ∞ ∥ η k ∥ ∞ / ∥ x ∥ ∞ \lVert M\rVert_\infty\lVert\eta_k\rVert_\infty/\lVert x\rVert_\infty ∥ M ∥ ∞ ∥ η k ∥ ∞ / ∥ x ∥ ∞ n = 4 n=4 n = 4 1.3 × 10 − 4 1.3\times10^{-4} 1.3 × 1 0 − 4 n = 6 n=6 n = 6 7.8 × 10 − 2 7.8\times10^{-2} 7.8 × 1 0 − 2 1.8 × 10 − 1 1.8\times10^{-1} 1.8 × 1 0 − 1 k ≥ 2 k\ge2 k ≥ 2 n = 4 n=4 n = 4 2.2 × 10 − 5 2.2\times10^{-5} 2.2 × 1 0 − 5 n = 6 n=6 n = 6 2.3 × 10 − 3 2.3\times10^{-3} 2.3 × 1 0 − 3 n = 8 n=8 n = 8 q > 1 q>1 q > 1 命題 7.1 (3) は適用されない。r ~ \widetilde r r F h F_h F h x 8 x_8 x 8 0.24 0.24 0.24
8 演習 解答. 段k k k 1 ≤ k ≤ n − 1 1\le k\le n-1 1 ≤ k ≤ n − 1 i > k i>k i > k 1 1 1 i , j > k i,j>k i , j > k 1 1 1 n n n ∑ k = 1 n − 1 ( n − k ) = n ( n − 1 ) / 2 \sum_{k=1}^{n-1}(n-k)=n(n-1)/2 ∑ k = 1 n − 1 ( n − k ) = n ( n − 1 ) /2 ∑ k = 1 n − 1 ( n − k ) 2 = ∑ m = 1 n − 1 m 2 = ( n − 1 ) n ( 2 n − 1 ) / 6 \sum_{k=1}^{n-1}(n-k)^2=\sum_{m=1}^{n-1}m^2=(n-1)n(2n-1)/6 ∑ k = 1 n − 1 ( n − k ) 2 = ∑ m = 1 n − 1 m 2 = ( n − 1 ) n ( 2 n − 1 ) /6
n ( n − 1 ) 2 + ( n − 1 ) n ( 2 n − 1 ) 3 = 2 n 3 3 − n 2 2 − n 6 \frac{n(n-1)}{2}+\frac{(n-1)n(2n-1)}{3}=\frac{2n^3}{3}-\frac{n^2}{2}-\frac n6 2 n ( n − 1 ) + 3 ( n − 1 ) n ( 2 n − 1 ) = 3 2 n 3 − 2 n 2 − 6 n である。L L L 1 1 1 L y = P b Ly=Pb L y = P b i i i i − 1 i-1 i − 1 ∑ i = 1 n 2 ( i − 1 ) = n ( n − 1 ) \sum_{i=1}^n2(i-1)=n(n-1) ∑ i = 1 n 2 ( i − 1 ) = n ( n − 1 ) P b Pb P b U x = y Ux=y U x = y i i i n − i n-i n − i 1 1 1 ∑ i = 1 n ( 2 ( n − i ) + 1 ) = n 2 \sum_{i=1}^n(2(n-i)+1)=n^2 ∑ i = 1 n ( 2 ( n − i ) + 1 ) = n 2 2 n 2 − n 2n^2-n 2 n 2 − n ▨
問題 8.2. 定理 5.2 (5) の式による計算がn 3 / 3 + n 2 / 2 − 5 n / 6 n^3/3+n^2/2-5n/6 n 3 /3 + n 2 /2 − 5 n /6 n n n
解答. 第j j j c j j c_{jj} c j j j − 1 j-1 j − 1 1 1 1 i > j i>j i > j c i j c_{ij} c ij j − 1 j-1 j − 1 1 1 1
∑ j = 1 n ( 2 ( j − 1 ) + ( n − j ) ( 2 j − 1 ) ) = n ( n − 1 ) + ( n 3 3 − n 2 2 + n 6 ) = n 3 3 + n 2 2 − 5 n 6 \sum_{j=1}^n\bigl(2(j-1)+(n-j)(2j-1)\bigr)=n(n-1)+\Bigl(\frac{n^3}{3}-\frac{n^2}{2}+\frac n6\Bigr)=\frac{n^3}{3}+\frac{n^2}{2}-\frac{5n}{6} j = 1 ∑ n ( 2 ( j − 1 ) + ( n − j ) ( 2 j − 1 ) ) = n ( n − 1 ) + ( 3 n 3 − 2 n 2 + 6 n ) = 3 n 3 + 2 n 2 − 6 5 n である。ここで∑ j = 1 n ( n − j ) ( 2 j − 1 ) = 2 n ∑ j j − n 2 − 2 ∑ j j 2 + ∑ j j = n 2 ( n + 1 ) − n 2 − n ( n + 1 ) ( 2 n + 1 ) / 3 + n ( n + 1 ) / 2 = n 3 / 3 − n 2 / 2 + n / 6 \sum_{j=1}^n(n-j)(2j-1)=2n\sum_jj-n^2-2\sum_jj^2+\sum_jj=n^2(n+1)-n^2-n(n+1)(2n+1)/3+n(n+1)/2=n^3/3-n^2/2+n/6 ∑ j = 1 n ( n − j ) ( 2 j − 1 ) = 2 n ∑ j j − n 2 − 2 ∑ j j 2 + ∑ j j = n 2 ( n + 1 ) − n 2 − n ( n + 1 ) ( 2 n + 1 ) /3 + n ( n + 1 ) /2 = n 3 /3 − n 2 /2 + n /6 1 1 1 n n n ▨
問題 8.3. n ∈ N ≥ 1 n\in\NN n ∈ N ≥ 1 A ∈ M n ( R ) A\in M_n(\R) A ∈ M n ( R ) j j j ∣ a j j ∣ ≥ ∑ i ≠ j ∣ a i j ∣ \lvert a_{jj}\rvert\ge\sum_{i\ne j}\lvert a_{ij}\rvert ∣ a j j ∣ ≥ ∑ i = j ∣ a ij ∣ A A A r k = k r_k=k r k = k 2 2 2
解答. 定理 2.5 (1) により消去はどの段でも失敗しない。段k k k W ( k ) W^{(k)} W ( k ) 1 , … , k − 1 1,\dots,k-1 1 , … , k − 1 r m = m r_m=m r m = m j ≥ k j\ge k j ≥ k ∣ w j j ( k ) ∣ ≥ ∑ i ≥ k , i ≠ j ∣ w i j ( k ) ∣ \lvert w^{(k)}_{jj}\rvert\ge\sum_{i\ge k,\,i\ne j}\lvert w^{(k)}_{ij}\rvert ∣ w j j ( k ) ∣ ≥ ∑ i ≥ k , i = j ∣ w ij ( k ) ∣ j ≥ k j\ge k j ≥ k ∑ i ≥ k ∣ w i j ( k ) ∣ ≤ ∑ i = 1 n ∣ a i j ∣ \sum_{i\ge k}\lvert w^{(k)}_{ij}\rvert\le\sum_{i=1}^n\lvert a_{ij}\rvert ∑ i ≥ k ∣ w ij ( k ) ∣ ≤ ∑ i = 1 n ∣ a ij ∣ k = 1 k=1 k = 1 k < n k<n k < n j = k j=k j = k i > k i>k i > k ∣ w k k ( k ) ∣ ≥ ∣ w i k ( k ) ∣ \lvert w^{(k)}_{kk}\rvert\ge\lvert w^{(k)}_{ik}\rvert ∣ w k k ( k ) ∣ ≥ ∣ w ik ( k ) ∣ r k = k r_k=k r k = k V ( k ) = W ( k ) V^{(k)}=W^{(k)} V ( k ) = W ( k ) k k k l i : = w i k ( k ) / w k k ( k ) l_i:=w^{(k)}_{ik}/w^{(k)}_{kk} l i := w ik ( k ) / w k k ( k ) i > k i>k i > k ∑ i > k ∣ l i ∣ ≤ 1 \sum_{i>k}\lvert l_i\rvert\le1 ∑ i > k ∣ l i ∣ ≤ 1 j > k j>k j > k w i j ( k + 1 ) = w i j ( k ) − l i w k j ( k ) w^{(k+1)}_{ij}=w^{(k)}_{ij}-l_iw^{(k)}_{kj} w ij ( k + 1 ) = w ij ( k ) − l i w k j ( k ) i > k i>k i > k
∑ i > k ∣ w i j ( k + 1 ) ∣ ≤ ∑ i > k ∣ w i j ( k ) ∣ + ∣ w k j ( k ) ∣ ∑ i > k ∣ l i ∣ ≤ ∑ i ≥ k ∣ w i j ( k ) ∣ \sum_{i>k}\lvert w^{(k+1)}_{ij}\rvert\le\sum_{i>k}\lvert w^{(k)}_{ij}\rvert+\lvert w^{(k)}_{kj}\rvert\sum_{i>k}\lvert l_i\rvert\le\sum_{i\ge k}\lvert w^{(k)}_{ij}\rvert i > k ∑ ∣ w ij ( k + 1 ) ∣ ≤ i > k ∑ ∣ w ij ( k ) ∣ + ∣ w k j ( k ) ∣ i > k ∑ ∣ l i ∣ ≤ i ≥ k ∑ ∣ w ij ( k ) ∣ であり、(b) から段k + 1 k+1 k + 1
∑ i > k , i ≠ j ∣ w i j ( k + 1 ) ∣ ≤ ∑ i > k , i ≠ j ∣ w i j ( k ) ∣ + ∣ w k j ( k ) ∣ ( 1 − ∣ l j ∣ ) = ∑ i ≥ k , i ≠ j ∣ w i j ( k ) ∣ − ∣ l j ∣ ∣ w k j ( k ) ∣ \sum_{i>k,\,i\ne j}\lvert w^{(k+1)}_{ij}\rvert\le\sum_{i>k,\,i\ne j}\lvert w^{(k)}_{ij}\rvert+\lvert w^{(k)}_{kj}\rvert(1-\lvert l_j\rvert)=\sum_{i\ge k,\,i\ne j}\lvert w^{(k)}_{ij}\rvert-\lvert l_j\rvert\lvert w^{(k)}_{kj}\rvert i > k , i = j ∑ ∣ w ij ( k + 1 ) ∣ ≤ i > k , i = j ∑ ∣ w ij ( k ) ∣ + ∣ w k j ( k ) ∣ ( 1 − ∣ l j ∣) = i ≥ k , i = j ∑ ∣ w ij ( k ) ∣ − ∣ l j ∣ ∣ w k j ( k ) ∣ であり、段k k k ∣ w j j ( k ) ∣ − ∣ l j ∣ ∣ w k j ( k ) ∣ ≤ ∣ w j j ( k + 1 ) ∣ \lvert w^{(k)}_{jj}\rvert-\lvert l_j\rvert\lvert w^{(k)}_{kj}\rvert\le\lvert w^{(k+1)}_{jj}\rvert ∣ w j j ( k ) ∣ − ∣ l j ∣ ∣ w k j ( k ) ∣ ≤ ∣ w j j ( k + 1 ) ∣ k + 1 k+1 k + 1 k k k k k k w i j ( k ) w^{(k)}_{ij} w ij ( k ) i , j ≥ k i,j\ge k i , j ≥ k ∣ w i j ( k ) ∣ ≤ ∑ i ′ = 1 n ∣ a i ′ j ∣ ≤ 2 ∣ a j j ∣ ≤ 2 max p , q ∣ a p q ∣ \lvert w^{(k)}_{ij}\rvert\le\sum_{i'=1}^n\lvert a_{i'j}\rvert\le2\lvert a_{jj}\rvert\le2\max_{p,q}\lvert a_{pq}\rvert ∣ w ij ( k ) ∣ ≤ ∑ i ′ = 1 n ∣ a i ′ j ∣ ≤ 2 ∣ a j j ∣ ≤ 2 max p , q ∣ a pq ∣ 2 2 2 ▨