प्रीकंडीशनर: Difference between revisions
No edit summary |
No edit summary |
||
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</math> ऑपरेटर को बनाए रखते हुए न्यूनतम संख्या में रैखिक पुनरावृत्तियों को प्राप्त करने के प्रयास में, इन दो चरम सीमाओं के बीच कहीं <math>P^{-1}</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 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>P^{-1}(Ax-b) = 0</math> के लिए <math>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> \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 53: | 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>T = P^{-1}</math>, हम इस बात पर प्रकाश डालते हैं कि प्रीकंडीशनिंग को व्यावहारिक रूप से कुछ | दर्शाने <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> रैखिक नहीं हो सकता. विशिष्ट उदाहरणों में प्रीकंडीशनर निर्माण के भाग के रूप में गैर-रेखीय पुनरावृत्त विधियों का उपयोग करना शामिल है, उदाहरण के लिए, संयुग्म ग्रेडिएंट विधि। ऐसे प्रीकंडीशनर व्यावहारिक रूप से बहुत कुशल हो सकते हैं, हालांकि, सैद्धांतिक रूप से उनके व्यवहार की भविष्यवाणी करना कठिन है। | ||
=== यादृच्छिक पूर्व शर्त === | === यादृच्छिक पूर्व शर्त === | ||
Line 63: | Line 64: | ||
===वर्णक्रमीय समतुल्य पूर्व शर्त=== | ===वर्णक्रमीय समतुल्य पूर्व शर्त=== | ||
प्रीकंडीशनिंग का सबसे आम उपयोग [[आंशिक अंतर समीकरण]]ों के अनुमान के परिणामस्वरूप रैखिक प्रणालियों के पुनरावृत्त समाधान के लिए है। सन्निकटन गुणवत्ता जितनी | प्रीकंडीशनिंग का सबसे आम उपयोग [[आंशिक अंतर समीकरण]]ों के अनुमान के परिणामस्वरूप रैखिक प्रणालियों के पुनरावृत्त समाधान के लिए है। सन्निकटन गुणवत्ता जितनी उत्तम होगी, आव्युह का आकार उतना ही बड़ा होगा। ऐसे मामले में, इष्टतम प्रीकंडीशनिंग का लक्ष्य, तरफ, वर्णक्रमीय स्थिति संख्या बनाना है <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>\|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 88: | ||
== eigenvalue समस्याओं के लिए पूर्व शर्त == | == 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> किसी को | एक [[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 समस्या कहा जाता है <math> Ax = \lambda x</math> इसे शिफ्ट-एंड-इनवर्ट समस्या से बदल दिया गया है <math> (A-\alpha I)^{-1}x = \mu x</math>. आइजेनसदिश संरक्षित हैं, और कोई पुनरावृत्त सॉल्वर, जैसे, पावर पुनरावृत्ति द्वारा शिफ्ट-एंड-इनवर्ट समस्या को हल कर सकता है। यह व्युत्क्रम पुनरावृत्ति देता है, जो सामान्यतः शिफ्ट के निकटतम ईजेनवैल्यू के अनुरूप, ईजेनसदिश में परिवर्तित हो जाता है <math>\alpha</math>. [[रेले भागफल पुनरावृत्ति]] परिवर्तनशील बदलाव के साथ शिफ्ट-एंड-इनवर्ट विधि है। | ||
वर्णक्रमीय परिवर्तन eigenvalue समस्याओं के लिए विशिष्ट हैं और रैखिक प्रणालियों के लिए इसका कोई एनालॉग नहीं है। उन्हें शामिल परिवर्तन की सटीक संख्यात्मक गणना की आवश्यकता होती है, जो बड़ी समस्याओं के लिए मुख्य बाधा बन जाती है। | वर्णक्रमीय परिवर्तन eigenvalue समस्याओं के लिए विशिष्ट हैं और रैखिक प्रणालियों के लिए इसका कोई एनालॉग नहीं है। उन्हें शामिल परिवर्तन की सटीक संख्यात्मक गणना की आवश्यकता होती है, जो बड़ी समस्याओं के लिए मुख्य बाधा बन जाती है। | ||
===सामान्य पूर्व शर्त=== | ===सामान्य पूर्व शर्त=== | ||
रैखिक प्रणालियों से घनिष्ठ संबंध बनाने के लिए, आइए मान लें कि लक्षित eigenvalue <math>\lambda_\star</math> (लगभग) ज्ञात है। फिर कोई सजातीय रैखिक प्रणाली से संबंधित | रैखिक प्रणालियों से घनिष्ठ संबंध बनाने के लिए, आइए मान लें कि लक्षित 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 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> | ||
Line 104: | Line 105: | ||
====आदर्श पूर्व शर्त<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=(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>, जो बड़ी समस्याओं के लिए उपरोक्त शिफ्ट-एंड-इनवर्ट विधि जितनी महंगी हो जाती है। यदि समाधान पर्याप्त सटीक नहीं है, तो चरण दो निरर्थक हो सकता है। | ||
====व्यावहारिक पूर्व शर्त==== | ====व्यावहारिक पूर्व शर्त==== | ||
Line 111: | Line 112: | ||
एक लोकप्रिय विकल्प है <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>\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>\lambda_n</math>रेखीय प्रणालियों के मामले की तुलना में, व्यापक सैद्धांतिक अभिसरण विश्लेषण बहुत अधिक कठिन है, यहां तक कि रिचर्डसन पुनरावृत्ति जैसे सबसे सरल | बदलते मूल्य के कारण <math>\lambda_n</math>रेखीय प्रणालियों के मामले की तुलना में, व्यापक सैद्धांतिक अभिसरण विश्लेषण बहुत अधिक कठिन है, यहां तक कि रिचर्डसन पुनरावृत्ति जैसे सबसे सरल विधियों के लिए भी। | ||
===बाहरी संबंध=== | ===बाहरी संबंध=== | ||
Line 118: | Line 119: | ||
== अनुकूलन में पूर्व शर्त == | == अनुकूलन में पूर्व शर्त == | ||
[[File:gradient descent.png|thumb|right|350px|क्रमिक अवतरण का चित्रण]][[अनुकूलन (गणित)]] में, प्रीकंडीशनिंग का उपयोग | [[File:gradient descent.png|thumb|right|350px|क्रमिक अवतरण का चित्रण]][[अनुकूलन (गणित)]] में, प्रीकंडीशनिंग का उपयोग सामान्यतः [[प्रथम-क्रम सन्निकटन]]|प्रथम-क्रम अनुकूलन (गणित) [[एल्गोरिदम]] को तेज करने के लिए किया जाता है। | ||
=== विवरण === | === विवरण === | ||
Line 125: | Line 126: | ||
प्रीकंडीशनर को ग्रेडिएंट पर लागू किया जाता है: | प्रीकंडीशनर को ग्रेडिएंट पर लागू किया जाता है: | ||
<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> इस मामले में पूर्वनिर्धारित ढाल का लक्ष्य चित्र के अनुसार एक्स्ट्रेमा के बिंदु के करीब है, जो अभिसरण को गति देता है। | ||
===रैखिक प्रणालियों से कनेक्शन=== | ===रैखिक प्रणालियों से कनेक्शन=== | ||
द्विघात फलन का न्यूनतम | द्विघात फलन का न्यूनतम | ||
<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>\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 138: | 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>\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 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 समस्याओं को हल करने के लिए पूर्वनिर्धारित रिचर्डसन पुनरावृत्ति का एनालॉग है। | यह eigenvalue समस्याओं को हल करने के लिए पूर्वनिर्धारित रिचर्डसन पुनरावृत्ति का एनालॉग है। | ||
Line 145: | Line 146: | ||
कई मामलों में, स्तर सेट के बदलते आकार को समायोजित करने के लिए [[पुनरावृत्त एल्गोरिदम]] के कुछ या यहां तक कि हर चरण पर प्रीकंडीशनर को बदलना फायदेमंद हो सकता है, जैसा कि | कई मामलों में, स्तर सेट के बदलते आकार को समायोजित करने के लिए [[पुनरावृत्त एल्गोरिदम]] के कुछ या यहां तक कि हर चरण पर प्रीकंडीशनर को बदलना फायदेमंद हो सकता है, जैसा कि | ||
<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>, व्युत्क्रम हेसियन आव्युह का ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शैनो एल्गोरिदम सन्निकटन, इस विधि को क्वासी-न्यूटन विधि के रूप में जाना जाता है। | ||
==संदर्भ== | ==संदर्भ== |
Revision as of 13:14, 13 August 2023
गणित में, प्रीकंडीशनिंग परिवर्तन का अनुप्रयोग है, जिसे प्रीकंडीशनर कहा जाता है, जो किसी दी गई समस्या को ऐसे रूप में प्रस्तुत करता है जो संख्यात्मक गणित को हल करने के विधियों के लिए अधिक उपयुक्त है। प्रीकंडीशनिंग सामान्यतः समस्या की स्थिति संख्या को कम करने से संबंधित है। पूर्वनिर्धारित समस्या को सामान्यतः पुनरावृत्तीय विधि द्वारा हल किया जाता है।
रैखिक प्रणालियों के लिए पूर्व नियम
रैखिक बीजगणित और संख्यात्मक विश्लेषण में, आव्युह का प्रीकंडीशनर आव्युह ऐसा है जैसे कि की स्थिति संख्या से छोटी है।. इसे कहना भी सामान्य बात है के अतिरिक्त प्रीकंडीशनर, क्योंकि स्वयं शायद ही कभी स्पष्ट रूप से उपलब्ध होता है। आधुनिक प्रीकंडीशनिंग में, का अनुप्रयोग अर्थात, स्तम्भ सदिश, या स्तम्भ वैक्टर के ब्लॉक को से गुणा करना, सामान्यतः आव्युह-मुक्त विधियों में किया जाता है | आव्युह-मुक्त फैशन, अर्थात, जहां न तो , और न (और अधिकांशतः भी नहीं) आव्युह रूप में स्पष्ट रूप से उपलब्ध हैं।
प्रीकंडीशनर के लिए रैखिक प्रणाली को हल करने के लिए पुनरावृत्त विधियों में उपयोगी होते हैं चूंकि अधिकांश पुनरावृत्त रैखिक सॉल्वरों के लिए अभिसरण की दर बढ़ जाती है क्योंकि प्रीकंडीशनिंग के परिणामस्वरूप आव्युह की स्थिति संख्या कम हो जाती है। पूर्वनिर्धारित पुनरावृत्त सॉल्वर सामान्यतः प्रत्यक्ष सॉल्वर से उत्तम प्रदर्शन करते हैं, उदाहरण के लिए, गॉसियन उन्मूलन, बड़े के लिए, विशेष रूप से विरल आव्युह, मैट्रिसेस के लिए। पुनरावृत्त सॉल्वर का उपयोग आव्युह-मुक्त विधियों के रूप में किया जा सकता है, अर्थात गुणांक आव्युह होने पर एकमात्र विकल्प बन जाता है स्पष्ट रूप से संग्रहीत नहीं है, किन्तु आव्युह-सदिश उत्पादों का मूल्यांकन करके इस तक पहुंचा जाता है।
विवरण
के लिए मूल रैखिक प्रणाली को हल करने के अतिरिक्त, कोई सही पूर्व नियम प्रणाली पर विचार कर सकता है
वैकल्पिक रूप से, कोई बाईं पूर्व नियम प्रणाली को हल कर सकता है
दो तरफा पूर्व नियम प्रणाली
प्रीकंडीशनिंग का लक्ष्य नियम संख्या को कम करना है, उदाहरण के लिए, बाएं या दाएं प्रीकंडिशनिंग सिस्टम आव्युह की या . छोटी स्थिति संख्याएं पुनरावृत्त सॉल्वरों के तेजी से अभिसरण का लाभ उठाती हैं और सिस्टम आव्युह और दाईं ओर गड़बड़ी के संबंध में समाधान की स्थिरता में सुधार करती हैं, उदाहरण के लिए, कम परिशुद्धता (कंप्यूटर) का उपयोग करके आव्युह प्रविष्टियों के अधिक आक्रामक परिमाणीकरण (सिग्नल प्रोसेसिंग) की अनुमति देती है विज्ञान)।
पूर्वनिर्धारित आव्युह या शायद ही कभी स्पष्ट रूप से गठित किया गया हो। केवल प्रीकंडीशनर लगाने की क्रिया ही ऑपरेशन को हल करती है किसी दिए गए सदिश की गणना करने की आवश्यकता हो सकती है।
सामान्यतः चयन में समझौता होता है . ऑपरेटर के बाद से इसे पुनरावृत्त रैखिक सॉल्वर के प्रत्येक चरण पर लागू किया जाना चाहिए, इसे लागू करने की छोटी लागत (कंप्यूटिंग समय) होनी चाहिए संचालन। इसलिए सबसे सस्ता प्रीकंडीशनर होगा के बाद से स्पष्ट रूप से, इसका परिणाम मूल रैखिक प्रणाली में होता है और प्रीकंडीशनर कुछ नहीं करता है। दूसरे चरम पर, विकल्प देता है जिसकी इष्टतम स्थिति संख्या 1 है, अभिसरण के लिए एकल पुनरावृत्ति की आवश्यकता है; हालाँकि इस मामले में और प्रीकंडीशनर को लागू करना मूल प्रणाली को हल करने जितना ही कठिन है। इसलिए कोई चुनता है ऑपरेटर को बनाए रखते हुए न्यूनतम संख्या में रैखिक पुनरावृत्तियों को प्राप्त करने के प्रयास में, इन दो चरम सीमाओं के बीच कहीं यथासंभव सरल। विशिष्ट प्रीकंडीशनिंग दृष्टिकोण के कुछ उदाहरण नीचे विस्तृत हैं।
पूर्वनिर्धारित पुनरावृत्तीय विधियाँ
के लिए पूर्वनिर्धारित पुनरावृत्तीय विधियाँ अधिकांश मामलों में, गणितीय रूप से पूर्वनिर्धारित प्रणाली पर लागू मानक पुनरावृत्त विधियों के बराबर हैं उदाहरण के लिए, हल करने के लिए मानक रिचर्डसन पुनरावृत्ति है
आव्युह विभाजन
एक पुनरावृत्तीय विधि#स्थिर पुनरावृत्तीय विधियाँ आव्युह विभाजन द्वारा निर्धारित की जाती हैं और पुनरावृत्ति आव्युह . ये मानते हुए
- सिस्टम आव्युह सममित आव्युह है सकारात्मक-निश्चित आव्युह|सकारात्मक-निश्चित,
- विभाजन आव्युह सममित आव्युह है सकारात्मक-निश्चित आव्युह|सकारात्मक-निश्चित,
- स्थिर पुनरावृत्त विधि अभिसरण है, जैसा कि निर्धारित किया गया है ,
नियम संख्या से ऊपर घिरा हुआ है
ज्यामितीय व्याख्या
एक सममित आव्युह सकारात्मक-निश्चित आव्युह आव्युह के लिए पूर्व नियम लगानेवाला सामान्यतः सममित सकारात्मक निश्चित होने के लिए भी चुना जाता है। पूर्व नियम ऑपरेटर फिर सममित सकारात्मक निश्चित भी है, किन्तु के संबंध में -आधारित अदिश उत्पाद। इस मामले में, प्रीकंडीशनर को लागू करने में वांछित प्रभाव प्रीकंडीशनर ऑपरेटर का द्विघात रूप बनाना है के प्रति सम्मान के साथ -आधारित अदिश उत्पाद का लगभग गोलाकार होना।[1]
परिवर्तनीय और गैर-रैखिक पूर्व शर्त
दर्शाने , हम इस बात पर प्रकाश डालते हैं कि प्रीकंडीशनिंग को व्यावहारिक रूप से कुछ सदिश को गुणा करने के रूप में कार्यान्वित किया जाता है द्वारा , अर्थात, उत्पाद की गणना करना कई अनुप्रयोगों में, आव्युह के रूप में नहीं, बल्कि ऑपरेटर के रूप में दिया गया है सदिश पर कार्य करना . हालाँकि, कुछ लोकप्रिय प्रीकंडीशनर बदल जाते हैं और पर निर्भरता रैखिक नहीं हो सकता. विशिष्ट उदाहरणों में प्रीकंडीशनर निर्माण के भाग के रूप में गैर-रेखीय पुनरावृत्त विधियों का उपयोग करना शामिल है, उदाहरण के लिए, संयुग्म ग्रेडिएंट विधि। ऐसे प्रीकंडीशनर व्यावहारिक रूप से बहुत कुशल हो सकते हैं, हालांकि, सैद्धांतिक रूप से उनके व्यवहार की भविष्यवाणी करना कठिन है।
यादृच्छिक पूर्व शर्त
वैरिएबल प्रीकंडीशनिंग का दिलचस्प विशेष मामला रैंडम प्रीकंडिशनिंग है, उदाहरण के लिए, रैंडम कोर्स ग्रिड पर मल्टीग्रिड प्रीकंडिशनिंग।[2] यदि ढतला हुआ वंश विधियों में उपयोग किया जाता है, तो यादृच्छिक प्रीकंडीशनिंग को स्टोकेस्टिक ग्रेडिएंट डिसेंट के कार्यान्वयन के रूप में देखा जा सकता है और निश्चित प्रीकंडिशनिंग की तुलना में तेजी से अभिसरण हो सकता है, क्योंकि यह ग्रेडिएंट डिसेंट के एसिम्प्टोटिक ज़िग-ज़ैग पैटर्न को तोड़ता है।
वर्णक्रमीय समतुल्य पूर्व शर्त
प्रीकंडीशनिंग का सबसे आम उपयोग आंशिक अंतर समीकरणों के अनुमान के परिणामस्वरूप रैखिक प्रणालियों के पुनरावृत्त समाधान के लिए है। सन्निकटन गुणवत्ता जितनी उत्तम होगी, आव्युह का आकार उतना ही बड़ा होगा। ऐसे मामले में, इष्टतम प्रीकंडीशनिंग का लक्ष्य, तरफ, वर्णक्रमीय स्थिति संख्या बनाना है ऊपर से आव्युह आकार से स्वतंत्र स्थिरांक द्वारा घिरा होना, जिसे एवगेनी जॉर्जिविच डी'याकोनोव|डी'याकोनोव द्वारा वर्णक्रमीय समकक्ष प्रीकंडीशनिंग कहा जाता है। दूसरी ओर, के आवेदन की लागत आदर्श रूप से गुणन की लागत के समानुपाती (आव्युह आकार से भी स्वतंत्र) होना चाहिए सदिश द्वारा.
उदाहरण
जैकोबी (या विकर्ण) प्रीकंडीशनर
जैकोबी प्रीकंडीशनर प्रीकंडीशनिंग के सबसे सरल रूपों में से है, जिसमें प्रीकंडीशनर को आव्युह के विकर्ण के रूप में चुना जाता है यह मानते हुए , हम पाते हैं यह विकर्ण रूप से प्रभावी आव्युह के लिए कुशल है . इसका उपयोग बीम समस्याओं या 1-डी समस्याओं के लिए विश्लेषण सॉफ़्टवेयर में किया जाता है (उदाहरण:- STAAD PRO)
एसपीएआई
विरल अनुमानित व्युत्क्रम प्रीकंडीशनर न्यूनतम करता है कहाँ फ्रोबेनियस मानदंड है और विरल आव्यूहों के कुछ उपयुक्त रूप से सीमित सेट से है। फ्रोबेनियस मानदंड के तहत, यह कई स्वतंत्र न्यूनतम-वर्ग समस्याओं (प्रत्येक स्तम्भ के लिए एक) को हल करने में कम हो जाता है। में प्रविष्टियाँ इसे कुछ विरलता पैटर्न तक ही सीमित रखा जाना चाहिए अन्यथा समस्या उतनी ही कठिन और समय लेने वाली बनी रहेगी जितनी इसका सटीक व्युत्क्रम खोजना . यह विधि एम.जे. ग्रोट और टी. हकल द्वारा विरल पैटर्न के चयन के दृष्टिकोण के साथ पेश की गई थी।[3]
अन्य प्रीकंडीशनर
- अधूरा चोलेस्की गुणनखंडन
- अधूरा एलयू फैक्टराइजेशन
- क्रमिक अति-विश्राम
- मल्टीग्रिड विधि#मल्टीग्रिड प्रीकंडीशनिंग
बाहरी संबंध
- Preconditioned Conjugate Gradient – math-linux.com
- Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods
eigenvalue समस्याओं के लिए पूर्व शर्त
आइजेनवैल्यू समस्याओं को कई वैकल्पिक विधियों से तैयार किया जा सकता है, जिनमें से प्रत्येक की अपनी पूर्व नियम होती है। पारंपरिक प्रीकंडीशनिंग तथाकथित वर्णक्रमीय परिवर्तनों पर आधारित है। लक्षित आइगेनवैल्यू को (लगभग) जानते हुए, कोई संबंधित सजातीय रैखिक प्रणाली को हल करके संबंधित आइजेनसदिश की गणना कर सकता है, इस प्रकार रैखिक प्रणाली के लिए प्रीकंडीशनिंग का उपयोग करने की अनुमति मिलती है। अंत में, रेले भागफल के अनुकूलन के रूप में आइगेनवैल्यू समस्या को तैयार करने से दृश्य में पूर्वनिर्धारित अनुकूलन तकनीक आती है।[4]
वर्णक्रमीय परिवर्तन
एक eigenvalue समस्या के लिए, रैखिक प्रणालियों के अनुरूप किसी को आव्युह को बदलने का प्रलोभन हो सकता है आव्युह के साथ प्रीकंडीशनर का उपयोग करना . हालाँकि, यह केवल तभी समझ में आता है जब eigenvectors की तलाश हो और समान हैं। यह वर्णक्रमीय परिवर्तनों का मामला है।
सबसे लोकप्रिय वर्णक्रमीय परिवर्तन तथाकथित शिफ्ट-एंड-इनवर्ट परिवर्तन है, जहां किसी दिए गए स्केलर के लिए , जिसे शिफ्ट, मूल eigenvalue समस्या कहा जाता है इसे शिफ्ट-एंड-इनवर्ट समस्या से बदल दिया गया है . आइजेनसदिश संरक्षित हैं, और कोई पुनरावृत्त सॉल्वर, जैसे, पावर पुनरावृत्ति द्वारा शिफ्ट-एंड-इनवर्ट समस्या को हल कर सकता है। यह व्युत्क्रम पुनरावृत्ति देता है, जो सामान्यतः शिफ्ट के निकटतम ईजेनवैल्यू के अनुरूप, ईजेनसदिश में परिवर्तित हो जाता है . रेले भागफल पुनरावृत्ति परिवर्तनशील बदलाव के साथ शिफ्ट-एंड-इनवर्ट विधि है।
वर्णक्रमीय परिवर्तन eigenvalue समस्याओं के लिए विशिष्ट हैं और रैखिक प्रणालियों के लिए इसका कोई एनालॉग नहीं है। उन्हें शामिल परिवर्तन की सटीक संख्यात्मक गणना की आवश्यकता होती है, जो बड़ी समस्याओं के लिए मुख्य बाधा बन जाती है।
सामान्य पूर्व शर्त
रैखिक प्रणालियों से घनिष्ठ संबंध बनाने के लिए, आइए मान लें कि लक्षित eigenvalue (लगभग) ज्ञात है। फिर कोई सजातीय रैखिक प्रणाली से संबंधित आइजनसदिश की गणना कर सकता है . रैखिक प्रणालियों के लिए बाईं पूर्व नियम की अवधारणा का उपयोग करते हुए, हम प्राप्त करते हैं , कहाँ प्रीकंडीशनर है, जिसे हम रिचर्डसन पुनरावृत्ति का उपयोग करके हल करने का प्रयास कर सकते हैं
आदर्श पूर्व शर्त[4]
मूर-पेनरोज़ स्यूडोइनवर्स प्रीकंडीशनर है, जो ऊपर रिचर्डसन पुनरावृत्ति को चरण में अभिसरण बनाता है , तब से , द्वारा चिह्नित , ईजेनस्पेस पर ऑर्थोगोनल प्रोजेक्टर है, जो इसके अनुरूप है . विकल्प तीन स्वतंत्र कारणों से अव्यावहारिक है। पहला, वास्तव में ज्ञात नहीं है, हालाँकि इसे इसके सन्निकटन से बदला जा सकता है . दूसरा, सटीक मूर-पेनरोज़ स्यूडोइनवर्स के लिए आइजेनसदिश के ज्ञान की आवश्यकता होती है, जिसे हम खोजने की कोशिश कर रहे हैं। जैकोबी-डेविडसन प्रीकंडीशनर के उपयोग से इसे कुछ हद तक टाला जा सकता है , कहाँ अनुमानित . अंतिम, किन्तु कम महत्वपूर्ण नहीं, इस दृष्टिकोण के लिए सिस्टम आव्युह के साथ रैखिक प्रणाली के सटीक संख्यात्मक समाधान की आवश्यकता होती है , जो बड़ी समस्याओं के लिए उपरोक्त शिफ्ट-एंड-इनवर्ट विधि जितनी महंगी हो जाती है। यदि समाधान पर्याप्त सटीक नहीं है, तो चरण दो निरर्थक हो सकता है।
व्यावहारिक पूर्व शर्त
आइए सबसे पहले सैद्धांतिक मूल्य को प्रतिस्थापित करें उपरोक्त रिचर्डसन पुनरावृत्ति में इसके वर्तमान सन्निकटन के साथ व्यावहारिक एल्गोरिदम प्राप्त करने के लिए
बदलते मूल्य के कारण रेखीय प्रणालियों के मामले की तुलना में, व्यापक सैद्धांतिक अभिसरण विश्लेषण बहुत अधिक कठिन है, यहां तक कि रिचर्डसन पुनरावृत्ति जैसे सबसे सरल विधियों के लिए भी।
बाहरी संबंध
अनुकूलन में पूर्व शर्त
अनुकूलन (गणित) में, प्रीकंडीशनिंग का उपयोग सामान्यतः प्रथम-क्रम सन्निकटन|प्रथम-क्रम अनुकूलन (गणित) एल्गोरिदम को तेज करने के लिए किया जाता है।
विवरण
उदाहरण के लिए, किसी वास्तविक-मूल्यवान फ़ंक्शन का स्थानीय न्यूनतम ज्ञात करना ग्रेडियेंट डिसेंट का उपयोग करते हुए, व्यक्ति ग्रेडिएंट के नकारात्मक के अनुपात में कदम उठाता है वर्तमान बिंदु पर फ़ंक्शन का (या अनुमानित ग्रेडिएंट का):
रैखिक प्रणालियों से कनेक्शन
द्विघात फलन का न्यूनतम
आइजेनवैल्यू समस्याओं से कनेक्शन
रेले भागफल का न्यूनतम
परिवर्तनीय पूर्व शर्त
कई मामलों में, स्तर सेट के बदलते आकार को समायोजित करने के लिए पुनरावृत्त एल्गोरिदम के कुछ या यहां तक कि हर चरण पर प्रीकंडीशनर को बदलना फायदेमंद हो सकता है, जैसा कि
संदर्भ
- ↑ Shewchuk, Jonathan Richard (August 4, 1994). "कष्टकारी दर्द के बिना संयुग्मित ग्रेडिएंट विधि का परिचय" (PDF).
- ↑ 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
- ↑ Grote, M. J. & Huckle, T. (1997). "विरल अनुमानित व्युत्क्रमों के साथ समानांतर प्रीकंडीशनिंग". SIAM Journal on Scientific Computing. 18 (3): 838–53. doi:10.1137/S1064827594276552.
- ↑ 4.0 4.1 Knyazev, Andrew V. (1998). "Preconditioned eigensolvers - an oxymoron?". Electronic Transactions on Numerical Analysis. 7: 104–123.
- ↑ Himmelblau, David M. (1972). एप्लाइड नॉनलाइनियर प्रोग्रामिंग. New York: McGraw-Hill. pp. 78–83. ISBN 0-07-028921-2.
स्रोत
- Axelsson, Owe (1996). पुनरावृत्तीय समाधान विधियाँ. Cambridge University Press. p. 6722. ISBN 978-0-521-55569-2.
- D'yakonov, E. G. (1996). अण्डाकार समस्याओं को हल करने में अनुकूलन. CRC-Press. p. 592. ISBN 978-0-8493-2872-5.
- Saad, Yousef & van der Vorst, Henk (2001). "Iterative solution of linear systems in the 20th century". In Brezinski, C. & Wuytack, L. (eds.). संख्यात्मक विश्लेषण: 20वीं सदी में ऐतिहासिक विकास. Elsevier Science Publishers. §8 Preconditioning methods, pp 193–8. ISBN 0-444-50617-9.
- van der Vorst, H. A. (2003). बड़े रैखिक प्रणालियों के लिए पुनरावृत्त क्रायलोव विधियाँ. Cambridge University Press, Cambridge. ISBN 0-521-81828-1.
- Chen, Ke (2005). मैट्रिक्स प्रीकंडीशनिंग तकनीक और अनुप्रयोग. Cambridge: Cambridge University Press. ISBN 978-0521838283. OCLC 61410324.
श्रेणी:संख्यात्मक रैखिक बीजगणित