###### tags: `one-offs` `analysis` `semigroups`

# Decompositions à la Alekseev-Groebner

**Overview**: In this note, I sketch out a basic form of the Alekseev-Groebner lemma, a useful tool for the stability and perturbation analysis of dissipative semigroups. The base construction is presented here only for linear dynamical systems, but can be generalised to many other contexts.

## Introduction

The idea is roughly as follows: suppose that there is some stable semigroup which you would like to understand, and in order to do so, it appears natural to first study another more tractable semigroup, which is also stable.

The hope is then to show that the approximating semigroup tracks the ideal semigroup well, and hopefully even *uniformly in time*. The reason why this should be possible is that by the stability of each semigroup means, one can hope that any approximation errors which are incurred will be dissipated over time, rather than accumulating.

## Linear Dynamical Systems

I present here a formulation framed in terms of linear dynamical systems for simplicity. Let $\Phi$ denote the semigroup corresponding to the evolution

\begin{align}
x_{t}=A_{t}x_{t-1}+b_{t},
\end{align}

and let $\hat{\Phi}$ have the same structure, parametrised by $\left\{ \hat{A}_{t},\hat{b}_{t}\right\} _{t\geqslant1}$. We will assume that the systems are exponentially stable, in the sense that for some $c\geqslant1$, for any $s\leqslant t$, it holds that

\begin{align}
\left\Vert A_{t}\cdots A_{s}\right\Vert _{\mathrm{op}} &\leqslant c\cdot\left(1-\kappa\right)^{t-s} \\
\left\Vert \hat{A}_{t}\cdots\hat{A}_{s}\right\Vert _{\mathrm{op}} &\leqslant\hat{c}\cdot\left(1-\hat{\kappa}\right)^{t-s}
\end{align}

for constants $c,\hat{c}>0$ and $\kappa, \hat{\kappa} \in \left(0,1\right)$. Assume also that the one-step transitions for each system are close, in the sense that

\begin{align}
\left\Vert \hat{A}_{t}-A_{t}\right\Vert _{\mathrm{op}} &\leqslant \alpha \\
\left|\hat{b}_{t}-b_{t}\right| &\leqslant \beta.
\end{align}

Fixing some initial conditions $x_{0}=\hat{x}_{0}=x$ and a time horizon $T>0$, we will aim to show that $\left|\hat{x}_{T}-x_{T}\right|$ is small. The key decomposition is to interpolate from $x_{T} = \Phi_{0,T}\left(x\right)$ to $\hat{x}_{T} = \hat{\Phi}_{0,T}\left(x\right)$ along the sequence $t \mapsto \left(\hat{\Phi}_{t,T} \circ \Phi_{0,t}\right) \left( x \right)$, thus writing

\begin{align}
\hat{x}_{T}-x_{T}=\sum_{0<t\leqslant T}\left\{ \left(\hat{\Phi}_{t,T}\circ\Phi_{0,t}\right)\left(x\right)-\left(\hat{\Phi}_{t-1,T}\circ\Phi_{0,t-1}\right)\left(x\right)\right\} .
\end{align}

We then estimate that

\begin{align}
\left| \left(\hat{\Phi}_{t,T}\circ\Phi_{0,t}\right)\left(x\right)-\left(\hat{\Phi}_{t-1,T}\circ\Phi_{0,t-1}\right)\left(x\right) \right| &\leqslant \hat{c} \cdot \left(1-\hat{\kappa}\right)^{T-t}\cdot\left|\left(\Phi_{t-1,t}\circ\Phi_{0,t-1}\right)\left(x\right)-\left(\hat{\Phi}_{t-1,t}\circ\Phi_{0,t-1}\right)\left(x\right)\right| \\
\left|\left(\Phi_{t-1,t}\circ\Phi_{0,t-1}\right)\left(x\right)-\left(\hat{\Phi}_{t-1,t}\circ\Phi_{0,t-1}\right)\left(x\right)\right| &\leqslant\alpha\cdot\left|\Phi_{0,t-1}\left(x\right)-\Phi_{0,t-1}\left(x\right)\right|+\beta \\
\left|\Phi_{0,t-1}\left(x\right)-\Phi_{0,t-1}\left(x\right)\right| &\leqslant c\cdot\left(1-\kappa\right)^{t-1}\cdot\left|x\right|,
\end{align}

so that

\begin{align}
\left|\left(\hat{\Phi}_{t,T}\circ\Phi_{0,t}\right)\left(x\right)-\left(\hat{\Phi}_{t-1,T}\circ\Phi_{0,t-1}\right)\left(x\right)\right| &\leqslant\alpha\cdot c\cdot\hat{c}\cdot\left(1-\hat{\kappa}\right)^{T-t}\cdot\left(1-\kappa\right)^{t-1}\cdot\left|x\right| \\
&+\beta\cdot\hat{c}\cdot\left(1-\hat{\kappa}\right)^{T-t}.
\end{align}

Summing over $\left(0,T\right]$, this furnishes that (assuming for now that $\kappa>\hat{\kappa}$)

\begin{align}
\left|\hat{x}_{T}-x_{T}\right| &\leqslant \sum_{0<t\leqslant T}\left\{ \alpha\cdot c\cdot\hat{c}\cdot\left(1-\hat{\kappa}\right)^{T-t}\cdot\left(1-\kappa\right)^{t-1}\cdot\left|x\right|+\beta\cdot\hat{c}\cdot\left(1-\hat{\kappa}\right)^{T-t}\right\} \\
&\leqslant\left(1-\hat{\kappa}\right)^{T}\cdot\frac{\alpha\cdot c\cdot\hat{c}}{\kappa-\hat{\kappa}}\cdot\left|x\right|+\frac{\beta\cdot\hat{c}}{\hat{\kappa}}.
\end{align}

In particular, this is uniformly bounded over $T\geqslant0$, and so the two systems remain close to one another for all times. Additionally, if the shifts are equal, i.e. $b_{t}=\hat{b}_{t}$, then the second term vanishes, and the two systems even contract towards each other. Note that there is no assumption that the processes are converging to a fixed state; indeed, this strategy is even quite well-adapted to inhomogeneous systems.

Similar decompositions can be exhibited for other problems, e.g. nonlinear dynamical systems and their approximations by numerical integrators, problems involving evolving sequences of probability measures (e.g. sequential Monte Carlo), perturbation theory for Markov chains, and more. In each case, a key step is to interpolate along the sequence $t\mapsto\left(\hat{\Phi}_{t,T}\circ\Phi_{0,t}\right)\left(x\right)$, and control the magnitude of the telescoping terms.

It bears emphasis that the prerequisites for the decomposition to be informative are essentially that

1. the systems in question are stable, and even { contractive / dissipative / etc. }, and
2. the two systems are good approximations to one another over a single step.

Given that many computational problems involve searching for an equilibrium state in some form or another, these situations are widespread in practice.