Python趣味算法入门 - 牛顿迭代法求方程根

问题描述

编写用牛顿迭代法求方程根的函数。方程为，系数a，b，c，d由主函数输入，求x在1附近的一个实根。求出根后，由主函数输出。

牛顿迭代法的公式：，设迭代到  时结束。

分析

在网上可以找到很多关于牛顿迭代法的专业文章，包括应用该方法求方程根的限制与条件等等。问哥在这里就不深入探讨了，以免显得业余。这里仅简单介绍原理，方便大家就地了解编写代码解决此问题。

牛顿迭代法的基本原理是导数的概念，以及如何求导。

方程  求导方法为

也就是

上面对只求导一次，得到的一元二次方程式，称作1阶导数，代表的是原方程式中对任意点做切线，该切线的斜率（计算方法）。

题目中是求一元三次方程的根，为了快速介绍，下面简化成一元二次，因为原理都是一样的。以下图为例，坐标中的函数是  ，而我们要求70的平方根，相当于是在坐标中求当y=0时，x的取值。

对  求导可得 ，代表的就是上任一点切线的斜率。

然后，使用牛顿迭代法求  可分为以下几步：

1. 设定一个初始值，这个值其实是估算的，距离我们要求的结果越接近越好，比如图中，我们设定初始值为15；
2. 可以计算出当x取值15时，对应原方程坐标图中y的取值为，所以代入导数计算公式，可在该方程中对坐标点 (15,155) 做切线 ，该切线的斜率为
3. 所谓斜率，就是 ，而我们要求出对应x坐标轴上线段  的长度，就是用除以斜率，也就是 （图中橘色的垂直线段长度除以斜率）
4. 然后用  减去  ，得到，也就是。肉眼可见，该值向我们要求解的最终答案（ 的根）更近了一步。
5. 然后重复步骤1到4，得到新的，直到前后两次迭代在x轴上的距离小于某个极小值，比如，我们就可以认为，得到一个误差足够小的正确解。

回到我们的一元三次方程中来，我们已经知道  以及1阶导数  的计算方法，按照上面例子中的步骤，一步步如法炮制，我们可以编写代码如下：

def fun(a,b,c,d,x0):
    x = 1 # 题目要求为1附近
    while abs(x-x0)>1e-5: # 判定迭代结束条件，最后两次迭代的值距离小于0.00001时结束迭代
        x = x0
        f = a*x**3+b*x**2+c*x+d # 原方程式
        fd = 3*a*x**2+2*b*x+c # 步骤2，1阶导数方程式，代表该点切线的斜率
        h = f/fd # 步骤3，根据斜率求坐标上的距离
        x0 -= h # 步骤4，得到新的x0
    return x0

其中，a，b，c，d为方程的系数，x0为我们估算的初始值，这里可以使用原书中的1.5，也可以换成其他值，通常情况下，该值越接近最终解，迭代次数越少，最终解越精确。比如已知最终解约等于2，你可以自己试试1.,8或者1.9？ 

输出

print(fun(2,-4,3,-6,1.5))
2.0000000000163607