طرق التكرار الثابتة والاسترخاء
تحل طرق التكرار الثابتة نظامًا خطيًا عن طريق تقسيم المصفوفة وتطبيق قاعدة تحديث ثابتة بشكل متكرر؛ وتُعد مخططات جاكوبي وجاوس-سايدل والاسترخاء المتتالي الزائد الأمثلة الأساسية.
Definition
الطريقة التكرارية الثابتة هي تلك التي يطبق تحديثها نفس مصفوفة التكرار في كل خطوة، وهي مشتقة من تقسيم مصفوفة المعاملات إلى جزء سهل الانعكاس وجزء متبقي؛ ويتحكم نصف القطر الطيفي لمصفوفة التكرار الناتجة في التقارب.
Scope
يغطي هذا الموضوع إطار تقسيم المصفوفة، وتكرارات جاكوبي وجاوس-سايدل، والاسترخاء المتتالي الزائد واختيار معامل الاسترخاء الأمثل، ومعيار نصف القطر الطيفي للتقارب، والدور الذي تلعبه هذه التكرارات البسيطة اليوم كـ 'مُنعّمات' (smoothers) ضمن الشبكات المتعددة (multigrid) وكمُهيّئات (preconditioners).
Core questions
- كيف يؤدي تقسيم المصفوفة إلى تكرار نقطة ثابتة للنظام الخطي؟
- ما هي أوجه الاختلاف بين طريقتي جاكوبي وجاوس-سايدل، ولماذا تكون طريقة جاوس-سايدل أسرع عادةً؟
- كيف يسرّع الاسترخاء الزائد التقارب، وكيف يتم اختيار المعامل الأمثل؟
- تحت أي شروط على المصفوفة تتقارب هذه التكرارات؟
Key theories
- تقسيم المصفوفة ومعيار نصف القطر الطيفي
- تؤدي كتابة المصفوفة كجزء سهل الانعكاس مطروحًا منه جزء متبقي إلى تعريف تكرار ثابت يتضاعف خطأه بواسطة مصفوفة تكرار في كل خطوة؛ ويتقارب التكرار لكل تخمين بدء إذا وفقط إذا كان نصف القطر الطيفي لمصفوفة التكرار هذه أقل من واحد.
- الاسترخاء المتتالي الزائد
- من خلال تجاوز تصحيح جاوس-سايدل بعامل استرخاء، يمكن للاسترخاء المتتالي الزائد أن يقلل بشكل كبير من نصف القطر الطيفي؛ وبالنسبة لبعض المصفوفات المهيكلة، يُعرف معامل الاسترخاء الأمثل تحليليًا ويؤدي إلى تسريع كبير.
Mechanisms
تُحدّث طريقة جاكوبي كل مجهول في وقت واحد باستخدام قيم من المسح السابق فقط، وهو ما يعادل فصل القطر. تستخدم طريقة جاوس-سايدل أحدث القيم المحدثة ضمن نفس المسح، مع فصل الجزء المثلثي السفلي، والذي يتقارب عادةً بشكل أسرع. يشكل الاسترخاء المتتالي الزائد متوسطًا مرجحًا للقيمة القديمة وتحديث جاوس-سايدل الذي يحكمه معامل استرخاء؛ ويؤدي اختيار هذا المعامل أكبر من واحد إلى تسريع التقارب للمصفوفات المناسبة. يضمن التقارب للطرق الثلاث لفئات مثل المصفوفات ذات القطر المهيمن بشكل صارم أو المصفوفات المتماثلة الموجبة المحددة، ويتم تحديد كميته بواسطة نصف القطر الطيفي لمصفوفة التكرار.
Clinical relevance
على الرغم من أنها عادةً ما تكون بطيئة جدًا بحيث لا تكون حلولًا تنافسية قائمة بذاتها للأنظمة الكبيرة، إلا أن الطرق الثابتة تظل مهمة كـ 'مُنعّمات' في قلب الشبكات المتعددة، وكمُهيّئات بسيطة لطرق كريلوف، وكمكونات بناء سهلة التوازي؛ وتنتشر طرق جاوس-سايدل وجاكوبي المرجحة بشكل خاص داخل حلول المستويات المتعددة الحديثة.
History
يعود تاريخ تكرارات جاكوبي وجاوس-سايدل إلى القرن التاسع عشر، بينما طوّر ديفيد يونغ وريتشارد فارغا الاسترخاء المتتالي الزائد ونظريته الصارمة للتقارب في الخمسينيات؛ وعلى الرغم من أن طرق كريلوف والشبكات المتعددة قد طغت عليها لاحقًا كحلول أساسية، إلا أن هذه التكرارات أُعيد إحياؤها كمكونات أساسية للمخططات متعددة المستويات والمُهيّئة.
Key figures
- Carl Friedrich Gauss
- Philipp Ludwig von Seidel
- David M. Young
- Richard S. Varga
Related topics
Seminal works
- saad2003
- varga2000
Frequently asked questions
- لماذا تكون طريقة جاوس-سايدل أسرع عادةً من جاكوبي؟
- تستخدم طريقة جاوس-سايدل القيم المحدثة على الفور ضمن نفس المسح، لذا تنتشر المعلومات بشكل أسرع عبر المجاهيل، مما يقلل عادةً عدد التكرارات إلى النصف مقارنةً بطريقة جاكوبي، التي تستخدم قيمًا من المسح السابق فقط.
- إذا كانت هذه الطرق بطيئة، فلماذا لا تزال تُدرس؟
- إنها 'مُنعّمات' ممتازة ومُهيّئات بسيطة. فداخل الشبكات المتعددة، تعمل بضع مسحات من جاوس-سايدل أو جاكوبي المرجحة على إزالة الأخطاء المتذبذبة بكفاءة، وهو بالضبط الدور الذي تحتاجه الشبكات المتعددة، لذا تستمر هذه التكرارات الكلاسيكية كمكونات لحلول حديثة سريعة.