计算机数学基础: sqrt平方根(函数零点)近似求解算法 - 根号2计算
计算机数学基础: sqrt平方根(函数零点)近似求解算法 - 根号2计算
一、背景介绍
根号2是个很常见的数, 并且是个无理数, 你知道他的数值是多少吗? 可能有大神直接开始1.414.....
(关于他还有个非常知名的数学故事, 但我们今天不聊故事)
但我们今天不考察记忆力, 而是简单的聊一聊关于他的计算方法
更准确的说是在数值计算中关于平方根求解又或者说是方程根(函数零点)近似求解的方法
即实现下面这个常用的函数
sqrt(2)
二、对平方根问题进行数学建模
我们可以把根号2当成一个未知数X, 然后就获得了f(x)这个函数 , 也就对应上图中的函数图像
此时我们已经把一个a=2的平方根问题转为了求解f(x)正零点(方程f(x)=0的正根) 问题了
二、方法一 - 二分法求解
2.1 核心概念 - 二分查找
维基百科介绍
2.2 连续区间/函数 - 离散化
基于上面二分查找的基本概念, 我能可以简单理解一般能应用这个算法的问题, 具有一下特征:
- 可存储到数组中
- 数组中的值是有序的(单调的)
首先我们可以轻易确定查找区间为[0, 2], 以0.01为间隔对f(x)在区间[0, 2]进行离散化(这里假设误差为0.01)
就可以得到一个
长度为200, index为索引对应f(index * tolerance)函数值的 -- 有序数组f(index * tolerance)_value[0,..,200]
2.3 求解过程 - 动画
通过二分查找, 每次都把问题规模将为原来的二分之一, 也就是logN的复杂度
其中这个N = 区间长度 / 误差
当达到容忍误差要求时即查找区间小于误差
就结束计算并返回对应结果(区间中的任意值), 这个结果就是根号2的近似值
2.4 代码实现
def sqrt_binary_serach(target, tolerance=0.001):
#assert target > 0
interval = [0, target]
def f(x):
return x * x - target
fx_value = f(target)
while True:
# 计算新的估计值 Xn+1 = Xn - F(Xn) / F'(Xn)
mid = (interval[0] + interval[1]) / 2
fx_value = f(mid)
if fx_value == 0:
return mid
if fx_value > 0:
interval[1] = mid # 更新区间右值
else:
interval[0] = mid # 更新区间左值
# 计算误差, 符合要求误差就break出
if abs(interval[0] - interval[1]) < tolerance:
break
return interval[0]
三、方法一 - 牛顿迭代法求解
实际应用: Fast inverse square root - 雷神之锤 III 竞技场 - Quake III Arena
3.1 核心概念 - 泰勒级数/函数近似
在一个“邻域”通过泰勒展开对原函数做近似, 获得一个较好计算的近似函数表示
牛顿迭代为了求解方便, 只取了展开式的前两项 - 做线性近似
通过求解这个线性近似函数的(正)零点, 进而获得原函数的零点的近似解
3.2 收敛条件及迭代法
由于只是线性近似, 上述展开式x0取值(常)很难足够接近零点, 导致零点(实际解)和x0的距离往往不是一个理想且足够小的"邻域"
这种情况下, 只做一次求解, 往往误差比较大, 但可以确定的是当在查找区间中原函数f(x)满足:
- 一阶导数f'(x)不为0
- 二阶导数f''(x)连续
此时牛顿法是向实际解收敛的
既然是收敛的, 我们就可以使用迭代法进行逐渐逼近, 对上面这个基于x0展开的线性近似函数, 反解决出X
这个X就是X1, 同时这个表达是也就是牛顿迭代法的迭代公式
3.3 求解过程 - 动画
牛顿迭代法多数情况下都是二次收敛的, 所以对于平方根求解问题其算法复杂度是通常是优于二法分logN的
3.4 代码实现
# 计算平方根: f(x) = x^2 - a
def sqrt_newton(target, tolerance=0.0001):
Xn = target # 牛顿迭代法的初始估计值
while True:
# 计算新的估计值 Xn+1 = Xn - F(Xn) / F'(Xn)
new_Xn = Xn - (Xn * Xn - target) / (2 * Xn)
# 检查新的估计值是否足够接近旧的估计值
if abs(new_Xn - Xn) < tolerance:
break
# 更新估计值
Xn = new_Xn
return Xn
四、对应的数学动画视频
CSMathBase: 二分法计算平方根近似解 算法动画解析
计算机数学基础: 函数零点近似求解 牛顿迭代法 动画
五、最后/Other
欢迎大家到评论区讨论, 如果你喜欢这个文章的话也欢迎点赞 收藏 和关注哦
我是 Sunrisepeak言峰 一个开源软件[开发/爱好]者 不定期更新 开源项目 / 技术 / Thinking 相关的文章和视频
Ref