秦九韶算法

秦九韶算法是中國南宋時期的數學家秦九韶表述求解一元高次多項式的值的算法——正負開方術。它也可以配合牛頓法用來求解一元高次多項式的根。

− 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. 

參見

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