เหตุใด Gauss-Seidel จึงเร็วกว่า Jacobi โดยทั่วไป?

Gauss-Seidel ใช้ค่าที่ได้รับการปรับปรุงทันทีภายในรอบเดียวกัน ดังนั้นข้อมูลจึงแพร่กระจายผ่านค่าที่ไม่ทราบได้เร็วกว่า โดยทั่วไปจะลดจำนวนการวนซ้ำลงครึ่งหนึ่งเมื่อเทียบกับ Jacobi ซึ่งใช้เฉพาะค่าจากการกวาดครั้งก่อนหน้า

หากวิธีเหล่านี้ช้า เหตุใดจึงยังคงมีการศึกษา?

วิธีเหล่านี้เป็นตัวปรับเรียบที่ยอดเยี่ยมและเป็นตัวปรับสภาพที่เรียบง่าย ภายในมัลติกริด การกวาดแบบ Gauss-Seidel หรือ weighted-Jacobi เพียงไม่กี่ครั้งจะช่วยขจัดข้อผิดพลาดแบบสั่นได้อย่างมีประสิทธิภาพ ซึ่งเป็นบทบาทที่มัลติกริดต้องการอย่างแท้จริง ดังนั้นการวนซ้ำแบบคลาสสิกเหล่านี้จึงยังคงมีชีวิตอยู่เป็นส่วนประกอบของตัวแก้ปัญหาที่ทันสมัยและรวดเร็ว

วิธีการวนซ้ำแบบคงที่และการผ่อนคลาย (Stationary and Relaxation Methods)

วิธีการวนซ้ำแบบคงที่ (Stationary iterative methods) ใช้ในการแก้ระบบสมการเชิงเส้นโดยการแยกเมทริกซ์และประยุกต์ใช้กฎการปรับปรุงที่ตายตัวซ้ำๆ; ตัวอย่างพื้นฐานได้แก่ วิธี Jacobi, Gauss-Seidel และ successive over-relaxation แบบคลาสสิก

ค้นหาหัวข้อด้วย PaperMindเร็ว ๆ นี้Find papers & topics

Tools & resources

ดาวน์โหลดสไลด์

Learn & explore

วิดีโอเร็ว ๆ นี้

Definition

วิธีการวนซ้ำแบบคงที่คือวิธีที่การปรับปรุงใช้เมทริกซ์การวนซ้ำเดียวกันในทุกขั้นตอน ซึ่งได้มาจากการแยกเมทริกซ์สัมประสิทธิ์ออกเป็นส่วนที่สามารถผกผันได้ง่ายและส่วนที่เหลือ; การลู่เข้าถูกควบคุมโดยรัศมีสเปกตรัมของเมทริกซ์การวนซ้ำที่ได้

Scope

หัวข้อนี้ครอบคลุมกรอบการแยกเมทริกซ์ (matrix-splitting framework), การวนซ้ำของ Jacobi และ Gauss-Seidel, successive over-relaxation และการเลือกพารามิเตอร์การผ่อนคลายที่เหมาะสมที่สุด, เกณฑ์รัศมีสเปกตรัม (spectral-radius criterion) สำหรับการลู่เข้า, และบทบาทของการวนซ้ำแบบง่ายเหล่านี้ในปัจจุบันในฐานะตัวปรับเรียบ (smoothers) ภายในมัลติกริด (multigrid) และในฐานะตัวปรับสภาพ (preconditioners)

Core questions

การแยกเมทริกซ์ทำให้เกิดการวนซ้ำแบบจุดตรึง (fixed-point iteration) สำหรับระบบเชิงเส้นได้อย่างไร?
วิธี Jacobi และ Gauss-Seidel แตกต่างกันอย่างไร และเหตุใด Gauss-Seidel จึงเร็วกว่าโดยทั่วไป?
การผ่อนคลายเกิน (over-relaxation) เร่งการลู่เข้าได้อย่างไร และจะเลือกพารามิเตอร์ที่เหมาะสมที่สุดได้อย่างไร?
ภายใต้เงื่อนไขใดของเมทริกซ์ที่การวนซ้ำเหล่านี้จะลู่เข้า?

Key theories

การแยกเมทริกซ์และเกณฑ์รัศมีสเปกตรัม: การเขียนเมทริกซ์เป็นส่วนที่สามารถผกผันได้ง่ายลบด้วยส่วนที่เหลือ จะกำหนดการวนซ้ำแบบคงที่ซึ่งข้อผิดพลาดจะถูกคูณด้วยเมทริกซ์การวนซ้ำในแต่ละขั้นตอน; การวนซ้ำจะลู่เข้าสำหรับทุกการคาดเดาเริ่มต้นก็ต่อเมื่อรัศมีสเปกตรัมของเมทริกซ์การวนซ้ำนั้นน้อยกว่าหนึ่ง
Successive over-relaxation: ด้วยการปรับแก้ Gauss-Seidel เกินด้วยปัจจัยการผ่อนคลาย (relaxation factor) วิธี successive over-relaxation สามารถลดรัศมีสเปกตรัมได้อย่างมาก; สำหรับเมทริกซ์ที่มีโครงสร้างบางอย่าง พารามิเตอร์การผ่อนคลายที่เหมาะสมที่สุดเป็นที่ทราบในเชิงวิเคราะห์และให้ความเร็วที่เพิ่มขึ้นอย่างมาก

Mechanisms

วิธี Jacobi ปรับปรุงค่าที่ไม่ทราบทั้งหมดพร้อมกันโดยใช้เฉพาะค่าจากการกวาดครั้งก่อนหน้า ซึ่งเทียบเท่ากับการแยกส่วนแนวทแยงออก วิธี Gauss-Seidel ใช้ค่าที่ได้รับการปรับปรุงล่าสุดภายในรอบเดียวกัน โดยแยกส่วนสามเหลี่ยมล่างออก ซึ่งโดยทั่วไปจะลู่เข้าได้เร็วกว่า วิธี successive over-relaxation สร้างค่าเฉลี่ยถ่วงน้ำหนักของค่าเก่าและการปรับปรุงแบบ Gauss-Seidel ซึ่งควบคุมโดยพารามิเตอร์การผ่อนคลาย; การเลือกพารามิเตอร์นี้ให้มีค่ามากกว่าหนึ่งจะช่วยเร่งการลู่เข้าสำหรับเมทริกซ์ที่เหมาะสม การลู่เข้าสำหรับทั้งสามวิธีรับประกันสำหรับคลาสของเมทริกซ์ เช่น เมทริกซ์ที่มีแนวทแยงเด่นอย่างเคร่งครัด (strictly diagonally dominant) หรือเมทริกซ์สมมาตรบวกแน่นอน (symmetric positive-definite) และถูกวัดปริมาณโดยรัศมีสเปกตรัมของเมทริกซ์การวนซ้ำ

Clinical relevance

แม้ว่าโดยทั่วไปจะช้าเกินไปที่จะเป็นตัวแก้ปัญหาแบบเดี่ยวที่แข่งขันได้สำหรับระบบขนาดใหญ่ แต่วิธีการแบบคงที่ยังคงมีความสำคัญในฐานะตัวปรับเรียบที่เป็นหัวใจของมัลติกริด ในฐานะตัวปรับสภาพอย่างง่ายสำหรับวิธี Krylov และในฐานะองค์ประกอบพื้นฐานที่สามารถขนานกันได้ง่าย; โดยเฉพาะอย่างยิ่ง Gauss-Seidel และ weighted Jacobi มีอยู่ทั่วไปในตัวแก้ปัญหาแบบหลายระดับที่ทันสมัย

History

การวนซ้ำของ Jacobi และ Gauss-Seidel มีมาตั้งแต่ศตวรรษที่สิบเก้า ในขณะที่ successive over-relaxation และทฤษฎีการลู่เข้าที่เข้มงวดได้รับการพัฒนาโดย David Young และ Richard Varga ในทศวรรษ 1950; แม้ว่าในภายหลังจะถูกบดบังด้วยวิธี Krylov และ multigrid ในฐานะตัวแก้ปัญหาหลัก แต่การวนซ้ำเหล่านี้ก็ได้รับการฟื้นฟูให้เป็นองค์ประกอบสำคัญของแผนการแบบหลายระดับและแบบปรับสภาพ

Key figures

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

Seminal works

saad2003
varga2000

Frequently asked questions

เหตุใด Gauss-Seidel จึงเร็วกว่า Jacobi โดยทั่วไป?: Gauss-Seidel ใช้ค่าที่ได้รับการปรับปรุงทันทีภายในรอบเดียวกัน ดังนั้นข้อมูลจึงแพร่กระจายผ่านค่าที่ไม่ทราบได้เร็วกว่า โดยทั่วไปจะลดจำนวนการวนซ้ำลงครึ่งหนึ่งเมื่อเทียบกับ Jacobi ซึ่งใช้เฉพาะค่าจากการกวาดครั้งก่อนหน้า
หากวิธีเหล่านี้ช้า เหตุใดจึงยังคงมีการศึกษา?: วิธีเหล่านี้เป็นตัวปรับเรียบที่ยอดเยี่ยมและเป็นตัวปรับสภาพที่เรียบง่าย ภายในมัลติกริด การกวาดแบบ Gauss-Seidel หรือ weighted-Jacobi เพียงไม่กี่ครั้งจะช่วยขจัดข้อผิดพลาดแบบสั่นได้อย่างมีประสิทธิภาพ ซึ่งเป็นบทบาทที่มัลติกริดต้องการอย่างแท้จริง ดังนั้นการวนซ้ำแบบคลาสสิกเหล่านี้จึงยังคงมีชีวิตอยู่เป็นส่วนประกอบของตัวแก้ปัญหาที่ทันสมัยและรวดเร็ว