Неявный метод чередующегося направления

В числовой линейной алгебре неявный метод чередования направлений (ADI) представляет собой итерационный метод, используемый для решения матричных уравнений Сильвестра . Это популярный метод решения больших матричных уравнений, возникающих в теории систем и управлении . и может быть сформулирован для построения решений в эффективно использующей память факторизованной форме. Он также используется для численного решения параболических и эллиптических уравнений в частных производных и является классическим методом, используемым для моделирования теплопроводности и решения уравнения диффузии в двух или более измерениях. Это пример метода разделения операторов .

ADI для матричных уравнений

Метод

Метод ADI представляет собой двухэтапный итерационный процесс, который поочередно обновляет пространства столбцов и строк приближенного решения до $AX-XB=C$. Одна итерация ADI состоит из следующих шагов:

1. Решите $X^{(j+1/2)}$, где $\left(A-\beta _{j+1}I\right)X^{(j+1/2)}=X^{(j)}\left(B-\beta _{j+1}I\right)+C.$

2. Решите $X^{(j+1)}$, где $X^{(j+1)}\left(B-\alpha _{j+1}I\right)=\left(A-\alpha _{j+1}I\right)X^{(j+1/2)}-C$.

Числа $(\alpha _{j+1},\beta _{j+1})$ называются параметрами сдвига, и сходимость сильно зависит от выбора этих параметров. Чтобы выполнить $K$ итерации ADI, первоначальное предположение $X^{(0)}$ требуется, а также $K$ параметры переключения, $\{(\alpha _{j},\beta _{j})\}_{j=1}^{K}$.

Когда использовать ADI

Если $A\in \mathbb {C} ^{m\times m}$ и $B\in \mathbb {C} ^{n\times n}$, затем $AX-XB=C$ можно решить непосредственно в ${\mathcal {O}}(m^{3}+n^{3})$ с использованием метода Бартельса-Стюарта . Поэтому использовать ADI выгодно только при умножении матрицы на вектор и линейном решении, включающем $A$ и $B$ можно применять дешево.

Уравнение $AX-XB=C$ имеет единственное решение тогда и только тогда, когда $\sigma (A)\cap \sigma (B)=\emptyset$, где $\sigma (M)$ это спектр ​ $M$. Однако метод ADI особенно эффективен, когда $\sigma (A)$ и $\sigma (B)$ хорошо разделены и $A$ и $B$ являются нормальными матрицами . Этим предположениям удовлетворяет, например, уравнение Ляпунова $AX+XA^{*}=C$ когда $A$ является положительно определенным . При этих предположениях близкие к оптимальным параметры сдвига известны для нескольких вариантов выбора. $A$ и $B$. Кроме того, можно вычислить априорные границы ошибок, тем самым устраняя необходимость контролировать остаточную ошибку при реализации.

Метод ADI все еще можно применять, если вышеуказанные допущения не выполняются. Использование неоптимальных параметров сдвига может отрицательно повлиять на сходимость. и на сходимость также влияет ненормальность $A$ или $B$ (иногда выгодно). Методы подпространств Крылова , такие как метод рационального подпространства Крылова, в этих условиях обычно сходятся быстрее, чем ADI, и это привело к развитию гибридных методов ADI-проецирования.

Выбор параметра сдвига и уравнение ошибки ADI

Проблема поиска хороших параметров сдвига нетривиальна. Эту проблему можно понять, изучив уравнение ошибки ADI. После $K$ итераций, ошибка определяется выражением

$X-X^{(K)}=\prod _{j=1}^{K}{\frac {(A-\alpha _{j}I)}{(A-\beta _{j}I)}}\left(X-X^{(0)}\right)\prod _{j=1}^{K}{\frac {(B-\beta _{j}I)}{(B-\alpha _{j}I)}}.$

Выбор $X^{(0)}=0$ приводит к следующей оценке относительной ошибки:

${\frac {\left\|X-X^{(K)}\right\|_{2}}{\|X\|_{2}}}\leq \|r_{K}(A)\|_{2}\|r_{K}(B)^{-1}\|_{2},\quad r_{K}(M)=\prod _{j=1}^{K}{\frac {(M-\alpha _{j}I)}{(M-\beta _{j}I)}}.$

где $\|\cdot \|_{2}$ является операторной нормой . Идеальный набор параметров переключения передач $\{(\alpha _{j},\beta _{j})\}_{j=1}^{K}$ определяет рациональную функцию $r_{K}$ что минимизирует количество $\|r_{K}(A)\|_{2}\|r_{K}(B)^{-1}\|_{2}$. Если $A$ и $B$ являются нормальными матрицами и имеют собственные разложения $A=V_{A}\Lambda _{A}V_{A}^{*}$ и $B=V_{B}\Lambda _{B}V_{B}^{*}$, затем

$\|r_{K}(A)\|_{2}\|r_{K}(B)^{-1}\|_{2}=\|r_{K}(\Lambda _{A})\|_{2}\|r_{K}(\Lambda _{B})^{-1}\|_{2}$.

Параметры переключения, близкие к оптимальным

В некоторых случаях известны почти оптимальные параметры сдвига, например, когда $\Lambda _{A}\subset [a,b]$ и $\Lambda _{B}\subset [c,d]$, где $[a,b]$ и $[c,d]$ являются непересекающимися интервалами на действительной прямой. Уравнение Ляпунова $AX+XA^{*}=C$, например, удовлетворяет этим предположениям, когда $A$ является положительно определенным . В этом случае параметры сдвига можно выразить в замкнутой форме с помощью эллиптических интегралов и легко вычислить численно.

В более общем смысле, если замкнутые, непересекающиеся множества $E$ и $F$, где $\Lambda _{A}\subset E$ и $\Lambda _{B}\subset F$, задача выбора оптимального параметра сдвига приближенно решается путем нахождения экстремальной рациональной функции, достигающей значения

$Z_{K}(E,F):=\inf _{r}{\frac {\sup _{z\in E}|r(z)|}{\inf _{z\in F}|r(z)|}},$

где нижняя грань берется по всем рациональным функциям степени $(K,K)$. Эта задача аппроксимации связана с несколькими результатами теории потенциала : и была решена Золотаревым в 1877 г. $E$ = [а, b] и $F=-E.$ Решение также известно, когда $E$ и $F$ представляют собой непересекающиеся диски в комплексной плоскости.

Эвристические стратегии сдвига параметров

Когда о нем известно меньше $\sigma (A)$ и $\sigma (B)$, или когда $A$ или $B$ являются ненормальными матрицами, может оказаться невозможным найти почти оптимальные параметры сдвига. В этой ситуации можно использовать различные стратегии для создания хороших параметров переключения. К ним относятся стратегии, основанные на асимптотических результатах теории потенциала, используя значения Ритца матриц $A$, $A^{-1}$, $B$, и $B^{-1}$ сформулировать жадный подход, и циклические методы, в которых один и тот же небольшой набор параметров сдвига используется повторно до тех пор, пока не будет достигнут допуск сходимости. Когда на каждой итерации используется один и тот же параметр сдвига, ADI эквивалентен алгоритму, называемому методом Смита.

Факторизованный ADI

Во многих приложениях $A$ и $B$ очень большие, разреженные матрицы, и $C$ может быть факторизован как $C=C_{1}C_{2}^{*}$, где $C_{1}\in \mathbb {C} ^{m\times r},C_{2}\in \mathbb {C} ^{n\times r}$, с $r=1,2$. В такой ситуации может оказаться невозможным сохранить потенциально плотную матрицу. $X$ явно. Вариант ADI, называемый факторизованным ADI, можно использовать для вычисления $ZY^{*}$, где $X\approx ZY^{*}$. Эффективность факторизованного ADI зависит от того, $X$ хорошо аппроксимируется матрицей низкого ранга. Известно, что это верно при различных предположениях о $A$ и $B$.

ADI для параболических уравнений

Исторически метод ADI был разработан для решения двумерного уравнения диффузии в квадратной области с использованием конечных разностей. В отличие от ADI для матричных уравнений, ADI для параболических уравнений не требует выбора параметров сдвига, поскольку сдвиг, возникающий на каждой итерации, определяется такими параметрами, как временной шаг, коэффициент диффузии и шаг сетки. Связь с ADI в матричных уравнениях можно наблюдать, если рассмотреть действие итерации ADI на систему в установившемся состоянии.

Пример: двумерное уравнение диффузии

Трафарет для неявного метода знакопеременного направления в конечно-разностных уравнениях

Традиционным методом численного решения уравнения теплопроводности является метод Кранка-Николсона . Этот метод приводит к очень сложному набору уравнений в нескольких измерениях, решение которых требует больших затрат. Преимущество метода ADI состоит в том, что уравнения, которые необходимо решить на каждом этапе, имеют более простую структуру и могут быть эффективно решены с помощью алгоритма трехдиагональной матрицы .

Рассмотрим линейное уравнение диффузии в двух измерениях:

${\partial u \over \partial t}=\left({\partial ^{2}u \over \partial x^{2}}+{\partial ^{2}u \over \partial y^{2}}\right)=(u_{xx}+u_{yy})$

Неявный метод Кранка – Николсона дает следующее конечно-разностное уравнение:

${u_{ij}^{n+1}-u_{ij}^{n} \over \Delta t}={1 \over 2(\Delta x)^{2}}\left(\delta _{x}^{2}+\delta _{y}^{2}\right)\left(u_{ij}^{n+1}+u_{ij}^{n}\right)$

где:

$\Delta x=\Delta y$

и $\delta _{p}^{2}$ — центральный оператор второй разности для p -й координаты

$\delta _{p}^{2}u_{ij}=u_{ij+e_{p}}-2u_{ij}+u_{ij-e_{p}}$

с $e_{p}=10$ или $01$ для $p=x$ или $y$ соответственно (и $ij$ сокращение для точек решетки $(i,j)$).

После выполнения анализа устойчивости можно показать, что этот метод будет стабилен для любого $\Delta t$.

Недостатком метода Кранка – Николсона является то, что матрица в приведенном выше уравнении имеет полосовую ширину, которая обычно довольно велика. Это делает прямое решение системы линейных уравнений весьма дорогостоящим (хотя существуют эффективные приближенные решения, например, использование метода сопряженных градиентов, обусловленного неполной факторизацией Холецкого ).

Идея метода ADI состоит в том, чтобы разбить конечно-разностные уравнения на два: одно с неявно взятой производной по x , а другое с неявно взятой производной по y :

${u_{ij}^{n+1/2}-u_{ij}^{n} \over \Delta t/2}={\left(\delta _{x}^{2}u_{ij}^{n+1/2}+\delta _{y}^{2}u_{ij}^{n}\right) \over \Delta x^{2}}$

${u_{ij}^{n+1}-u_{ij}^{n+1/2} \over \Delta t/2}={\left(\delta _{x}^{2}u_{ij}^{n+1/2}+\delta _{y}^{2}u_{ij}^{n+1}\right) \over \Delta y^{2}}$

Используемая система уравнений является симметричной и трехдиагональной (с полосой пропускания 3) и обычно решается с использованием алгоритма трехдиагональной матрицы .

Можно показать, что этот метод безусловно устойчив и имеет второй порядок во времени и пространстве. Существуют более совершенные методы ADI, такие как методы Дугласа, или метод f-фактора который можно использовать для трех или более измерений.

Обобщения

Использование метода ADI в качестве схемы разделения операторов можно обобщить. То есть мы можем рассматривать общие эволюционные уравнения

${\dot {u}}=F_{1}u+F_{2}u,$

где $F_{1}$ и $F_{2}$ являются (возможно, нелинейными) операторами, определенными в банаховом пространстве. В приведенном выше примере диффузии мы имеем $F_{1}={\partial ^{2} \over \partial x^{2}}$ и $F_{2}={\partial ^{2} \over \partial y^{2}}$.

Фундаментальный ADI (FADI)

Упрощение ADI до FADI

Можно упростить традиционный метод ADI до фундаментального метода ADI, который имеет аналогичные операторы только в левой части и не содержит операторов в правой части. Это можно рассматривать как фундаментальную (базовую) схему метода ADI. без дополнительных операторов (которые нужно сократить) в правых частях, в отличие от большинства традиционных неявных методов, которые обычно состоят из операторов в обеих частях уравнений. Метод FADI приводит к более простым, кратким и эффективным уравнениям обновления без ухудшения точности традиционного метода ADI.

Отношения с другими неявными методами

Многие классические неявные методы Писмана-Рэчфорда, Дугласа-Ганна, Д'Яконова, Бима-Уорминга, Крэнка-Николсона и т. д. можно упростить до фундаментальных неявных схем с безоператорными правыми частями. В своих фундаментальных формах метод FADI временной точности второго порядка может быть тесно связан с фундаментальным локально-одномерным методом (FLOD), который может быть повышен до временной точности второго порядка, например, для трехмерных уравнений Максвелла. в вычислительной электромагнетике . Для двумерных и трехмерных уравнений теплопроводности и диффузии методы FADI и FLOD могут быть реализованы более простым, эффективным и стабильным способом по сравнению с их традиционными методами.