स्थिर और शिथिलन विधियाँ

स्थिर पुनरावृत्तीय विधियाँ मैट्रिक्स को विभाजित करके और एक निश्चित अद्यतन नियम को बार-बार लागू करके एक रैखिक प्रणाली को हल करती हैं; शास्त्रीय जैकोबी, गॉस-सीडेल, और क्रमिक अति-शिथिलन योजनाएँ इसके मूलभूत उदाहरण हैं।

Definition

एक स्थिर पुनरावृत्तीय विधि वह है जिसका अद्यतन प्रत्येक चरण में समान पुनरावृत्ति मैट्रिक्स को लागू करता है, जो गुणांक मैट्रिक्स को एक आसानी से व्युत्क्रमणीय भाग और एक शेष में विभाजित करने से प्राप्त होता है; अभिसरण परिणामी पुनरावृत्ति मैट्रिक्स की स्पेक्ट्रल त्रिज्या द्वारा नियंत्रित होता है।

Scope

यह विषय मैट्रिक्स-विभाजन ढाँचे, जैकोबी और गॉस-सीडेल पुनरावृत्तियों, क्रमिक अति-शिथिलन और इष्टतम शिथिलन पैरामीटर के चुनाव, अभिसरण के लिए स्पेक्ट्रल-त्रिज्या मानदंड, और बहुग्रिड के भीतर स्मूथर के रूप में तथा प्रीकंडीशनर के रूप में इन सरल पुनरावृत्तियों की भूमिका को शामिल करता है।

Core questions

• मैट्रिक्स को विभाजित करने से रैखिक प्रणाली के लिए एक निश्चित-बिंदु पुनरावृत्ति कैसे प्राप्त होती है?
• जैकोबी और गॉस-सीडेल विधियाँ कैसे भिन्न हैं, और गॉस-सीडेल सामान्यतः तेज़ क्यों है?
• अति-शिथिलन अभिसरण को कैसे तेज़ करता है, और इष्टतम पैरामीटर का चुनाव कैसे किया जाता है?
• मैट्रिक्स पर किन शर्तों के तहत ये पुनरावृत्तियाँ अभिसरण करती हैं?

Key theories

मैट्रिक्स विभाजन और स्पेक्ट्रल त्रिज्या मानदंड

मैट्रिक्स को एक आसानी से व्युत्क्रमणीय भाग और एक शेष के रूप में लिखने से एक स्थिर पुनरावृत्ति परिभाषित होती है जिसकी त्रुटि प्रत्येक चरण में एक पुनरावृत्ति मैट्रिक्स द्वारा गुणा की जाती है; पुनरावृत्ति प्रत्येक प्रारंभिक अनुमान के लिए अभिसरण करती है यदि और केवल यदि उस पुनरावृत्ति मैट्रिक्स की स्पेक्ट्रल त्रिज्या एक से कम है।

क्रमिक अति-शिथिलन

एक शिथिलन कारक के साथ गॉस-सीडेल सुधार को ओवरशूट करके, क्रमिक अति-शिथिलन स्पेक्ट्रल त्रिज्या को बहुत कम कर सकता है; कुछ संरचित मैट्रिक्स के लिए एक इष्टतम शिथिलन पैरामीटर विश्लेषणात्मक रूप से ज्ञात होता है और नाटकीय गति-वृद्धि प्रदान करता है।

Mechanisms

जैकोबी विधि पिछले स्वीप के मानों का उपयोग करके प्रत्येक अज्ञात को एक साथ अद्यतन करती है, जो विकर्ण को अलग करने के समतुल्य है। गॉस-सीडेल उसी स्वीप के भीतर सबसे हाल ही में अद्यतन किए गए मानों का उपयोग करती है, निचले-त्रिकोणीय भाग को अलग करती है, जो सामान्यतः तेज़ी से अभिसरण करती है। क्रमिक अति-शिथिलन पुराने मान और गॉस-सीडेल अद्यतन का एक भारित औसत बनाती है जो एक शिथिलन पैरामीटर द्वारा नियंत्रित होता है; इस पैरामीटर को एक से बड़ा चुनने से उपयुक्त मैट्रिक्स के लिए अभिसरण में तेजी आती है। तीनों के लिए अभिसरण कड़ाई से विकर्णतः प्रभावी या सममित धनात्मक-निश्चित मैट्रिक्स जैसे वर्गों के लिए सुनिश्चित है, और इसे पुनरावृत्ति मैट्रिक्स की स्पेक्ट्रल त्रिज्या द्वारा मापा जाता है।

Clinical relevance

यद्यपि बड़े प्रणालियों के लिए प्रतिस्पर्धी स्टैंडअलोन सॉल्वर के रूप में सामान्यतः बहुत धीमी होती हैं, स्थिर विधियाँ बहुग्रिड के केंद्र में स्मूथर के रूप में, क्रायलोव विधियों के लिए सरल प्रीकंडीशनर के रूप में, और आसानी से समानांतर करने योग्य बिल्डिंग ब्लॉक के रूप में महत्वपूर्ण बनी हुई हैं; गॉस-सीडेल और भारित जैकोबी विशेष रूप से आधुनिक मल्टीलेवल सॉल्वर के भीतर सर्वव्यापी हैं।

History

जैकोबी और गॉस-सीडेल पुनरावृत्तियाँ उन्नीसवीं सदी की हैं, जबकि क्रमिक अति-शिथिलन और इसका कठोर अभिसरण सिद्धांत डेविड यंग और रिचर्ड वर्गी द्वारा 1950 के दशक में विकसित किया गया था; यद्यपि बाद में प्राथमिक सॉल्वर के रूप में क्रायलोव और मल्टीग्रिड विधियों द्वारा ग्रहण कर लिया गया, इन पुनरावृत्तियों को मल्टीलेवल और प्रीकंडीशंड योजनाओं के आवश्यक घटकों के रूप में पुनर्जीवित किया गया।

Key figures

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

Seminal works

• saad2003
• varga2000

Frequently asked questions

गॉस-सीडेल जैकोबी से सामान्यतः तेज़ क्यों है?

गॉस-सीडेल उसी स्वीप के भीतर तुरंत अद्यतन मानों का उपयोग करता है, इसलिए जानकारी अज्ञातों के माध्यम से तेज़ी से फैलती है, सामान्यतः जैकोबी की तुलना में पुनरावृत्तियों की संख्या आधी हो जाती है, जो केवल पिछले स्वीप के मानों का उपयोग करता है।

यदि ये विधियाँ धीमी हैं, तो भी इनका अध्ययन क्यों किया जाता है?

वे उत्कृष्ट स्मूथर और सरल प्रीकंडीशनर हैं। मल्टीग्रिड के भीतर, कुछ गॉस-सीडेल या भारित-जैकोबी स्वीप दोलनशील त्रुटि को कुशलता से हटाते हैं, जो मल्टीग्रिड को ठीक वही भूमिका चाहिए, इसलिए ये शास्त्रीय पुनरावृत्तियाँ तेज़ आधुनिक सॉल्वर के घटकों के रूप में जीवित रहती हैं।