秦九韶算法

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

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

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

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

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

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

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

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

${\displaystyle -<!--\; -\; -->x^4+763200x^2-<!--\; -\; -->40642560000=0}$

将方程式写成一般式${\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）。

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

其中经过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}$

筹算程序：

得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）秦九韶算法同样可以求出小数点后的数值，后来的中国数学家和日本数学正是这么做的。

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