Gradient liên hợp (conjugate gradient)

liên hợp tuyến tính là thuật toán lặp để giải hệ $Hz=b$ khi H đối xứng dương xác định. Nó tạo các hướng liên hợp theo H và chỉ cần phép nhân H với , nên có thể tránh lưu một dày.

Lĩnh vực: Thuật toán tối ưu

Định nghĩa trên trang này được dùng trong lĩnh vực vừa nêu. Một từ giống nhau ở môn khác có thể mang nghĩa khác.

Bài giảng dùng khái niệm này

• Các phương pháp tối ưu trong học sâuToán cho AI

Giải thích kỹ thuật

Các hướng liên hợp theo . Với $H\succ 0$, hai hướng $p_i,p_j$ liên hợp khi $p_i^{T}H{p}_j=0$. CG xây các hướng như vậy từ phần dư $r=b-Hz$, nhờ đó trong số học chính xác giải hệ $n$ chiều sau nhiều nhất $n$ bước.

Trong số học máy, tính trực giao liên hợp bị ảnh hưởng bởi làm tròn. Tiền điều kiện có thể cải thiện tốc độ. CG tuyến tính giải hệ SPD khác với CG phi tuyến dùng cho một hàm tổng quát. Nguồn: Shewchuk, An Introduction to the Conjugate Method, §8.

Ví dụ

Với $H=diag(1,2)$, $b=(1,1)$, nghiệm của $Hz=b$ là $z=(1,\frac{1}{2})$.

Khi nào cần dùng?

Giải gần đúng hệ Newton lớn hoặc hệ SPD.

Câu hỏi ôn lại

Có thể áp dụng trực tiếp công thức CG tuyến tính khi bất định không?

Xem đáp án

Không. Giả thiết SPD phải được bảo đảm hoặc xử lý bằng phương pháp khác.

Thuật ngữ liên quan

• Hessian
• Hệ phương trình tuyến tính
• BFGS