好好学Java：从零基础到项目实战
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

2.4.1　利用牛顿迭代法求平方根

虽然Java自带了数学函数库Math，但是该库仅支持开方运算中的开平方，并不支持开N次方的运算，连计算三次方根也无能为力。比如求解27的三次方根，中学生都知道27的三次方根为3，但求三次方根的Java代码该怎么写呢？换句话说，Math库的开平方函数sqrt是怎样实现的呢？开三次方与开二次方，乃至开N次方，本质上解法是一样的，只要掌握了具体的解题思路，开多少次方均可触类旁通。现在问题在于，Java的基础运算只有加减乘除四则运算，如何才能利用四则运算实现开N次方根的功能呢？

在计算器发明之前，普通人要计算一个数的N次方根，可以先猜个约数，求得该约数的N次方，再与这个数比较，结果比这个数大则约数改小，结果比这个数小则约数改大。如此重复多次，直到约数的N次方足够接近这个数，那么该约数即可近似为这个数的N次方根。然而落实到编码上就不容易了，一方面约数怎么猜，另一方面约数改小要改多小，约数改大又要改多大，这些都是很模糊的说法，没法写到代码里面。因为人类动脑子的同时用到了经验，猜多猜少依据的是后天获得的经验，但一段简单的计算机程序犹如学龄前幼儿，什么经验都没有，连瞎猜也不会，必须告诉它准确无误的做法才行。也就是说，每行程序代码都得由明确的数字与符号组成，就像求解方程式那样，严格按照式子开展运算，这样才能求得精确的数值。

仅仅依靠加减乘除就想计算N次方根，这不是天方夜谭，而是一种巧妙的数学解法，叫作“牛顿迭代法”。顾名思义，该解法是牛顿发现的，正如苹果砸到牛顿头上促使他发现了万有引力定律一样，牛顿对着N次方程式的函数曲线冥思苦想发现了牛顿迭代法。假定某个数字为a，它的N次方根为x，则方程式可写作a=xn。把a挪到等号右边，此时方程式变为0=x2－a，对应的函数式为f(x)=xn－a，其中f(x)=0的时候可求得方根x的数值。

简单起见，假设n=2、a=2，则函数式f(x)=xn－a可简化为f(x)=x2－2，该式子对应一条二次函数曲线，具体如图2-1所示。

图2-1　f(x)=x2－2的函数曲线

从图2-1可见，该曲线经过坐标点(0,-2)，并且它与x轴有两个交点，其中右边的交点落在(1,0)与(2,0)之间，这里将该交点记作x0，显然x0的横坐标数值即为原函数式的解。为了求得x0的横坐标，牛顿想了一个办法，他先在x轴上挑一个坐标点(3.5,0)，并将该点记作x1。接着在x1画一条垂线与曲线f(x)交汇，并在交点处描绘函数曲线的切线，切线与x轴相交于坐标点x2。继续在x2画一条垂线与曲线f(x)交汇，仍在交点处描绘函数曲线的切线，新切线与x轴相交于坐标点x3。此时添加了垂线和切线的坐标系空间，如图2-2所示。

图2-2　对函数曲线交替做垂线与切线的示意图

观察这几个点的位置，可知x1到x2再到x3，其值逐渐逼近x0，倘若在x3位置重复画垂线、描绘切线的操作，新求得的xm必然越来越趋向于x0，如此便能计算出方根的近似值。

在坐标系上画垂线很容易，但描绘曲线某点的切线就不简单了，因为你不知道该切线的斜率是多少。从几何角度看，切线与曲线只有一个交点，且在交点处二者近乎重合。物理学上有一个自由落体运动公式，其中g表示重力加速度（值为9.8m/s2），t为下落时间，S为下落高度，这个自由落体曲线与前面讲的二次函数曲线相似，此时切线的斜率等价于物体在该时间点的瞬时速度V=gt。在代数学体系中，函数式f(x)对应的斜率式子为f'(x)，它被称作原函数式的导数，意思是引导方向的函数。就式子f(x)=xn-a而言，它的导数为f'(x)=nxn-1，倘若已知x的具体值，则f'(x)求得的导数即为该点切线的斜率。

假设从坐标点xm开始做曲线方程f(x)=xn－a的垂线，并在垂线与曲线的交点处做切线，且该切线与x轴相交于xm + 1点，则包含曲线、垂线、切线在内的坐标系如图2-3所示。

图2-3　函数曲线在xm处的垂线与切线

此时可求得垂线与曲线的交点坐标为，根据斜率公式可得，分别代入，方程式变为，一番计算后求得，该结果正是点的横坐标值。由求得的数值之后，还可如法炮制求得、等各点的数值，并且、越来越接近点，如此反复迭代多次，的数值将非常逼近方根的真实值。以上求解的整个过程便构成了牛顿迭代法，通过多次迭代运算，从而求得N次方程式的方根近似值。

当然，上述的迭代式无疑太复杂了，因为该式子为N次方程的迭代式。对于二次方程式来说，可将n=2代入，于是迭代式可逐步简化，，最终得到的便是求平方根所需的迭代式。

接下来，利用求平方根的迭代式计算数字2的平方根，且令变量Xm从数字自身开始迭代3次，据此编写的示例代码如下（完整代码见本章源码的src\com\arithmetic\Pingfanggen.java）：

        double number=2;                  // 需要求平方根的数值
        double Xm=number;                  // 每次迭代后的数值
        Xm=(Xm + number/Xm) / 2;          // 第一次迭代后的平方根
        System.out.println(number+"的平方根="+Xm);
        Xm=(Xm + number/Xm) / 2;          // 第二次迭代后的平方根
        System.out.println(number+"的平方根="+Xm);
        Xm=(Xm + number/Xm) / 2;          // 第三次迭代后的平方根
        System.out.println(number+"的平方根="+Xm);

运行上面的求方根代码，打印出来的日志如下：

2.0的平方根=1.5
2.0的平方根=1.4166666666666665
2.0的平方根=1.4142156862745097

由日志可见，仅需3次迭代，求得的平方根数值1.414就精确到了小数点后面3位。

把代码里的number取值改成3，准备求数字3的平方根，重新运行修改后的求方根代码，打印出来的日志如下：

3.0的平方根=2.0
3.0的平方根=1.75
3.0的平方根=1.7321428571428572

可见3次迭代之后，计算出来的1.732依然精确到了小数点后面3位，说明通过牛顿迭代法求方根的效率很高。同理，可由式子推出3次方根、4次方根的迭代计算代码，有兴趣的读者不妨动手实践。

上一章目录下一章