Toán học - Chương II: Giải hệ phương trình ax = b

Chöông II : GIAÛÛI HEÄÄ PHÖÔNG TRÌNH Ax=b 1) Heäää coùùù A laøøø ma traäään tam giaùùùc treââân             =                     = n n b b x x a aaa aaa xA . . . . ..... ..00 .0 .. 2 1 2 1 33 22322 11211 Phương pháp TínhNgô Thu Lương          nnnn bxa0000 Tính nghieäm 1 2 3 1....n n n nx x x x x− − −→ → → →      =++ =++ =++ 1.001.000 2.2021.00 0.182 3 32 321 x xx xxx Ví duïïï :    = = 2 4 2 1 x x Phương pháp TínhNgô Thu Lương   =103x 2) Heäää có A laøøø ma traäään tam giaùùùc döôùùùi                 =                                 = nnnnnn b b b x x x aaa aaa aa a xA . . . . .. 0.... .. 0.0 0..0 2 1 2 1 21 333231 2221 11 Phương pháp TínhNgô Thu Lương Tính nghieäm 1 2 3 4.... nx x x x x→ → → → 3) Giaûûûi baèèèng phöông phaùùùp nhaââân töûûû LU : ( A ma traäään vuoâââng baááát kyøøø ) a) Noäääi dung : 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 Phương pháp TínhNgô Thu Lương Vieäc giaûi heä phöông trình seõ ñöa veà giaûi hai heäää phöông trình daïng tam giaùùùc Quy öôùc 11 22 33 .. 1l l l= = = = : coù nghieäm duy nhaát Caùùùch tìm L, U töøø ma traään A : Nhaân haøng1 cuûa Lvôùi coät 1 cuûa U tìm ñöôïc 11u Nhaân haøng2 cuûa Lvôùi coät 1 cuûa U tìm ñöôïc 21l Nhaân haøng3 cuûa Lvôùi coät 1 cuûa U tìm ñöôïc 31l Nhaân haøng1 cuûa Lvôùi coät 2 cuûa U tìm ñöôïc 12u Nhaân haøng1 cuûa Lvôùi coät 3 cuûa U tìm ñöôïc 13u Nhaân haøng2 cuûa vôùi coät 2 cuûa tìm ñöôïc Phương pháp TínhNgô Thu Lương L U 22u Nhaân haøng3 cuûa Lvôùi coät 2 cuûa U tìm ñöôïc 32l Nhaân haøng2 cuûa Lvôùi coät 3 cuûa U tìm ñöôïc 23u Nhaân haøng3 cuûa Lvôùi coät 3 cuûa U tìm ñöôïc 33u 4) Phöông phaùùùp Cholesky ( phöông phaùùùp caêêên baäääc hai ) a) Noäääi dung : Bieåu dieãn ma traän A döôùi daïng TBBA .= trong ñoù B laø ma traän tam giaùc döôùi Phương pháp TínhNgô Thu Lương ( TB : ma traän chuyeån vò cuûa B, laø ma traän tam giaùc treân ) b) Nhaään xeùùt : Caùch tìm B töông töïïï nhö phöông phaùp LU nhöng soá pheùp tính giaûm ñi 2 laàn Phöông phaùp Cholesky khoâââng ñoøi hoûi ñöôøng cheùo cuûa ma traän B baèng 1 Phương pháp TínhNgô Thu Lương Khi laáy caên baäc 2 quy öôùc raèng laáy caêêên soááá hoïïïc ( caêêên laøøø soááá döông ) Ví duï :           = 1451 551 111 A 0 0 0B     =     Phương pháp TínhNgô Thu Lương             − −− − = 210 121 012 A 0 0 0B     =   Phương pháp TínhNgô Thu Lương    b) Nhaäään xeùùùt : *) Phöông phaùp chæ duøng ñöôïc neáu A laø ñoááái xöùùùng vaø xaùùùc ñònh döông 5) Caùùùc phöông phaùùùp laëëëp : (thöôøng duøng cho caùc heä vôùi ma traän A coù kích thöôùc raát lôùn) Phương pháp TínhNgô Thu Lương 5.1) Ñònh nghóa : (Chuaån cuûa vectô ) i ni xx ≤≤∞ = 1 max ( ix : caùc thaønh phaàn cuûa veùctô x ) (chuaån voâ haïn , haøng ) i n i xx ∑= =1 1 ( chuaån 1, coät )      − = 2 1 x x ∞ = 5.1) Ñònh nghóa : (Chuaån cuûa vectô ) Phương pháp TínhNgô Thu Lương − 3 1x = 0x ≥ 0 0x x= ↔ = 5.2) Ñònh nghóa ( Chuaån cuûa ma traän )         ∑= =≤≤ ∞ n j ji ni aMaxA 11 (chuaån voâ haïn , chuaån haøng)     ∑= n jiaMaxA 1 Phương pháp TínhNgô Thu Lương  =≤≤ inj 11 (chuaån 1 , chuaån coät ) Ví duïïï :       = 12 34 A ta coù 7)3,7( 11 ==         ∑= =≤≤ ∞ MaxaMaxA n j ji ni 6)4,6( 11 1 ==      ∑= =≤≤ MaxaMaxA n i ji nj Phương pháp TínhNgô Thu Lương Caùùùc tính chaááát cuûûûa chuaååån ma traäään : 0 0 0 A A A ≥ = ⇔ = BABA +≤+ xAxA .. ≤ 5.3) Ñònh nghóa ( Soá ñieàu kieän cuaû ma traän A) 1 1 111 .)()( − == AAAcondAk ∞ − ∞∞∞ == 1 .)()( AAAcondAk Ví duïïï :       = 12 34 A ,     = − − − 21 2/32/11A Phương pháp TínhNgô Thu Lương 213.7.)( 1 === ∞ − ∞∞ AAAk 11 1 1 7( ) . 6 21 2 k A A A−= = = Ví duïïï :           = 01.51.63 41.42 121 A           −− − −− = − 100100100 200020101980 390039203859 1A Phương pháp TínhNgô Thu Lương 69.164790)( =∞ Ak 73566)(1 =Ak 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 heäää soááá tyûûû leäää laø )(Ak ' ( ) 'x x k A b b− ≈ − 5.4) Phöông phaùùùp laëëëp Jacobi ( laëëëp ñôn ) : a) Noäääi dung: *) Ñöa heä bxA = veà daïng gxx +Φ= Phương pháp TínhNgô Thu Lương *) Kieåm tra ñieàu kieän 1<=Φ q (chuaån haøng hoaëc coät) *) Laáy )0(x laø veùctô giaù trò ban ñaàu tuøu yù *) Daõy laëp )(kx xaây döïng theo coâng thöùc gxx kk +Φ=+ )()1( b) Ñaùùùnh giaùùù sai soááá : ( ) (1) (0) 1 k k d qx x x x q − ≤ − − coâng thöùc tieân nghieäm ( ) ( ) ( 1) 1 k d k kqx x x x q − − ≤ − − coâng thöùc haäu nghieäm Phương pháp TínhNgô Thu Lương Ví duïïï : Xeùt heä phöông trình      −=++ =−+ =+− 101032 51101 02110 321 321 321 xxx xxx xxx  +−+= 02.01.0 xxx Phương pháp TínhNgô Thu Lương     −−−= ++−= 13.02.0 5.01.01.0 213 312 321 xxx xxx 5.0=Φ ∞ = ∞q 4.01 =Φ = 1q        −−−= ++−= +−+= + + + 13.02.0 5.01.01.0 02.01.0 )( 2 )( 1 )1( 3 )( 3 )( 1 )1( 2 )( 3 )( 2 )1( 1 kkk kkk kkk xxx xxx xxx Vôùi Tx ]000[)0( = , soá böôùc laëp laø k = 3 Phương pháp TínhNgô Thu Lương k 0 1 2 3 )( 1 k x 0 0 0.25 0.270 )( 2 k x 0 0.5 0.4 0.360 )( 3 k x 0 -1 -1.15 -1.170 Sai soá ∞ - 0.04 c)Nhaäään xeùùùt : A ma traän coù ñöôøøøng cheùùùo troäääi theo haøøøng: ii ji ji aa <∑ ≠ ⇒ 1<Φ ∞ A ma traän coù ñöôøøøng cheùùùo troäääi theo coääät ii ij ji aa <∑ ≠ ⇒ 11 <Φ Phương pháp TínhNgô Thu Lương 5.5) Phöông phaùùùp laëëëp Gauss - Seidel : Noäääi dung : Caùc thaønh phaàn cuûa )1( +kix vöøa tính ñöôïc ñaõ duøøøng ngay ñeå tính )1( 1 + + k ix trong böôùc tieáp theo ( 1) ( ) ( )0.1 0.2 0k k kx x x+ = + − + Phương pháp TínhNgô Thu Lương 1 2 3 ( 1) ( ) 2 1 3 ( 1 ( 3 ( ) ( 1 2 0.1 0.1 0.5 0.2 0.3 1 k k k x x x x x x + + + + +   =− + +  =− − − k 1) k 1) k 1) k 0 1 2 3 )( 1 k x 0 0 0.28 0.26832 )( 2 k x 0 0.5 0.357 0.356858 )( 3 k x 0 -1.15 -1.1631 -1.1607214 c) Nhaäään xeùùùt: Phương pháp TínhNgô Thu Lương 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 Ax b= A D L U= − − 10 0 0 0 10 0 0 0 10 D     =      0 0 0 1 0 0L     = −   Jacobi ( )D L U x b− − = ( )Dx L U x b= + + 1 1( )x D L U x D b− −= + + x x g= Φ + Phương pháp TínhNgô Thu Lương 10 1 2 1 10 1 2 3 10 A −    = −      0 1 2 0 0 1 0 0 0 U −    =      2 3 0− −   Ax b= A D L U= − − Gauss-Seidel ( )D L U x b− − = ( )D L x Ux b− = + Phương pháp TínhNgô Thu Lương 1( )D L U−− = Φ 1 1( ) ( )x D L U x D L b− −= − + − 1( )D L b g−− = ?= 10 3 5 11 A −  =   −  10 0  10 0 5 11 D L   − =   −  (làm tròn hai chữ số lẻ) gΦ Phương pháp TínhNgô Thu Lương 0 11 D =     0 0 5 0 L   =     0 3 0 0 U  =     1 0.1 0( ) 0.04545454 0.09090909 D L −   − =     1 0 0.3( ) 0 0.136363636 D L U−  − =    