Iterative Rational Krylov Algorithm: Difference between revisions

Help

Revision as of 07:10, 30 May 2013

Description

The iterative rational Krylov algorithm (IRKA) is an interpolation-based model reduction method for single-input-single-output linear time invariant systems

\dot{x} (t) = A x (t) + b u (t), y (t) = c^{T} x (t), E, A \in ℝ^{n \times n}, b \in ℝ^{n}, c \in ℝ^{n} . (1)

(1)

For a given system $G$ and a prescribed reduced system order $r$ , the goal of the algorithm is to find a local minimizer $\hat{G}$ for the $H_{2}$ model reduction problem

| | G - \hat{G} | |_{H_{2}} = \min_{dim (\tilde{G}) = r} | | G - \hat{G} | |_{H_{2}} .

Initially investigated in ^[1], first order necessary conditions for a local minimizer $\hat{G}$ imply that its rational transfer function $\hat{G} (s) = {\hat{c}}^{T} (s I - \hat{A})^{- 1} b$ is a Hermite interpolant of the original transfer function at its reflected system poles, i.e.,

G (- {\hat{λ}}_{i}) = \hat{G} (- {\hat{λ}}_{i}), G^{'} (- {\hat{λ}}_{i}) = {\hat{G}}^{'} (- {\hat{λ}}_{i}),, i = 1, \dots, r,

where ${{\hat{λ}}_{1}, \dots, {\hat{λ}}_{r}}$ are assumed to be the simple poles of $\hat{G}$ . Based on the idea of rational interpolation by rational Krylov subspaces, in ^[2] the authors have picked up the optimality conditions and proposed to iteratively correct projection subspaces until interpolation is ensured. In pseudocode, the classical algorithm (IRKA) from ^[2] looks like

1. Make an initial selection of  $σ_{i}$  for  $i = 1, \dots, r$  that is closed under conjugation and fix a convergence tolerance  $t o l$ .
2. Choose  $V_{r}$  and  $W_{r}$  so that  $Ran (V_{r}) = {(σ_{1} I - A)^{- 1} b, \dots, (σ_{r} I - A)^{- 1} b}$ ,  $Ran (W_{r}) = {(σ_{1} I - A^{T})^{- 1} c, \dots, (σ_{r} I - A^{T})^{- 1} c}$  and  $W_{r}^{T} V_{r} = I$ .
3. while (relative change in  ${σ_{i}} > t o l$ )
 (a)  $\hat{A} = W_{r}^{T} A V_{r}$ 
 (b) Assign  $σ_{i} \leftarrow - λ_{i} (\hat{A}),$  for  $i = 1, \dots, r$ 
 (c) Update  $V_{r}$  and  $W_{r}$  so that  $Ran (V_{r}) = {(σ_{1} I - A)^{- 1} b, \dots, (σ_{r} I - A)^{- 1} b}$ ,  $Ran (W_{r}) = {(σ_{1} I - A^{T})^{- 1} c, \dots, (σ_{r} I - A^{T})^{- 1} c}$  and  $W_{r}^{T} V_{r} = I$ .
4.  $\hat{A} = W_{r}^{T} A V_{r}, \hat{b} = W_{r}^{T} b, {\hat{c}}^{T} = c^{T} V_{r} .$

Although a rigorous convergence proof so far has only be given for symmetric state space systems ^[3], numerous experiments have shown that the algorithm often converges rapidly.

References

^[1]

^[2]

^[3]

</ references>

↑ ^1.0 ^1.1 L. Meier, D.G. Luenberger, "Approximation of linear constant systems", IEEE Transactions on Automatic Control, vol.12, no.5, pp.585-588 1967
↑ ^2.0 ^2.1 ^2.2 S. Gugercin, A.C. Antoulas, C. Beattie "H2 Model Reduction for Large-Scale Linear Dynamical Systems", SIAM. J. Matrix Anal. & Appl., vol.30, no.2, pp.609-638 2008
↑ ^3.0 ^3.1 G. Flagg, C. Beattie, S. Gugercin "Convergence of the Iterative Rational Krylov Algorithm", Systems & Control Letters, vol.61, no.6, pp.688-691 2012

[MeiL67-1] 1.0 ^1.1 L. Meier, D.G. Luenberger, "Approximation of linear constant systems", IEEE Transactions on Automatic Control, vol.12, no.5, pp.585-588 1967

[GugAB08-2] 2.0 ^2.1 ^2.2 S. Gugercin, A.C. Antoulas, C. Beattie "H2 Model Reduction for Large-Scale Linear Dynamical Systems", SIAM. J. Matrix Anal. & Appl., vol.30, no.2, pp.609-638 2008

[FlaBG12-3] 3.0 ^3.1 G. Flagg, C. Beattie, S. Gugercin "Convergence of the Iterative Rational Krylov Algorithm", Systems & Control Letters, vol.61, no.6, pp.688-691 2012

[1]

[2]

[3]

@@ Line 27: / Line 27: @@
 G(-\hat{\lambda}_i) = \hat{G}(-\hat{\lambda}_i), \quad G'(-\hat{\lambda}_i) = \hat{G}'(-\hat{\lambda}_i), \quad, i =1,\dots,r,
 </math>
-where <math>\{\hat{\lambda}_1,\dots,\hat{\lambda}_r\} </math> are assumed to be the simple poles of <math> \hat{G} </math>. Based on the idea of rational interpolation by rational Krylov subspaces, in <ref name="GugAB08"></ref> the authors have picked up the optimality conditions and proposed to iteratively correct the projection subspaces. In pseudocode, the classical algorithm (IRKA) from <ref name="GugAB08"></ref> looks like
+where <math>\{\hat{\lambda}_1,\dots,\hat{\lambda}_r\} </math> are assumed to be the simple poles of <math> \hat{G} </math>. Based on the idea of rational interpolation by rational Krylov subspaces, in <ref name="GugAB08"></ref> the authors have picked up the optimality conditions and proposed to iteratively correct projection subspaces until interpolation is ensured. In pseudocode, the classical algorithm (IRKA) from <ref name="GugAB08"></ref> looks like
 . Make an initial selection of <math>\sigma_i </math> for <math>i=1,\dots,r </math> that is closed under conjugation and fix a convergence tolerance <math>tol</math>.