Учебная книга: Вычислительные методы линейной алгебры A x = b, A m {Ab } {Ab } A m {Ab } A m = 2 a 11x 1 + a 12x 2 = b 1 a 21x 1 + a 22x 2 = b 2 5x 1 + 7x 2 = 12, 7x 1 + 10x 2 = 17, x 1 = 1 x 2 = 1 F t = 2 β = 10 t F β F x 1 = 2. 4 x 2 = 0 12 16. 8 0 0. 2 1. 4 −1 F x 1 = 2. 4 x 2 = 0 F x ∈ R m A m × m , kA k kA k > 0 A 6= 0 kA k = 0 ⇔ A = 0 m × m kA k kA kα kx kα kA kβ kx kα = kx kβ E E Ax = b ∆A b A A + ∆A x ∗ . , . (A + ∆A )−1 − A −1 = A −1 A (A + ∆A )−1 − A −1 (A + ∆A ) (A + ∆A )−1 = = A −1 (A − (A + ∆A )) (A + ∆A )−1 = −A −1 ∆A (A + ∆A )−1 . δ (x ) 6 cond(A )k∆A k/ kA k δ (x ) 6 cond( , cond(A ) = kA −1 k kA k k∆A k → 0 cond(A ) = kA −1 k kA k t t O (2−t ) O (2t/ 2) O (2−t/ 2) cond(A ) = kA −1 k kA k cond(A ) ≥ 1 A A −1 = E ⇒ 1 = kE k = kA A −1 k > kA k kA −1 k = cond(A ) cond(c A ) = cond(A ) c cond(A B ) 6 cond(A ) cond(B ) cond(A −1 ) = cond(A ) max dii cond( D D = diag(dii ) 16i 6m cond(A ) = kA k2 kA −1 k2 cond(A ) A = A ∗ > 0 i = 1,...,m R m , . b . εi λl A−1 A −1 ε “ δ A x = b, x a ij aij = 0 i > j (i < j ) U U T U −1 U T U = UU T = E |det(U )| = 1 1 = det(E ) = det(UU T ) = det(U ) det(U T ) = det2 (U ) 1 Pij i j i j P 24 5 × 5 0 0 0 1 0  0 A 0 A i j A 24  1 0 0 0 0  P =0 0 1 0 0 0 1 0 0 0 Pij Qij (ϕ ) i j Q 24 (ϕ ) 5 × 5 24 1 0 0 0 0   0 cosϕ 0 −sinϕ 0 Q (ϕ ) =0 0 1 0 0 0 sinϕ 0 cosϕ 0 0 0 0 0 1 Qij P m v 1 > 0, e = (1, 0,..., 0)T v 1 < 0. , u = v −σ kv ke P . u 1 u P y = αu + βs Aij aij = 0 i > j + 1(i < j − 1) “ “ , α = 1. 2. 3 x 1 + 0. 99 x 2 = 1. 99, 0. 99 x 1 + 0. 98x 2 = 1. 97, x 1 = 1 x 2 = 1 x 1 = 3 x 2 = −1. 0203 A = L U L U L Ux = b. , . LU Ly = b l 11y 1 = b 1 , l 21y 1+ l 22y 2 = b 2 , ... ... ... ... ... ... ..., l m −1, 1y 1+ l m −1, 2y 2+ ... + ... + l m −1,m −1y m −1 = b m −1, l m 1y 1+ l m 2y 2+ ... + ... + l m,m − 1y m − 1+ l mm y m = bm . y 1 = b 1/l 11 yi Ux = y u 11x 1+ u 12x 2+ u 13x 3+ ... + ... + u 1m x m = y 1, u 21x 2+ u 23x 3+ ... + ... + u 2m x m = y 2, ... ... ... ..., u m −1,m −1x m −1+ u mm x m = y m −1 u mm x m = y m . x m = y m /u mm . Q R QR A QRx = b, Rx = Q T b. m × m , Am . l mm u mm Am LDU U l ii = 1 u ii = 1 D A = LU A = LDU uii = 1 lii = 1 A = L 1D 1U 1 A = L 2D 2U 2 L 1D 1U 1 = L 2D 2U 2 U 1U 2−1 = D 1−1L −1 1L 2D 2 U 1U 2−1 D 1−1L −1 1L 2D 2 U 1 U 2 U 1U 2−1 = D = E ⇒ U 1 = U 2 D 1−1L −1 1L 2D 2 = E L −1 1L 2 = D 1D 2−1 L 1 L 2 L −1 1L 2 = E ⇒ L 1 = L 2 D 1 = D 2  a 11 a 12 ... ... ... ... a 1m  a 21 a 22 ... ... ... ... a 2m A... ... ... ... ... ... ... ... ... ... ... ... ... ... =  a m −1, 1 a m −1, 2 ... ... ... ... a m −1,m   am 1 am 2 ... ... ... ... amm   1 a (1) 1222 ... ... ... ... a 1(1) 2mm   0 a (1) ... ... ... ... a (1) A (1) = L 1 D 1 A =... ... ... ... ... ... ... , ... ... ... ... ... ... ...  0 a (1)m −1, 2 ... ... ... ... a (1)m − 1,m   0 a m (1) 2 ... ... ... ... ...a mm (1) 1/a 11 0 0 ... 0 1 0 0 ... 0 D 1 =  0 1 0 ... 0  L 1 k = 1 −a 21 1 0 A... (k 0 . ... ... ... ... ... ... ... ... ... ...  0 0 0 ... 1 −am 1 0 0 ... 1 k − −1) 1  ... 0 A (k − 1) = L D ...L D A =  0 a (1)12 ... 1 0 ... ... 0 1 ... ... a (kk −−11),k a (k −1) ... ... ... ... ... ... ... ... k a (1)1m 1,m  ... a (k − 1) − a (k − 1)  ... 0 ... 0 ... 0 ... a (mk k −1) ... ... ... ...  ... a (mmk − 1)   A (k −1) Dk k −1 k −1 1 1   k (kkk +11),k k (k,mk +11)  0 0 0 a − ... ... a − ,m Dk = diag(1 , Lk ... ... ... ... ... ... 0 ... 1 0 ... 0 k   1 ... ... k (mk (kk +11)1),k ... ... 0  L =. 0 ... −a − 1 ... 0 ... ... ... ... ... ... 0 ... −a − 0 ... 1 A (k ) = L k D k L k −1D k −1 ...L 1D 1A = − − ,m  1 ... a 11,k 1 a 11,k ... a 11,m 1 a 1 11,m    ... ... ... k (... k 11),k ... k (k ( k,m ...k 1)1) ,m 11 (k ... k 0 ... 1 a − ... a − a −1) − − − −  0 ... 0 0 m (k ) 1,m 1 m  = 0 ... 0 1 ... a a (k ) − k,m  ... ... ... ... ... ... ... 0 ... 0 0 ... a a (k )  − − −1,m m −1 U U = Dm Lm −1Dm −1 ...L 1 D 1 A = − − 1,m ... ... ... ... ... ... ... 0 ... 1 a − ... a − a − 1)   1 ... a 11,k 1 a (kk 11,k 11),k ... a (kk (k,m 11k,m 1)1),m 111 m (a k (mk 111    − − − − ,m = 0 ... 0 1 ... a a (k ) − k,m ... ... ... ... ... ... ... 0 ... 0 0 ... 1 a − 1) − ,m 0 ... 0 0 ... 0 1 L −1 = Dm Lm −1Dm −1 ...L 1 D 1 A L −1 A = LU. U cond(U) = cond(L − 1 A ) = cond(Dm Lm −1Dm −1 ...L 1 D 1 A ) 6 cond(cond(Li ) cond(A ) =1 m cond(Li ) > 1 cond(U ) D  i , |a (iii )| < 1 cond(  |aii , |a (iii )| > 1 cond(Di ) cond(U ) cond(A ) L i D i “ a 11x 1 + a 12x 2 + ... + a 1m x m = b 1 a 21x 1 + a 22x 2 + ... + a 2m x m = b 2 .............................. a m 1x 1 + a m 2x 2 + ... + a mm x m = b m U xk A a i,n +1 = b i k 1 m − 1 i k + 1 m + 1 r := a ik /a kk j k + 1 m + 1 a ij := a ij − r a kj j i k x n := a n,n +1/a n,n k n − 1 1 x k := a k,n +1 − P a kj x j !/a kk n j =k +1 k Ux = y cond(A ) Ux = y U A k xk |a ln |(k ) = 6max6 |a ij |(k ) k l k n k i,j m k n x ∗ x (1) kr (1)k 6 ε x (1) ε A A = QR, Q R A a 25 a 35 a 45 a 55 a 15  12 12  cosϕ 1212 −sinϕ 1212 0 0 0  sinϕ cosϕ 0 0 0 Q (ϕ ) =0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 A 12 = Q 12A 12   a 1111 cosϕ 1212 −514131a 2121 sinϕ 1212 ·524232 · · a 1515 cosϕ 1212 − a 2525 sinϕ 12  a sinϕ + a cosϕ · · · a cosϕ + a sinϕ 12 A =a a · · · a a · · · a a · · · ϕ 12 A 12 a 11 sinϕ 12 + a 21 cosϕ 12 = 0. A 1 Q 3 Q 4 A 4 = Q 4 · Q 3 · Q 2 · Q 1 A A m × m Am − 1 = Qm − 1 · ... · Q 1 · A = Q e · A, e Q A m −1 A = QR Q = Q e−1 R = Am −1 QR A v = m A v 1 = (a 11,a 21,...,a m 1)T P 1 m × m a (1)12mm   a (1) mm ·  · a (1) m − 1 v 2 , A m −1 Q Pi T i = 1,...,m − 1 Q A = QR Q R Ax = b Rx = Q T b cond(A ) = cond(R ) A Qij i j b (1)ik = b ik cosϕ ij − a jk sinϕ ij k = 1,...,m. (1) b jk = b ik sinϕ ij + a jk cosϕ ij Q Am −1 = R QR A QR i k i i R = Am − 1 A = Q R i A m −1 A m −1 QR Qij O (2m 3 ) QR Pi m × m A = A ∗ A = L U. A = L U = A ∗ = U ∗ L ∗ ⇒ L U = U ∗ L ∗ ⇒ U (L ∗ )− 1 = L − 1 U ∗ . U (L ∗ )− 1 = L − 1 U ∗ = D ⇒ U = D L ∗ ⇒ A = L D L ∗ . , D = diag( A L k > i i = 1 a 1j = a j 1 = l 11d 11l j 1, LU LU QR A l QR x (0) x ∗ A x = b “ “ x (n ) kx (n ) − x ∗ k O (m 2 ) B b, n = 1, 2,... x (n ) x ∗ n → ∞ x (n ) τn = τ τn n = 1, 2,... B B −1 x (n ) ε n = n (ε ) . ε τn n = 1, 2,... r (n ) n τn = τ r (n ) = Sr (n −1) = S Sr (n −2) ... = S n r (0). S S kS k 6 1 kr (n )k → 0 n → ∞ S S n → ∞ |µ k | < 1 , . kr (n )k = kG −1J n G r (0)k 6 kG −1k kJ n k kG k kr (0)k → 0 n → ∞. S ε n → ∞ B = E S = E − τA S max|µk | τ max|µk | k k τ A = A ∗ > 0 A 0 < γ 1 6 λk 6 γ 2 k = λk S µk = 1 − τλk 0 < τ < 2/γ 2 |µk | = |1−τλk | < 1 0 < τ < 2/γ 2 τ = τ ∗ |µ ∗| = 0<τ< min2/γ 2 1max6k 6m |1 − τλ k | τ γ 1 < λ < γ 2 gλ (τ ) = 1−τλ τ = τ ∗ |gλ (τ ∗)| 6 |gλ (τ )| γ 1 < λ < γ 2 0 < τ < 2/γ 2 0 < τ < 1/γ 2 |gγ 2 (τ )| 6 |gγ 1 (τ )| τ > 1/γ 1 |gγ 1 (τ )| 6 |gγ 2 (τ )| 1/γ 2 6 τ 6 1/γ 1 τ 0 |gγ 2 (τ 0 )| = |gγ 1 (τ 0 )|, τ 0 cond(A ) 1 kS k → 1 ζ → ∞ aii =6 0 i = 1,...,m (n +1) B = diag(a 11 ,...,amm ) = b ⇒ x (n +1) = (E − B −1A )x (n ) + B −1b, A , . x (0) n := 0 x (1) Ax = b ε n N n > N A Ax = b a ii =6 0 (n + 1) i + ... = b 1 + ... + a 2m x m (n ) = b 2 ................................................... . m = 2 (x 1 ,x 2 ) , I , II x (0) n := 0 i 1 m n := n + 1 Ax = b x ∗ A = A ∗ > 0 . Φ(x ) = (Ax − b,Ax − b ) x ∈ Rm x ∗ F (x ) = F (x 1 ,x 2 ,...,xm ). F (x ) x 1 ϕ 1(x 1) = F (x 1,x 2(n ),...,x m (n )), x (1 n +1) . x 2 . (n + 1) A = A ∗ > 0 C = 0 a 1 A 1 (x (1)1 ,x (1)2 ) C Ax = b Ax = b A = A∗ > 0 k k k n + 1 x (k n +1) . . . Xk −1 a ik x (in +1) + a kk x k (n +1) + Xm a ik x ni = b k . i =1 i =k +1 A = A ∗ > 0 F (x ) x grad x (n +1) x (n +1) = x (n ) − α n gradF (x (n )), αn x (n +1) gradF (xn ) αn := αn / 2 x (n +1) αn αn N x (n +1) ε ε “ , “ , αn |ϕ (αn )| ϕ (α n ) = F (x (n +1)) = F (x (n ) − α n gradF (x (n ))). αn A = A ∗ > 0 grad . αn Ax = b A = A∗ > 0 A 0 = (x 01,x 02) gradF (x 0 ) A 0A 1 A 0A 1 (x 11,x 12) A 1 A 0A 1 A = A ∗ > 0 n , n , . . . , x (n +1) , i 0 < ω < 1 1 < ω < 2 ω = 1 x (n ) = Sx (n −1) + c, c ε kr (n )k = kx (n ) − x ∗ k 6 ε kr (n )k = kx (n ) −x ∗ k x (n ) x ∗ v (n ) . R m µi S 1 > |µ 1 | > |µ 2 | > |µ 3 | > ... > |µm |, µi , . kw (n )k = O ( |µ 1|n ) , . , . , n . kx (n ) − x (n −1)k µ 1 , kv (n ) k 6 ε 1, α β x (k +1) = S x (k ) + c ? , S = E − τA 0 < τ < 0. 4 α β α β α β n = 2 m × m A ∗ A A A ∗ a ji AA A −1 b =6 0 A m λ ϕ 6= 0 A m det (A − λE ) = 0. A ρ (A ) = max|λi | i A trA A A A A ajj ej = (0,..., 0, 1 , 0,..., 0) j |{z} λ k λ j A λ k =6 λ j λk ϕk k = 1,...,m R m R m R m A ∗ ψk k = 1,...,m (ϕk ,ψj ) = 0, k =6 j. A A B P B = P −1 AP P B = P ∗AP A B , . grad α gradF y F (x ) x F (x ) = c F (x ) = c x 0 = . max |a ij | 16i,j 6m E S (A ) = √trAA ∗