7,129
个编辑
更改
跳到导航
跳到搜索
第217行：
第217行： − 定理： <math>T_0 \frac{u_{0i}}{u_{ii}}u_{ij}=T_{j}-T'_{j}</math>对所有的j不等于0和N+1的节点都成立就可以了。+ − 首先，我们来证明一个引理：+ − '''引理'''：<math>(U_{-i})_{ij}=\frac{u_{ij}}{u_{ii}}</math>，其中，<math>U_{-i}=(I-M_{-i})^{-1}</math>，<math>M_{-i}=M-\Delta M</math>+ − '''证明'''：+ − 因为：+ − <math>U=(I-M)^{-1}, + − 所以<math>U(I-M)=I=U_{-i}(I-M_{-i})</math>，再根据<math>M_{-i}=M-\Delta M</math>，这样就有：+ − <math>U-U_{-i}=U\Delta M U_{-i}</math>+ − 考虑第i行第j列的元素，也就是：+ − <math>+ − 又因为：<math>UM=U-I</math>，所以：+ − <math>+ − 于是：+ − <math>+ − 所以：+ − <math>(U_{-i})_{ij}=\frac{u_{ij}}{u_{ii}}</math>，+ − 这样，引理得证。+ − <math>TM+S=T</math>+ − 也就是，每个节点的流等于从其它节点转移过来的入流加上从源转移过来的入流，+ − 同样的道理，对于删除i节点后的马尔科夫矩阵，+ − <math>T'M_{-i}+S'=T'</math>，+ − 于是，将两式相减：+ − <math>+ − 而我们知道<math>M_{-i}=M-\Delta M</math>，所以：+ − <math>T-T'=T(M_{-i}+\Delta M)-T'M_{-i}+S-S'</math>+ − 于是，可以得到：+ − <math>T-T'=(T\Delta M +S-S')\cdot (I-M_{-i})^{-1}=T_i((U_{-i})_{i,1},(U_{-i})_{i,2},\cdot\cdot\cdot,(U_{-i})_{i,N})</math>+ − 于是，该向量的第j个元素：+ − <math>(T-T')_j=(T_i((U_{-i})_{i,1},(U_{-i})_{i,2},\cdot\cdot\cdot,(U_{-i})_{i,N}))_j=T_i(U_{-i})_{ij}</math>+ − 又由于i节点的流量i又等于从源到i的总流量（参见[[基于马尔科夫链的流网络分析]]）。+ − 于是，T<sub>i</sub>又可以写作：+ − <math>+ − 而又根据引理，<math>(U_{-i})_{ij}=\frac{u_{ij}}{u_{ii}}</math>+ − 所以，+ − <math>+ − 根据[[基于马尔可夫链的流网络分析]]，将首达流公式代入，就得到：+ − <math>+ − 于是，证明了定理所述等式成立。+ − 事实上，有一种更加简单的方法能得到证明：+ − 因为<math>SU=T</math>，于是有<math>\delta T_j = U_{ji}\delta S_i</math>, <math>\delta T_i = u_{ii}\delta S_i</math>+ − 得到<math>\delta T_j = u_{ji}/u_{ii}\delta T_i</math>+ − 而去掉点i,相当于<math>\delta T_i = T_i = \sum S_k u_{ki}</math>+ − 所以<math>\delta T_j = T_i u_{ji}/u_{ii}</math>+ − 再将<math>T_i=\phi_{0,i}u_{ii} </math>的表达式代入即可。+ + +
→两种定义的等价性
虽然上面给出了两种关于C<sub>i</sub>的定义，但是我们可以证明它们是彼此等价的，也就是说这两种方法计算出的C<sub>i</sub>严格相等。我们观察算式{{EquationNote|eq1}}和{{EquationNote|eq2}}就会发现，如果两种算法相等，那么只需要验证如下事实就可以了，即
虽然上面给出了两种关于C<sub>i</sub>的定义，但是我们可以证明它们是彼此等价的，也就是说这两种方法计算出的C<sub>i</sub>严格相等。我们观察算式{{EquationNote|eq1}}和{{EquationNote|eq2}}就会发现，如果两种算法相等，那么只需要验证如下事实就可以了，即
:定理： <math>T_0 \frac{u_{0i}}{u_{ii}}u_{ij}=T_{j}-T'_{j}</math>对所有的j不等于0和N+1的节点都成立就可以了。
下面给出该定理严格的数学证明：
下面给出该定理严格的数学证明：
:首先，我们来证明一个引理：
'''引理'''：<math>(U_{-i})_{ij}=\frac{u_{ij}}{u_{ii}}</math>，其中，<math>U_{-i}=(I-M_{-i})^{-1}</math>，<math>M_{-i}=M-\Delta M</math>
'''证明'''：
因为：
:<math>U=(I-M)^{-1},
U_{-i}=(I-M_{-i})^{-1}
U_{-i}=(I-M_{-i})^{-1}
</math>，
</math>，
所以<math>U(I-M)=I=U_{-i}(I-M_{-i})</math>，再根据<math>M_{-i}=M-\Delta M</math>，这样就有：
:<math>U-U_{-i}=U\Delta M U_{-i}</math>
考虑第i行第j列的元素，也就是：
:<math>
u_{ij}-(U_{-i})_{ij}=(U_{-i})_{ij}\sum_{k=1}^{N}u_{ik}m_{ki}
u_{ij}-(U_{-i})_{ij}=(U_{-i})_{ij}\sum_{k=1}^{N}u_{ik}m_{ki}
</math>
</math>
又因为：<math>UM=U-I</math>，所以：
:<math>
\sum_{k=1}^Nu_{ik}m_{ki}=u_{ii}-1
\sum_{k=1}^Nu_{ik}m_{ki}=u_{ii}-1
</math>
</math>
于是：
:<math>
u_{ij}-(U_{-i})_{ij}=(U_{-i})_{ij}(u_{ii}-1)
u_{ij}-(U_{-i})_{ij}=(U_{-i})_{ij}(u_{ii}-1)
</math>
</math>
所以：
:<math>(U_{-i})_{ij}=\frac{u_{ij}}{u_{ii}}</math>，
这样，引理得证。
下面，我们来证明定理：
下面，我们来证明定理：
'''证明'''：设<math>S=(f_{0,1},f_{0,2},\cdot\cdot\cdot,f_{0,N})</math>，<math>T=(T_1,T_2,\cdot\cdot\cdot,T_N)</math>为流网络达到稳态时各个节点流量T<sub>i</sub>的分布向量，则根据流平衡有：
'''证明'''：设<math>S=(f_{0,1},f_{0,2},\cdot\cdot\cdot,f_{0,N})</math>，<math>T=(T_1,T_2,\cdot\cdot\cdot,T_N)</math>为流网络达到稳态时各个节点流量T<sub>i</sub>的分布向量，则根据流平衡有：
:<math>TM+S=T</math>
也就是，每个节点的流等于从其它节点转移过来的入流加上从源转移过来的入流，
同样的道理，对于删除i节点后的马尔科夫矩阵，
:<math>T'M_{-i}+S'=T'</math>，
于是，将两式相减：
:<math>
TM-T'M_{-i}+S-S'=T-T'
TM-T'M_{-i}+S-S'=T-T'
</math>
</math>
而我们知道<math>M_{-i}=M-\Delta M</math>，所以：
:<math>T-T'=T(M_{-i}+\Delta M)-T'M_{-i}+S-S'</math>
于是，可以得到：
:<math>T-T'=(T\Delta M +S-S')\cdot (I-M_{-i})^{-1}=T_i((U_{-i})_{i,1},(U_{-i})_{i,2},\cdot\cdot\cdot,(U_{-i})_{i,N})</math>
于是，该向量的第j个元素：
:<math>(T-T')_j=(T_i((U_{-i})_{i,1},(U_{-i})_{i,2},\cdot\cdot\cdot,(U_{-i})_{i,N}))_j=T_i(U_{-i})_{ij}</math>
又由于i节点的流量i又等于从源到i的总流量（参见[[基于马尔科夫链的流网络分析]]）。
于是，T<sub>i</sub>又可以写作：
:<math>
T_i=\phi_{0,i}u_{ii}
T_i=\phi_{0,i}u_{ii}
</math>
</math>
而又根据引理，<math>(U_{-i})_{ij}=\frac{u_{ij}}{u_{ii}}</math>
所以，
:<math>
(T-T')_j=\phi_{0,i}u_{ii}(U_{-1})_{ij}=\phi_{0,i}u_{ij}
(T-T')_j=\phi_{0,i}u_{ii}(U_{-1})_{ij}=\phi_{0,i}u_{ij}
</math>
</math>
根据[[基于马尔可夫链的流网络分析]]，将首达流公式代入，就得到：
:<math>
(T-T')_j=T_0\frac{u_{0i}}{u_{ii}}u_{ij}
(T-T')_j=T_0\frac{u_{0i}}{u_{ii}}u_{ij}
</math>
</math>
于是，证明了定理所述等式成立。
事实上，有一种更加简单的方法能得到证明：
因为<math>SU=T</math>，于是有<math>\delta T_j = U_{ji}\delta S_i</math>, <math>\delta T_i = u_{ii}\delta S_i</math>
得到<math>\delta T_j = u_{ji}/u_{ii}\delta T_i</math>
而去掉点i,相当于<math>\delta T_i = T_i = \sum S_k u_{ki}</math>
所以<math>\delta T_j = T_i u_{ji}/u_{ii}</math>
再将<math>T_i=\phi_{0,i}u_{ii} </math>的表达式代入即可。
<br>
===η的含义===
===η的含义===