›
›

Bài giảng Giải hệ thống phương trình đại số tuyến tính

ppt 79 trang phuongnguyen 2340
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Giải hệ thống phương trình đại số tuyến tính", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_giai_he_thong_phuong_trinh_dai_so_tuyen_tinh.ppt

Nội dung text: Bài giảng Giải hệ thống phương trình đại số tuyến tính

  1. Báo Cáo Chương Lưu Hoàng em – DH7A2 Đại học An Giang
  2. • ĐẶT VẤN ĐỀ • PHƯƠNG PHÁP TRỰC TIẾP: PHƯƠNG PHÁP GAOXƠ (HAY PHƯƠNG PHÁP KHỬ) • NHỮNG PHƯƠNG PHÁP LẶP
  3. BÀI 1. ĐẶT VẤN ĐỀ Trong chương này, ta xét giải hệ thống phương trình đại số tuyến tính (pt đstt) n pt n ẩn. a11 x 1+ a 12 x 2 + a 13 x 3 + + a 1n x n = a 1 n+ 1 a21 x 1+ a 22 x 2 + a 23 x 3 + + a 2n x n = a 2 n+ 1 (3.1) an1 x 1+ a n 2 x 2 + a n 3 x 3 + + a nn x n = a nn+ 1 Muốn giải hệ thống pt này bằng pp Crame thì khối lượng tính rất lớn khi n lớn. Vì vậy, người ta phải xây dựng những pp sao cho khối lượng tính có thể thực hiện được khi n lớn.
  4. Những pp giải hệ thống pt (3.1) được chia làm 2 loại: những pp trực tiếp và những pp lặp. Việc chọn pp giải phụ thuộc vào đặc điểm cảu ma trận hệ số A của hệ. Việc chọn không phải là một nguyên tắc cứng nhắc, không phải không có những trường hợp ngoại lệ.
  5. BÀI 2. PHƯƠNG PHÁP GAOXƠ 2.1. Nội dung pp 2.2. Sơ đồ tính 2.3. Kiểm tra quá trình tính 2.4. Khối lượng tính 2.5. Sai số của pp Gaoxơ 2.6. PP Gaoxơ có tìm trụ lớn nhất 2.7. Tính định thức bằng pp Gaoxơ 2.8. Tính ma trận nghịch đảo bằng pp Gaoxơ 2.9. Chuẩn của ma trận và chuẩn của pp vectơ 2.10. Sự không ổn định của hệ thống pt đstt
  6. Nội dung cơ bản của PP Gaoxơ là khử dần các ẩn số để đưa hệ (3.4) về hệ “tam giác” tương đương (ma trận hệ số của hệ là ma trận tam giác trên): (1) (1) (1) (1) x1+ a 12 x 2 + a 13 x 3 + a 14 x 4 = a 15 (1) (1) (1) x2+ a 23 x 3 + a 24 x 4 = a 25 (1) (1) (3.5) x3+= a 34 x 4 a 35 (1) xa4= 45 Sau đó giải hệ (3.5) từ dưới lên trên. Quá trình đưa hệ (3.4) về hệ (3.5) gọi là quá trình thuận, quá trình giải hệ (3.5) gọi là quá trình ngược.
  7. a) Quá trình thuận (0) (0) Khử x 1 . Giả sử aa 11 0( 11 gọi là trụ thứ nhất). Chia (0) phương trình đầu của hệ (3.4) cho a 11 , ta nhận được: (1) (1) (1) (1) x1+ a 12 x 2 + a 13 x 3 + a 14 x 4 = a 15 (3.6) (1) (0) (aij== a ij , j 2,3,4,5) Dùng pt (3.6) khử trong ba pt còn lại của hệ (3.6). Muốn thế, đem pt thứ hai của hệ (3.4) trừ pt (3.6) đã nhân với (0) đem a21 phương trình thứ ba của hệ (3.4) trừ phương trình (3.6) đã nhân (0) với a 31 đem phương trìng thứ tư của hệ (3.4) trừ phương trình (3.6) đã nhân với (0) a41
  8. Kết quả nhận được hệ ba phương trình sau: (1) (1) (1) (1) a22 x 2+ a 23 x 3 + a 24 x 4 = a 25 (1) (1) (1) (1) a32 x 2+ a 33 x 3 + a 34 x 4 = a 35 (3.7) (1) (1) (1) (1) a42 x 2+ a 43 x 3 + a 44 x 4 = a 45 (1) (0) (0) (1) (aij= a ij − a 11 a ij , i = 2,3,4; j = 2,3,4,5) (1) (1) Khử x 2 . Giả sử aa 22 0( 22 gọi là trụ hạng thứ hai). Chia (1) pt đầu của hệ (3.7) cho a 22 , ta được: (2) (2) (2) x2+ a 23 x 3 + a 24 x 4 = a 25 (3.8) (2) (1) (1) (a2jj== a 2 / a 22 , j 3,4,5).
  9. Đem phương trình thứ hai của hệ (3.7) trừ phương trình (3.8) (1) đã nhân với a 42 . Kết quả nhận được hệ hai phương trình sau: (2) (2) (2) a33 x 3+= a 34 x 4 a 35 (2) (2) (2) ( 3.9) a43 x 3+= a 44 x 4 a 45 (2) (1) (1) (2) (aij= aij − a i 2 a 2 j , i = 3,4; j = 3,4,5)
  10. (2) (2) Khử x 3 . Giả sử aa 33 0( 33 gọi là trụ thứ ba). Chia pt (2) đầu của hệ (3.9) cho a 33 và đem pt thứ hai của hệ (3.9) (2) trừ pt vừa nhận được đã nhân với a 43 ,ta được: (3) (3) x3+= a 34 x 4 a 35 ( 3.10) (3) (3) a44 x 4= a 45 ( 3.11) (3) (2) (2) (3) (2) (2) (3) (a3j= a 3 j / a 33 , a 4 j = a 4 j − a 43 a 3 j , j = 4,5) (3) (3) Cuối cùng nếu aa 44 0( 44 gọi là trụ thứ tư), ta (3) (4) chia pt (3.11) cho a 44 , pt (3.11) có dạng: xa4= 45 ( 3.12) (4) (3) (3) (a45 = a45/ a 44 )
  11. (0) (1) (2) (3) Rõ ràng là các phần tử trụ a 11 ,, a 22 a 33 vaø a 44 khác không thì hệ thống phương trình (3.4) tương đương với hệ thống phương trình “tam giác” sau: (1) (1) (1) (1) x1+ a 12 x 2 + a 13 x 3 + a 14 x 5 = a 15 (2) (2) (2) x2+ a 23 x 3 + a 24 x 4 = a 25 (3) (3) (3.13) x3+= a 34 x 4 a 35 (4) xa4= 45
  12. b) Quá trình ngược: Giải hệ thống (3.13) từ dưới lên, ta có: (4) xa4= 45 (3) (3) x3=− a 35 a 34 x 4 (3.14) (2) (2) (2) x2= a 25 x 3 − a 23 x 3 − a 24 x 4 (1) (1) (1) (1) x1= a 15 − a 12 x 2 − a 13 x 3 − a 14 x 4 Chú ý rằng điều kiện để áp dụng phương pháp Gaoxơ là các phần tử trụ phải khác không.
  13. 2.2. Sơ đồ tính Phân tích quá trình áp dụng phương pháp Gaoxơ ở mục 2.1 ta thấy: để đưa hệ thống (3.4) về hệ thống “tam giác” tương đương (3.13), chỉ cần tính các hệ số (1) (1) a1j ( j= 2,5), a ij ( i = 2,4; j = 2,5), (2) (2) a2j ( j= 3,5), a ij ( i = 3,4; j = 3,5), (3) (3) (4) a3jj, a 4 ( j= 4,5), a 45 . Kết quả tính, trong trường hợp không dùng máy tính điện tử, thường được ghi thành bảng, gọi là sơ đồ Gaoxơ, trong đó cột  dùng để kiểm tra quá trình tính.
  14. 2.3. Kiểm tra quá trình tính Khi không dùng máy tính điện tử, để có thể kiểm tra từng bước quá trình tính toán của phương pháp Gaoxơ, người ta 5 dùng “tổng kiểm tra” (0) (0) ai6 == a ij , i 1;2;3;4 ( 3.15) j=1 (nó chính là tổng những phần tử thuộc hàng I cùa ma trận hệ số A và số hạng vế phải tương ứng) như một vế phải mới của hệ thống phương trình (3.4) và xét hệ thống phương trình: 4 (0) (0) aij x j== a i6 , i 1;2;3;4 ( 3.16) j=1 Rõ ràng là: xjj= x +1, i = 1;2;3;4 ( 3.17)
  15. Thật vậy, thay (3.17) vào (3.16) do (3.4), ta nhân được: 44 (0) (0) aij x j=+ a ij( x j 1) jj==11 4 4 4 5 (0) (0) (0) (0) (0) (0) =aij x j +  a ij = ai5 +  a ij =  a ij = a i 6 , i = 1;2;3;4 j=1 j = 1 j = 1 j = 1 Vì đối với mỗi phần tử của cột  ta đều thực hiện những phép tính giống như đối với những phần tử của những cột bên trái cột và nằm trong cùng một hàng với phần tử của cột nên nếu không có sai số tính toán thì những phần tử của cột phải bằng tổng những phần tử tương ứng của những cột bên trái cột . Hiện tượng này được dùng để kiểm tra quá trình thuận. Quá trình ngược được kiểm tra bằng hệ thức (3.17). Sơ đồ Gaoxơ
  16. Nếu khi tính toán có sai số làm tròn thì bắt đầu từng hàng thứ 5 trở đi (trong sơ đố Gaoxơ) phần từ ờ cột  và tổng những phần tử cùng hàng và ở bên trái và bên trái được phép lệch nhau trong phạm vi giới hạn của sai số làm tròn đã phạm phải. một sự chênh lệch lớn chứng tỏ đã có sự nhầm lẫn trong quá trình tính toán Nhận xét: Sơ đồ Gaoxơ nêu trên hoàn toàn có thể mở rộng cho hệ thông n phương trình n ẩn số. Nếu ma trận hệ số A của hệ thống phương trình xuất phát đối xứng, nghĩa là aa ij = ji thì căn cứ vào các công thức (3.6), (3.8) và (3.9) dễ thấy rằng a(1)== a (1), a (2) a (2) ijji ij ji
  17. Nghĩa là những ma trận trung gian: (1) (1) (1) aaa22 23 24 (2) (1) (1) (1) (1) (1) (2) aa33 34 A== a32 a 33 a 34 , A aa(1) (1) (1) (1) (1) 43 44 aaa42 43 44 Cũng đối xứng. Do đặc điểm này, trong sơ đồ Gaoxơ, ta chỉ cần tính a (1) , a (2) j i vì vậy khối lượng tính toán sẽ giảm đi ij ij ( ) gân một nửa.
  18. 2.4. Khối lượng tính Xét hệ thống n phương trình n ẩn số. Căn cứ vào những công thức tính của pp Gaoxơ, ta đếm được số các phép tính cộng, trừ, nhân và chia S n cần phải thực hiện gồm (không kể các phép tính đối với các phần tử của cột kiểm tra  ): n( n−+ 1)(2 n 5) phép nhân 6 nn(+ 1) phép chia 2 n( n−+ 1)(2 n 5) phép cộng hoặc trừ 6 4n32+− 9 n 7 n S = phép tính. n 6
  19. Nếu ma trận hệ số của hệ thống phương trình đối xứng thì số các phép tính cộng, trừ, nhân và chia cần phải thực Sn hiện gồm : n( n−+ 1)( n 1) phép nhân 6 nn(+ 1) phép chia 2 n( n−+ 1)( n 1) phép cộng hoặc trừ 6 23n32++ n n S = phép tính. n 6 giảm hơn một nửa so với trường hợp ma trận hệ số A không đối xứng.
  20. 2.5. Sai số của pp Gaoxơ Nếu các phép tính cộng, trừ, nhân và chia làm đúng hoàn toàn và không phải làm tròn thì phương pháp Gaoxơ cho ta nghiệm đúng của hệ thống phương trình (3.1). Vì vậy phương pháp Gaoxơ là một phương pháp đúng. Tuy nhiên, trong tính toán, không tránh khỏi sai số làm tròn, cho nên trong thực tế, dùng phương pháp Gaoxơ ta cũng chỉ nhận được nghiệm gần đúng.
  21. Thí dụ: Dùng phương pháp Gaoxơ giải hệ thống pt sau : 2,0x1+ 1,0 x 2 − 0,1 x 3 + 1,0 x 4 = 2,7 0,4x1+ 0,5 x 2 + 4,0 x 3 − 8,5 x 4 = 21,9 (3.18) 0,3x1− 1,0 x 2 + 1,0 x 3 + 5,2 x 4 = − 3,9 1,0x1+ 0,2 x 2 + 2,5 x 3 − 1,0 x 4 = 9,9 Giải: Kết quả tính toán được ghi trong bảng (3.1). Từ bảng (3.1), ta nhận được nghiệm của hệ thống (3.18) là: Bảng 3.1
  22. 2.6. PP Gaoxơ có tìm trụ lớn nhất Quá trình Gaoxơ trình bày ở mục 2.1 sẽ không thực hiện được nếu một trong các trụ a (0) ,,, a (1) a (2) a (3) bằng không, dù 11 22 33 44 hệ thống phương trình có nghiệm duy nhất. Ngoài ra, nếu định thức của hệ thống phương trình khác không. Nhưng nếu một và phần tử trụ về trị tuyệt đối rất nhỏ so với những phần tử còn lại trong cùng hàng thì khi chia các phần tử ấy cho phần tử trụ, sai số làm tròn sẽ lớn , do đó có thể làm giảm nhiều độ chính xác của nghiệm tìm được.
  23. Để khắc phục những hạn chế vừa nêu, người ta thường dùng phương pháp Gaoxơ có tìm trụ lớn nhất. Nội dung phương pháp như sau: Sau khi khử x trong sơ đồ Gaoxơ, người ta chọn số lớn 1 nhất về trụ tuyệt đối trong các số aaaa (0) ,,, (0) (0) (0) làm trụ lớn 11 21 31 41 nhất và gọi là trụ lớn nhất thứ nhất. Sau đó ta hoán vị hàng chứa trụ lớn nhất thứ nhất với hàng thứ nhất nằm đúng ở hàng 1 cột 1 của sơ đồ Gaoxơ (nghĩa là ở hàng 1 cột 1 của ma trận hệ số A), và quá trình khử được tiến hành như ở mục 2.1a.
  24. x Khi khử 2 trong sơ đồ Gaoxơ, người ta chọn số lớn nhất về trị tuyệt đối trong các số aaa (1) ,, (1) (1) làm trụ thứ hai và gọi là trụ 22 32 42 lớn nhất thứ hai. Sau đó ta hoán vị hàng chưa trụ lớn nhất thứ a(1) hai với hàng chứa phần tử 22 để trụ lớn nhất thứ hai nằm đúng ở hàng 6 cột 2 của sơ đồ Gaoxơ (nghĩa là ở hàng 1 cột 1 của ma trận trung gian A (1) ) và quá trình khử x được tiến hành 2 như ở mục 2.1a. Tương tự cho x Chú ý: sơ đồ Gaoxơ3 có tìm trụ lớn nhất nêu trên hoàn toàn có thể áp dụng cho hệ thống n phương trình n ẩn. Thí dụ 3.doc
  25. 2.7. Tính định thức bằng pp Gaoxơ Để tính định thức: a a a a a a a a 11 12 13 14 11 12 13 14 a a a a a a a a det(A ) = 21 22 23 24 của ma trận A = 21 22 23 24 a a a a a a a a 31 32 33 34 31 32 33 34 a a a a a a a a 41 42 43 44 41 42 43 44 Ta áp dụng quá trình thuận của sơ đồ Gaoxơ trong đó không có cột số hạng tự do. Kết quả ta nhận được ma trận tam giác: 1 a(1) a (1) a (1) 12 13 14 01 aa( 2 ) ( 2 ) 23 24 B = 0 0 1 a( 3 ) 34 0 0 0 1
  26. Những phần tử của mt tam giác B lần lượt nhận được từ những phần tử của mt A và của những mt trung gian AAA (1) ,, ( 2 ) ( 3 ) ( 3 ) (ma trận ( 3 ) chỉ có một phần tử a ) bằng những phép biến đổi A 44 sơ cấp sau: a. Chia các hàng đầu của A và những mt trung gian AAA (1) ,, ( 2 ) ( 3 ) ( 3 ) ( A chỉ có một phần tử a ( 3 )) cho các trụ khác không 44 a(0)( a (0)= a ), a (1) , a (2) , a (3) 11 11 11 22 33 44 Khi đó định thức của mt A cũng phải chia cho các trụ trên. b. Trừ khỏi các hàng của ma trận A và của những ma trận trung gian AA (1) , ( 2 ) các hàng đầu nhận được từ phép biến đổi a của những ma trận ấy đã nhân với một số. Khi đó định thức của A không thay đổi giá trị.
  27. det(B )= 1.1.1.1 = 1 = det( A ) / a(0) . a (1) . a (2) . a (3) Vậy ta có: 11 22 33 44 Từ đó: det(A )= a(0) . a (1) . a (2) . a (3) (3.21) 11 22 33 44 Nếu ta áp dụng quá trình thuận của sơ đồ Gaoxơ có tìm trụ lớn nhất, thì mỗi lần hoán vị hai hàng với nhau, ta đã làm đổi dấu định thức của ma trận A det(A )=− ( 1)p a(0) . a (1) . a (2) . a (3) (3.22) 11 22 33 44 a( 0 ),, a (1) a ( 2 ) là các trụ lớn thứ nhất, thứ hai, thứ ba, p là số lần 11 22 33 phải hoán vị hai hàng.
  28. Nhận xét: 1.Những công thức (3.21), (3.22) hoàn toàn có thể mở rộng để tính định thức cấp n của ma trận vuông cấp n. 2.So với cách tính định thức bằng khai triển Laplaxơ, phương pháp Gaoxơ đòi hỏi ít phép tính nhiều hơn, nhất là khi n lớn. 3.Khi áp dụng phương pháp Gaoxơ giải hệ thống pt Ax = b ta có thể nhận được đồng thời nghiệm và định thức của ma trận hệ số A của hệ thống pt.
  29. Thí dụ 3.4 Dùng phương pháp Gaoxơ, tính định thức: 7,4 2,2− 3,1 0,7 =1,6 4,8− 8,5 4,5 4,7 7,0− 6,0 6,6 5,9 2,7 4,9− 5,3 Giải: Kết quả tính toán được ghi trong bảng 3.4. Cần lưu ý rằng, so với sơ đồ Gaoxơ, trong bảng 3.4 không có cột số hạng tự do. Từ bảng 3.4 ta nhận được: =7,4.4,32432.6,11332.( − 7,58387) = − 1483,6024
  30. x x x x  1 2 3 4 7,4 2,2 -3,1 0,7 7,2 1,6 4,8 -8,5 4,5 2,4 4,7 7,0 -6,0 6,6 12,3 5,9 4,9 4,9 -5,3 8,2 1 0,29730 -0,41892 0,09459 0,97297 4,32432 -7,82973 4,34866 0,84325 5,06269 -4,03180 6,15543 7,72704 0,94593 7,37163 -5,85808 2,45948 1 -1,81063 1,00563 0,45948 6,11332 0,52120 6,63452 9,08436 -6,80934 2,27502 1 0,08526 1,08526 -7,58387 -7,58387
  31. 2.8. Tính mt nghịch đảo bằng pp Gaoxơ Cho A là một ma trận vuông cấp n trên K. Ta bảo A là ma trận khả nghịch, nếu tồn tại một ma trận B vuông cấp n trên K sao cho: A.B = B.A = In. Khi đó, B được gọi là ma trận nghịch đảo của ma trận A, ký hiệu A-1. Như vậy: A.A-1= A-1.A= In Cho A là ma trận vuông cấp n trên K (n ≥ 2). Khi đó : Nếu A khả nghịch thì In nhận được từ A bởi một số hữu hạn các phép biến đổi sơ cấp dòng (cột); đồng thời, chính dãy các phép biến đổi sơ cấp dòng (cột) đó sẽ biến In thành nghịch đảo của ma trận A.
  32. Ma trận In có dạng sau: Ta thực hiện các bước sau đây : Bước 1: Lập ma trận n hàng, 2n cột bằng cách ghép thêm ma trận đơn vị cấp n I vào bên phải ma trận A
  33. Bước 2: Dùng các phép biến đổi sơ cấp dòng để đưa [ A|I ] về dạng [ A' | B ], trong đó A’ là một ma trận bậc thang chính tắc. Nếu A’ = In thì A khả nghịch và A-1 = B Nếu A’ ≠ In thì A không khả nghịch. Nghĩa là, trong quá trình biến đổi nếu A’ xuất hiện ít nhất 1 dòng không thì lập tức kết luận A không khả nghịch (không cần phải đưa A’ về dạng chính tắc) và kết thúc thuật toán. Nhận xét: Phương pháp này đều tính được ma trận vuông cấp n không suy biến. So với cách tính ma trận nghịch đảo bằng định thức, phương pháp nêu trên đòi hỏi ít phép tính hơn nhiều, lúc là khi n lớn. Thí dụ 3.5
  34. 2.9. Chuẩn của mt và chuẩn của pp vectơ Chuẩn của ma trận A = (aij) là một số thực ký hiệu A thoả mãn những điều kiện sau: a. A ³ 0 (AA= 0 Û = 0) b ,() aAARAA= a a Î - = c. ABAB+ £ + d ABAB£
  35. Người ta thường dùng ba chuẩn ma trận sau: A= m a x a 1 j å ij (chuẩn cột) i 1 æö2 2 ÷ Aa= ç ÷ (chuẩn Ơclit) 2 çå ij ÷ èøç ij. ÷ A= m a x a ¥ i å ij (chuẩn hàng) i
  36. 2.10. Sự không ổn định của hệ thống pt đstt Trong tính toán thực hành, ta có thể gặp những hệ thống phương trình đại số tuyến tính mà những thay đổi nhỏ trên các hệ số hoặc trên các phần tử ở vế phải của hệ thống phương trình sẽ gây ra những thay đổi rất lớn về nghiệm. Hệ thống phương trình như vậy gọi là hệ thống phương trình không ổn định trong tính toán. Nếu ngược lại, hệ thống phương trình gọi là ổn định trong tính toán.
  37. Thí dụ 3.8: Hệ thống phương trình: 2x1 + x2 = 2 2x1 + 1,01x2 = 2,01 Có nghiệm x1 = 0,5 và x2 = 1, trong khi đó hệ thống phương trình cới các hệ số của x1, x2 và vế phải của phương trình thứ hai thay đồi "đôi chút" ở chữ số lẻ thứ hai sau dấu phẩy: 2x1 + x2 = 2 2,01x1 + 1x2 = 2,05 Có nghiệm x1 = 5 và x2 = -8 (khác nhiều so với x1 = 0,5 và x2 = 1). Vậy hệ thống phương trình đã cho là một hệ thống phương trình không ổn định trong tính toán.
  38. Cách đơn giản nhất để nhận biết một hệ thống phương trình tuyến tính Ax = b có ổn định trong tính toán hay không là bên cạnh việc giải hệ thống phương trình đã cho, ta giải thêm hệ thống phương trình Ax = b1 với các phần tử của b1 sai khác các phần tử tương ứng của b rất ít. Nếu nghiệm của hệ thống phương trình này khác đáng kể so với nghiệm của hệ thống phương trình đã cho thì hệ thống phương trình đã cho không ổn định trong tính toán. Ngoài ra, người ta chứng minh được rằng đại lượng Cond(A) xác định bởi: Cond( A) = AA- 1
  39. (ở đây A là một chuẩn ma trận nào đó) do mức độ nhạy cảm của nghiệm x của hệ thống phương trình Ax = b đối với những thay đổi trên các phần tử của ma trận hệ số A và của vế phải b, nghĩa là do mức độ ổn định của hệ thống phương trình Ax = b Cond(A) lớn chứng tỏ hệ thống phương trình Ax = b không ổn định trong tính toán Cond(A) càng gần 1, hệ thống phương trình Ax = b càng ổn định trong tính toán.
  40. æö ç21÷ Trở lại các thí dụ 3.8 và 3.9 ta thấy rằng đối với: A = ç ÷ 1 ç2 1,01÷ æö èø 21÷ Cond A == A ç ÷ ( 1) 1 ç ÷ èøç2 1,01÷ æö10 7 8 7 ç ÷ ç ÷ ç 7 5 6 5 ÷ còn đối với: A = ç ÷ 2 ç 8 6 10 9 ÷ ç ÷ ç ÷ èøç 7 5 9 10÷ Thì Cond(A2) = 2984,108
  41. æö 50,5- 50÷ A - 1 = ç ÷ Chú ý rằng định thức của mt A1 là 0,02 và: 1 ç ÷ èøç- 100 100 ÷ Nhưng định thức của ma trận đối xứng A2 là 1 và: æö ç 25 41 10 6÷ ç ÷ ç 41 68 17 10 ÷ Cũng là một ma trận đối xứng. A - 1 = ç ÷ 2 ç 10 17 5 3÷ ç ÷ ç ÷ èøç 6 1 3 2 ÷
  42. Để nâng cao độ chính xác của nghiệm khi giải hệ thống phương trình không ổn định trong tính toán, người ta có thể dùng độ chính xác kép đối với các phép tính trung gian nhưng biện pháp này tốn nhiều thời gian tính toán, do đó không tính tế. Một biện pháp khác là dùng quá trình lặp sau: Xét hệ thống phương trình: ïì a x+ a x + a x + a x = b ï 11 1 12 2 13 3 14 4 1 ï a x+ a x + a x + a x = b íï 21 1 22 2 23 3 24 4 2 3 . 23 ï a x+ a x + a x + a x = b ( ) ï 31 1 32 2 33 3 33 4 3 ï a x+ a x + a x + a x = b îï 41 2 42 2 42 3 44 4 4
  43. Giả sử x 1 ,,, x 2 x 3 x 4 là nghiệm gần đúng tìm được. Thay chúng vào vế trái của (3.23) nhận được những giá trị mới của b1, b2, b3, b4 là b1,,, b 2 b 3 b 4 nghĩa là: ì ï a x1+ a x 2 + a x 3 + a x 4 = b 1 ï 11 12 13 14 ï ï a21 x1+ a 22 x 2 + a 23 x 3 + a 24 x 4 = b 2 í 3 . 24 ï ( ) ï a31 x1+ a 32 x 2 + a 33 x 3 + a 34 x 4 = b 3 ï ï a x1+ a x 2 + a x 3 + a x 4 = b 4 îï 41 42 43 44
  44. Đem mỗi phương trình của (2.23) trừ phương trình tương ứng của (3.24), nhận được: ïì a e+ a e + a e + a e = d ï 11 1 12 2 13 3 14 4 1 ï a e+ a e + a e + a e = d íï 21 1 22 2 23 3 24 4 2 3 . 25 ï a e+ a e + a e + a e = d ( ) ï 31 1 32 2 33 3 34 4 3 ï a e+ a e + a e + a e = d îï 41 1 42 2 43 3 44 4 4 Trong đó ei= x i - xii, d i = b i - b ( i = 1,4) Bây giờ, ta giải hệ thống pt (3.25) đối với e1, e2, e3 và e4. do ei= x i - xii Þ x i = x + e i ( i = 1,4) Là nghiệm gần đúng tốt hơn của (3.23). Để nâng cao hơn nữa độ chính xác của nghiệm, ta có thể lặp lại quá trình trên.
  45. BÀI 3. NHỮNG PHƯƠNG PHÁP LẶP • 3.1. PP lặp đơn • 3.2. PP lặp dâyđen • 3.3. Đưa hệ thống phương trình tuyến tính về dạng thỏa mãn điều kiện hội tụ của phương pháp lặp đơn hoặc phương pháp lặp Dây đen:
  46. 3.1. PP lặp ñôn a.Noäi dung phöông phaùp Xeùt heä thoáng phöông trình Ax= b (3.2) Ñöa (3.2) veà daïng töông ñöông sau xx=+ (3.34)  11 12 1n 1  == 21 22 2n ; 2 n12 n nn  n
  47. Sau ñoù ta töï cho moät vectô, goïi laø vectô xaáp xæ ñaàu, kyù hieäu laø xx(00) ()( ) =  roài tính daàn theo coâng thöùc: x(kk+1) = + ax( ) , k = 0, 1, 2, (3.35) veùctô x(k) goïi laø vectô laëp thöù k. Neáu daõy nhöõng vectô laëp x(01) , x( ) , , x(k) , , coù gi ôù i han ï : x* = lim x(k) k→ thì giôùi haïn aáy laø nghieäm ñuùng cuûa heä thoáng , vaø ñoù cuõng laø nghieäm cuûa heä thoáng (3.2). Thaät vaäy, ta coù: limx(k+1) = lim + x( k) =  + lim x( k) k→ k → ( ) k → hay : xx =+
  48. b.Söï hoäi tuï cuûa phöông phaùp Ngöôøi ta chöùng minh ñöôïc raèng quaù trình laëp ñôn hoäi tuï ñeán nghieäm duy nhaát cuûa heä thoáng phöông trình (3.2), khoâng phuï thuoäc vaøo vieät luïa choïn vectô xaáp xæ ñaàu (nghóa laø x ( 0 ) chon tuøy yù), neáu: 1(3.36) p
  49. c. Ñaùnh giaù sai soá cuûa gaàn ñuùng Ñeã ñaùnh giaù ñoä leäch giöõa nghieäm gaàn ñuùng x ( k ) nhaän ñöôïc baèng phöông phaùp laëp ñôn, vaø nghieäm ñuùng x * cuûa heä thoáng (3.2), ngöôøi ta chöùng minh ñöôïc nhöõng coâng thöùc sau: x(k) − x* p x( k) − x( k−1) (3.37) pp1− p k k ( p ) 10 va:ø x( ) − x* x( ) − x( ) (3.38) pp1− p
  50. Töø (3.38) deã thaáy raèng söï hoäi tuï cuûa phöông phaùp laép ñôn caøng nhanh neáu caøng beù. Baát ñaúng thöùc (3.38) cuõng p cho pheùp, sau laàn laëp thöù nhaát (sau khi bieát ñöôïc x ( 1 ) ) xaùc ñònh ñöôïc soá laàn laëp can tieán haønh K (  ) ñeå nhaän ñöôïc nghieäm gaàn ñuùng x ( k ) ñaït ñoä chinh xaùc  Trong tröôøng hôïp 1 ñaùnh giaù(3.37) coù daïng ñôn giaûn sau: p 2 x(k) − x* x( k) − x( k−1) (3.39) pp Chuù yù: . neâu trong muïc b vaø c coù theå duøng p . hoacë . hoaëc . 12 Ví dụ 3.10
  51. 3.2) PP lặp Dâyđen a) Nội dung phương pháp Xét hệ thống phương trình (3.2). Đưa (3.2) về dạng tương đương sau: xx=+  11 12 1n 1  == 21 22 2n ; 2 n12 n nn  n n hay: x1= 1 + ij xj ( i = 1,2, , n) j=1
  52. Sau ñoù ta töï cho moät vectô, goïi laø vectô xaáp xæ ñaàu, kyù hieäu laø xx(00) ()( ) =  roài tính daàn theo coâng thöùc: n (kk+ 1) ( ) xx1=+ 1 1 jj j=1 n (k++ 1) ( k 1) ( k ) x2= 2 + 21 x 1 +  2 jj x (3.4) j=2 in−1 (k++ 1) ( k 1) ( k ) xi= i + ij x j + ij x j jj==11 n−1 (kk++ 1) ( 1) xn= n + nj x j + nn x n , k = 0,1, j=1
  53. Đó là phương pháp lặp Dâyđen, phương pháp này có thể xem là một biến dạng của phương pháp lặp đơn. Phương pháp lặp Dâyđen khác phương pháp lặp đơn ở chỗ: khi tính thành (k+ 1) phần thứ i của vectơ lặp thứ k +1: x 1 ta sử dụng ngay những thành phần ( k + 1) ( k + 1) ( k + 1) vừa tính được. x1, x 2 , , xi− 1 Hoàn toàn giống phương pháp lặp đơn, dễ chỉ ra rằng nếu dãy những vectơ lặp x ( 01 ) , x ( ) , , x ( k ) , có giới hạn thì giới hạn ấy là nghiệm đúng của hệ thống (3.26) và do đó cũng là nghiệm đúng của (3.2).
  54. b) Sự hội tụ của phương pháp Điều kiện hội tụ của phương pháp lặp Dâyđen hoàn toàn giống điều kiện hội tụ của phương pháp lặp đơn. c) Đánh giá sai số của nghiệm gần đúng (k) Để đánh giá độ lệch giữa nghiệm gần đúng x nhận được bằng phương pháp lặp Dâyđen và nghiệm đúng x * của hệ thống phương trình (3.2), người ta chứng minh được những công thức sau:
  55.  Đối với .: x(k )− x − x ( k ) − x ( k 1) (3.35) q 1−   ==maxi , i 1,2, , n i 1− p i in−1 pq== ; iijj==11ij ij (k )k (1) (0) và x− x x − x (3.36) 1−
  56. p Đối với .:x(k )− x − x ( k ) − x ( k 1) (3.37) 1 11(1−−sp )(1 ) n t j Trong đó : s= m ax ij ; p = m ax , j = 1, n jj ( ) jk=+1 1− s j j n tjj= ij; s = ij ,( j = 1, n − 1) i=11 i = j + n stn==0; n in i=1 pk Và : x(k )− x x (1) − x (0) (3.38) 11(11−−sp)( ) Đối với .: ta không xét vì phức tạp. 0
  57. Nhận xét: (k+ 1) Khi tính x i ( 1 i n ) bằng phương pháp lặp Dâyđen ()()()k k k (công thức (3.34)), ta không dùng x 1 , x 2 , , x i − 1 (k+ 1) ( k + 1) ( k + 1) mà dùng ngay x 1 , x 2 , , x i − 1 vừa tính được, vì vậy (k+ 1) k sau khi tính xong x i ta không cần giữ lại x i nữa và có thể đặt ( k + 1) vào ô nhớ của pháp lặp Dâyđen thay cho 2n ô xi nhớ đối với phương pháp lặp đơn. Đây chính là ưu điểm của phương pháp lặp Dâyđen so với phương pháp lặp đơn khi n lớn.
  58. Thí dụ 3.11. Dùng phương pháp lặp Dâyđen, tìm nghiệm gần đúng của hệ thống phương trình: 4x += 0,24x – 0,08x 8 1 2 3 0,09x1 += 3x 2 – 0,15x 3 9 0,04x1 – 0,08x 2 += 4x 3 20 Giải: 1) Theo kết quả ở thí dụ 3.10, ta có x = 2 − 0,06x + 0,02x 1 2 3 x2 =+ 3 – 0,03x 1 0,05x 3 ( 3.32) x3 =+ 5 – 0,01x 1 0,02x2 và : = 0,08 1. Vậy quá trình lặp Dâyđen áp dụng vào hệ thông (3.3) sẽ hội tụ:
  59. 2 x(0) == 3 2) Chọn: 5 Và tính xx ( 12 ) , ( ) , bằng công thức lặp (3.34) ta nhận được bảng kết quả sau: ()k ()k ()k k x1 x2 x3 0 2 3 5 1 1,92 3,1924 5,044648 2 1,9093489 3,194952 5,0448056 3 1,909119 3,1949643 5,0448073
  60. 3) Xem x 3 là nghiệm gần đúng phải tìm, ta có thể đánh giá sai số phạm phải của theo (3.35): (3)(2)(3)(2) xxmxx− − ax ii i == max( 0,0001499; 0,0000123;0,0000017 0,000) 1499 q  ===maxmaxi 0,08; 0,0515463( 0,08 ) i 1− pi  Vàxxxx : 0,000013(3)(3)(2)− −= 1− 
  61. Qua thí dụ này ta thấy rằng nếu lấy x 3 làm nghiệm gần đúng phải tìm thì phương pháp lặp Dâyđen cho ta kết quả tốt hơn phương pháp lặp đơn. Tổng quát, người ta chứng minh được kết quả sau: “Nếu phương pháp lặp đơn hội tụ thì phương pháp lặp Dâyđen cũng hội tụ và phương pháp lặp Dâyđen hội tụ nhanh hơn.
  62. 3.3. Đưa hệ thống PTTT về dạng thỏa mãn điều kiện hội tụ của PP lặp đơn hoặc PP lặp Dây đen: Muốn giải hệ thống phương trình Ax = b bằng phương pháp lặp đơn hoặc phương pháp lặp Dâyđen, ta phải đưa về dạng tương đương xx=+  11 12 1n 1  == 21 22 2n ; 2 n12 n nn  n
  63. nn sao cho: 1i = 1, n h ay : 1 j = 1, n ij( ) ij ( ) ji==11 (Ở đây, ta chỉ xét chuẩn hàng hoặc chuẩn cột của ma trận ). Khi đó dãy những vectơ lặp x ( 12 ) , x ( ) , , x ( n ) nhận được từ PP lặp đơn hoặc PP lặp Dâyđen sẽ hội tụ đến nghiệm duy nhất của hệ thống phương trình đã cho khi n → + không phụ thuộc vào việc lựa chọn vectơ xấp xỉ đầu (nghĩa là x ( 0) chọn tùy ý). Đối với hệ thống phương trình đầu: n Axbhay= ax = bi =1, n  ij j i ( ) j=1 phương pháp lặp đơn hoặc phương pháp lặp Dâyđen sẽ hội tụ nếu điều kiện sau được thỏa mãn: a = a i1, n (*) ii ij ( ) ji
  64. Nghĩa là trị tuyệt đối của hệ số chéo của mỗi phương trình của hệ thống (đó là hệ số nằm trên đường chéo chính của ma trận hệ số A của hệ thống phương trình) phải lớn hơn tổng trị tuyệt đối của hệ số còn lại của phương trình (không kể số hạng tự do của phương trình), vì khi đó có thể đưa hệ thống về dạng tương đương xx =+  với các hệ số ij thỏa mãn điều kiện hội tụ. Nếu hệ thống phương trình Ax = b đã cho bất kì (nghĩa là không thỏa mãn điều kiện (*)) thì bằng cách dùng những biến đổi sơ cấp thích hợp, ta có thể đưa hệ thống về dạng thỏa mãn điều kiện (*). Cách làm như sau:
  65. Từ hệ thống pt đã cho, ta lấy ra những pt mà hệ số của chúng thỏa mãn điều kiện (*), sau đó ta xếp các pt ấy vào các hàng của hệ thống pt mới sao cho hệ số có trị tuyết đối lớn nhấ của mỗi pt chính là phần tử nằm trên đường chéo chính là phần tử nằm trên đường chéo chính của ma trận hệ số của hệ thống pt mới. Từ những pt đã và chưa được dùng đến của hệ thống pt ban đầu, ta thành lập những tổ hợp tuyến tính, độc lập tuyến tính với nhau, để tạo nên những pt thỏa mãn nguyên tắc lựa chọn nêu trên và xếp chúng vào những vị trí thích hợp của những hàng còn lại của hệ thống pt mới, với chú ý rằng mỗi pt chưa được dùng đến của hệ thống pt ban đầu phải có mặt trong một tổ hợp tuyên tính để tạo nên một pt nằm trong những hàng còn lại của hệ thống phương trình mới.
  66. Thí dụ: Đưa hệ thống pt sau về dạng thỏa mãn điều kiện hội tự của PP lặp đơn hoặc PP lặp Dâyđen. 2x1+ 3 x 2 − 4 x 3 + x 4 = 3 ( A ) x−2 x − 5 x + x = 2 ( B ) 1 2 3 4 (1) 5x− 3 x + x − 4 x = 1 ( C ) 1 2 3 4 10x1+ 2 x 2 − x 3 + 2 x 4 = − 4 ( D ) 1) Trong pt (B), hệ số của x 3 có trị tuyệt đối lớn hơn tổng trị tuyệt đối của những hệ số còn lại (không kể những số hạng tự do), do đó ta xếp pt (B) vào hàng thứ ba của hệ thống phương trình mới: x1−2 x 2 − 5 x 3 + x 4 = 2 ( III) Hệ số của x 1 trong pt (D) có trị tuyết đối cũng thỏa mãn điều kiện (*), vậy có thể xếp pt (D) vào hàng thứ nhất của hệ thống pt mới: 10x1+ 2 x 2 − x 3 + 2 x 4 = − 4 (I)
  67. 2. Căn cứ vào hệ thống pt đã cho, dễ thấy rằng để nhận được pt thứ hai của hệ thống pt mới với hệ số của x 2 có trị tuyệt đối thỏa điều kiện (*), ta thành lập tổ hợp tuyến tính (A) – (B) và có: x1+5 x 2 + x 3 + 0 x 4 = 1 ( II) Như vậy, trong hệ thống pt mới đã có sự tham gia của các pt(A), (B), và (D), do đó trong pt thứ tư của hệ thống pt mới bắt buộc phải có sự góp mặt của pt(C). Muốn thế, ta có thể lập tổ hợp tuyến tính 2(A) – (B) + 2(C) – (D) và nhận được: 3x1+ 0 x 2 + 0 x 3 − 9 x 4 = 10 ( IV)
  68. 3. Kết quả ta nhận được hệ thống phương trình (I), (II), (III) và (IV), tương đương với hệ thống phương trình ban đầu và thỏa mãn điều kiện (*). Bây giờ ta chia hai vế của phương trình (I) cho 10, hai vế của phương trình (II) cho 5, hai vế của phương trình (III) cho -5 và hai vế của phương trình (IV) cho - 9 và nhận được hệ thống phương trình tương đương sau: x1=0 x 1 − 0,2 x 2 + 0,1 x 3 − 0,2 x 4 − 0,4 x= −0,2 x + 0 x − 0,2 x + 0 x + 0,2 2 1 2 3 4 (2) x=0,2 x − 0,4 x + 0 x + 0,2 x − 0,4 3 1 2 3 4 x4=0,333 x 1 + 0 x 2 + 0 x 3 + 0 x 4 − 1,111 0−− 0,2 0,1 0,2 −−0,2 0 0,2 0 = 0,2− 0,4 0 0,2 0,333 0 0 0
  69. 4 =max = max(0,5;0,4;0,8;0,333) = 0,8 1 i  ij j=1 Vậy ta có thể dùng phương pháp lặp đơn hoặc phương pháp lặp Dâyđen đối với hệ thống phương trình (2) để tìm nghiệm gần đúng của hệ thống phương trình (1).
  70. Bài tập 1. Dùng PP Gaoxơ giải những hệ thống PT Ax = b cho dưới đây. Các phép tính lấy đến 5 số lẻ sau dấu phẩy: 1,50,20,10,4− aAb.0,11,50,1=−−= ;0,8 −−0,30,20,50,2 8,302,624,101,9010,65 − 3,928,457,782,4612,21 bAb.;== 3,777,218,042,2815,45 2,213,651,696,998,35 −
  71. a. Kết quả tính toán được ghi trong bảng sau: Số hạng Quá trình x1 x2 x3 tự do  1,5 -0,2 0,1 0,4 1,8 -0,1 1,5 -0,1 0,8 2,1 -0,3 0,2 -0,5 0,2 -0,4 1 -0,13333 0,06667 0,26667 1,2 Quá 1,48667 -0,09333 0,82667 2,22 trình 0,16000 -0,47999 0,28000 -0,04 thuận 1 -0,06278 0,55605 1,49327 -0,46995 0,19103 -0,27892 1 -0,40649 0,59351 -0,40649 0,59351 Quá 1 1 1 0,53053 1,53053 trình 0,36450 1,36450 nghịch
  72. Từ bảng trên ta nhận được nghiệm của hệ thống phương trình là: x1=0,36450; x 2 = 0,53053; x 3 = − 0,40649 b. Kết quả tính toán được ghi trong bảng sau:
  73. Số hạng Quá x1 x2 x3 x4 tự do  trình 8,3 2,62 4,1 1,9 -10,65 6,27 3,92 8,45 7,78 2,46 12,21 55,574 3,77 7,21 8,04 2,28 15,45 36,75 2,21 3,65 1,69 6,99 -8,35 6,13 1 0,31566 0,49398 0,22892 -1,28313 0,75542 7,21261 5,84359 1,56263 17,23987 31,8587 6,01996 6,17769 1,41697 20,2874 33,90202 2,95239 0,59830 6,48409 -5,51428 4,5205 Quá 1 0,81019 0,21665 2,39024 4,41708 Trình thuận 5,89825 1,30038 0,11275 7,31138 - -1,79369 5,84445 -8,52044 12,57120 1 0,08671 4,53579 5,62284 5,99998 -4,43539 1,56459
  74. Số hạng Quá trình x1 x2 x3 x3 tự do  -0,73923 0,26077 Quá 4,59989 5,59989 1 1 1 1 trình -1,17639 -0,17639 nghịch -3,01482 -2,01482 Từ bảng trên ta nhận được nghiệm của hệ thống phương trình là: x1= −3,01482; x 2 = − 1,17639; x 3 = 4,59989; x 4 = − 0,73923
  75. 2. Dùng phương pháp Gaoxơ có tìm trụ lớn nhất, giải những hệ thống phương trình Ax = b cho dưới đây. Các phép tính lấy đến 5 chữ số có nghĩa: 2,6−− 4,5 2,0 19,07 a. A== 3,0 3,0 4,3; b 3,21 −−6,0 3,5 3,0 18,25 3,81 0,25 1,28 0,75 4,21 2,25 1,32 4,58 0,49 6,47 b.; A== b 5,31 6,28 0,98 1,04 2,38 9,39 2,45 3,35 2,28 10,48 Giải: a. Kết quả tính toán được ghi trong bảng sau:
  76. Số hạng tự Quá trình x1 x2 x3 do  2,6 -4,5 -2,0 19,07 15,17 3,0 3,0 4,3 3,21 13,51 -6,0 3,5 3,0 -18,25 -17,75 -6,0 3,5 3,0 -18,25 -17,75 3,0 3,0 4,3 3,21 13,51 2,6 -4,5 -2,0 19,07 15,17 1 -0,58333 -0,5 3,0417 2,9583 Quá trình 4,7499 5,8 -5,9151 4,6351 thuận -2,9833 -0,7 11,162 7,4784 1 1,2211 -1,2453 0,97583 2,9429 7,4469 10,389 1 2,5305 3,5305 2,5305 3,5305 Quá trình 1 1 1 -4,3353 -3,3353 nghịch
  77. Từ bảng trên ta nhận được nghiệm của hệ thống phương trình là: x1=1,7780; x 2 = − 4,3353; x 3 = 2,5305