प्रीकंडीशनर: Difference between revisions
From Vigyanwiki
(Created page with "{{Short description|Transforms equations for numerical solution}} {{redirect|Preconditioning}} {{more footnotes needed|date=February 2013}} गणित में, प्र...") |
No edit summary |
||
| (8 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Transforms equations for numerical solution}} | {{Short description|Transforms equations for numerical solution}} | ||
{{redirect| | {{redirect|प्रीकंडीशनिंग}} | ||
गणित में, प्रीकंडीशनिंग परिवर्तन का अनुप्रयोग है, जिसे '''प्रीकंडीशनर''' कहा जाता है, जो किसी दी गई समस्या को ऐसे रूप में प्रस्तुत करता है जो [[संख्यात्मक गणित]] को हल करने के विधियों के लिए अधिक उपयुक्त है। प्रीकंडीशनिंग सामान्यतः समस्या की स्थिति संख्या को कम करने से संबंधित है। पूर्वनिर्धारित समस्या को सामान्यतः पुनरावृत्तीय विधि द्वारा हल किया जाता है। | |||
== रैखिक प्रणालियों के लिए पूर्व नियम == | |||
प्रीकंडीशनर | रैखिक बीजगणित और [[संख्यात्मक विश्लेषण]] में, आव्युह <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 display="block"> AP^{-1}(Px) = b</math> | <math display="block"> AP^{-1}(Px) = b</math> | ||
और हल करें | और हल करें | ||
<math display="block">AP^{-1}y=b</math> | <math display="block">AP^{-1}y=b</math> | ||
<math>y</math> के लिए और | |||
<math display="block">Px = y</math> | <math display="block">Px = y</math> | ||
<math>x</math> के लिए . | |||
वैकल्पिक रूप से, कोई बाईं पूर्व | वैकल्पिक रूप से, कोई बाईं पूर्व नियम प्रणाली को हल कर सकता है | ||
<math display="block"> P^{-1}(Ax-b)=0 .</math> | <math display="block"> P^{-1}(Ax-b)=0 .</math> | ||
दोनों प्रणालियाँ मूल प्रणाली के समान ही समाधान देती हैं जब तक कि प्रीकंडीशनर | दोनों प्रणालियाँ मूल प्रणाली के समान ही समाधान देती हैं जब तक कि प्रीकंडीशनर आव्युह <math>P</math> बीजगणितीय वक्र या विलक्षणता है। बाईं ओर की पूर्व नियम अधिक पारंपरिक है। | ||
दो तरफा पूर्व | दो तरफा पूर्व नियम प्रणाली | ||
<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>P^{-1}A</math> या <math>AP^{-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>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 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> | ||
रैखिक प्रणालियों के लिए लोकप्रिय पूर्वनिर्धारित पुनरावृत्त | रैखिक प्रणालियों के लिए लोकप्रिय पूर्वनिर्धारित पुनरावृत्त विधियों के उदाहरणों में पूर्वनिर्धारित संयुग्म ग्रेडिएंट विधि, द्विसंयुग्म ग्रेडिएंट विधि और [[सामान्यीकृत न्यूनतम अवशिष्ट विधि]] सम्मिलित हैं। पुनरावृत्तीय विधियाँ, जो पुनरावृत्तीय मापदंडों की गणना करने के लिए अदिश उत्पादों का उपयोग करती हैं, उन्हें <math>Ax-b = 0. </math>के स्थान पर <math>P^{-1}(Ax-b) = 0 </math> को प्रतिस्थापन करने के साथ-साथ अदिश उत्पाद में संगत परिवर्तनों की आवश्यकता होती है | ||
==== | ==== आव्युह विभाजन ==== | ||
इस प्रकार पुनरावृत्तीय विधि या स्थिर पुनरावृत्तीय विधियाँ आव्युह विभाजन <math> A=M-N </math> और पुनरावृत्ति आव्युह <math> C=I-M^{-1}A </math> द्वारा निर्धारित की जाती हैं . ये मानते हुए | |||
* | * पद्धति आव्युह <math> A </math> [[सममित मैट्रिक्स|सममित]] आव्युह है [[सकारात्मक-निश्चित मैट्रिक्स|धनात्मक -निश्चित आव्युह]]| धनात्मक -निश्चित, | ||
*विभाजन | *विभाजन आव्युह <math> M </math> सममित आव्युह है धनात्मक -निश्चित आव्युह| धनात्मक -निश्चित, | ||
* स्थिर पुनरावृत्त विधि अभिसरण है, जैसा कि | * स्थिर पुनरावृत्त विधि अभिसरण है, जैसा कि <math> \rho(C) < 1 </math> द्वारा निर्धारित किया गया है , | ||
नियम संख्या <math> \kappa(M^{-1}A) </math> से ऊपर घिरा हुआ है | |||
<math display="block"> | <math display="block"> | ||
\kappa(M^{-1}A) \leq \frac{1+\rho(C)}{1-\rho(C)} \,. | \kappa(M^{-1}A) \leq \frac{1+\rho(C)}{1-\rho(C)} \,. | ||
| Line 54: | 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 87: | 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> | ||
===वर्णक्रमीय परिवर्तन=== | ===वर्णक्रमीय परिवर | ||