प्रीकंडीशनर

"प्रीकंडीशनिंग" redirects here. For other uses, see प्रीकंडीशनिंग (disambiguation).

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

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

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

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

विवरण

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

$$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^{-1}$ को यथासंभव सरल रखते हुए न्यूनतम संख्या में रैखिक पुनरावृत्तियों को प्राप्त करने के प्रयास में, इन दोनों चरम सीमाओं के मध्य में $P$ को चुना जाता है। विशिष्ट प्रीकंडीशनिंग दृष्टिकोण के कुछ उदाहरण नीचे विस्तृत हैं।

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

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

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

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

$T=P^{-1}$ को दर्शाते हुए, हम इस बात पर प्रकाश डालते हैं कि प्रीकंडीशनिंग को व्यावहारिक रूप से कुछ सदिश $r$ को $T$ से गुणा करने के रूप में कार्यान्वित किया जाता है, अर्थात, उत्पाद $Tr.$ की गणना करना होता है | अनेक अनुप्रयोगों में, $T$ को आव्युह के रूप में नहीं दिया जाता है, बल्कि सदिश $r$ पर कार्य करने वाले ऑपरेटर $T(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-D समस्याओं के लिए विश्लेषण सॉफ़्टवेयर में किया जाता है (उदाहरण:- स्टैड प्रो)

एसपीएआई

विरल अनुमानित व्युत्क्रम प्रीकंडीशनर $\|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

आइजेनवैल्यू समस्याओं के लिए प्रीकंडीशनिंग

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

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

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

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

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

सामान्य प्रीकंडीशनिंग

रैखिक प्रणालियों से घनिष्ठ संबंध बनाने के लिए, आइए मान लें कि लक्षित आइजेनवैल्यू $\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-$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.$$

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

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

बाहरी संबंध

• Templates for the Solution of Algebraic आइजेनवैल्यू 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$ वास्तविक सममित आव्युह धनात्मक -निश्चित आव्युह है, इसका सबसे छोटा आइजेनवैल्यू है $A$, जबकि मिनिमाइज़र संगत आइजन्वेक्टर है। तब से $\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.$$

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

परिवर्तनीय प्रीकंडीशनिंग

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

$$\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.

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