algorithm - 为什么平均阻尼会神奇地加快定点计算器的收敛速度？

Question

我正在阅读 SICP，作者在计算函数的不动点时刷过平均阻尼技术。我知道在某些情况下它是必要的，即平方根以抑制函数的振荡y = x/y但是，我不明白为什么它会神奇地帮助定点计算函数的收敛。帮助？

编辑

显然，我已经考虑了一些。我似乎无法理解为什么在重复应用时平均一个函数会加速收敛。

Answer 1

它只会加速那些重复应用程序“绕过”固定点的功能。直观地说，这就像在钟摆上加了一个刹车——刹车会更快停止。

但并不是每个函数都有这个属性。考虑f(x)=x/2。这个函数在没有平均阻尼的情况下会更快收敛（log base 2 steps vs log base (4/3) steps），因为它从一侧接近固定点。

Answer 2

虽然我无法在数学基础上回答您的问题，但我会尝试一个直观的问题：定点技术需要围绕其 ..well.. 定点的“平面”函数图。这意味着：如果您在 XY 图表上描绘您的定点函数，您会看到该函数在真实结果处与对角线 (+x,+y) 正好相交。在您的定点算法的一个步骤中，您正在猜测一个 X 值，该值需要位于一阶导数介于 (-1..+1) 之间的交点周围的区间内，并取 Y 值。您采用的 Y 将更靠近交点，因为从交点开始，沿着坡度小于 +/-1 的路径可以到达，与您使用的前一个 X 值相反，在这个意义上，它具有精确的斜率 -1。现在很清楚，当使用 Y 作为新 X 时，斜率越小，越接近交点（真正的函数值）。最好的插值函数通常是一个常数，斜率为 0，给你第一步的真实值。

对不起所有的数学家。