Bài giảng Phương pháp tính giải tích số - Chương 2: Giải hệ phương trình Ax=b - Ngô Thu Lương

Nội dung text: Bài giảng Phương pháp tính giải tích số - Chương 2: Giải hệ phương trình Ax=b - Ngô Thu Lương

1. CChhööôônngg IIII :: GGIIAAÛÛII HHEEÄÄ PPHHÖÖÔÔNNGG TTRRÌÌNNHH AAxx==bb 111))) HHHeeeää ä cccoooùù ù AAA lllaaaøø ø mmmaaa tttrrraaaäänänn tttaaammm gggiiiaaaùùcùcc tttrrreeeâânânn a11 a12 . . a1n   x1   b1        b  0 a22 a23 . a2n  x2   2  A x =  0 0 a33 . .   .  =  .        .  . . . . .   .     0 0 0 0 ann  xn  b n  Tính nghieäm → → → → xxnn−1 x n − 2 x n − 3 x 1 Ngô Thu L ươ ng Ph ươ ng pháp Tính
2. VVíí dduuïï ï ::: x1 + 2x2 + x3 = 18 .0   0 + 0.1x2 + 2x3 = 20 .2   0 +0 + 0.01 x3 =0.1 x1 = 4  x2 = 2  x3 =10 Ngô Thu L ươ ng Ph ươ ng pháp Tính
3. 222))) HHHeeeää ä cccóóó AAA llaaaøø ø mmmaaa tttrrraaaäänänn tttaaammm gggiiaaaùùcùcc dddöööôôôùùiùii a11 0 . . 0   x1  b1        b a21 a22 0 . 0  x2   2  A x = a31 a32 a33 . .   .  =  .        .  . . . . 0   .    an1 an2 . . ann  xn  b n  → → → → Tính nghieäm xxxx1 2 3 4 x n Ngô Thu L ươ ng Ph ươ ng pháp Tính
4. 33)) GGGiiiaaûûiûi bbaaèènèngg pphhööôônngg ppphhhaaùùpùp nnhhaaâânân tttöööûû û LLLUU ::: (( AA mmaaa ttrraaäänän vvuuoooâânângg bbbaaáátátt kkkyyøø ø )) aa)) NNooääiäi dduuunnnggg : Phaân tích ma traän A = L.U L laø ma traän tam giaùc döôùi U laø ma traän tam giaùc treân Vieäc giaûi heä phöông trình seõ ñöa veà giaûi hhhaaiii hhheeäää phöông trình daïng ttaamm ggiiaaùcùcùc = = = = Quy öôùc l11 l 22 l 33 1 : coù nghieäm duy nhaát Ngô Thu L ươ ng Ph ươ ng pháp Tính
5. CCaaùùcùchh ttììmm LL,, UU ttööø ø mmaa ttrraaäänn AA :: Nhaân haøng1 cuûa Lvôùi coät 1 cuûa U tìm ñöôïc u11 Nhaân haøng2 cuûa Lvôùi coät 1 cuûa U tìm ñöôïc l21 Nhaân haøng3 cuûa Lvôùi coät 1 cuûa U tìm ñöôïc l31 Nhaân haøng1 cuûa Lvôùi coät 2 cuûa U tìm ñöôïc u12 Nhaân haøng1 cuûa Lvôùi coät 3 cuûa U tìm ñöôïc u13 Nhaân haøng2 cuûa Lvôùi coät 2 cuûa U tìm ñöôïc u22 Nhaân haøng3 cuûa Lvôùi coät 2 cuûa U tìm ñöôïc l32 Nhaân haøng2 cuûa Lvôùi coät 3 cuûa U tìm ñöôïc u23 Nhaân haøng3 cuûa Lvôùi coät 3 cuûa U tìm ñöôïc u33 Ngô Thu L ươ ng Ph ươ ng pháp Tính
6. 444))) PPhhhööôôônnnggg pphhhaaaùùpùpp CChhhoolleeessskkyyy ((( ppphhöööôônngg pphhhaaaùùpùpp ccaaêênên bbbaaaääcäcc hhhaaaiii )) aa)) NNNooääiäii dduunngg : Bieåu dieãn ma traän A döôùi daïng A = B.BT trong ñoù B laø ma traän tam giaùc döôùi (BT : ma traän chuyeån vò cuûa B, laø ma traän tam giaùc treân ) Ngô Thu L ươ ng Ph ươ ng pháp Tính
7. bb)) NNhhaaänän xxeeùtùt :: Caùch tìm B tttöööôôônnngg tttööïïï nhö phöông phaùp LU nhöng soá pheùp tính giaûm ñi 2 laàn Phöông phaùp Cholesky kkkhhhoooâânângg ñoøi hoûi ñöôøng cheùo cuûa ma traän B baèng 1 Khi laáy caên baäc 2 quy öôùc raèng laáy ccaaaêênên ssooáá á hhooïïcïcc ( cccaaaêênên llaaaøø ø ssooáá á ddööôônngg ) Ngô Thu L ươ ng Ph ươ ng pháp Tính
8. 1 1 1  VVVííí ddduuuï : =   A 1 5 5  1 5 14  0 0  =   B 0    Ngô Thu L ươ ng Ph ươ ng pháp Tính
9.  2 −1 0  = − −  A  1 2 1  0 −1 2  0 0  =   B 0    Ngô Thu L ươ ng Ph ươ ng pháp Tính
10. bbb))) NNNhhhaaaäänänn xxxeeeùùtùtt ::: *) Phöông phaùp chæ duøng ñöôïc neáu A laø ñññoooáiáiái xxxöööùnùnùnggg vaø xxxaaaùcùcùc ñññòòònnnhhh dddöööôôônnnggg 555))) CCCaaaùùcùcc ppphhhöööôôônnnggg ppphhhaaaùùpùpp lllaaaëëpëpp ::: (thöôøng duøng cho caùc heä vôùi ma traän A coù kích thöôùc raát lôùn ) 555 111))) ÑÑÑòòònnnhhh nnnggghhhóóóaaa : (Chuaån cuûa vectô ) x ∞ = max xi 1≤i≤n ( xi : caùc thaønh phaàn cuûa veùctô x ) (chuaån voâ haïn , haøng ) Ngô Thu L ươ ng Ph ươ ng pháp Tính
11. 555 111))) ÑÑÑòòònnnhhh nnnggghhhóóóaaa : (Chuaån cuûa vectô ) n = ∑ x 1 xi i =1 ( chuaån 1, coät ) −1 x = =   ∞ x  2  = − 3 x 1 x ≥ 0 x=0 ↔ x = 0 Ngô Thu L ươ ng Ph ươ ng pháp Tính
12. 555 222))) ÑÑòòònnnhh nnngghhhóóaa ( Chuaån cuûa ma traän )  n  =   A ∞ Max  ∑ ai j  1≤ i ≤ n  j =1  (chuaån voâ haïn , chuaån haøng)  n  =  ∑  A 1 Max  ai j  1≤ j ≤ n  i =1  (chuaån 1 , chuaån coät ) Ngô Thu L ươ ng Ph ươ ng pháp Tính
13. 4 3 = VVVííí ddduuuïï ï : A   ta coù 2 1  n  =  ∑  = = A ∞ Max  ai j  Max ( 7,3) 7 1≤ i ≤ n  j =1   n  =  ∑  = = A 1 Max  ai j  Max ( 6,4) 6 1≤ j ≤ n i=1  CCCaaaùùcùcc tttííínnnhhh ccchhhaaaáátátt cccuuuûûaûaa ccchhhuuuaaaåånånn mmmaaa tttrrraaaäänänn ::: A ≥ 0 AA=0 ⇔ = 0 A + B ≤ A + B A. x ≤ A . x Ngô Thu L ươ ng Ph ươ ng pháp Tính
14. 55 33)) ÑÑòònnhh nngghhóóaa ( Soá ñieàu kieän cuaû ma traän A) −1 k1 ( A) = cond 1 ( A) = A . A 1 1 −1 k∞ ( A) = cond ∞ ( A) = A . A ∞ ∞ 4 3 − = −1= 1/2 3/2 VVVíí ddduuuïï ï : A   , A   2 1  1 −2 −1 k∞(A) = A . A = 7.3= 21 ∞ ∞ =−1 =7 = k1() A A . A 6 21 1 1 2 Ngô Thu L ươ ng Ph ươ ng pháp Tính
15. 1 2 1  Ví duï : =   VVíí dduuï ï :: A 2 4.1 4  3 6.1 5.01  − 3859 − 3920 3900  −1 =  −  A  1980 2010 2000   −100 −100 100  k∞(A)= 164790 .69 k1(A) = 73566 Ngô Thu L ươ ng Ph ươ ng pháp Tính
16. Söï bieán thieân cuûa nghieäm tyû leä vôùi söï bieán thieân cuûa veá phaûi vôùi hhheeeää ä sssoooáá á tttyyyûû û llleeeäää laø k(A) xx−' ≈ kAbb () − ' 5. 4))) PPPhhhöööôôônnnggg ppphhhaaaùùpùpp lllaaaëëpëpp JJJaaacccooobbbiii ((( lllaaaëëpëpp ñññôôônnn ))) ::: aaa))) NNNoooääiäii ddduuunnnggg::: *) Ñöa heä A x = b veà daïn g x = Φ x + g *) Kieåm tra ñieàu kieän Φ = q < 1 (chuaån haøng hoaëc coät) *) Laáy x(0) laø veùctô giaù trò ban ñaàu tuøu yù *) Daõy laëp x(k) xaây döïng theo coâng thöùc + x(k 1) = Φx(k) + g Ngô Thu L ươ ng Ph ươ ng pháp Tính
17. bbb))) ÑÑÑaaaùùnùnnhhh gggiiiaaaùù ù sssaaaiii sssoooáá á ::: q k xx(k )− d ≤ xx (1) − (0) 1− q coâng thöùc tieân nghieäm q − xx()kd− ≤ xx ()(1) kk − 1− q coâng thöùc haäu nghieäm Ngô Thu L ươ ng Ph ươ ng pháp Tính
18. VVííí dduuuïï ï : Xeùt heä phöông trình 10 x1 −1x2 + 2x3 = 0  1x1 +10 x2 − 1x3 = 5  2x1 + 3x2 + 10 x3 = −10  x1 = + 0.1x2 − 0.2 x3 + 0   x2 = − 0.1x1 + 0.1x3 + 0.5   x3 = − 0.2 x1 − 0.3x2 −1 Φ ∞ = 0.5 = q∞ Φ = 1 0.4 = q1 Ngô Thu L ươ ng Ph ươ ng pháp Tính
19. + x(k 1) = + 0.1x(k) −0.2x(k) + 0  1 2 3  (k+1) = − (k) + (k) + x 2 0.1x 1 0.1x 3 0.5  + x(k 1) = −0.2x(k) −0.3x(k) −1  3 1 2 Vôùi x(0) =[ 0 0 0 ]T , soá böôùc laëp laø k = 3 k 0 1 2 3 (k) 0 0 0.25 0.270 x1 (k) 0 0.5 0.4 0.360 x2 (k) 0 -1 -1.15 -1.170 x3 Sai soá ∞ - 0.04 Ngô Thu L ươ ng Ph ươ ng pháp Tính
20. cc)))NNhhaaäänän xxeeùùtùtt : A ma traän coù ññöööôôôøønøngg cchhheeùùoùoo tttrrrooääiäi theo hhhaaøønønngg: Φ < ∑ ai j < aii ⇒ ∞ 1 i≠ j A ma traän coù ññöööôôôøønøngg cchhheeùùoùoo tttrrrooääiäi theo cccooäätät < Φ < ∑ ai j ai i ⇒ 1 1 j≠i Ngô Thu L ươ ng Ph ươ ng pháp Tính
21. 555 555))) PPPhhhöööôôônnnggg ppphhhaaaùùpùpp lllaaaëëpëpp GGGaaauuussssss SSSeeeiiidddeeelll ::: (k+1) NNNoooääiäii ddduuunnnggg : Caùc thaønh phaàn cuûa x i vöøa + duøng ngay (k 1) tính ñöôïc ñaõ dduuøønngg nnggaayy ñeå tính xi+1 trong böôùc tieáp theo + x(1)k= +0.1 x () k − 0.2 x () k + 0  1 2 3  (k+ 1)=−(k+ 1) + ( k ) + x20.1 x 1 0.1 x 3 0.5   (k+ 1 ) =−(k+ 1) −( k + 1 ) − x3 0.2 x1 0.3 x 2 1 Ngô Thu L ươ ng Ph ươ ng pháp Tính
22. k 0 1 2 3 (k) 0 0 0.28 0.26832 x1 (k) 0 0.5 0.357 0.356858 x2 (k) 0 -1.15 -1.1631 -1.1607214 x3 ccc))) NNNhhhaaaäänänn xxxeeeùùtùtt: Phöông phaùp Gauss – Seidel thoâng thöôøng coù toác ñoä hoäi tuï nhanh hôn phöông phaùp laëp jacobi Giaûi thuaät ñôn giaûn hôn so vôùi phöông phaùp Jacobi . Nh ược điểm : Đánh giá sai s ố ph ức t ạp Ngô Thu L ươ ng Ph ươ ng pháp Tính
23. = Jacobi Ax b 10 0 0  ADLU= − − =   (D− L − U ) x = b D 0 10 0  = + + Dx( L U ) x b 0 0 10  =−1 + + − 1 x D( L U ) x D b 0 0 0  x= Φ x + g   L = −1 0 0 −   10 1 2  − −   2 3 0  A =1 10 − 1   0 1− 2  2 3 10    =   U 0 0 1  0 0 0  Ngô Thu L ươ ng Ph ươ ng pháp Tính
24. GaussGauss SeidelSeidel Ax= b ADLU= − − (D− L − U ) x = b (D− L ) x = Ux + b − − x=() D − L1 U x + () D − L 1 b − (DLU− ) 1 = Φ − (D− L ) 1 b = g Ngô Thu L ươ ng Ph ươ ng pháp Tính
25. = Φg ? (làm tròn hai 10− 3  = 10 0  chữ s ố l ẻ) A   − = −5 11  DL   −5 11  10 0  D =   −1 0.1 0  0 11  (DL− ) =   0 0  0.04545454 0.09090909  L =   5 0  −1 0 0.3  (DLU− ) =   0 3  0 0.136363636  U =   0 0 Ngô Thu L ươ  ng Ph ươ ng pháp Tính