Неявный метод с переменным направлением

В числовой линейной алгебре , то неявный метод переменных направлений (ДСП) представляет собой итеративный метод , используемый для решения матричных уравнений Сильвестра . Это популярный метод для решения больших матричных уравнений, возникающих в теории систем и управлении , ^[1] и может быть сформулировано для построения решения в памяти эффективной, разложенном виде. ^{[2] [3]} Он также используется для численного решения параболических и эллиптических уравнений в частных производных и представляет собой классический метод, используемый для моделирования теплопроводности и решения уравнения диффузии.в двух или более измерениях. ^[4] Это пример метода разделения операторов . ^[5]

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

Метод [ править ]

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

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

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

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

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

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

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

Метод ADI все еще может применяться, когда вышеприведенные предположения не выполняются. Использование субоптимальных параметров сдвига может отрицательно повлиять на сходимость ^[1], и на сходимость также влияет ненормальность или (иногда предпочтительно). ^[10] Методы подпространства Крылова , такие как Рациональный метод подпространств Крылова, ^[11], как правило, сходятся быстрее, чем ADI в этой настройке, ^{[1] [3],} и это привело к развитию гибридных методов ADI-проекции. . ^[3]${\displaystyle A}$${\displaystyle B}$

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

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

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

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

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

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

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

Почти оптимальные параметры смены [ править ]

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

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

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

где нижняя грань берется по всем рациональным функциям степени . ^[8] Эта проблема аппроксимации связана с несколькими результатов в теории потенциала , ^{[12] [13]} и был решен Золотарёвым в 1877 г. для = [а, Ь] и ^[14] Решение также известно , когда и непересекающиеся диски в комплексная плоскость. ^[15]${\displaystyle (K,K)}$${\displaystyle E}$${\displaystyle F=-E.}$${\displaystyle E}$${\displaystyle F}$

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

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

Фактор ADI [ править ]

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

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

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

Пример: двумерное уравнение диффузии [ править ]

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

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

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

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

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

где:

${\displaystyle \Delta x=\Delta y}$

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

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

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

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

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

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

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

${\displaystyle {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) и обычно решается с использованием алгоритма трехдиагональной матрицы .

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

Обобщения [ править ]

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

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

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

Фундаментальный ADI (FADI) [ править ]

Упрощение ADI до FADI [ править ]

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

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

Многие классические неявные методы Пичмана-Рачфорда, Дугласа-Ганна, Д'Яконова, Луча-Уорминга, Крэнка-Николсона и т. Д. Могут быть упрощены до фундаментальных неявных схем с правыми частями без операторов. ^[25] В своих основных формах метод временной точности FADI второго порядка может быть тесно связан с фундаментальным методом локально-одномерного (FLOD), который может быть повышен до временной точности второго порядка, например, для трехмерного Уравнения Максвелла ^{[26] [27]} в вычислительной электромагнетизме . Для двумерных и трехмерных уравнений теплопроводности и диффузии методы FADI и FLOD могут быть реализованы более простым, более эффективным и стабильным образом по сравнению с их традиционными методами. ^{[28] [29]}

Ссылки [ править ]