计算科学 - 递归关系中的错误传播 - 吾爱随笔录

计算科学数值分析精确

2021-12-20 04:05:09

我有一个递归关系

P_{n} = A_{n} P_{n - 1} - B_{n} P_{n - 2}

$P_{n} = A_{n} P_{n-1} - B_{n}P_{n-2}$

给定和。 $P_{0}$ $P_{1}$

在数值上，每个和都以某种精度计算。这同样适用于和。如何估计第项的误差？ $A_{n}$ $B_{n}$ $P_{0}$ $P_{1}$ $n$

1个回答

我认为这方面的一个很好的参考是FWJ Olver 的Error Bounds for Linear Recurrence Relations (Mathematics of Computation, 1988)。

在最基本的层面上，您可以检查变化的敏感性。所以一阶导致递归如您所见，误差项满足相同的递推关系，但有一个额外的不均匀项，它取决于中的误差。 $P_n$ $A_m,B_m$

P_{n} + δ P_{n} = (A_{n} + δ A_{n}) (P_{n - 1} + δ P_{n - 1}) - (B_{n} + δ B_{n}) (P_{n - 2} + δ P_{n - 2}),

$P_n+\delta P_n = (A_n+\delta A_n)(P_{n-1}+\delta P_{n-1}) - (B_n + \delta B_n)(P_{n-2} + \delta P_{n-2}),$

P_{n} = A_{n} P_{n - 1} - B_{n} P_{n - 2},

$P_n = A_nP_{n-1} - B_n P_{n-2},$

δ P_{n} = A_{n} δ P_{n - 1} - B_{n} δ P_{n - 2} + (δ A_{n} P_{n - 1} - δ B_{n} P_{n - 2}) .

$\delta P_n = A_n \delta P_{n-1} - B_n \delta P_{n-2} + (\delta A_n P_{n-1} - \delta B_n P_{n-2}).$

A_{n}, B_{n}

$A_n,B_n$

如果您可以找到非齐次递推关系的一般解决方案，并且还对非齐次项设置了界限，那么您将对中的错误进行限制。这类似于 ODE 的有限差分方法的截断误差如何转换为方法全局误差的界限。这通常也称为正向模式灵敏度分析。 $P_n$

这里的一个问题是中的误差通常不是独立的，这种分析可能过于保守；使用区间算术分析递推关系中的舍入误差可能会出现类似的问题。Olver 的论文展示了如何获得严格的界限。 $A_n,B_n$

其它你可能感兴趣的问题