# On solution of a discrete-time equation

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

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