En álgebra lineal numérica , el algoritmo de Bartels-Stewart se utiliza para resolver numéricamente la ecuación de la matriz de Sylvester . Desarrollado por RH Bartels y GW Stewart en 1971, [1] fue el primer método numéricamente estable que pudo aplicarse 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] conocido como el algoritmo Hessenberg-Schur. Sigue siendo un enfoque estándar para resolver ecuaciones de Sylvester cuando es de tamaño pequeño a moderado.
El algoritmo
Dejar , y suponga que los valores propios de son distintos de los valores propios de . Entonces, la ecuación matricialtiene una solución única. El algoritmo de Bartels-Stewart calculaaplicando los siguientes pasos: [2]
1.Calcule las descomposiciones reales de Schur.
Las matrices y son matrices triangulares superiores en bloque, con bloques diagonales de tamaño o .
2. Establecer
3. Resuelve el sistema simplificado , dónde . Esto se puede hacer usando la sustitución hacia adelante en los bloques. Específicamente, si, luego
dónde es el a columna de . Cuándo, columnas deben concatenarse y resolverse simultáneamente.
4. Establecer
Costo computacional
Usando el algoritmo QR , las descomposiciones reales de Schur en el paso 1 requieren aproximadamente fracasos, de modo que el costo computacional general es . [2]
Simplificaciones y casos especiales
En el caso especial donde y es simétrico, la solución también será simétrico. Esta simetría se puede aprovechar para quese encuentra de manera más eficiente en el paso 3 del algoritmo. [1]
El algoritmo de Hessenberg-Schur
El algoritmo Hessenberg-Schur [2] reemplaza la descomposición en el paso 1 con la descomposición , dónde es una matriz de Hessenberg superior . Esto conduce a un sistema de la formaque se puede resolver mediante sustitución hacia adelante. La ventaja de este enfoque es quese puede encontrar utilizando las reflexiones de los jefes de hogar a un costo de fracasos, en comparación con el flops necesarios para calcular la descomposición de Schur real de .
Software e implementación
Las subrutinas necesarias para la variante Hessenberg-Schur del algoritmo de Bartels-Stewart se implementan en la biblioteca SLICOT. Estos se utilizan en la caja de herramientas del sistema de control MATLAB.
Aproximaciones alternativas
Para sistemas grandes, el El costo del algoritmo de Bartels-Stewart puede ser prohibitivo. Cuándo y son escasas o estructuradas, por lo que las soluciones lineales y las multiplicaciones de vectores matriciales que los involucran son eficientes, los algoritmos iterativos pueden funcionar mejor. Estos incluyen métodos basados en proyecciones, que utilizan iteraciones del subespacio de Krylov , métodos basados en la iteración de dirección alterna implícita (ADI) e hibridaciones que involucran tanto la proyección como la ADI. [3] Los métodos iterativos también se pueden utilizar para construir directamente aproximaciones de rango bajo para al resolver .
Referencias
- ^ a b 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 .
- ^ a b c d Golub, G .; Nash, S .; Préstamo, C. Van (1979). "Un método de Hessenberg-Schur para el problema AX + XB = C". Transacciones IEEE sobre control automático . 24 (6): 909–913. doi : 10.1109 / TAC.1979.1102170 . hdl : 1813/7472 . ISSN 0018-9286 .
- ^ Simoncini, V. (2016). "Métodos computacionales para ecuaciones matriciales lineales". Revisión SIAM . 58 (3): 377–441. doi : 10.1137 / 130912839 . ISSN 0036-1445 . S2CID 17271167 .