पूर्व शर्त

"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$ स्पष्ट रूप से संग्रहीत नहीं है, लेकिन मैट्रिक्स-वेक्टर उत्पादों का मूल्यांकन करके इसका उपयोग किया जाता है।

विवरण

उपरोक्त मूल रेखीय प्रणाली को हल करने के बजाय, सही पूर्वानुकूलित प्रणाली पर विचार किया जा सकता है

$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$ रेखीय नहीं हो सकता। विशिष्ट उदाहरणों में गैर-रैखिक पुनरावृत्त विधियों का उपयोग करना शामिल है, उदाहरण के लिए, संयुग्मी ढाल विधि, पूर्व शर्त निर्माण के एक भाग के रूप में। इस तरह के पूर्व शर्त व्यावहारिक रूप से बहुत कुशल हो सकते हैं, हालांकि, उनके व्यवहार का सैद्धांतिक रूप से अनुमान लगाना कठिन है।

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

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

स्पेक्ट्रल रूप से समकक्ष पूर्व शर्त

आंशिक अंतर समीकरणों के सन्निकटन से उत्पन्न रैखिक प्रणालियों के पुनरावृत्त समाधान के लिए पूर्वानुकूलन का सबसे आम उपयोग है। सन्निकटन गुणवत्ता जितनी बेहतर होगी, मैट्रिक्स का आकार उतना ही बड़ा होगा। ऐसे मामले में, एक ओर, इष्टतम पूर्वानुकूलन का लक्ष्य वर्णक्रमीय स्थिति को संख्या बनाना है $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-डी समस्याओं के लिए विश्लेषण सॉफ्टवेयर में किया जाता है (EX:- 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 समस्याओं को कई वैकल्पिक तरीकों से तैयार किया जा सकता है, जिनमें से प्रत्येक अपनी पूर्व शर्त के लिए अग्रणी है। पारंपरिक पूर्व शर्त तथाकथित वर्णक्रमीय परिवर्तनों पर आधारित है। लक्षित eigenvalue (लगभग) जानने के बाद, संबंधित सजातीय रैखिक प्रणाली को हल करके संबंधित eigenvector की गणना कर सकते हैं, इस प्रकार रैखिक प्रणाली के लिए पूर्व शर्त का उपयोग करने की अनुमति मिलती है। अंत में, ईगेनवैल्यू समस्या को रेले भागफल के अनुकूलन के रूप में तैयार करने से दृश्य के लिए पूर्व शर्त वाली अनुकूलन तकनीकें सामने आती हैं।

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

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

सबसे लोकप्रिय स्पेक्ट्रल ट्रांसफॉर्मेशन तथाकथित शिफ्ट-एंड-इनवर्ट ट्रांसफॉर्मेशन है, जहां किसी दिए गए स्केलर के लिए $\alpha$, जिसे शिफ्ट कहा जाता है, मूल eigenvalue समस्या $Ax=\lambda x$ शिफ्ट-एंड-इनवर्ट समस्या से बदल दिया गया है $(A-\alpha I)^{-1}x=\mu x$. eigenvectors संरक्षित हैं, और एक पुनरावृत्त सॉल्वर, जैसे, शक्ति पुनरावृत्ति द्वारा शिफ्ट-एंड-इनवर्ट समस्या को हल कर सकते हैं। यह व्युत्क्रम पुनरावृत्ति देता है, जो आम तौर पर ईजेनवेक्टर में परिवर्तित हो जाता है, जो शिफ्ट के निकटतम ईजेनवेल्यू के अनुरूप होता है। $\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-(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=(diag(A))^{-1}$ या $T=(diag(A-\lambda _{n}I))^{-1}.$ आइगेनवैल्यू समस्याओं के कुछ वर्गों के लिए दक्षता $T\approx A^{-1}$ संख्यात्मक और सैद्धांतिक दोनों रूप से प्रदर्शित किया गया है। विकल्प $T\approx A^{-1}$ ईजेनवैल्यू समस्याओं के लिए आसानी से उपयोग करने की अनुमति देता है, रैखिक प्रणालियों के लिए विकसित किए गए विभिन्न प्रकार के प्रीकंडीशनर।

बदलते मूल्य के कारण $\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} )={\frac {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$, जबकि मिनिमाइज़र संबंधित आइजन्वेक्टर है। तब से $\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.$

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

स्रोत

• 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.). संख्यात्मक विश्लेषण: बीसवीं शताब्दी में ऐतिहासिक विकास. 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.
• के चेन: मैट्रिक्स प्रीकंडीशनिंग तकनीक और अनुप्रयोग, कैम्ब्रिज यूनिवर्सिटी प्रेस, ISBN 978-0521838283 (2005).

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