›
›

Bài giảng Phương pháp tính - Chương 2: Hệ phương trình tuyến tính - Nguyễn Hồng Lộc

pdf 78 trang haiha333 08/01/2022 5911
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Phương pháp tính - Chương 2: Hệ phương trình tuyến tính - Nguyễn Hồng Lộc", để 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:

  • pdfbai_giang_phuong_phap_tinh_chuong_2_he_phuong_trinh_tuyen_ti.pdf

Nội dung text: Bài giảng Phương pháp tính - Chương 2: Hệ phương trình tuyến tính - Nguyễn Hồng Lộc

  1. HỆ PHƯƠNG TRÌNH TUYẾN TÍNH Bài giảng điện tử Nguyễn Hồng Lộc Trường Đại học Bách Khoa TP HCM Khoa Khoa học ứng dụng, bộ môn Toán ứng dụng TP. HCM — 2013. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 1 / 76
  2. Đặt vấn đề Đặt vấn đề Trong chương này, chúng ta sẽ học một số phương pháp giải hệ phương trình đại số tuyến tính  a x + a x + + a x + + a x = b  11 1 12 2 1i i 1n n 1   ai1x1 + ai2x2 + + aii xi + + ainxn = bi     an1x1 + an2x2 + + ani xi + + annxn = bn (1) thường xuất hiện trong các bài toán kỹ thuật. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 2 / 76
  3. Đặt vấn đề Ta chỉ xét hệ gồm n phương trình và n ẩn số, trong đó A = (aij ) ∈ Mn(K) và detA =6 0. Do đó hệ sẽ có nghiệm duy nhất X = A−1B. Tuy nhiên, việc tìm ma trận nghịch đảo A−1 đôi khi còn khó khăn gấp nhiều lần so với việc giải trực tiếp hệ phương trình (1). Do đó cần phải có phương pháp để giải hệ (1) hiệu quả. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 3 / 76
  4. Phương pháp Gauss Hệ phương trình tương đương Sử dụng phép biến đổi sơ cấp trên hàng để giải hệ Xét hệ phương trình tuyến tính gồm n phương trình và n ẩn  a x + a x + + a x + + a x = b  11 1 12 2 1j j 1n n 1   ai1x1 + ai2x2 + + aij xj + + ainxn = bi     an1x1 + an2x2 + + anj xj + + annxn = bn Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 4 / 76
  5. Phương pháp Gauss Hệ phương trình tương đương Nếu thực hiện các phép biến đổi sơ cấp sau trên hệ (1): 1 Đổi chỗ các phương trình của hệ (hi ↔ hj ) hay ci ↔ cj có đánh số lại các ẩn. 2 Nhân vào một phương trình của hệ một số λ =6 0(hi → λhi ). 3 Cộng vào một phương trình của hệ một phương trình khác đã được nhân với một số (hi → hi + λhj ) thì ta sẽ được một hệ phương trình mới tương đương với hệ (1). Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 5 / 76
  6. Phương pháp Gauss Hệ phương trình tương đương   a a a b 11 12 1n 1   BĐ sơ cấp trên hàng  a21 a22 a2n b2    −−−−−−−−−−−−−−→   an1 an2 ann bn   c c c d 11 12 1n 1    0 c22 c2n d2    với   0 0 cnn dn cii =6 0, i = 1, 2, , n. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 6 / 76
  7. Phương pháp Gauss Phương pháp Gauss Phương pháp Gauss 1 Viết ma trận mở rộng AB = (A|B) của hệ (1). 2 Dùng các phép biến đổi sơ cấp trên hàng biến đổi ma trận mở rộng về ma trận bậc thang. 3 Viết hệ phương trình tương ứng với ma trận bậc thang. 4 Ta giải hệ phương trình ngược từ dưới lên, tìm biến xn sau đó xn−1, , x1 ta được 1 nghiệm duy nhất. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 7 / 76
  8. Phương pháp Gauss Phương pháp Gauss Ví dụ Giải hệ phương trình  x + 2x + 2x = 9  1 2 3 2x1 + 4x2 + 9x3 = 23  3x1 + 7x2 + 8x3 = 31 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 8 / 76
  9. Phương pháp Gauss Phương pháp Gauss Giải.     1 2 2 9 h2→h2−2h1 1 2 2 9 h3→h3−3h1  2 4 9 23  −−−−−−→  0 0 5 5  3 7 8 31 0 1 2 4    1 2 2 9 x1 = 3 h2↔h3  −−−→  0 1 2 4  ⇔ x2 = 2 0 0 5 5  x3 = 1 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 9 / 76
  10. Phương pháp Gauss Phương pháp Gauss-Jordan Phương pháp Gauss-Jordan Định nghĩa Phần tử trội là phần tử có trị tuyệt đối lớn nhất, sao cho không cùng hàng và cột với những phần tử đã chọn trước. Phương pháp Gauss-Jordan 1 Chọn phần tử trội để biến đổi cho tất cả các phần tử trên cùng cột của phần tử trội bằng không. 2 Qua n bước ta sẽ tìm được nghiệm cần tìm. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 10 / 76
  11. Phương pháp Gauss Phương pháp Gauss-Jordan Ví dụ Giải hệ phương trình   x1 − x2 + 2x3 − x4 = −8   2x1 − 2x2 + 3x3 − 3x4 = −20  x1 + x2 + x3 + 0x4 = −2   x1 − x2 + 4x3 + 3x4 = 4   1 −1 2 −1 −8    2 −2 3 −3 −20  Giải.    1 1 1 0 −2  1 −1 4 3 4 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 11 / 76
  12.   1 −1 0 −5 −20    5 −5 0 −21 −92     3 5 0 −3 −12  1 −1 4 3 4 Phương pháp Gauss Phương pháp Gauss-Jordan Chọn phần tử trội là a43 = 4. Thực hiện các phép biến đổi sơ cấp h3→4h3−h4 h2→4h2−3h4 h →2h −h −−−−−−−→1 1 4 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 12 / 76
  13. Phương pháp Gauss Phương pháp Gauss-Jordan Chọn phần tử trội là a43 = 4. Thực hiện các phép biến đổi sơ cấp   h3→4h3−h4 1 −1 0 −5 −20 h →4h −3h 2 2 4   h1→2h1−h4  5 −5 0 −21 −92  −−−−−−−→    3 5 0 −3 −12  1 −1 4 3 4 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 12 / 76
  14. Phương pháp Gauss Phương pháp Gauss-Jordan Chọn phần tử trội không được nằm trên hàng 4 và cột 3 là phần tử a24 = −21. Thực hiện các phép biến đổi sơ cấp   h1→21h1−5h2 −4 4 0 0 40 h →7h −h 3 3 2   h4→7h4+h2  5 −5 0 −21 −92  −−−−−−−→    16 40 0 0 8  12 −12 28 0 −64 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 13 / 76
  15. Phương pháp Gauss Phương pháp Gauss-Jordan Chọn phần tử trội không được nằm trên hàng 4,2 và cột 3,4 là phần tử a32 = 40. Thực hiện các phép biến đổi sơ cấp   h1→10h1−h3 −56 0 0 0 392 h →8h +h 2 2 3   h4→10h4+3h3  56 0 0 −168 −728  −−−−−−−→    16 40 0 0 8  168 0 280 0 −616 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 14 / 76
  16. Phương pháp Gauss Phương pháp Gauss-Jordan Chọn phần tử trội không được nằm trên hàng 4,2,3 và cột 3,4,2 là phần tử a11 = −56. Thực hiện các phép biến đổi sơ cấp   h2→h2+h1 −56 0 0 0 392 h →7h +2h 3 3 1   h4→h4+3h1  0 0 0 −168 −336  −−−−−−−→    0 280 0 0 840  0 0 280 0 560 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 15 / 76
  17. Phương pháp Gauss Phương pháp Gauss-Jordan Vậy hệ đã cho tương đương với hệ sau   −56x = 392 x = −7  1  1  −168x = −336  x = 3 4 ⇔ 2  280x2 = 840  x3 = 2    280x3 = 560  x4 = 2 Suy ra hệ đã cho có 1 nghiệm duy nhất (x1, x2, x3, x4) = (−7, 3, 2, 2) Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 16 / 76
  18. Phương pháp Gauss Bài tập Bài tập Bài 1. Sử dụng phương pháp phần tử trội giải hệ phương trình  2x − 1.5x + 3x = 1  1 2 3 −x1 + 2x3 = 3  4x1 − 4.5x2 + 5x3 = 1 Đáp số (x1, x2, x3) = (−1, 0, 1) Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 17 / 76
  19. Phương pháp nhân tử LU Những khái niệm cơ bản Những khái niệm cơ bản Định nghĩa   a11 a12 a1n  0 a a  Ma trận vuông A =  22 2n  được  . . .   . . .  0 0 ann gọi là ma trận tam giác trên. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 18 / 76
  20. Phương pháp nhân tử LU Những khái niệm cơ bản Định nghĩa   a11 0 0 0  a a 0  Ma trận vuông  21 22  được gọi là  . . .   . . .  an1 an2 ann ma trận tam giác dưới. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 19 / 76
  21. Phương pháp nhân tử LU Nội dung phương pháp Nội dung phương pháp Nội dung của phương pháp nhân tử LU là phân tích ma trận A thành tích của 2 ma trận L và U, trong đó L là ma trận tam giác dưới, còn U là ma trận tam giác trên. Khi đó việc giải hệ (1) sẽ trở thành giải 2 hệ phương trình LY = B và UX = Y . Có nhiều phương pháp phân tích A = LU, tuy nhiên ta thường xét trường hợp L có đường chéo chính bằng 1 và gọi là phương pháp Doolittle. Khi đó L và U có dạng Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 20 / 76
  22. Phương pháp nhân tử LU Nội dung phương pháp   1 0 0 0  ` 1 0  L =  21   . . .   . . .  `n1 `n2 1 ,   u11 u12 u1n  0 u u  U =  22 2n   . . .   . . .  0 0 unn Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 21 / 76
  23. Phương pháp nhân tử LU Nội dung phương pháp Các phần tử của 2 ma trận L và U được xác định theo công thức  u = a (1 j n)  1j 1j 6 6  ai1  `i1 = (2 6 i 6 n)  u11  i−1 P uij = aij − `ikukj (1 < i 6 j)  k=1   j−1   1 P  `ij = aij − `ikukj (1 < j < i)  uij k=1 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 22 / 76
  24. Phương pháp nhân tử LU Nội dung phương pháp Ví dụ Giải hệ phương trình  2x + 2x − 3x = 9  1 2 3 −4x1 − 3x2 + 4x3 = −15  2x1 + x2 + 2x3 = 3 Giải.       2 2 −3 1 0 0 u11 u12 u13  −4 −3 4  =  `21 1 0  .  0 u22 u23  2 1 2 `31 `32 1 0 0 u33 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 23 / 76
  25. Phương pháp nhân tử LU Nội dung phương pháp     2 2 −3 h2→h2+2h1 2 2 −3 h3→h3−1h1  −4 −3 4  −−−−−−→  0 1 −2  2 1 2 0 −1 5  2 2 −3  h3→h3+1h2 −−−−−−→  0 1 −2  = U 0 0 3  1 0 0  L =  −2 1 0  1 −1 1 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 24 / 76
  26. Phương pháp nhân tử LU Nội dung phương pháp       1 0 0 y1 9 Do đó LY = B ⇔  −2 1 0   y2  =  −15  1 −1 1 y3 3 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 25 / 76
  27. Phương pháp nhân tử LU Nội dung phương pháp  9  ⇒ Y = L−1B =  3  −3       2 2 −3 x1 9 UX = Y ⇔  0 1 −2   x2  =  3  0 0 3 x3 −3  2  ⇒ X = U−1Y =  1  −1 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 26 / 76
  28. Phương pháp nhân tử LU Nội dung phương pháp Định nghĩa Định thức con chính cấp k của ma trận A là định thức có được từ ma trận con chính cấp k(ma trận có được từ giao của k hàng đầu và k cột đầu của A), ký hiệu Dk  2 2 3  Ví dụ: A =  3 5 2 , D1(A) = 2 5 7 7 2 2 3 2 2 D2(A) = = 4, D3(A) = 3 5 2 = 8 3 5 5 7 7 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 27 / 76
  29. Phương pháp nhân tử LU Nội dung phương pháp   a11 a12 a1n  a a a   21 22 2n  =  . . .   . . .  an1 an2 ann     1 0 0 0 u11 u12 u1n      `21 1 0   0 u22 u2n   . . .   . . .   . . .   . . .  `n1 `n2 1 0 0 unn Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 28 / 76
  30. Phương pháp nhân tử LU Nội dung phương pháp Từ tính chất của tích ma trận tam giác dưới và ma trận tam giác trên Dk(L)Dk(U) = Dk(A) ⇒ U11U22 Ukk = Dk(A) Dk (A) ⇒ {U11 = D1(A); Ukk = , k > 1} Dk−1(A)  2 2 −3  Ví dụ: A =  −4 −3 4  2 1 2 D1(A) = 2, D2(A) = 2, D3(A) = 6 D2(A) D3(A) ⇒ U11 = 2; U22 = = 1; U33 = = 3 D1(A) D2(A) Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 29 / 76
  31. Phương pháp nhân tử LU Bài tập Bài tập  4 4 5  Bài 1. Cho A =  6 9 7 . Phân tích A = LU 4 7 1 theo Doolite, tìm phần tử L32 của ma trận L. Giải 6   h2→h2−4h1   4 4 5 4 4 4 5 h3→h3−4h1  6 9 7  −−−−−−→  03?  4 7 1 03? 3 32 L = 3 = 1.0000 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 30 / 76
  32. Phương pháp nhân tử LU Bài tập  1 1 1  Bài 2. Cho A =  3 2 1 . Phân tích A = LU 5 1 1 theo Doolite, tính tổng các phần tử tr(U) = U11 + U22 + U33 của ma trận U. Giải D1 = 1; D2 = −1; D3 = −4 D2 D3 tr(U) = U11 + U22 + U33 = D1 + + = 4.0000 D1 D2 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 31 / 76
  33. Phương pháp nhân tử LU Bài tập Bài 3. Sử dụng phương pháp nhân tử LU giải hệ phương trình  2x − 5x + 4x = 1  1 2 3 3x1 + 3x2 + 9x3 = 0  3x1 + 6x2 + 5x3 = 4 Đáp số (x1, x2, x3) = (89/34, 2/17, −31/34) Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 32 / 76
  34. Phương pháp Choleski Ma trận xác định dương Định lý Ma trận vuông A xác đinh dương nếu các định thức con chính của nó đều dương  3 2 3  Ví dụ: Tìm α để ma trận A =  2 α 4  xác 3 4 4 định dương 4 D1 = 3 > 0,D2 = 3α − 4 > 0 → α > 3, 16 16 D3 = 3α − 16 > 0 → α > 3 ⇒ α > 3 Kết luận : α > 5.3333 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 33 / 76
  35. Phương pháp Choleski Định lý Choleski Định lý Một ma trận vuông A đối xứng và xác định dương có thể phân tích duy nhất được dưới dạng A = BBT với B là ma trận tam giác dưới Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 34 / 76
  36. Phương pháp Choleski Định lý Choleski   a11 a12 a1n  a a a   21 22 2n  =  . . .   . . .  an1 an2 ann     B11 0 0 0 B11 B12 B1n      B12 B22 0   0 B22 B2n   . . .   . . .   . . .   . . .  B1n B2n Bnn 0 0 Bnn Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 35 / 76
  37. Phương pháp Choleski Định lý Choleski Các phần tử của ma trận B được xác định theo công thức  √  B11 = a11  ai1  B = (2 i n)  i1 B 6 6  s11  i−1 B = a − P B2 (1 < i n)  ii ii ik 6  k=1   j−1   1 P  Bij = aij − BikBjk (1 < j < i)  Bjj k=1 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 36 / 76
  38. Phương pháp Choleski Định lý Choleski  1 1 −1  Ví dụ: Phân tích ma trận A =  1 2 0  −1 0 4 thành BBT theo Choleski √ a21 a31 B11 = a11 = 1; B21 = = 1; B31 = = −1 B11 B11 p 2 B22 = a22 − B21 = 1; B32 = 1 (a32 − B31b21) = 1 B22 √ p 2 2 B33 = a33 − B31 − B32 = 2  1 0 0  B =  1 1√ 0  −1 1 2 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 37 / 76
  39. Phương pháp Choleski Định lý Choleski Từ tính chất của tích ma trận tam giác dưới và ma trận tam giác trên T 2 Dk(B)Dk(B ) = Dk(A) ⇒ (B11B22 Bkk) = Dk(A) q p Dk (A) ⇒ {B11 = D1(A); Bkk = , k > 1} Dk−1(A)  1 1 −1  Ví dụ: A =  1 2 0  −1 0 4 D1(A) = 1, D2(A) = 1, D3(A) = 2 q q √ D2(A) D3(A) 11 B = 1; B22 = D (A) = 1; B33 = D (A) = 2 1 2 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 38 / 76
  40. Phương pháp Choleski Bài tập Bài tập  3 −4 −3  Bài 1. Cho A =  −4 8 −3 . Phân tích −3 −3 25 A = BBT theo Choleski, tính tổng các phần tử tr(B) = B11 + B22 + B33 của ma trận B. Giải D = 3; D = 8; D = 29 1 √2 q3 q D2 D3 tr(B) = D1 + + = 5.2690 D1 D2 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 39 / 76
  41. Phương pháp Choleski Bài tập  13 4 2  Bài 2. Cho A =  4 α 2 . Với điều kiện nào 2 2 1 của α thì ma trận A đối xứng và xác định dương. Giải D1 = 13 > 0; D2 = 13α − 16 > 0; D3 = 9α − 36 > 0 ⇒ α > 4.0000 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 40 / 76
  42. Chuẩn của véctơ, chuẩn của ma trận Chuẩn của véctơ Định nghĩa Trong không gian tuyến tính thực Rn. Chuẩn của véctơ X ∈ Rn là một số thực, ký hiệu ||X || thỏa các điều kiện sau: n 1 ∀X ∈ R , ||X || > 0, ||X || = 0 ⇔ X = 0 n 2 ∀X ∈ R , ∀λ ∈ R, ||λX || = |λ|.||X || n 3 ∀X , Y ∈ R , ||X + Y || 6 ||X || + ||Y ||. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 41 / 76
  43. Chuẩn của véctơ, chuẩn của ma trận Chuẩn của véctơ Trong Rn có rất nhiều chuẩn, tuy nhiên ta chỉ xét chủ yếu 2 chuẩn thường dùng sau: T n ∀X = (x1, x2, , xn) ∈ R n P ||X ||1 = |x1| + |x2| + + |xn| = |xk|. k=1 ||X ||∞ = max{|x1|, |x2|, , |xn|} = max |xk|. k=1,n Ví dụ Cho X = (1, 2, 3, −5)T . ||X ||1 = 1 + 2 + 3 + 5 = 11 và ||X ||∞ = max{1, 2, 3, 5} = 5 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 42 / 76
  44. Chuẩn của véctơ, chuẩn của ma trận Chuẩn của ma trận Chuẩn của ma trận Định nghĩa Chuẩn của ma trận tương ứng với chuẩn véctơ được xác định theo công thức ||AX || ||A|| = max ||AX || = max ||X ||=1 ||X ||6=0 ||X || Từ định nghĩa chuẩn của ma trận, ta có ||AX || 6 ||A||.||X || Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 43 / 76
  45. Chuẩn của véctơ, chuẩn của ma trận Chuẩn của ma trận Ví dụ  1 2  Xác định chuẩn của ma trận A = tương 3 4   x1 ứng với chuẩn ||X ||1. Với mọi X = thỏa x2 ||X ||1 = |x1| + |x2| = 1, ta có ||AX ||1 = |x1 + 2x2| + |3x1 + 4x2| 6 4|x1| + 6|x2| = 4 + 2|x2| 6 6. Do đó ||A|| = 6. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 44 / 76
  46. Chuẩn của véctơ, chuẩn của ma trận Chuẩn của ma trận Định lý Chuẩn của ma trận A = (aij ) được xác định như sau: n P ||A||1 = max |aij |− chuẩn cột 16j6n i=1 n P ||A||∞ = max |aij |− chuẩn hàng 16i6n j=1 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 45 / 76
  47. Chuẩn của véctơ, chuẩn của ma trận Chuẩn của ma trận Ví dụ  2 −1 4  Cho A =  5 3 2  . Lúc này 6 −7 3 ||A||1 = max{2 + 5 + 6, 1 + 3 + 7, 4 + 2 + 3} = 13, ||A||∞ = max{2+1+4, 5+3+2, 6+7+3} = 16. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 46 / 76
  48. Những phương pháp lặp Những khái niệm cơ bản Những khái niệm cơ bản Định nghĩa (m) ∞ (m) n Xét dãy các véctơ (X )m=0 với X ∈ R . Dãy các véctơ này được gọi là hội tụ về véctơ X khi m → +∞ nếu và chỉ nếu ||X (m) − X || → 0 khi m → +∞ (hội tụ theo chuẩn). Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 47 / 76
  49. Những phương pháp lặp Những khái niệm cơ bản Định lý (m) ∞ Để dãy các véctơ (X )m=0 hội tụ về véctơ X khi m → +∞ thì điều kiện cần và đủ là những dãy (m) (xk ) hội tụ về xk, ∀k = 1, 2, , n. (hội tụ theo tọa độ). Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 48 / 76
  50. Những phương pháp lặp Số điều kiện của ma trận Xét hệ phương trình AX = B(det(A) =6 0) có nghiệm x = A−1.B. Cho B một số gia ∆B, khi đó nghiệm X tương ứng sẽ có số gia ∆X và A.∆X = ∆B ⇔ ∆X = A−1.∆B. Như vậy, ta có −1 −1 ||∆X || = ||A .∆B|| 6 ||A ||.||∆B|| và ||B|| = ||AX || 6 ||A||.||X || Từ đây ta được ||∆X || ||∆B|| ||A||.||A−1||. ||X || 6 ||B|| Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 49 / 76
  51. Những phương pháp lặp Số điều kiện của ma trận Định nghĩa Số k(A) = Cond(A) = ||A||.||A−1|| được gọi là số điều kiện của ma trận A. Số điều kiện k(A) thỏa 1 6 k(A) 6 +∞ Ví dụ:    1 3 −1  3 1 1 17 17 17 −1 −19 11 2 A =  5 2 1  ⇒ A =  17 17 17  33 −20 1 1 7 4 17 17 17 −1 53 ||A||1 = 10; ||A ||1 = 17 ⇒ k1(A) = 31.1765 −1 54 ||A ||∞ = 12; ||A ||∞ = ⇒ k∞(A) = 38.1177 17 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 50 / 76
  52. Những phương pháp lặp Sự không ổn định của hệ phương trình tuyến tính Trong thực hành tính toán, ta có thể gặp những hệ phương trình tuyến tính mà những thay đổi nhỏ trên các hệ số tự do của hệ sẽ gây ra những thay đổi rất lớn về nghiệm. Hệ phương trình tuyến tính như vậy được gọi là hệ phương trình không ổn định trong tính toán. Nếu ngược lại, hệ được gọi là hệ phương trình ổn định trong tính toán Chú ý. Người ta chứng minh được rằng, số điều kiện của ma trận đặc trưng cho tính ổn định của hệ phương trình tuyến tính. Giá trị k(A) càng gần với 1 thì hệ càng ổn định. Số điều kiện k(A) càng lớn thì hệ càng mất ổn định. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 51 / 76
  53. Những phương pháp lặp Sự không ổn định của hệ phương trình tuyến tính Ví dụ  1 2  Xét hệ phương trình AX = B với A = và 1 2.01  3  B = . Dễ dàng thấy được hệ có nghiệm 3.01  1   3  X = . Bây giờ xét hệ AX = B với B = . 1 e e e 3.1  −17  Nghiệm bây giờ của hệ là X = . Ta thấy e 10 k∞(A) = 1207.01 >> 1. Do đó B ≈ Be nhưng X và Xe khác nhau rất xa. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 52 / 76
  54. Những phương pháp lặp Bài tập Bài tập  8 −6  Bài 1. Cho A = .Tìm số điều kiện 8 3 theo chuẩn một của A  1 1  −1 24 12 Giải. A = 1 1 . −9 9 −1 7 k1(A) = ||A||1||A ||1 = 16.36 = 3.1111 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 53 / 76
  55. Những phương pháp lặp Bài tập  −8 5 −8  Bài 2. Cho A =  3 −4 6  .Tìm số điều −7 −5 −2 kiện theo chuẩn vô cùng của A  19 5 1  −70 −14 70 −1 9 2 6 Giải. A =  35 7 −35  . 43 15 17 140 28 −140 −1 27 k∞(A) = ||A||∞||A ||∞ = 21.28 = 20.2500 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 54 / 76
  56. Những phương pháp lặp Phương pháp lặp Ý tưởng chính Từ hệ AX = b, ta phân tích A = M − N, với M là ma trận "dễ" khả nghịch,khi đó ta có: (M − N)X = b ⇔ MX = NX + b ⇔ X = M−1NX + M−1b Đặt T = M−1N, c = M−1b → X = TX + c Xuất phát từ véctơ ban đầu X (0) ta xây dựng dãy (m) ∞ (X )m=0 theo công thức X (m) = TX (m−1) + c, m = 1, 2, (2) Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 55 / 76
  57. Những phương pháp lặp Phương pháp lặp Định lý (m) ∞ Nếu ||T || < 1 thì dãy các véctơ (X )m=0 xác định theo công thức lặp (2) sẽ hội tụ về véctơ nghiệm X của hệ với mọi véctơ lặp ban đầu X (0). Khi đó công thức đánh giá sai số như sau: ||T ||m ||X (m) − X || .||X (1) − X (0)|| 6 1 − ||T || hoặc (m) ||T || (m) (m−1) ||X − X || 6 .||X − X || 1 − ||T || Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 56 / 76
  58. Những phương pháp lặp Phương pháp lặp Jacobi Phương pháp lặp Jacobi Xét hệ phương trình AX = b . Ta phân tích ma trận A theo dạng     a11 a12 a1n a11 0 0  a21 a22 a2n   0 a22 0  A =   =   −     an1 an2 ann 0 0 ann     0 0 0 0 −a12 −a1n  −a21 0 0   0 0 −a2n    −       −an1 −an2 0 0 0 0 = D − L − U. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 57 / 76
  59. Những phương pháp lặp Phương pháp lặp Jacobi Do aii =6 0, ∀i = 1, 2, , n nên detD =6 0. Như vậy  1 0 0  a11  0 1 0  −1  a22  D =     0 0 1 ann Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 58 / 76
  60. Những phương pháp lặp Phương pháp lặp Jacobi Nội dung phương pháp Jacobi Ta có AX = B ⇔ (D − L − U)X = B ⇔ (D)X = (L + U)X + B ⇔ X = D−1(L + U)X + D−1B. −1 −1 Ký hiệu Tj = D (L + U) và Cj = D B. Khi đó công thức lặp có dạng (m) (m−1) X = Tj X + Cj , m = 1, 2, Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 59 / 76
  61. Những phương pháp lặp Phương pháp lặp Jacobi Dạng tường minh của công thức lặp Jacobi là  i−1 n  (m) 1 X m−1 X m−1 xi = − aij xj − aij xj + bi  . aii j=1 j=i+1 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 60 / 76
  62. Những phương pháp lặp Phương pháp lặp Jacobi Ví dụ  6x + 2x − 3x = 8  1 2 3 Xét hệ phương trình 2x1 + 7x2 + 3x3 = 9  3x1 + 2x2 + 8x3 = 7 Sử dụng phương pháp Jacobi,với vectơ lặp ban đầu x(0) = (0.1; 0.2; 0.3)T ,hãy tính vectơ lặp x(3) và đánh giá sai số của nó theo công thức hậu nghiệm,sử dụng chuẩn vô cùng.  −1 1  0 3 2 −2 −3 4 9 7 T Tj =  7 0 7 ; cj = (3; 7; 8) −3 −1 0 8 4 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 61 / 76
  63. Những phương pháp lặp Phương pháp lặp Jacobi  6x + 2x − 3x = 8  1 2 3 2x1 + 7x2 + 3x3 = 9  3x1 + 2x2 + 8x3 = 7  6x = 8 − 2x + 3x  1 2 3 ⇔ 7x2 = 9 − 2x1 − 3x3  8x3 = 7 − 3x1 − 2x2  (m) (m−1) (m−1)  x1 = (8 − 2x2 + 3x3 )/6  (m) (m−1) (m−1) ⇔ x2 = (9 − 2x1 − 3x3 )/7  (m) (m−1) (m−1) x3 = (7 − 3x1 − 2x2 )/8 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 62 / 76
  64. Những phương pháp lặp Phương pháp lặp Jacobi (m) (m) (m) m x1 x2 x3 0 0.1 0.2 0.3 17 79 63 1 12 70 80 1513 913 69 2 1120 1680 1120 3407 6847 893 3 2880 7840 3840 x(3) = (1.1830; 0.8733; 0.2326)T (3) (2) 677 7759 919 T x − x = (−4032; 23520; 5376) (3) (2) 7759 5 ||x − x ||∞ = 23520; ||Tj ||∞ = 6 (3) ||Tj ||∞ (3) (2) ∆x ≤ ||x − x ||∞ = 1.6495 1−||Tj ||∞ Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 63 / 76
  65. Những phương pháp lặp Bài tập Bài tập Bài 1. Bằng phương pháp lăp Jacobi, tìm nghiệm gần đúng của hệ phương trình với sai số 10−3, chọn chuẩn vô cùng  4x − x + x = 1  1 2 3 3x1 + 8x2 + 2x3 = 0  3x1 + 3x2 + 10x3 = 4 Đáp số (x1, x2, x3) = (0. 1115, −0.1442, 0.4099), ∆x(7) = 3.94.10−4 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 64 / 76
  66. Những phương pháp lặp Phương pháp Gauss-Seidel Nội dung phương pháp Gauss-Seidel Phân tích A = D − L − U,ta có:AX = B ⇔ (D − L − U)X = B ⇔ (D − L)X = UX + B ⇔ X = (D − L)−1UX + (D − L)−1B. −1 −1 Ký hiệu Tg = (D − L) U và Cg = (D − L) B. Khi đó công thức lặp có dạng (m) (m−1) X = Tg X + Cg , m = 1, 2, Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 65 / 76
  67. Những phương pháp lặp Phương pháp Gauss-Seidel Dạng tường minh của công thức lặp Gauss-Seidel n (m) 1 X (m−1) x1 = (b1 − a1j xj ), a11 j=2 n (m) 1 (m) X m−1 x2 = (b2 − a21x1 − a2j xj ), a22 j=3 i−1 n (m) 1 X (m) X m−1 xi = (bi − aij xj − aij xj ), aii j=1 j=i+1 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 66 / 76
  68. Những phương pháp lặp Phương pháp Gauss-Seidel Phương pháp Gauss-Seidel có thể xem là 1 biến dạng của phương pháp lặp Jacobi, nhưng khác phương pháp Jacobi ở chỗ: khi tính thành phần thứ i của véctơ lặp X (m) thì ta sử dụng ngay (m) (m) (m) những thành phần x1 , x2 , , xi−1 vừa tính được. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 67 / 76
  69. Những phương pháp lặp Phương pháp Gauss-Seidel Ví dụ  6x + 2x − 3x = 8  1 2 3 Xét hệ phương trình 2x1 + 7x2 + 3x3 = 9  3x1 + 2x2 + 8x3 = 7 Sử dụng phương pháp Gauss-seidel,với x(0) = (0.1; 0.2; 0.3)T ,hãy tính vectơ lặp x(3) và đánh giá sai số của nó theo công thức tiên nghiệm,sử dụng chuẩn vô cùng. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 68 / 76
  70. Những phương pháp lặp Phương pháp Gauss-Seidel −1  6 2 −3  A =  2 7 3  3 2 8 −1  6 0 0   0 −2 3  Tg =  2 7 0   0 0 −3  3 2 8 0 0 0  −1 1  0 3 2 2 2 Tg =  0 21 7  17 −29 0 168 112 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 69 / 76
  71. Những phương pháp lặp Phương pháp Gauss-Seidel  6x + 2x − 3x = 8  1 2 3 2x1 + 7x2 + 3x3 = 9 ⇔  3x1 + 2x2 + 8x3 = 7  (m) (m−1) (m−1)  6x1 = 8 − 2x2 + 3x3  (m) (m) (m−1) 2x1 + 7x2 = 9 − 3x3  (m) (m) (m) 3x1 + 2x2 + 8x3 = 7  (m) (m−1) (m−1)  x1 = (8 − 2x2 + 3x3 )/6  (m) (m) (m−1) ⇔ x2 = (9 − 2x1 − 3x3 )/7  (m) (m) (m) x3 = (7 − 3x1 − 2x2 )/8 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 70 / 76
  72. Những phương pháp lặp Phương pháp Gauss-Seidel (m) (m) (m) m x1 x2 x3 0 0.1 0.2 0.3 17 79 523 1 12 105 3360 2 1.1604 0.8875 0.2180 3 1.1465 0.8647 0.2289 x(3) = (1.1465; 0.8647; 0.2289)T (1) (0) 79 58 97 T x − x = (60; 105; −672) (1) (0) 79 5 ||x − x ||∞ = 60; ||Tg ||∞ = 6 3 ∆x(3) ≤ ||Tg ||∞ ||x(1) − x(0)|| = 4.5718 1−||Tg ||∞ ∞ Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 71 / 76
  73. Những phương pháp lặp Sự hội tụ của phương pháp lặp Định nghĩa Ma trận A được gọi là ma trận đường chéo trội nghiêm ngặt nếu nó thỏa mãn điều kiện n X |aij | < |aii |, i = 1, 2, , n j=1,j6=i Định lý Các phương pháp lặp Jacobi, Gauss-Seidel cho hệ phương trình AX = b sẽ hội tụ nếu A là ma trận có đường chéo trội nghiêm ngặt. Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 72 / 76
  74. Những phương pháp lặp Bài tập Bài tập  13x − 4x = 6 Bài 1. Cho hệ phương trình 1 2 5x1 + 15x2 = 4 Với x(0) = [0.7; 1.0]T , tìm sai số ∆x(2) của vectơ lặp x(2) theo phương pháp Jacobi,sử dụng công thức hậu nghiệm và chuẩn vô cùng 1 Giải. ||Tj ||∞ = 3; (1) 10 1 T (2) 92 2 T x = [13; 30] ;x = [195; 195] (2) ||Tj ||∞ (2) (1) 1/3 58 ∆x = ||x − x ||∞ = = 1−||Tj ||∞ 1−1/3 195 0.1488 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 73 / 76
  75. Những phương pháp lặp Bài tập Bài 2. Cho hệ phương trình  11x + 5x = 2 1 2 Với x(0) = [0.9; 0.2]T , tìm −3x1 + 11x2 = 4 vectơ lặp x(3) theo phương pháp Jacobi. Giải. x(3) = [0.005; 0.338]T Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 74 / 76
  76. Những phương pháp lặp Bài tập  15x − 4x = 2 Bài 3. Cho hệ phương trình 1 2 −4x1 + 7x2 = 5 Với x(0) = [0.2; 0.5]T , tìm sai số ∆x(2) của vectơ lặp x(2) theo phương pháp Gauss-Seidel,sử dụng công thức tiên nghiệm và chuẩn vô cùng 4 (1) 4 13 T Giải. ||Tg ||∞ = 15; x = [15; 15] ; 2 4 2 (2) ||Tg ||∞ (1) (0) (15) 11 ∆x = 1−||T || ||x − x ||∞ = 4 30 = g ∞ 1−15 0.0356 Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 75 / 76
  77. Những phương pháp lặp Bài tập Bài 4. Cho hệ phương trình  11x − 5x = 4 1 2 Với x(0) = [0.2; 0.8]T , tìm −6x1 + 11x2 = 6 vectơ lặp x(3) theo phương pháp Gauss-Seidel. Giải. x(3) = [0.808; 0.986]T Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 76 / 76
  78. Những phương pháp lặp Bài tập Bài 5. Cho hệ phương trình  38x + 2.73x − 1.85x = 12.89  1 2 3 1.34x1 + 37x2 − 3.24x3 = 15.73 Với  1.18x1 − 4.87x2 + 34x3 = 18.42 x(0) = [0.5; 2.3; 3.4]T , tìm vectơ lặp x(3) theo phương pháp Gauss-Seidel. Giải. x(3) = [0.3346; 0.4654; 0.5968]T Nguyễn Hồng Lộc (BK TPHCM) HỆ PHƯƠNG TRÌNH TUYẾN TÍNH TP. HCM — 2013. 77 / 76