प्रीकंडीशनर: Difference between revisions
From Vigyanwiki
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 समस्याओं के लिए रैखिक प्रणालियों के लिए विकसित किए गए पूर्वकंडिशनरों की विशाल विविधता का आसानी से उपयोग करने की अनुमति देता है। | |||