प्रीकंडीशनर

"Preconditioning" redirects here. For other uses, see Preconditioning (disambiguation).

गणित में, प्रीकंडीशनिंग एक परिवर्तन का अनुप्रयोग है, जिसे प्रीकंडीशनर कहा जाता है, जो किसी दी गई समस्या को ऐसे रूप में प्रस्तुत करता है जो संख्यात्मक गणित को हल करने के तरीकों के लिए अधिक उपयुक्त है। प्रीकंडीशनिंग आम तौर पर समस्या की स्थिति संख्या को कम करने से संबंधित है। पूर्वनिर्धारित समस्या को आमतौर पर पुनरावृत्तीय विधि द्वारा हल किया जाता है।

रैखिक प्रणालियों के लिए पूर्व शर्त

रैखिक बीजगणित और संख्यात्मक विश्लेषण में, एक पूर्व शर्तकर्ता $P$ एक मैट्रिक्स का $A$ एक मैट्रिक्स ऐसा है $P^{-1}A$ से छोटी शर्त संख्या है $A$. कॉल करना भी आम बात है $T=P^{-1}$ पूर्व शर्तकर्ता, के बजाय $P$, तब से $P$ स्वयं शायद ही कभी स्पष्ट रूप से उपलब्ध हो। आधुनिक प्रीकंडीशनिंग में, का अनुप्रयोग $T=P^{-1}$, यानी, एक कॉलम वेक्टर, या कॉलम वैक्टर के एक ब्लॉक का गुणन $T=P^{-1}$, आमतौर पर मैट्रिक्स-मुक्त तरीकों में किया जाता है | मैट्रिक्स-मुक्त फैशन, यानी, जहां न तो $P$, और न $T=P^{-1}$ (और अक्सर नहीं भी $A$) मैट्रिक्स रूप में स्पष्ट रूप से उपलब्ध हैं।

प्रीकंडीशनर एक रैखिक प्रणाली को हल करने के लिए पुनरावृत्त तरीकों में उपयोगी होते हैं $Ax=b$ के लिए $x$ चूंकि अधिकांश पुनरावृत्त रैखिक सॉल्वरों के लिए अभिसरण की दर बढ़ जाती है क्योंकि प्रीकंडीशनिंग के परिणामस्वरूप मैट्रिक्स की स्थिति संख्या कम हो जाती है। पूर्वनिर्धारित पुनरावृत्त सॉल्वर आम तौर पर प्रत्यक्ष सॉल्वर से बेहतर प्रदर्शन करते हैं, उदाहरण के लिए, गॉसियन उन्मूलन, बड़े के लिए, विशेष रूप से विरल मैट्रिक्स, मैट्रिसेस के लिए। पुनरावृत्त सॉल्वर का उपयोग मैट्रिक्स-मुक्त तरीकों के रूप में किया जा सकता है, यानी गुणांक मैट्रिक्स होने पर एकमात्र विकल्प बन जाता है $A$ स्पष्ट रूप से संग्रहीत नहीं है, लेकिन मैट्रिक्स-वेक्टर उत्पादों का मूल्यांकन करके इस तक पहुंचा जाता है।

विवरण

मूल रैखिक प्रणाली को हल करने के बजाय $Ax=b$ के लिए $x$, कोई सही पूर्व शर्त प्रणाली पर विचार कर सकता है

$$AP^{-1}(Px)=b$$

और हल करें

$$AP^{-1}y=b$$

के लिए $y$ और

$$Px=y$$

के लिए $x$.

वैकल्पिक रूप से, कोई बाईं पूर्व शर्त प्रणाली को हल कर सकता है

$$P^{-1}(Ax-b)=0.$$

दोनों प्रणालियाँ मूल प्रणाली के समान ही समाधान देती हैं जब तक कि प्रीकंडीशनर मैट्रिक्स $P$ बीजगणितीय वक्र#विलक्षणता है। बाईं ओर की पूर्व शर्त अधिक पारंपरिक है।

दो तरफा पूर्व शर्त प्रणाली

$$QAP^{-1}(Px)=Qb$$

फायदेमंद हो सकता है, उदाहरण के लिए, मैट्रिक्स समरूपता को संरक्षित करने के लिए: यदि मूल मैट्रिक्स $A$ वास्तविक सममित और वास्तविक पूर्व शर्तकर्ता है $Q$ और $P$ संतुष्ट करना $Q^{T}=P^{-1}$ फिर पूर्वनिर्धारित मैट्रिक्स $QAP^{-1}$ सममित भी है. जहां प्रीकंडीशनर विकर्ण स्केलिंग के लिए दो-तरफा प्रीकंडीशनिंग आम है $Q$ और $P$ विकर्ण हैं और स्केलिंग मूल मैट्रिक्स के स्तंभों और पंक्तियों दोनों पर लागू होती है $A$, उदाहरण के लिए, मैट्रिक्स की प्रविष्टियों की गतिशील सीमा को कम करने के लिए।

प्रीकंडीशनिंग का लक्ष्य शर्त संख्या को कम करना है, उदाहरण के लिए, बाएं या दाएं प्रीकंडिशनिंग सिस्टम मैट्रिक्स की $P^{-1}A$ या $AP^{-1}$. छोटी स्थिति संख्याएं पुनरावृत्त सॉल्वरों के तेजी से अभिसरण का लाभ उठाती हैं और सिस्टम मैट्रिक्स और दाईं ओर गड़बड़ी के संबंध में समाधान की स्थिरता में सुधार करती हैं, उदाहरण के लिए, कम परिशुद्धता (कंप्यूटर) का उपयोग करके मैट्रिक्स प्रविष्टियों के अधिक आक्रामक परिमाणीकरण (सिग्नल प्रोसेसिंग) की अनुमति देती है विज्ञान)।

पूर्वनिर्धारित मैट्रिक्स $P^{-1}A$ या $AP^{-1}$ शायद ही कभी स्पष्ट रूप से गठित किया गया हो। केवल प्रीकंडीशनर लगाने की क्रिया ही ऑपरेशन को हल करती है $P^{-1}$ किसी दिए गए वेक्टर की गणना करने की आवश्यकता हो सकती है।

आम तौर पर चयन में समझौता होता है $P$. ऑपरेटर के बाद से $P^{-1}$ इसे पुनरावृत्त रैखिक सॉल्वर के प्रत्येक चरण पर लागू किया जाना चाहिए, इसे लागू करने की एक छोटी लागत (कंप्यूटिंग समय) होनी चाहिए $P^{-1}$ संचालन। इसलिए सबसे सस्ता प्रीकंडीशनर होगा $P=I$ के बाद से $P^{-1}=I.$ स्पष्ट रूप से, इसका परिणाम मूल रैखिक प्रणाली में होता है और प्रीकंडीशनर कुछ नहीं करता है। दूसरे चरम पर, विकल्प $P=A$ देता है $P^{-1}A=AP^{-1}=I,$ जिसकी इष्टतम स्थिति संख्या 1 है, अभिसरण के लिए एकल पुनरावृत्ति की आवश्यकता है; हालाँकि इस मामले में $P^{-1}=A^{-1},$ और प्रीकंडीशनर को लागू करना मूल प्रणाली को हल करने जितना ही कठिन है। इसलिए कोई चुनता है $P$ ऑपरेटर को बनाए रखते हुए न्यूनतम संख्या में रैखिक पुनरावृत्तियों को प्राप्त करने के प्रयास में, इन दो चरम सीमाओं के बीच कहीं $P^{-1}$ यथासंभव सरल। विशिष्ट प्रीकंडीशनिंग दृष्टिकोण के कुछ उदाहरण नीचे विस्तृत हैं।

पूर्वनिर्धारित पुनरावृत्तीय विधियाँ

के लिए पूर्वनिर्धारित पुनरावृत्तीय विधियाँ $Ax-b=0$ अधिकांश मामलों में, गणितीय रूप से पूर्वनिर्धारित प्रणाली पर लागू मानक पुनरावृत्त तरीकों के बराबर हैं $P^{-1}(Ax-b)=0.$ उदाहरण के लिए, हल करने के लिए मानक रिचर्डसन पुनरावृत्ति $Ax-b=0$ है

$$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}(A\mathbf {x} _{n}-\mathbf {b} ),\ n\geq 0.$$

पूर्व शर्त प्रणाली पर लागू किया गया $P^{-1}(Ax-b)=0,$ यह एक पूर्वनिर्धारित पद्धति में बदल जाता है

$$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}(A\mathbf {x} _{n}-\mathbf {b} ),\ n\geq 0.$$

रैखिक प्रणालियों के लिए लोकप्रिय पूर्वनिर्धारित पुनरावृत्त तरीकों के उदाहरणों में पूर्वनिर्धारित संयुग्म ग्रेडिएंट विधि, द्विसंयुग्म ग्रेडिएंट विधि और सामान्यीकृत न्यूनतम अवशिष्ट विधि शामिल हैं। पुनरावृत्तीय विधियाँ, जो पुनरावृत्तीय मापदंडों की गणना करने के लिए अदिश उत्पादों का उपयोग करती हैं, उन्हें प्रतिस्थापन के साथ-साथ अदिश उत्पाद में संगत परिवर्तनों की आवश्यकता होती है $P^{-1}(Ax-b)=0$ के लिए $Ax-b=0.$

मैट्रिक्स विभाजन

एक पुनरावृत्तीय विधि#स्थिर पुनरावृत्तीय विधियाँ मैट्रिक्स विभाजन द्वारा निर्धारित की जाती हैं $A=M-N$ और पुनरावृत्ति मैट्रिक्स $C=I-M^{-1}A$. ये मानते हुए

• सिस्टम मैट्रिक्स $A$ सममित मैट्रिक्स है सकारात्मक-निश्चित मैट्रिक्स|सकारात्मक-निश्चित,
• विभाजन मैट्रिक्स $M$ सममित मैट्रिक्स है सकारात्मक-निश्चित मैट्रिक्स|सकारात्मक-निश्चित,
• स्थिर पुनरावृत्त विधि अभिसरण है, जैसा कि निर्धारित किया गया है $\rho (C)<1$,

शर्त संख्या $\kappa (M^{-1}A)$ से ऊपर घिरा हुआ है

$$\kappa (M^{-1}A)\leq {\frac {1+\rho (C)}{1-\rho (C)}}\,.$$

ज्यामितीय व्याख्या

एक सममित मैट्रिक्स सकारात्मक-निश्चित मैट्रिक्स मैट्रिक्स के लिए $A$ पूर्व शर्त लगानेवाला $P$ आमतौर पर सममित सकारात्मक निश्चित होने के लिए भी चुना जाता है। पूर्व शर्त ऑपरेटर $P^{-1}A$ फिर सममित सकारात्मक निश्चित भी है, लेकिन के संबंध में $P$-आधारित अदिश उत्पाद। इस मामले में, प्रीकंडीशनर को लागू करने में वांछित प्रभाव प्रीकंडीशनर ऑपरेटर का द्विघात रूप बनाना है $P^{-1}A$ के प्रति सम्मान के साथ $P$-आधारित अदिश उत्पाद का लगभग गोलाकार होना।

परिवर्तनीय और गैर-रैखिक पूर्व शर्त

दर्शाने $T=P^{-1}$, हम इस बात पर प्रकाश डालते हैं कि प्रीकंडीशनिंग को व्यावहारिक रूप से कुछ वेक्टर को गुणा करने के रूप में कार्यान्वित किया जाता है $r$ द्वारा $T$, यानी, उत्पाद की गणना करना $Tr.$ कई अनुप्रयोगों में, $T$ एक मैट्रिक्स के रूप में नहीं, बल्कि एक ऑपरेटर के रूप में दिया गया है $T(r)$ वेक्टर पर कार्य करना $r$. हालाँकि, कुछ लोकप्रिय प्रीकंडीशनर बदल जाते हैं $r$ और पर निर्भरता $r$ रैखिक नहीं हो सकता. विशिष्ट उदाहरणों में प्रीकंडीशनर निर्माण के एक भाग के रूप में गैर-रेखीय पुनरावृत्त तरीकों का उपयोग करना शामिल है, उदाहरण के लिए, संयुग्म ग्रेडिएंट विधि। ऐसे प्रीकंडीशनर व्यावहारिक रूप से बहुत कुशल हो सकते हैं, हालांकि, सैद्धांतिक रूप से उनके व्यवहार की भविष्यवाणी करना कठिन है।

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

वैरिएबल प्रीकंडीशनिंग का एक दिलचस्प विशेष मामला रैंडम प्रीकंडिशनिंग है, उदाहरण के लिए, रैंडम कोर्स ग्रिड पर मल्टीग्रिड प्रीकंडिशनिंग। यदि ढतला हुआ वंश विधियों में उपयोग किया जाता है, तो यादृच्छिक प्रीकंडीशनिंग को स्टोकेस्टिक ग्रेडिएंट डिसेंट के कार्यान्वयन के रूप में देखा जा सकता है और निश्चित प्रीकंडिशनिंग की तुलना में तेजी से अभिसरण हो सकता है, क्योंकि यह ग्रेडिएंट डिसेंट के एसिम्प्टोटिक ज़िग-ज़ैग पैटर्न को तोड़ता है।

वर्णक्रमीय समतुल्य पूर्व शर्त

प्रीकंडीशनिंग का सबसे आम उपयोग आंशिक अंतर समीकरणों के अनुमान के परिणामस्वरूप रैखिक प्रणालियों के पुनरावृत्त समाधान के लिए है। सन्निकटन गुणवत्ता जितनी बेहतर होगी, मैट्रिक्स का आकार उतना ही बड़ा होगा। ऐसे मामले में, इष्टतम प्रीकंडीशनिंग का लक्ष्य, एक तरफ, वर्णक्रमीय स्थिति संख्या बनाना है $P^{-1}A$ ऊपर से मैट्रिक्स आकार से स्वतंत्र एक स्थिरांक द्वारा घिरा होना, जिसे एवगेनी जॉर्जिविच डी'याकोनोव|डी'याकोनोव द्वारा वर्णक्रमीय समकक्ष प्रीकंडीशनिंग कहा जाता है। दूसरी ओर, के आवेदन की लागत $P^{-1}$ आदर्श रूप से गुणन की लागत के समानुपाती (मैट्रिक्स आकार से भी स्वतंत्र) होना चाहिए $A$ एक वेक्टर द्वारा.

उदाहरण

जैकोबी (या विकर्ण) प्रीकंडीशनर

जैकोबी प्रीकंडीशनर प्रीकंडीशनिंग के सबसे सरल रूपों में से एक है, जिसमें प्रीकंडीशनर को मैट्रिक्स के विकर्ण के रूप में चुना जाता है $P=\mathrm {diag} (A).$ यह मानते हुए $A_{ii}\neq 0,\forall i$, हम पाते हैं $P_{ij}^{-1}={\frac {\delta _{ij}}{A_{ij}}}.$ यह विकर्ण रूप से प्रभावी मैट्रिक्स के लिए कुशल है $A$. इसका उपयोग बीम समस्याओं या 1-डी समस्याओं के लिए विश्लेषण सॉफ़्टवेयर में किया जाता है (उदाहरण:- STAAD PRO)

एसपीएआई

विरल अनुमानित व्युत्क्रम प्रीकंडीशनर न्यूनतम करता है $\|AT-I\|_{F},$ कहाँ $\|\cdot \|_{F}$ फ्रोबेनियस मानदंड है और $T=P^{-1}$ विरल आव्यूहों के कुछ उपयुक्त रूप से सीमित सेट से है। फ्रोबेनियस मानदंड के तहत, यह कई स्वतंत्र न्यूनतम-वर्ग समस्याओं (प्रत्येक कॉलम के लिए एक) को हल करने में कम हो जाता है। में प्रविष्टियाँ $T$ इसे कुछ विरलता पैटर्न तक ही सीमित रखा जाना चाहिए अन्यथा समस्या उतनी ही कठिन और समय लेने वाली बनी रहेगी जितनी इसका सटीक व्युत्क्रम खोजना $A$. यह विधि एम.जे. ग्रोट और टी. हकल द्वारा विरल पैटर्न के चयन के दृष्टिकोण के साथ पेश की गई थी।

अन्य पूर्व शर्तकर्ता

• अधूरा चोलेस्की गुणनखंडन
• अधूरा एलयू फैक्टराइजेशन
• क्रमिक अति-विश्राम
  • सममित क्रमिक अति-विश्राम
• मल्टीग्रिड विधि#मल्टीग्रिड प्रीकंडीशनिंग

बाहरी संबंध

• Preconditioned Conjugate Gradient – math-linux.com
• Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods

eigenvalue समस्याओं के लिए पूर्व शर्त

आइजेनवैल्यू समस्याओं को कई वैकल्पिक तरीकों से तैयार किया जा सकता है, जिनमें से प्रत्येक की अपनी पूर्व शर्त होती है। पारंपरिक प्रीकंडीशनिंग तथाकथित वर्णक्रमीय परिवर्तनों पर आधारित है। लक्षित आइगेनवैल्यू को (लगभग) जानते हुए, कोई संबंधित सजातीय रैखिक प्रणाली को हल करके संबंधित आइजेनवेक्टर की गणना कर सकता है, इस प्रकार रैखिक प्रणाली के लिए प्रीकंडीशनिंग का उपयोग करने की अनुमति मिलती है। अंत में, रेले भागफल के अनुकूलन के रूप में आइगेनवैल्यू समस्या को तैयार करने से दृश्य में पूर्वनिर्धारित अनुकूलन तकनीक आती है।

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

एक eigenvalue समस्या के लिए, रैखिक प्रणालियों के अनुरूप $Ax=\lambda x$ किसी को मैट्रिक्स को बदलने का प्रलोभन हो सकता है $A$ मैट्रिक्स के साथ $P^{-1}A$ एक प्रीकंडीशनर का उपयोग करना $P$. हालाँकि, यह केवल तभी समझ में आता है जब eigenvectors की तलाश हो $A$ और $P^{-1}A$ समान हैं। यह वर्णक्रमीय परिवर्तनों का मामला है।

सबसे लोकप्रिय वर्णक्रमीय परिवर्तन तथाकथित शिफ्ट-एंड-इनवर्ट परिवर्तन है, जहां किसी दिए गए स्केलर के लिए $\alpha$, जिसे शिफ्ट, मूल eigenvalue समस्या कहा जाता है $Ax=\lambda x$ इसे शिफ्ट-एंड-इनवर्ट समस्या से बदल दिया गया है $(A-\alpha I)^{-1}x=\mu x$. आइजेनवेक्टर संरक्षित हैं, और कोई पुनरावृत्त सॉल्वर, जैसे, पावर पुनरावृत्ति द्वारा शिफ्ट-एंड-इनवर्ट समस्या को हल कर सकता है। यह व्युत्क्रम पुनरावृत्ति देता है, जो आम तौर पर शिफ्ट के निकटतम ईजेनवैल्यू के अनुरूप, ईजेनवेक्टर में परिवर्तित हो जाता है $\alpha$. रेले भागफल पुनरावृत्ति एक परिवर्तनशील बदलाव के साथ एक शिफ्ट-एंड-इनवर्ट विधि है।

वर्णक्रमीय परिवर्तन eigenvalue समस्याओं के लिए विशिष्ट हैं और रैखिक प्रणालियों के लिए इसका कोई एनालॉग नहीं है। उन्हें शामिल परिवर्तन की सटीक संख्यात्मक गणना की आवश्यकता होती है, जो बड़ी समस्याओं के लिए मुख्य बाधा बन जाती है।

सामान्य पूर्व शर्त

रैखिक प्रणालियों से घनिष्ठ संबंध बनाने के लिए, आइए मान लें कि लक्षित eigenvalue $\lambda _{\star }$ (लगभग) ज्ञात है। फिर कोई सजातीय रैखिक प्रणाली से संबंधित आइजनवेक्टर की गणना कर सकता है $(A-\lambda _{\star }I)x=0$. रैखिक प्रणालियों के लिए बाईं पूर्व शर्त की अवधारणा का उपयोग करते हुए, हम प्राप्त करते हैं $T(A-\lambda _{\star }I)x=0$, कहाँ $T$ प्रीकंडीशनर है, जिसे हम रिचर्डसन पुनरावृत्ति का उपयोग करके हल करने का प्रयास कर सकते हैं

$$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}T(A-\lambda _{\star }I)\mathbf {x} _{n},\ n\geq 0.$$

आदर्श पूर्व शर्त

मूर-पेनरोज़ स्यूडोइनवर्स $T=(A-\lambda _{\star }I)^{+}$ प्रीकंडीशनर है, जो ऊपर रिचर्डसन पुनरावृत्ति को एक चरण में अभिसरण बनाता है $\gamma _{n}=1$, तब से $I-(A-\lambda _{\star }I)^{+}(A-\lambda _{\star }I)$, द्वारा चिह्नित $P_{\star }$, ईजेनस्पेस पर ऑर्थोगोनल प्रोजेक्टर है, जो इसके अनुरूप है $\lambda _{\star }$. विकल्प $T=(A-\lambda _{\star }I)^{+}$ तीन स्वतंत्र कारणों से अव्यावहारिक है। पहला, $\lambda _{\star }$ वास्तव में ज्ञात नहीं है, हालाँकि इसे इसके सन्निकटन से बदला जा सकता है ${\tilde {\lambda }}_{\star }$. दूसरा, सटीक मूर-पेनरोज़ स्यूडोइनवर्स के लिए आइजेनवेक्टर के ज्ञान की आवश्यकता होती है, जिसे हम खोजने की कोशिश कर रहे हैं। जैकोबी-डेविडसन प्रीकंडीशनर के उपयोग से इसे कुछ हद तक टाला जा सकता है $T=(I-{\tilde {P}}_{\star })(A-{\tilde {\lambda }}_{\star }I)^{-1}(I-{\tilde {P}}_{\star })$, कहाँ ${\tilde {P}}_{\star }$ अनुमानित $P_{\star }$. अंतिम, लेकिन कम महत्वपूर्ण नहीं, इस दृष्टिकोण के लिए सिस्टम मैट्रिक्स के साथ रैखिक प्रणाली के सटीक संख्यात्मक समाधान की आवश्यकता होती है $(A-{\tilde {\lambda }}_{\star }I)$, जो बड़ी समस्याओं के लिए उपरोक्त शिफ्ट-एंड-इनवर्ट विधि जितनी महंगी हो जाती है। यदि समाधान पर्याप्त सटीक नहीं है, तो चरण दो निरर्थक हो सकता है।

व्यावहारिक पूर्व शर्त

आइए सबसे पहले सैद्धांतिक मूल्य को प्रतिस्थापित करें $\lambda _{\star }$ उपरोक्त रिचर्डसन पुनरावृत्ति में इसके वर्तमान सन्निकटन के साथ $\lambda _{n}$ एक व्यावहारिक एल्गोरिदम प्राप्त करने के लिए

$$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}T(A-\lambda _{n}I)\mathbf {x} _{n},\ n\geq 0.$$

एक लोकप्रिय विकल्प है $\lambda _{n}=\rho (x_{n})$ रेले भागफल फ़ंक्शन का उपयोग करना $\rho (\cdot )$. व्यावहारिक पूर्व-कंडीशनिंग केवल उपयोग करने जितनी ही तुच्छ हो सकती है $T=(\operatorname {diag} (A))^{-1}$ या $T=(\operatorname {diag} (A-\lambda _{n}I))^{-1}.$ eigenvalue समस्याओं के कुछ वर्गों के लिए की दक्षता $T\approx A^{-1}$ संख्यात्मक और सैद्धांतिक दोनों रूप से प्रदर्शित किया गया है। विकल्प $T\approx A^{-1}$ यह किसी को eigenvalue समस्याओं के लिए रैखिक प्रणालियों के लिए विकसित किए गए पूर्वकंडिशनरों की विशाल विविधता का आसानी से उपयोग करने की अनुमति देता है।

बदलते मूल्य के कारण $\lambda _{n}$रेखीय प्रणालियों के मामले की तुलना में, एक व्यापक सैद्धांतिक अभिसरण विश्लेषण बहुत अधिक कठिन है, यहां तक ​​कि रिचर्डसन पुनरावृत्ति जैसे सबसे सरल तरीकों के लिए भी।

बाहरी संबंध

• Templates for the Solution of Algebraic Eigenvalue Problems: a Practical Guide

अनुकूलन में पूर्व शर्त

क्रमिक अवतरण का चित्रण

अनुकूलन (गणित) में, प्रीकंडीशनिंग का उपयोग आमतौर पर प्रथम-क्रम सन्निकटन|प्रथम-क्रम अनुकूलन (गणित) एल्गोरिदम को तेज करने के लिए किया जाता है।

विवरण

उदाहरण के लिए, किसी वास्तविक-मूल्यवान फ़ंक्शन का स्थानीय न्यूनतम ज्ञात करना $F(\mathbf {x} )$ ग्रेडियेंट डिसेंट का उपयोग करते हुए, व्यक्ति ग्रेडिएंट के नकारात्मक के अनुपात में कदम उठाता है $-\nabla F(\mathbf {a} )$ वर्तमान बिंदु पर फ़ंक्शन का (या अनुमानित ग्रेडिएंट का):

$$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.$$

प्रीकंडीशनर को ग्रेडिएंट पर लागू किया जाता है:

$$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}\nabla F(\mathbf {x} _{n}),\ n\geq 0.$$

यहां प्रीकंडिशनिंग को लेवल सेट को सर्कल की तरह दिखने के लक्ष्य के साथ वेक्टर स्पेस की ज्यामिति को बदलने के रूप में देखा जा सकता है। इस मामले में पूर्वनिर्धारित ढाल का लक्ष्य चित्र के अनुसार एक्स्ट्रेमा के बिंदु के करीब है, जो अभिसरण को गति देता है।

रैखिक प्रणालियों से कनेक्शन

द्विघात फलन का न्यूनतम

$$F(\mathbf {x} )={\tfrac {1}{2}}\mathbf {x} ^{T}A\mathbf {x} -\mathbf {x} ^{T}\mathbf {b} ,$$

कहाँ $\mathbf {x}$ और $\mathbf {b}$ वास्तविक कॉलम-वेक्टर हैं और $A$ एक वास्तविक सममित मैट्रिक्स सकारात्मक-निश्चित मैट्रिक्स है, बिल्कुल रैखिक समीकरण का समाधान है $A\mathbf {x} =\mathbf {b}$. तब से $\nabla F(\mathbf {x} )=A\mathbf {x} -\mathbf {b}$, न्यूनतम करने की पूर्वनिर्धारित ग्रेडिएंट डिसेंट विधि $F(\mathbf {x} )$ है

$$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}(A\mathbf {x} _{n}-\mathbf {b} ),\ n\geq 0.$$

यह रैखिक समीकरणों की एक प्रणाली को हल करने के लिए पूर्वनिर्धारित रिचर्डसन पुनरावृत्ति है।

आइजेनवैल्यू समस्याओं से कनेक्शन

रेले भागफल का न्यूनतम

$$\rho (\mathbf {x} )={\frac {\mathbf {x} ^{T}A\mathbf {x} }{\mathbf {x} ^{T}\mathbf {x} }},$$

कहाँ $\mathbf {x}$ एक वास्तविक गैर-शून्य कॉलम-वेक्टर है और $A$ एक वास्तविक सममित मैट्रिक्स सकारात्मक-निश्चित मैट्रिक्स है, इसका सबसे छोटा eigenvalue है $A$, जबकि मिनिमाइज़र संगत eigenvector है। तब से $\nabla \rho (\mathbf {x} )$ के लिए आनुपातिक है $A\mathbf {x} -\rho (\mathbf {x} )\mathbf {x}$, न्यूनतम करने की पूर्वनिर्धारित ग्रेडिएंट डिसेंट विधि $\rho (\mathbf {x} )$ है

$$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}(A\mathbf {x} _{n}-\rho (\mathbf {x_{n}} )\mathbf {x_{n}} ),\ n\geq 0.$$

यह eigenvalue समस्याओं को हल करने के लिए पूर्वनिर्धारित रिचर्डसन पुनरावृत्ति का एक एनालॉग है।

परिवर्तनीय पूर्व शर्त

कई मामलों में, स्तर सेट के बदलते आकार को समायोजित करने के लिए पुनरावृत्त एल्गोरिदम के कुछ या यहां तक ​​कि हर चरण पर प्रीकंडीशनर को बदलना फायदेमंद हो सकता है, जैसा कि

$$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P_{n}^{-1}\nabla F(\mathbf {x} _{n}),\ n\geq 0.$$

हालाँकि, किसी को यह ध्यान में रखना चाहिए कि एक कुशल प्रीकंडीशनर का निर्माण अक्सर कम्प्यूटेशनल रूप से महंगा होता है। प्रीकंडीशनर को अपडेट करने की बढ़ी हुई लागत तेजी से अभिसरण के सकारात्मक प्रभाव को आसानी से खत्म कर सकती है। अगर $P_{n}^{-1}=H_{n}$, व्युत्क्रम हेसियन मैट्रिक्स का एक ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शैनो एल्गोरिदम सन्निकटन, इस विधि को क्वासी-न्यूटन विधि के रूप में जाना जाता है।

स्रोत

• 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.

श्रेणी:संख्यात्मक रैखिक बीजगणित