Chương 2 Hệ phương trình tuyến tính ax = b

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) 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 TỔ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) PHƯƠNG PHÁP KHỬ GAUSS----------------------------------------------------------------------------------------------------------------------------------- Xây dựng ma trận mở rộng Khử cột 1 với hệ số khử m1j GIẢI LÙI & PHẦN TỬ TRỤ ------------------------------------------------------------------------------------------------------------------------------- KHỬ GAUSS VỚI LỆNH MAPLE -------------------------------------------------------------------------------------------------------------------------------- KHỬ GAUSS VỚI MA TRẬN “LẺ”: PIVOT ĐƠN VỊ ------------------------------------------------------------------------------------------------------------------------------------- THỰC TẾ TÍNH TOÁN: VẤN ĐỀ LÀM TRÒN SỐ --------------------------------------------------------------------------------------------------------------------------------- Biến đổi cột một: (E2)  (E2) – m21(E1) PHÂN TÍCH NHÂN TỬ (MATRIX FACTORIZATIONS) --------------------------------------------------------------------------------------------------------------------------------- Giải hệ đầu  Giải 2 hệ : Ly = b (2) tìm y; Ux = y (1) tìm x VÍ DỤ --------------------------------------------------------------------------------------------------------------------------------- Giải Ly = b tìm y Giải Ux = y tìm x 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 GIẢI THUẬT TÌM LU (CROUT – DOOLITLE) --------------------------------------------------------------------------------------------------------------------------------- MINH HOẠ GIẢI THUẬT DOOLITLE (ĐCHÉO L = 1) ------------------------------------------------------------------------------------------------------------------------------- PHÂN TÍCH CHOLESKY ---------------------------------------------------------------------------------------------------------------------------- Tương tự phân tích LU nhưng gọn hơn “phân nửa”! 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 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 ------------------------------------------------------------------------------------------------------------------------------- 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 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 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 CÔNG THỨC LẶP JACOBI --------------------------------------------------------------------------------------------------------------------------- 2/ Từ x(0) tính x(1): LẶP JACOBI KHÔNG BIẾN ĐỔI MA TRẬN A --------------------------------------------------------------------------------------------------------------------------- Hệ Ax = b: 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) LẶP GAUSS – SEIDEL --------------------------------------------------------------------------------------------------------------------------- Tương tự lặp Jacobi nhưng với thông tin cập nhật hoá 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 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: TỔNG KẾT LẶP JACOBI & GAUSS – SEIDEL --------------------------------------------------------------------------------------------------------------------------- HỆ PHƯƠNG TRÌNH BỊ NHIỄU-------------------------------------------------------------------------------------------------------------------------- Minh hoạ: Giải 2 hệ phương trình và nhận xét VÍ DỤ WILSON: Ax = b, detA = 1-------------------------------------------------------------------------------------------------------------------------- SỐ ĐIỀU KIỆN CỦA HỆ Ax = b-------------------------------------------------------------------------------------------------------------------------- Hệ điều kiện xấu (ill – conditionned): (A) >> 1 VÍ 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 ---------------------------------------------------------------------------------------------------------------------------