9 8 m n mn N.J.Nigham, Accuracy and Stability of Numerical Algorithms 2nd ed., (SIAM) x x = x2 + y 2 = x + y = max( x, y ) x y x () (norm) (condition number) 8. R C a, b C a b 0 a, b a = a 0 0 0 n C n R n
92 8 8.. ( ) a C n ( R n ) R a R C n. a C n (or R n ) a 0 2. α C( R ) a C n αa = α a 3. a, b C n a + b a + b ( ) p 8..2 (p ) a = [a a n ] T C n p n a p = a i p i= /p p =, 2,, 2 ( ), a = n a i n a 2 = a i 2 = (a, a) i= i= a = max i a i x = [x x 2 ] T R 2 8. (= ) x, x 2,..., x k,... C n R n lim k x k p = a p
8.. 93 x 2 x - x x = x 2 = - x = 8.: x = x 2 = x = lim k x k q = p q x C n x p α pq x q α pq 0 3 α pq 8. 8.: α pq p 2 q n n 2 n p 8..3 ( p ) A M n (C)( M n (R) ) p p Ax p A p = sup x 0 x p
94 8 Ax A = sup = max x 0 x j Ax 2 A 2 = sup x 0 x 2 Ax A = sup = max x 0 x i n a i j i= = max λ i (A A) ( λ i (A) A ) i n p p A M n (C) x C n j= a i j Ax p A p x p A, B M n (C) AB p A p B p C n M n (C) R n M n (R) 8..4 ( ) a R n ã R n E(ã) = a ã (8.) ã re(ã) = a ã = E(ã) a a (a 0) a ã = E(ã) (a = 0) (8.2) ã p E p (ã) = a ã p, re p (ã) = E p(ã) a p A M n (R) Ã M n (R) E(Ã), E p (Ã), re(ã), re p (Ã)
8.2. 95 8..5 ( ) A M n (R) κ(a) κ(a) = A A p κ p (A) κ(a) A (ill-conditioned) 8.. A M 2 (R) κ (A) κ (A) A = 0 2 8.2 (7.) (7.) Ã x = b x E( x) 8.2. ( b ) A(x + E( x)) = b + E( b) re( x) κ(a) re( b) ( ) E( x) = A E( b) E( x) A E( b) b A x ( )
96 8 8.2.2 ( A ) (A + E(Ã))(x + E( x)) = b E( x) κ(a) re(ã) x + E( x) ( ) x = A b = A (A + E(Ã))(x + E( x)) = x + E( x) + A E(Ã)(x + E( x)) E( x) = A E(Ã)(x + E( x)) E( x) A E(Ã) x + E( x) = A A E(Ã) A x + E( x) ( ) 8.2.3 () (A + E(Ã))(x + E( x)) = b + E( b) A E(Ã) < κ(a) ( re( x) re( b) + re(ã) ) A E(Ã) ( ) I + A E(Ã) + λ(a E(Ã)) λ(a E(Ã)) (I + A E(Ã)) = I A E(Ã)(I + A E(Ã)) (I + A E(Ã)) + A E(Ã) (I + A E(Ã)) (I + A E(Ã)) ( A E(Ã) ) (I + A E(Ã)) A E(Ã)
8.2. 97 (A + E(Ã))(x + E( x)) = b + E( b) Ax = b A E( x) E(Ã)x + (A + E(Ã))E( x) = E( b) A E(Ã)x + (I + A E(Ã))E( x) = A E( b) E( x) = (I + A E(Ã)) A (E(Ã)x E( b)) E( x) x (I + A E(Ã)) A E(Ã) + E( b) x A E(Ã) + E( b) A E(Ã) b x A b ( ) A A re( x) κ(a) E(Ã) A (re(ã) + re( b) ) (8.3). re( x) κ(a) re( b) 2. E( x) κ(a) re(ã) x + E( x) 3. κ(a) ( re( x) re( b) + re(ã) ) A E(Ã) 2. E( x) x E( x) > x E( x) x + E( x)
98 8 3. E(Ã) / A < log 0 (κ(a)) + max(ã, b) (8.4) Ã b + log 0 n 3 Wilkinson 8.3 Hilbert Wilkinson[42] SparcStation IPX Sun Fortran( 2 24 ) 8.3. Courant-Fischer(Min-Max) Weyl 8.3. (Weyl ) A, B : n n Hermite, λ i (A) : A i (λ (A) λ 2 (A) λ n (A)) λ i (A) + λ (B) λ i (A + B) λ i (A) + λ n (B) (i =, 2,, n) (8.5) Wilkinson [42](p.0 p.02) B A b i j ε (i, j =, 2,, n) (8.6) λ i (B) nε (i =, 2,, n) (8.7)
8.3. Hilbert 99 Rayleigh-Ritz λ i (A + B) λ i (A) nε (i =, 2,, n) (8.8) n 8.3.2 Hilbert A = 2. n = [a i j ] 2 n 3 n+.. n+ 2n a i j = i+ j. 2 24 2. 2 53 4 2 3 2 Table Hilbert (Dimension:0) 0.75920E + 0 0.7599670265775E + 0 0.945007773E 07 2 0.3429295E + 00 0.34292954848350908E + 00 0.364589606E 07 3 0.357483E 0 0.35748627639246E 0 0.8359224E 07 4 0.2530897E 02 0.25308907686700395E 02 0.645588386E 08 5 0.287263E 03 0.287496427636959E 03 0.233577239E 07 6 0.4739574E 05 0.472968929384492E 05 0.988459762E 08 7 0.260786E 06 0.2289677387895489E 06 0.388020E 08 8 0.2996E 07 0.24743888628759E 08 0.320635455E 07 9 0.3893632E 07 0.22667468977874495E 0 0.38936475E 07 0 0.20689E 07 0.09309587263586E 2 0.20680775E 07 Hilbert (8.6) ε ε 0.39736 0 7 (8.9)
00 8 n ε 0.39736 0 6 (8.8) 4 QR ( ) Table 2 Hilbert (Dimension:0) 4.75903E +.7599575764398E +.75995757644005265046698972405E + 2.3429263E + 0.3429295202454800E + 0.3429295202454838333243449462269E + 0 3.357406E.3574834630860338E.35748346308606843928879039309898E 4.25304E 2.25308972245537668E 2.2530897224553907639524862478389967E 2 5.286942E 3.2872625655238820E 3.28726256552406739468549549803E 3 6.4697030E 5.473957389084527E 5.4739573890825403879227082233544E 5 7.872392E 6.2607857589827829E 6.2607857589234694322830850406264E 6 8.476993E 7.299606699545878E 7.299606703302573389364483930E 7 9.46460E 7.389363502525424E 7.389363502537948889724969006644E 7 0.36074E 7.206886899426792E 7.2068868944346767284476423905832E 7 order 8.3.2 Hilbert order Dimension 4 Hilbert Table 3 Hilbert Dimension κ 2 ( ) κ 2 ( ) κ 2 (4 ) 5 0.4737947E+06 0.4766073E+06 0.4766073E+06 0 0.868655E+08 0.60274E+4 0.602629E+4 5 0.326038E+0 0.246449E+20 0.66566E+2 20 0.8902582E+0 0.405365E+9 0.245256E+29 Dimension ε
8.3. Hilbert 0 Table 4 4.796.766 26.732 2 0.39 0.436 25.603 3 0.450 9.728 25.05 4 0.889 9.733 25.279 5 0.856 9.06 25.3 6 0.69 8.687 26.768 7.00 8.860 25.305 8 0.09 9.33 25.485 9 0.789 9.083 27.335 0 0.44 9.654 25.467 log 0 () Hilbert 4 ( 0 ) x i = i (i =, 2,, 0) b i = 0 j= a i j j 4 (0 +8 ). order 2. 3.. A A = 3 0 3 0 3 (a) A () 3 A = 2 3 (2) 3 3 (3) (b) κ (A), κ (A) 2. a, b C
02 8 3.,, ( ) 4. A M n (R) A / A 5. A κ 2 (A) = max i λ i (A) min i λ i (A) λ i (A) (i =, 2,..., n) A 6. A M n (R) Frobenius A F A F = n n a i j 2 (8.0) i= j=