Algoritmo iterativo racional de Krylov

El algoritmo iterativo racional de Krylov (IRKA) es un algoritmo iterativo, útil para la reducción de orden de modelo (MOR) de sistemas dinámicos lineales invariantes en el tiempo de una entrada y una salida (SISO) . ^{[ 1 ]} En cada iteración, IRKA realiza una interpolación de tipo Hermite de la función de transferencia del sistema original. Cada interpolación requiere resolver${\displaystyle r}$pares desplazados de sistemas lineales , cada uno de tamaño${\displaystyle n\times n}$; dónde${\displaystyle n}$es el orden del sistema original, y${\displaystyle r}$es el orden del modelo reducido deseado (generalmente${\displaystyle r\ll n}$).

El algoritmo fue presentado por primera vez por Gugercin, Antoulas y Beattie en 2008. ^{[ 2 ]} Se basa en una condición de optimalidad necesaria de primer orden, investigada inicialmente por Meier y Luenberger en 1967. ^{[ 3 ]} La primera prueba de convergencia de IRKA fue dada por Flagg, Beattie y Gugercin en 2012, ^{[ 4 ]} para un tipo particular de sistemas.

Consideremos un sistema dinámico lineal invariante en el tiempo SISO, con entrada${\displaystyle v(t)}$y salida${\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}.}$

Aplicando la transformada de Laplace , con condiciones iniciales nulas, obtenemos la función de transferencia.${\displaystyle G}$, que es una fracción de polinomios:

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

Asumir${\displaystyle G}$es estable. Dado${\displaystyle r<n}$MOR intenta aproximar la función de transferencia.${\displaystyle G}$mediante una función de transferencia racional estable${\displaystyle G_{r}}$, de orden${\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}.}$

Un posible criterio de aproximación es minimizar el error absoluto en${\displaystyle H_{2}}$norma:

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

Esto se conoce como el${\displaystyle H_{2}}$problema de optimización . Este problema ha sido estudiado extensamente y se sabe que no es convexo ^{[ 4 ],} lo que implica que normalmente será difícil encontrar un minimizador global.

La siguiente condición necesaria de optimalidad de primer orden para la${\displaystyle H_{2}}$Este problema es de gran importancia para el algoritmo IRKA.

Tenga en cuenta que los polos${\displaystyle \lambda _{i}(A_{r})}$son los valores propios de la reducida${\displaystyle r\times r}$matriz${\displaystyle A_{r}}$.

Un interpolante ermitaño${\displaystyle G_{r}}$de la función racional${\displaystyle G}$a través de${\displaystyle r}$puntos distintos${\displaystyle \sigma _{1},\ldots ,\sigma _{r}\in \mathbb {C} }$tiene componentes:

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

donde las matrices${\displaystyle V_{r}=(v_{1}\mid \ldots \mid v_{r})\in \mathbb {C} ^{n\times r}}$y${\displaystyle W_{r}=(w_{1}\mid \ldots \mid w_{r})\in \mathbb {C} ^{n\times r}}$se puede encontrar resolviendo${\displaystyle r}$pares duales de sistemas lineales, uno para cada desplazamiento ^{[ 4 ]} [Teorema 1.1]:

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

Como se puede ver en la sección anterior, encontrar un interpolador de Hermite${\displaystyle G_{r}}$de${\displaystyle G}$a través de${\displaystyle r}$La obtención de puntos de referencia es relativamente sencilla. La dificultad reside en encontrar los puntos de interpolación correctos. IRKA intenta aproximar iterativamente estos puntos de interpolación "óptimos".

Para ello, comienza con${\displaystyle r}$puntos de interpolación arbitrarios (cerrados bajo conjugación) y luego, en cada iteración${\displaystyle m}$, impone la condición de optimalidad necesaria de primer orden de la${\displaystyle H_{2}}$problema:

1. Hallar el interpolante de Hermite${\displaystyle G_{r}}$de${\displaystyle G}$a través de la realidad${\displaystyle r}$puntos de cambio:${\displaystyle \sigma _{1}^{m},\ldots ,\sigma _{r}^{m}}$.

2. Actualizar los desplazamientos utilizando los polos del nuevo${\displaystyle G_{r}}$:${\displaystyle \sigma _{i}^{m+1}=-\lambda _{i}(A_{r}),\,\forall \,i=1,\ldots ,r.}$

La iteración se detiene cuando el cambio relativo en el conjunto de desplazamientos de dos iteraciones sucesivas es menor que una tolerancia dada. Esta condición se puede expresar como:

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

Como ya se mencionó, cada interpolación de Hermite requiere resolver${\displaystyle r}$pares desplazados de sistemas lineales, cada uno de tamaño${\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.}$

Además, actualizar los turnos requiere encontrar el${\displaystyle r}$polos del nuevo interpolante${\displaystyle G_{r}}$. Es decir, encontrar el${\displaystyle r}$autovalores del reducido${\displaystyle r\times r}$matriz${\displaystyle A_{r}}$.

El siguiente es un pseudocódigo para el algoritmo IRKA ^{[ 2 ]} [Algoritmo 4.1].

Entrada del algoritmo IRKA :${\displaystyle A,b,c}$,${\displaystyle {\text{tol}}>0}$,${\displaystyle \sigma _{1},\ldots ,\sigma _{r}}$cerrado bajo conjugación ${\displaystyle (\sigma _{i}I-A)v_{i}=b,\,\forall \,i=1,\ldots ,r}$% Resolver sistemas primales ${\displaystyle (\sigma _{i}I-A)^{*}w_{i}=c,\,\forall \,i=1,\ldots ,r}$% Resolver sistemas duales mientras que el cambio relativo en {${\displaystyle \sigma _{i}}$} > tol ${\displaystyle A_{r}=W_{r}^{*}AV_{r}}$Matriz de orden reducido % ${\displaystyle \sigma _{i}=-\lambda _{i}(A_{r}),\,\forall \,i=1,\ldots ,r}$% Actualizar los cambios, usando polos de${\displaystyle G_{r}}$${\displaystyle (\sigma _{i}I-A)v_{i}=b,\,\forall \,i=1,\ldots ,r}$% Resolver sistemas primales ${\displaystyle (\sigma _{i}I-A)^{*}w_{i}=c,\,\forall \,i=1,\ldots ,r}$% Resuelve sistemas duales final mientrasdevolver${\displaystyle A_{r}=W_{r}^{*}AV_{r},\,b_{r}=W_{r}^{*}b,\,c_{r}^{T}=c^{T}V_{r}}$% Modelo de pedido reducido

Se dice que un sistema lineal SISO tiene un espacio de estados simétrico (SSS) cuando${\displaystyle A=A^{T},\,b=c.}$Este tipo de sistemas aparece en muchas aplicaciones importantes, como en el análisis de circuitos RC y en problemas inversos que involucran ecuaciones de Maxwell en 3D . ^{[ 4 ]} Para sistemas SSS con polos distintos, se ha demostrado el siguiente resultado de convergencia: ^{[ 4 ]} "IRKA es una iteración de punto fijo localmente convergente a un minimizador local de la${\displaystyle H_{2}}$problema de optimización."

Aunque no existe una prueba de convergencia para el caso general, numerosos experimentos han demostrado que IRKA a menudo converge rápidamente para diferentes tipos de sistemas dinámicos lineales. ^{[ 1 ] [ 4 ]}

El algoritmo IRKA ha sido extendido por los autores originales a sistemas de entrada múltiple y salida múltiple (MIMO), y también a sistemas de tiempo discreto y algebraicos diferenciales ^{[ 1 ] [ 2 ]} [Observación 4.1].

Reducción de orden de modelo

• Wiki de reducción de orden modelo