numerical-stability - 在线更新向量和的数值稳定算法

Question

给定一个向量 v，我想在变量 sum_v 中跟踪其元素的总和。向量 v 的每个元素 i 是权重向量 w_i 与其他向量 d_i 的点积。所以，每次 d_i 改变时，v 也会改变。我一直在更新 sum_v，只要 d_i 改变，我就会根据 v_i 的变化来改变它。不幸的是，小的数值不稳定性很快就会增加。

我可以使用哪些有效的技术来防止这种情况发生？

编辑：现在，每当 d_i 更改时，我的算法都会花费恒定的时间来更新 sum_v。我想保持在 log(n) 以下，其中 n 是 v 的长度。

Answer 1

一种解决方案是构建一个完整的二叉树，使得每个叶子代表 v_i 的一个元素，而父母代表他们孩子的总和。更改 v 的一个元素需要对数时间来过滤对 sum_v 的更改，但是对于消除增量而言，结果在数值上是稳定的，尽管对于消除 v 的相邻元素来说不是。

找到一种方法来保持它对这两个问题的数值稳定是一个有趣的问题。