प्रीकंडीशनर: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 32: | Line 32: | ||
पूर्वनिर्धारित आव्युह <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</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</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>r</math> पर कार्य करने वाले ऑपरेटर <math>T(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> 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-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> | ||
==== अन्य प्रीकंडीशनर ==== | ==== अन्य प्रीकंडीशनर ==== | ||
| Line 81: | Line 80: | ||
* [[क्रमिक अति-विश्राम]] | * [[क्रमिक अति-विश्राम]] | ||
** [[सममित क्रमिक अति-विश्राम]] | ** [[सममित क्रमिक अति-विश्राम]] | ||
* | * मल्टीग्रिड प्रीकंडीशनिंग | ||
===बाहरी संबंध=== | ===बाहरी संबंध=== | ||
| Line 88: | Line 87: | ||
== | == आइजेनवैल्यू समस्याओं के लिए प्रीकंडीशनिंग == | ||
आइजेनवैल्यू समस्याओं को | आइजेनवैल्यू समस्याओं को अनेक वैकल्पिक विधियों से तैयार किया जा सकता है, जिनमें से प्रत्येक की अपनी पूर्व नियम होती है। पारंपरिक प्रीकंडीशनिंग तथाकथित वर्णक्रमीय परिवर्तनों पर आधारित है। लक्षित आइगेनवैल्यू को (लगभग) जानते हुए, कोई संबंधित सजातीय रैखिक प्रणाली को हल करके संबंधित आइजेनसदिश की गणना कर सकता है, इस प्रकार रैखिक प्रणाली के लिए प्रीकंडीशनिंग का उपयोग करने की अनुमति मिलती है। अंत में, [[रेले भागफल]] के अनुकूलन के रूप में आइगेनवैल्यू समस्या को तैयार करने से दृश्य में पूर्वनिर्धारित अनुकूलन तकनीक आती है।<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]] समस्या | रैखिक प्रणालियों के अनुरूप [[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> के लिए, जिसे शिफ्ट कहा जाता है मूल आइजेनवैल्यू समस्या <math> Ax = \lambda x</math> को शिफ्ट-एंड-इनवर्ट समस्या <math> (A-\alpha I)^{-1}x = \mu x</math> से परिवर्तित कर दिया गया है. आइजेनसदिश संरक्षित हैं, और कोई पुनरावृत्त सॉल्वर, जैसे, पावर पुनरावृत्ति द्वारा शिफ्ट-एंड-इनवर्ट समस्या को हल कर सकता है। यह व्युत्क्रम पुनरावृत्ति देता है, जो सामान्यतः शिफ्ट <math>\alpha</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" />==== | ||
मूर-पेनरोज़ स्यूडोइनवर्स <math>T=(A-\lambda_\star I)^+</math> प्रीकंडीशनर है, जो | |||