संयुग्म प्रवणता विधि

किसी दिए गए रैखिक प्रणाली से जुड़े द्विघात समारोह को कम करने के लिए इष्टतम चरण आकार (हरे रंग में) और संयुग्म वेक्टर (लाल रंग में) के साथ ढाल वंश के अभिसरण की तुलना। संयुग्मी ढाल, त्रुटिहीन अंकगणित मानते हुए, अधिकांश n चरणों में अभिसरण करता है, जहाँ n प्रणाली के मैट्रिक्स का आकार है (यहाँ n = 2)।

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

संयुग्मी ढाल विधि का उपयोग ऊर्जा न्यूनीकरण जैसी अप्रतिबंधित गणितीय अनुकूलन स्थितियों को हल करने के लिए भी किया जा सकता है। यह सामान्यतः मैग्नस हेस्टेन्स और एडवर्ड बूट्स को जिम्मेदार ठहराया जाता है, जिसने इसे Z4 (कंप्यूटर) पर प्रोग्राम किया, और इस पर गहन शोध किया।

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

संयुग्म ग्रेडिएंट्स द्वारा संबोधित समस्या का विवरण

मान लीजिए हम रैखिक समीकरणों की प्रणाली को हल करना चाहते हैं।

$\mathbf {A} \mathbf {x} =\mathbf {b}$

वेक्टर के लिए $\mathbf {x}$, जहां जाना जाता है $n\times n$ आव्यूह $\mathbf {A}$ सममित मैट्रिक्स है (अर्थात, A^T = A), धनात्मक-निश्चित मैट्रिक्स | धनात्मक-निश्चित (अर्थात x^TAx > 0 सभी शून्येतर सदिशों के लिए $\mathbf {x}$ⁿ आर में), और वास्तविक संख्या, और $\mathbf {b}$ भी जाना जाता है। हम इस प्रणाली में $\mathbf {x} _{*}$ के अद्वितीय समाधान को निरूपित करते हैं।

प्रत्यक्ष विधि के रूप में व्युत्पत्ति

Main article: संयुग्मी प्रवणता विधि की व्युत्पत्ति

संयुग्मी प्रवणता पद्धति को कई भिन्न-भिन्न दृष्टिकोणों से प्राप्त किया जा सकता है, जिसमें अनुकूलन के लिए संयुग्मी दिशा पद्धति की विशेषज्ञता और eigenvalue स्थितियों के लिए अर्नोल्डी पुनरावृत्ति / एइगेन्लैंवलुएक्ज़ोस पुनरावृत्ति की भिन्नता सम्मलित है। उनके दृष्टिकोणों में अंतर के बावजूद, ये व्युत्पत्ति सामान्य विषय को साझा करते हैं - अवशेषों की ओर्थोगोनलिटी और खोज दिशाओं की संयुग्मता को सिद्ध करते हैं। विधि के प्रसिद्ध संक्षिप्त सूत्रीकरण को विकसित करने के लिए ये दो गुण महत्वपूर्ण हैं।

हम कह सकते हैं कि दो शून्येतर सदिश u और v संयुग्मी हैं (के संबंध में $\mathbf {A}$) यदि

$\mathbf {u} ^{\mathsf {T}}\mathbf {A} \mathbf {v} =0.$

तब से $\mathbf {A}$ सममित और सकारात्मक-निश्चित है, बाएं हाथ की ओर आंतरिक उत्पाद स्थान को परिभाषित करता है

$\mathbf {u} ^{\mathsf {T}}\mathbf {A} \mathbf {v} =\langle \mathbf {u} ,\mathbf {v} \rangle _{\mathbf {A} }:=\langle \mathbf {A} \mathbf {u} ,\mathbf {v} \rangle =\langle \mathbf {u} ,\mathbf {A} ^{\mathsf {T}}\mathbf {v} \rangle =\langle \mathbf {u} ,\mathbf {A} \mathbf {v} \rangle .$

यदि दो सदिश संयुग्मी हैं और यदि वे इस आंतरिक उत्पाद के संबंध में ओर्थोगोनल हैं। संयुग्मी होना सममित संबंध है, यदि $\mathbf {v}$, $\mathbf {u}$ से संयुग्मित है तब $\mathbf {v}$ से संयुग्मित $\mathbf {u}$ है अर्थात् प्रतीत होता है कि

$P=\{\mathbf {p} _{1},\dots ,\mathbf {p} _{n}\}$

$n$ के संबंध में पारस्परिक रूप से संयुग्मित वैक्टर $\mathbf {A}$ है अर्थात। $\mathbf {p} _{i}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{j}=0$ सभी के लिए $i\neq j$. का सेट है

तब $P$ के लिए आधार (रैखिक बीजगणित) बनाता है $\mathbb {R} ^{n}$, और हम समाधान व्यक्त कर सकते हैं $\mathbf {x} _{*}$ का $\mathbf {Ax} =\mathbf {b}$ इस आधार पर:

$\mathbf {x} _{*}=\sum _{i=1}^{n}\alpha _{i}\mathbf {p} _{i}\Rightarrow \mathbf {A} \mathbf {x} _{*}=\sum _{i=1}^{n}\alpha _{i}\mathbf {A} \mathbf {p} _{i}.$

समस्या को वाम-गुणा करना $\mathbf {Ax} =\mathbf {b}$ वेक्टर के साथ $\mathbf {p} _{k}^{\mathsf {T}}$ उत्पन्नवार

$\mathbf {p} _{k}^{\mathsf {T}}\mathbf {b} =\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {x} _{*}=\sum _{i=1}^{n}\alpha _{i}\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{i}=\sum _{i=1}^{n}\alpha _{i}\left\langle \mathbf {p} _{k},\mathbf {p} _{i}\right\rangle _{\mathbf {A} }=\alpha _{k}\left\langle \mathbf {p} _{k},\mathbf {p} _{k}\right\rangle _{\mathbf {A} }$

अतः

$\alpha _{k}={\frac {\langle \mathbf {p} _{k},\mathbf {b} \rangle }{\langle \mathbf {p} _{k},\mathbf {p} _{k}\rangle _{\mathbf {A} }}}.$

यह निम्न विधि देता है। समीकरण को हल करने के लिए Ax = b: का क्रम खोजें $n$ संयुग्मित दिशाएँ, और फिर $\alpha _{k}$ गुणांकों की गणना करे.

पुनरावृत्त विधि के रूप में

यदि हम संयुग्म वैक्टर $\mathbf {p} _{k}$ सावधानी से चुनते हैं, तब समाधान के लिए उचित सन्निकटन $\mathbf {x} _{*}$ प्राप्त करने के लिए हमें उन सभी की आवश्यकता नहीं हो सकती है अतः, हम संयुग्मी ढाल विधि को पुनरावृत्त विधि के रूप में मानना ​​​​चाहते हैं। यह हमें उन प्रणालियों को हल करने की भी अनुमति देता है जहाँ n इतना बड़ा है कि प्रत्यक्ष विधि में बहुत अधिक समय लगेगा।

हम x_∗ द्वारा x₀ (हम सामान्यता के नुकसान के बिना मान सकते हैं कि x₀ = 0, अन्यथा प्रणाली Az = b - Ax₀ पर विचार करें अतिरिक्त) के लिए प्रारंभिक अनुमान निरूपित करते हैं। x₀ से प्रारंभ होने पर हम समाधान की खोज करते हैं और प्रत्येक पुनरावृत्ति में हमें यह व्यक्त करने के लिए मीट्रिक की आवश्यकता होती है कि क्या हम समाधान x_∗ के समीप हैं (यह हमारे लिए अज्ञात है)। यह मीट्रिक इस तथ्य से आता है कि समाधान x_∗ निम्नलिखित द्विघात फलन का अद्वितीय न्यूनतमकारक भी है।

$f(\mathbf {x} )={\tfrac {1}{2}}\mathbf {x} ^{\mathsf {T}}\mathbf {A} \mathbf {x} -\mathbf {x} ^{\mathsf {T}}\mathbf {b} ,\qquad \mathbf {x} \in \mathbf {R} ^{n}\,.$

अद्वितीय न्यूनतम का अस्तित्व स्पष्ट है क्योंकि इसके दूसरे व्युत्पन्न का हेसियन मैट्रिक्स सममित सकारात्मक-निश्चित है

$\mathbf {H} (f(\mathbf {x} ))=\mathbf {A} \,,$

और यह कि न्यूनतम (उपयोग Df('x')=0) प्रारंभिक समस्या को इसके प्रथम व्युत्पन्न से हल करता है

$\nabla f(\mathbf {x} )=\mathbf {A} \mathbf {x} -\mathbf {b} \,.$

यह प्रथम आधार सदिश P₀ लेने का सुझाव देता है और 'x₀' = 'x₀' पर f की प्रवणता का ऋणात्मक होता है जिससे f की प्रवणता समान्तर होती है Ax − b. प्रारंभिक अनुमान x₀ से प्रारंभ किया जाता है इसका तात्पर्य है कि हम P₀ = B- कुल्हाड़ी लेते हैं जिसके आधार में अन्य वैक्टर ग्रेडिएंट के संयुग्मित होंगे, अतः नाम संयुग्म ग्रेडिएंट विधि है। ध्यान दें कि 'P'₀ एल्गोरिथम के इस प्रारंभिक चरण द्वारा प्रदान किया गया अवशिष्ट (संख्यात्मक विश्लेषण) भी है।

अतः r_k kवें चरण में अवशिष्ट (संख्यात्मक विश्लेषण) होता है।

$\mathbf {r} _{k}=\mathbf {b} -\mathbf {Ax} _{k}.$

जैसा कि ऊपर देखा गया है, $\mathbf {r} _{k}$ की ऋणात्मक प्रवणता $\mathbf {x} _{k}$ है,अतः ग्रेडिएंट डिसेंट विधि को दिशा r_k में स्थानांतरित करने की आवश्यकता होगी चूंकि, हम कह सकते हैं कि निर्देश $\mathbf {p} _{k}$ दूसरे से संयुग्मित होना चाहिए। इसे प्रयुक्त करने के लिए व्यावहारिक विधि यह है कि वर्तमान अवशिष्ट और सभी पिछली खोज दिशाओं से अगली खोज दिशा बनाई जाए। जो संयुग्मन बाधा ऑर्थोनॉर्मल-प्रकार की बाधा है अतः एल्गोरिथम को ग्राम-श्मिट प्रक्रिया के उदाहरण के रूप में देखा जा सकता है। ग्राम-श्मिट ऑर्थोनॉर्मलाइज़ेशन के माध्यम से निम्नलिखित अभिव्यक्ति देता है।

$\mathbf {p} _{k}=\mathbf {r} _{k}-\sum _{i<k}{\frac {\mathbf {p} _{i}^{\mathsf {T}}\mathbf {A} \mathbf {r} _{k}}{\mathbf {p} _{i}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{i}}}\mathbf {p} _{i}$

(अभिसरण पर संयुग्मन बाधा के प्रभाव के लिए लेख के शीर्ष पर चित्र देखें)। इस दिशा का पालन करते हुए अगला इष्टतम स्थान दिया गया है।

$\mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}$

जिसके साथ

$\alpha _{k}={\frac {\mathbf {p} _{k}^{\mathsf {T}}(\mathbf {b} -\mathbf {Ax} _{k})}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}}={\frac {\mathbf {p} _{k}^{\mathsf {T}}\mathbf {r} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}},$

जहां अंतिम समानता $\mathbf {r} _{k}$ की परिभाषा होती है।

जिसके लिए अभिव्यक्ति $\alpha _{k}$ व्युत्पन्न किया जा सकता है यदि कोई x_k+1 के लिए अभिव्यक्ति को प्रतिस्थापित करता है तब f और में और $\alpha _{k}$ इसके संबंध में इसे कम करना होता है

${\begin{aligned}f(\mathbf {x} _{k+1})&=f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})=:g(\alpha _{k})\\g'(\alpha _{k})&{\overset {!}{=}}0\quad \Rightarrow \quad \alpha _{k}={\frac {\mathbf {p} _{k}^{\mathsf {T}}(\mathbf {b} -\mathbf {Ax} _{k})}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}}\,.\end{aligned}}$

परिणामी एल्गोरिथ्म

उपरोक्त एल्गोरिथम संयुग्मी प्रवणता विधि की सबसे सरल व्याख्या देता है। प्रतीत होता है, जैसा कि कहा गया है कि एल्गोरिदम को सभी पिछली खोज दिशाओं और अवशेष वैक्टरों के साथ-साथ कई मैट्रिक्स-वेक्टर गुणाओं के भंडारण की आवश्यकता होती है, और इस प्रकार कम्प्यूटेशनल रूप से महंगा हो सकता है। चूँकि, एल्गोरिथम के करीबी विश्लेषण से पता चलता है $\mathbf {r} _{i}$ यह ओर्थोगोनल है $\mathbf {r} _{j}$, अर्थात। $\mathbf {r} _{i}^{\mathsf {T}}\mathbf {r} _{j}=0$ , मैं ≠ जे के लिए। और $\mathbf {p} _{i}$है $\mathbf {A}$-ऑर्थोगोनल यह $\mathbf {p} _{j}$ , अर्थात। $\mathbf {p} _{i}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{j}=0$ , के लिए $i\neq j$. यह माना जा सकता है कि जैसे-जैसे एल्गोरिथम आगे बढ़ता है, $\mathbf {p} _{i}$ और $\mathbf {r} _{i}$ ही क्रायलोव उप-क्षेत्र में फैला हुआ है। कहाँ $\mathbf {r} _{i}$ मानक आंतरिक उत्पाद के संबंध में ऑर्थोगोनल आधार बनाते हैं, और $\mathbf {p} _{i}$ द्वारा प्रेरित आंतरिक उत्पाद के संबंध में ऑर्थोगोनल आधार बनाते हैं $\mathbf {A}$. अतः, $\mathbf {x} _{k}$ का प्रक्षेपण माना जा सकता है $\mathbf {x}$ क्रायलोव उपक्षेत्र पर।

Ax = b को हल करने के लिए एल्गोरिथम का विवरण नीचे दिया गया है $\mathbf {A}$ वास्तविक, सममित, सकारात्मक-निश्चित मैट्रिक्स है। इनपुट वेक्टर $\mathbf {x} _{0}$ अनुमानित प्रारंभिक समाधान या 0 हो सकता है। यह ऊपर वर्णित त्रुटिहीन प्रक्रिया का अलग सूत्रीकरण है।

${\begin{aligned}&\mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{0}\\&{\hbox{if }}\mathbf {r} _{0}{\text{ is sufficiently small, then return }}\mathbf {x} _{0}{\text{ as the result}}\\&\mathbf {p} _{0}:=\mathbf {r} _{0}\\&k:=0\\&{\text{repeat}}\\&\qquad \alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {Ap} _{k}}}\\&\qquad \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\\&\qquad \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}\\&\qquad {\hbox{if }}\mathbf {r} _{k+1}{\text{ is sufficiently small, then exit loop}}\\&\qquad \beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {r} _{k+1}}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}}\\&\qquad \mathbf {p} _{k+1}:=\mathbf {r} _{k+1}+\beta _{k}\mathbf {p} _{k}\\&\qquad k:=k+1\\&{\text{end repeat}}\\&{\text{return }}\mathbf {x} _{k+1}{\text{ as the result}}\end{aligned}}$

यह सबसे अधिक उपयोग किया जाने वाला एल्गोरिदम है। के लिए ही सूत्र है β_k फ्लेचर-रीव्स नॉनलाइनियर कंजुगेट ग्रेडिएंट विधि में भी प्रयोग किया जाता है।

पुनरारंभ

हमने ध्यान दिया कि $\mathbf {x} _{1}$ ग्रेडिएंट डिसेंट#सॉल्यूशन ऑफ़ ए लीनियर प्रणाली मेथड द्वारा गणना की जाती है $\mathbf {x} _{0}$. सेटिंग $\beta _{k}=0$ इसी तरह बना देगा $\mathbf {x} _{k+1}$ ग्रेडिएंट डिसेंट#सॉल्यूशन ऑफ़ ए लीनियर प्रणाली मेथड द्वारा गणना की गई $\mathbf {x} _{k}$, अर्थात, संयुग्म ढाल पुनरावृत्तियों के पुनरारंभ के सरल कार्यान्वयन के रूप में उपयोग किया जा सकता है।पुनर्प्रारंभ अभिसरण को धीमा कर सकता है, लेकिन स्थिरता में सुधार कर सकता है यदि संयुग्मी ग्रेडिएंट विधि गलत व्यवहार करती है, उदाहरण के लिए, राउंड-ऑफ़ त्रुटि के कारण।

स्पष्ट अवशिष्ट गणना

सूत्र $\mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}$ और $\mathbf {r} _{k}:=\mathbf {b} -\mathbf {Ax} _{k}$, जो दोनों त्रुटिहीन अंकगणित में धारण करते हैं, सूत्र बनाते हैं $\mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}$ और $\mathbf {r} _{k+1}:=\mathbf {b} -\mathbf {Ax} _{k+1}$ गणितीय समकक्ष। पूर्व का उपयोग एल्गोरिथम में अतिरिक्त गुणन से बचने के लिए किया जाता है $\mathbf {A}$ वेक्टर के बाद से $\mathbf {Ap} _{k}$ मूल्यांकन के लिए पहले से ही गणना की गई है $\alpha _{k}$. उत्तरार्द्ध अधिक त्रुटिहीन हो सकता है, स्पष्ट गणना को प्रतिस्थापित कर सकता है $\mathbf {r} _{k+1}:=\mathbf {b} -\mathbf {Ax} _{k+1}$ निहित के लिए पुनरावर्ती त्रुटि संचय के अधीन है, और इस प्रकार सामयिक मूल्यांकन के लिए अनुशंसित है। अवशिष्ट का मानदंड सामान्यतः मानदंडों को रोकने के लिए उपयोग किया जाता है। स्पष्ट अवशिष्ट का मानदंड $\mathbf {r} _{k+1}:=\mathbf {b} -\mathbf {Ax} _{k+1}$ त्रुटिहीन अंकगणित और राउंडिंग त्रुटियों की उपस्थिति में त्रुटिहीनता का गारंटीकृत स्तर प्रदान करता है, जहां अभिसरण स्वाभाविक रूप से स्थिर हो जाता है। इसके विपरीत, निहित अवशिष्ट $\mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}$ गोलाई त्रुटियों के स्तर से अधिक नीचे आयाम में छोटा होता रहता है और इस प्रकार अभिसरण के ठहराव को निर्धारित करने के लिए उपयोग नहीं किया जा सकता है।

अल्फा और बीटा की गणना

एल्गोरिथ्म में, α_k ऐसा चुना जाता है $\mathbf {r} _{k+1}$ यह ओर्थोगोनल है $\mathbf {r} _{k}$. भाजक से सरलीकृत किया गया है

$\alpha _{k}={\frac {\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}}={\frac {\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {Ap} _{k}}}$

तब से $\mathbf {r} _{k+1}=\mathbf {p} _{k+1}-\mathbf {\beta } _{k}\mathbf {p} _{k}$. β_k }} ऐसा चुना जाता है कि $\mathbf {p} _{k+1}$ से संयुग्मित है $\mathbf {p} _{k}$. प्रारंभ में, β_k है

$\beta _{k}=-{\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}}}$

का उपयोग करते हुए

$\mathbf {r} _{k+1}=\mathbf {r} _{k}-\alpha _{k}\mathbf {A} \mathbf {p} _{k}$

और समान रूप से

$\mathbf {A} \mathbf {p} _{k}={\frac {1}{\alpha _{k}}}(\mathbf {r} _{k}-\mathbf {r} _{k+1}),$ का अंश β_k के रूप में पुनः लिखा जाता है

$\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}={\frac {1}{\alpha _{k}}}\mathbf {r} _{k+1}^{\mathsf {T}}(\mathbf {r} _{k}-\mathbf {r} _{k+1})=-{\frac {1}{\alpha _{k}}}\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {r} _{k+1}$

क्योंकि $\mathbf {r} _{k+1}$ और $\mathbf {r} _{k}$ डिजाइन द्वारा ओर्थोगोनल हैं। भाजक को फिर से लिखा जाता है

$\mathbf {p} _{k}^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}=(\mathbf {r} _{k}+\beta _{k-1}\mathbf {p} _{k-1})^{\mathsf {T}}\mathbf {A} \mathbf {p} _{k}={\frac {1}{\alpha _{k}}}\mathbf {r} _{k}^{\mathsf {T}}(\mathbf {r} _{k}-\mathbf {r} _{k+1})={\frac {1}{\alpha _{k}}}\mathbf {r} _{k}^{\mathsf {T}}\mathbf {r} _{k}$

इसका उपयोग करते हुए खोज दिशाएँ p_k संयुग्मित हैं और फिर से अवशिष्ट ऑर्थोगोनल हैं। यह देता है β एल्गोरिथ्म में रद्द करने के बाद α_k.

== MATLAB / GNU ऑक्टेव में उदाहरण कोड

<वाक्यविन्यास प्रकाश लैंग = matlab> फ़ंक्शन एक्स = कंजग्रेड (ए, बी, एक्स)

   आर = बी - ए * एक्स;
   पी = आर;
   आरसोल्ड = आर' * आर;

   मैं = 1 के लिए: लंबाई (बी)
       एपी = ए * पी;
       अल्फा = रसोल्ड / (पी '* एपी);
       एक्स = एक्स + अल्फा * पी;
       आर = आर - अल्फा * एपी;
       आरएसन्यू = आर' * आर;
       यदि sqrt(rsnew) <1e-10
           तोड़ना
       अंत
       पी = आर + (rsnew / rsold) * पी;
       rsold = rsnew;
   अंत

अंत </वाक्यविन्यास हाइलाइट>

संख्यात्मक उदाहरण

द्वारा दी गई रैखिक प्रणाली Ax = b पर विचार करें

$\mathbf {A} \mathbf {x} ={\begin{bmatrix}4&1\\1&3\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}={\begin{bmatrix}1\\2\end{bmatrix}},$

हम प्रारंभिक अनुमान से शुरुआत करते हुए संयुग्मी ढाल विधि के दो चरण करेंगे

$\mathbf {x} _{0}={\begin{bmatrix}2\\1\end{bmatrix}}$

प्रणाली के लिए अनुमानित समाधान खोजने के लिए।

उपाय

संदर्भ के लिए, त्रुटिहीन समाधान है

$\mathbf {x} ={\begin{bmatrix}{\frac {1}{11}}\\\\{\frac {7}{11}}\end{bmatrix}}\approx {\begin{bmatrix}0.0909\\\\0.6364\end{bmatrix}}$

हमारा पहला कदम अवशिष्ट सदिश r की गणना करना है₀ x से जुड़ा हुआ है₀. इस अवशिष्ट की गणना सूत्र r से की जाती है₀ = बी - कुल्हाड़ी₀, और हमारे स्थितियों में के बराबर है

$\mathbf {r} _{0}={\begin{bmatrix}1\\2\end{bmatrix}}-{\begin{bmatrix}4&1\\1&3\end{bmatrix}}{\begin{bmatrix}2\\1\end{bmatrix}}={\begin{bmatrix}-8\\-3\end{bmatrix}}=\mathbf {p} _{0}.$

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

अब हम स्केलर की गणना करते हैं α₀ संबंध का उपयोग करना

$\alpha _{0}={\frac {\mathbf {r} _{0}^{\mathsf {T}}\mathbf {r} _{0}}{\mathbf {p} _{0}^{\mathsf {T}}\mathbf {Ap} _{0}}}={\frac {{\begin{bmatrix}-8&-3\end{bmatrix}}{\begin{bmatrix}-8\\-3\end{bmatrix}}}{{\begin{bmatrix}-8&-3\end{bmatrix}}{\begin{bmatrix}4&1\\1&3\end{bmatrix}}{\begin{bmatrix}-8\\-3\end{bmatrix}}}}={\frac {73}{331}}\approx 0.2205$

अब हम x की गणना कर सकते हैं₁ सूत्र का उपयोग करना

$\mathbf {x} _{1}=\mathbf {x} _{0}+\alpha _{0}\mathbf {p} _{0}={\begin{bmatrix}2\\1\end{bmatrix}}+{\frac {73}{331}}{\begin{bmatrix}-8\\-3\end{bmatrix}}\approx {\begin{bmatrix}0.2356\\0.3384\end{bmatrix}}.$

यह परिणाम पहले पुनरावृत्ति को पूरा करता है, परिणाम प्रणाली के लिए बेहतर अनुमानित समाधान है, x₁. अब हम आगे बढ़ सकते हैं और अगले अवशिष्ट सदिश r की गणना कर सकते हैं₁ सूत्र का उपयोग करना

$\mathbf {r} _{1}=\mathbf {r} _{0}-\alpha _{0}\mathbf {A} \mathbf {p} _{0}={\begin{bmatrix}-8\\-3\end{bmatrix}}-{\frac {73}{331}}{\begin{bmatrix}4&1\\1&3\end{bmatrix}}{\begin{bmatrix}-8\\-3\end{bmatrix}}\approx {\begin{bmatrix}-0.2810\\0.7492\end{bmatrix}}.$

इस प्रक्रिया में हमारा अगला कदम स्केलर की गणना करना है β₀ जिसका उपयोग अंततः अगली खोज दिशा p निर्धारित करने के लिए किया जाएगा₁.

$\beta _{0}={\frac {\mathbf {r} _{1}^{\mathsf {T}}\mathbf {r} _{1}}{\mathbf {r} _{0}^{\mathsf {T}}\mathbf {r} _{0}}}\approx {\frac {{\begin{bmatrix}-0.2810&0.7492\end{bmatrix}}{\begin{bmatrix}-0.2810\\0.7492\end{bmatrix}}}{{\begin{bmatrix}-8&-3\end{bmatrix}}{\begin{bmatrix}-8\\-3\end{bmatrix}}}}=0.0088.$

अब इस अदिश का उपयोग करते हुए β₀, हम अगली खोज दिशा p की गणना कर सकते हैं₁ संबंध का उपयोग करना

$\mathbf {p} _{1}=\mathbf {r} _{1}+\beta _{0}\mathbf {p} _{0}\approx {\begin{bmatrix}-0.2810\\0.7492\end{bmatrix}}+0.0088{\begin{bmatrix}-8\\-3\end{bmatrix}}={\begin{bmatrix}-0.3511\\0.7229\end{bmatrix}}.$

अब हम स्केलर की गणना करते हैं α₁ हमारे नए अधिग्रहीत पी का उपयोग करना₁ के लिए जिस विधि का उपयोग किया जाता है उसी विधि का उपयोग करना α₀.

$\alpha _{1}={\frac {\mathbf {r} _{1}^{\mathsf {T}}\mathbf {r} _{1}}{\mathbf {p} _{1}^{\mathsf {T}}\mathbf {Ap} _{1}}}\approx {\frac {{\begin{bmatrix}-0.2810&0.7492\end{bmatrix}}{\begin{bmatrix}-0.2810\\0.7492\end{bmatrix}}}{{\begin{bmatrix}-0.3511&0.7229\end{bmatrix}}{\begin{bmatrix}4&1\\1&3\end{bmatrix}}{\begin{bmatrix}-0.3511\\0.7229\end{bmatrix}}}}=0.4122.$

अंत में, हम x पाते हैं₂ x को खोजने के लिए उपयोग की जाने वाली विधि का उपयोग करना₁.

$\mathbf {x} _{2}=\mathbf {x} _{1}+\alpha _{1}\mathbf {p} _{1}\approx {\begin{bmatrix}0.2356\\0.3384\end{bmatrix}}+0.4122{\begin{bmatrix}-0.3511\\0.7229\end{bmatrix}}={\begin{bmatrix}0.0909\\0.6364\end{bmatrix}}.$

नतीजा, एक्स₂, x की तुलना में प्रणाली के समाधान का बेहतर सन्निकटन है₁ और एक्स₀. यदि इस उदाहरण में सीमित-परिशुद्धता के अतिरिक्त त्रुटिहीन अंकगणित का उपयोग किया जाना था, तो सैद्धांतिक रूप से त्रुटिहीन समाधान n = 2 पुनरावृत्तियों (n प्रणाली का क्रम होने के नाते) के बाद पहुंचा होगा।

अभिसरण गुण

संयुग्मी ढाल विधि को सैद्धांतिक रूप से प्रत्यक्ष विधि के रूप में देखा जा सकता है, क्योंकि गोल-बंद त्रुटि के अभाव में यह पुनरावृत्तियों की सीमित संख्या के बाद त्रुटिहीन समाधान उत्पन्न करता है, जो मैट्रिक्स के आकार से बड़ा नहीं है। व्यावहारिक रूप से, त्रुटिहीन समाधान कभी प्राप्त नहीं होता है क्योंकि संयुग्मी ढाल विधि छोटी गड़बड़ी के संबंध में भी अस्थिर है, उदाहरण के लिए, क्रायलोव उप-स्थानों को उत्पन्न करने की अपक्षयी प्रकृति के कारण, अधिकांश दिशाएं संयुग्मित व्यवहार में नहीं हैं।

पुनरावृत्त विधि के रूप में, संयुग्मी ढाल विधि नीरस रूप से (ऊर्जा मानक में) सन्निकटन में सुधार करती है $\mathbf {x} _{k}$ त्रुटिहीन समाधान के लिए और पुनरावृत्तियों की अपेक्षाकृत छोटी (समस्या के आकार की तुलना में) संख्या के बाद आवश्यक सहिष्णुता तक पहुंच सकता है। सुधार सामान्यतः रैखिक होता है और इसकी गति स्थिति संख्या द्वारा निर्धारित की जाती है $\kappa (A)$ प्रणाली मैट्रिक्स का $A$: बड़ा $\kappa (A)$ है, सुधार जितना धीमा होगा। यदि $\kappa (A)$ बड़ा है, मूल प्रणाली को बदलने के लिए सामान्यतः पूर्व शर्त का उपयोग किया जाता है $\mathbf {Ax} -\mathbf {b} =0$ साथ $\mathbf {M} ^{-1}(\mathbf {Ax} -\mathbf {b} )=0$ ऐसा है कि $\kappa (\mathbf {M} ^{-1}\mathbf {A} )$ की तुलना में छोटा है $\kappa (\mathbf {A} )$, नीचे देखें।

अभिसरण प्रमेय

बहुपदों के उपसमुच्चय को इस रूप में परिभाषित कीजिए

$\Pi _{k}^{*}:=\left\lbrace \ p\in \Pi _{k}\ :\ p(0)=1\ \right\rbrace \,,$

कहाँ $\Pi _{k}$ अधिकतम डिग्री के बहुपद वलय का समुच्चय है $k$.

होने देना $\left(\mathbf {x} _{k}\right)_{k}$ त्रुटिहीन समाधान के पुनरावृत्त सन्निकटन हो $\mathbf {x} _{*}$, और त्रुटियों को परिभाषित करें $\mathbf {e} _{k}:=\mathbf {x} _{k}-\mathbf {x} _{*}$. अब, अभिसरण की दर का अनुमान लगाया जा सकता है

${\begin{aligned}\left\|\mathbf {e} _{k}\right\|_{\mathbf {A} }&=\min _{p\in \Pi _{k}^{*}}\left\|p(\mathbf {A} )\mathbf {e} _{0}\right\|_{\mathbf {A} }\\&\leq \min _{p\in \Pi _{k}^{*}}\,\max _{\lambda \in \sigma (\mathbf {A} )}|p(\lambda )|\ \left\|\mathbf {e} _{0}\right\|_{\mathbf {A} }\\&\leq 2\left({\frac {{\sqrt {\kappa (\mathbf {A} )}}-1}{{\sqrt {\kappa (\mathbf {A} )}}+1}}\right)^{k}\ \left\|\mathbf {e} _{0}\right\|_{\mathbf {A} }\,,\end{aligned}}$

कहाँ $\sigma (\mathbf {A} )$ मैट्रिक्स के स्पेक्ट्रम को दर्शाता है, और $\kappa (\mathbf {A} )$ स्थिति संख्या को दर्शाता है।

ध्यान दें, महत्वपूर्ण सीमा कब $\kappa (\mathbf {A} )$ आदत है $\infty$

${\frac {{\sqrt {\kappa (\mathbf {A} )}}-1}{{\sqrt {\kappa (\mathbf {A} )}}+1}}\approx 1-{\frac {2}{\sqrt {\kappa (\mathbf {A} )}}}\quad {\text{for}}\quad \kappa (\mathbf {A} )\gg 1\,.$

यह सीमा जैकोबी पद्धति या गॉस-सीडेल विधि की पुनरावृत्ति विधियों की तुलना में तेज अभिसरण दर दिखाती है। $\approx 1-{\frac {2}{\kappa (\mathbf {A} )}}$.

अभिसरण प्रमेय में कोई गोल-बंद त्रुटि नहीं मानी जाती है, लेकिन अभिसरण सीमा सामान्यतः व्यवहार में मान्य होती है जैसा कि सैद्धांतिक रूप से समझाया गया हैऐनी ग्रीनबाउम द्वारा।

व्यावहारिक अभिसरण

यदि बेतरतीब ढंग से आरंभ किया जाता है, तो पुनरावृत्तियों का पहला चरण अधिकांशतःसबसे तेज़ होता है, क्योंकि क्रायलोव उप-स्थान के भीतर त्रुटि समाप्त हो जाती है जो प्रारंभ में छोटी प्रभावी स्थिति संख्या को दर्शाती है। अभिसरण का दूसरा चरण सामान्यतः सैद्धांतिक अभिसरण द्वारा अच्छी तरह से परिभाषित होता है ${\textstyle {\sqrt {\kappa (\mathbf {A} )}}}$, लेकिन मैट्रिक्स के स्पेक्ट्रम के वितरण के आधार पर सुपर-रैखिक हो सकता है $A$ और त्रुटि का वर्णक्रमीय वितरण।अंतिम चरण में, सबसे छोटी प्राप्य त्रुटिहीनता तक पहुँच जाती है और अभिसरण रुक जाता है या विधि विचलन भी प्रारंभ कर सकती है। बड़े आकार के मैट्रिसेस के लिए डबल-परिशुद्धता फ़्लोटिंग-पॉइंट प्रारूप में विशिष्ट वैज्ञानिक कंप्यूटिंग अनुप्रयोगों में, संयुग्म ढाल विधि सहिष्णुता के साथ रोक मानदंड का उपयोग करती है जो पहले या दूसरे चरण के दौरान पुनरावृत्तियों को समाप्त करती है।

पूर्वानुकूल संयुग्म ग्रेडिएंट विधि

See also: Preconditioner

ज्यादातर स्थितियों में, संयुग्म ढाल विधि के तेजी से अभिसरण सुनिश्चित करने के लिए पूर्व शर्त आवश्यक है। यदि $\mathbf {M} ^{-1}$ सममित सकारात्मक-निश्चित है और $\mathbf {M} ^{-1}\mathbf {A}$ से बेहतर स्थिति संख्या है $\mathbf {A}$, पूर्वानुकूलित संयुग्मी प्रवणता विधि का उपयोग किया जा सकता है। यह निम्न रूप लेता है:

$\mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{0}$

$\mathbf {z} _{0}:=\mathbf {M} ^{-1}\mathbf {r} _{0}$

$\mathbf {p} _{0}:=\mathbf {z} _{0}$

$k:=0\,$

दोहराना

$\alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathsf {T}}\mathbf {z} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {Ap} _{k}}}$

$\mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}$

$\mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}$

यदि आर_k+1 पर्याप्त रूप से छोटा है तो बाहर निकलें लूप अंत यदि

$\mathbf {z} _{k+1}:=\mathbf {M} ^{-1}\mathbf {r} _{k+1}$

$\beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {z} _{k+1}}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {z} _{k}}}$

$\mathbf {p} _{k+1}:=\mathbf {z} _{k+1}+\beta _{k}\mathbf {p} _{k}$

$k:=k+1\,$

अंत दोहराएँ

परिणाम x है_k+1

उपरोक्त सूत्रीकरण नियमित संयुग्मी ढाल विधि को पूर्वानुकूलित प्रणाली में प्रयुक्त करने के बराबर है

$\mathbf {E} ^{-1}\mathbf {A} (\mathbf {E} ^{-1})^{\mathsf {T}}\mathbf {\hat {x}} =\mathbf {E} ^{-1}\mathbf {b}$

कहाँ

$\mathbf {EE} ^{\mathsf {T}}=\mathbf {M} ,\qquad \mathbf {\hat {x}} =\mathbf {E} ^{\mathsf {T}}\mathbf {x} .$

प्रणाली की समरूपता (और सकारात्मक निश्चितता) को बनाए रखने के लिए प्रीकंडिशनर के चोल्स्की अपघटन का उपयोग किया जाना चाहिए। चूँकि, इस अपघटन की गणना करने की आवश्यकता नहीं है, और यह जानने के लिए पर्याप्त है $\mathbf {M} ^{-1}$. यह दिखाया जा सकता है $\mathbf {E} ^{-1}\mathbf {A} (\mathbf {E} ^{-1})^{\mathsf {T}}$ के समान स्पेक्ट्रम है $\mathbf {M} ^{-1}\mathbf {A}$.

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

सामान्यतः उपयोग किए जाने वाले प्रीकंडीशनर का उदाहरण अपूर्ण चोल्स्की गुणनखंडन है।

लचीला पूर्व शर्त संयुग्म ढाल विधि

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

$\beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\left(\mathbf {z} _{k+1}-\mathbf {z} _{k}\right)}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {z} _{k}}}$

अरैखिक संयुग्मी ग्रेडिएंट पद्धति के अतिरिक्त | फ्लेचर-रीव्स सूत्र

$\beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {z} _{k+1}}{\mathbf {r} _{k}^{\mathsf {T}}\mathbf {z} _{k}}}$

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

लचीले संस्करण के कार्यान्वयन के लिए अतिरिक्त वेक्टर के भंडारण की आवश्यकता होती है। निश्चित एसपीडी पूर्व शर्त के लिए, $\mathbf {r} _{k+1}^{\mathsf {T}}\mathbf {z} _{k}=0,$ अतः दोनों सूत्र β_k त्रुटिहीन अंकगणित में समतुल्य हैं, अर्थात राउंड-ऑफ त्रुटि के बिना।

गैर-रैखिक संयुग्म ग्रेडिएंट विधि के साथ विधि के बेहतर अभिसरण व्यवहार की गणितीय व्याख्या। पोलक-रिबिएर सूत्र यह है कि इस स्थितियों में विधि स्थानीय रूप से इष्टतम है, विशेष रूप से, यह स्थानीय रूप से इष्टतम स्टीपेस्ट डिसेंट विधि की तुलना में धीमी अभिसरण नहीं करती है।

बनाम। स्थानीय रूप से इष्टतम स्टीपेस्ट डिसेंट विधि

मूल और पूर्वानुकूल संयुग्म ग्रेडिएंट दोनों विधियों में केवल सेट करने की आवश्यकता होती है $\beta _{k}:=0$ रेखा खोज, तेज वंश विधियों का उपयोग करके उन्हें स्थानीय रूप से इष्टतम बनाने के लिए। इस प्रतिस्थापन के साथ, vectors p हमेशा वैक्टर के समान होते हैं z, अतः वैक्टर को स्टोर करने की कोई जरूरत नहीं है p. इस प्रकार, संयुग्मित ढाल विधियों की तुलना में इन सबसे तेज वंश विधियों का प्रत्येक पुनरावृत्ति थोड़ा सस्ता है। चूंकि, बाद वाला तेजी से अभिसरण करता है, जब तक कि (अत्यधिक) चर और/या गैर-एसपीडी पूर्व शर्त का उपयोग नहीं किया जाता है, ऊपर देखें।

== डबल इंटीग्रेटर == के लिए इष्टतम प्रतिक्रिया नियंत्रक के रूप में संयुग्मित ढाल विधि

इष्टतम नियंत्रण का उपयोग करके संयुग्म ढाल विधि भी प्राप्त की जा सकती है। इस दृष्टिकोण में, संयुग्मी ढाल विधि प्रतिक्रिया नियंत्रण के रूप में बाहर हो जाती है,

$$u=k(x,v):=-\gamma _{a}\nabla f(x)-\gamma _{b}v$$

डबल इंटीग्रेटर के लिए,

$${\dot {x}}=v,\quad {\dot {v}}=u$$

मात्राएँ $\gamma _{a}$ और $\gamma _{b}$ परिवर्तनीय प्रतिक्रिया लाभ हैं।

सामान्य समीकरणों पर संयुग्म ढाल

संयुग्मी ढाल विधि को सामान्य समीकरणों 'ए' पर प्रयुक्त करके मनमाने ढंग से एन-बाय-एम मैट्रिक्स पर प्रयुक्त किया जा सकता है।^TA और दाईं ओर सदिश A^टीबी, चूंकि ए^TA किसी भी A के लिए सममित सकारात्मक-निश्चित मैट्रिक्स#Negative-definite.2C अर्ध-निश्चित और अनिश्चित मैट्रिक्स|सकारात्मक-अर्ध-अर्ध-परिमित मैट्रिक्स है। परिणाम सामान्य समीकरणों (CGNR) पर संयुग्मित ढाल है।

ए^टीकुल्हाड़ी = ए^{टी</सुप>बी}

पुनरावृत्त विधि के रूप में, A बनाना आवश्यक नहीं है^TA स्मृति में स्पष्ट रूप से लेकिन केवल मैट्रिक्स-वेक्टर को निष्पादित करने और मैट्रिक्स-वेक्टर गुणन को स्थानांतरित करने के लिए। अतः, सीजीएनआर विशेष रूप से उपयोगी होता है जब 'ए' विरल मैट्रिक्स होता है क्योंकि ये ऑपरेशन सामान्यतः बेहद कुशल होते हैं। चूँकि सामान्य समीकरण बनाने का नकारात्मक पक्ष यह है कि स्थिति संख्या κ(A^TA) κ के बराबर है²(ए) और अतः सीजीएनआर के अभिसरण की दर धीमी हो सकती है और अनुमानित समाधान की गुणवत्ता राउंडऑफ त्रुटियों के प्रति संवेदनशील हो सकती है। अच्छा पूर्व-कंडीशनर ढूँढना अधिकांशतःसीजीएनआर पद्धति का उपयोग करने का महत्वपूर्ण हिस्सा होता है।

कई एल्गोरिदम प्रस्तावित किए गए हैं (उदाहरण के लिए, सीजीएलएस, एलएसक्यूआर)। LSQR एल्गोरिथम कथित तौर पर सर्वश्रेष्ठ संख्यात्मक स्थिरता रखता है जब A बीमार होता है, अर्थात, A के पास बड़ी स्थिति संख्या होती है।

जटिल हर्मिटियन मेट्रिसेस के लिए संयुग्मी ग्रेडिएंट विधि

जटिल-मूल्यवान मैट्रिक्स ए और वेक्टर बी, रैखिक समीकरणों की प्रणाली को देखते हुए, तुच्छ संशोधन के साथ संयुग्म ढाल विधि को हल करने के लिए विस्तार योग्य है $\mathbf {A} \mathbf {x} =\mathbf {b}$ कॉम्प्लेक्स-वैल्यू वेक्टर x के लिए, जहां ए हर्मिटियन है (अर्थात, ए' = ए) और सकारात्मक-निश्चित मैट्रिक्स, और प्रतीक ' MATLAB/GNU ऑक्टेव शैली का उपयोग करके संयुग्मित संक्रमण को दर्शाता है। तुच्छ संशोधन हर जगह वास्तविक स्थानान्तरण के लिए बस संयुग्म स्थानान्तरण को प्रतिस्थापित कर रहा है। यह प्रतिस्थापन पिछड़ा संगत है, क्योंकि संयुग्मित स्थानान्तरण वास्तविक-मूल्यवान सदिशों और आव्यूहों पर वास्तविक स्थानान्तरण में बदल जाता है। ऊपर दिए गए कॉन्जुगेट ग्रेडिएंट मेथड # उदाहरण कोड MATLAB / GNU ऑक्टेव में | MATLAB / GNU ऑक्टेव में उदाहरण कोड इस प्रकार पहले से ही जटिल हर्मिटियन मैट्रिसेस के लिए काम करता है, जिसमें किसी संशोधन की आवश्यकता नहीं है।

यह भी देखें

• बीकॉन्जुगेट ग्रेडिएंट विधि (बीआईसीजी)
• अवशिष्ट अवशिष्ट विधि
• विश्वास प्रचार # गाऊसी विश्वास प्रचार .28GaBP.29
• इटरेटिव मेथड # लीनियर सिस्टम | इटरेटिव मेथड: लीनियर सिस्टम
• क्रायलोव उपक्षेत्र
• गैर रेखीय संयुग्म ढाल विधि
• पूर्व शर्त
• विरल मैट्रिक्स-वेक्टर गुणन

अग्रिम पठन

• 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]