确定算法的稳定性?

计算科学 收敛 稳定
2021-12-22 10:01:15

这与我在Stack Overflow上回答的关于计算数字平方根的问题有关。我正在考虑它,并意识到该公式只是一系列算法中的第一个来计算p一个数的根(即求解y=xp为了x)。

xn=(p2)y+j=npn1xjj=npn1k=npkjn1xk

我们可以证明为n结果收敛到正确答案,但我不确定如何寻找其他重要特征,例如收敛速度和稳定性要求。对资源有什么建议吗?

1个回答

您可以做的第一件事是通过实验确定收敛速度。为此,以对数对数比例绘制误差与迭代并检查连接迭代的线的斜率(大约)就足够了。如果该方法收敛得非常快,您可能需要任意精度的实数才能获得足够的数据点。

如果实验没有告诉您该算法至少是二次的,那么如果这种方法有任何用处,我会感到惊讶——基线是牛顿法。