查看“︁秦九韶算法”︁的源代码

[[File:Qin Jiushao high order equation.GIF|thumb|right|300px|− x⁴ + 15245x² − 6262506.25的秦九韶算法]]

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

==历史==
[[File:Wylie on Ling lung Kae fang.jpg|thumb|300px|[[偉烈亞力]]《中国科学札记》论秦九韶玲珑开方]]

19世纪初，[[英国]]数学家{{Link-en|威廉·乔治·霍纳|William George Horner}}重新发现并证明，後世称作'''霍纳算法'''（{{lang|en|Horner's method}}、{{lang|en|Horner scheme}}）<ref>{{Cite web |url=http://www.masterliness.com/a/Horner.scheme.htm |title=Horner Scheme History Basic Idea Horner Algorithm-MASTERLINES |accessdate=2008-10-12 |archive-date=2008-12-03 |archive-url=https://web.archive.org/web/20081203204805/http://www.masterliness.com/a/Horner.scheme.htm |dead-url=yes }}</ref>。但是，19世纪英国传教士[[偉烈亞力]]  Alexander Wylie. (1815–1887) 最早对霍纳的发明权提出质疑。他在1852年著的《中国科学札记》（Jottings on the Science of the Chinese）一篇论文中，详细介绍秦九韶的正负开方术之后写道“读者不难认出这就是霍纳在1819年因为发表《解所有次方程》论文，被数学家[[奧古斯都·德·摩根]]评为‘必使其发明人因发现此算法而置身于重要发明家之列’的方法；我以为应该对霍纳的发明权提出辩驳。欧洲的朋友们可能会觉得意外，一位来自天朝帝国的竞争者，有更大的机会确立他的优先权”<ref>Alexander  Wylie Jottings on the Sciences of The Chinese  p188   1852</ref>。<ref>[[吴文俊]]主编《[[中国数学史大系 (吴文俊主编)|中国数学史大系]]》第五卷533-537</ref>此后，日本数学史家[[三上义夫]]在《中日数学史》一书中在详述秦九韶的正负开方术后写道：“谁能否认，霍纳的辉煌方法，至少在早于欧洲六百年之前，已经在中国运用了。”<ref>Yoshio Mikami, The Development of Mathematics in China and Japan, Chelsia, New York, 1913 edition, p77</ref>。三上义夫还最先指出，秦九韶算法起源于汉代《[[九章算术]]》的开方法。其后[[王玲]]和[[李约瑟]]有专文论述秦九韶算法起源于《九章算术》。前苏联数学史家尤什克维奇说“这是中国传统数学最伟大成就之一”，他还说印度人不知有此方法，而阿拉伯数学家可能从中国前人传入此方法<ref>Urich  Librecht  Chinese  Mathematics in Thirteen  Century平08  Dover</ref>。

下面以自今到古的顺序，列出早在霍纳之前对该算法的发现：
* 1809年，[[保羅·魯菲尼]]<ref name="Cajori">[[Florian Cajori]], [http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.bams/1183421253 Horner's method of approximation anticipated by Ruffini] {{Wayback|url=http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.bams%2F1183421253 |date=20170904152220 }}, 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).</ref><ref name="St Andrews">{{MacTutor Biography|id=Horner}}</ref>
* 1669年，[[艾萨克·牛顿]]（但缺乏详细引文）
* 14世纪，中国数学家[[朱世杰|朱世-{杰}-]]<ref name="St Andrews" />
* 13世纪，中国数学家秦九韶在《数书九章》中
* 12世纪，波斯的伊斯兰数学家{{Link-en|萨拉夫·丁·图西|Sharaf al-Dīn al-Tūsī}}<ref>{{cite journal | last1 = Berggren | first1 = J. L. | year = 1990 | title = Innovation and Tradition in Sharaf al-Din al-Tusi's Muadalat | url = | journal = Journal of the American Oriental Society | volume = 110 | issue = 2| pages = 304–309 | doi=10.2307/604533}}</ref>
* 11世纪（[[宋朝]]），中国数学家[[贾宪]]
* 汉朝（公元前202到公元220年），[[刘徽]]所注的《九章算术》中<ref>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.</ref>{{dubious}}

霍纳在1819年发表的《解所有次方程》论文中的算例，其算法程序和数字处理都远不及五百多年前的秦九韶有条理；秦九韶算法不仅在时间上早于霍纳，也比较成熟。<ref>[[白尚恕]]  《中国数学史研究白尚恕文集》  47页</ref>

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

==用秦九韶算法解方程==
[[File:Qingjiushaoquad1.GIF|thumb|400px|<math>-x^4+763200x^2-40642560000=0</math>秦九韶算法<br>精确解x=840]]

[[南宋]]数学家[[秦九韶]]将[[贾宪]]的[[增乘开立方术|增乘开方术]]推广，以求解任意高次方程的实数根的数值解。秦九韶的《[[数书九章]]》详细叙述用秦九韶算法求解二十六个二次到十次方程的的实数根的数值解，其中包含二十个二次方程，一个三次方程，四个四次方程和一个十次方程。<ref>Urich  Librecht  Chinese Mathematics in the Thirteen Century p189  Dover</ref>；其中有些得到精确解；多数得近似解。

《数书九章》“《遥度圆城》”题列出一个十次方程，求解圆城的直径：
:::<math>x^{10}+15x^8+72x^6-864x^4-11664x^2-34992=0  </math>，得'''精确解'''x=3<ref>吴文俊主编  中国数学史大系第五卷  302-309页</ref>。 

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

<math>-x^4+763200x^2-40642560000=0</math><ref>吴文俊主编中国数学史大系第五卷  293-298页</ref>

將方程式寫成一般式<math>-x^4+0x^3+763200x^2+0x-40642560000=0</math>

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

《数书九章》“《环田三积》”题列出另一个四次方程，
<center><math> -x^4+15245x^2-6262506.25=0</math><ref>吴文俊主编中国数学史大系第五卷  299-302页</ref><ref>Jean Claude Matzloff, A History of Chinese Mathematics, p233-245  ISBN 3-54033782-2</ref></center>
下图为秦九韶解下列[[四次方程]]的程序。
[[File:Qin Jiushao high order equation.GIF|center|thumb|400px|<math> -x^4+15245x^2-6262506.25=0</math>秦九韶算法<br>近似解x=20.5]]


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

{| class="wikitable"
! 原算法 !! 现代数学语言
|-
|
#置6262506.25为实
#置15245为上廉
#置1为益隅
| 列出方程<math> -x^4+15\,245x^2-6\,262\,506.25=0</math>
|-
|
<ol>
<li value="4">上廉超二位，益隅超三<ref>原文似有误；对应的算筹图上移动了四位。</ref>位</li>
<li>置商20步</li>
</ol>
| 令<math>x=10x'</math>，得<math>-10\,000x'^4+1\,524\,500x'^2-6\,262\,506.25=0</math>；<br />估计解的整数部分为2。
|-
|
<ol>
<li value="6">以商乘益隅入下廉位</li>
<li>以下廉乘商生负廉</li>
<li>以负廉与正廉相消得正上廉</li>
<li>以商乘上廉为方</li>
<li>以方乘商除实</li>
</ol>
| 令<math>x'=y+2</math>，算得新方程的常数项为<math>-10\,000\cdot 2^4+1\,524\,500\cdot 2^2-6\,262\,506.25=-324506.25</math>
|-
|
<ol>
<li value="11">又以商乘益隅入下廉</li>
<li>以下廉乘商生负廉</li>
<li>负廉与正廉相消</li>
<li>商与上廉生方</li>
<li>商隅相乘入下廉</li>
<li>商与下廉生负廉</li>
<li>负廉与正廉相消</li>
<li>商又与隅生下廉</li>
</ol>
| 依次算出新方程的各系数，得<math>-10\,000y^4-80\,000y^3+1\,284\,500y^2+5\,778\,000y-324\,506.25=0</math>。
|-
|
<ol>
<li value="19">方一退，上廉再退，下廉三退，隅四退</li>
<li>无商</li>
</ol>
| 令<math>y'=10y</math>，得<math>-y'^4-80y'^3+12\,845y'^2+577\,800y'-324\,506.25=0</math>；<br />估计解的整数部分为0。
|-
|
<ol>
<li value="21">以上廉并入方，并益隅入下廉</li>
<li>益隅并负廉与正方廉相消，命为母</li>
</ol>
| 估计得数的非整数部分；当<math>y'=1</math>和<math>y'=0</math>时等式左边相差590&nbsp;564，得<math>y\approx \frac{324\,506.25}{590\,564}</math>。
|-
|
<ol>
<li value="23">约分</li>
</ol>
| 折算回<math>x</math>的值，得<math>x\approx 20 + \frac{324\,506.25}{590\,564} = 20\frac{1298025}{2362256}</math>。
|}

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

三上义夫特别指出：
#秦九韶在处理<math> -x^4+15245x^2-6262506.25=0</math>这一类四次方程式时，绝非作为<math>x^2</math>的二次方程式来求解（所谓双二次方程），而是按四次方程来求解的。
#秦九韶算法同样可以求出小数点后的数值，后来的中国数学家和日本数学正是这么做的。<ref>Yoshio Mikami, Mathematics in China and Japan  p77, 1912  </ref>

== 原理 ==
设有<math>n+1</math>项的<math>n</math>次函数
</p>
<math>f(x)=a_nx^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+......+a_2x^2+a_1x+a_0</math>
</p>
<br />
将前<math>n</math>项提取公因子<math>x</math>，得
</p>
<math>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</math>
</p>
<br />
再将括号内的前<math>n-1</math>项提取公因子<math>x</math>，得
</p>
<math>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</math>
</p>
<br />
'''如此反复提取公因子<math>x</math>'''，最后将函数化为
</p>
<math>f(x)=(((a_nx+a_{n-1})x+a_{n-2})x+......+a_1)x+a_0</math>
</p>
<br />
令
</p>
<math>f_1=a_nx+a_{n-1}</math>
</p>
<math>f_2=f_1x+a_{n-2}</math>
</p>
<math>f_3=f_2x+a_{n-3}</math>
</p>
......
</p>
<math>f_n=f_{n-1}x+a_0</math>
</p>
<br />
则<math>f_n</math>即为所求

== 应用示例 ==
求当<math>x=3
</math>时<math>f(x)=2x^3-6x^2+2x-1\,</math>的值。
<br />
反复提取公因子<math>x</math>后，原函数可以写成<math>f_1(x)=x(x(2x-6)+2)-1</math>。建立下列'''[[系数表]]'''可以用来加快演算速度：
  <math>     x_0</math> |   <math>x^3</math>   <math>x^2</math>    <math>x^1</math>   <math>x^0</math> 
   3 |   2    -6     2    -1
     |        6      0    6  
     |----------------------
         2    0      2    5

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

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

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

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

== 参考文献 ==
=== 引用 ===
{{Reflist|30em}}

=== 来源 ===
{{refbegin}}
; 书籍
* {{cite book |title=《数值分析》 |edition=第四版 |editors = 李庆扬、王能超、易大义 |publisher = 清华大学出版社、Springer出版社 |ISBN = 7-302-04561-5 }}
{{refend}}

== 参见 ==
{{Portal box|数学|中国数学史}}
* [[秦九韶]]
* [[数学机械化自动推理平台#多项式方程求解|多项式方程求解]]

{{-}}
{{多項式}}
{{中国数学史}}

[[Category:数值分析]]
[[Category:算法]]
[[Category:宋朝发明]]