MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hello, members. I have a problem for the following problem when I derive an optimization algorithm for stochastic singular systems $$S(k+1)=A(k)S(k)A^{T}(k)+R(k)+F(k)S(k+1)F^{T}(k)$$ where $R(k)>=0$ So, how to calculate $S$, is there analytic solution or numerical solution to $S$?

This problem is different from the following one On solution of a recursion with rectangular matrices

Thanks for your help

share|cite|improve this question
up vote 1 down vote accepted

you'll want to solve this equation iteratively, considering $S(k)$ as known and $S(k+1)$ as unknown; for $F(k)$ invertible you then have a Sylvester equation, of the form $F^{-1}(k)S(k+1)-S(k+1)F^{T}(k)=C(k)$, which has a unique solution iff $F^{-1}(k)$ and $F(k)$ have no common eigenvalue. The Wikipedia page gives algorithms to solve this equation, implemented in several software packages.

share|cite|improve this answer
There are numerical methods dealing directly with the equation $X-FXF^T=C$, known as discrete-time Lyapunov equation, or Stein equation. There is no need to invert $F$ and convert it to a Sylvester; sometimes algorithms even go the other way round and convert a continuous-time Lyapunov equation to a discrete-time one to solve it. – Federico Poloni Apr 28 '13 at 18:37
Thanks for your kind help, Dr. Carlo and Dr. Federico. When $F$ is singular, The Sylvester method may fail to work. So, would you please give me some links or references on the equation $X-FXF^{T}=C$. It seems we can solve it using LMI techniques for obtaining numerical solutions. – eolithr Apr 29 '13 at 1:07
No, I made the problem too complex. By using 'dlyap' in Matlab can solve this equation. – eolithr Apr 29 '13 at 3:04
Yep. dlyap will be fine for a small-scale problem; it should use a variant of the same Bartels-Stewart method that is used for continous-time lyapunov eqs; essentially, take a Schur form of $F$ and solve directly via back-substitution for each entry of $X$ "in the right order". For large-scale problems, you can truncate the series $X=\sum_{i=0}^{\infty} F^{i}CF^{Ti}$, or obtain the partial sum truncated at the term $2^{k}$ directly from the one truncated at $2^{k-1}$ with some manipulations (Smith methods). You can apply some Möbius transforms to $F$ without changing the solution to make... – Federico Poloni Apr 29 '13 at 7:09
it more stable, and ultimately obtain a discrete-time version of the ADI method for Lyapunov equations. In short, with some algebraic manipulations everything that works in the continuous-time case rates to work in the discrete-time case as well. – Federico Poloni Apr 29 '13 at 7:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.