Bài giảng Phương pháp tính (Computation Methods) - Chương II : Giải hệ phương trình - Ngô Thu Lương

Chương II : GIẢÛI HỆÄ PHƯƠNG TRÌNH Ax=b 1) Hệää cóùù A làøø ma trậään tam giáùùc trêââ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 nghiệ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í dụïï :    = = 2 4 2 1 x x Phương pháp TínhNgơ Thu Lương   =103x 2) Hệää cĩ A làøø ma trậään tam giáùù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 nghiệm 1 2 3 4.... nx x x x x→ → → → 3) Giảûûi bằèèng phương pháùùp nhââân tửûû LU : ( A ma trậään vuôââng bấáát kỳøø ) a) Nộääi dung : Phân tích ma trận A = L.U L là ma trận tam giác dưới U là ma trận tam giác trên Phương pháp TínhNgơ Thu Lương Việc giải hệ phương trình sẽ đưa về giải hai hệää phương trình dạng tam giáùùc Quy ước 11 22 33 .. 1l l l= = = = : có nghiệm duy nhất Cáùùch tìm L, U từø ma trậän A : Nhân hàng1 của Lvới cột 1 của U tìm được 11u Nhân hàng2 của Lvới cột 1 của U tìm được 21l Nhân hàng3 của Lvới cột 1 của U tìm được 31l Nhân hàng1 của Lvới cột 2 của U tìm được 12u Nhân hàng1 của Lvới cột 3 của U tìm được 13u Nhân hàng2 của với cột 2 của tìm được Phương pháp TínhNgơ Thu Lương L U 22u Nhân hàng3 của Lvới cột 2 của U tìm được 32l Nhân hàng2 của Lvới cột 3 của U tìm được 23u Nhân hàng3 của Lvới cột 3 của U tìm được 33u 4) Phương pháùùp Cholesky ( phương pháùùp căêên bậääc hai ) a) Nộääi dung : Biểu diễn ma trận A dưới dạng TBBA .= trong đó B là ma trận tam giác dưới Phương pháp TínhNgơ Thu Lương ( TB : ma trận chuyển vị của B, là ma trận tam giác trên ) b) Nhậän xéùt : Cách tìm B tương tựïï như phương pháp LU nhưng số phép tính giảm đi 2 lần Phương pháp Cholesky khôââng đòi hỏi đường chéo của ma trận B bằng 1 Phương pháp TínhNgơ Thu Lương Khi lấy căn bậc 2 quy ước rằng lấy căêên sốáá họïïc ( căêên làøø sốáá dương ) Ví dụ :           = 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) Nhậään xéùùt : *) Phương pháp chỉ dùng được nếu A là đốáái xứùùng và xáùùc định dương 5) Cáùùc phương pháùùp lặëëp : (thường dùng cho các hệ với ma trận A có kích thước rất lớn) Phương pháp TínhNgơ Thu Lương 5.1) Định nghĩa : (Chuẩn của vectơ ) i ni xx ≤≤∞ = 1 max ( ix : các thành phần của véctơ x ) (chuẩn vô hạn , hàng ) i n i xx ∑= =1 1 ( chuẩn 1, cột )      − = 2 1 x x ∞ = 5.1) Định nghĩa : (Chuẩn của vectơ ) Phương pháp TínhNgơ Thu Lương − 3 1x = 0x ≥ 0 0x x= ↔ = 5.2) Định nghĩa ( Chuẩn của ma trận )         ∑= =≤≤ ∞ n j ji ni aMaxA 11 (chuẩn vô hạn , chuẩn hàng)     ∑= n jiaMaxA 1 Phương pháp TínhNgơ Thu Lương  =≤≤ inj 11 (chuẩn 1 , chuẩn cột ) Ví dụïï :       = 12 34 A ta có 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 Cáùùc tính chấáát củûûa chuẩåån ma trậään : 0 0 0 A A A ≥ = ⇔ = BABA +≤+ xAxA .. ≤ 5.3) Định nghĩa ( Số điều kiện cuả ma trận A) 1 1 111 .)()( − == AAAcondAk ∞ − ∞∞∞ == 1 .)()( AAAcondAk Ví dụïï :       = 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í dụïï :           = 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ự biến thiên của nghiệm tỷ lệ với sự biến thiên của vế phải với hệää sốáá tỷûû lệää là )(Ak ' ( ) 'x x k A b b− ≈ − 5.4) Phương pháùùp lặëëp Jacobi ( lặëëp đơn ) : a) Nộääi dung: *) Đưa hệ bxA = về dạng gxx +Φ= Phương pháp TínhNgơ Thu Lương *) Kiểm tra điều kiện 1<=Φ q (chuẩn hàng hoặc cột) *) Lấy )0(x là véctơ giá trị ban đầu tùu ý *) Dãy lặp )(kx xây dựng theo công thức gxx kk +Φ=+ )()1( b) Đáùùnh giáùù sai sốáá : ( ) (1) (0) 1 k k d qx x x x q − ≤ − − công thức tiên nghiệm ( ) ( ) ( 1) 1 k d k kqx x x x q − − ≤ − − công thức hậu nghiệm Phương pháp TínhNgơ Thu Lương Ví dụïï : Xét hệ 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( = , số bước lặp là 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 số ∞ - 0.04 c)Nhậään xéùùt : A ma trận có đườøøng chéùùo trộääi theo hàøøng: ii ji ji aa <∑ ≠ ⇒ 1<Φ ∞ A ma trận có đườøøng chéùùo trộääi theo cộäät ii ij ji aa <∑ ≠ ⇒ 11 <Φ Phương pháp TínhNgơ Thu Lương 5.5) Phương pháùùp lặëëp Gauss - Seidel : Nộääi dung : Các thành phần của )1( +kix vừa tính được đã dùøøng ngay để tính )1( 1 + + k ix trong bước tiế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) Nhậään xéùùt: Phương pháp TínhNgơ Thu Lương Phương pháp Gauss – Seidel thông thường có tốc độ hội tụ nhanh hơn phương pháp lặp jacobi Giải thuật đơn giản hơn so với phương phá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−  − =    