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