Algoritmo de Bartels-Stewart

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}$${\estilo de visualización A}$${\estilo de visualización B}$${\displaystyle AX-XB=C}$${\estilo de visualización X}$

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}}$${\estilo de visualización A}$${\estilo de visualización B}$${\displaystyle AX-XB=C}$${\estilo de visualización 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 . ${\estilo de visualización R}$${\estilo de visualización 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}$$Estilo de visualización Y=U^{T}XV$$estilo de visualización 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}}$${\estilo de visualización k}$${\estilo de visualización Y}$${\displaystyle s_{k-1,k}\neq 0}$${\displaystyle [y_{k-1}\mid y_{k}]}$

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

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

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]$Estilo de visualización B=-A^{T}}$${\estilo de visualización C}$${\estilo de visualización X}$${\estilo de visualización Y}$

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 . $Estilo de visualización R=U^{T}AU$$Estilo de visualización H=Q^{T}AQ}$${\estilo de visualización H}$$Estilo de visualización HY-YS^{T}=F}$$Estilo de visualización H=Q^{T}AQ}$$estilo de visualización (5/3)m^{3}}$$Estilo de visualización 10m^{3}}$${\estilo de visualización A}$

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.

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 vectores matriciales 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})}$${\estilo de visualización A}$${\estilo de visualización B}$${\estilo de visualización X}$${\displaystyle AX-XB=C}$