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

रैखिक बीजगणित और [[संख्यात्मक विश्लेषण]] में, आव्युह <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>y</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</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>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>

=== यादृच्छिक पूर्व शर्त ===

वैरिएबल प्रीकंडीशनिंग का दिलचस्प विशेष मामला रैंडम प्रीकंडिशनिंग है, उदाहरण के लिए, रैंडम कोर्स ग्रिड पर [[मल्टीग्रिड]] प्रीकंडिशनिंग।<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>\|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>

 

* मल्टीग्रिड विधि#मल्टीग्रिड प्रीकंडीशनिंग

== 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>

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

[[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> समान हैं। यह वर्णक्रमीय परिवर्तनों का मामला है।

सबसे लोकप्रिय वर्णक्रमीय परिवर्तन तथाकथित शिफ्ट-एंड-इनवर्ट परिवर्तन है, जहां किसी दिए गए स्केलर के लिए <math>\alpha</math>, जिसे शिफ्ट, मूल eigenvalue समस्या कहा जाता है <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> प्रीकंडीशनर है, जिसे हम रिचर्डसन पुनरावृत्ति का उपयोग करके हल करने का प्रयास कर सकते हैं

====आदर्श पूर्व शर्त<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>\lambda_\star</math> उपरोक्त रिचर्डसन पुनरावृत्ति में इसके वर्तमान सन्निकटन के साथ <math>\lambda_n</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 समस्याओं के लिए रैखिक प्रणालियों के लिए विकसित किए गए पूर्वकंडिशनरों की विशाल विविधता का आसानी से उपयोग करने की अनुमति देता है।