›
›

Bài giảng Toán ứng dụng - Chương 2: Hệ phương trình tuyến tính ax=b - Nguyễn Quốc Lân

ppt 31 trang huongle 2090
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán ứng dụng - Chương 2: Hệ phương trình tuyến tính ax=b - Nguyễn Quốc Lân", để 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_toan_ung_dung_chuong_2_he_phuong_trinh_tuyen_tinh.ppt

Nội dung text: Bài giảng Toán ứng dụng - Chương 2: Hệ phương trình tuyến tính ax=b - Nguyễn Quốc Lân

  1. BỘ MÔN TOÁN ỨNG DỤNG - ĐHBK PHƯƠNG PHÁP TÍNH – BG SINH VIÊN CHƯƠNG 2 HỆ PHƯƠNG TRÌNH TUYẾN TÍNH Ax = b TS. NGUYỄN QUỐC LÂN (2/2006)
  2. NỘI DUNG A- CÁC PHƯƠNG PHÁP CHÍNH XÁC 1- PHƯƠNG PHÁP KHỬ GAUSS (PHẦN TỬ TRỤ) 2- PHÂN TÍCH NHÂN TỬ A = LU 3- PHÂN TÍCH CHOLESKY B- CÁC PHƯƠNG PHÁP LẶP 1- LẶP JACOBI 2- LẶP GAUSS - SEIDEL C- SỐ ĐIỀU KIỆN – HỆ ĐIỀU KIỆN XẤU
  3. TỔNG QUAN Hệ n phương trình bậc 1 (tuyến tính), n ẩn Dạng Ax = b: Đơn giản: Hệ tam giác Giải lùi T Hàng i: hi = [ai1 ai2 ain] . Biến đổi sơ cấp trên hàng hi hi + khj: Nhân hj với k rồi cộng xuống hi (chỉ hi thay đổi)
  4. PHƯƠNG PHÁP KHỬ GAUSS Giải thuật: Biến đổi sơ cấp trên hàng A: trên Giải lùi VD: Giải hệ Xây dựng ma trận mở rộng Khử cột 1 với hệ số khử m1j
  5. GIẢI LÙI & PHẦN TỬ TRỤ Khử cột 2 với hệ số khử: Giải lùi với hệ tam giác trên thu được: (1) (2) Điều kiện: Khử cột 1: a11 0 & Khử cột 2: a22 0 & (3) Giải lùi: a33 0 Phần tử trụ (pivot) akk 0
  6. KHỬ GAUSS VỚI LỆNH MAPLE > with(linalg); # Khởi động gói lệnh Đại số tuyến tính > A := matrix(2,3,[2, 3, 4, 1, 2, 3]); # Nhập ma trận > m21 := A[2,1]/A[1,1]; # Tính hệ số khử > A := addrow(A,1,2,–m21) ; # Cộng hàng h2 h2 – m21h1 > A := swaprow(A,1,2) ; # Nếu cần thiết, đổi hàng h2  h1 > x := backsup(A) ; # Hệ đã ở dạng tam giác trên: Giải lùi > AA := gausselim(A); # Lệnh gộp khử Gauss toàn ma trận VD: Giải hệ
  7. KHỬ GAUSS VỚI MA TRẬN “LẺ”: PIVOT ĐƠN VỊ VD: Giải hệ với phép khử Gauss, làm tròn 3 chữ số lẻ)
  8. THỰC TẾ TÍNH TOÁN: VẤN ĐỀ LÀM TRÒN SỐ VD: Giải hệ trên máy tính với phép làm tròn 4 chữ có nghĩa Nghiệm chính xác: [10, 1]T Quy tắc làm tròn trên máy tính: Làm tròn chữ số có nghĩa Trụ khử: a11 = 0.003 0 Biến đổi cột một: (E2) (E2) – m21(E1)
  9. PHÂN TÍCH NHÂN TỬ (MATRIX FACTORIZATIONS) Ma trận vuông A phân tích được thành dạng LU Hệ Ax = b (LU)x = b Giải hệ đầu Giải 2 hệ : Ly = b (2) tìm y; Ux = y (1) tìm x Nhân A Nhân L Nhân U
  10. VÍ DỤ Giả sử ma trận A phân tích được thành dạng LU như sau: Sử dụng phân tích LU trên giải hệ Ax = b = [–9 5 7 11]T Giải Ly = b tìm y Giải Ux = y tìm x
  11. PHÂN TÍCH NHÂN TỬ A = LU Quan sát: Ma trận khử L và ma trận kết quả U. Xét tích L.U Kết quả: Nếu quá trình khử Gauss diễn ra bình thường (không đổi hàng), ma trận A của hệ Ax = b phân tích được thành tích LU: A = LU với Ø L (lower): ma trận tam giác dưới, đường chéo chính bằng 1, chứa các hệ số khử ở vị trí khử Ø U (upper): ma trận tam giác trên, cũng là ma trận kết quả nhận được sau quá trình khử Gauss
  12. GIẢI THUẬT TÌM LU (CROUT – DOOLITLE) Phân tích LU với đường chéo chính L bằng 1 Khử Gauss (không đổi hàng). Các hệ số khử tạo L, ma trận kết quả: U VD: L (hoặc U) có đchéo chính = 1 G/thuật Doolitle (Crout) For j = 1 to n: i = 1 j Tự xem i = j +1 n SGK/ 35
  13. MINH HOẠ GIẢI THUẬT DOOLITLE (ĐCHÉO L = 1) VD: j = 1: i = 1 i = 2 i = 3 j = 2: i = 1 i = 2 i = 3 j = 3: i = 1 i = 2 i = 3 i = 3
  14. PHÂN TÍCH CHOLESKY Tương tự phân tích LU nhưng gọn hơn “phân nửa”! Ma trận vuông A (n hàng, n cột) : A = [ aij ] xác định dương VD: : ma trận (đối xứng) xác định dương vì A: XĐD n định thức con (hvuông) trên đ/chéo chính đều > 0
  15. GIẢI THUẬT CHOLESKY Định lý: Ma trận A đối xứng xác định dương Tồn tại ma trận tam giác dưới B thoả mãn : A = BBT A đối xứng: For i = 1 to n do For j = i+1 to n do Ax = b (BBT)x = b BTx = y & By = b: 2 hệ (như LU) A k0 xác định dương (chỉ đối xứng): A = BBT có thể chứa số phức 2 hệ BTx = y & By = b: phức. Nhưng nghiệm x: thực!
  16. MINH HOẠ GIẢI THUẬT CHOLESKY VD: i = 1 j = 2 j = 3 i = 2 j = 3 i = 3
  17. TỔNG QUAN PHƯƠNG PHÁP LẶP Chương 1: Phương pháp lặp đơn với phương trình f(x) = 0 Hệ Ax = b x = Tx + c = (x), T: ma trận, c: vectơ. Đkiện:  (x) – (y) qx – y Dãy lặp: x(n+1) = Tx(n) + c T n Chuẩn vectơ, ma trận: x = [x1, x2 xn] R , A = [aij ]
  18. VÍ DỤ Ø Tính các chuẩn vectơ và ma trận Ø Vectơ nào trong số hai vectơ sau xấp xỉ tốt nhất theo chuẩn , chuẩn một nghiệm hệ phương trình Tch. chuẩn vectơ, chuẩn ma trận: Chuẩn tích tích chuẩn
  19. LẶP JACOBI Với vectơ x(0) = [0, 0, 0]T, tìm vectơ nghiệm xấp xỉ x(k) của phép lặp Jacobi với hệ sau. Dừng: x(k) “giống” x(k-1) (khoảng 0.3) . So với nghiệm = [0.5, 1, -0.5]T 1/ Rút x trên đường chéo chính Đưa về dạng x = Tx + c x = Tx + c
  20. CÔNG THỨC LẶP JACOBI 2/ Từ x(0) tính x(1): Tổng quát: x(k) x(k+1): Sai số: Như lặp đơn với q = ||T|| :
  21. LẶP JACOBI KHÔNG BIẾN ĐỔI MA TRẬN A Hệ Ax = b: : Giữ đ/chéo chính ở vế trái ( x(k+1)) ; Chuyển số hạng còn lại sang vế phải ( x(k)) : Thay x(k) vào các số hạng ngoài đường chéo chính. Xem x(k+1) là ẩn. Giải x(k+1)
  22. TÍNH TOÁN & KẾT QUẢ LẶP JACOBI k 0 1 2 (k) x1 0.0 0.75 (k) x2 0.0 0.9 (k) x3 0.0 –0.3125 (k) (k-1) x -x  0.9 Ưu điểm Lặp Jacobi: Giải các hệ “thưa” (chứa rất nhiều số 0) M/trận đ/c trội nghiêm ngặt:
  23. LẶP GAUSS – SEIDEL Tương tự lặp Jacobi nhưng với thông tin cập nhật hoá Dùng x(k) để tính giá trị của x(k+1) v x1 (mới): dùng x2 (cũ), x3 (cũ) v x2 (mới): dùng x1 (mới), x3 (cũ) v x3 (mới): dùng x1 (mới), x2 (mới)
  24. LẶP GAUSS – SEIDEL: SƠ ĐỒ TÁCH MA TRẬN Trình bày dạng khác: Xem x(k+1) là ẩn và chuyển sang vế trái Gauss - Seidel: Biết x(k) Tính vế phải b(k) Giải hệ ra x(k+1)
  25. LẶP GAUSS – SEIDEL: VÍ DỤ TÁCH MA TRẬN Xét ví dụ lặp Gauss – Seidel, x(0) = [0, 0, 0]T. Công thức lặp: k 0 1 2 x b x b x b (k) x1 0.0 (k) x2 0.0 (k) x3 0.0 (k) (k-1) x -x  Phép lặp Thay hệ Ax = b bằng giải liên tiếp nhiều hệ
  26. TỔNG KẾT LẶP JACOBI & GAUSS – SEIDEL x = Tx + c Lặp Jacobi Lặp Gauss– Seidel
  27. HỆ PHƯƠNG TRÌNH BỊ NHIỄU Minh hoạ: Giải 2 hệ phương trình và nhận xét Hệ “gần” nhau, nghiệm “xa” nhau! Do detA 0:
  28. VÍ DỤ WILSON: Ax = b, detA = 1
  29. SỐ ĐIỀU KIỆN CỦA HỆ Ax = b •“Nhiễu” vế phải A(x + x) = b + b •“Nhiễu” vế trái (A + A)(x + x) = b –1 Số điều kiện:  (A) = ||A|| . ||A || đặc trưng cho độ “nhạy cảm” của nghiệm hệ Ax = b đối với những thay đổi dù rất nhỏ trên b hoặc A Hệ điều kiện xấu (ill – conditionned):  (A) >> 1
  30. VÍ DỤ VD Wilson: VD: Tính số điều kiện theo chuẩn vô cùng  (A) của ma trận
  31. PHƯƠNG PHÁP TÌM MA TRẬN NGƯỢC Tính ma trận ngược T Ø Giải hệ phương trình A.c1 = e1 = [1 0] (vectơ đơn vị thứ nhất) trên máy tính bỏ túi Cột 1 của ma trận ngược Ø Vẫn trong chế độ giải hệ phương trình, giải tiếp hệ A.c2 T -1 = e2 = [0 1] (vectơ đơn vị thứ nhì) Cột 2 của A Ø Trường hợp ma trận cấp 3: Giải 3 hệ Ac1 = e1, Ac2 = e2, Ac3 = e3 với e1, e2, e3 lần lượt là 3 vectơ đơn vị Tìm được 3 –1 vectơ nghiệm c1, c2, c3: 3 cột của ma trận ngược A cần tìm