秦九韶算法

− x⁴ + 15245x² − 6262506.25的秦九韶算法

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

历史

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

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

下面以自今到古的顺序，列出早在霍纳之前对该算法的发现：

• 1809年，保羅·魯菲尼^[6][7]
• 1669年，艾萨克·牛顿（但缺乏详细引文）
• 14世纪，中国数学家朱世杰^[7]
• 13世纪，中国数学家秦九韶在《数书九章》中
• 12世纪，波斯的伊斯兰数学家萨拉夫·丁·图西（英语：Sharaf al-Dīn al-Tūsī）^[8]
• 11世纪（宋朝），中国数学家贾宪
• 汉朝（公元前202到公元220年），刘徽所注的《九章算术》中^[9][可疑]

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

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

秦九韶算法

${\displaystyle -x^{4}+763200x^{2}-40642560000=0}$秦九韶算法
精确解x=840

${\displaystyle -x^{4}+15245x^{2}-6262506.25=0}$秦九韶算法
近似解x=20.5

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

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

${\displaystyle x^{10}+15x^{8}+72x^{6}-864x^{4}-11664x^{2}-34992=0}$，得精确解x=3^[12]。

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

${\displaystyle -x^{4}+763200x^{2}-40642560000=0}$^[13]

將方程式寫成一般式${\displaystyle -x^{4}+0x^{3}+763200x^{2}+0x-40642560000=0}$

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

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

${\displaystyle -x^{4}+15245x^{2}-6262506.25=0}$^[14]右图为秦九韶解下列四次方程的程序

${\displaystyle -x^{4}+15245x^{2}-6262506.25=0}$^[15]

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

${\displaystyle -10000y^{4}-80000y^{3}+1284500y^{2}+577800y-324506.25=0}$

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

${\displaystyle -z^{4}-80z^{3}+12845z^{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~${\displaystyle 20{\frac {1298025}{2362256}}}$ 其中：${\displaystyle {\frac {1298025}{2362256}}}$不等于0，其第一位有效数字=0.5；即商的下一位数字为5，商~20.5，按秦九韶程序的一般规则，运算须继续进行下去直到“实”=0为止；但秦九韶在商=20.5而止，因20.5的精确度已满足在相关问题的需要。

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

原理

设有${\displaystyle n+1}$项的${\displaystyle n}$次函数

${\displaystyle 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}}$

将前${\displaystyle n}$项提取公因子${\displaystyle x}$，得

${\displaystyle f(x)=(a_{n}x^{n-1}+a_{n-1}x^{n-2}+a_{n-2}x^{n-3}+......+a_{2}x+a_{1})x+a_{0}}$

再将括号内的前${\displaystyle n-1}$项提取公因子${\displaystyle x}$，得

${\displaystyle f(x)=((a_{n}x^{n-2}+a_{n-1}x^{n-3}+a_{n-2}x^{n-4}+......+a_{2})x+a_{1})x+a_{0}}$

如此反复提取公因子${\displaystyle x}$，最后将函数化为

${\displaystyle f(x)=(((a_{n}x+a_{n-1})x+a_{n-2})x+......+a_{1})x+a_{0}}$

令

${\displaystyle f_{1}=a_{n}x+a_{n-1}}$

${\displaystyle f_{2}=f_{1}x+a_{n-2}}$

${\displaystyle f_{3}=f_{2}x+a_{n-3}}$

......

${\displaystyle f_{n}=f_{n-1}x+a_{0}}$

则${\displaystyle f_{n}}$即为所求

应用示例

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

 ${\displaystyle x_{0}}$ |   ${\displaystyle x^{3}}$   ${\displaystyle x^{2}}$    ${\displaystyle x^{1}}$   ${\displaystyle x^{0}}$ 
  3 |   2    -6     2    -1
    |        6      0    6  
    |----------------------
        2    0      2    5

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

效率

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

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

意义

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

参考文献

引用

1. Horner Scheme History Basic Idea Horner Algorithm-MASTERLINES. [2008-10-12]. （原始内容存档于2008-12-03）. 
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. Florian Cajori, Horner's method of approximation anticipated by Ruffini （页面存档备份，存于互联网档案馆）, Bulletin of the American Mathematical Society, Vol. 17, No. 9, pp. 409–414, 1911 (read before the Southwestern Section of the American Mathematical Society on November 26, 1910).
7. 約翰·J·奧康納; 埃德蒙·F·羅伯遜, Horner, MacTutor数学史档案 （英语） 
8. Berggren, J. L. Innovation and Tradition in Sharaf al-Din al-Tusi's Muadalat. Journal of the American Oriental Society. 1990, 110 (2): 304–309. doi:10.2307/604533. 
9. Temple, Robert. (1986). The Genius of China: 3,000 Years of Science, Discovery, and Invention. With a forward by Joseph Needham. New York: Simon and Schuster, Inc. ISBN 0-671-62028-2. Page 142.
10. 白尚恕 《中国数学史研究白尚恕文集》 47页
11. Urich Librecht Chinese Mathematics in the Thirteen Century p189 Dover
12. 吴文俊主编 中国数学史大系第五卷 302-309页
13. 吴文俊主编中国数学史大系第五卷 293-298页
14. 吴文俊主编中国数学史大系第五卷 299-302页
15. Jean Claude Matzloff, A History of Chinese Mathematics, p233-245 ISBN 3-54033782-2
16. Yoshio Mikami ,Mathematics in China and Japan p77, 1912

来源

书籍

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

参见

• 秦九韶
• 多项式方程求解