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

BỘ MÔN TOÁN ỨNG DỤNG - ĐHBK-------------------------------------------------------------------------------------PHƯƠNG PHÁP TÍNH – BG SINH VIÊN CHƯƠNG 2HỆ PHƯƠNG TRÌNH TUYẾN TÍNHAx = bTS. NGUYỄN QUỐC LÂN (2/2006)NỘI DUNG---------------------------------------------------------------------------------------------------------------------------A- CÁC PHƯƠNG PHÁP CHÍNH XÁC1- PHƯƠNG PHÁP KHỬ GAUSS (PHẦN TỬ TRỤ)2- PHÂN TÍCH NHÂN TỬ A = LU3- PHÂN TÍCH CHOLESKYB- CÁC PHƯƠNG PHÁP LẶP1- LẶP JACOBI2- LẶP GAUSS - SEIDELC- SỐ ĐIỀU KIỆN – HỆ ĐIỀU KIỆN XẤUTỔNG QUAN --------------------------------------------------------------------------------------------------------------------------------Hệ n phương trình bậc 1 (tuyến tính), n ẩn  Dạng Ax = b:Hàng i: hi = [ai1 ai2 ain]T. 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)Đơn giản: Hệ tam giác Giải lùiPHƯƠ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ùiVD: Giải hệXây dựng ma trận mở rộngKhử cột 1 với hệ số khử m1jGIẢI LÙI & PHẦN TỬ TRỤ -------------------------------------------------------------------------------------------------------------------------------Điều kiện: Khử cột 1: a11(1)  0 & Khử cột 2: a22(2)  0 & Giải lùi: a33(3)  0  Phần tử trụ (pivot) akk  0 Giải lùi với hệ tam giác trên thu được:Khử cột 2 với hệ số khử:KHỬ GAUSS VỚI LỆNH MAPLE --------------------------------------------------------------------------------------------------------------------------------VD: Giải hệ> 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> with(linalg); # Khởi động gói lệnh Đại số tuyến tínhKHỬ 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ẻ)THỰC TẾ TÍNH TOÁN: VẤN ĐỀ LÀM TRÒN SỐ ---------------------------------------------------------------------------------------------------------------------------------Quy tắc làm tròn trên máy tính: Làm tròn chữ số có nghĩaTrụ khử: a11 = 0.003  0 Biến đổi cột một: (E2)  (E2) – m21(E1) Nghiệm chính xác: [10, 1]TVD: Giải hệ trên máy tính với phép làm tròn 4 chữ có nghĩaPHÂN TÍCH NHÂN TỬ (MATRIX FACTORIZATIONS) ---------------------------------------------------------------------------------------------------------------------------------Ma trận vuông A phân tích được thành dạng LU Giải hệ đầu  Giải 2 hệ : Ly = b (2) tìm y; Ux = y (1) tìm xHệ Ax = b  (LU)x = b Nhân UNhân LNhân AVÍ DỤ ---------------------------------------------------------------------------------------------------------------------------------Giải Ly = b tìm yGiả 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]TGiải Ux = y tìm xPHÂ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.UKế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ử GaussGIẢI THUẬT TÌM LU (CROUT – DOOLITLE) ---------------------------------------------------------------------------------------------------------------------------------VD:L (hoặc U) có đchéo chính = 1  G/thuật Doolitle (Crout)For j = 1 to n: i = 1  j i = j +1  n Tự xem SGK/ 35Phâ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ả: UMINH HOẠ GIẢI THUẬT DOOLITLE (ĐCHÉO L = 1) -------------------------------------------------------------------------------------------------------------------------------VD: j = 1:j = 2:j = 3:i = 3i = 2i = 3i = 2i = 3i = 2i = 1i = 1i = 1i = 3PHÂ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 A: XĐD n định thức con (hvuông) trên đ/chéo chính đều > 0VD: : ma trận (đối xứng) xác định dương vì 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 = BBTA đối xứng:For i = 1 to n doFor j = i+1 to n doAx = 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!MINH HOẠ GIẢI THUẬT CHOLESKY -------------------------------------------------------------------------------------------------------------------------------i = 1i = 2i = 3VD: j = 2j = 3j = 3TỔ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) = 0Hệ 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 Chuẩn vectơ, ma trận: x = [x1, x2 xn]T  Rn, A = [aij ] VÍ DỤ --------------------------------------------------------------------------------------------------------------------------- Tính các chuẩn vectơ và ma trậnTch. chuẩn vectơ, chuẩn ma trận: Chuẩn tích  tích chuẩ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 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)1/ Rút x trên đường chéo chính  Đưa về dạng x = Tx + c. So với nghiệm  = [0.5, 1, -0.5]T  x = Tx + cCÔ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||: 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) TÍNH TOÁN & KẾT QUẢ LẶP JACOBI ------------------------------------------------------------------------------------------------------------------------------------Ư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:k012x1(k)0.00.75x2(k)0.00.9 x3(k)0.0–0.3125 x(k)-x(k-1)0.9LẶ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) x1 (mới): dùng x2 (cũ), x3 (cũ) x2 (mới): dùng x1 (mới), x3 (cũ) x3 (mới): dùng x1 (mới), x2 (mới) 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áiGauss - Seidel: Biết x(k)  Tính vế phải b(k)  Giải hệ ra x(k+1)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:Phép lặp  Thay hệ Ax = b bằng giải liên tiếp nhiều hệ x2b10kx(k)-x(k-1) 0.0x3(k) 0.0x2(k)0.0x1(k)bxbxTỔNG KẾT LẶP JACOBI & GAUSS – SEIDEL ---------------------------------------------------------------------------------------------------------------------------x = Tx + cLặp JacobiLặp Gauss– SeidelHỆ PHƯƠNG TRÌNH BỊ NHIỄU--------------------------------------------------------------------------------------------------------------------------Minh hoạ: Giải 2 hệ phương trình và nhận xétHệ “gần” nhau, nghiệm “xa” nhau! Do detA  0: VÍ DỤ WILSON: Ax = b, detA = 1--------------------------------------------------------------------------------------------------------------------------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 Số điều kiện: (A) = ||A|| . ||A–1|| đặ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) >> 1VÍ DỤ ---------------------------------------------------------------------------------------------------------------------------VD Wilson:VD: Tính số điều kiện theo chuẩn vô cùng (A) của ma trận PHƯƠNG PHÁP TÌM MA TRẬN NGƯỢC ---------------------------------------------------------------------------------------------------------------------------Tính ma trận ngược Giải hệ phương trình A.c1 = e1 = [1 0]T (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 = e2 = [0 1]T (vectơ đơn vị thứ nhì)  Cột 2 của A-1 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 vectơ nghiệm c1, c2, c3: 3 cột của ma trận ngược A–1 cần tìm