秦九邵算法，牛顿迭代算法，盛金公式

• 1.牛顿迭代法
• • (1)为什么要牛顿迭代
  • (2)实现牛顿跌代
• 2.秦九邵算法
• • (1).历史由来
  • (2).算法介绍
• 3.盛金公式

啥是牛顿迭代法？大大的疑问
在用程序解方程的时候，我们通过循环遍历查找答案，直到找到答案，比如求解， y = x 2 + c ( c < 0 ) y=x^2+c (c<0) y=x2+c(c<0)
那么求解x的值，就是找到一个x，使x^2近似c，下面是代码

#include
#include
#include
using namespace std;

int main()
{
	double x = 0;
	int c = -3;
	int sum=0;
	for (x;; x += 0.0001)  //x是解，每次加0.0001
	{
		if (abs(x * x + c) < 1e-3)  //当x^2+c=0近似看成接近0
		{
			break;
		}
		
		else
		{
			sum+=1;
		}
	}
	cout << "方程x^2+c=0的解是" << x;
	cout << endl << "计算次数:" << sum;
	return 0;
}

首先肯定的是这种解法是可以的，而且很容易想到，用二分求解应该也是可以的。但是计算量很大！那么牛顿迭代要做什么呢？就是使求解的步骤减少，减小运算量。

所以要首先知道牛顿迭代的作用就是使求解的计算量减少！
专业一点：牛顿迭代法使一种快速求解函数零点的方法！

还是求解上面的函数：
y = x 2 + c , 令 y = 0 , 所 以 x 2 + c = 0 y=x^2+c,令y=0,所以x^2+c=0 y=x2+c,令y=0,所以x2+c=0

首先任意选取一个初始值，找图像上的点 ( x 0 , f ( x 0 ) ) , (x_0,f(x_0)), (x0​,f(x0​)),过该点做一条切线交x轴于 ( x 1 , 0 ) (x_1,0) (x1​,0)，显然，该切线的斜率为 f ′ ( x 0 ) = 2 x 0 fprime(x_0)=2x_0 f′(x0​)=2x0​，过该点的切线方程为： y − y 0 = k ( x − x 0 ) y-y_0=k(x-x_0) y−y0​=k(x−x0​),带入 k , y 0 , x 0 ， y = 2 x 0 ( x − x 0 ) + x 0 2 + c . k,y_0,x_0，y=2x_0(x-x_0)+x_0^2+c. k,y0​,x0​，y=2x0​(x−x0​)+x02​+c.
该方程与x轴的新交点为 ( x 1 , 0 ) (x_1,0) (x1​,0),显然 x 1 = 1 2 ( x 0 − c x i ) x1=frac 12(x_0-frac{c}{x_i}) x1=21​(x0​−xi​c​),由于 x 0 , x 1 x_0,x_1 x0​,x1​都是未知量，所以一次推导就可以归纳迭代式： x i + 1 = 1 2 ( x i − c x i ) x_{i+1}=frac12(x_{i}-frac{c}{x_i}) xi+1​=21​(xi​−xi​c​).每次迭代都去计算一下 x i 2 + c x_i^2+c xi2​+c,可以认为当其值无限逼近0的时候看作最终解。即 x i 2 + c < = 1 e − 6 x_i^2+c<=1e-6 xi2​+c<=1e−6.
下面是代码

#include
#include
using namespace std;

double x0, x1;
int main()
{
	int sum = 0;
	int c = -3;
	x0 = -c;
	bool k = true;
	while (k)
	{
		x1 = 0.5 * (x0 - c / x0);
		if (x1 * x1 + c < 1e-6)
			break;
		sum += 1;
		x0 = x1;
	}
	cout <<"答案是："< 
 
 
两个程序，第一个计算了17000多次，第二个计算了3次。虽然和x一开始的取值有关，但是可见差距。好了，这就是牛顿迭代法
 总节一下：求解一个方程，只要模拟一次逼近零点求解的过程，找到x0，x1的关系，然后迭代即可。注意，要选取合适的x初始值
 
 
2.秦九邵算法 
(1).历史由来 
秦九韶算法是中国南宋时期的数学家秦九韶提出的一种多项式简化算法。在西方被称作霍纳算法。秦九韶（约公元1202年－1261年），字道古，南宋末年人，出生于鲁郡（今山东曲阜一带人）。
 早年曾从隐君子学数术，后因其父往四川做官，即随父迁徙，也认为是普州安岳（今四川安岳县）人。
 
(2).算法介绍 
一般地，一元n次多项式的求值需要经过(n+1)*n/2次乘法和n次加法，而秦九韶算法只需要n次乘法和n次加法。在人工计算时，一次大大简化了运算过程。
 
    
     
      
       
        f
       
       
        (
       
       
        x
       
       
        )
       
       
        =
       
       
        
         a
        
        
         n
        
       
       
        
         x
        
        
         n
        
       
       
        +
       
       
        
         a
        
        
         
          n
         
         
          −
         
         
          1
         
        
       
       
        
         x
        
        
         
          n
         
         
          −
         
         
          1
         
        
       
       
        +
       
       
        
         a
        
        
         
          n
         
         
          −
         
         
          2
         
        
       
       
        
         x
        
        
         
          n
         
         
          −
         
         
          2
         
        
       
       
        +
       
       
        .
       
       
        .
       
       
        .
       
       
        +
       
       
        
         a
        
        
         2
        
       
       
        
         x
        
        
         2
        
       
       
        +
       
       
        
         a
        
        
         1
        
       
       
        x
       
       
        +
       
       
        
         a
        
        
         0
        
       
      
      
       f(x)=a_nx^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_2x^2+a_1x+a_0
      
     
    f(x)=an​xn+an−1​xn−1+an−2​xn−2+...+a2​x2+a1​x+a0​
 给一个x带入方程，怎么求解呢?最暴力的方法就是一个个算，那么第一项算n次，第二项算n-1次，那么第n项算1次，一共算多少次？
 
    
     
      
       
        1
       
       
        +
       
       
        2
       
       
        +
       
       
        3
       
       
        +
       
       
        4
       
       
        +
       
       
        5
       
       
        +
       
       
        .
       
       
        .
       
       
        .
       
       
        +
       
       
        n
       
       
        =
       
       
        x
       
      
      
       1+2+3+4+5+...+n=x
      
     
    1+2+3+4+5+...+n=x
 
    
     
      
       
        n
       
       
        +
       
       
        n
       
       
        −
       
       
        1.......
       
       
        +
       
       
        3
       
       
        +
       
       
        2
       
       
        +
       
       
        1
       
       
        =
       
       
        x
       
      
      
       n+n-1.......+3+2+1=x
      
     
    n+n−1.......+3+2+1=x
 
    
     
      
       
        (
       
       
        n
       
       
        +
       
       
        1
       
       
        )
       
       
        +
       
       
        (
       
       
        n
       
       
        −
       
       
        1
       
       
        +
       
       
        2
       
       
        )
       
       
        +
       
       
        (
       
       
        n
       
       
        −
       
       
        2
       
       
        +
       
       
        3
       
       
        )
       
       
        +
       
       
        .
       
       
        .
       
       
        .
       
       
        .
       
       
        +
       
       
        (
       
       
        n
       
       
        +
       
       
        1
       
       
        )
       
       
        =
       
       
        x
       
       
        +
       
       
        x
       
      
      
       (n+1)+(n-1+2)+(n-2+3)+....+(n+1)=x+x
      
     
    (n+1)+(n−1+2)+(n−2+3)+....+(n+1)=x+x
 
    
     
      
       
        (
       
       
        n
       
       
        +
       
       
        1
       
       
        )
       
       
        ∗
       
       
        n
       
       
        =
       
       
        2
       
       
        ∗
       
       
        x
       
      
      
       (n+1)*n=2*x
      
     
    (n+1)∗n=2∗x
 
    
     
      
       
        x
       
       
        =
       
       
        
         
          (
         
         
          n
         
         
          +
         
         
          1
         
         
          )
         
         
          ∗
         
         
          n
         
        
        
         2
        
       
      
      
       x=frac{(n+1)*n}{2}
      
     
    x=2(n+1)∗n​
 显然，需要算x次这么多，，那么秦九昭算法可以大大减少计算量；
 
    
     
      
       
        f
       
       
        (
       
       
        x
       
       
        )
       
       
        =
       
       
        (
       
       
        
         a
        
        
         n
        
       
       
        
         x
        
        
         n
        
       
       
        +
       
       
        
         a
        
        
         
          n
         
         
          −
         
         
          1
         
        
       
       
        
         x
        
        
         
          n
         
         
          −
         
         
          1
         
        
       
       
        +
       
       
        .
       
       
        .
       
       
        .
       
       
        +
       
       
        
         a
        
        
         1
        
       
       
        )
       
       
        ∗
       
       
        x
       
       
        +
       
       
        
         a
        
        
         0
        
       
      
      
       f(x)=(a_nx^n+a_{n-1}x^{n-1}+...+a_1)*x+a_0
      
     
    f(x)=(an​xn+an−1​xn−1+...+a1​)∗x+a0​
 
    
     
      
       
        =
       
       
        (
       
       
        (
       
       
        
         a
        
        
         n
        
       
       
        
         x
        
        
         n
        
       
       
        +
       
       
        
         a
        
        
         
          n
         
         
          −
         
         
          1
         
        
       
       
        
         x
        
        
         
          n
         
         
          −
         
         
          1
         
        
       
       
        +
       
       
        .
       
       
        .
       
       
        .
       
       
        +
       
       
        
         a
        
        
         2
        
       
       
        )
       
       
        ∗
       
       
        x
       
       
        +
       
       
        
         a
        
        
         1
        
       
       
        )
       
       
        ∗
       
       
        x
       
       
        +
       
       
        
         a
        
        
         0
        
       
      
      
       =((a_nx^n+a_{n-1}x^{n-1}+...+a_2)*x+a_1)*x+a_0
      
     
    =((an​xn+an−1​xn−1+...+a2​)∗x+a1​)∗x+a0​
 
    
     
      
       
        =
       
       
        (
       
       
        (
       
       
        (
       
       
        
         a
        
        
         n
        
       
       
        
         x
        
        
         n
        
       
       
        +
       
       
        
         a
        
        
         
          n
         
         
          −
         
         
          1
         
        
       
       
        
         x
        
        
         
          n
         
         
          −
         
         
          1
         
        
       
       
        +
       
       
        .
       
       
        .
       
       
        .
       
       
        +
       
       
        
         a
        
        
         3
        
       
       
        )
       
       
        ∗
       
       
        x
       
       
        +
       
       
        
         a
        
        
         2
        
       
       
        )
       
       
        ∗
       
       
        x
       
       
        +
       
       
        
         a
        
        
         1
        
       
       
        )
       
       
        ∗
       
       
        x
       
       
        +
       
       
        
         a
        
        
         0
        
       
      
      
       =(((a_nx^n+a_{n-1}x^{n-1}+...+a_3)*x+a_2)*x+a_1)*x+a_0
      
     
    =(((an​xn+an−1​xn−1+...+a3​)∗x+a2​)∗x+a1​)∗x+a0​
 …
 …
 
    
     
      
       
        =
       
       
        (
       
       
        .
       
       
        .
       
       
        .
       
       
        (
       
       
        (
       
       
        
         a
        
        
         n
        
       
       
        x
       
       
        +
       
       
        
         a
        
        
         
          n
         
         
          −
         
         
          1
         
        
       
       
        )
       
       
        ∗
       
       
        x
       
       
        +
       
       
        
         a
        
        
         
          n
         
         
          −
         
         
          2
         
        
       
       
        )
       
       
        ∗
       
       
        x
       
       
        +
       
       
        .
       
       
        .
       
       
        .
       
       
        .
       
       
        .
       
       
        +
       
       
        
         a
        
        
         1
        
       
       
        )
       
       
        ∗
       
       
        x
       
       
        +
       
       
        
         a
        
        
         0
        
       
      
      
       =(...((a_nx+a_{n-1})*x+a_{n-2})*x+.....+a_1)*x+a_0
      
     
    =(...((an​x+an−1​)∗x+an−2​)∗x+.....+a1​)∗x+a0​
 
规律是否很明显了？
 也就是说，只要把最里层的算出来，然后按规律往外面相加相乘，最后可以得到答案.
 
 
 
先算(an*x+an-1),然后往外面扩展,先乘再加
 每次都消掉当前的an，这样算n次就可以得到答案。
 
 

    
     
      
       
        计
       
       
        算
       
       
        复
       
       
        杂
       
       
        度
       
       
        由
       
       
        之
       
       
        前
       
       
        的
       
       
        
         
          n
         
         
          ∗
         
         
          (
         
         
          n
         
         
          +
         
         
          1
         
         
          )
         
        
        
         2
        
       
       
        到
       
       
        如
       
       
        今
       
       
        的
       
       
        2
       
       
        n
       
       
        次
       
       
        （
       
       
        n
       
       
        次
       
       
        乘
       
       
        ，
       
       
        n
       
       
        次
       
       
        加
       
       
        ）
       
      
      
       计算复杂度由之前的frac{n*(n+1)}{2}到如今的2n次（n次乘，n次加）
      
     
    计算复杂度由之前的2n∗(n+1)​到如今的2n次（n次乘，n次加）
 
上代码
 
#include 
#include 
#include 
#include 
using namespace std;
int main()
 {
    int n;
    cout << "请输入多项式的次数 ：";
    cin >> n;
    double *a = new double[n+1];//n次多项式申请n+1大小的数组
    cout << "请输入多项式的系数（最高次项开始）:" << endl;
    for(int i = n; i >= 0; i --)
        cin >> a[i];//读入各项系数
    double x0,ans=a[n];
    cout << "请输入 X0 " << endl;
    cin >> x0;
    for(int i = n-1;i >= 0;i --)
        ans = ans*x0 + a[i];//最高次项开始，往外展开
    cout << "多项式在X0出的函数值为：" << ans << endl;
    delete []a;//释放动态内存
    return 0;
}
 
 
 
总结，这其实是一个递归过程，还有点像动态规划。
 思路就是：先算最里层，然后依次往外面推导就好。
 
 
3.盛金公式 
盛金公式
 
不知道怎么推导的，上面链接公式
 是求1元三次方程的万能公式