Phương pháp Gradient liên hợp giải hệ phương trình đại số tuyến tính

Phương pháp Gradient liên hợp được Hestenses và Stiefel nêu ra đầu tiên vào những năm 1950 để giải hệ phương trình đại số tuyến tính (PTĐSTT). Vì việc giải một hệ phương trình tuyến tính tương đương với việc tìm cực tiểu của một hàm toàn phương xác định dương nên năm 1960 Fletcher – Reeves đã cải biên và phát triển nó thành phương pháp Gradient liên hợp cho cực tiểu không ràng buộc.
Nội dung trích xuất từ tài liệu:
Phương pháp Gradient liên hợp giải hệ phương trình đại số tuyến tính Bùi Thị Thanh Xuân và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 117 - 121 PHƢƠNG PHÁP GRADIENT LIÊN HỢP GIẢI HỆ PHƢƠNG TRÌNH ĐẠI SỐ TUYẾN TÍNH Bùi Thị Thanh Xuân*, Dương Thị Nhung Trường Đại học Công nghệ thông tin và Truyền thông – ĐH Thái Nguyên TÓM TẮT Phương pháp Gradient liên hợp được Hestenses và Stiefel nêu ra đầu tiên vào những năm 1950 để giải hệ phương trình đại số tuyến tính (PTĐSTT). Vì việc giải một hệ phương trình tuyến tính tương đương với việc tìm cực tiểu của một hàm toàn phương xác định dương nên năm 1960 Fletcher – Reeves đã cải biên và phát triển nó thành phương pháp Gradient liên hợp cho cực tiểu không ràng buộc. Phương pháp Gradient liên hợp (CG) chỉ cần tới đạo hàm bậc nhất nhưng làm tăng hiệu quả và độ tin cậy của thuật toán. Trên cơ sở đó, bài báo nghiên cứu thuật toán CG và cài đặt thử nghiệm trên Matlab. Từ khóa: hệ phương trình đại số tuyến tính, phương pháp lặp, phương pháp Gradient liên hợp, CG, dạng toàn phương. TỔNG QUAN* Xét hệ phương trình đại số tuyến tính Ax b trong đó A là ma trận vuông cấp n, x và b là véc tơ n chiều a11 a21 ... an1 a12 a22 ... an 2 ... a1n ... a2 n ... ... ... ann x1 x2 ... xn b1 b2 ... bn Hệ phương trình đại số tuyến tính xuất hiện trong rất nhiều lĩnh vực như trong kinh tế, thống kê, hệ thống điện, xử lý ảnh, tối ưu hóa, giải số các phương trình vi phân,... với kích thước của bài toán n có thể là 2 hoặc đến hàng chục triệu. Do đó một yêu cầu cần thiết là cần có các phương pháp hiệu quả để giải hệ đại số tuyến tính nói trên. Các nhà Toán học đã nghiên cứu các phương pháp giải hệ ĐSTT và phân loại thành 2 nhóm phương pháp giải: phương pháp trực tiếp (phương pháp cho ta nghiệm đúng của hệ sau một số hữu hạn các phép tính) và phương pháp lặp (phương pháp k xây dựng một dãy vô hạn các xấp xỉ x mà giới hạn của nó là nghiệm đúng của hệ) Các nhà toán học cũng đưa ra sự hạn chế của các phương pháp trực tiếp. Chẳng hạn như phương pháp Cramer về mặt lý thuyết là giải được hệ với n tùy ý, trong thực tế nếu ta có hệ * n ẩn số phương pháp Cramer cần n!(n+1)(n-1) phép tính số học, khi đó máy tính hiện đại không thể tính được với n =20! Hay với 2 phương pháp Gauss đòi hỏi n 3 phép tính và 3 ổn định. Như hơn nữa thuật toán Gauss không vậy để giải số các bài toán có kích thước lớn cần dùng đến các phương pháp lặp.Các phương pháp lặp có thể kể đến như phương pháp Jacobi, Gauss-Seidel, phương pháp độ dốc lớn nhất (Steepest descent), ...đặc biệt là phương pháp Gradient liên hợp (Conjugate Gradient method) tỏ ra hiệu quả khi ma trận hệ số là ma trận đối xứng, xác định dương. Trong không gian R n ta đưa vào một tích vô hướng mới được xác định bởi công thức: x, y A Ax, y , trong đó .,. là tích vô hướng thông thường cho bởi x, y n xi yi . i 1 Tích vô hướng mới này được gọi là tích năng lượng và chuẩn cảm sinh bởi nó được gọi là chuẩn năng lượng. Như vậy x A Ax, x Xét quá trình lặp B x(k 1) x(k ) Ax ( k ) b,k 0,1, 2... (*) 0 với x bất kỳ. Định lý Samarski: Giả sử A là ma trận đối xứng xác định dương và B là ma trận xác định Tel: 0906 062458, Email: bttxuan@ictu.edu.vn 117 Bùi Thị Thanh Xuân và Đtg dương. Khi đó nếu B Tạp chí KHOA HỌC & CÔNG NGHỆ A thì phương pháp 2 lặp (*) hội tụ theo chuẩn năng lượng của A, tức là lim x k x 0. k A PHƢƠNG PHÁP ĐỘ DỐC LỚN NHẤT (STEEPEST DESCENT) Cho hệ phương trình đại số tuyến tính Ax b với giả thiết A là ma trận đối xứng xác định dương xT Ax 0, x 0. Bài toán trên tương đương với bài toán cực x , trong tiểu hóa dạng toàn phương: minn x  đó dạng toàn phương x 1 T x Ax 2 b x Gradient của dạng toàn phương: T x x1 x , x2 x ,.., xn x . Gradient là trường véc tơ hướng theo hướng x tại điểm x đã cho giảm nhanh nhất của x 1 T 1 A x Ax b . 2 2 x Ax b . Cho Nếu A đối xứng thì gradient bằng 0 ta thu được nghiệm của phương trình Ax b . Nghiệm của phương trình là điểm tới hạn của hàm . Nếu A vừa đối xứng vừa xác định dương thì nghiệm của phương trình Ax b là điểm cực x . tiểu toàn cục của Do x đạt cực trị khi gradient x Ax b 0 nên bài toán tìm cực trị tương đương với việc giải hệ phương trình đại số tuyến tính Ax b . Ta biết rằng gradient là hướng hàm tăng nhanh nhất. Như thế muốn đi đến cực tiểu ta cho x, tính gradient và tìm theo hướng ngược lại cho đến khi hàm không giảm nữa. Phương pháp độ dốc lớn nhất (steepest desceent) thực hiện như sau: - Xuất phát từ x0 tạo ra dãy x1 , x2 ,... tiến gần đến nghiệm x. - Tại mỗi bước chọn hướng giảm nhanh nhất – hướng ngược lại với gradient của tại xi b Axi xi : 118 Sai số ei xi vậy Aei ; ri ri x . Độ lệch ri b Axi . Như độ lệch là xi hướng giảm nhanh nhất của hàm x . Thuật toán Steepest Descent Cho x0 Tính r0 b Ax0 Lặp k =1,2,... rk T rk rk T Ark k xk rk T 116 (02): 117 - 121 xk 1 b 1 r k k Axk 1 cho tới khi hội tụ. Phương pháp Steepest descent lặp theo hướng của các bước trước nên hội tụ không nhanh, sẽ hiệu quả hơn ...