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

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

Theorem ([Theorem 3.4] [Theorem 1.2]) —  Assume that the $H_{2}$ optimization problem admits a solution $G_{r}$ with simple poles. Denote these poles by: $\lambda _{1}(A_{r}),\ldots ,\lambda _{r}(A_{r})$. Then, $G_{r}$ must be an Hermite interpolator of $G$, through the reflected poles of $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})$ घटे हुए के eigenvalues ​​हैं $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$ घटे हुए के eigenvalues $r\times r$ आव्यूह $A_{r}$.

स्यूडोकोड

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

एचआरसीए एल्गोरिथ्म
 इनपुट: $A,b,c$, ${\text{tol}}>0$, $\sigma _{1},\ldots ,\sigma _{r}$ संयुग्मन के तहत बंद 

$(\sigma _{i}I-A)v_{i}=b,\,\forall \,i=1,\ldots ,r$ % मौलिक प्रणालियों को हल करें $(\sigma _{i}I-A)^{*}w_{i}=c,\,\forall \,i=1,\ldots ,r$ % दोहरी प्रणालियों को हल करें

 जबकि सापेक्ष परिवर्तन {$\sigma _{i}$} > टोल 

$A_{r}=W_{r}^{*}AV_{r}$ % कम ऑर्डर मैट्रिक्स $\sigma _{i}=-\lambda _{i}(A_{r}),\,\forall \,i=1,\ldots ,r$ पोल्स का उपयोग करके % अपडेट शिफ्ट $G_{r}$

 $(\sigma _{i}I-A)v_{i}=b,\,\forall \,i=1,\ldots ,r$ % मौलिक प्रणालियों को हल करें 

$(\sigma _{i}I-A)^{*}w_{i}=c,\,\forall \,i=1,\ldots ,r$ % दोहरी प्रणालियों को हल करें

 समय समाप्त करें

 वापस करना $A_{r}=W_{r}^{*}AV_{r},\,b_{r}=W_{r}^{*}b,\,c_{r}^{T}=c^{T}V_{r}$ % कम ऑर्डर मॉडल

अभिसरण

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

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

एक्सटेंशन

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

यह भी देखें

मॉडल ऑर्डर में कमी

बाहरी संबंध

• Model Order Reduction Wiki