“Bartels–Stewart algorithm”的意思、由来-开放百科全书

In numerical linear algebra, the Bartels–Stewart algorithm is used to numerically solve the Sylvester matrix equation

. Developed by R.H. Bartels and G.W. Stewart in 1971^[1], it was the first numerically stable method that could by systematically applied to solve such equations. The algorithm works by using the real Schur decompositions of

and

to transform

into a triangular system that can then be solved using forward or backward substitution. In 1979, G. Golub, C. Van Loan and S. Nash introduced an improved version of the algorithm^[2], known as the Hessenberg–Schur algorithm. It remains a standard approach for solving Sylvester equations when

is of small to moderate size.

The algorithm

Let

, and assume that the eigenvalues of

are distinct from the eigenvalues of

. Then, the matrix equation

has a unique solution. The Bartels–Stewart algorithm computes

by applying the following steps^[2]:

The matrices

and

are block-upper triangular matrices, with square blocks of size no greater than

3. Solve the simplified system

, where

. This can be done using forward substitution on the blocks. Specifically, if

, then

where

is the

th column of

. When

, columns

should be concatenated and solved for simultaneously.

Computational cost

Using the QR algorithm, the real Schur decompositions in step 1 require approximately

flops, so that the overall computational cost is

^[2].

Simplifications and special cases

In the special case where

and

is symmetric, the solution

will also be symmetric. This symmetry can be exploited so that

is found more efficiently in step 3 of the algorithm^[1].

The Hessenberg–Schur algorithm

The Hessenberg–Schur algorithm^[2] replaces the decomposition

in step 1 with the decomposition

, where

is an upper-Hessenberg matrix. This leads to a system of the form

that can be solved using forward substitution. The advantage of this approach is that

can be found using Householder reflections at a cost of

flops, compared to the

flops required to compute the real Schur decomposition of

Software and implementation

The subroutines required for the Hessenberg-Schur variant of the Bartels–Stewart algorithm are implemented in the SLICOT library. These are used in the MATLAB control system toolbox.

Alternative approaches

For large systems, the

cost of the Bartels–Stewart algorithm can be prohibitive. When

and

are sparse or structured, so that linear solves and matrix vector multiplies involving them are efficient, iterative algorithms can potentially perform better. These include projection-based methods, which use Krylov subspace iterations, methods based on the alternating direction implicit (ADI) iteration, and hybridizations that involve both projection and ADI^[3]. Iterative methods can also be used to directly construct low rank approximations to

when solving

References

1. ^¹{{Cite journal|last=Bartels|first=R. H.|last2=Stewart|first2=G. W.|date=1972|title=Solution of the matrix equation AX + XB = C [F4]|url=http://dl.acm.org/citation.cfm?id=361573.361582|journal=Communications of the ACM|volume=15|issue=9|pages=820–826|doi=10.1145/361573.361582|issn=0001-0782}}
2. ^¹²³{{Cite journal|last=Golub|first=G.|last2=Nash|first2=S.|last3=Loan|first3=C. Van|date=1979|title=A Hessenberg–Schur method for the problem AX + XB= C|url=https://ieeexplore.ieee.org/document/1102170/|journal=IEEE Transactions on Automatic Control|volume=24|issue=6|pages=909–913|doi=10.1109/TAC.1979.1102170|issn=0018-9286|hdl=1813/7472}}
3. ^{{Cite journal|last=Simoncini|first=V.|date=2016|title=Computational Methods for Linear Matrix Equations|journal=SIAM Review|language=en-US|volume=58|issue=3|pages=377–441|doi=10.1137/130912839|issn=0036-1445}}