2
$\begingroup$

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

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • 2
    $\begingroup$ 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. $\endgroup$
    – Federico Poloni
    Commented Apr 28, 2013 at 18:37
  • $\begingroup$ 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. $\endgroup$
    – eolithr
    Commented Apr 29, 2013 at 1:07
  • 1
    $\begingroup$ No, I made the problem too complex. By using 'dlyap' in Matlab can solve this equation. $\endgroup$
    – eolithr
    Commented Apr 29, 2013 at 3:04
  • 1
    $\begingroup$ 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... $\endgroup$
    – Federico Poloni
    Commented Apr 29, 2013 at 7:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – Federico Poloni
    Commented Apr 29, 2013 at 7:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .