प्रीकंडीशनर

"प्रीकंडीशनिंग" 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^{-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.

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