Iterative rational Krylov algorithm

Итерационный рациональный алгоритм Крылова (IRKA) — это итеративный алгоритм, полезный для понижения порядка модели (MOR) с одним входом и одним выходом линейных, инвариантных во времени динамических систем (SISO) . ^[1] На каждой итерации IRKA выполняет интерполяцию типа Эрмита исходной передаточной функции системы. Каждая интерполяция требует решения $r$ сдвинутые пары линейных систем , каждая размером $n\times n$ ; где $n$ - исходный системный порядок, и $r$ желаемый приведенный порядок модели (обычно $r\ll n$ ).

Алгоритм был впервые представлен Гугерсиным, Антуласом и Битти в 2008 году. ^[2] Он основан на необходимом условии оптимальности первого порядка, первоначально исследованном Мейером и Люенбергером в 1967 году. ^[3] Первое доказательство сходимости IRKA было предоставлено Флэггом, Битти и Гугерсином в 2012 году. ^[4] для определенного типа систем.

MOR как задача оптимизации

Рассмотрим линейную нестационарную динамическую систему SISO с входными данными $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$ , MOR пытается аппроксимировать передаточную функцию $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}$ оптимизации проблема . Эта проблема широко изучена, и известно, что она невыпуклая; ^[4] это означает, что обычно будет трудно найти глобальный минимизатор.

Условия Мейера – Люенбергера

Следующее необходимое условие оптимальности первого порядка для $H_{2}$ Проблема имеет большое значение для алгоритма IRKA.

Теорема ( ^[2][Теорема 3.4] ^[4][Теорема 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$ двойные пары линейных систем, по одной на каждую смену ^[4][Теорема 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$ учитывая очки, относительно легко. Сложнее всего найти правильные точки интерполяции. IRKA пытается итеративно аппроксимировать эти «оптимальные» точки интерполяции.

Для этого все начинается с $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}$ .

Псевдокод

Ниже приведен псевдокод алгоритма IRKA. ^[2][Алгоритм 4.1].

algorithm IRKA    input:  $A,b,c$ ,  ${\text{tol}}>0$ ,  $\sigma _{1},\ldots ,\sigma _{r}$  closed under conjugation         $(\sigma _{i}I-A)v_{i}=b,\,\forall \,i=1,\ldots ,r$  % Solve primal systems         $(\sigma _{i}I-A)^{*}w_{i}=c,\,\forall \,i=1,\ldots ,r$  % Solve dual systems    while relative change in { $\sigma _{i}$ } > tol         $A_{r}=W_{r}^{*}AV_{r}$  % Reduced order matrix         $\sigma _{i}=-\lambda _{i}(A_{r}),\,\forall \,i=1,\ldots ,r$  % Update shifts, using poles of  $G_{r}$          $(\sigma _{i}I-A)v_{i}=b,\,\forall \,i=1,\ldots ,r$  % Solve primal systems         $(\sigma _{i}I-A)^{*}w_{i}=c,\,\forall \,i=1,\ldots ,r$  % 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

Конвергенция

Говорят, что линейная система SISO имеет симметричное пространство состояний (SSS), когда: $A=A^{T},\,b=c.$ Системы этого типа встречаются во многих важных приложениях, например, при анализе RC-цепей и в обратных задачах, включающих трехмерные уравнения Максвелла . ^[4] Для систем НДС с разными полюсами доказан следующий результат сходимости: ^[4] «IRKA — это локально сходящаяся итерация с фиксированной точкой для локального минимизатора $H_{2}$ проблема оптимизации».

Хотя для общего случая нет доказательства сходимости, многочисленные эксперименты показали, что IRKA часто сходится быстро для различных типов линейных динамических систем. ^[1]^[4]

Расширения

Алгоритм IRKA был расширен первоначальными авторами на системы с несколькими входами и многими выходами (MIMO), а также на дискретные и дифференциально-алгебраические системы. ^[1]^[2][Замечание 4.1].

См. также

Уменьшение порядка модели

Ссылки

^ Jump up to: ^а ^б ^с «Итерационный рациональный алгоритм Крылова» . МОР Wiki . Проверено 3 июня 2021 г.
^ Jump up to: ^а ^б ^с ^д Гугерцин, С.; Антулас, AC ; Битти, К. (2008). $H_{2}$ Редукция модели для крупномасштабных линейных динамических систем , Журнал матричного анализа и приложений, том. 30, СИАМ, стр. 609–638.
^ Л. Мейер; Д. Г. Люенбергер (1967), Приближение систем линейных констант , Транзакции IEEE по автоматическому управлению, том. 12, стр. 585–588.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Г. Флэгг; К. Битти; С. Гугерчин (2012), Сходимость итеративного рационального алгоритма Крылова , Системы и управляющие буквы, т. 1, с. 61, стр. 688–691.

Внешние ссылки

Сокращение заказа модели вики

[mor_wiki_2021-1] Jump up to: ^а ^б ^с «Итерационный рациональный алгоритм Крылова» . МОР Wiki . Проверено 3 июня 2021 г.

[gugercin_2008-2] Jump up to: ^а ^б ^с ^д Гугерцин, С.; Антулас, AC ; Битти, К. (2008). $H_{2}$ Редукция модели для крупномасштабных линейных динамических систем , Журнал матричного анализа и приложений, том. 30, СИАМ, стр. 609–638.

[meier_1967-3] Л. Мейер; Д. Г. Люенбергер (1967), Приближение систем линейных констант , Транзакции IEEE по автоматическому управлению, том. 12, стр. 585–588.

[flagg_2012-4] Jump up to: ^а ^б ^с ^д ^и ^ж ^г Г. Флэгг; К. Битти; С. Гугерчин (2012), Сходимость итеративного рационального алгоритма Крылова , Системы и управляющие буквы, т. 1, с. 61, стр. 688–691.

[1]

[2]

[3]

[4]