संयुग्म प्रवणता विधि
गणित में, संयुग्मी ढाल विधि रैखिक समीकरणों की विशेष प्रणाली के संख्यात्मक व्याख्या के लिए कलन विधि है, जिसका मैट्रिक्स सकारात्मक-निश्चित मैट्रिक्स है। संयुग्मी ढाल पद्धति को अधिकांशतः पुनरावृत्त विधि के रूप में प्रयुक्त किया जाता है, जो विरल मैट्रिक्स प्रणाली पर प्रयुक्त होता है जो प्रत्यक्ष कार्यान्वयन या अन्य प्रत्यक्ष प्रणाली जैसे चोल्स्की अपघटन द्वारा नियंत्रित किया जा सकता है। आंशिक अंतर समीकरणों या अनुकूलन स्थितियों को संख्यात्मक रूप से हल करते समय बड़ी विरल प्रणालियां उत्पन्न होती हैं।
संयुग्मी ढाल विधि का उपयोग ऊर्जा न्यूनीकरण जैसी अप्रतिबंधित गणितीय अनुकूलन स्थितियों को हल करने के लिए भी किया जा सकता है। यह सामान्यतः मैग्नस हेस्टेन्स और एडवर्ड बूट्स को जिम्मेदार प्रबन्धित किया जाता है,[1][2] जिसने इसे Z4 (कंप्यूटर) पर प्रोग्राम किया,[3] और इस पर गहन शोध किया।[4][5]
बीसंयुग्म प्रवणता विधि गैर-सममित आव्यूहों को सामान्यीकरण प्रदान करती है। विभिन्न अरैखिक संयुग्मी प्रवणता विधियाँ अरैखिक अनुकूलन स्थितियों की न्यूनतम खोज करती हैं।
संयुग्म प्रवणता द्वारा संबोधित स्थिति का विवरण
मान लीजिए हम रैखिक समीकरणों की प्रणाली को हल करना चाहते हैं।
,सदिश के लिए जहां आव्यूह जाना जाता है जंहा सममित मैट्रिक्स (अर्थात, AT = A), धनात्मक-निश्चित मैट्रिक्स है। धनात्मक-श्चित (अर्थात xTAx > 0 सभी शून्येतर सदिशों के लिए n r में), और वास्तविक संख्या, और भी जाना जाता है। हम इस प्रणाली में के अद्वितीय व्याख्या को निरूपित करते हैं।
प्रत्यक्ष विधि के रूप में व्युत्पत्ति
संयुग्मी प्रवणता पद्धति को कई भिन्न-भिन्न दृष्टिकोणों से प्राप्त किया जा सकता है, जिसमें अनुकूलन के लिए संयुग्मी दिशा पद्धति की विशेषज्ञता और एइगेन्वलुए स्थितियों के लिए अर्नोल्डी पुनरावृत्ति / एइगेन्लैंवलुएक्ज़ोस पुनरावृत्ति की भिन्नता सम्मलित है। उनके दृष्टिकोणों में अंतर के अतिरिक्त, ये व्युत्पत्ति सामान्य विषय को साझा करते हैं - अवशेषों की ओर्थोगोनलिटी और खोज दिशाओं की संयुग्मता को सिद्ध करते हैं। विधि के प्रसिद्ध संक्षिप्त सूत्रीकरण को विकसित करने के लिए ये दो गुण महत्वपूर्ण हैं।
हम कह सकते हैं कि दो शून्येतर सदिश u और v संयुग्मी हैं (के संबंध में ) यदि
तब से सममित और सकारात्मक-निश्चित है, बाएं हाथ की ओर आंतरिक उत्पाद स्थान को परिभाषित करता है
यदि दो सदिश संयुग्मी हैं और यदि वे इस आंतरिक उत्पाद के संबंध में ओर्थोगोनल हैं तब संयुग्मी होना सममित संबंध है, यदि , से संयुग्मित है तब से संयुग्मित है अर्थात् प्रतीत होता है कि
के संबंध में पारस्परिक रूप से संयुग्मित सदिश है अर्थात। सभी के लिए . का चयन है
तब के लिए आधार (रैखिक बीजगणित) बनाता है , और हम व्याख्या व्यक्त कर सकते हैं का इस आधार पर:
स्थिति को वाम-गुणा करना सदिश के साथ उत्पन्नवार
अतः
यह निम्न विधि देता है।[4] समीकरण को हल करने के लिए Ax = b: का क्रम खोजें संयुग्मित दिशाएँ, और फिर गुणांकों की गणना करता है।
पुनरावृत्त विधि के रूप में
यदि हम संयुग्म सदिश के संरक्षण का चयन करते हैं, तब व्याख्या के लिए उचित सन्निकटन प्राप्त करने के लिए हमें उन सभी की आवश्यकता नहीं होती है अतः, हम संयुग्मी ढाल विधि को पुनरावृत्त विधि के रूप में मान लेते हैं। यह हमें उन प्रणालियों को हल करने की भी अनुमति देता है जहाँ n इतना बड़ा है कि प्रत्यक्ष विधि में बहुत अधिक समय लगेगा।
हम x∗ द्वारा x0 (हम सामान्यता के नुकसान के बिना मान सकते हैं कि x0 = 0, अन्यथा प्रणाली Az = b - Ax0 पर विचार करें अतिरिक्त) के लिए प्रारंभिक अनुमान निरूपित करते हैं। x0 से प्रारंभ होने पर हम व्याख्या की खोज करते हैं और प्रत्येक पुनरावृत्ति में हमें यह व्यक्त करने के लिए मीट्रिक की आवश्यकता होती है कि क्या हम व्याख्या x∗ के समीप हैं (यह हमारे लिए अज्ञात है)। यह मीट्रिक इस तथ्य से आता है कि व्याख्या x∗ निम्नलिखित द्विघात फलन का अद्वितीय न्यूनतमकारक भी है।
अद्वितीय न्यूनतम का अस्तित्व स्पष्ट है क्योंकि इसके दूसरे व्युत्पन्न का हेसियन मैट्रिक्स सममित सकारात्मक-निश्चित है
और यह कि न्यूनतम (उपयोग Df('x')=0) प्रारंभिक स्थिति को इसके प्रथम व्युत्पन्न से हल करता है
यह प्रथम आधार सदिश P0 लेने का प्रस्ताव देता है और 'x0' = 'x0' पर f की प्रवणता का ऋणात्मक होता है जिससे f की प्रवणता समान्तर होती है Ax − b. प्रारंभिक अनुमान x0 से प्रारंभ किया जाता है इसका तात्पर्य है कि हम P0 = B- कुल्हाड़ी लेते हैं जिसके आधार में अन्य सदिश प्रवणता के संयुग्मित होंगे अतः इसका नाम संयुग्म प्रवणता विधि है। ध्यान दें कि 'P'0 एल्गोरिथम (कलन विधि) के इस प्रारंभिक चरण द्वारा प्रदान किया गया अवशिष्ट (संख्यात्मक विश्लेषण) भी है।
अतः rk kवें चरण में अवशिष्ट (संख्यात्मक विश्लेषण) होता है।
जैसा कि ऊपर देखा गया है, की ऋणात्मक प्रवणता है,अतः प्रवणता अवतरण विधि को दिशा rk में स्थानांतरित करने की आवश्यकता होगी चूंकि, हम कह सकते हैं कि निर्देश दूसरे से संयुग्मित होना चाहिए। इसे प्रयुक्त करने के लिए व्यावहारिक विधि यह है कि वर्तमान अवशिष्ट और सभी पिछली खोज दिशाओं से अगली खोज दिशा बनाई जाए। जो संयुग्मन बाधा ऑर्थोनॉर्मल-प्रकार की बाधा है अतः एल्गोरिथम (कलन विधि) को ग्राम-श्मिट प्रक्रिया के उदाहरण के रूप में देखा जाता है। ग्राम-श्मिट ऑर्थोनॉर्मलाइज़ेशन के माध्यम से निम्नलिखित अभिव्यक्ति देता है।
(अभिसरण पर संयुग्मन बाधा के प्रभाव के लिए लेख के शीर्ष पर चित्र देखें)। इस दिशा का पालन करते हुए अगला प्रभावशाली स्थान दिया गया है।
जिसके साथ
जहां अंतिम समानता की परिभाषा होती है।
जिसके लिए अभिव्यक्ति व्युत्पन्न किया जा सकता है यदि कोई xk+1 के लिए अभिव्यक्ति को प्रतिस्थापित करता है तब f और में और इसके संबंध में इसे कार्य करना होता है
परिणामी एल्गोरिथ्म
उपरोक्त एल्गोरिथम (कलन विधि) संयुग्मी प्रवणता विधि की सबसे सरल व्याख्या देता है। जैसा कि कहा जाता है जिससे प्रतीत होता है, कि एल्गोरिदम को सभी पिछली खोज दिशाओं और अवशेष सदिशों के साथ-साथ कई मैट्रिक्स-सदिश गुणाओं के भंडारण की आवश्यकता होती है और इस प्रकार कम्प्यूटेशनल रूप में मूल्यवान हो सकता है। चूँकि, एल्गोरिथम (कलन विधि) के समीप विश्लेषण से पता चलता है और यह ओर्थोगोनल है अर्थात। ,i ≠ j के लिए है। -ऑर्थोगोनल यह , अर्थात। , के लिए . यह माना जा सकता है कि जैसे-जैसे एल्गोरिथम (कलन विधि) आगे बढ़ता है, और ही क्रायलोव उप-क्षेत्र में फैला हुआ है। जंहा मानक आंतरिक उत्पाद के संबंध में ऑर्थोगोनल आधार बनाते हैं, और द्वारा प्रेरित आंतरिक उत्पाद के संबंध में ऑर्थोगोनल आधार बनाते हैं अतः, क्रायलोव उपक्षेत्र पर का प्रक्षेपण माना जा सकता है।
Ax = b को हल करने के लिए एल्गोरिथम (कलन विधि) का विवरण नीचे दिया गया है वास्तविक, सममित, सकारात्मक-निश्चित मैट्रिक्स है। निवेश सदिश अनुमानित प्रारंभिक व्याख्या या 0 हो सकता है। यह ऊपर वर्णित त्रुटिहीन प्रक्रिया का अलग सूत्रीकरण है।
यह सबसे अधिक उपयोग किया जाने वाला प्रारूप है। इसके लिए βk सूत्र है जिसमे फ्लेचर-रीव्स अरेखीय संयुग्म प्रवणता विधि में भी प्रयोग किया जाता है।
पुनरारंभ
हमने यह ज्ञात किया कि प्रवणता के अलग रेखा के व्याख्या प्रणाली विधि द्वारा गणना की जाती है स्थिर करने के लिए इसी तरह बना देगा। प्रवणता के अलग रेखा के व्याख्या प्रणाली विधि द्वारा गणना की गई अर्थात, संयुग्म ढाल पुनरावृत्तियों के पुनरारंभ के सरल कार्यान्वयन के रूप में उपयोग किया जा सकता है।[4] पुनर्प्रारंभ अभिसरण को धीमा कर सकता है, लेकिन स्थिरता में सुधार कर सकता है यदि संयुग्मी प्रवणता विधि गलत व्यवहार करती है, उदाहरण के लिए, पूर्णांक करने की त्रुटि का कारण इत्यादि।
स्पष्ट अवशिष्ट गणना
सूत्र और , जो दोनों त्रुटिहीन अंकगणित में धारण करते हैं और यह सूत्र बनाते हैं और गणितीय समकक्ष पूर्व का उपयोग एल्गोरिथम (कलन विधि) में अतिरिक्त गुणन से बचने के लिए किया जाता है सदिश के पश्चात् से मूल्यांकन के लिए पहले से ही गणना की गई है . उत्तरार्द्ध अधिक त्रुटिहीन हो सकता है, जो स्पष्ट गणना को प्रतिस्थापित कर सकता है निहित के लिए पुनरावर्ती त्रुटि संचय के अधीन है और इस प्रकार सामयिक मूल्यांकन के लिए अनुशंसित है।[6]
अवशिष्ट का मानदंड सामान्यतः मानदंडों को रोकने के लिए उपयोग किया जाता है। स्पष्ट अवशिष्ट का मानदंड त्रुटिहीन अंकगणित और राउंडिंग त्रुटियों की उपस्थिति में त्रुटिहीनता का गारंटीकृत स्तर प्रदान करता है, जहां अभिसरण स्वाभाविक रूप से स्थिर हो जाता है। इसके विपरीत, निहित अवशिष्ट गोलाई त्रुटियों के स्तर से अधिक नीचे आयाम में छोटा होता रहता है और इस प्रकार अभिसरण के ठहराव को निर्धारित करने के लिए उपयोग नहीं किया जा सकता है।
अल्फा और बीटा की गणना
एल्गोरिथ्म में, αk ऐसा चुना जाता है यह ओर्थोगोनल है . भाजक से सरलीकृत किया गया है।
तब से . βk }} ऐसा चुना जाता है कि से संयुग्मित है . प्रारंभ में, βk है।
का उपयोग करते हुए
और समान रूप से
का अंश βk के रूप में पुनः लिखा जाता है।
क्योंकि और डिजाइन द्वारा ओर्थोगोनल हैं। भाजक को फिर से लिखा जाता है।
इसका उपयोग करते हुए खोज दिशाएँ pk संयुग्मित हैं और फिर से अवशिष्ट ऑर्थोगोनल हैं। यहβ देता है और एल्गोरिथ्म αk. में रद्द करने के पश्चात् कार्य करता है।
== MATLAB / GNU ऑक्टेव में उदाहरण कोड
<वाक्यविन्यास प्रकाश लैंग = matlab>
कार्य एक्स = कंजग्रेड (ए, बी, एक्स)
आर = बी - ए * एक्स; पी = आर; आरसोल्ड = आर' * आर;
मैं = 1 के लिए: लंबाई (बी) एपी = ए * पी; अल्फा = रसोल्ड / (पी '* एपी); एक्स = एक्स + अल्फा * पी; आर = आर - अल्फा * एपी; आरएसन्यू = आर' * आर; यदि sqrt(rsnew) <1e-10 तोड़ना अंत पी = आर + (rsnew / rsold) * पी; rsold = rsnew; अंत
अंत
</वाक्यविन्यास हाइलाइट>
संख्यात्मक उदाहरण
द्वारा दी गई रैखिक प्रणाली Ax = b पर विचार करें।
हम प्रारंभिक अनुमान से शुरुआत करते हुए संयुग्मी ढाल विधि के दो चरण करेंगे।
प्रणाली के लिए अनुमानित व्याख्या खोजने के लिए।
उपाय
संदर्भ के लिए, त्रुटिहीन व्याख्या है।
हमारा पहला कदम अवशिष्ट सदिश r0 की गणना करता है जो x0 से जुड़ा हुआ है इस अवशिष्ट की गणना सूत्र r से की जाती है r0 = b- कुल्हाड़ी0, और हमारे स्थितियों में k समान्तर होता है।
चूंकि यह प्रथम पुनरावृत्ति है, हम अवशिष्ट सदिश r0 का उपयोग करेंगे हमारी प्रारंभिक खोज दिशा p0 के रूप में pk चुनने की विधि में आगे के पुनरावृत्तियों में परिवर्तित हो जाएगा।
अब हम स्केलर की गणना करते हैं α0 संबंध का उपयोग करना
अब हम x1 की गणना कर सकते हैं, सूत्र का उपयोग करना
यह परिणाम प्रथम पुनरावृत्ति को पूरा करता है, परिणाम प्रणाली के लिए बेहतर अनुमानित व्याख्या है, x1 अब हम आगे बढ़ सकते हैं और अगले अवशिष्ट सदिश r1 की गणना कर सकते हैं सूत्र का उपयोग करना
इस प्रक्रिया में हमारा अगला कदम स्केलर की गणना करना है β0 जिसका उपयोग अंततः अगली खोज दिशा p1 निर्धारित करने के लिए किया जाएगा।
अब इस अदिश β0 का उपयोग करते हुए हम अगली खोज दिशा p1 की गणना कर सकते हैं संबंध का उपयोग करना
अब हम स्केलर की गणना करते हैं α1 हमारे नए अधिग्रहीत p1 का उपयोग करने के लिए जिस विधि का उपयोग किया जाता है उसी विधि का α0. में उपयोग करना
अंत में, हम x2 पाते हैं x1 को खोजने के लिए उपयोग की जाने वाली विधि का उपयोग करना
परिणामस्वरूप, x2, x1 की तुलना में प्रणाली के व्याख्या का बेहतर सन्निकटन है और x0 यदि इस उदाहरण में सीमित-परिशुद्धता के अतिरिक्त त्रुटिहीन अंकगणित का उपयोग किया जाना था, तो सैद्धांतिक रूप से त्रुटिहीन व्याख्या n = 2 पुनरावृत्तियों (n प्रणाली का क्रम होने के नाते) के पश्चात् पहुंचा होगा।
अभिसरण गुण
संयुग्मी ढाल विधि को सैद्धांतिक रूप से प्रत्यक्ष विधि के रूप में देखा जा सकता है, जिससे कि गोल-बंद त्रुटि के अभाव में यह पुनरावृत्तियों की सीमित संख्या के पश्चात् त्रुटिहीन व्याख्या उत्पन्न करता है, जो मैट्रिक्स के आकार से बड़ा नहीं है। व्यावहारिक रूप से, त्रुटिहीन व्याख्या कभी प्राप्त नहीं होता है क्योंकि संयुग्मी ढाल विधि छोटी अस्तव्यस्तता के संबंध में भी अस्थिर है, उदाहरण के लिए, क्रायलोव उप-स्थानों को उत्पन्न करने की अपक्षयी प्रकृति के कारण, अधिकांश दिशाएं संयुग्मित व्यवहार में नहीं हैं।
पुनरावृत्त विधि के रूप में, संयुग्मी ढाल विधि नीरस रूप से (ऊर्जा मानक में) सन्निकटन में सुधार करती है त्रुटिहीन व्याख्या के लिए और पुनरावृत्तियों की अपेक्षाकृत छोटी (स्थिति के आकार की तुलना में) संख्या के पश्चात् आवश्यक सहिष्णुता तक पहुंच सकता है। सुधार सामान्यतः रैखिक होता है और इसकी गति स्थिति संख्या द्वारा निर्धारित की जाती है प्रणाली मैट्रिक्स का : बड़ा है, सुधार जितना धीमा होगा।[7]
यदि बड़ा है, मूल प्रणाली को बदलने के लिए सामान्यतः पूर्व शर्त का उपयोग किया जाता है साथ ऐसा कहा जाता है कि की तुलना में छोटा है , नीचे देखें।
अभिसरण प्रमेय
बहुपदों के उपसमुच्चय को इस रूप में परिभाषित कीजिए।
कहाँ अधिकतम डिग्री के बहुपद वलय का समुच्चय है।
होने देना त्रुटिहीन व्याख्या , के पुनरावृत्त सन्निकटन हो और त्रुटियों को परिभाषित करें .
अब, अभिसरण की दर का अनुमान लगाया जा सकता है [4][8]
जंहा मैट्रिक्स के वर्णक्रम को दर्शाता है और स्थिति संख्या को दर्शाता है।
ध्यान दें, महत्वपूर्ण सीमा जब शिष्टाचार है
यह सीमा जैकोबी पद्धति या गॉस-सीडेल विधि की पुनरावृत्ति विधियों की तुलना में तेज अभिसरण दर दिखाती है। .
अभिसरण प्रमेय में कोई गोल-बंद त्रुटि नहीं मानी जाती है, लेकिन अभिसरण सीमा सामान्यतः व्यवहार में मान्य होती है जैसा कि सैद्धांतिक रूप से ऐनी ग्रीनबाउम द्वारा समझाया गया है।[5]
व्यावहारिक अभिसरण
यदि बेहतरीन रूप से आरंभ किया जाता है, तो पुनरावृत्तियों का पहला चरण अधिकांशतः सबसे तेज़ होता है, क्योंकि क्रायलोव उप-स्थान ,में आंतरिक त्रुटि समाप्त हो जाती है जो प्रारंभ में छोटी प्रभावी स्थिति संख्या को दर्शाती है। अभिसरण का दूसरा चरण सामान्यतः सैद्धांतिक अभिसरण द्वारा उचित प्रकार से परिभाषित होता है लेकिन मैट्रिक्स के स्पेक्ट्रम के वितरण के आधार पर सुपर-रैखिक हो सकता है और त्रुटि का वर्णक्रमीय वितरण होता है।[5]अंतिम चरण में, सबसे छोटी प्राप्त त्रुटिहीनता तक पहुँच जाती है और अभिसरण रुक जाता है या विधि विचलन भी प्रारंभ कर सकती है। बड़े आकार के मैट्रिसेस के लिए दुगनी-परिशुद्धता तैरनेवाला स्थल प्रारूप में विशिष्ट वैज्ञानिक कंप्यूटिंग अनुप्रयोगों में, संयुग्म ढाल विधि सहिष्णुता के साथ रोक मानदंड का उपयोग करती है जो पहले या दूसरे चरण के दौरान पुनरावृत्तियों को समाप्त करती है।
पूर्वानुकूल संयुग्म प्रवणता विधि
ज्यादातर स्थितियों में, संयुग्म विचलन विधि के तेजी से अभिसरण सुनिश्चित करने के लिए पूर्व शर्त आवश्यक है। यदि सममित सकारात्मक-निश्चित है और से बेहतर स्थिति संख्या है , पूर्वानुकूलित संयुग्मी प्रवणता विधि का उपयोग किया जा सकता है। यह निम्न रूप लेता है।[9]
- दोहराना
- यदि आरk+1 पर्याप्त रूप से छोटा है तो बाहर निकलें लूप अंत यदि
- अंत दोहराएँ
- परिणाम xk+1 है।
उपरोक्त सूत्रीकरण नियमित संयुग्मी ढाल विधि को पूर्वानुकूलित प्रणाली में प्रयुक्त करने के बराबर है।[10]
कहाँ
प्रणाली की समरूपता (और सकारात्मक निश्चितता) को बनाए रखने के लिए पूर्व शर्तो के चोल्स्की अपघटन का उपयोग किया जाना चाहिए। चूँकि, इस अपघटन की गणना करने की आवश्यकता नहीं है और यह जानने के लिए पर्याप्त है यह दिखाया जा सकता है के समान स्पेक्ट्रम है
पूर्व शर्त मैट्रिक्स M को सममित सकारात्मक-निश्चित और निश्चित होना चाहिए, अर्थात पुनरावृत्ति से पुनरावृत्ति में परिवर्तित नही कर सकता है।
यदि पूर्वानुकूलन पर इनमें से किसी भी धारणा का उल्लंघन किया जाता है, तो पूर्वानुकूलित संयुग्मी प्रवणता पद्धति का व्यवहार अप्रत्याशित हो सकता है।
सामान्यतः उपयोग किए जाने वाले पूर्व शर्तो का उदाहरण अपूर्ण चोल्स्की गुणनखंडन है।[11]
लचीला पूर्व शर्त संयुग्म ढाल विधि
संख्यात्मक रूप से चुनौतीपूर्ण अनुप्रयोगों में, परिष्कृत पूर्व शर्तो का उपयोग किया जाता है, जिससे पुनरावृत्तियों के मध्य परिवर्तनशील पूर्वानुकूलन हो सकता है। यहां तक कि यदि पूर्व शर्त प्रत्येक पुनरावृत्ति पर सममित सकारात्मक-निश्चित है, तो तथ्य यह है कि यह परवर्तित हो सकता है जो तर्कों को अमान्य बना देता है, और व्यावहारिक परीक्षणों में ऊपर प्रस्तुत एल्गोरिदम के अभिसरण की महत्वपूर्ण धीमी गति की ओर जाता है। अरैखिक संयुग्मी प्रवणता पद्धति का उपयोग करना पोलक-रिबिएर सूत्र द्वारा
अरैखिक संयुग्मी प्रवणता पद्धति के अतिरिक्त | फ्लेचर-रीव्स सूत्र
इस स्थितियों में नाटकीय रूप से अभिसरण में सुधार कर सकते हैं।[12] पूर्वानुकूल संयुग्म प्रवणता विधि के इस संस्करण को लचीला कहा जा सकता है[13] जिससे कि यह परिवर्तनीय पूर्व शर्त के लिए अनुमति देता है।
लचीला संस्करण भी दिखाया गया है[14] मजबूत होने के लिए यदि पूर्व शर्त सममित सकारात्मक निश्चित (एसपीडी) न हो।
लचीले संस्करण के कार्यान्वयन के लिए अतिरिक्त सदिश के भंडारण की आवश्यकता होती है। निश्चित एसपीडी पूर्व शर्त के लिए, अतः दोनों सूत्र βk त्रुटिहीन अंकगणित में समतुल्य हैं, अर्थात राउंड-ऑफ त्रुटि के बिना।
गैर-रैखिक संयुग्म प्रवणता विधि के साथ विधि के बेहतर अभिसरण व्यवहार की गणितीय व्याख्या होती है। पोलक-रिबिएर सूत्र यह है कि इस स्थितियों में विधि स्थानीय रूप से प्रभावशाली है, विशेष रूप से, यह स्थानीय रूप से प्रभावशाली तीव्र पृथक विधि की तुलना में धीमी अभिसरण नहीं करती है।[15]
बनाम। स्थानीय रूप से प्रभावशाली तीव्र पृथक विधि
मूल और पूर्वानुकूल संयुग्म प्रवणता दोनों विधियों में केवल चयन करने की आवश्यकता होती है रेखा खोज, तेज वंश विधियों का उपयोग करके उन्हें स्थानीय रूप से प्रभावशाली बनाने के लिए। इस प्रतिस्थापन के साथ, vectors p हमेशा सदिश z के समान होते हैं अतः सदिश p को स्टोर करने की कोई आवश्यकता नहीं है इस प्रकार, संयुग्मित ढाल विधियों की तुलना में इन सबसे तेज वर्ग विधियों का प्रत्येक पुनरावृत्ति थोड़ा सस्ता है। चूंकि, पश्चात् वाला तेजी से अभिसरण करता है, जब तक कि (अत्यधिक) चर और/या गैर-एसपीडी पूर्व शर्त का उपयोग नहीं किया जाता है, ऊपर देखें।
== डबल इंटीग्रेटर == के लिए प्रभावशाली प्रतिक्रिया नियंत्रक के रूप में संयुग्मित ढाल विधि
प्रभावशाली नियंत्रण का उपयोग करके संयुग्म ढाल विधि भी प्राप्त की जा सकती है।[16] इस दृष्टिकोण में, संयुग्मी ढाल विधि प्रतिक्रिया नियंत्रण के रूप में बाहर हो जाती है,
सामान्य समीकरण पर संयुग्म ढाल
संयुग्मी ढाल विधि को सामान्य समीकरणों 'A' पर प्रयुक्त करके मनमाने ढंग से एन-बाय-एम मैट्रिक्स पर प्रयुक्त किया जा सकता है। ATऔर दाईं ओर सदिश ATb, चूंकि ATA किसी भी A के लिए सममित सकारात्मक-निश्चित मैट्रिक्स नकारात्मक निश्चित.2C अर्ध-निश्चित और अनिश्चित मैट्रिक्स सकारात्मक अर्ध-परिमित मैट्रिक्स है। परिणाम सामान्य समीकरणों (CGNR) पर संयुग्मित ढाल है।
- ATकुल्हाड़ी = AT
पुनरावृत्त विधि के रूप में, AT बनाना आवश्यक नहीं है A स्मृति में स्पष्ट रूप से लेकिन केवल मैट्रिक्स-सदिश को निष्पादित करने और मैट्रिक्स-सदिश गुणन को स्थानांतरित करने के लिए किया जाता है। अतः, CGNR विशेष रूप से उपयोगी होता है जब 'A' विरल मैट्रिक्स होता है जिससे कि ये ऑपरेशन सामान्यतः अधिक कुशल होते हैं। चूँकि सामान्य समीकरण बनाने का नकारात्मक पक्ष यह है कि स्थिति संख्या κ(ATA) κ के बराबर (ए)2 है और अतः CGNR के अभिसरण की दर धीमी हो सकती है और अनुमानित व्याख्या की गुणवत्ता राउंड ऑफ त्रुटियों के प्रति संवेदनशील हो सकती है। अच्छा पूर्व-कंडीशनर ढूँढना अधिकांशतः CGNR पद्धति का उपयोग करने का महत्वपूर्ण ]भाग होता है।
कई एल्गोरिदम प्रस्तावित किए गए हैं (उदाहरण के लिए, सीजीएलएस, एलएसक्यूआर इत्यदि)। LSQR एल्गोरिथम (कलन विधि) कथित तौर पर सर्वश्रेष्ठ संख्यात्मक स्थिरता रखता है जब A बीमार होता है, अर्थात, A के समीप बड़ी स्थिति संख्या होती है।
जटिल हर्मिटियन मेट्रिसेस के लिए संयुग्मी प्रवणता विधि
जटिल-मूल्यवान मैट्रिक्स A और सदिश B, रैखिक समीकरणों की प्रणाली को देखते हुए, तुच्छ संशोधन के साथ संयुग्म ढाल विधि को हल करने के लिए विस्तार योग्य है कॉम्प्लेक्स-वैल्यू सदिश x के लिए, जहां A हर्मिटियन है (अर्थात, A' = A) और सकारात्मक-निश्चित मैट्रिक्स, और प्रतीक ' MATLAB/GNU ऑक्टेव शैली का उपयोग करके संयुग्मित संक्रमण को दर्शाता है। तुच्छ संशोधन हर जगह वास्तविक स्थानान्तरण के लिए बस संयुग्म स्थानान्तरण को प्रतिस्थापित कर रहा है। यह प्रतिस्थापन पिछड़ा संगत है, जिस कारण संयुग्मित स्थानान्तरण वास्तविक-मूल्यवान सदिशों और आव्यूहों पर वास्तविक स्थानान्तरण में परिवर्तित हो जाता है। ऊपर दिए गए संयुग्म प्रवणता विधि उदाहरण कोड MATLAB / GNU ऑक्टेव में उदाहरण कोड इस प्रकार पहले से ही जटिल हर्मिटियन मैट्रिसेस के लिए कार्य करता है, जिसमें किसी संशोधन की आवश्यकता नहीं है।
यह भी देखें
- उभयलिंगी ढाल विधि (बीआईसीजी)
- अवशिष्ट विधि
- विश्वास प्रचार गाऊसी विश्वास प्रचार .28GaBP.29
- सिस्टम के पास पुनरावृत्त विधि | पुनरावर्ती विधि:निर्जीव प्रणाली
- क्रायलोव उपक्षेत्र
- गैर रेखीय संयुग्म ढाल विधि
- पूर्व शर्त
- विरल मैट्रिक्स-सदिश गुणन
संदर्भ
- ↑ Hestenes, Magnus R.; Stiefel, Eduard (December 1952). "Methods of Conjugate Gradients for Solving Linear Systems" (PDF). Journal of Research of the National Bureau of Standards. 49 (6): 409. doi:10.6028/jres.049.044.
- ↑ Straeter, T. A. (1971). "On the Extension of the Davidon–Broyden Class of Rank One, Quasi-Newton Minimization Methods to an Infinite Dimensional Hilbert Space with Applications to Optimal Control Problems". NASA Technical Reports Server. NASA. hdl:2060/19710026200.
- ↑ Speiser, Ambros (2004). "Konrad Zuse und die ERMETH: Ein weltweiter Architektur-Vergleich" [Konrad Zuse and the ERMETH: A worldwide comparison of architectures]. In Hellige, Hans Dieter (ed.). Geschichten der Informatik. Visionen, Paradigmen, Leitmotive (in Deutsch). Berlin: Springer. p. 185. ISBN 3-540-00217-0.
- ↑ 4.0 4.1 4.2 4.3 Polyak, Boris (1987). Introduction to Optimization (in English).
- ↑ 5.0 5.1 5.2 Greenbaum, Anne (1997). Iterative Methods for Solving Linear Systems (in English). doi:10.1137/1.9781611970937. ISBN 978-0898713961.
- ↑ Shewchuk, Jonathan R (1994). An Introduction to the Conjugate Gradient Method Without the Agonizing Pain (PDF).
- ↑ Saad, Yousef (2003). Iterative methods for sparse linear systems (2nd ed.). Philadelphia, Pa.: Society for Industrial and Applied Mathematics. pp. 195. ISBN 978-0-89871-534-7.
- ↑ Hackbusch, W. (2016-06-21). Iterative solution of large sparse systems of equations (2nd ed.). Switzerland: Springer. ISBN 9783319284835. OCLC 952572240.
- ↑ Barrett, Richard; Berry, Michael; Chan, Tony F.; Demmel, James; Donato, June; Dongarra, Jack; Eijkhout, Victor; Pozo, Roldan; Romine, Charles; van der Vorst, Henk. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (PDF) (in English) (2nd ed.). Philadelphia, PA: SIAM. p. 13. Retrieved 2020-03-31.
- ↑ Golub, Gene H.; Van Loan, Charles F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press. sec. 11.5.2. ISBN 978-1-4214-0794-4.
- ↑ Concus, P.; Golub, G. H.; Meurant, G. (1985). "Block Preconditioning for the Conjugate Gradient Method". SIAM Journal on Scientific and Statistical Computing. 6 (1): 220–252. doi:10.1137/0906018.
- ↑ Golub, Gene H.; Ye, Qiang (1999). "Inexact Preconditioned Conjugate Gradient Method with Inner-Outer Iteration". SIAM Journal on Scientific Computing. 21 (4): 1305. CiteSeerX 10.1.1.56.1755. doi:10.1137/S1064827597323415.
- ↑ Notay, Yvan (2000). "Flexible Conjugate Gradients". SIAM Journal on Scientific Computing. 22 (4): 1444–1460. CiteSeerX 10.1.1.35.7473. doi:10.1137/S1064827599362314.
- ↑ Bouwmeester, Henricus; Dougherty, Andrew; Knyazev, Andrew V. (2015). "Nonsymmetric Preconditioning for Conjugate Gradient and Steepest Descent Methods 1". Procedia Computer Science. 51: 276–285. doi:10.1016/j.procs.2015.05.241. S2CID 51978658.
- ↑ Knyazev, Andrew V.; Lashuk, Ilya (2008). "Steepest Descent and Conjugate Gradient Methods with Variable Preconditioning". SIAM Journal on Matrix Analysis and Applications. 29 (4): 1267. arXiv:math/0605767. doi:10.1137/060675290. S2CID 17614913.
- ↑ 16.0 16.1 Ross, I. M., "An Optimal Control Theory for Accelerated Optimization," arXiv:1902.09004, 2019.
अग्रिम पठन
- Atkinson, Kendell A. (1988). "Section 8.9". An introduction to numerical analysis (2nd ed.). John Wiley and Sons. ISBN 978-0-471-50023-0.
- Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 978-0-486-43227-4.
- Golub, Gene H.; Van Loan, Charles F. (2013). "Chapter 11". Matrix Computations (4th ed.). Johns Hopkins University Press. ISBN 978-1-4214-0794-4.
- Saad, Yousef (2003-04-01). "Chapter 6". Iterative methods for sparse linear systems (2nd ed.). SIAM. ISBN 978-0-89871-534-7.
- Gérard Meurant: "Detection and correction of silent errors in the conjugate gradient algorithm", Numerical Algorithms, vol.92 (2023), pp.869-891. url=https://doi.org/10.1007/s11075-022-01380-1
बाहरी संबंध
- "Conjugate gradients, method of", Encyclopedia of Mathematics, EMS Press, 2001 [1994]