反復有理クリロフアルゴリズム

反復有理クリロフアルゴリズム（IRKA）は、単入力単出力（SISO）線形時間不変動的システムのモデル次数削減（MOR）に有用な反復アルゴリズムです。^[1]各反復で、IRKAは元のシステム伝達関数のエルミート型補間を行います。各補間では、サイズが の線形システムのシフトされたペアを解く必要があります。ここで、は元のシステム次数、 は目的の削減モデル次数（通常は ）です。 ${\displaystyle r}$${\displaystyle n\times n}$${\displaystyle n}$${\displaystyle r}$${\displaystyle r\ll n}$

このアルゴリズムは、2008年にGugercin、Antoulas、Beattieによって初めて導入されました。^[2]これは、1967年にMeierとLuenbergerによって最初に調査された第1次の必要最適条件に基づいています。^[3] IRKAの最初の収束証明は、2012年にFlagg、Beattie、Gugercinによって特定の種類のシステムに対して 与えられました。 ^[4]

入力、出力を持つ SISO 線形時間不変動的システムを考えます。 ${\displaystyle v(t)}$${\displaystyle y(t)}$

${\displaystyle {\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}.}$

初期条件がゼロのラプラス変換を適用すると、多項式の分数である 伝達関数が得られます。 ${\displaystyle G}$

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

は安定していると仮定します。 が与えられた場合、MOR は伝達関数 を次の次数の安定した有理伝達関数 で近似しようとします。 ${\displaystyle G}$${\displaystyle r<n}$${\displaystyle G}$${\displaystyle G_{r}}$${\displaystyle r}$

${\displaystyle 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}.}$

可能な近似基準は、ノルム の絶対誤差を最小化することです。${\displaystyle H_{2}}$

${\displaystyle 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.}$

これは最適化問題として知られています。この問題は広く研究されており、非凸であることが知られています。^[4]つまり、通常は大域的最小値を見つけることは困難です。 ${\displaystyle H_{2}}$

この問題に対する次の第一次の必要最適条件は、IRKA アルゴリズムにとって非常に重要です。 ${\displaystyle H_{2}}$

極は簡約された行列の固有値であることに注意してください。 ${\displaystyle \lambda _{i}(A_{r})}$${\displaystyle r\times r}$${\displaystyle A_{r}}$

異なる点を通る有理関数 のエルミート補間式には、次の要素があります。 ${\displaystyle G_{r}}$${\displaystyle G}$${\displaystyle r}$${\displaystyle \sigma _{1},\ldots ,\sigma _{r}\in \mathbb {C} }$

${\displaystyle 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};}$

ここで、行列と行列は、各シフトごとに1つずつ、線形システムの双対を解くことによって見つけることができる^[4] [定理1.1]： ${\displaystyle V_{r}=(v_{1}\mid \ldots \mid v_{r})\in \mathbb {C} ^{n\times r}}$${\displaystyle W_{r}=(w_{1}\mid \ldots \mid w_{r})\in \mathbb {C} ^{n\times r}}$${\displaystyle r}$

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

前のセクションからわかるように、与えられた点を通るのエルミート補間を見つけることは比較的簡単です。難しいのは、正しい補間点を見つけることです。IRKA は、これらの「最適な」補間点を反復的に近似しようとします。 ${\displaystyle G_{r}}$${\displaystyle G}$${\displaystyle r}$

このため、任意の補間点（共役に対して閉じている）から開始し、各反復で、問題の1次の必要な最適性条件を課します。 ${\displaystyle r}$${\displaystyle m}$${\displaystyle H_{2}}$

1.実際のシフトポイントを通るのエルミート補間関数を求めます。 ${\displaystyle G_{r}}$${\displaystyle G}$${\displaystyle r}$${\displaystyle \sigma _{1}^{m},\ldots ,\sigma _{r}^{m}}$

2. 新しいの極を使用してシフトを更新します。${\displaystyle G_{r}}$${\displaystyle \sigma _{i}^{m+1}=-\lambda _{i}(A_{r}),\,\forall \,i=1,\ldots ,r.}$

2 つの連続する反復のシフト セットの相対的な変化が指定された許容値よりも小さい場合、反復は停止されます。この条件は次のように表すことができます。

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

すでに述べたように、各エルミート補間では、サイズが である線形システムのシフトされたペアを解く必要があります。 ${\displaystyle r}$${\displaystyle n\times n}$

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

また、シフトを更新するには、新しい補間関数の極を見つける必要があります。つまり、縮小された行列の固有値を見つける必要があります。 ${\displaystyle r}$${\displaystyle G_{r}}$${\displaystyle r}$${\displaystyle r\times r}$${\displaystyle A_{r}}$

以下はIRKAアルゴリズム^[2] [アルゴリズム4.1]の疑似コードである。

アルゴリズムIRKA
    入力: 、、共役で閉じている
         % 主システムを解く
         % 双対システムを解く${\displaystyle A,b,c}$${\displaystyle {\text{tol}}>0}$${\displaystyle \sigma _{1},\ldots ,\sigma _{r}}$${\displaystyle (\sigma _{i}I-A)v_{i}=b,\,\forall \,i=1,\ldots ,r}$${\displaystyle (\sigma _{i}I-A)^{*}w_{i}=c,\,\forall \,i=1,\ldots ,r}$

    相対変化 { } > tol
          % 行列の次元を縮小
         % シフトを更新、極を使用 % 主システムを解く
         % 双対システムを解く
    end while${\displaystyle \sigma _{i}}$${\displaystyle A_{r}=W_{r}^{*}AV_{r}}$${\displaystyle \sigma _{i}=-\lambda _{i}(A_{r}),\,\forall \,i=1,\ldots ,r}$${\displaystyle G_{r}}$
        ${\displaystyle (\sigma _{i}I-A)v_{i}=b,\,\forall \,i=1,\ldots ,r}$${\displaystyle (\sigma _{i}I-A)^{*}w_{i}=c,\,\forall \,i=1,\ldots ,r}$

    リターン  % 縮小順序モデル
${\displaystyle A_{r}=W_{r}^{*}AV_{r},\,b_{r}=W_{r}^{*}b,\,c_{r}^{T}=c^{T}V_{r}}$

SISO 線形システムは、次の場合に対称状態空間 (SSS) を持つと言われます。このタイプのシステムは、RC 回路の解析や 3Dマクスウェル方程式を含む逆問題など、多くの重要なアプリケーションで使用されます。^[4]異なる極を持つ SSS システムの場合、次の収束結果が証明されています。^[4]「IRKA は、最適化問題の局所的最小化に対する局所的に収束する固定点反復です。」 ${\displaystyle A=A^{T},\,b=c.}$${\displaystyle H_{2}}$

一般的なケースでは収束の証明はないが、多くの実験により、IRKAはさまざまな種類の線形動的システムに対して急速に収束することがわかっている。^{[1] [4]}

IRKAアルゴリズムは、オリジナルの著者によって、多入力多出力（MIMO）システム、離散時間システム、微分代数システムにも拡張されている^{[1] [2]} [注4.1]。

モデル次数削減

• モデル次数削減 Wiki