Bài giảng Phương pháp tính - Chương 3: Hệ phương trình tuyến tính

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

1. CHƯƠNG 3 HỆ PHƯƠNG TRÌNH TUYẾN TÍNH
2. I. ĐẶT BÀI TOÁN : Hệ phương trình tuyến tính n pt và n ẩn có dạng Ax = b với
3. Các phương pháp giải ➢ Phương pháp giải chính xác ▪ Phương pháp Gauss ▪ Phương pháp nhân tử LU ▪ Phương pháp Cholesky ➢ Phương pháp giải gần đúng ▪ Phương pháp lặp Jacobi ▪ Phương pháp lặp Gauss-Seidel
4. II. PHƯƠNG PHÁP GAUSS 1. Các dạng ma trận đặc biệt : a. Ma trận tam giác dưới detA = a11a22 . . . ann ≠ 0 ⇔ aii ≠ 0, ∀i Phương trình có nghiệm
5. b. Ma trận tam giác trên : detA = a11a22 . . . ann ≠ 0 ⇔ aii ≠ 0, ∀i Phương trình có nghiệm
6. 2. Phương pháp Gauss : Ta sử dụng các phép biến đổi sơ cấp theo dòng để chuyển ma trận A về ma trân tam giác trên Các phép biến đổi sơ cấp theo dòng ➢ hoán chuyển 2 dòng ➢ nhân 1 dòng với 1 số khác 0 ➢ cộng 1 dòng với dòng khác
7. Ví dụ : Giải hệ phương trình Giải Giải pt ma trận tam giác trên, ta được nghiệm t x = (-7, 3, 2, 2)
8. III. PHƯƠNG PHÁP NHÂN TỬ LU Phân tích ma trận A thành tích 2 ma trận L và U A = LU L : ma trận tam giác dưới U : ma trận tam giác trên Phương trình Ax = b ⇔ L(Ux) = b Ta đưa về giải 2 hệ phương trình
9. Phương pháp Doolittle : Giả sử A ma trận không suy biến và a11 ≠ 0 Ta có thể phân tích A thành A = LU Ma trân Δ dưới Ma trân Δ trên
10. Các phần tử của L và U được xác định theo công thức
11. Ví dụ : Giải hệ phương trình Giải Ta phân tích
12. Giải hệ Ly = b Giải hệ Ux = y
13. IV. PHƯƠNG PHÁP CHOLESKY Phương pháp Cholesky là pp LU với A là ma trận đối xứng và xác định dương Định nghĩa : ➢ Ma trân A gọi là đối xứng nếu t A = A ➢ Ma trân A gọi là xác định dương nếu
14. Để kiểm tra xác định dương, ta dùng đình lý sau: Định lý : Ma trận A là xác định dương khi và chỉ khi tất cả các định thức con chính của nó đều dương Ví dụ : Kiểm tra tính xác định dương của ma trận Giải Các định thức con chính: Vậy A là xác định dương
15. Định lý (Cholesky) : Nếu A ma trận đối xứng và xác định dương, thì tồn tại ma trận Δ dưới, khả đảo B sao cho t A = BB Ma trận B = (bij) tìm theo công thức sau :
16. Ví dụ : Giải hệ phương trình Ax = b Giải Ta có A ma trận đối xứng và xác định dương t Phân tích A = BB Các hệ số
17. Giải hệ By = b t Giải hệ B x = y
18. Ví dụ : a. Kiểm tra tính xác định dương b. Phân tích A = BBT theo pp cholesky Tính b11+b22+b33
19. a. Các định thức con chính: Vậy A là xác định dương b. Các hệ số b11+b22+b33 = 6
20. V. CHUẨN : 1. Chuẩn vector : Có nhiều công thức chuẩn, thường ta dùng chuẩn ∞ và chuẩn 1 t ∀x= (x1,x2, , xn)
21. 2. Chuẩn ma trận : Cho ma trận A = (aij), ta có
22. Ví dụ : Ví dụ : Tính
23. V. Hệ pt ổn định và số điều kiện : 1. Hệ pt ổn định : Xét hệ phương trình Ax = b Định nghĩa : Hệ phương trình gọi là ổn định nếu mọi thay đổi nhỏ của A hay b thì nghiệm của hệ chỉ thay đổi nhỏ
24. Ví dụ : Xét hệ phương trình Ax = b với T Hệ phương trình có nghiệm x = (1, 1) Thay đổi T Nghiệm của hệ : x=(-17, 10) Ta thấy nghiệm của hệ khác rất xa khi b thay đổi nhỏ. Vậy hệ không ổn định
25. 2. Số điều kiện : Ta tìm điều kiện để hệ ổn định Định nghĩa : Số k(A) = ||A|| ||A-1|| Gọi là số điều kiện của ma trận A Nhận xét : 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 ➢ k(A) càng gần 1 thì hệ càng ổn định ➢ k(A) càng xa 1 thì hệ càng không ổn định
26. Ví dụ : Tính số điều kiện k(A) theo chuẩn ∞ Ta có ● k(A) = 3.01 x 401 = 1207.01 >> 1 Vậy hệ không ổn định
27. Ví dụ : Tính số điều kiện k(A) theo chuẩn 1 Ta có -1 ● k(A) = ||A||1||A ||1=6 x 20/13 = 9.2308
28. VI. PHƯƠNG PHÁP LẶP : Ta chuyển hệ pt về dạng x = Tx + c Với T là ma trận vuông cấp n và c là 1 vector Để tìm nghiệm gần đúng, với vector ban đầu x(0), ta xây dựng dãy lặp theo công thức (m) (m-1) x = Tx + c, ∀m=1,2, (m) Ta cần khảo sát sự hội tụ của dãy {x }
29. Ta có định lý sau Định lý : Nếu ||T|| < 1 thì dãy lặp x(m) sẽ hội tụ về nghiệm x (0) của hệ pt, với mọi vector ban đầu x . Ta có công thức đánh giá sai số : hoặc
30. 1. Phương pháp lặp Jacobi : Ta phân tích A = D + L + U trong đó
31. Phương trình Ax = b ⇔ (D+L+U)x = b ⇔ Dx = -(L+U)x + b -1 -1 ⇔ x = -D (L+U)x + D b ⇔ x = Tx + c -1 -1 với T = -D (L+U) và c = D b pp lặp theo phân tích trên gọi là pp lặp Jacobi Bây giờ ta tìm điều kiện để pp lặp Jacobi HT
32. Định nghĩa : Ma trận A gọi là ma trận đường chéo trội nghiêm ngặt nếu nó thỏa điều kiện sau : Nhận xét : Nếu A là ma trận đường chéo trội nghiêm ngặt thì detA ≠ 0 và aii ≠ 0 ∀i=1,n
33. Định lý : Nếu A là ma trận đường chéo trội nghiêm ngặt, thì pp (0) lặp Jacobi hội tụ với mọi vector ban đầu x A ma trân đường chéo trội nghiêm ngặt nên ⇒ pp lặp hội tụ
34. (m) (m-1) x = Tx + c, ∀m=1,2, Thay vao, ta có công thức lặp Jacobi
35. Ví dụ : Cho hệ phương trình a. Tìm nghiệm gần đúng x(5) với vector ban đầu x(0) = 0 b. Tính ma trận T và c c. Tính sai số của nghiệm x(5) theo công thức hậu nghiệm
36. a. Công thức lặp Jacobi m 0 1 2 3 4 5 (m) x1 0 0.7 0.71 0.725 0.7267 0.72717 (m) x2 0 0.8 0.64 0.640 0.6368 0.63648 (m) x3 0 0.9 0.89 0.907 0.9085 0.90899
37. b. Ta có c. Công thức sai số Ta có ||T|| =0.2, nên ∞
38. 2. Phương pháp lặp Gauss-Seidel : Ta phân tích A = D + L + U như trong phần trước Phương trình Ax = b ⇔ (D+L+U)x = b ⇔ (D+L)x = -Ux + b -1 -1 ⇔ x = -(D+L) Ux + (D+L) b ⇔ x = Tx + c -1 -1 với T = -(D+L) U và c = (D+L) b pp lặp theo phân tích này gọi là pp lặp Gauss-Seidel
39. Định lý : Nếu A là ma trận đường chéo trội nghiêm ngặt, thì pp lặp Gauss-Seidel hội tụ với mọi vector ban đầu (0) x Ta có công thức lặp Gauss-Seidel
40. Ví dụ : Cho hệ phương trình a. Tìm nghiệm gần đúng x(4) với vector ban đầu x(0) =(0,0,0) b. Tính ma trận T và c c. Tính sai số của nghiệm x(4) theo công thức hậu nghiệm
41. a. Công thức lặp Gauss-Seidel m 0 1 2 3 4 (m) x1 0 0.6 0.5519 0.554268975 0.554233852 (m) x2 0 0.62 0.661955 0.661700938 0.661713904 (m) x3 0 0.791 0.78828775 0.788511944 0.788509080
42. b. Ta có
43. c. Công thức sai số Ta có ||T|| =0.15, nên ∞