Algoritmo de Bartels-Stewart

Algoritmo en álgebra lineal numérica

En álgebra lineal numérica , el algoritmo de Bartels-Stewart se utiliza para resolver numéricamente la ecuación matricial de Sylvester . Desarrollado por RH Bartels y GW Stewart en 1971, ^[1] fue el primer método numéricamente estable que se pudo aplicar sistemáticamente para resolver tales ecuaciones. El algoritmo funciona utilizando las descomposiciones reales de Schur de y para transformar en un sistema triangular que luego se puede resolver mediante sustitución hacia adelante o hacia atrás. En 1979, G. Golub , C. Van Loan y S. Nash introdujeron una versión mejorada del algoritmo, ^[2] conocida como el algoritmo de Hessenberg-Schur. Sigue siendo un enfoque estándar para resolver ecuaciones de Sylvester cuando es de tamaño pequeño a moderado. ${\displaystyle AX-XB=C}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle AX-XB=C}$ ${\displaystyle X}$

El algoritmo

Sea , y supongamos que los valores propios de son distintos de los valores propios de . Entonces, la ecuación matricial tiene una solución única. El algoritmo de Bartels-Stewart realiza el cálculo aplicando los siguientes pasos: ^[2] ${\displaystyle X,C\in \mathbb {R} ^{m\times n}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle AX-XB=C}$ ${\displaystyle X}$

1.Calcular las descomposiciones reales de Schur

${\displaystyle R=U^{T}AU,}$

${\displaystyle S=V^{T}B^{T}V.}$

Las matrices y son matrices triangulares de bloque superior, con bloques diagonales de tamaño o . ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle 1\times 1}$ ${\displaystyle 2\times 2}$

2. Establecer ${\displaystyle F=U^{T}CV.}$

3. Resuelva el sistema simplificado , donde . Esto se puede hacer mediante sustitución hacia adelante en los bloques. Específicamente, si , entonces ${\displaystyle RY-YS^{T}=F}$ ${\displaystyle Y=U^{T}XV}$ ${\displaystyle s_{k-1,k}=0}$

${\displaystyle (R-s_{kk}I)y_{k}=f_{k}+\sum _{j=k+1}^{n}s_{kj}y_{j},}$

donde es la columna n de . Cuando , las columnas deben concatenarse y resolverse simultáneamente. ${\displaystyle y_{k}}$ ${\displaystyle k}$ ${\displaystyle Y}$ ${\displaystyle s_{k-1,k}\neq 0}$ ${\displaystyle [y_{k-1}\mid y_{k}]}$

4. Establecer ${\displaystyle X=UYV^{T}.}$

Costo computacional

Usando el algoritmo QR , las descomposiciones de Schur reales en el paso 1 requieren aproximadamente flops, de modo que el costo computacional general es . ^[2] ${\displaystyle 10(m^{3}+n^{3})}$ ${\displaystyle 10(m^{3}+n^{3})+2.5(mn^{2}+nm^{2})}$

Simplificaciones y casos especiales

En el caso especial en que y es simétrica, la solución también será simétrica. Esta simetría se puede aprovechar para que se encuentre de manera más eficiente en el paso 3 del algoritmo. ^[1] ${\displaystyle B=-A^{T}}$ ${\displaystyle C}$ ${\displaystyle X}$ ${\displaystyle Y}$

El algoritmo de Hessenberg-Schur

El algoritmo de Hessenberg-Schur ^[2] reemplaza la descomposición en el paso 1 con la descomposición , donde es una matriz de Hessenberg superior . Esto conduce a un sistema de la forma que se puede resolver mediante sustitución hacia adelante. La ventaja de este enfoque es que se puede encontrar utilizando reflexiones de Householder a un costo de flops, en comparación con los flops necesarios para calcular la descomposición de Schur real de . ${\displaystyle R=U^{T}AU}$ ${\displaystyle H=Q^{T}AQ}$ ${\displaystyle H}$ ${\displaystyle HY-YS^{T}=F}$ ${\displaystyle H=Q^{T}AQ}$ ${\displaystyle (5/3)m^{3}}$ ${\displaystyle 10m^{3}}$ ${\displaystyle A}$

Software e implementación

Las subrutinas necesarias para la variante Hessenberg-Schur del algoritmo Bartels-Stewart están implementadas en la biblioteca SLICOT y se utilizan en la caja de herramientas del sistema de control de MATLAB.

Enfoques alternativos

Para sistemas grandes, el costo del algoritmo Bartels-Stewart puede ser prohibitivo. Cuando y son dispersos o estructurados, de modo que las resoluciones lineales y las multiplicaciones de matrices vectoriales que los involucran son eficientes, los algoritmos iterativos pueden potencialmente tener un mejor desempeño. Estos incluyen métodos basados ​​en proyección, que usan iteraciones del subespacio de Krylov , métodos basados ​​en la iteración implícita de dirección alternada (ADI) e hibridaciones que involucran tanto la proyección como la ADI. ^[3] Los métodos iterativos también se pueden usar para construir directamente aproximaciones de bajo rango a cuando se resuelven . ${\displaystyle {\mathcal {O}}(m^{3}+n^{3})}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle X}$ ${\displaystyle AX-XB=C}$

Referencias

1. Bartels, RH; Stewart, GW (1972). "Solución de la ecuación matricial AX + XB = C [F4]". Comunicaciones de la ACM . 15 (9): 820–826. doi : 10.1145/361573.361582 . ISSN  0001-0782.
2. Golub, G.; Nash, S.; Loan, C. Van (1979). "Un método de Hessenberg–Schur para el problema AX + XB = C". IEEE Transactions on Automatic Control . 24 (6): 909–913. doi :10.1109/TAC.1979.1102170. hdl : 1813/7472 . ISSN  0018-9286.
3. Simoncini, V. (2016). "Métodos computacionales para ecuaciones matriciales lineales". SIAM Review . 58 (3): 377–441. doi :10.1137/130912839. hdl : 11585/586011 . ISSN  0036-1445. S2CID  17271167.