全为实根的能达丰富性递推计算及计算复杂性

     对特征根全为实根的线性离散系统，其 $N$ 步能达丰富性的计算式为

      $V_{n}(C_{n}(P_{0,N-1}))=\left(\prod_{i=1}^{n}b_{i}\right)\sum_{\left(i_{1},i_{2},\cdots,i_{n}\right)\in\Omega_{0,N-1}^{n}}\left|\det\left[\begin{array}{cccc} \lambda_{1}^{i_{1}} & \lambda_{1}^{i_{2}} & \cdots & \lambda_{1}^{i_{n}}\\ \lambda_{2}^{i_{1}} & \lambda_{2}^{i_{2}} & \cdots & \lambda_{2}^{i_{n}}\\ \vdots & \vdots & \ddots & \vdots\\ \lambda_{n}^{i_{1}} & \lambda_{n}^{i_{2}} & \cdots & \lambda_{n}^{i_{n}} \end{array}\right]\right|$

                      $=\left(\prod_{i=1}^{n}b_{i}\right)V_{N}^{\lambda_{1},\lambda_{2},\cdots,\lambda_{n}}$

其中

$V_{N}^{\lambda_{1},\lambda_{2},\cdots,\lambda_{n}}=\sum_{\left(i_{1},i_{2},\cdots,i_{n}\right)\in\Omega_{0,N-1}^{n}}\left|\det\left[\begin{array}{cccc} \lambda_{1}^{i_{1}} & \lambda_{1}^{i_{2}} & \cdots & \lambda_{1}^{i_{n}}\\ \lambda_{2}^{i_{1}} & \lambda_{2}^{i_{2}} & \cdots & \lambda_{2}^{i_{n}}\\ \vdots & \vdots & \ddots & \vdots\\ \lambda_{n}^{i_{1}} & \lambda_{n}^{i_{2}} & \cdots & \lambda_{n}^{i_{n}} \end{array}\right]\right|$

    由博文“单输入系统有限时间能控丰富性的一个估计”(http://blog.sciencenet.cn/blog-3343777-1064601.html)可知，若 $0<\lambda_{1}<\lambda_{2}<\cdots<\lambda_{n}$ ,则上式求和号内的类范德蒙矩阵的行列式值都大于0，因此有 $V_{N}^{\lambda_{1},\lambda_{2},\cdots,\lambda_{n}}$ 如下递推计算式

$V_{N}^{\lambda_{1},\lambda_{2},\cdots,\lambda_{n}}=V_{N-1}^{\lambda_{1},\lambda_{2},\cdots,\lambda_{n}}+\sum_{j=1}^{n}(-1)^{n+j}\lambda_{j}^{N-1}V_{N-1}^{\lambda_{1},\lambda_{2},\cdots,\lambda_{n}\setminus\lambda_{j}}$

其中“ $\lambda_{1},\lambda_{2},\cdots,\lambda_{n}\setminus\lambda_{j}$ ”表示从序列中“ $\lambda_{1},\lambda_{2},\cdots,\lambda_{n}$ ”去掉“ $\lambda_{j}$ ”得到的新序列。上述递推计算的计算复杂性以乘法次数考量则为 $\mathcal{O}(n^{n}N)$ ，即对于实根的情形，关于N的能达丰富性计算复杂性从定义计算式的 $\mathcal{O}(N^{n})$ 降至改进的递推计算式的 $\mathcal{O}(N)$ ，为 $N$ 的线性时间复杂性。