版权声明：本⽂为博主原创⽂章，未经博主允许不得转载。blog.csdn/weixin_38451800/article/details/90418337
秦九韶算法介绍及MATLAB实现
⽬录
数值计算中算法设计好坏不但影响计算结果的精度，还可⼤量节省计算时间，减少运算次数和舍⼊误差，这也是算法设计中⼀个重要原则，下⾯以多项式求值为例，介绍数值计算中第⼀个常⽤的技巧——秦九韶算法或Horner法则（霍纳法则）。
1 秦九韶算法由来
19世纪初，英国数学家威廉·乔治·霍纳重新发现并证明，后世称作霍纳算法（Horner’s method、Horner scheme）。但是，19世纪英国传教⼠伟烈亚⼒Alexander Wylie. (1815–1887) 最早对霍纳的发明权提出质疑。他在1852年著的《中国科学扎记》（Jottings on the Science of the Chinese）⼀篇论⽂中，详细介绍秦九韶的正负开⽅术之后写道“读者不难认出这就是霍纳在1819年因为发表《解所有次⽅程》论⽂，被数学家奥古斯都·德·摩根评为‘必使其发明⼈因发现此算法⽽置⾝于重要发明家之列’的⽅法；我以为应
该对霍纳的发明权提出辩驳。欧洲的朋友们可能会觉得意外，⼀位来⾃天朝帝国的竞争者，有更⼤的机会确⽴他的优先权”。此后，⽇本数学史家三上义夫在《中⽇数学史》⼀书中在详述秦九韶的正负开⽅术后写道：“谁能否认，霍纳的辉煌⽅法，⾄少在早于欧洲六百年之前，已经在中国运⽤了。”。三上义夫还最先指出，秦九韶算法起源于汉代《九章算术》的开⽅法。其后王玲和李约瑟有专⽂论述秦九韶算法起源于《九章算术》。前苏联数学史家尤什克维奇说“这是中国传统数学最伟⼤成就之⼀”，他还说印度⼈不知有此⽅法，⽽阿拉伯数学家可能从中国前⼈传⼊此⽅法。
2 原理公式及MATLAB实现
韶设给定n次多项式：
已知系数矩阵A[]和x*，求f(x*)值。
分析：⽤常规⽅法（⽤重复乘法计算幂，再把各项相加）计算出结果最多需要n次加法和(n^2+n)/2次乘法。若⽤x迭代的⽅法计算幂则需要n次加法和2n+1次乘法。如果计算中的数值数据是以字节⽅式储存的，那么常规⽅法约需要占⽤字节的2n倍空间。如果⽤秦九韶算法呢？
若采⽤：f(x)=(…( a(0)*x+a(1) )*x+…+a(n-1) )x+a(n) （1），则b=f(x)值即为所求，此算法被称为秦九
韶算法。⽤它计算n次多项式只需作n次加法和n次乘法，最多需要占⽤的字节的n倍空间。
MATLAB代码实现
function p=QJS(A,x)
%秦九韶算法,A为函数系数向量，降幂排列，x为某点
n=length(A);
p=A(1);
for k=1:1:n-1
p=p*x+A(k+1);
end
3 另外⼀个好处——求f(x)在x*处导数值
我们对于上⾯（1）式变形可得：
b(0)=a(0)
b(i)=b(i-1)*x+a(i)，其中i=1，2，3……n。
所以对f(x)求导数可得：
q(x)=b(0)x^(n-1)+…+b(n-1)，⼜是⼀个多项式。
所以，⼜可以⽤秦九韶算法求解。
4 举例
5 C语⾔代码实现
double f (int n,double a[],double x){//n代表a[]的⼤⼩，数组的传递需要指定数组⼤⼩int i;//a[]储存每个x项的系数值，在函数外初始化
double p=a[n];//初始化p；
for(i=n;i>0;i--)
p=a[i-1]+x*p;
return p;
}
6 Java代码实现
class test{
public static long poly2(int[] arr,int x,int n){ //arr存储系数, x 表⽰基数, n 表⽰幂
long poly =0;
for(int i =0; i <= n; i++)
poly = poly * x + arr[i];
return poly;
}
public static void main(String[] args){ int[]b ={4,8,0,1,2};
System.out.println(poly2(b,3,4));
}
}
发布评论