《九章算术》开方算法系统及其与现代计算机程序的比较.docx
《《九章算术》开方算法系统及其与现代计算机程序的比较.docx》由会员分享,可在线阅读,更多相关《《九章算术》开方算法系统及其与现代计算机程序的比较.docx(12页珍藏版)》请在冰点文库上搜索。
《九章算术》开方算法系统及其与现代计算机程序的比较
《九章算术》开方算法系统
及其与现代计算机程序的比较
傅海伦
中国古代把开方法与二次、三次或高次数字方程解法统称为开方术。
《九章算术》少广章
提出了完整的开平方、开立方程序。
一、《九章算术》的开平方程序
开平方相当于求x2=N的根。
开方术曰:
「置积为实。
借一算,步之,超一等。
议所得,以一乘所借一
算为法,而以除。
除已,倍法为定法。
其复除,折法而下。
复置借算,步之如
初,以复议一乘之,所得副以加定法,以除。
以所得副从定法。
复除,折下如
前。
…」[1]
《九章算术》给出的术文言简意赅,在开方筹式中每一个数字的记数和入
算,都严格遵循位置值制。
由于其中明确指出:
「复除,折而下」、「复除,
折下如前」,可见,这是一个具有一般性的机械化算法程序。
即是说,不论平
方根有多少位数,反复实施这一程序都可求出来。
所以,在此有必要对一般情
形下的这种机械化程序加以剖析。
以总的来说,开平方的程序是:
首先作四行的筹式布算,即从上到下的四
行依次布以方根(「议所得」)、被开方数(实)、法和借算,然后机械反复
实施「超」、「议」、「除」、「折」的四大步骤,直至「适尽」、结束。
「超」:
将置于个位上的借算自右向左隔一位移一步,移到与实的最高位
(N为奇数位)或次高位(N为偶数位时)对齐为止。
若移n位,这相当于将
方程进行倍根变换,变换后的方程为102nx12=N的形式,如图
(2)
「议」:
议得根的第一位得数为a1
「除」:
以a1乘借算102n得102na1作为法。
置于第三行,使得以法除实时,
恰得商a1,而余数N1小于102na12:
N÷(102na1)=a1+N1/102na1[2]。
「折」:
撤去借算,将法102na1加倍为定法,并将定法向右退一位为2102n
-1a1如图(4),再在下行个位上布置借一算。
为求方根第二位得数,需要重复以上四个步骤:
「超」:
将置于个位上的借算自右向左隔一位移一步,显然只需移n-1步,
即102n-2如图(5),这又相当于求方程102n-2x22+2102n-1a1x2=N-102na12的正根。
「议」:
复议得根的第二位得数a2
「除」:
以a2乘借算102n-2,加定法,得法:
2102n-1a1+102n-2a2,同样以
法除实:
(N-102na12)÷(2102n-1a1+102n-2a2)=a2+N2/(2102n-1a1+102n-2a2),余
数N2小于(2102n-1a1+102n-2a2)a2。
如图(6),如果余数为零,则开方完毕;若
不为零,则「折下如前」,按接下来的程序步骤继续开方。
通过对上述筹算开平方法的分析,可知它是根据下面这些公式来逐步推求
的,与现代的迭代法完全一致,可以通过计算机来实现:
(a+b)2=a2+(2a+b)b
(a+b+c)2=(a+b)2+[2(a+b)+c]c
(a+b+c+d)2=(a+b+c)2+2[(a+b+c)+d]d
……
开平方术文还有对几种特殊情况的处理方法:
一是被开方数为分数的情形,
要「通分内子」,若分母是平方数,则分子、分母分别开方,然后相除,即A=
b/a,
;若分母不可开,则以分母乘分子,开分子后再以分母除,
即A=b/a,A=ab/a2,
。
二是开方不尽的情形,这相当于求无理根,
称为不可开,求出整数部分后,「以面命之」。
显然,有了以上程序和处理方法,任何一个数可以开平方,说明《九章算
术》的术文更具有抽象性、普适性。
二、《九章算术》的开立方程序
开立方相当于求x3=N的根。
《九章算术》开立方术是:
开立方术曰:
「置积为实。
借一算,步之,超二等。
议所得,以再乘所借
一算为法,而除之。
除已,三之为定法。
复除,折而下。
以三乘所得数,置中
行。
复借一算,置下行。
步之,中超一,下超二等。
复置议,以一乘中,再乘
下,皆副以加定法。
以定除。
除已,倍下,并中从定法。
复除,折下如前。
…」[3]。
对比开平方术和开立方术,不难看出,两种开方的程序基本上是统一的,
都是通过筹式布算,机械重复地实施「超」、「议」、「除」和「折」的四大
步骤,直至适尽,结束。
只是在开立方的筹式布算中,在「法」和「借算」之
间增加一行「中行」,使原来的四行布算变为五行布算,并在相应的「超」和
「折」的步骤中有细小的变动或调整。
对被开方数是分数、或分母不是立方的
情形,处理的方式也与开平方相同,这说明,开立方的程序也具有抽象性和普
适性,适应于任何一个数的开立方。
根据术文,对一般情形下的开立方及其与
开平方程序过程的比较可见下表:
商
10na1
10na1
10na1
10na1
实
开平方
N
N
N-102na12
N-102na12
N-102na12
(N-102na12)-(2102n-1a12+102n-2a2)a2
开立方
N-103na13
N-103na13
N-103na13
(N-103na13)-(3103n-1a12+3103n-2a1a2+103n-3a22)a2
法
开平方
102na1
2102na1
2102n-1a1
2102n-1a1+102n-2a2
开立方
103na12
3103na12
103n-1a12
3103n-1a12+3103n-2a1a2+103n-3a22
中行
开平方
无
开立方
3a1
3103n-2a12
3103n-2a1(副)3103n-2a1a2
借算
开平方
1
102n
102n
102n-2
102n-2
开立方
1
103n
1
103n-3
103n-3(副)103n-3a22
(1)
(2)
(3)
(4)
(5)
(6)
通过分析上面的筹算开立方方法,可知它是根据下面这些公式来逐步推求
的,也和现代迭代的方法完全一致,可以在计算机上实现。
(a+b)3=a3+(3a2+3ab+b2)b
(a+b+c)3=(a+b)3+[3(a+b)2+3(a+b)c+c2]c
(a+b+c+d)3=(a+b+c)3+[3(a+b+c)2+3(a+b+c)d+d2]d
……
中国古代数学将二次方程x2+bx+c=0(b,c>0)的正根称为开带从平方
法,《九章算术》虽未给出开带从平方和开带从立方的程序,但在开平方、开
立方术中从求根的第二位得数起,就是求形如x2+bx+c=0,x3+bx2+cx=d(b,
c,d>0)正根的程序,这实际上已蕴含了开带从平方和立方的程序。
三、刘徽对开方程序的改进
刘徽借助于出入相补原理,对《九章算术》提出的开平方、开立方程序给
予了几何解释,从而证明了开方程序的合理性,使人们对开方术有了直观性的
感性认识。
同时,在阐述其几何意义时,对开方程序也作了改进,以往论者认
为刘徽的开方程序与《九章算术》相同,刘徽只是解释了《九章算术》的程序,
郭书春先生经过研究指出二者起码有两个重大不同[4]:
首先,《九章算术》中,在议得某位得数(设第一位a,第二位b)后,算
出法(或定法)(开平方是a及2a+b;开立方是a2及3a2+3ab+b2),再「以
法除实」,使得「实如法」恰恰得到该位得数。
此「除」即除法,显然它还保
留了开方由除法脱胎出来的痕迹,刘徽注开方术,是将「除实」解释成以议得
数乘法(开平方a2及(2a+b)b;开立方是a3及(3a2+3ab+b2)b减实,此「除」,
即减,这无疑是程序上的一大进步。
其次,《九章算术》的借算在每使用一次后都要撤去,议得次一位得数时
要复置借算(开立方时还要置中行)于个位,再「步之如初」,显得繁琐,刘
徽则保留借算,将中行与借算先与法对齐,再通过退位求减根方程,显得简洁。
总之,通过刘徽的改进,程序已简便得多,已基本接近于现今方法,后来
在《孙子算经》,《张丘建算经》及贾宪《黄帝九章算经细草》中得到了继承
和发展。
四、《九章算术》「开方术」与现代计算机程序比较
以上开平方、开立方、开带以平方和立方程序,共同构成中国古代数学一
个独立的算法程序系统——开方算法程序系统,《九章算术》中开方算法程序
不仅表现了中国筹算所能达到的高超的算技,而且充份体现了中国数学思想方
法的构造性和算法机械化特色。
《九章算术》与这种开方算法具有的代数意义
密切相关。
由于在开方中都借用一根算筹分别表示未知量的平方和立方,这样
就赋予用算筹所列出的开方式以x2=N和x3=N两个代数方程,于是,开平方
和开立方的各个演算步骤也就成了解方程求正根的过程。
事实上,要保证算法
程序机械化的一步步进行,并在有限步骤内求得方根的每一位得数,从这种二
项二次方程或二项三次方程的代数意义上,都要经过以下三个步骤:
I.首先把方程进行倍根变换,估计方根的第一次近似值。
II.每求得方根的一次近似值之后,就利用二项展开式将原方程进行减根
变换,求出一个新的方程。
III.在新方程中,以定法除实即以一次项系数常数项,求得方程的下一次
近似值。
因此这些步骤可循环重复,直至根值全部求出或求到一定数位为止。
以开立方为例,相当于求方程f(x)=x3-N=0的正根,估计方根的第一次
近似值为x1,依II进行减根变换,即令x=x1+y则y=x-x1代入f(x)=0得
y3+3x1y2+3x12y=N-x13再依IIIy=(N-x13)/3x12=-f(x1)/f'(x1),因此,
x=x1-f(x1)/f'(x1)。
这就是《九章算术》开方术的演算原理,而这一原理,恰好是Newton-Raphson
解法的根据[5][6]。
现代计算机要用牛顿一类的迭代法求一元二次或三次方程f(x)=0的根,
首先大致估计出根的范围,给一个初值x0,然后可用迭代公式xi+1=xi-f(xi)/f'(xi)
依次求出第i+1次根的近似值xi+1,设是所求根的精度要求,若满足
|(xi+1-xi)/xi+1|<,则xi+1的值即为所求方程的解,否则再求
xi+2=xi+1-f(xi+1)/f'(xi+1),然后判断|(xi+2-xi+1)/xi+2|<是否成立,直至满足精度
为止。
由此看来,迭代法虽然也是程序化较强的算法,它是将每一次求得的新
值又作为下一次的初值来推求,直到前后两次求出的值很接近,即接近真正的
根,而且其初估值x0以及每次的近似值也不一定是所求根的每一位得数,这和
中国古算开平方和立方求方根的方法、程序不同。
中国古算开方程序在有限步
骤内依次求得方根的每位得数,通过倍根变换,估得方根的最高位得数,再通
过减根变换,求得新方程和下一次近似值,即为所求方根的次高位得数,如此
继续下去…,直至结束。
内蒙师大科学史研究所的沙娜曾用计算机“FORTRAN77”程序语言设计出
「开方术」的计算机程序,并对《九章》开方术与现代计算机开方中用到的牛
顿迭代法进行比较[7],指出虽然古今开方原理一样,然而在具体程序进行中,
因计算工具有不同,其算法亦不尽相同,因而「开方」计算机程序也不完全同
一般的计算机牛顿开方算法。
计算机:
一般牛顿法开方有两个缺点:
1)在理论上初始值x1>0即可,然而计算时
此值若不在根附近,则往往不收敛。
2)在计算机中用到一阶微分f'(x),但它可
能无法得到或不易列出。
这两点在一般的开方中还并不明显,但在以后的高次
方程的数值解中则显得突出。
筹算:
1.对初始值的选取,由于一开始倍根,使得初始值很容易估计在根附近,并由
于采用位置值制,使这一步极易做到。
由于这个方法被一直保留到高次方程
的数值解中,因而在高次方程数值解中亦不存在问题。
2.一阶微分即减根方程中的「方」,由于是用二次展开式系数得到,所以很好
计算,在以后的高次方程数值解中,因用「增乘」方法得到,亦是很易计算
与表达的。
计算机:
在求根的下一位有效值时,其值不取整,亦无倍根过程,因而迭代次数是
筹算的1-2倍,当然对计算机这并不算甚么。
筹算:
因用手移动筹来计算,计算次数不仅劳作繁忙且易出错,对此筹算采取了
取整的方法,使运算一次即可得到一位有效值,减少了计算量,使用筹开方成
为可能,这些方法均保留至以后的高次方程数值解中。
(注一)
中算史学家们对开方算法的代数意义及其构造性和机械化思想方法进行了
深入的探究,发现开方算法用来求方程的数值解不仅较目前的牛顿一类的迭代
法直截了当,而且可排除各种病态的优越性是颇为显着的[8]。
以上讨论为此观
点提供了又一佐证。
《九章算术》中的开方程序一方面奠定了中国开方术历史的良好基础,开
方术后来不断改进和发展,成为中国古代数学的一个重要分支,同时也是中国
古算中最发达的领域——解一般高次数字方程的程序,并取得了具有世界意义
的重大成就:
但另一方面,中国古代虽然能解高次方程,但没有考虑过用一个
公式来表示一方程的根,唐代僧一行和元代朱世杰虽然有类似的公式表示法,
但中国古代重视数值计算,用公式求正根不如直接开方便捷,故公式表示一直
没有受到重视。
参考文献与注释
[1][3]《九章算术》,郭书春汇校,辽宁教育出版社,1990年。
第258、261页。
[2][4]郭书春:
《古代世界数学泰斗刘徽》,山东科技出版社,1992年。
第29-30页。
[5]李兆华:
「《九章算术》开立方术的代数意义」载《〈九章算术〉与刘徽》(吴文俊主编),
北京师范大学出版社,1993年,第261页
[6].Smith:
HistoryofMathematics,1950,Vol.II.-473
[7]沙娜:
「筹算开方术的计算机程序与算法研究」,载《数学史研究文集》第四辑。
[8]吴文俊:
「从《数书九章》看中国传统数学的构造性和机械化特色」,载吴文俊主编,
《秦九韶与〈数书九章〉》,北师大出版社,1987年,第80页。
(注一)在国外,高次方程数值解的霍纳算法即没有倍根过程,这可能因其用笔算而致。