秦九韶算法

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

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

历史

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

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

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

• 1809年，保羅·魯菲尼
• 1669年，艾萨克·牛顿（但缺乏详细引文）
• 14世纪，中国数学家朱世杰
• 13世纪，中国数学家秦九韶在《数书九章》中
• 12世纪，波斯的伊斯兰数学家萨拉夫·丁·图西
• 11世纪（宋朝），中国数学家贾宪
• 汉朝（公元前202到公元220年），刘徽所注的《九章算术》中

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

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

用秦九韶算法解方程

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

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

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

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

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

$-x^{4}+763200x^{2}-40642560000=0$

將方程式寫成一般式$-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）。

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

$-x^{4}+15245x^{2}-6262506.25=0$

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

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

以下是原算法与现代数学语言的对照：

原算法	现代数学语言
置6262506.25为实 置15245为上廉 置1为益隅	列出方程$-x^{4}+15\,245x^{2}-6\,262\,506.25=0$
上廉超二位，益隅超三位 置商20步	令$x=10x'$，得$-10\,000x'^{4}+1\,524\,500x'^{2}-6\,262\,506.25=0$； 估计解的整数部分为2。
以商乘益隅入下廉位 以下廉乘商生负廉 以负廉与正廉相消得正上廉 以商乘上廉为方 以方乘商除实	令$x'=y+2$，算得新方程的常数项为$-10\,000\cdot 2^{4}+1\,524\,500\cdot 2^{2}-6\,262\,506.25=-324506.25$
又以商乘益隅入下廉 以下廉乘商生负廉 负廉与正廉相消 商与上廉生方 商隅相乘入下廉 商与下廉生负廉 负廉与正廉相消 商又与隅生下廉	依次算出新方程的各系数，得$-10\,000y^{4}-80\,000y^{3}+1\,284\,500y^{2}+5\,778\,000y-324\,506.25=0$。
方一退，上廉再退，下廉三退，隅四退 无商	令$y'=10y$，得$-y'^{4}-80y'^{3}+12\,845y'^{2}+577\,800y'-324\,506.25=0$； 估计解的整数部分为0。
以上廉并入方，并益隅入下廉 益隅并负廉与正方廉相消，命为母	估计得数的非整数部分；当$y'=1$和$y'=0$时等式左边相差590 564，得$y\approx {\frac {324\,506.25}{590\,564}}$。
约分	折算回$x$的值，得$x\approx 20+{\frac {324\,506.25}{590\,564}}=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. 秦九韶算法同样可以求出小数点后的数值，后来的中国数学家和日本数学正是这么做的。

原理

设有$n+1$项的$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}$

将前$n$项提取公因子$x$，得

$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}$

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

$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}$

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

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

令

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

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

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

......

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

则$f_{n}$即为所求

应用示例

求当$x=3$时$f(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个一次多项式的值。在人工计算时，利用秦九韶算法和其中的系数表可以大幅简化运算；对于计算机程序算法而言，加法比乘法的计算效率要高很多，因此该算法仍有极大的意义，用于减少中央处理器运算时间。

参考文献

来源

书籍

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

参见

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