为什么要加宽算子？
因为当格的偏序集合L不满足升链条件，从最小元迭代计算最小不动点的过程是不收敛的，即迭代序列(fⁿ(⊥))ₙ不保证最终稳定，且其最小上界不保证等于最小不动点，因此需要一种近似lfp(f)的方法。引入加宽算子fw:L×L—>L, fw(x)=x▽f(x)，可以将L上的一个序列转为收敛的升链，从L的最小元开始迭代不断上升，直至lfp(f)的一个上近似即fw的最小不动点lfp(fw)，关系式为lfp(f)<=f(lfp(fw))<=fw(lfp(fw))=lfp(fw)。对上式反复应用f单调得到：lfp(f)<=fⁿ⁺¹(lfp(fw))<=fⁿ(lfp(fw))<=…<=f(lfp(fw))<=lfp(fw)，这表明对lfp(fw)使用f迭代可获得更精确的上近似，其过程可看成沿一个递降链进一步逼近lfp(f)，但L不一定满足降链条件而导致上述过程不收敛，故需要引入变窄算子fn:L×L—>L, fn(x)=x△f(x)，将L的一个序列转为收敛的降链，从lfp(fw)开始迭代，不断下降直至fn的一个不动点fp(fn)，则有关系式：lfp(f)<=fp(fn)<=lfp(fw)。注意，这里根据加宽算子的定义可知fw是单调的，但根据变窄算子的定义不确定fn是否单调，故从lfp(fw)迭代求得的fp(fn)，不确定是最小还是最大不动点，只能说是一个不动点，这也反映了变窄算子不需要满足单调性，就可以更加逼近lfp(f)
posted on 2023-09-06 22:45
春秋十二月 阅读(40)
评论(0) 编辑 收藏 引用 所属分类:
Compiler