秦九韶算法 是中国 南宋 时期的数学家 秦九韶 表述求解一元高次多项式的值的算法 ——正负开方术。它也可以配合牛顿法 用来求解一元高次多项式的根。
− x⁴ + 15245x² − 6262506.25的秦九韶算法
偉烈亞力 《中国科学札记》论秦九韶玲珑开方19世纪初，英国 数学家威廉·乔治·霍纳 霍纳算法 （Horner's method 、Horner scheme ）[ 1] 偉烈亞力 Alexander Wylie. (1815–1887) 最早对霍纳的发明权提出质疑。他在1852年著的《中国科学札记》（Jottings on the Science of the Chinese）一篇论文中，详细介绍秦九韶的正负开方术之后写道“读者不难认出这就是霍纳在1819年因为发表《解所有次方程》论文，被数学家奧古斯都·德·摩根 评为‘必使其发明人因发现此算法而置身于重要发明家之列’的方法；我以为应该对霍纳的发明权提出辩驳。欧洲的朋友们可能会觉得意外，一位来自天朝帝国的竞争者，有更大的机会确立他的优先权”[ 2] [ 3] 三上义夫 在《中日数学史》一书中在详述秦九韶的正负开方术后写道：“谁能否认，霍纳的辉煌方法，至少在早于欧洲六百年之前，已经在中国运用了。”[ 4] 九章算术 》的开方法。其后王玲 和李约瑟 有专文论述秦九韶算法起源于《九章算术》。前苏联数学史家尤什克维奇说“这是中国传统数学最伟大成就之一”，他还说印度人不知有此方法，而阿拉伯数学家可能从中国前人传入此方法[ 5]
下面以自今到古的顺序，列出早在霍纳之前对该算法的发现：
霍纳在1819年发表的《解所有次方程》论文中的算例，其算法程序和数字处理都远不及五百多年前的秦九韶有条理；秦九韶算法不仅在时间上早于霍纳，也比较成熟。[ 10]
元代 数学家李冶 和朱世杰继承了秦九韶算法。
−
x
4
+
763200
x
2
−
40642560000
=
0
{\displaystyle -x^{4}+763200x^{2}-40642560000=0}
南宋 数学家秦九韶 将贾宪 的增乘开方术 推广，以求解任意高次方程的实数根的数值解。秦九韶的《数书九章 》详细叙述用秦九韶算法求解二十六个二次到十次方程的的实数根的数值解，其中包含二十个二次方程，一个三次方程，四个四次方程和一个十次方程。[ 11]
《数书九章》“《遥度圆城》”题列出一个十次方程，求解圆城的直径：
x
10
+
15
x
8
+
72
x
6
−
864
x
4
−
11664
x
2
−
34992
=
0
{\displaystyle x^{10}+15x^{8}+72x^{6}-864x^{4}-11664x^{2}-34992=0}
精确解 x=3[ 12] 《数书九章》“《兴田求积》”题列出一个四次方程，
−
x
4
+
763200
x
2
−
40642560000
=
0
{\displaystyle -x^{4}+763200x^{2}-40642560000=0}
[ 13]
將方程式寫成一般式
−
x
4
+
0
x
3
+
763200
x
2
+
0
x
−
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
4
+
15245
x
2
−
6262506.25
=
0
{\displaystyle -x^{4}+15245x^{2}-6262506.25=0}
[ 14] [ 15] 下图为秦九韶解下列四次方程 的程序。
−
x
4
+
15245
x
2
−
6262506.25
=
0
{\displaystyle -x^{4}+15245x^{2}-6262506.25=0}
更多信息 列出方程
原算法
现代数学语言
置6262506.25为实
置15245为上廉
置1为益隅
列出方程
−
x
4
+
15
245
x
2
−
6
262
506.25
=
0
{\displaystyle -x^{4}+15\,245x^{2}-6\,262\,506.25=0}
上廉超二位，益隅超三[ 16]
置商20步
令
x
=
10
x
′
{\displaystyle x=10x'}
−
10
000
x
′
4
+
1
524
500
x
′
2
−
6
262
506.25
=
0
{\displaystyle -10\,000x'^{4}+1\,524\,500x'^{2}-6\,262\,506.25=0}
以商乘益隅入下廉位
以下廉乘商生负廉
以负廉与正廉相消得正上廉
以商乘上廉为方
以方乘商除实
令
x
′
=
y
+
2
{\displaystyle x'=y+2}
−
10
000
⋅
2
4
+
1
524
500
⋅
2
2
−
6
262
506.25
=
−
324506.25
{\displaystyle -10\,000\cdot 2^{4}+1\,524\,500\cdot 2^{2}-6\,262\,506.25=-324506.25}
又以商乘益隅入下廉
以下廉乘商生负廉
负廉与正廉相消
商与上廉生方
商隅相乘入下廉
商与下廉生负廉
负廉与正廉相消
商又与隅生下廉
依次算出新方程的各系数，得
−
10
000
y
4
−
80
000
y
3
+
1
284
500
y
2
+
5
778
000
y
−
324
506.25
=
0
{\displaystyle -10\,000y^{4}-80\,000y^{3}+1\,284\,500y^{2}+5\,778\,000y-324\,506.25=0}
方一退，上廉再退，下廉三退，隅四退
无商
令
y
′
=
10
y
{\displaystyle y'=10y}
−
y
′
4
−
80
y
′
3
+
12
845
y
′
2
+
577
800
y
′
−
324
506.25
=
0
{\displaystyle -y'^{4}-80y'^{3}+12\,845y'^{2}+577\,800y'-324\,506.25=0}
以上廉并入方，并益隅入下廉
益隅并负廉与正方廉相消，命为母
估计得数的非整数部分；当
y
′
=
1
{\displaystyle y'=1}
y
′
=
0
{\displaystyle y'=0}
y
≈
324
506.25
590
564
{\displaystyle y\approx {\frac {324\,506.25}{590\,564}}}
约分
折算回
x
{\displaystyle x}
x
≈
20
+
324
506.25
590
564
=
20
1298025
2362256
{\displaystyle x\approx 20+{\frac {324\,506.25}{590\,564}}=20{\frac {1298025}{2362256}}}
关闭
其中：
1298025
2362256
{\displaystyle {\frac {1298025}{2362256}}}
三上义夫特别指出：
秦九韶在处理
−
x
4
+
15245
x
2
−
6262506.25
=
0
{\displaystyle -x^{4}+15245x^{2}-6262506.25=0}
x
2
{\displaystyle x^{2}}
秦九韶算法同样可以求出小数点后的数值，后来的中国数学家和日本数学正是这么做的。[ 17]
设有
n
+
1
{\displaystyle n+1}
n
{\displaystyle 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
{\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}}
n
{\displaystyle n}
x
{\displaystyle 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
{\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}}
n
−
1
{\displaystyle n-1}
x
{\displaystyle 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
{\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}}
如此反复提取公因子
x
{\displaystyle x}
，最后将函数化为
f
(
x
)
=
(
(
(
a
n
x
+
a
n
−
1
)
x
+
a
n
−
2
)
x
+
.
.
.
.
.
.
+
a
1
)
x
+
a
0
{\displaystyle 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
{\displaystyle f_{1}=a_{n}x+a_{n-1}}
f
2
=
f
1
x
+
a
n
−
2
{\displaystyle f_{2}=f_{1}x+a_{n-2}}
f
3
=
f
2
x
+
a
n
−
3
{\displaystyle f_{3}=f_{2}x+a_{n-3}}
......
f
n
=
f
n
−
1
x
+
a
0
{\displaystyle f_{n}=f_{n-1}x+a_{0}}
f
n
{\displaystyle f_{n}}
对于一个n次的多项式函数 ，用常规方法（用重复乘法计算幂 ，再把各项相加）计算出结果最多需要n次加法和
(
n
2
+
n
)
2
{\displaystyle {\frac {(n^{2}+n)}{2}}}
迭代 的方法计算幂则需要n次加法和2n+1次乘法。如果计算中的数值数据是以字节 方式储存的，那么常规方法约需要x占用的字节的2n倍空间。
而使用秦九韶算法时，至多只需作n次加法和n次乘法，最多需要x占用的字节的n倍空间。
该算法看似简单，其最大的意义在于将求n次多项式 的值转化为求n个一次多项式的值。在人工计算时，利用秦九韶算法和其中的系数表可以大幅简化运算；对于计算机程序 算法 而言，加法 比乘法 的计算效率 要高很多，因此该算法仍有极大的意义，用于减少中央处理器 运算时间。
Alexander Wylie Jottings on the Sciences of The Chinese p188 1852
Yoshio Mikami, The Development of Mathematics in China and Japan, Chelsia, New York, 1913 edition, p77
Urich Librecht Chinese Mathematics in Thirteen Century平08 Dover
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 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. Urich Librecht Chinese Mathematics in the Thirteen Century p189 Dover
吴文俊主编 中国数学史大系第五卷 302-309页
Yoshio Mikami, Mathematics in China and Japan p77, 1912
...
