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 ---------------------------------------------------------------------------------------------------------------------------