Bartels–Stewart algorithm: Difference between revisions

Revision as of 22:45, 20 September 2018

Revision as of 00:21, 21 September 2018

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 forand thespecial Lyapunov equationcases ==

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]].

When <math>A</math> and <math>B</math> are both normal matrices, their Schur decompositions are also their eigendecompositions, and <math>R</math> and <math>S^T</math> from step 1 are diagonal. The solution matrix <math>Y</math> from step 3 in the algorithm can therefore be expressed explicitly as <math>Y_{jk} = 1/(R_{jj} - R_{kk}) F_{jk}</math>.

In the special case where <math>AX + XA^T =C</math>, with <math>C</math> symmetric, the solution <math>X</math> will also be symmetric. This symmetry can be exploited so that <math>Y</math> is found more efficiently in step 3 of the algorithm. Note that if, in addition, <math>A = A^T</math>, so that <math>AX + XA^T =C</math>, the equation is diagonalized.

== Alternative approaches ==