Método implícito de dirección alternada

El método ADI es un proceso iterativo de dos pasos que actualiza alternativamente los espacios de columnas y filas de una solución aproximada para${\displaystyle AX-XB=C}$. Una iteración de ADI consta de los siguientes pasos: ^{[ 7 ]}

1. Resuelve para${\displaystyle X^{(j+1/2)}}$, dónde${\displaystyle \left(A-\beta _{j+1}I\right)X^{(j+1/2)}=X^{(j)}\left(B-\beta _{j+1}I\right)+C.}$

2. Resuelve para${\displaystyle X^{(j+1)}}$, dónde ${\displaystyle X^{(j+1)}\left(B-\alpha _{j+1}I\right)=\left(A-\alpha _{j+1}I\right)X^{(j+1/2)}-C}$.

Los números${\displaystyle (\alpha _{j+1},\beta _{j+1})}$se denominan parámetros de desplazamiento, y la convergencia depende en gran medida de la elección de estos parámetros. ^{[ 8 ] [ 9 ]} Para realizar${\displaystyle K}$iteraciones de ADI, una suposición inicial${\displaystyle X^{(0)}}$es necesario, así como${\displaystyle K}$parámetros de cambio,${\displaystyle \{(\alpha _{j},\beta _{j})\}_{j=1}^{K}}$.

Si${\displaystyle A\in \mathbb {C} ^{m\times m}}$y ${\displaystyle B\in \mathbb {C} ^{n\times n}}$, entonces${\displaystyle AX-XB=C}$se puede resolver directamente en${\displaystyle {\mathcal {O}}(m^{3}+n^{3})}$utilizando el método de Bartels-Stewart . ^{[ 10 ]} Por lo tanto, solo es beneficioso utilizar ADI cuando la multiplicación matriz-vector y las soluciones lineales involucran${\displaystyle A}$y${\displaystyle B}$Se puede aplicar a bajo costo.

La ecuación${\displaystyle AX-XB=C}$tiene una solución única si y solo si${\displaystyle \sigma (A)\cap \sigma (B)=\emptyset }$, dónde${\displaystyle \sigma (M)}$es el espectro de${\displaystyle M}$. ^{[ 1 ]} Sin embargo, el método ADI funciona especialmente bien cuando${\displaystyle \sigma (A)}$y${\displaystyle \sigma (B)}$están bien separados y${\displaystyle A}$y${\displaystyle B}$son matrices normales . Estas suposiciones se cumplen, por ejemplo, con la ecuación de Lyapunov.${\displaystyle AX+XA^{*}=C}$cuando${\displaystyle A}$es definida positiva . Bajo estas suposiciones, se conocen parámetros de desplazamiento casi óptimos para varias opciones de${\displaystyle A}$y${\displaystyle B}$. ^{[ 8 ] [ 9 ]} Además, se pueden calcular límites de error a priori, eliminando así la necesidad de monitorear el error residual en la implementación.

El método ADI aún puede aplicarse cuando no se cumplen los supuestos anteriores. El uso de parámetros de desplazamiento subóptimos puede afectar negativamente la convergencia, ^{[ 1 ]} y la convergencia también se ve afectada por la no normalidad de${\displaystyle A}$o${\displaystyle B}$(a veces ventajosamente). ^{[ 11 ]} Se observa que los métodos de subespacio de Krylov , como el Método de Subespacio de Krylov Racional, ^{[ 12 ]} convergen típicamente más rápidamente que ADI en este contexto, ^{[ 1 ] [ 3 ]} y esto ha llevado al desarrollo de métodos híbridos de proyección ADI. ^{[ 3 ]}

El problema de encontrar buenos parámetros de desplazamiento no es trivial. Este problema se puede comprender examinando la ecuación de error ADI. Después${\displaystyle K}$iteraciones, el error viene dado por

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

Elegir${\displaystyle X^{(0)}=0}$Esto da como resultado la siguiente cota para el error relativo:

${\displaystyle {\frac {\left\|XX^{(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)}}.}$

dónde${\displaystyle \|\cdot \|_{2}}$es la norma del operador . El conjunto ideal de parámetros de desplazamiento${\displaystyle \{(\alpha _{j},\beta _{j})\}_{j=1}^{K}}$define una función racional${\displaystyle r_{K}}$que minimiza la cantidad${\displaystyle \|r_{K}(A)\|_{2}\|r_{K}(B)^{-1}\|_{2}}$. Si${\displaystyle A}$y${\displaystyle B}$son matrices normales y tienen descomposiciones en valores propios.${\displaystyle A=V_{A}\Lambda _ {A}V_{A}^{*}}$y${\displaystyle B=V_{B}\Lambda _{B}V_{B}^{*}}$, entonces

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

En muchas aplicaciones,${\displaystyle A}$y${\displaystyle B}$son matrices muy grandes y dispersas, y${\displaystyle C}$puede ser factorizado como${\displaystyle C=C_{1}C_{2}^{*}}$, dónde${\displaystyle C_{1}\in \mathbb {C} ^{m\times r},C_{2}\in \mathbb {C} ^{n\times r}}$, con${\displaystyle r=1,2}$. ^{[ 1 ]} En tal escenario, puede que no sea factible almacenar la matriz potencialmente densa.${\displaystyle X}$explícitamente. Una variante de ADI, llamada ADI factorizada, ^{[ 3 ] [ 2 ]} puede usarse para calcular${\displaystyle ZY^{*}}$, dónde${\displaystyle X\approx ZY^{*}}$. La efectividad del ADI factorizado depende de si${\displaystyle X}$se aproxima bien mediante una matriz de bajo rango. Se sabe que esto es cierto bajo diversas suposiciones sobre${\displaystyle A}$y${\displaystyle B}$. ^{[ 11 ] [ 9 ]}

El método tradicional para resolver numéricamente la ecuación de conducción de calor es el método de Crank-Nicolson . Este método genera un conjunto de ecuaciones muy complejas en múltiples dimensiones, cuya resolución resulta costosa. La ventaja del método ADI radica en que las ecuaciones que deben resolverse en cada paso tienen una estructura más simple y pueden resolverse eficientemente mediante el algoritmo de matriz tridiagonal .

Consideremos la ecuación de difusión lineal en dos dimensiones,

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

El método implícito de Crank-Nicolson produce la siguiente ecuación de diferencias finitas:

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

dónde:

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

y${\displaystyle \delta _{p}^{2}}$es el operador de segunda diferencia central para la p -ésima coordenada

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

con${\displaystyle e_{p}=(1,0)}$o${\displaystyle (0,1)}$para${\displaystyle p=x}$o${\displaystyle y}$respectivamente (y${\displaystyle ij}$una abreviatura para puntos de la red${\displaystyle (i,j)}$).

Después de realizar un análisis de estabilidad , se puede demostrar que este método será estable para cualquier${\displaystyle \Delta t}$.

Una desventaja del método de Crank-Nicolson es que la matriz en la ecuación anterior está segmentada con un ancho de banda generalmente bastante grande. Esto hace que la solución directa del sistema de ecuaciones lineales sea bastante costosa (aunque existen soluciones aproximadas eficientes, por ejemplo, el uso del método del gradiente conjugado precondicionado con la factorización de Cholesky incompleta ).

La idea detrás del método ADI es dividir las ecuaciones de diferencias finitas en dos, una con la derivada x tomada implícitamente y la siguiente con la derivada y tomada implícitamente,

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

El sistema de ecuaciones involucrado es simétrico y tridiagonal (con banda de ancho de banda 3), y normalmente se resuelve utilizando el algoritmo de matriz tridiagonal .

Se puede demostrar que este método es incondicionalmente estable y de segundo orden en el tiempo y el espacio. ^{[ 20 ]} Existen métodos ADI más refinados, como los métodos de Douglas, ^{[ 21 ]} o el método del factor f ^{[ 22 ]} que pueden utilizarse para tres o más dimensiones.

El uso del método ADI como esquema de división de operadores puede generalizarse. Es decir, podemos considerar ecuaciones de evolución generales.

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

dónde${\displaystyle F_{1}}$y${\displaystyle F_{2}}$son operadores (posiblemente no lineales) definidos en un espacio de Banach . ^{[ 23 ] [ 24 ]} En el ejemplo de difusión anterior tenemos${\displaystyle F_{1}={\partial ^{2} \over \partial x^{2}}}$y${\displaystyle F_{2}={\partial ^{2} \over \partial y^{2}}}$.

Es posible simplificar el método ADI convencional a un método ADI fundamental, que solo tiene operadores similares en el lado izquierdo y carece de operadores en el lado derecho. Esto puede considerarse el esquema fundamental (básico) del método ADI, ^{[ 25 ] [ 26 ]} sin más operadores (que reducir) en el lado derecho, a diferencia de la mayoría de los métodos implícitos tradicionales que suelen constar de operadores en ambos lados de las ecuaciones. El método ADI fundamental genera ecuaciones de actualización más simples, concisas y eficientes sin degradar la precisión del método ADI convencional.

Muchos métodos implícitos clásicos de Peaceman-Rachford, Douglas-Gunn, D'Yakonov, Beam-Warming, Crank-Nicolson, etc., pueden simplificarse a esquemas implícitos fundamentales con segundos miembros libres de operadores. ^{[ 26 ]} En sus formas fundamentales, el método FADI de precisión temporal de segundo orden puede relacionarse estrechamente con el método fundamental localmente unidimensional (FLOD), que puede actualizarse a precisión temporal de segundo orden, como para las ecuaciones de Maxwell tridimensionales ^{[ 27 ] [ 28 ]} en electromagnetismo computacional . Para ecuaciones de conducción y difusión de calor bidimensionales y tridimensionales, tanto los métodos FADI como FLOD pueden implementarse de una manera más simple, eficiente y estable en comparación con sus métodos convencionales. ^{[ 29 ] [ 30 ]}