Derivation of the conjugate gradient method
संख्यात्मक रैखिक बीजगणित में, संयुग्म प्रवणता विधि रैखिक प्रणाली को संख्यात्मक रूप से हल करने के लिए एक पुनरावृत्ति विधि है जहां सममित सकारात्मक-निश्चित है। संयुग्म प्रवणता विधि को कई अलग-अलग दृष्टिकोणों से प्राप्त किया जा सकता है, जिसमें अनुकूलन के लिए संयुग्म दिशा विधि का विशेषज्ञता और आइगेनवैल्यू समस्याओं के लिए अर्नोल्डी/लैंक्ज़ोस पुनरावृत्ति की भिन्नता शामिल है। इस लेख का उद्देश्य इन व्युत्पत्तियों में महत्वपूर्ण चरणों का दस्तावेजीकरण करना है। संयुग्म दिशा विधि से व्युत्पत्ति संयुग्म प्रवणता विधि को द्विघात फलन को न्यूनतम करने के लिए लागू संयुग्म दिशा विधि के एक विशेष मामले के रूप में देखा जा सकता है संयुग्म दिशा विधि संयुग्म दिशा विधि को न्यूनतम करने के लिए संयुग्म दिशा विधि एक प्रारंभिक अनुमान और संबंधित अवशिष्ट के साथ शुरू होती है, और सूत्र द्वारा पुनरावृत्ति और अवशिष्ट की गणना करती है जहां पारस्परिक रूप से संयुग्म दिशाओं की एक श्रृंखला होती है, यानी किसी के लिए भी। संयुग्म दिशा विधि इस अर्थ में अस्पष्ट है कि दिशाओं के चयन के लिए कोई सूत्र नहीं दिए गए हैं। विशिष्ट विकल्प संयुग्म प्रवणता विधि और गौसी उन्मूलन सहित विभिन्न विधियों की ओर ले जाते हैं। अर्नोल्डी/लैंक्ज़ोस पुनरावृत्ति से व्युत्पत्ति संयुग्म प्रवणता विधि को रैखिक प्रणालियों को हल करने के लिए लागू अर्नोल्डी/लैंक्ज़ोस पुनरावृत्ति के एक प्रकार के रूप में भी देखा जा सकता है। सामान्य अर्नोल्डी विधि अर्नोल्डी पुनरावृत्ति में, एक वेक्टर के साथ शुरू होता है और धीरे-धीरे क्रायलोव उपक्षेत्र का एक ऑर्थोनॉर्मल आधार बनाता है, यह परिभाषित करके कि दूसरे शब्दों में, ग्राम-श्मिट द्वारा सामान्यीकरण के खिलाफ ऑर्थोगोनलाइज़िंग के लिए पाया जाता है। मैट्रिक्स के रूप में रखें, पुनरावृत्ति को समीकरण द्वारा पकड़ा जाता है जहां के साथ रैखिक प्रणालियों को हल करने के लिए अर्नोल्डी पुनरावृत्ति को लागू करते समय, एक प्रारंभिक अनुमान के अनुरूप अवशिष्ट के साथ शुरू होता है। पुनरावृत्ति के प्रत्येक चरण के बाद, एक गणना और नया पुनरावृत्ति होता है। प्रत्यक्ष लैंक्ज़ोस विधि शेष चर्चा के लिए, हम मानते हैं कि यह सममित सकारात्मक-निश्चित है। की समरूपता के साथ, ऊपरी हेसेनबर्ग मैट्रिक्स सममित हो जाता है और इस प्रकार त्रिकोणीय हो जाता है। इसके बाद इसे अधिक स्पष्ट रूप से दर्शाया जा सकता है यह पुनरावृत्ति के लिए एक छोटी तीन-अवधि की पुनरावृत्ति को सक्षम बनाता है, और अर्नोल्डी पुनरावृत्ति को लैंक्ज़ोस पुनरावृत्ति तक कम कर दिया जाता है। चूँकि यह सममित धनात्मक-निश्चित है, इसलिए है। इसलिए, और के लिए सुविधाजनक पुनरावृत्तियों के साथ आंशिक धुरी के बिना एल. यू. को फैक्टराइज किया जा सकता हैः अब यह देखना महत्वपूर्ण है कि वास्तव में, और के लिए भी छोटी पुनरावृत्तियां हैंः इस सूत्रीकरण के साथ, हम एक सरल पुनरावृत्ति पर पहुंचते हैंः उपरोक्त संबंध सीधे सीधे लैंकोस विधि की ओर ले जाते हैं, जो थोड़ा अधिक जटिल हो जाता है। यदि हम स्थिर कारक में स्केलिंग को मापने और क्षतिपूर्ति करने की अनुमति देते हैं, तो हम संभावित रूप से रूप की सरल पुनरावृत्ति कर सकते हैंः सरलीकरण के लिए परिसर के रूप में, अब हम की ऑर्थोगोनलिटी और संयुग्मता प्राप्त करते हैं, यानी, के लिए, अवशिष्ट पारस्परिक रूप से ऑर्थोगोनल हैं क्योंकि अनिवार्य रूप से के लिए एक गुणक है, क्योंकि, संयुग्मता को देखने के लिए, यह दिखाने के लिए पर्याप्त है कि विकर्ण हैः सममित और निम्न त्रिकोणीय है और इस प्रकार विकर्ण होना चाहिए। अब हम स्थिर कारकों को प्राप्त कर सकते हैं और केवल की ऑर्थोगोनलिटी और संयुग्मता को लागू करके स्केल किए गए के संबंध में। की ऑर्थोगोनलिटी के कारण, यह आवश्यक है कि। नतीजतन, इसी तरह, संयुग्मता के कारण, यह आवश्यक है कि। नतीजतन, यह व्युत्पत्ति को पूरा करता है। संदर्भ संख्यात्मक रैखिक बीजगणित अनुकूलन एल्गोरिदम और विधियाँ प्रवणता विधियाँ प्रमाण वाले लेख