Content deleted Content added
No edit summary |
|||
Line 3:
'''Bartels-Stewart Algorithm'''
In [[numerical linear algebra]], the '''Bartels-Stewart''' algorithm is used to numerically solve the [[Sylvester equation|Sylvester matrix equation]] <math> AX - XB = C</math>. Developed by R.H. Bartels and G.W. Stewart in 1971, it was the first [[numerical stability|numerically stable]] method that could by systematically applied to solve such equations. The algorithm works by using the [[Schur decomposition|Schur decompositions]] of <math>A</math> and <math>B</math> to transform <math> AX - XB = C</math> into a triangular system that can then be solved using forward and back-substitutions. In 1979, [[Gene H. Golub|G. Golub]], [[Charles F. Van Loan|C. Van Loan]] and S.Nash introduced an improved version of the algorithm, known as the Hessenberg-Schur algorithm. It remains the standard approach for solving Sylvester equations when <math>X</math> is of small to moderate size.
== The algorithm ==
Let <math>X, C \in \mathbb{R}^{m \times n}</math>, and assume that the eigenvalues of <math>A</math> are distinct from the eigenvalues of <math>B</math>. Then, the matrix <math> AX - XB = C</math> has a unique solution. The Bartels-Stewart algorithm computes <math>X</math> by applying the following steps:
1.Compute the [[Schur decomposition|Schur decompositions]]
<math>R = U^TAU</math>,
Line 22:
<math>(R - s_{kk}I)y_k = f_{k} + \sum_{j = k+1}^n s_{kj}y_j</math>,
where <math>y_k</math>is the <math>k</math>th column of <math>Y</math>. When <math>s_{k-1, k} \neq 0</math>, columns <math>[ y_{k-1} | y_{k}]</math> should be solved for simultaneously.
4. Set <math>X = UYV^T</math>.
Line 32:
The Hessenberg-Schur algorithm replaces the decomposition <math>R = U^TAU</math> in step 1 with the decomposition <math>H = Q^TAQ</math>, where <math>H</math> is an upper-Hessenberg matrix and <math>S</math> is block-upper triangular. This leads to a system of the form <math> HY + YS^T = F</math> that can be solved using forward substitution. The advantage of this approach is that <math>H = Q^TAQ</math> can be found using Householder reflections at a cost of <math>(5/3)m^3</math> flops, compared to the <math>10m^3</math> flops required to compute the Schur decomposition of <math>A</math>.
== Simplifications for the Lyapunov equation ==
A special case of the Sylvester equation where <math>AX + XA^T = C</math>, with <math> A = A^T</math> and <C = C^T</math>, is known as the [[Lyapunov equation| discrete Lyapunov equation]].
== Alternative approaches ==
| |||