प्रीकंडीशनर: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(5 intermediate revisions by 3 users not shown)
Line 6: Line 6:
== रैखिक प्रणालियों के लिए पूर्व नियम ==
== रैखिक प्रणालियों के लिए पूर्व नियम ==


रैखिक बीजगणित और [[संख्यात्मक विश्लेषण]] में, आव्युह <math>A                                                                                                                                                                                                                    </math> का प्रीकंडीशनर <math>P</math> आव्युह ऐसा है जैसे कि <math> P^{-1}A                                                                                                                                                                                                            </math> की स्थिति संख्या <math>A</math> से छोटी है।. इसे <math>T=P^{-1}</math>कहना भी सामान्य बात है <math>P</math> के अतिरिक्त प्रीकंडीशनर, क्योंकि <math>P</math> स्वयं शायद ही कभी स्पष्ट रूप से उपलब्ध होता है। आधुनिक प्रीकंडीशनिंग में, <math>T = P^{-1}</math>का अनुप्रयोग अर्थात, स्तम्भ सदिश, या स्तम्भ वैक्टर के ब्लॉक को <math>T = P^{-1}</math> से गुणा करना, सामान्यतः आव्युह-मुक्त विधियों में किया जाता है | आव्युह-मुक्त फैशन, अर्थात, जहां न तो <math>P</math>, और न <math>T = P^{-1}</math> (और अधिकांशतः <math>A</math> भी नहीं) आव्युह रूप में स्पष्ट रूप से उपलब्ध हैं।
रैखिक बीजगणित और [[संख्यात्मक विश्लेषण]] में, आव्युह <math>A                                                                                                                                                                                                                    </math> का प्रीकंडीशनर <math>P</math> आव्युह ऐसा है जैसे कि <math> P^{-1}A                                                                                                                                                                                                            </math> की स्थिति संख्या <math>A</math> से छोटी है।. इसे <math>T=P^{-1}</math>कहना भी सामान्य बात है <math>P</math> के अतिरिक्त प्रीकंडीशनर, क्योंकि <math>P</math> स्वयं शायद ही कभी स्पष्ट रूप से उपलब्ध होता है। आधुनिक प्रीकंडीशनिंग में, <math>T = P^{-1}</math>का अनुप्रयोग अर्थात, स्तम्भ सदिश, या स्तम्भ सदिश के ब्लॉक को <math>T = P^{-1}</math> से गुणा करना, सामान्यतः आव्युह-मुक्त विधियों में किया जाता है | आव्युह-मुक्त फैशन, अर्थात, जहां न तो <math>P</math>, और न <math>T = P^{-1}</math> (और अधिकांशतः <math>A</math> भी नहीं) आव्युह रूप में स्पष्ट रूप से उपलब्ध हैं।


प्रीकंडीशनर <math>x</math> के लिए रैखिक प्रणाली <math>Ax=b                                                                                                                                                                                                  </math> को हल करने के लिए पुनरावृत्त विधियों में उपयोगी होते हैं चूंकि अधिकांश पुनरावृत्त रैखिक सॉल्वरों के लिए [[अभिसरण की दर]] बढ़ जाती है क्योंकि प्रीकंडीशनिंग के परिणामस्वरूप आव्युह की स्थिति संख्या कम हो जाती है। पूर्वनिर्धारित पुनरावृत्त सॉल्वर सामान्यतः प्रत्यक्ष सॉल्वर से उत्तम प्रदर्शन करते हैं, उदाहरण के लिए, गॉसियन उन्मूलन, बड़े के लिए, विशेष रूप से [[विरल मैट्रिक्स|विरल आव्युह]], मैट्रिसेस के लिए। पुनरावृत्त सॉल्वर का उपयोग आव्युह-मुक्त विधियों के रूप में किया जा सकता है, अर्थात गुणांक आव्युह होने पर एकमात्र विकल्प बन जाता है <math>A</math> स्पष्ट रूप से संग्रहीत नहीं है, किन्तु आव्युह-सदिश उत्पादों का मूल्यांकन करके इस तक पहुंचा जाता है।  
प्रीकंडीशनर <math>x</math> के लिए रैखिक प्रणाली <math>Ax=b                                                                                                                                                                                                  </math> को हल करने के लिए पुनरावृत्त विधियों में उपयोगी होते हैं चूंकि अधिकांश पुनरावृत्त रैखिक सॉल्वरों के लिए [[अभिसरण की दर]] बढ़ जाती है क्योंकि प्रीकंडीशनिंग के परिणामस्वरूप आव्युह की स्थिति संख्या कम हो जाती है। पूर्वनिर्धारित पुनरावृत्त सॉल्वर सामान्यतः प्रत्यक्ष सॉल्वर से उत्तम प्रदर्शन करते हैं, उदाहरण के लिए, गॉसियन उन्मूलन, बड़े के लिए, विशेष रूप से [[विरल मैट्रिक्स|विरल]] मैट्रिसेस के लिए पुनरावृत्त सॉल्वर का उपयोग आव्युह-मुक्त विधियों के रूप में किया जा सकता है, अर्थात गुणांक आव्युह होने पर एकमात्र विकल्प बन जाता है जहाँ <math>A</math> स्पष्ट रूप से संग्रहीत नहीं है, किन्तु आव्युह-सदिश उत्पादों का मूल्यांकन करके इस तक पहुंचा जाता है।  


=== विवरण ===
=== विवरण ===
Line 16: Line 16:
और हल करें
और हल करें
<math display="block">AP^{-1}y=b</math>
<math display="block">AP^{-1}y=b</math>
<math>y</math> के लिए और
<math>y</math> के लिए और
<math display="block">Px = y</math>
<math display="block">Px = y</math>
<math>x</math> के लिए .
<math>x</math> के लिए .
Line 26: Line 26:
दो तरफा पूर्व नियम प्रणाली   
दो तरफा पूर्व नियम प्रणाली   
<math display="block"> QAP^{-1}(Px) = Qb</math>
<math display="block"> QAP^{-1}(Px) = Qb</math>
लाभदायक हो सकता है, उदाहरण के लिए, आव्युह समरूपता को संरक्षित करने के लिए: यदि मूल आव्युह <math>A</math> वास्तविक सममित है और वास्तविक प्रीकंडीशनर <math>Q</math> और <math>P</math> <math>Q^{T} = P^{-1}</math> संतुष्ट करते हैं तब फिर पूर्वनिर्धारित आव्युह <math> QAP^{-1}</math> सममित भी है. दो-तरफा प्रीकंडीशनर विकर्ण स्केलिंग के लिए सामान्य है जहां प्रीकंडीशनिंग <math>Q</math> और <math>P</math> विकर्ण हैं और स्केलिंग मूल आव्युह <math>A</math> के स्तंभों और पंक्तियों दोनों पर प्रयुक्त होती है, जहाँ उदाहरण के लिए, आव्युह की प्रविष्टियों की गतिशील सीमा को कम करने के लिए उपयोग किया जाता है।
यह लाभदायक हो सकता है, उदाहरण के लिए, आव्युह समरूपता को संरक्षित करने के लिए: यदि मूल आव्युह <math>A</math> वास्तविक सममित है और वास्तविक प्रीकंडीशनर <math>Q</math> और <math>P</math> <math>Q^{T} = P^{-1}</math> संतुष्ट करते हैं तब फिर पूर्वनिर्धारित आव्युह <math> QAP^{-1}</math> सममित भी है. दो-तरफा प्रीकंडीशनर विकर्ण स्केलिंग के लिए सामान्य है जहां प्रीकंडीशनिंग <math>Q</math> और <math>P</math> विकर्ण हैं और स्केलिंग मूल आव्युह <math>A</math> के स्तंभों और पंक्तियों दोनों पर प्रयुक्त होती है, जहाँ उदाहरण के लिए, आव्युह की प्रविष्टियों की गतिशील सीमा को कम करने के लिए उपयोग किया जाता है।


प्रीकंडीशनिंग का लक्ष्य नियम संख्या को कम करना है, उदाहरण के लिए, बाएं या दाएं प्रीकंडिशनिंग पद्धति आव्युह <math>P^{-1}A</math> या <math>AP^{-1}</math> की | छोटी स्थिति संख्याएं पुनरावृत्त सॉल्वरों के तेजी से अभिसरण का लाभ उठाती हैं और पद्धति आव्युह और दाईं ओर त्रुटी के संबंध में समाधान की स्थिरता में सुधार करती हैं, उदाहरण के लिए, कम परिशुद्धता (कंप्यूटर) का उपयोग करके आव्युह प्रविष्टियों के अधिक आक्रामक [[ परिमाणीकरण (सिग्नल प्रोसेसिंग) |परिमाणीकरण (सिग्नल प्रोसेसिंग)]] की अनुमति देती है विज्ञान)।
प्रीकंडीशनिंग का लक्ष्य नियम संख्या को कम करना है, उदाहरण के लिए, बाएं या दाएं प्रीकंडिशनिंग पद्धति आव्युह <math>P^{-1}A</math> या <math>AP^{-1}</math> की छोटी स्थिति संख्याएं पुनरावृत्त सॉल्वरों के तेजी से अभिसरण का लाभ उठाती हैं और पद्धति आव्युह और दाईं ओर त्रुटी के संबंध में समाधान की स्थिरता में सुधार करती हैं, उदाहरण के लिए, कम परिशुद्धता (कंप्यूटर) का उपयोग करके आव्युह प्रविष्टियों के अधिक आक्रामक [[ परिमाणीकरण (सिग्नल प्रोसेसिंग) |परिमाणीकरण (सिग्नल प्रोसेसिंग)]] विज्ञान की अनुमति देती है।


पूर्वनिर्धारित आव्युह <math>P^{-1}A</math> या <math>AP^{-1}</math> शायद ही कभी स्पष्ट रूप से गठित किया गया हो। किसी दिए गए सदिश पर केवल प्रीकंडीशनर सॉल्व ऑपरेशन <math>P^{-1}</math> को प्रयुक्त करने की क्रिया की गणना करने की आवश्यकता हो सकती है।
पूर्वनिर्धारित आव्युह <math>P^{-1}A</math> या <math>AP^{-1}</math> शायद ही कभी स्पष्ट रूप से गठित किया गया हो। किसी दिए गए सदिश पर केवल प्रीकंडीशनर सॉल्व ऑपरेशन <math>P^{-1}</math> को प्रयुक्त करने की क्रिया की गणना करने की आवश्यकता हो सकती है।


सामान्यतः <math>P</math> चयन में समझौता होता है चूंकि ऑपरेटर <math>P^{-1}</math> को पुनरावृत्त रैखिक सॉल्वर के प्रत्येक चरण पर प्रयुक्त किया जाना चाहिए, इसीलिए इसे प्रयुक्त करने की छोटी लागत (कंप्यूटिंग समय) होनी चाहिए <math>P^{-1}</math> संचालन। इसलिए सबसे सस्ता प्रीकंडीशनर <math>P=I</math> होगा क्योंकि तब <math>P^{-1}=I.</math>. स्पष्ट रूप से, इसका परिणाम मूल रैखिक प्रणाली में होता है और प्रीकंडीशनर कुछ नहीं करता है। दूसरे चरम पर, विकल्प <math>P=A</math> देता है <math>P^{-1}A = AP^{-1} = I,</math> जिसकी इष्टतम स्थिति संख्या 1 है, अभिसरण के लिए एकल पुनरावृत्ति की आवश्यकता है; '''हालाँकि''' इस मामले में <math>P^{-1}=A^{-1},</math> और प्रीकंडीशनर को प्रयुक्त करना मूल प्रणाली को हल करने जितना ही कठिन है। इसलिए, ऑपरेटर <math>P^{-1}</math> को यथासंभव सरल रखते हुए न्यूनतम संख्या में रैखिक पुनरावृत्तियों को प्राप्त करने के प्रयास में, इन दोनों चरम सीमाओं के मध्य में <math>P</math> को चुना जाता है। विशिष्ट प्रीकंडीशनिंग दृष्टिकोण के कुछ उदाहरण नीचे विस्तृत हैं।
सामान्यतः <math>P</math> चयन में समझौता होता है चूंकि ऑपरेटर <math>P^{-1}</math> को पुनरावृत्त रैखिक सॉल्वर के प्रत्येक चरण पर प्रयुक्त किया जाना चाहिए, इसीलिए इसे प्रयुक्त करने की छोटी निवेश (कंप्यूटिंग समय) होनी चाहिए <math>P^{-1}</math> संचालन। इसलिए सबसे सस्ता प्रीकंडीशनर <math>P=I</math> होगा क्योंकि तब <math>P^{-1}=I.</math>. स्पष्ट रूप से, इसका परिणाम मूल रैखिक प्रणाली में होता है और प्रीकंडीशनर कुछ नहीं करता है। दूसरे चरम पर, विकल्प <math>P=A</math> देता है <math>P^{-1}A = AP^{-1} = I,</math> जिसकी इष्टतम स्थिति संख्या 1 है, अभिसरण के लिए एकल पुनरावृत्ति की आवश्यकता है; चूँकि इस स्तिथि में <math>P^{-1}=A^{-1},</math> और प्रीकंडीशनर को प्रयुक्त करना मूल प्रणाली को हल करने जितना ही कठिन है। इसलिए, ऑपरेटर <math>P^{-1}</math> को यथासंभव सरल रखते हुए न्यूनतम संख्या में रैखिक पुनरावृत्तियों को प्राप्त करने के प्रयास में, इन दोनों चरम सीमाओं के मध्य में <math>P</math> को चुना जाता है। विशिष्ट प्रीकंडीशनिंग दृष्टिकोण के कुछ उदाहरण नीचे विस्तृत हैं।


===पूर्वनिर्धारित पुनरावृत्तीय विधियाँ===
===पूर्वनिर्धारित पुनरावृत्तीय विधियाँ===
<math>Ax - b = 0</math> के लिए पूर्वनिर्धारित पुनरावृत्तीय विधियाँ अधिकांश स्तिथियों में, गणितीय रूप से पूर्वनिर्धारित प्रणाली <math>P^{-1}(Ax-b)=0.</math> पर प्रयुक्त मानक पुनरावृत्त विधियों के समान हैं उदाहरण के लिए, <math>Ax - b = 0</math> को हल करने के लिए मानक [[रिचर्डसन पुनरावृत्ति]] है
<math>Ax - b = 0</math> के लिए पूर्वनिर्धारित पुनरावृत्तीय विधियाँ अधिकांश स्तिथियों में, गणितीय रूप से पूर्वनिर्धारित प्रणाली <math>P^{-1}(Ax-b)=0.</math> पर प्रयुक्त मानक पुनरावृत्त विधियों के समान हैं उदाहरण के लिए, <math>Ax - b = 0</math> को हल करने के लिए मानक [[रिचर्डसन पुनरावृत्ति]] है
<math display="block">\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n (A\mathbf{x}_n-\mathbf{b}),\ n \ge 0.</math>
<math display="block">\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n (A\mathbf{x}_n-\mathbf{b}),\ n \ge 0.</math>


पूर्व नियम प्रणाली <math>P^{-1}(Ax-b)=0,                                                                                                                                                                                                    </math> पर प्रयुक्त किया गया यह पूर्वनिर्धारित पद्धति में परिवर्तित हो जाता है
पूर्व नियम प्रणाली <math>P^{-1}(Ax-b)=0,                                                                                                                                                                                                    </math> पर प्रयुक्त किया गया यह पूर्वनिर्धारित पद्धति में परिवर्तित हो जाता है
Line 55: Line 54:


===ज्यामितीय व्याख्या===
===ज्यामितीय व्याख्या===
सममित आव्युह धनात्मक -निश्चित आव्युह आव्युह के लिए <math>A</math> पूर्व नियम लगानेवाला <math>P</math> सामान्यतः सममित धनात्मक निश्चित होने के लिए भी चुना जाता है। पूर्व नियम ऑपरेटर <math>P^{-1}A</math> फिर सममित धनात्मक निश्चित भी है, किन्तु के संबंध में <math>P</math>-आधारित [[अदिश उत्पाद]]इस मामले में, प्रीकंडीशनर को प्रयुक्त करने में वांछित प्रभाव प्रीकंडीशनर ऑपरेटर का [[द्विघात रूप]] बनाना है <math>P^{-1}A</math> के प्रति सम्मान के साथ <math>P</math>-आधारित अदिश उत्पाद का लगभग गोलाकार होना।<ref>{{cite web |title=कष्टकारी दर्द के बिना संयुग्मित ग्रेडिएंट विधि का परिचय|first=Jonathan Richard |last=Shewchuk |date=August 4, 1994 |url=https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf#page=24 }}</ref>
सममित आव्युह धनात्मक -निश्चित आव्युह <math>A</math> के लिए प्रीकंडीशनर <math>P</math> को सामान्यतः सममित धनात्मक निश्चित होने के लिए भी चुना जाता है। प्रीकंडीशनर ऑपरेटर <math>P^{-1}A</math> फिर भी सममित धनात्मक निश्चित है, किन्तु <math>P</math>-आधारित [[अदिश उत्पाद]] के संबंध में। इस स्तिथि में, प्रीकंडीशनर को प्रयुक्त करने में वांछित प्रभाव <math>P</math>-आधारित स्केलर उत्पाद के संबंध में प्रीकंडिशनर ऑपरेटर <math>P^{-1}A</math> के द्विघात रूप को लगभग गोलाकार बनाना है।।<ref>{{cite web |title=कष्टकारी दर्द के बिना संयुग्मित ग्रेडिएंट विधि का परिचय|first=Jonathan Richard |last=Shewchuk |date=August 4, 1994 |url=https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf#page=24 }}</ref>




=== परिवर्तनीय और गैर-रैखिक पूर्व शर्त ===
दर्शाने <math>T = P^{-1}</math>, हम इस बात पर प्रकाश डालते हैं कि प्रीकंडीशनिंग को व्यावहारिक रूप से कुछ सदिश को गुणा करने के रूप में कार्यान्वित किया जाता है <math>r</math> द्वारा <math>T</math>, अर्थात, उत्पाद की गणना करना <math>Tr.</math> कई अनुप्रयोगों में, <math>T</math> आव्युह के रूप में नहीं, बल्कि ऑपरेटर के रूप में दिया गया है <math>T(r)</math> सदिश पर कार्य करना <math>r</math>. हालाँकि, कुछ लोकप्रिय प्रीकंडीशनर परिवर्तित हो जाते हैं <math>r</math> और पर निर्भरता <math>r</math> रैखिक नहीं हो सकता. विशिष्ट उदाहरणों में प्रीकंडीशनर निर्माण के भाग के रूप में गैर-रेखीय पुनरावृत्त विधियों का उपयोग करना सम्मिलित है, उदाहरण के लिए, संयुग्म ग्रेडिएंट विधि। ऐसे प्रीकंडीशनर व्यावहारिक रूप से बहुत कुशल हो सकते हैं, हालांकि, सैद्धांतिक रूप से उनके व्यवहार की भविष्यवाणी करना कठिन है।


=== यादृच्छिक पूर्व शर्त ===
=== परिवर्तनीय और गैर-रैखिक प्रीकंडीशनिंग ===
वैरिएबल प्रीकंडीशनिंग का दिलचस्प विशेष मामला रैंडम प्रीकंडिशनिंग है, उदाहरण के लिए, रैंडम कोर्स ग्रिड पर [[मल्टीग्रिड]] प्रीकंडिशनिंग।<ref>Henricus Bouwmeester, Andrew Dougherty, Andrew V Knyazev. Nonsymmetric Preconditioning for Conjugate Gradient and Steepest Descent Methods. Procedia Computer Science, Volume 51, Pages 276-285, Elsevier, 2015. https://doi.org/10.1016/j.procs.2015.05.241</ref> यदि [[ ढतला हुआ वंश |ढतला हुआ वंश]] विधियों में उपयोग किया जाता है, तो यादृच्छिक प्रीकंडीशनिंग को [[स्टोकेस्टिक ग्रेडिएंट डिसेंट]] के कार्यान्वयन के रूप में देखा जा सकता है और निश्चित प्रीकंडिशनिंग की तुलना में तेजी से अभिसरण हो सकता है, क्योंकि यह ग्रेडिएंट डिसेंट के एसिम्प्टोटिक ज़िग-ज़ैग पैटर्न को तोड़ता है।
<math>T = P^{-1}</math> को दर्शाते हुए, हम इस बात पर प्रकाश डालते हैं कि प्रीकंडीशनिंग को व्यावहारिक रूप से कुछ सदिश <math>r                                                                                                                                                        </math> को <math>T                                                                                                                                                                                                      </math> से गुणा करने के रूप में कार्यान्वित किया जाता है, अर्थात, उत्पाद <math>Tr.</math> की गणना करना होता है | अनेक अनुप्रयोगों में, <math>T</math> को आव्युह के रूप में नहीं दिया जाता है, बल्कि सदिश <math>r</math> पर कार्य करने वाले ऑपरेटर <math>T(r)</math> के रूप में दिया गया है. चूँकि, कुछ लोकप्रिय प्रीकंडीशनर <math>r</math> के साथ परिवर्तित हो जाते हैं और <math>r</math> पर निर्भरता रैखिक नहीं हो सकती है | विशिष्ट उदाहरणों में प्रीकंडीशनर निर्माण के भाग के रूप में गैर-रेखीय पुनरावृत्त विधियों का उपयोग करना सम्मिलित है, उदाहरण के लिए, संयुग्म ग्रेडिएंट विधि। ऐसे प्रीकंडीशनर व्यावहारिक रूप से बहुत कुशल हो सकते हैं, चूंकि, सैद्धांतिक रूप से उनके व्यवहार की भविष्यवाणी करना कठिन है।


===वर्णक्रमीय समतुल्य पूर्व शर्त===
=== यादृच्छिक प्रीकंडीशनिंग ===
प्रीकंडीशनिंग का सबसे सामान्य उपयोग [[आंशिक अंतर समीकरण]]ों के अनुमान के परिणामस्वरूप रैखिक प्रणालियों के पुनरावृत्त समाधान के लिए है। सन्निकटन गुणवत्ता जितनी उत्तम होगी, आव्युह का आकार उतना ही बड़ा होगा। ऐसे मामले में, इष्टतम प्रीकंडीशनिंग का लक्ष्य, तरफ, वर्णक्रमीय स्थिति संख्या बनाना है <math> P^{-1}A</math> ऊपर से आव्युह आकार से स्वतंत्र स्थिरांक द्वारा घिरा होना, जिसे एवगेनी जॉर्जिविच डी'याकोनोव|डी'याकोनोव द्वारा वर्णक्रमीय समकक्ष प्रीकंडीशनिंग कहा जाता है। दूसरी ओर, के आवेदन की लागत <math> P^{-1}</math> आदर्श रूप से गुणन की लागत के समानुपाती (आव्युह आकार से भी स्वतंत्र) होना चाहिए <math>A</math> सदिश द्वारा.
वैरिएबल प्रीकंडीशनिंग का दिलचस्प विशेष स्तिथि रैंडम प्रीकंडिशनिंग है, उदाहरण के लिए, रैंडम कोर्स ग्रिड पर [[मल्टीग्रिड]] प्रीकंडिशनिंग।<ref>Henricus Bouwmeester, Andrew Dougherty, Andrew V Knyazev. Nonsymmetric Preconditioning for Conjugate Gradient and Steepest Descent Methods. Procedia Computer Science, Volume 51, Pages 276-285, Elsevier, 2015. https://doi.org/10.1016/j.procs.2015.05.241</ref> यदि [[ ढतला हुआ वंश |ग्रेडिएंट डिसेंट]] विधियों में उपयोग किया जाता है, तो यादृच्छिक प्रीकंडीशनिंग को [[स्टोकेस्टिक ग्रेडिएंट डिसेंट]] के कार्यान्वयन के रूप में देखा जा सकता है और निश्चित प्रीकंडिशनिंग की तुलना में तेजी से अभिसरण हो सकता है, क्योंकि यह ग्रेडिएंट डिसेंट के एसिम्प्टोटिक ज़िग-ज़ैग पैटर्न को तोड़ता है।
 
===वर्णक्रमीय समतुल्य प्रीकंडीशनिंग ===
प्रीकंडीशनिंग का सबसे सामान्य उपयोग [[आंशिक अंतर समीकरण|आंशिक अंतर समीकरणों]] के अनुमान के परिणामस्वरूप रैखिक प्रणालियों के पुनरावृत्त समाधान के लिए है। सन्निकटन गुणवत्ता जितनी उत्तम होगी, आव्युह का आकार उतना ही बड़ा होगा जितना ऐसे स्तिथि में, इष्टतम प्रीकंडीशनिंग का लक्ष्य, तरफ, <math> P^{-1}A</math> की वर्णक्रमीय स्थिति संख्या को आव्युह आकार से स्वतंत्र स्थिरांक द्वारा ऊपर से सीमित करना होता है, जिसे कहा जाता है डायकोनोव द्वारा वर्णक्रमीय रूप से समतुल्य प्रीकंडीशनिंग। दूसरी ओर, <math> P^{-1}</math> के अनुप्रयोग की निवेश आदर्श रूप से सदिश द्वारा <math>A</math> के गुणन की निवेश के समानुपाती (आव्युह आकार से स्वतंत्र भी) होनी चाहिए।


===उदाहरण===
===उदाहरण===


====जैकोबी (या विकर्ण) प्रीकंडीशनर====
====जैकोबी (या विकर्ण) प्रीकंडीशनर====
जैकोबी प्रीकंडीशनर प्रीकंडीशनिंग के सबसे सरल रूपों में से है, जिसमें प्रीकंडीशनर को आव्युह के विकर्ण के रूप में चुना जाता है <math> P = \mathrm{diag}(A).</math> यह मानते हुए <math>A_{ii} \neq 0, \forall i </math>, हम पाते हैं <math>P^{-1}_{ij} = \frac{\delta_{ij}}{A_{ij}}.</math> यह विकर्ण रूप से प्रभावी आव्युह के लिए कुशल है <math> A</math>. इसका उपयोग बीम समस्याओं या 1-डी समस्याओं के लिए विश्लेषण सॉफ़्टवेयर में किया जाता है (उदाहरण:- STAAD PRO)
जैकोबी प्रीकंडीशनर प्रीकंडीशनिंग के सबसे सरल रूपों में से है, जिसमें प्रीकंडीशनर को आव्युह <math> P = \mathrm{diag}(A).                                                                                                                                                                                       </math> के विकर्ण के रूप में चुना जाता है यह मानते हुए <math>A_{ii} \neq 0, \forall i </math>, हम <math>P^{-1}_{ij} = \frac{\delta_{ij}}{A_{ij}}.                                                                                                                                                                   </math> पाते हैं यह विकर्ण रूप से प्रभावी आव्युह <math> A</math> के लिए कुशल है. इसका उपयोग बीम समस्याओं या 1-D समस्याओं के लिए विश्लेषण सॉफ़्टवेयर में किया जाता है (उदाहरण:- स्टैड प्रो)


====एसपीएआई====
====एसपीएआई====
विरल अनुमानित व्युत्क्रम प्रीकंडीशनर न्यूनतम करता है <math>\|AT-I\|_F,</math> कहाँ <math>\|\cdot\|_F</math> [[फ्रोबेनियस मानदंड]] है और <math>T = P^{-1}</math> विरल आव्यूहों के कुछ उपयुक्त रूप से सीमित सेट से है। फ्रोबेनियस मानदंड के तहत, यह कई स्वतंत्र न्यूनतम-वर्ग समस्याओं (प्रत्येक स्तम्भ के लिए एक) को हल करने में कम हो जाता है। में प्रविष्टियाँ <math>T</math> इसे कुछ विरलता पैटर्न तक ही सीमित रखा जाना चाहिए अन्यथा समस्या उतनी ही कठिन और समय लेने वाली बनी रहेगी जितनी इसका सटीक व्युत्क्रम खोजना <math>A</math>. यह विधि एम.जे. ग्रोट और टी. हकल द्वारा विरल पैटर्न के चयन के दृष्टिकोण के साथ पेश की गई थी।<ref>{{cite journal |first=M. J. |last=Grote |first2=T. |last2=Huckle |name-list-style=amp |year=1997 |title=विरल अनुमानित व्युत्क्रमों के साथ समानांतर प्रीकंडीशनिंग|journal=[[SIAM Journal on Scientific Computing]] |volume=18 |issue=3 |pages=838–53 |doi=10.1137/S1064827594276552 }}</ref>
विरल अनुमानित व्युत्क्रम प्रीकंडीशनर <math>\|AT-I\|_F,</math> को न्यूनतम करता है, जहाँ <math>\|\cdot\|_F</math> [[फ्रोबेनियस मानदंड]] है और <math>T = P^{-1}</math> कुछ उपयुक्त रूप से सीमित समुच्चय से है। विरल आव्यूहों के फ्रोबेनियस मानदंड के तहत, यह अनेक स्वतंत्र न्यूनतम-वर्ग समस्याओं (प्रत्येक स्तम्भ के लिए एक) को हल करने में कम हो जाता है। <math>T</math> में प्रविष्टियाँ को कुछ विरलता पैटर्न तक ही सीमित रखा जाना चाहिए अन्यथा समस्या <math>A</math> के स्पष्ट व्युत्क्रम खोजना उतना ही कठिन और समय लेने वाली बनी रहेगी यह विधि एम.जे. ग्रोट और टी. हकल द्वारा विरल पैटर्न के चयन के दृष्टिकोण के साथ प्रस्तुत की गई थी।<ref>{{cite journal |first=M. J. |last=Grote |first2=T. |last2=Huckle |name-list-style=amp |year=1997 |title=विरल अनुमानित व्युत्क्रमों के साथ समानांतर प्रीकंडीशनिंग|journal=[[SIAM Journal on Scientific Computing]] |volume=18 |issue=3 |pages=838–53 |doi=10.1137/S1064827594276552 }}</ref>
 


==== अन्य प्रीकंडीशनर ====
==== अन्य प्रीकंडीशनर ====
Line 81: Line 80:
* [[क्रमिक अति-विश्राम]]
* [[क्रमिक अति-विश्राम]]
** [[सममित क्रमिक अति-विश्राम]]
** [[सममित क्रमिक अति-विश्राम]]
* मल्टीग्रिड विधि#मल्टीग्रिड प्रीकंडीशनिंग
* मल्टीग्रिड प्रीकंडीशनिंग


===बाहरी संबंध===
===बाहरी संबंध===
Line 88: Line 87:




== eigenvalue समस्याओं के लिए पूर्व शर्त ==
== आइजेनवैल्यू समस्याओं के लिए प्रीकंडीशनिंग ==
आइजेनवैल्यू समस्याओं को कई वैकल्पिक विधियों से तैयार किया जा सकता है, जिनमें से प्रत्येक की अपनी पूर्व नियम होती है। पारंपरिक प्रीकंडीशनिंग तथाकथित वर्णक्रमीय परिवर्तनों पर आधारित है। लक्षित आइगेनवैल्यू को (लगभग) जानते हुए, कोई संबंधित सजातीय रैखिक प्रणाली को हल करके संबंधित आइजेनसदिश की गणना कर सकता है, इस प्रकार रैखिक प्रणाली के लिए प्रीकंडीशनिंग का उपयोग करने की अनुमति मिलती है। अंत में, [[रेले भागफल]] के अनुकूलन के रूप में आइगेनवैल्यू समस्या को तैयार करने से दृश्य में पूर्वनिर्धारित अनुकूलन तकनीक आती है।<ref name="K98">{{Cite journal| title = Preconditioned eigensolvers - an oxymoron?| journal = [[Electronic Transactions on Numerical Analysis]]| volume = 7 | pages = 104–123| year = 1998| last1 = Knyazev | first1 = Andrew V. | url=http://etna.mcs.kent.edu/vol.7.1998/pp104-123.dir/ }}</ref>
आइजेनवैल्यू समस्याओं को अनेक वैकल्पिक विधियों से तैयार किया जा सकता है, जिनमें से प्रत्येक की अपनी पूर्व नियम होती है। पारंपरिक प्रीकंडीशनिंग तथाकथित वर्णक्रमीय परिवर्तनों पर आधारित है। लक्षित आइगेनवैल्यू को (लगभग) जानते हुए, कोई संबंधित सजातीय रैखिक प्रणाली को हल करके संबंधित आइजेनसदिश की गणना कर सकता है, इस प्रकार रैखिक प्रणाली के लिए प्रीकंडीशनिंग का उपयोग करने की अनुमति मिलती है। अंत में, [[रेले भागफल]] के अनुकूलन के रूप में आइगेनवैल्यू समस्या को तैयार करने से दृश्य में पूर्वनिर्धारित अनुकूलन तकनीक आती है।<ref name="K98">{{Cite journal| title = Preconditioned eigensolvers - an oxymoron?| journal = [[Electronic Transactions on Numerical Analysis]]| volume = 7 | pages = 104–123| year = 1998| last1 = Knyazev | first1 = Andrew V. | url=http://etna.mcs.kent.edu/vol.7.1998/pp104-123.dir/ }}</ref>




===वर्णक्रमीय परिवर्तन===
===वर्णक्रमीय परिवर्तन       ===
[[eigenvalue]] समस्या के लिए, रैखिक प्रणालियों के अनुरूप <math> Ax = \lambda x</math> किसी को आव्युह को बदलने का प्रलोभन हो सकता है <math>A</math> आव्युह के साथ <math>P^{-1}A</math> प्रीकंडीशनर का उपयोग करना <math>P</math>. हालाँकि, यह केवल तभी समझ में आता है जब [[eigenvectors]] की तलाश हो <math>A</math> और <math>P^{-1}A</math> समान हैं। यह वर्णक्रमीय परिवर्तनों का मामला है।
रैखिक प्रणालियों के अनुरूप [[eigenvalue|आइजेनवैल्यू]] समस्या <math> Ax = \lambda x</math> के लिए किसी को प्रीकंडीशनर <math>P</math> का उपयोग करके आव्युह <math>A</math> को आव्युह <math>P^{-1}A</math> के साथ परिवर्तन करने का प्रलोभन हो सकता है. चूँकि, यह केवल तभी समझ में आता है जब [[eigenvectors|आइजन्वेक्टर्स]] की तलाश होती है तब <math>A</math> और <math>P^{-1}A</math> समान हैं। यह वर्णक्रमीय परिवर्तनों का स्तिथि है।


सबसे लोकप्रिय वर्णक्रमीय परिवर्तन तथाकथित शिफ्ट-एंड-इनवर्ट परिवर्तन है, जहां किसी दिए गए स्केलर के लिए <math>\alpha</math>, जिसे शिफ्ट, मूल eigenvalue समस्या कहा जाता है <math> Ax = \lambda x</math> इसे शिफ्ट-एंड-इनवर्ट समस्या से परिवर्तित कर दिया गया है <math> (A-\alpha I)^{-1}x = \mu x</math>. आइजेनसदिश संरक्षित हैं, और कोई पुनरावृत्त सॉल्वर, जैसे, पावर पुनरावृत्ति द्वारा शिफ्ट-एंड-इनवर्ट समस्या को हल कर सकता है। यह व्युत्क्रम पुनरावृत्ति देता है, जो सामान्यतः शिफ्ट के निकटतम ईजेनवैल्यू के अनुरूप, ईजेनसदिश में परिवर्तित हो जाता है <math>\alpha</math>. [[रेले भागफल पुनरावृत्ति]] परिवर्तनशील बदलाव के साथ शिफ्ट-एंड-इनवर्ट विधि है।
सबसे लोकप्रिय वर्णक्रमीय परिवर्तन तथाकथित शिफ्ट-एंड-इनवर्ट परिवर्तन है, जहां किसी दिए गए स्केलर <math>\alpha</math> के लिए, जिसे शिफ्ट कहा जाता है मूल आइजेनवैल्यू समस्या <math> Ax = \lambda x</math> को शिफ्ट-एंड-इनवर्ट समस्या <math> (A-\alpha I)^{-1}x = \mu x</math> से परिवर्तित कर दिया गया है. आइजेनसदिश संरक्षित हैं, और कोई पुनरावृत्त सॉल्वर, जैसे, पावर पुनरावृत्ति द्वारा शिफ्ट-एंड-इनवर्ट समस्या को हल कर सकता है। यह व्युत्क्रम पुनरावृत्ति देता है, जो सामान्यतः शिफ्ट <math>\alpha</math> के निकटतम ईजेनवैल्यू के अनुरूप, ईजेनवेक्टर में परिवर्तित हो जाता है . [[रेले भागफल पुनरावृत्ति]] परिवर्तनशील बदलाव के साथ शिफ्ट-एंड-इनवर्ट विधि है।


वर्णक्रमीय परिवर्तन eigenvalue समस्याओं के लिए विशिष्ट हैं और रैखिक प्रणालियों के लिए इसका कोई एनालॉग नहीं है। उन्हें सम्मिलित परिवर्तन की सटीक संख्यात्मक गणना की आवश्यकता होती है, जो बड़ी समस्याओं के लिए मुख्य बाधा बन जाती है।
वर्णक्रमीय परिवर्तन आइजेनवैल्यू समस्याओं के लिए विशिष्ट हैं और रैखिक प्रणालियों के लिए इसका कोई एनालॉग नहीं है। उन्हें सम्मिलित परिवर्तन की स्पष्ट संख्यात्मक गणना की आवश्यकता होती है, जो बड़ी समस्याओं के लिए मुख्य बाधा बन जाती है।


===सामान्य पूर्व शर्त===
===सामान्य प्रीकंडीशनिंग ===
रैखिक प्रणालियों से घनिष्ठ संबंध बनाने के लिए, आइए मान लें कि लक्षित eigenvalue <math>\lambda_\star</math> (लगभग) ज्ञात है। फिर कोई सजातीय रैखिक प्रणाली से संबंधित आइजनसदिश की गणना कर सकता है <math>(A-\lambda_\star I)x=0</math>. रैखिक प्रणालियों के लिए बाईं पूर्व नियम की अवधारणा का उपयोग करते हुए, हम प्राप्त करते हैं <math>T(A-\lambda_\star I)x=0</math>, कहाँ <math>T</math> प्रीकंडीशनर है, जिसे हम रिचर्डसन पुनरावृत्ति का उपयोग करके हल करने का प्रयास कर सकते हैं
रैखिक प्रणालियों से घनिष्ठ संबंध बनाने के लिए, आइए मान लें कि लक्षित आइजेनवैल्यू <math>\lambda_\star</math> (लगभग) ज्ञात है। फिर कोई सजातीय रैखिक प्रणाली <math>(A-\lambda_\star I)x=0</math> से संबंधित आइजनवेक्टर की गणना कर सकता है. रैखिक प्रणालियों के लिए बाईं पूर्व नियम की अवधारणा का उपयोग करते हुए, हम <math>T(A-\lambda_\star I)x=0</math> प्राप्त करते हैं, जहाँ <math>T</math> प्रीकंडीशनर है, जिसे हम रिचर्डसन पुनरावृत्ति का उपयोग करके हल करने का प्रयास कर सकते हैं


<math display="block">\mathbf{x}_{n+1} = \mathbf{x}_n-\gamma_n T(A-\lambda_\star I)\mathbf{x}_n,\ n \ge 0.</math>
<math display="block">\mathbf{x}_{n+1} = \mathbf{x}_n-\gamma_n T(A-\lambda_\star I)\mathbf{x}_n,\ n \ge 0.</math>




====आदर्श पूर्व शर्त<ref name="K98" />====
====आदर्श प्रीकंडीशनिंग <ref name="K98" />====
मूर-पेनरोज़ स्यूडोइनवर्स <math>T=(A-\lambda_\star I)^+</math> प्रीकंडीशनर है, जो ऊपर रिचर्डसन पुनरावृत्ति को चरण में अभिसरण बनाता है <math>\gamma_n=1</math>, तब से <math>I-(A-\lambda_\star I)^+(A-\lambda_\star I)</math>, द्वारा चिह्नित <math>P_\star</math>, ईजेनस्पेस पर ऑर्थोगोनल प्रोजेक्टर है, जो इसके अनुरूप है <math>\lambda_\star</math>. विकल्प <math>T=(A-\lambda_\star I)^+</math> तीन स्वतंत्र कारणों से अव्यावहारिक है। पहला, <math>\lambda_\star</math> वास्तव में ज्ञात नहीं है, हालाँकि इसे इसके सन्निकटन से बदला जा सकता है <math>\tilde\lambda_\star</math>. दूसरा, सटीक मूर-पेनरोज़ स्यूडोइनवर्स के लिए आइजेनसदिश के ज्ञान की आवश्यकता होती है, जिसे हम खोजने की कोशिश कर रहे हैं। जैकोबी-डेविडसन प्रीकंडीशनर के उपयोग से इसे कुछ हद तक टाला जा सकता है <math>T=(I-\tilde P_\star)(A-\tilde\lambda_\star I)^{-1}(I-\tilde P_\star)</math>, कहाँ <math>\tilde P_\star</math> अनुमानित <math>P_\star</math>. अंतिम, किन्तु कम महत्वपूर्ण नहीं, इस दृष्टिकोण के लिए पद्धति आव्युह के साथ रैखिक प्रणाली के सटीक संख्यात्मक समाधान की आवश्यकता होती है <math>(A-\tilde\lambda_\star I)</math>, जो बड़ी समस्याओं के लिए उपरोक्त शिफ्ट-एंड-इनवर्ट विधि जितनी महंगी हो जाती है। यदि समाधान पर्याप्त सटीक नहीं है, तो चरण दो निरर्थक हो सकता है।
मूर-पेनरोज़ स्यूडोइनवर्स <math>T=(A-\lambda_\star I)^+</math> प्रीकंडीशनर है, जो उपरोक्त रिचर्डसन पुनरावृत्ति को <math>\gamma_n=1</math> के साथ चरण में अभिसरण करता है, क्योंकि I-<math>I-(A-\lambda_\star I)^+(A-\lambda_\star I)</math>, जिसे <math>P_\star</math> द्वारा निरूपित किया जाता है, आइजेनस्पेस पर ऑर्थोगोनल प्रोजेक्टर है, जो <math>\lambda_\star</math> के अनुरूप है . विकल्प <math>T=(A-\lambda_\star I)^+</math> तीन स्वतंत्र कारणों से अव्यावहारिक है। सबसे पहले, <math>\lambda_\star</math> वास्तव में ज्ञात नहीं है, चूँकि इसे इसके सन्निकटन <math>\tilde\lambda_\star</math>से परिवर्तित किया जा सकता है। दूसरा, स्पष्ट मूर-पेनरोज़ स्यूडोइनवर्स के लिए आइजेनवेक्टर के ज्ञान की आवश्यकता होती है, जिसे हम खोजने की कोशिश कर रहे हैं। जैकोबी-डेविडसन प्रीकंडीशनर <math>T=(I-\tilde P_\star)(A-\tilde\lambda_\star I)^{-1}(I-\tilde P_\star)</math> <math>\tilde P_\star</math>के अनुमान के उपयोग से इसे कुछ सीमा तक टाला जा सकता है, जहां <math>P_\star</math> अनुमानित है अंतिम, किन्तु कम महत्वपूर्ण नहीं, इस दृष्टिकोण के लिए प्रणाली आव्युह <math>(A-\tilde\lambda_\star I)</math> के साथ रैखिक प्रणाली के स्पष्ट संख्यात्मक समाधान की आवश्यकता होती है, जो शिफ्ट-एंड-इनवर्ट जैसी बड़ी समस्याओं के लिए उतना ही मूल्यवान हो जाता है। उपरोक्त विधि. यदि समाधान पर्याप्त स्पष्ट नहीं है, तो चरण दो निरर्थक हो सकता है।


====व्यावहारिक पूर्व शर्त====
====व्यावहारिक प्रीकंडीशनिंग  ====
आइए सबसे पहले सैद्धांतिक मूल्य को प्रतिस्थापित करें <math>\lambda_\star</math> उपरोक्त रिचर्डसन पुनरावृत्ति में इसके वर्तमान सन्निकटन के साथ <math>\lambda_n</math> व्यावहारिक एल्गोरिदम प्राप्त करने के लिए
आइए सबसे पहले सैद्धांतिक मान <math>\lambda_\star</math> को प्रतिस्थापित करें उपरोक्त रिचर्डसन पुनरावृत्ति में इसके वर्तमान सन्निकटन के साथ <math>\lambda_n</math> व्यावहारिक एल्गोरिदम प्राप्त करने के लिए
<math display="block">\mathbf{x}_{n+1} = \mathbf{x}_n-\gamma_n T(A-\lambda_n I)\mathbf{x}_n,\ n \ge 0.</math>
<math display="block">\mathbf{x}_{n+1} = \mathbf{x}_n-\gamma_n T(A-\lambda_n I)\mathbf{x}_n,\ n \ge 0.</math>
लोकप्रिय विकल्प है <math>\lambda_n = \rho(x_n)</math> रेले भागफल फ़ंक्शन का उपयोग करना <math>\rho(\cdot)</math>. व्यावहारिक पूर्व-कंडीशनिंग केवल उपयोग करने जितनी ही तुच्छ हो सकती है <math>T=(\operatorname{diag}(A))^{-1}</math> या <math>T=(\operatorname{diag}(A-\lambda_n I))^{-1}.</math> eigenvalue समस्याओं के कुछ वर्गों के लिए की दक्षता <math>T\approx A^{-1}</math> संख्यात्मक और सैद्धांतिक दोनों रूप से प्रदर्शित किया गया है। विकल्प <math>T\approx A^{-1}</math> यह किसी को eigenvalue समस्याओं के लिए रैखिक प्रणालियों के लिए विकसित किए गए पूर्वकंडिशनरों की विशाल विविधता का आसानी से उपयोग करने की अनुमति देता है।
रेले भागफल फ़ंक्शन <math>\rho(\cdot)</math> का उपयोग करके एक लोकप्रिय विकल्प <math>\lambda_n = \rho(x_n)</math> है। व्यावहारिक पूर्व-कंडीशनिंग केवल <math>T=(\operatorname{diag}(A))^{-1}</math> या <math>T=(\operatorname{diag}(A-\lambda_n I))^{-1}.</math> का उपयोग करने जितनी ही तुच्छ हो सकती है,आइगेनवैल्यू समस्याओं के कुछ वर्गों के लिए संख्यात्मक और सैद्धांतिक रूप से <math>T\approx A^{-1}</math> की दक्षता प्रदर्शित की गई है। <math>T\approx A^{-1}</math> का विकल्प किसी को आइजेनवैल्यू समस्याओं के लिए रैखिक प्रणालियों के लिए विकसित पूर्वकंडिशनरों की विशाल विविधता का आसानी से उपयोग करने की अनुमति देता है।


बदलते मूल्य के कारण <math>\lambda_n</math>रेखीय प्रणालियों के मामले की तुलना में, व्यापक सैद्धांतिक अभिसरण विश्लेषण बहुत अधिक कठिन है, यहां तक ​​कि रिचर्डसन पुनरावृत्ति जैसे सबसे सरल विधियों के लिए भी।
परिवर्तित मान के कारण <math>\lambda_n</math>रेखीय प्रणालियों के स्तिथि की तुलना में, व्यापक सैद्धांतिक अभिसरण विश्लेषण बहुत अधिक कठिन है, यहां तक ​​कि रिचर्डसन पुनरावृत्ति जैसे सबसे सरल विधियों के लिए भी कठिन है।


===बाहरी संबंध===
===बाहरी संबंध===
* [http://www.cs.ucdavis.edu/~bai/ET/contents.html Templates for the Solution of Algebraic Eigenvalue Problems: a Practical Guide]
* [http://www.cs.ucdavis.edu/~bai/ET/contents.html Templates for the Solution of Algebraic आइजेनवैल्यू Problems: a Practical Guide]




== अनुकूलन में पूर्व शर्त ==
== अनुकूलन में प्रीकंडीशनिंग ==
[[File:gradient descent.png|thumb|right|350px|क्रमिक अवतरण का चित्रण]][[अनुकूलन (गणित)]] में, प्रीकंडीशनिंग का उपयोग सामान्यतः [[प्रथम-क्रम सन्निकटन]]|प्रथम-क्रम अनुकूलन (गणित) [[एल्गोरिदम]] को तेज करने के लिए किया जाता है।
[[File:gradient descent.png|thumb|right|350px|क्रमिक अवतरण का चित्रण]][[अनुकूलन (गणित)]] में, प्रीकंडीशनिंग का उपयोग सामान्यतः [[प्रथम-क्रम सन्निकटन]]| प्रथम-क्रम अनुकूलन (गणित) [[एल्गोरिदम]] को तेज करने के लिए किया जाता है।


=== विवरण ===
=== विवरण ===
उदाहरण के लिए, किसी वास्तविक-मूल्यवान फ़ंक्शन का [[स्थानीय न्यूनतम]] ज्ञात करना <math>F(\mathbf{x})</math> [[ ग्रेडियेंट |ग्रेडियेंट]] डिसेंट का उपयोग करते हुए, व्यक्ति ग्रेडिएंट के नकारात्मक के अनुपात में कदम उठाता है <math>-\nabla F(\mathbf{a})</math> वर्तमान बिंदु पर फ़ंक्शन का (या अनुमानित ग्रेडिएंट का):
उदाहरण के लिए, [[ ग्रेडियेंट |ग्रेडियेंट]] डिसेंट का उपयोग करते हुए किसी वास्तविक-मूल्यवान फ़ंक्शन <math>F(\mathbf{x})</math> का [[स्थानीय न्यूनतम]] ज्ञात करना, व्यक्ति ग्रेडिएंट <math>-\nabla F(\mathbf{a})</math> के ऋणात्मक के अनुपात में कदम उठाता है वर्तमान बिंदु पर फ़ंक्शन का (या अनुमानित ग्रेडिएंट का):
<math display="block">\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n \nabla F(\mathbf{x}_n),\ n \ge 0.</math>
<math display="block">\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n \nabla F(\mathbf{x}_n),\ n \ge 0.</math>
प्रीकंडीशनर को ग्रेडिएंट पर प्रयुक्त किया जाता है:
प्रीकंडीशनर को ग्रेडिएंट पर प्रयुक्त किया जाता है:
<math display="block">\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n P^{-1} \nabla F(\mathbf{x}_n),\ n \ge 0.</math>
<math display="block">\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n P^{-1} \nabla F(\mathbf{x}_n),\ n \ge 0.</math>
यहां प्रीकंडिशनिंग को लेवल सेट को सर्कल की तरह दिखने के लक्ष्य के साथ सदिश स्पेस की ज्यामिति को बदलने के रूप में देखा जा सकता है।<ref>{{cite book |first=David M. |last=Himmelblau |title=एप्लाइड नॉनलाइनियर प्रोग्रामिंग|location=New York |publisher=McGraw-Hill |year=1972 |isbn=0-07-028921-2 |pages=78–83 }}</ref> इस मामले में पूर्वनिर्धारित ढाल का लक्ष्य चित्र के अनुसार एक्स्ट्रेमा के बिंदु के करीब है, जो अभिसरण को गति देता है।
यहां प्रीकंडिशनिंग को लेवल समुच्चय को सर्कल की तरह दिखने के लक्ष्य के साथ सदिश स्पेस की ज्यामिति को परिवर्तन के रूप में देखा जा सकता है।<ref>{{cite book |first=David M. |last=Himmelblau |title=एप्लाइड नॉनलाइनियर प्रोग्रामिंग|location=New York |publisher=McGraw-Hill |year=1972 |isbn=0-07-028921-2 |pages=78–83 }}</ref> इस स्तिथि में पूर्वनिर्धारित स्लोप का लक्ष्य चित्र के अनुसार एक्स्ट्रेमा के बिंदु के समीप है, जो अभिसरण को गति देता है।


===रैखिक प्रणालियों से कनेक्शन===
===रैखिक प्रणालियों से कनेक्शन===
द्विघात फलन का न्यूनतम
द्विघात फलन का न्यूनतम
<math display="block">F(\mathbf{x}) = \tfrac{1}{2}\mathbf{x}^T A\mathbf{x}-\mathbf{x}^T\mathbf{b},</math>
<math display="block">F(\mathbf{x}) = \tfrac{1}{2}\mathbf{x}^T A\mathbf{x}-\mathbf{x}^T\mathbf{b},</math>
कहाँ <math>\mathbf{x}</math> और <math>\mathbf{b}</math> वास्तविक स्तम्भ-सदिश हैं और <math>A</math> वास्तविक सममित आव्युह धनात्मक -निश्चित आव्युह है, बिल्कुल रैखिक समीकरण का समाधान है <math>A\mathbf{x} = \mathbf{b}</math>. तब से <math>\nabla F(\mathbf{x}) = A\mathbf{x}-\mathbf{b}</math>, न्यूनतम करने की पूर्वनिर्धारित ग्रेडिएंट डिसेंट विधि <math>F(\mathbf{x})</math> है
जहाँ <math>\mathbf{x}</math> और <math>\mathbf{b}</math> वास्तविक स्तम्भ-सदिश हैं और <math>A</math> वास्तविक सममित आव्युह धनात्मक-निश्चित आव्युह है, बिल्कुल रैखिक समीकरण <math>A\mathbf{x} = \mathbf{b}</math> का समाधान है. तब से <math>\nabla F(\mathbf{x}) = A\mathbf{x}-\mathbf{b}</math>, को न्यूनतम करने की पूर्वनिर्धारित ग्रेडिएंट डिसेंट विधि <math>F(\mathbf{x})</math> है
<math display="block">\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n P^{-1}(A\mathbf{x}_n-\mathbf{b}),\ n \ge 0.</math>
<math display="block">\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n P^{-1}(A\mathbf{x}_n-\mathbf{b}),\ n \ge 0.</math>
यह रैखिक समीकरणों की प्रणाली को हल करने के लिए पूर्वनिर्धारित रिचर्डसन पुनरावृत्ति है।
यह रैखिक समीकरणों की प्रणाली को हल करने के लिए पूर्वनिर्धारित रिचर्डसन पुनरावृत्ति है।
Line 140: Line 139:
रेले भागफल का न्यूनतम
रेले भागफल का न्यूनतम
<math display="block">\rho(\mathbf{x})= \frac{\mathbf{x}^TA\mathbf{x}}{\mathbf{x}^T\mathbf{x}},</math>
<math display="block">\rho(\mathbf{x})= \frac{\mathbf{x}^TA\mathbf{x}}{\mathbf{x}^T\mathbf{x}},</math>
कहाँ <math>\mathbf{x}</math> वास्तविक गैर-शून्य स्तम्भ-सदिश है और <math>A</math> वास्तविक सममित आव्युह धनात्मक -निश्चित आव्युह है, इसका सबसे छोटा eigenvalue है <math>A</math>, जबकि मिनिमाइज़र संगत [[eigenvector]] है। तब से <math>\nabla \rho(\mathbf{x})</math> के लिए आनुपातिक है <math>A\mathbf{x}-\rho(\mathbf{x})\mathbf{x}</math>, न्यूनतम करने की पूर्वनिर्धारित ग्रेडिएंट डिसेंट विधि <math>\rho(\mathbf{x})</math> है
जहाँ <math>\mathbf{x}</math> वास्तविक गैर-शून्य स्तम्भ-सदिश है और <math>A</math> वास्तविक सममित आव्युह धनात्मक -निश्चित आव्युह है, इसका सबसे छोटा आइजेनवैल्यू है <math>A</math>, जबकि मिनिमाइज़र संगत [[eigenvector|आइजन्वेक्टर]] है। तब से <math>\nabla \rho(\mathbf{x})</math> के लिए आनुपातिक है तथा<math>A\mathbf{x}-\rho(\mathbf{x})\mathbf{x}</math>, को न्यूनतम करने की पूर्वनिर्धारित ग्रेडिएंट डिसेंट विधि <math>\rho(\mathbf{x})</math> है
<math display="block">\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n P^{-1}(A\mathbf{x}_n-\rho(\mathbf{x_n})\mathbf{x_n}),\ n \ge 0.</math>
<math display="block">\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n P^{-1}(A\mathbf{x}_n-\rho(\mathbf{x_n})\mathbf{x_n}),\ n \ge 0.</math>
यह eigenvalue समस्याओं को हल करने के लिए पूर्वनिर्धारित रिचर्डसन पुनरावृत्ति का एनालॉग है।
यह आइजेनवैल्यू समस्याओं को हल करने के लिए पूर्वनिर्धारित रिचर्डसन पुनरावृत्ति का एनालॉग है।


=== परिवर्तनीय पूर्व शर्त ===
=== परिवर्तनीय प्रीकंडीशनिंग ===
कई स्तिथियों में, स्तर सेट के बदलते आकार को समायोजित करने के लिए [[पुनरावृत्त एल्गोरिदम]] के कुछ या यहां तक ​​कि हर चरण पर प्रीकंडीशनर को बदलना लाभदायक हो सकता है, जैसा कि
अनेक स्तिथियों में, स्तर समुच्चय के परिवर्तित होते हुए आकार को समायोजित करने के लिए [[पुनरावृत्त एल्गोरिदम]] के कुछ या यहां तक ​​कि हर चरण पर प्रीकंडीशनर का परिवर्तन लाभदायक हो सकता है, जैसा कि
<math display="block">\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n P_n^{-1} \nabla F(\mathbf{x}_n),\ n \ge 0.</math>
<math display="block">\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n P_n^{-1} \nabla F(\mathbf{x}_n),\ n \ge 0.</math>
हालाँकि, किसी को यह ध्यान में रखना चाहिए कि कुशल प्रीकंडीशनर का निर्माण अधिकांशतः कम्प्यूटेशनल रूप से महंगा होता है। प्रीकंडीशनर को अपडेट करने की बढ़ी हुई लागत तेजी से अभिसरण के धनात्मक प्रभाव को आसानी से खत्म कर सकती है। अगर <math>P_n^{-1} = H_n</math>, व्युत्क्रम हेसियन आव्युह का ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शैनो एल्गोरिदम सन्निकटन, इस विधि को क्वासी-न्यूटन विधि के रूप में जाना जाता है।
 
 
चूँकि, किसी को यह ध्यान में रखना चाहिए कि कुशल प्रीकंडीशनर का निर्माण अधिकांशतः कम्प्यूटेशनल रूप से मूल्यवान होता है। तथा प्रीकंडीशनर को अपडेट करने की बढ़ी हुई निवेश तेजी से अभिसरण के धनात्मक प्रभाव को आसानी से खत्म कर सकती है। यदि <math>P_n^{-1} = H_n</math>,है तब व्युत्क्रम हेसियन आव्युह का ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शैनो एल्गोरिदम सन्निकटन की इस विधि को क्वासी-न्यूटन विधि के रूप में जाना जाता है।


==संदर्भ==
==संदर्भ==
Line 170: Line 171:
श्रेणी:संख्यात्मक रैखिक बीजगणित
श्रेणी:संख्यात्मक रैखिक बीजगणित


 
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category: Machine Translated Page]]
[[Category:Collapse templates]]
[[Category:Created On 09/08/2023]]
[[Category:Created On 09/08/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Missing redirects]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]

Latest revision as of 16:06, 22 August 2023

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

रैखिक प्रणालियों के लिए पूर्व नियम

रैखिक बीजगणित और संख्यात्मक विश्लेषण में, आव्युह का प्रीकंडीशनर आव्युह ऐसा है जैसे कि की स्थिति संख्या से छोटी है।. इसे कहना भी सामान्य बात है के अतिरिक्त प्रीकंडीशनर, क्योंकि स्वयं शायद ही कभी स्पष्ट रूप से उपलब्ध होता है। आधुनिक प्रीकंडीशनिंग में, का अनुप्रयोग अर्थात, स्तम्भ सदिश, या स्तम्भ सदिश के ब्लॉक को से गुणा करना, सामान्यतः आव्युह-मुक्त विधियों में किया जाता है | आव्युह-मुक्त फैशन, अर्थात, जहां न तो , और न (और अधिकांशतः भी नहीं) आव्युह रूप में स्पष्ट रूप से उपलब्ध हैं।

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

विवरण

के लिए मूल रैखिक प्रणाली को हल करने के अतिरिक्त, कोई सही पूर्व नियम प्रणाली पर विचार कर सकता है

और हल करें
के लिए और
के लिए .

वैकल्पिक रूप से, कोई बाईं पूर्व नियम प्रणाली को हल कर सकता है

दोनों प्रणालियाँ मूल प्रणाली के समान ही समाधान देती हैं जब तक कि प्रीकंडीशनर आव्युह बीजगणितीय वक्र या विलक्षणता है। बाईं ओर की पूर्व नियम अधिक पारंपरिक है।

दो तरफा पूर्व नियम प्रणाली

यह लाभदायक हो सकता है, उदाहरण के लिए, आव्युह समरूपता को संरक्षित करने के लिए: यदि मूल आव्युह वास्तविक सममित है और वास्तविक प्रीकंडीशनर और संतुष्ट करते हैं तब फिर पूर्वनिर्धारित आव्युह सममित भी है. दो-तरफा प्रीकंडीशनर विकर्ण स्केलिंग के लिए सामान्य है जहां प्रीकंडीशनिंग और विकर्ण हैं और स्केलिंग मूल आव्युह के स्तंभों और पंक्तियों दोनों पर प्रयुक्त होती है, जहाँ उदाहरण के लिए, आव्युह की प्रविष्टियों की गतिशील सीमा को कम करने के लिए उपयोग किया जाता है।

प्रीकंडीशनिंग का लक्ष्य नियम संख्या को कम करना है, उदाहरण के लिए, बाएं या दाएं प्रीकंडिशनिंग पद्धति आव्युह या की छोटी स्थिति संख्याएं पुनरावृत्त सॉल्वरों के तेजी से अभिसरण का लाभ उठाती हैं और पद्धति आव्युह और दाईं ओर त्रुटी के संबंध में समाधान की स्थिरता में सुधार करती हैं, उदाहरण के लिए, कम परिशुद्धता (कंप्यूटर) का उपयोग करके आव्युह प्रविष्टियों के अधिक आक्रामक परिमाणीकरण (सिग्नल प्रोसेसिंग) विज्ञान की अनुमति देती है।

पूर्वनिर्धारित आव्युह या शायद ही कभी स्पष्ट रूप से गठित किया गया हो। किसी दिए गए सदिश पर केवल प्रीकंडीशनर सॉल्व ऑपरेशन को प्रयुक्त करने की क्रिया की गणना करने की आवश्यकता हो सकती है।

सामान्यतः चयन में समझौता होता है चूंकि ऑपरेटर को पुनरावृत्त रैखिक सॉल्वर के प्रत्येक चरण पर प्रयुक्त किया जाना चाहिए, इसीलिए इसे प्रयुक्त करने की छोटी निवेश (कंप्यूटिंग समय) होनी चाहिए संचालन। इसलिए सबसे सस्ता प्रीकंडीशनर होगा क्योंकि तब . स्पष्ट रूप से, इसका परिणाम मूल रैखिक प्रणाली में होता है और प्रीकंडीशनर कुछ नहीं करता है। दूसरे चरम पर, विकल्प देता है जिसकी इष्टतम स्थिति संख्या 1 है, अभिसरण के लिए एकल पुनरावृत्ति की आवश्यकता है; चूँकि इस स्तिथि में और प्रीकंडीशनर को प्रयुक्त करना मूल प्रणाली को हल करने जितना ही कठिन है। इसलिए, ऑपरेटर को यथासंभव सरल रखते हुए न्यूनतम संख्या में रैखिक पुनरावृत्तियों को प्राप्त करने के प्रयास में, इन दोनों चरम सीमाओं के मध्य में को चुना जाता है। विशिष्ट प्रीकंडीशनिंग दृष्टिकोण के कुछ उदाहरण नीचे विस्तृत हैं।

पूर्वनिर्धारित पुनरावृत्तीय विधियाँ

के लिए पूर्वनिर्धारित पुनरावृत्तीय विधियाँ अधिकांश स्तिथियों में, गणितीय रूप से पूर्वनिर्धारित प्रणाली पर प्रयुक्त मानक पुनरावृत्त विधियों के समान हैं उदाहरण के लिए, को हल करने के लिए मानक रिचर्डसन पुनरावृत्ति है

पूर्व नियम प्रणाली पर प्रयुक्त किया गया यह पूर्वनिर्धारित पद्धति में परिवर्तित हो जाता है

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

आव्युह विभाजन

इस प्रकार पुनरावृत्तीय विधि या स्थिर पुनरावृत्तीय विधियाँ आव्युह विभाजन और पुनरावृत्ति आव्युह द्वारा निर्धारित की जाती हैं . ये मानते हुए

  • पद्धति आव्युह सममित आव्युह है धनात्मक -निश्चित आव्युह| धनात्मक -निश्चित,
  • विभाजन आव्युह सममित आव्युह है धनात्मक -निश्चित आव्युह| धनात्मक -निश्चित,
  • स्थिर पुनरावृत्त विधि अभिसरण है, जैसा कि द्वारा निर्धारित किया गया है ,

नियम संख्या से ऊपर घिरा हुआ है


ज्यामितीय व्याख्या

सममित आव्युह धनात्मक -निश्चित आव्युह के लिए प्रीकंडीशनर को सामान्यतः सममित धनात्मक निश्चित होने के लिए भी चुना जाता है। प्रीकंडीशनर ऑपरेटर फिर भी सममित धनात्मक निश्चित है, किन्तु -आधारित अदिश उत्पाद के संबंध में। इस स्तिथि में, प्रीकंडीशनर को प्रयुक्त करने में वांछित प्रभाव -आधारित स्केलर उत्पाद के संबंध में प्रीकंडिशनर ऑपरेटर के द्विघात रूप को लगभग गोलाकार बनाना है।।[1]


परिवर्तनीय और गैर-रैखिक प्रीकंडीशनिंग

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

यादृच्छिक प्रीकंडीशनिंग

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

वर्णक्रमीय समतुल्य प्रीकंडीशनिंग

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

उदाहरण

जैकोबी (या विकर्ण) प्रीकंडीशनर

जैकोबी प्रीकंडीशनर प्रीकंडीशनिंग के सबसे सरल रूपों में से है, जिसमें प्रीकंडीशनर को आव्युह के विकर्ण के रूप में चुना जाता है यह मानते हुए , हम पाते हैं यह विकर्ण रूप से प्रभावी आव्युह के लिए कुशल है. इसका उपयोग बीम समस्याओं या 1-D समस्याओं के लिए विश्लेषण सॉफ़्टवेयर में किया जाता है (उदाहरण:- स्टैड प्रो)

एसपीएआई

विरल अनुमानित व्युत्क्रम प्रीकंडीशनर को न्यूनतम करता है, जहाँ फ्रोबेनियस मानदंड है और कुछ उपयुक्त रूप से सीमित समुच्चय से है। विरल आव्यूहों के फ्रोबेनियस मानदंड के तहत, यह अनेक स्वतंत्र न्यूनतम-वर्ग समस्याओं (प्रत्येक स्तम्भ के लिए एक) को हल करने में कम हो जाता है। में प्रविष्टियाँ को कुछ विरलता पैटर्न तक ही सीमित रखा जाना चाहिए अन्यथा समस्या के स्पष्ट व्युत्क्रम खोजना उतना ही कठिन और समय लेने वाली बनी रहेगी यह विधि एम.जे. ग्रोट और टी. हकल द्वारा विरल पैटर्न के चयन के दृष्टिकोण के साथ प्रस्तुत की गई थी।[3]

अन्य प्रीकंडीशनर

बाहरी संबंध


आइजेनवैल्यू समस्याओं के लिए प्रीकंडीशनिंग

आइजेनवैल्यू समस्याओं को अनेक वैकल्पिक विधियों से तैयार किया जा सकता है, जिनमें से प्रत्येक की अपनी पूर्व नियम होती है। पारंपरिक प्रीकंडीशनिंग तथाकथित वर्णक्रमीय परिवर्तनों पर आधारित है। लक्षित आइगेनवैल्यू को (लगभग) जानते हुए, कोई संबंधित सजातीय रैखिक प्रणाली को हल करके संबंधित आइजेनसदिश की गणना कर सकता है, इस प्रकार रैखिक प्रणाली के लिए प्रीकंडीशनिंग का उपयोग करने की अनुमति मिलती है। अंत में, रेले भागफल के अनुकूलन के रूप में आइगेनवैल्यू समस्या को तैयार करने से दृश्य में पूर्वनिर्धारित अनुकूलन तकनीक आती है।[4]


वर्णक्रमीय परिवर्तन

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

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

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

सामान्य प्रीकंडीशनिंग

रैखिक प्रणालियों से घनिष्ठ संबंध बनाने के लिए, आइए मान लें कि लक्षित आइजेनवैल्यू (लगभग) ज्ञात है। फिर कोई सजातीय रैखिक प्रणाली से संबंधित आइजनवेक्टर की गणना कर सकता है. रैखिक प्रणालियों के लिए बाईं पूर्व नियम की अवधारणा का उपयोग करते हुए, हम प्राप्त करते हैं, जहाँ प्रीकंडीशनर है, जिसे हम रिचर्डसन पुनरावृत्ति का उपयोग करके हल करने का प्रयास कर सकते हैं


आदर्श प्रीकंडीशनिंग [4]

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

व्यावहारिक प्रीकंडीशनिंग

आइए सबसे पहले सैद्धांतिक मान को प्रतिस्थापित करें उपरोक्त रिचर्डसन पुनरावृत्ति में इसके वर्तमान सन्निकटन के साथ व्यावहारिक एल्गोरिदम प्राप्त करने के लिए

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

परिवर्तित मान के कारण रेखीय प्रणालियों के स्तिथि की तुलना में, व्यापक सैद्धांतिक अभिसरण विश्लेषण बहुत अधिक कठिन है, यहां तक ​​कि रिचर्डसन पुनरावृत्ति जैसे सबसे सरल विधियों के लिए भी कठिन है।

बाहरी संबंध


अनुकूलन में प्रीकंडीशनिंग

क्रमिक अवतरण का चित्रण

अनुकूलन (गणित) में, प्रीकंडीशनिंग का उपयोग सामान्यतः प्रथम-क्रम सन्निकटन| प्रथम-क्रम अनुकूलन (गणित) एल्गोरिदम को तेज करने के लिए किया जाता है।

विवरण

उदाहरण के लिए, ग्रेडियेंट डिसेंट का उपयोग करते हुए किसी वास्तविक-मूल्यवान फ़ंक्शन का स्थानीय न्यूनतम ज्ञात करना, व्यक्ति ग्रेडिएंट के ऋणात्मक के अनुपात में कदम उठाता है वर्तमान बिंदु पर फ़ंक्शन का (या अनुमानित ग्रेडिएंट का):

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

रैखिक प्रणालियों से कनेक्शन

द्विघात फलन का न्यूनतम

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

आइजेनवैल्यू समस्याओं से कनेक्शन

रेले भागफल का न्यूनतम

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

परिवर्तनीय प्रीकंडीशनिंग

अनेक स्तिथियों में, स्तर समुच्चय के परिवर्तित होते हुए आकार को समायोजित करने के लिए पुनरावृत्त एल्गोरिदम के कुछ या यहां तक ​​कि हर चरण पर प्रीकंडीशनर का परिवर्तन लाभदायक हो सकता है, जैसा कि


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

संदर्भ

  1. Shewchuk, Jonathan Richard (August 4, 1994). "कष्टकारी दर्द के बिना संयुग्मित ग्रेडिएंट विधि का परिचय" (PDF).
  2. Henricus Bouwmeester, Andrew Dougherty, Andrew V Knyazev. Nonsymmetric Preconditioning for Conjugate Gradient and Steepest Descent Methods. Procedia Computer Science, Volume 51, Pages 276-285, Elsevier, 2015. https://doi.org/10.1016/j.procs.2015.05.241
  3. Grote, M. J. & Huckle, T. (1997). "विरल अनुमानित व्युत्क्रमों के साथ समानांतर प्रीकंडीशनिंग". SIAM Journal on Scientific Computing. 18 (3): 838–53. doi:10.1137/S1064827594276552.
  4. 4.0 4.1 Knyazev, Andrew V. (1998). "Preconditioned eigensolvers - an oxymoron?". Electronic Transactions on Numerical Analysis. 7: 104–123.
  5. Himmelblau, David M. (1972). एप्लाइड नॉनलाइनियर प्रोग्रामिंग. New York: McGraw-Hill. pp. 78–83. ISBN 0-07-028921-2.


स्रोत


श्रेणी:संख्यात्मक रैखिक बीजगणित