पुनरावृत्तीय तर्कसंगत क्रायलोव एल्गोरिदम

पुनरावृत्त तर्कसंगत क्रायलोव एल्गोरिदम (आईआरकेए) ऐसी पुनरावृत्त एल्गोरिदम है, जो सिंगल-इनपुट सिंगल-आउटपुट (एसआईएसओ) के रैखिक समय-अपरिवर्तनीय गतिशील प्रणालियों के प्रारूप के आधार पर ऑर्डर में होने वाली कमी (एमओआर) के लिए उपयोग की जाती है। इस प्रकार प्रत्येक पुनरावृत्ति पर, आईआरकेए मूल प्रणाली पर ट्रांसफर फलन का हर्माइट प्रकार का इंटरपोलेशन करता है। इसके कारण प्रत्येक $r$ वाले प्रक्षेप को हल करने की आवश्यकता होती है, इस प्रकार रैखिक प्रणालियों के स्थानांतरित जोड़े के लिए प्रत्येक $n\times n$ आकार के के लिए जहाँ $n$ मूल सिस्टम ऑर्डर है, और $r$ वांछित कम किया गया प्रारूप क्रम सामान्यतः इसका मान $r\ll n$ के समान रहता हैं।

एल्गोरिथ्म को पहली बार 2008 में गुगेर्सिन, एंटोलास और बीट्टी द्वारा प्रस्तुत किया गया था। इस प्रकार यह पहले क्रम की आवश्यक इष्टतमता स्थिति पर आधारित है, जिसके प्रारंभ में 1967 में मेयर और लुएनबर्गर द्वारा जांच की गई थी। इस प्रकार आईआरकेए का पहला अभिसरण प्रमाण विशेष प्रकार की प्रणालियों के लिए 2012 में फ्लैग, बीट्टी और गुगेर्सिन द्वारा दिया गया था।

अनुकूलन समस्या के रूप में एमओआर

इनपुट के साथ एसआईएसओ रैखिक समय-अपरिवर्तनीय गतिशील प्रणाली $v(t)$, और आउटपुट $y(t)$ पर विचार करें:

${\begin{cases}{\dot {x}}(t)=Ax(t)+bv(t)\\y(t)=c^{T}x(t)\end{cases}}\qquad A\in \mathbb {R} ^{n\times n},\,b,c\in \mathbb {R} ^{n},\,v(t),y(t)\in \mathbb {R} ,\,x(t)\in \mathbb {R} ^{n}.$

लाप्लास परिवर्तन को लागू करने पर, शून्य प्रारंभिक शर्तों के साथ हम स्थानांतरण फलन $G$ का मान प्राप्त करते हैं, जो इस प्रकार बहुपदों का अंश है:

$G(s)=c^{T}(sI-A)^{-1}b,\quad A\in \mathbb {R} ^{n\times n},\,b,c\in \mathbb {R} ^{n}.$

मान लीजिए $G$ स्थिर है, यहाँ दिया गया हैं कि $r<n$ होने पर एमओआर स्थानांतरण फलन $G$ का अनुमान लगाने का प्रयास करता है, इस प्रकार इसके लिए स्थिर तर्कसंगत स्थानांतरण फलन द्वारा $G_{r}$ का मान इसके लिए आदेशित $r$ के कारण इस प्रकार हैं:

$G_{r}(s)=c_{r}^{T}(sI_{r}-A_{r})^{-1}b_{r},\quad A_{r}\in \mathbb {R} ^{r\times r},\,b_{r},c_{r}\in \mathbb {R} ^{r}.$

संभावित मानदंड के लिए पूर्ण त्रुटि $H_{2}$ को कम करना सामान्य है:

$G_{r}\in {\underset {\dim({\hat {G}})=r,\,{\hat {G}}{\text{ stable}}}{\operatorname {arg\min } }}\|G-{\hat {G}}\|_{H_{2}},\quad \|G\|_{H_{2}}^{2}:={\frac {1}{2\pi }}\int \limits _{-\infty }^{\infty }|G(ja)|^{2}\,da.$

इसे $H_{2}$ के नाम से जाना जाता है, यहाँ पर अनुकूलन समस्या के लिए इसे बड़े पैमाने पर अध्ययन किया जाता है, और इस प्रकार इसे उत्तल के समान नहीं माना जाता है, जिसका तात्पर्य यह है कि सामान्यतः इसके लिए वैश्विक मिनिमाइज़र ढूंढना कठिन हो जाता हैं।

मायर-लुएनबर्गर स्थितियाँ

निम्नलिखित प्रथम क्रम के लिए आवश्यक इष्टतमता शर्त $H_{2}$ समस्या, आईआरकेए एल्गोरिथम के लिए बहुत महत्वपूर्ण है।

Theorem ([Theorem 3.4] [Theorem 1.2]) — मान लीजिए कि $H_{2}$ अनुकूलन समस्या एक समाधान स्वीकार करती है $G_{r}$ साधारण डंडों के साथ. इन ध्रुवों को इस प्रकार निरूपित करें: $\lambda _{1}(A_{r}),\ldots ,\lambda _{r}(A_{r})$. इस प्रकार $G_{r}$ का हर्माइट इंटरपोलेटर $G$ होना चाहिए, के परावर्तित ध्रुवों $G_{r}$ के माध्यम से :

$G_{r}(\sigma _{i})=G(\sigma _{i}),\quad G_{r}^{\prime }(\sigma _{i})=G^{\prime }(\sigma _{i}),\quad \sigma _{i}=-\lambda _{i}(A_{r}),\quad \forall \,i=1,\ldots ,r.$

यहाँ पर ध्यान दें कि ध्रुव $\lambda _{i}(A_{r})$ पर घटते हुए क्रम में आईजन मान ​​$r\times r$ आव्यूह पर $A_{r}$ के समान हैं।

हर्मिट इंटरपोलेशन

एक अन्तर्विभाजक साधु $G_{r}$ तर्कसंगत कार्य का $G$, के माध्यम से $r$ विशिष्ट बिंदु $\sigma _{1},\ldots ,\sigma _{r}\in \mathbb {C}$, के घटक को प्रदर्शित करती हैं:

$A_{r}=W_{r}^{*}AV_{r},\quad b_{r}=W_{r}^{*}b,\quad c_{r}=V_{r}^{*}c,\quad A_{r}\in \mathbb {R} ^{r\times r},\,b_{r}\in \mathbb {R} ^{r},\,c_{r}\in \mathbb {R} ^{r};$

जहां आव्यूह $V_{r}=(v_{1}\mid \ldots \mid v_{r})\in \mathbb {C} ^{n\times r}$ और $W_{r}=(w_{1}\mid \ldots \mid w_{r})\in \mathbb {C} ^{n\times r}$ के मान को हल करके $r$ का मान पाया जा सकता है, इसके लिए रैखिक प्रणालियों के दोहरे जोड़े में प्रत्येक पारी के लिए [प्रमेय 1.1] का पालन किया जाता हैं:

$(\sigma _{i}I-A)v_{i}=b,\quad (\sigma _{i}I-A)^{*}w_{i}=c,\quad \forall \,i=1,\ldots ,r.$

आईआरकेए एल्गोरिदम

जैसा कि पिछले अनुभाग से देखा जा सकता है, हर्मिट इंटरपोलेटर को ढूंढना $G_{r}$ का $G$, के माध्यम से $r$ दिए गए अंक के लिए अपेक्षाकृत सरल है। इस प्रकार इसका कठिन भाग सही प्रक्षेप बिंदु को ढूंढना है। जिसके लिए आईआरकेए इन इष्टतम इंटरपोलेशन बिंदुओं को पुनरावृत्त रूप से अनुमानित करने का प्रयास करता है।

इसके लिए $r$ इसकी प्रारंभ सीमा है, जिसके लिए यह स्वयं प्रक्षेपण बिंदु इस संयुग्मन के अनुसार बंद, और फिर इस प्रकार प्रत्येक पुनरावृत्ति पर $m$, यह पहले क्रम की आवश्यक इष्टतमता शर्त $H_{2}$ संकट लगाता है:

1. हर्मिट इंटरपोलेंट $G_{r}$ के लिए $G$ का मान प्राप्त करते हैं, इसके कारण वास्तविकता के माध्यम से $r$ शिफ्ट बिंदु: $\sigma _{1}^{m},\ldots ,\sigma _{r}^{m}$ प्राप्त होता हैं।

2. नए के ध्रुवों का उपयोग करके परिवर्तनों को अद्यतन $G_{r}$: $\sigma _{i}^{m+1}=-\lambda _{i}(A_{r}),\,\forall \,i=1,\ldots ,r.$ द्वारा प्राप्त करते हैं।

पुनरावृत्ति तब रोक दी जाती है जब दो क्रमिक पुनरावृत्तियों की पारियों के सेट में सापेक्ष परिवर्तन दी गई सहनशीलता से कम होती हैं। इस स्थिति को इस प्रकार बताया जा सकता है:

${\frac {|\sigma _{i}^{m+1}-\sigma _{i}^{m}|}{|\sigma _{i}^{m}|}}<{\text{tol}},\,\forall \,i=1,\ldots ,r.$

जैसा कि पहले ही उल्लेख किया गया है, प्रत्येक हर्मिट इंटरपोलेशन $r$ को हल करने की आवश्यकता होती है, इस प्रकार रैखिक प्रणालियों के स्थानांतरित जोड़े, प्रत्येक आकार $n\times n$ के लिए इस प्रकार हैं :

$(\sigma _{i}^{m}I-A)v_{i}=b,\quad (\sigma _{i}^{m}I-A)^{*}w_{i}=c,\quad \forall \,i=1,\ldots ,r.$

इसके साथ होने वाले परिवर्तनों को अपडेट करने के लिए इसे खोजने की आवश्यकता होती है, इस प्रकार $r$ इसके नए इंटरपोलेंट के ध्रुव $G_{r}$ अर्ताथ $r$ के घटते हुए मान के लिए आईजन मान $r\times r$ आव्यूह $A_{r}$ पर निर्भर करती हैं।

स्यूडोकोड

निम्नलिखित आईआरकेए एल्गोरिदम के लिए स्यूडोकोड है, [एल्गोरिदम 4.1]।

algorithm IRKA
    input: , ,  closed under conjugation
         % Solve primal systems
         % Solve dual systems

    while relative change in {} > tol
         % Reduced order matrix
         % Update shifts, using poles of 
         % Solve primal systems
         % Solve dual systems
    end while

    return $A_{r}=W_{r}^{*}AV_{r},\,b_{r}=W_{r}^{*}b,\,c_{r}^{T}=c^{T}V_{r}$ % Reduced order model

अभिसरण

एसआईएसओ रैखिक प्रणाली को सममित स्थिति के लिए इसका उचित स्थान एसएसएस कहा जाता है, जब भी इसका मान $A=A^{T},\,b=c.$ के समान होता है तो इस कारण इस प्रकार की प्रणालियाँ कई महत्वपूर्ण अनुप्रयोगों में दिखाई देती हैं, जैसे आरसी परिपथ के विश्लेषण में और 3डी मैक्सवेल के समीकरणों से जुड़ी व्युत्क्रम समस्याओं में इसका उपयोग होता हैं। इस प्रकार अलग-अलग ध्रुवों वाली एसएसएस प्रणालियों के लिए निम्नलिखित अभिसरण परिणाम सिद्ध हुआ है: आईआरकेए स्थानीय मिनिमाइज़र के लिए स्थानीय रूप से अभिसरण निश्चित बिंदु $H_{2}$ अनुकूलन समस्या की पुनरावृत्ति को प्रदर्शित करता है।

यद्यपि सामान्य स्थिति के लिए कोई अभिसरण प्रमाण नहीं है, इसके कई प्रयोगों से पता चला है कि आईआरकेए अधिकांशतः विभिन्न प्रकार की रैखिक गतिशील प्रणालियों के लिए तेजी से अभिसरण करता है।

एक्सटेंशन

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

यह भी देखें

प्रारूप ऑर्डर में कमी

बाहरी संबंध

• Model Order Reduction Wiki