Các phương pháp lặp dừng và thư giãn

Các phương pháp lặp dừng giải một hệ phương trình tuyến tính bằng cách phân tách ma trận và lặp lại áp dụng một quy tắc cập nhật cố định; các lược đồ Jacobi, Gauss-Seidel cổ điển và thư giãn quá mức liên tiếp là những ví dụ nền tảng.

Definition

Một phương pháp lặp dừng là phương pháp mà phép cập nhật áp dụng cùng một ma trận lặp ở mỗi bước, được suy ra từ việc phân tách ma trận hệ số thành một phần dễ đảo ngược và một phần còn lại; sự hội tụ được điều chỉnh bởi bán kính phổ của ma trận lặp kết quả.

Scope

Chủ đề này bao gồm khung phân tách ma trận, các phép lặp Jacobi và Gauss-Seidel, thư giãn quá mức liên tiếp và việc lựa chọn tham số thư giãn tối ưu, tiêu chí bán kính phổ để hội tụ, và vai trò của các phép lặp đơn giản này ngày nay như các bộ làm mịn trong đa lưới và như các bộ tiền điều kiện.

Core questions

• Việc phân tách ma trận mang lại phép lặp điểm cố định cho hệ phương trình tuyến tính như thế nào?
• Các phương pháp Jacobi và Gauss-Seidel khác nhau như thế nào, và tại sao Gauss-Seidel thường nhanh hơn?
• Thư giãn quá mức tăng tốc độ hội tụ như thế nào, và tham số tối ưu được chọn như thế nào?
• Trong điều kiện nào của ma trận thì các phép lặp này hội tụ?

Key theories

Phân tách ma trận và tiêu chí bán kính phổ

Viết ma trận dưới dạng một phần dễ đảo ngược trừ đi một phần còn lại định nghĩa một phép lặp dừng mà sai số của nó được nhân với một ma trận lặp mỗi bước; phép lặp hội tụ cho mọi giá trị khởi tạo nếu và chỉ nếu bán kính phổ của ma trận lặp đó nhỏ hơn một.

Thư giãn quá mức liên tiếp

Bằng cách vượt quá hiệu chỉnh Gauss-Seidel với một hệ số thư giãn, thư giãn quá mức liên tiếp có thể giảm đáng kể bán kính phổ; đối với một số ma trận có cấu trúc, một tham số thư giãn tối ưu được biết đến một cách phân tích và mang lại sự tăng tốc đáng kể.

Mechanisms

Phương pháp Jacobi cập nhật mọi ẩn số đồng thời chỉ sử dụng các giá trị từ lần quét trước, tương đương với việc tách phần đường chéo. Gauss-Seidel sử dụng các giá trị được cập nhật gần đây nhất trong cùng một lần quét, tách phần tam giác dưới, thường hội tụ nhanh hơn. Thư giãn quá mức liên tiếp tạo thành một trung bình có trọng số của giá trị cũ và cập nhật Gauss-Seidel được điều chỉnh bởi một tham số thư giãn; việc chọn tham số này lớn hơn một sẽ tăng tốc độ hội tụ cho các ma trận phù hợp. Sự hội tụ cho cả ba phương pháp được đảm bảo cho các lớp ma trận như ma trận chéo trội chặt chẽ hoặc ma trận đối xứng xác định dương, và được định lượng bằng bán kính phổ của ma trận lặp.

Clinical relevance

Mặc dù thường quá chậm để cạnh tranh như các bộ giải độc lập cho các hệ thống lớn, các phương pháp dừng vẫn quan trọng như các bộ làm mịn cốt lõi của đa lưới, như các bộ tiền điều kiện đơn giản cho các phương pháp Krylov, và như các khối xây dựng dễ dàng song song hóa; đặc biệt Gauss-Seidel và Jacobi có trọng số phổ biến trong các bộ giải đa cấp hiện đại.

History

Các phép lặp Jacobi và Gauss-Seidel có từ thế kỷ XIX, trong khi thư giãn quá mức liên tiếp và lý thuyết hội tụ chặt chẽ của nó được David Young và Richard Varga phát triển vào những năm 1950; mặc dù sau đó bị lu mờ bởi các phương pháp Krylov và đa lưới như các bộ giải chính, các phép lặp này đã được hồi sinh như những thành phần thiết yếu của các lược đồ đa cấp và tiền điều kiện.

Key figures

• Carl Friedrich Gauss
• Philipp Ludwig von Seidel
• David M. Young
• Richard S. Varga

Seminal works

• saad2003
• varga2000

Frequently asked questions

Tại sao Gauss-Seidel thường nhanh hơn Jacobi?

Gauss-Seidel ngay lập tức sử dụng các giá trị đã được cập nhật trong cùng một lần quét, do đó thông tin lan truyền nhanh hơn qua các ẩn số, thường giảm một nửa số lần lặp so với Jacobi, vốn chỉ sử dụng các giá trị từ lần quét trước.

Nếu các phương pháp này chậm, tại sao chúng vẫn được nghiên cứu?

Chúng là những bộ làm mịn tuyệt vời và bộ tiền điều kiện đơn giản. Trong đa lưới, một vài lần quét Gauss-Seidel hoặc Jacobi có trọng số loại bỏ hiệu quả lỗi dao động, đây chính xác là vai trò mà đa lưới cần, vì vậy các phép lặp cổ điển này vẫn tồn tại như các thành phần của các bộ giải hiện đại nhanh chóng.