रैखिक प्रणालियों के लिए प्रत्यक्ष विधियाँ

प्रत्यक्ष विधियाँ एक रैखिक प्रणाली Ax = b को परिमित संख्या में अंकगणितीय चरणों में हल करती हैं, आमतौर पर मैट्रिक्स का गुणनखंडन करके और फिर प्रतिस्थापन द्वारा त्रिकोणीय प्रणालियों को हल करके।

Definition

एक प्रत्यक्ष विधि एक एल्गोरिथम है जो एक रैखिक प्रणाली का सटीक समाधान — गोलाई त्रुटि तक — संचालन की एक पूर्व निर्धारित परिमित संख्या में गणना करती है, इसके विपरीत एक पुनरावृत्त विधि जो अनुमानों का एक क्रम उत्पन्न करती है।

Scope

यह विषय गाऊसी विलोपन, LU गुणनखंडन के रूप में इसकी अभिव्यक्ति, त्रुटि वृद्धि को नियंत्रित करने में पिवोटिंग की भूमिका, त्रिकोणीय प्रणालियों के लिए फॉरवर्ड और बैक प्रतिस्थापन, और ऑपरेशन गणनाओं को शामिल करता है जो प्रत्यक्ष सॉल्वर को सघन और बैंडेड मैट्रिक्स के लिए व्यावहारिक बनाते हैं।

Core questions

• गाऊसी विलोपन एक प्रणाली को त्रिकोणीय रूप में कैसे कम करता है, और यह LU गुणनखंडन के समतुल्य क्यों है?
• पिवोटिंग क्यों आवश्यक है, और आंशिक और पूर्ण पिवोटिंग गोलाई त्रुटि की वृद्धि को कैसे नियंत्रित करते हैं?
• प्रत्यक्ष हल की कम्प्यूटेशनल लागत क्या है, और संरचना (समरूपता, बैंडेडनेस, विरलता) का लाभ उठाकर इसे कैसे कम किया जाता है?
• किन परिस्थितियों में आंशिक पिवोटिंग के साथ गाऊसी विलोपन व्यवहार में पश्चगामी स्थिर होता है?

Key theories

आंशिक पिवोटिंग के साथ LU गुणनखंडन

पंक्ति अंतर्विनिमय के साथ गाऊसी विलोपन एक मैट्रिक्स को PA = LU के रूप में गुणनखंडित करता है जिसमें L इकाई निम्न-त्रिकोणीय और U ऊपरी-त्रिकोणीय होता है; आंशिक पिवोटिंग गुणकों को सीमित करती है और व्यवहार में सामना किए गए लगभग सभी मैट्रिक्स के लिए विधि को विश्वसनीय बनाती है।

वृद्धि कारक और पश्चगामी स्थिरता

गाऊसी विलोपन की पश्चगामी त्रुटि विलोपन के दौरान प्रविष्टियों के वृद्धि कारक द्वारा नियंत्रित होती है; यद्यपि कृत्रिम मामलों में घातीय वृद्धि संभव है, आंशिक पिवोटिंग वृद्धि को इतना छोटा रखती है कि विधि वस्तुतः सभी वास्तविक समस्याओं के लिए पश्चगामी स्थिर होती है।

Mechanisms

गाऊसी विलोपन कॉलम दर कॉलम आगे बढ़ता है: प्रत्येक चरण में एक पिवट का चयन किया जाता है (आंशिक पिवोटिंग वर्तमान कॉलम में सबसे बड़े परिमाण वाले उम्मीदवार का चयन करती है), पिवट पंक्ति के गुणकों को नीचे की पंक्तियों से शून्य लाने के लिए घटाया जाता है, और गुणकों को L बनाने के लिए संग्रहीत किया जाता है। परिणामी ऊपरी-त्रिकोणीय U को बैक प्रतिस्थापन द्वारा हल किया जाता है और दाहिने हाथ की ओर को फॉरवर्ड प्रतिस्थापन द्वारा संसाधित किया जाता है। एक n-गुणा-n सघन मैट्रिक्स के लिए गुणनखंडन में लगभग दो-तिहाई n-क्यूब संचालन लगते हैं, जबकि प्रत्येक त्रिकोणीय हल में n-वर्ग क्रम का खर्च आता है।

Clinical relevance

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

History

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

Key figures

• Carl Friedrich Gauss
• James H. Wilkinson
• Nicholas J. Higham

Seminal works

• trefethen1997
• golub2013
• higham2002

Frequently asked questions

पुनरावृत्त विधि की तुलना में प्रत्यक्ष विधि को कब प्राथमिकता दी जानी चाहिए?

प्रत्यक्ष विधियों को तब प्राथमिकता दी जाती है जब मैट्रिक्स सघन या मध्यम आकार का हो, जब कई दाहिने हाथ की ओर एक मैट्रिक्स साझा करते हों (ताकि एक एकल गुणनखंडन का पुन: उपयोग किया जा सके), या जब एक गारंटीकृत परिमित, पूर्ण-सटीकता समाधान की आवश्यकता हो। बहुत बड़ी विरल प्रणालियाँ आमतौर पर पुनरावृत्त विधियों को पसंद करती हैं।

क्या पिवोटिंग हमेशा एक छोटी त्रुटि की गारंटी देता है?

आंशिक पिवोटिंग व्यवहार में लगभग सभी मैट्रिक्स के लिए पश्चगामी स्थिरता की गारंटी देता है, लेकिन यह खराब-कंडीशनिंग को दूर नहीं करता है: यदि मैट्रिक्स स्वयं लगभग विलक्षण है, तो एक पश्चगामी-स्थिर हल भी बड़ी फॉरवर्ड त्रुटि के साथ एक समाधान लौटा सकता है।