03 | 迭代法：不用编程语言的自带函数，你会如何计算平方根？
在编程与数学的交汇点，计算平方根是一项基础而重要的技能。尽管现代编程语言如Python、Java、C++等都提供了直接计算平方根的内置函数（如Python的math.sqrt()），但了解不使用这些内置函数，通过迭代法手动计算平方根的原理与方法，对于深入理解数值计算、算法设计以及数学原理有着不可估量的价值。本章将深入探讨几种经典的迭代算法，用于计算任意非负实数的平方根。
一、引言
平方根是一个数的平方等于给定数的非负实数。例如，4的平方根是2，因为2的平方等于4。在数学和计算机科学中，计算平方根的方法多种多样，从简单的二分搜索到复杂的牛顿迭代法，每种方法都有其独特的适用场景和性能特点。迭代法因其简单性和高效性，在实际应用中尤为常见。
二、二分搜索法求平方根
二分搜索法（Binary Search）是一种在有序数组中查找特定元素的快速算法，但也可以巧妙地用于计算平方根。基本思路是，对于给定的非负实数x，我们知道其平方根一定位于0和x之间（对于x=0，平方根为0，此处作为特殊情况处理）。通过不断缩小这个区间，我们可以逼近真实的平方根值。
算法步骤：
- 初始化：设置两个指针
left = 0和right = x，表示平方根可能存在的区间。 - 循环条件：当
left <= right时执行循环。 - 计算中点：
mid = left + (right - left) / 2，避免大数相加导致的溢出。 - 判断与调整：
- 如果
mid*mid等于x，则找到了精确的平方根，返回mid。 - 如果
mid*mid小于x，说明真实平方根在mid的右侧，更新left = mid + 1。 - 如果
mid*mid大于x，说明真实平方根在mid的左侧，更新right = mid - 1。
- 如果
- 循环结束：当
left > right时，循环结束，此时left或right（由于更新规则，两者相邻）即为所求平方根的近似值（根据精度要求，可能需要额外处理）。
注意：由于浮点数运算的精度限制，二分搜索法得到的平方根是一个近似值，其精度取决于循环的终止条件（如left - right < epsilon，其中epsilon是一个很小的正数，表示精度要求）。
三、牛顿迭代法（Newton’s Method）
牛顿迭代法，又称牛顿-拉弗森方法（Newton-Raphson method），是一种在实数域和复数域上近似求解方程的方法。对于平方根的计算，我们可以将其转化为求解方程f(y) = y^2 - x = 0的根。牛顿迭代法的基本思想是从一个初始猜测值开始，通过迭代不断逼近真实解。
算法步骤：
- 选择初始猜测值：通常选择
y0 = x / 2作为初始猜测值，因为对于任意非负实数x，其平方根不会超过x/2（除非x非常小或为零）。 - 迭代公式：根据牛顿迭代法的原理，迭代公式为
yn+1 = yn - f(yn) / f'(yn)。将f(y) = y^2 - x代入，得到yn+1 = (yn + x / yn) / 2。 - 迭代过程：使用上述迭代公式，从
y0开始，不断计算新的yn+1，直到满足某个终止条件（如|yn+1 - yn| < epsilon）。 - 输出结果：当满足终止条件时，
yn+1即为所求平方根的近似值。
优点：牛顿迭代法通常比二分搜索法收敛得更快，特别是对于接近真实解的初始猜测值。然而，其性能也依赖于初始猜测值的选择，不恰当的初始值可能导致算法不收敛或收敛到错误的解。
四、其他迭代方法简述
除了二分搜索法和牛顿迭代法外，还有其他一些迭代方法可用于计算平方根，如割线法（Secant Method）、固定点迭代法（Fixed-Point Iteration）等。这些方法各有特点，但基本原理相似，都是通过不断迭代逼近真实解。
- 割线法：是牛顿迭代法的一种近似，使用前两次迭代的结果来构造一条割线，以此割线与x轴的交点作为新的迭代值。
- 固定点迭代法：选择一个合适的函数
g(y)，使得g(y)的固定点（即满足y = g(y)的y值）即为所求方程的解。通过不断迭代y = g(y)来逼近固定点。
五、实际应用与注意事项
在实际应用中，选择哪种迭代方法取决于具体问题的需求、初始值的易得性、算法的收敛速度以及计算资源的限制。对于平方根的计算，牛顿迭代法因其高效性和广泛适用性而备受青睐。然而，无论采用哪种方法，都需要注意浮点数的精度问题，以及迭代过程中可能出现的数值稳定性问题。
此外，虽然迭代法能够手动实现平方根的计算，但在实际编程中，直接使用编程语言提供的内置函数往往更为高效和便捷。因此，了解这些迭代方法更多是为了深入理解数值计算的本质和算法设计的思想，而非完全替代内置函数的使用。
六、总结
本章介绍了通过迭代法计算平方根的几种经典方法，包括二分搜索法和牛顿迭代法。这些方法不仅展示了迭代法在数值计算中的应用，也体现了算法设计与数学原理的紧密结合。通过学习和掌握这些迭代方法，读者可以更加深入地理解数值计算的精髓，为后续的编程和算法学习打下坚实的基础。同时，也应注意到，在实际应用中，应根据具体问题的需求选择合适的算法，并关注数值稳定性和计算效率等关键问题。
