【学习笔记】牛顿迭代法求平方根倒数

简介

介绍使用牛顿迭代法求平方根倒数 1 x \frac{1}{\sqrt{x}} x ​1​的C语言实现和公式的推导。

代码

float InvSqrt(float num)
{float x = 1/num;float xhalf = 0.5f * num;float error = 1e-5;while (fabs(1.0f - num * x * x) >= error){x = x*(1.5f-(xhalf*x*x));}return x;
}

代码很简单，就是使用牛顿迭代法计算，然后判断是否达到想要的精度，达到精度后退出。

这里精度设置是0.00001，可以根据自己实际情况调整。

传进来的值num必须大于0。

可以加入一个判断防止传入的值小于等于0.

float InvSqrt(float num)
{if (num > 0){float x = 1/num;float xhalf = 0.5f * num;float error = 1e-5;while (fabs(1.0f - num * x * x) >= error){x = x*(1.5f-(xhalf*x*x));}return x;}else{return -1;}
}

公式推导

这里说明代码x = x*(1.5f-(xhalf*x*x));是如何得到的。

牛顿迭代法公式如下。

x n + 1 = x n − f ( x n ) f ′ ( x n ) x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} xn+1​=xn​−f′(xn​)f(xn​)​

我们计算平方根倒数的公式：

y = 1 x = x − 1 2 y = \frac{1}{\sqrt{x}} = x^{-\frac 12} y=x ​1​=x−21​

所以

1 y 2 = x \frac{1}{{y}^2} = x y21​=x

构建以y为自变量的函数方程为

f ( y ) = 1 y 2 − x = 0 f(y) = \frac{1}{{y}^2} - x = 0 f(y)=y21​−x=0

​ = y − 2 − x = 0 = {{y}^{-2}} - x = 0 =y−2−x=0

f ′ ( y ) = − 2 y − 3 = 0 f'(y) = {{-2}{y}^{-3}} = 0 f′(y)=−2y−3=0

将$f(y)$和 f ′ ( y ) f'(y) f′(y)带入

y − f ( y ) f ′ ( y ) = y − y − 2 − x − 2 y − 3 y - \frac{f(y)}{f'(y)} = y - \frac{{{y}^{-2}} - x}{{{-2}{y}^{-3}}} y−f′(y)f(y)​=y−−2y−3y−2−x​

​ = y + y − x y 3 2 = y + \frac{{y} - xy^3}{2} =y+2y−xy3​

​ = 3 2 y − 1 2 x y 3 = \frac{3}{2}y - \frac{1}{2}xy^3 =23​y−21​xy3

所以

y n + 1 = 3 2 y n − 1 2 x y n 3 y_{n+1} = \frac{3}{2}{y_n} - \frac{1}{2}x{y_n}^3 yn+1​=23​yn​−21​xyn​3 = 1.5 y n − 0.5 x y n 3 1.5{y_n} - 0.5x{y_n}^3 1.5yn​−0.5xyn​3

上面代码x = x*(1.5f-(xhalf*x*x));就是这样得到。

实际计算，设$x=2$， y 1 = 1 2 = 0.5 y_1 = \frac{1}2 = 0.5 y1​=21​=0.5

y 2 = 1.5 × 0.5 − 0.5 × 2 × 0. 5 3 = 0.625000 y_2 = 1.5×{0.5} - 0.5×2×{0.5^3} = 0.625000 y2​=1.5×0.5−0.5×2×0.53=0.625000

y 3 = 1.5 × 0.625 − 0.5 × 2 × 0.62 5 3 = 0.693359 y_3 = 1.5×{0.625} - 0.5×2×{0.625^3} = 0.693359 y3​=1.5×0.625−0.5×2×0.6253=0.693359

y 4 = 1.5 × 0.693359 − 0.5 × 2 × 0.69335 9 3 = 0.706708 y_4 = 1.5×{0.693359} - 0.5×2×{0.693359^3} = 0.706708 y4​=1.5×0.693359−0.5×2×0.6933593=0.706708

y 5 = 1.5 × 0.706708 − 0.5 × 2 × 0.70670 8 3 = 0.707106 y_5 = 1.5×{0.706708} - 0.5×2×{0.706708^3} = 0.707106 y5​=1.5×0.706708−0.5×2×0.7067083=0.707106

这里经过4次迭代，就得到了 1 2 \frac{1}{\sqrt{2}} 2 ​1​的值。

本文链接：https://blog.csdn.net/u012028275/article/details/113791370

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！