前面我们尽量保持同一个输出要求,再改变实现。现在给要求本身增加一个明确的余量:如果结果只需要精确到某个范围,可以怎样停止?
预计用时:40 分钟。打开 何时足够,从求 √2、目标半宽 10^-6 开始。
平方根是满足 y²=x 的非负数。对 x=2,可以先用区间 [0,2]。取中点 1,它的平方小于 2,所以根在 [1,2];再取 1.5,平方大于 2,于是根在 [1,1.5]。每次根据中点把区间缩小一半。
在精确实数运算下,根始终留在区间里。如果区间半宽不超过 ε,中点与根的距离也不超过 ε。这就是停止条件的来源,而不是“做够二十次应该差不多”。
区间宽度按 初始宽度 / 2^次数 缩小,因此多保留一位二进制精度大约需要再缩一次。图用对数纵轴显示半宽,让后面的微小变化仍能看见。
先猜:把目标从 10^-3 改成 10^-6,迭代次数会翻倍、增加固定几步,还是完全不变?实际拖动参数,记录次数与停止原因。
实现返回每轮的 lo、hi、mid、halfWidth 和 residual,页面调用的是这份真实轨迹。求 √2、容差 10^-6 时,本实现记录 21 次中点计算,返回约 1.4142141342163086。这里的计数包含最后一次检查目标的中点计算。
把容差继续调到 10^-18。随着区间缩小,中点可能被舍入成某个端点。再按同样规则更新,就无法取得新进展。实现检测这个条件,报告 stagnation,而不会无限重复。
因此我们区分三种停止:达到目标半宽、有限精度停滞、达到迭代上限。返回了一个数,不自动意味着满足了最初目标。
还有一个更细的边界:分支依据是浮点计算的 mid*mid < x。接近精度极限时,平方比较本身也有舍入误差。精确算术中的区间证明不能直接变成这段浮点代码的严格误差认证;那需要额外的舍入控制或更可靠的区间计算。
页面与 Math.sqrt 对照,是检查程序行为的一个参考;Math.sqrt 的输出同样是有限表示,不能称作精确实数真值。
实际应用通常应优先选择适合任务的成熟数值库。本例的作用是让“迭代、可观察进展、停止条件、失败原因”变得具体。类似结构会出现在解方程、优化和模拟中,那里未必有一个直接的系统函数。
不同方法每步花费和收敛速度不同。有的方法需要导数,有的依赖好的初值,有的能维护区间。比较它们时要包括每步成本、失败范围和所需精度,不能只看迭代次数。
固定 x=2,比较至少三个容差;再换 x=100,解释为什么起始区间不同会影响步骤。保留一次达到目标和一次停滞的轨迹。
选做:允许读者设置最大迭代次数,并让页面明确呈现 limit。验收需包含上限 1、不可能在给定上限内达到的目标,以及正常成功路径;任何停止都要保留真实原因。
下一节把数学容差放回用途,给 误差和时间各留一份预算。