Stationary Iterative Methods and the Conjugate Gradient Method for Solving Linear Systems

Abstract

บทคัดย่อ วิธีทำซ้ำสำหรับหาผลเฉลยระบบเชิงเส้นมีอยู่ด้วยกัน 2 แบบใหญ่ ๆ คือ วิธีทำซ้ำอย่างนิ่งกับวิธีปริภูมิย่อยไครลอฟ บทความวิชาการนี้อภิปรายแนวคิดทั่วไปและเทคนิคพื้นฐานของวิธีทำซ้ำอย่างนิ่ง ได้แก่ วิธีจาโคบี วิธีเกาส์-ไซเดล และวิธีผ่อนปรนเกินสืบเนื่อง นอกจากนั้นยังพิจารณาวิธีทำซ้ำที่พัฒนาต่อยอดจากวิธีดังกล่าว ได้แก่ วิธีผ่อนปรนเกินแบบเร่ง วิธีทำซ้ำที่มีฐานจากเกรเดียนต์ เและวิธีทำซ้ำกำลังสองน้อยสุด สำหรับวิธีปริภูมิย่อยไครลอฟนั้นมีต้นแบบมาจากวิธีคอนจูเกตเกรเดียนต์ วิธีดังกล่าวจะสร้างฐานหลักเชิงตั้งฉากของปริภูมิแบบยุคลิดจากเมทริกซ์สัมประสิทธิ์โดยพิจารณาจากเกรเดียนต์ของฟังก์ชันกำลังสองที่สอดคล้อง ฐานหลักดังกล่าวประกอบด้วยเวกเตอร์ที่มีทิศทางที่ทำให้ผลเฉลยค่าประมาณเข้าใกล้ผลเฉลยจริงได้เร็วที่สุด กล่าวโดยสรุปได้ว่า วิธีทำซ้ำอย่างนิ่ง 4 วิธีแรกที่กล่าวมานั้นจะการันตีการลู่เข้าของลำดับของผลเฉลยโดยประมาณสู่ผลเฉลยจริงเมื่อใช้กับระบบที่มีเมทริกซ์สัมประสิทธิ์อยู่ในรูปแบบเฉพาะ เช่น เมทริกซ์แนวทแยงมุมข่มแท้ เมทริกซ์ลดทอนไม่ได้ และเมทริกซ์แบบแอล โดยต้องกำหนดตัวแปรเสริมที่เหมาะสม ส่วนวิธีทำซ้ำที่มีฐานจากเกรเดียนต์และวิธีทำซ้ำกำลังสองน้อยสุดใช้ได้กับระบบที่มีเมทริกซ์สัมประสิทธิ์มีค่าลำดับชั้นเต็ม สำหรับวิธีคอนจูเกตเกรเดียนต์ใช้ได้กับระบบที่เมทริกซ์สัมประสิทธิ์เป็นเมทริกซ์สมมาตรที่เป็นบวกแน่นอน คำสำคัญ: ระบบเชิงเส้น วิธีผ่อนปรนเกินสืบเนื่อง  วิธีผ่อนปรนเกินแบบเร่ง วิธีทำซ้ำที่มีฐานจากเกรเดียนต์  วิธีคอนจูเกตเกรเดียนต์  ABSTRACT There are two major types of iterative methods for solving linear systems, namely, stationary iterative methods and Krylov subspace methods. This survey article discusses general ideas and elementary techniques for stationary iterative methods such as Jacobi method, Gauss-Seidel method, and the successive over-relaxation method. Moreover, we investigate further developed methods, namely, the accelerated over-relaxation method, the gradient based iterative method, and the least squares iterative method. On the other hand, Krylov subspace methods have prototypes from the conjugate gradient method. The latter method constructs an orthogonal basis for the Euclidean space from the gradient of the associated quadratic function. Such basis consists of vectors in directions so that the approximated solutions fastest approach to the exact solution. In conclusions, all 1st-4th mentioned stationary iterative methods guarantee the convergence of the sequence of approximated solutions to the exact solution when applying to the system with specific coefficient matrices such as strictly diagonally dominant matrices, irreducible matrices, and L-matrices. Here, the parameters in the methods must be appropriate. The gradient based iterative method and the least squares iterative method can be applied to systems with full-column rank coefficient matrices. The conjugate gradient method is applicable for the system whose coefficient matrix is a positive definite symmetric matrix.Keywords: linear system, successive over-relaxation method, accelerated over-relaxation method, gradient based iterative method, conjugate gradient method