طرق فضاء كريلوف الجزئي

تعمل طرق فضاء كريلوف الجزئي على حل الأنظمة الخطية الكبيرة المتفرقة عن طريق استخلاص أفضل تقريب من الفضاء الجزئي المتولد عن طريق ضربات متكررة للمصفوفة في المتجه، ولا تحتاج إلا إلى تأثير المصفوفة بدلاً من مدخلاتها.

Definition

طريقة فضاء كريلوف الجزئي هي حلال تكراري يسعى، في الخطوة m، إلى حل تقريبي في فضاء كريلوف الجزئي ذي الأبعاد m والممتد بواسطة الباقي وصوره المتتالية تحت تأثير المصفوفة، مع اختيار التكرار بواسطة شرط إسقاط أو تصغير.

Scope

يغطي هذا الموضوع فضاء كريلوف الجزئي وبناءه بواسطة عمليتي أرنولدي ولانكزوس، وطريقة التدرج المترافق للأنظمة المتماثلة الموجبة المحددة، وطريقتي MINRES وGMRES للمصفوفات المتماثلة غير المحددة والعامة، وطرق التعامد الثنائي مثل BiCGSTAB، ونظرية التقارب التي تربط عدد التكرارات بالطيف ورقم الشرط.

Core questions

• ما هو فضاء كريلوف الجزئي، وكيف يتم بناء أساس متعامد له بشكل مستقر؟
• لماذا تعتبر طريقة التدرج المترافق مثالية وذات تكرار قصير للأنظمة المتماثلة الموجبة المحددة؟
• كيف تتعامل GMRES مع الأنظمة العامة غير المتماثلة، ولماذا تتطلب زيادة في التخزين؟
• كيف تحدد الخصائص الطيفية للمصفوفة معدل التقارب؟

Key theories

طريقة التدرج المترافق

بالنسبة للأنظمة المتماثلة الموجبة المحددة، تقلل طريقة التدرج المترافق معيار الطاقة للخطأ عبر فضاء كريلوف الجزئي باستخدام تكرار قصير ثلاثي الحدود، وتتقارب في n خطوة على الأكثر في الحساب الدقيق وبسرعة أكبر بكثير عندما تتجمع القيم الذاتية.

GMRES وعملية أرنولدي

بالنسبة للمصفوفات العامة، تستخدم GMRES عملية أرنولدي لبناء أساس كريلوف متعامد وتقلل معيار الباقي عبر الفضاء الجزئي، ولكن نظرًا لعدم وجود تكرار قصير بشكل عام، يجب عليها تخزين جميع متجهات الأساس، مما يحفز المتغيرات المعاد تشغيلها.

Mechanisms

تضرب كل طريقة متجهًا بالمصفوفة بشكل متكرر لتوسيع فضاء كريلوف الجزئي وتعامد الاتجاه الجديد مقابل الاتجاهات السابقة. بالنسبة للمصفوفات المتماثلة، تنتج عملية لانكزوس إسقاطًا ثلاثي الأقطار وتكرارًا قصيرًا، لذا فإن طريقتي التدرج المترافق وMINRES تحتاجان فقط إلى عدد قليل من المتجهات للتخزين. بالنسبة للمصفوفات غير المتماثلة، تنتج عملية أرنولدي إسقاطًا كاملاً من نوع هيسنبرغ العلوي، وتقلل GMRES الباقي عن طريق حل مشكلة المربعات الصغرى الصغيرة في كل خطوة، على حساب تخزين القاعدة بأكملها؛ ويحد إعادة التشغيل من هذه التكلفة. يتحدد التقارب بمدى توزيع القيم الذاتية بشكل إيجابي، وهو ما يهدف التكييف المسبق إلى تحسينه.

Clinical relevance

تُعد طرق كريلوف، وخاصة التدرج المترافق المسبق التكييف وGMRES، هي الحلول القياسية داخل أكواد محاكاة العناصر المحدودة والحجوم المحدودة، والتحسين واسع النطاق، والحوسبة العلمية بشكل عام؛ وتسمح طبيعتها الخالية من المصفوفات بحل أنظمة تحتوي على ملايين أو مليارات من المجهولات التي لا يمكن لأي طريقة مباشرة تحليلها.

History

تم تقديم طريقة التدرج المترافق بواسطة هيستينس وستيفل في عام 1952 وعملية لانكزوس الأساسية في عام 1950؛ وقد تم التعرف على قوتها الكاملة كحلول تكرارية في السبعينيات، ووسع تطوير GMRES بواسطة سعد وشولتز في عام 1986 وتطوير الطرق المتعامدة الثنائية المستقرة النهج ليشمل الأنظمة العامة غير المتماثلة.

Key figures

• Magnus Hestenes
• Eduard Stiefel
• Cornelius Lanczos
• Yousef Saad
• Henk van der Vorst

Seminal works

• saad2003
• greenbaum1997

Frequently asked questions

لماذا تعمل طريقة التدرج المترافق فقط مع المصفوفات المتماثلة الموجبة المحددة؟

يعتمد تكرارها القصير والفعال وأمثليتها في معيار الطاقة على كون المصفوفة متماثلة موجبة محددة. بالنسبة للمصفوفات المتماثلة غير المحددة أو غير المتماثلة، تتطلب طرق مختلفة مثل MINRES أو GMRES، وعادةً ما تتطلب مساحة تخزين أو عملًا أكبر لكل خطوة.

لماذا تحتاج GMRES إلى الكثير من الذاكرة؟

بالنسبة للمصفوفة العامة غير المتماثلة، لا يوجد تكرار قصير يحافظ على تعامد أساس كريلوف، لذلك يجب على GMRES تخزين كل متجه أساس لتقليل الباقي. تحد GMRES المعاد تشغيلها من الذاكرة عن طريق التخلص الدوري من الأساس، على حساب تقارب أبطأ.