秦九韶算法

维基百科,自由的百科全书
跳转至: 导航搜索
− x⁴ + 15245x² − 6262506.25的秦九韶算法

秦九韶算法中国南宋时期的数学家秦九韶表述求解一元高次多项式的值的算法——正负开方术。它也可以配合牛顿法用来求解一元高次多项式的根

历史[编辑]

偉烈亞力 《中国科学扎纪》 论秦九韶 玲珑开方

十九世纪初,英国数学家威廉·乔治·霍纳重新发现并证明,後世称作霍纳算法Horner scheme[1]。 但是十九世纪英国传教士偉烈亞力最早对霍纳的发明权提出质疑。他在1852年著的《中国科学扎记》(Jointings on the Sciencs of the Chinese)一篇论文中,详细介绍秦九韶的正负开方术之后写道“读者不难认出这就是霍纳在1819年因为发表《解所有次方程》论文,被数学家奧古斯都·德·摩根评为‘必使其发明人因发现此算法而置身于重要发明家之列’的方法;我以为应该对霍纳的发明权提出辩驳。欧洲的朋友们可能会觉得意外,一位来自天朝帝国的竞争者,有更大的机会确立他的优先权”[2][3]此后日本数学史家三上义夫在《中日数学史》一书中在详述秦九韶的正负开方术后写道:“谁能否认,霍纳的辉煌方法,至少在早于欧洲六百年之前,已经在中国运用了。”[4]。三上义夫还最先指出,秦九韶算法起源于汉代《九章算术》的开方法。其后王玲李约瑟有专文论述秦九韶算法起源于《九章算术》。前苏联数学史家尤什克维奇说“这是中国传统数学最伟大成就之一”,他还说印度人不知有此方法,而阿拉伯数学家可能从中国前人传入此方法。[5]

霍纳在1819年发表的《解所有次方程》论文中的算例,其算法程序和数字处理都远不及五百多年前的秦九韶有条理;秦九韶算法不仅在时间上早于霍纳,也比较成熟。[6]

元代数学家李冶朱世杰继承了秦九韶算法。

秦九韶程序[编辑]

-x^4+763200x^2-40642560000=0秦九韶算法
精确解x=840
 -x^4+15245x^2-6262506.25=0秦九韶算法
近似解x=20.5

南宋数学家秦九韶贾宪增乘开方术推广,以求解任意高次方程的实数根的数值解。秦九韶的《数书九章》详细叙述用秦九韶算法求解二十六个二次到十次方程的的实数根的数值解,其中包含二十个二次方程,一个三次方程,四个四次方程和一个十次方程。[7];其中有些得到精确解;多数得近似解。

《数书九章》“《遥度圆城》” 题列出一个十次方程,求解圆城的直径:

x^{10}+15x^8+72x^6-864x^4-11664x^2-34992=0  ,得精确解 x=3[8]

《数书九章》“《兴田求积》” 题列出一个四次方程,

-x^4+763200x^2-40642560000=0[9]

ax^4+bx^3+cx^2+dx+e=0

其中 a=-1,b=0,c=763200,d=0,e=-40642560000

第一次估根~800;作y=x-800 减根代换,估出根的第二位数字为y=40;经过第二次减根代换z=y-40后常数项抵消为0;得精确解 y=40;x=800+y=800+40=840。 右图为用阿拉伯数字表示的解此四次方程的秦九韶程序图(c'、d'、e'是运算过程中的临时数,最终分别并入c、d、e)。

《数书九章》“《环田三积》” 题列出另一个四次方程,

 -x^4+15245x^2-6262506.25=0[10]

右图为秦九韶解下列四次方程的程序

 -x^4+15245x^2-6262506.25=0[11]


其中经过 x=10x' 扩根代换和 x'=y+2 减根代换得

-10000y^4-80000y^3+1284500y^2+577800y-324506.25=0

再次作扩根变换令z=10y 得:

-z^4-80z^3+12845x^2+57780z-324506.25=0


筹算程序:

  1. 置6262506.25 为实
  2. 置15245 为上廉
  3. 置1为益隅
  4. 上廉超二位,益隅超三位。
  5. 置商20步
  6. 以商乘益隅入下廉
  7. 以下廉乘商生负廉
  8. 以负廉与正廉相消得正上廉
  9. 以商乘上廉为方
  10. 以方乘商除实
  11. 又以商乘益隅入下廉
  12. 以下廉乘商生负廉
  13. 负廉与正廉相消
  14. 商与上廉生方
  15. 商隅相乘入下廉
  16. 商与下廉生负廉
  17. 负廉与正廉相消
  18. 商又与隅生下廉
  19. 下廉三退,隅四退
  20. 无商(商第二位为0),以上廉并入方,并益隅入下廉
  21. 益隅并负廉与正方廉相消,命为母
  22. 约分

得x~ 20\frac{1298025}{2362256} 其中:\frac{1298025}{2362256} 不等于0,其第一位有效数字=0.5;即商的下一位数字为5,商~20.5,按秦九韶程序的一般规则,运算须继续进行下去直到“实”=0为止;但秦九韶在商=20.5 而止,因20.5 的精确度已满足在相关问题的需要。


三上义夫特别指出(1)秦九韶在处理 -x^4+15245x^2-6262506.25=0这一类四次方程式时,绝非作为x^2 的二次方程式来求解(所谓双二次方程),而是按四次方程来求解的。(2)秦九韶算法同样可以求出小数点后的数值,后来的中国数学家和日本数学正是这么做的。[12]

原理[编辑]

设有n+1项的n次函数

f(x)=a_nx^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+......+a_2x^2+a_1x+a_0


将前n项提取公因子x,得

f(x)=(a_nx^{n-1}+a_{n-1}x^{n-2}+a_{n-2}x^{n-3}+......+a_2x+a_1)x+a_0


再将括号内的前n-1项提取公因子x,得

f(x)=((a_nx^{n-2}+a_{n-1}x^{n-3}+a_{n-2}x^{n-4}+......+a_2)x+a_1)x+a_0


如此反复提取公因子x,最后将函数化为

f(x)=(((a_nx+a_{n-1})x+a_{n-2})x+......+a_1)x+a_0


f_1=a_nx+a_{n-1}

f_2=f_1x+a_{n-2}

f_3=f_2x+a_{n-3}

......

f_n=f_{n-1}x+a_0


f_n即为所求


应用示例[编辑]

求当x=3f(x)=2x^3-6x^2+2x-1\,的值。
反复提取公因子x后,原函数可以写成f_1(x)=x(x(2x-6)+2)-1。建立下列系数表可以用来加快演算速度:

      x_0 |   x^3   x^2    x^1   x^0 
  3 |   2    -6     2    -1
    |        6      0    6  
    |----------------------
        2    0      2    5

第四行中的数是表中本列上方两数之和。第三行的数字是x的值与左下方第四行数的乘积。第二行的数是多项式各项按照次数从大到小排列后的系数。表中右下角的数就是函数的值:5。

效率[编辑]

对于一个n次的多项式函数,用常规方法(用重复乘法计算,再把各项相加)计算出结果最多需要n次加法和\frac{(n^2 + n)}{2}次乘法。若用x迭代的方法计算幂则需要n次加法和2n+1次乘法。如果计算中的数值数据是以字节方式储存的,那么常规方法约需要x占用的字节的2n倍空间。

而使用秦九韶算法时,至多只需作n次加法和n次乘法,最多需要x占用的字节的n倍空间。

意义[编辑]

该算法看似简单,其最大的意义在于将求n次多项式的值转化为求n个一次多项式的值。在人工计算时,利用秦九韶算法和其中的系数表可以大幅简化运算;对于计算机程序算法而言,加法乘法计算效率要高很多,因此该算法仍有极大的意义,用于减少CPU运算时间。

注释[编辑]

  1. ^ Horner Scheme History Basic Idea Horner Algorithm-MASTERLINES
  2. ^ Alexander Wylie Jottings on the Sciences of The Chinese p188 1852
  3. ^ 吴文俊主编 《中国数学史大系》第五卷 533-537
  4. ^ Yoshio Mikami, The Development of Mathematics in China and Japan, Chelsia, New York, 1913 edition, p77
  5. ^ Urich Librecht Chinese Mathematics in Thirteen Century 平08 Dover
  6. ^ 白尚恕 《中国数学史研究 白尚恕文集》 47页
  7. ^ Urich Librecht Chinese Mathematics in the Thirteen Century p189 Dover
  8. ^ 吴文俊主编 中国数学史大系 第五卷 302-309页
  9. ^ 吴文俊主编 中国数学史大系 第五卷 293-298页
  10. ^ 吴文俊主编 中国数学史大系 第五卷 299-302页
  11. ^ Jean Claude Matzloff, A History of Chinese Mathematics, p233-245 ISBN 3-54033782-2
  12. ^ Yoshio Mikami ,Mathematics in China and Japan p77, 1912

参见[编辑]

参考文献[编辑]

  • 李庆扬、王能超、易大义 (编). 《数值分析》 第四版. 清华大学出版社、Springer出版社. ISBN 7-302-04561-5.