族谱网 头条 人物百科

秦九韶算法

2020-10-16
出处:族谱网
作者:阿族小谱
浏览:1144
转发:0
评论:0
历史伟烈亚力《中国科学扎纪》论秦九韶玲珑开方19世纪初,英国数学家威廉·乔治·霍纳重新发现并证明,后世称作霍纳算法或Hornerscheme)。但是,19世纪英国传教士伟烈亚力最早对霍纳的发明权提出质疑。他在1852年著的《中国科学扎记》(JointingsontheSciencsoftheChinese)一篇论文中,详细介绍秦九韶的正负开方术之后写道“读者不难认出这就是霍纳在1819年因为发表《解所有次方程》论文,被数学家奥古斯都·德·摩根评为‘必使其发明人因发现此算法而置身于重要发明家之列’的方法;我以为应该对霍纳的发明权提出辩驳。欧洲的朋友们可能会觉得意外,一位来自天朝帝国的竞争者,有更大的机会确立他的优先权”。此后,日本数学史家三上义夫在《中日数学史》一书中在详述秦九韶的正负开方术后写道:“谁能否认,霍纳的辉煌方法,至少在早于欧洲六百年之前,已经在中国运用了。”。三上义夫还最先指出...

历史

秦九韶算法

伟烈亚力《中国科学扎纪》论秦九韶玲珑开方

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

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

1809年,保罗·鲁菲尼

1669年,艾萨克·牛顿(但缺乏详细引文)

14世纪,中国数学家朱世杰

13世纪,中国数学家秦九韶在《数书九章》中

12世纪,波斯的数学家Sharaf al-Dīn al-Tūsī

11世纪(宋朝),中国数学家贾宪

汉朝(公元前202到公元220年),刘徽所注的《九章算术》中

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

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

秦九韶程序

秦九韶算法

− − --> x 4 + 763200 x 2 − − --> 40642560000 = 0 {\displaystyle -x^{4}+763200x^{2}-40642560000=0}

秦九韶算法 精确解x=840

秦九韶算法

− − --> x 4 + 15245 x 2 − − --> 6262506.25 = 0 {\displaystyle -x^{4}+15245x^{2}-6262506.25=0} 秦九韶算法 近似解x=20.5

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

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

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

− − --> x 4 + 763200 x 2 − − --> 40642560000 = 0 {\displaystyle -x^{4}+763200x^{2}-40642560000=0}

设 a x 4 + b x 3 + c x 2 + d x + e = 0 {\displaystyle ax^{4}+bx^{3}+cx^{2}+dx+e=0}

其中 a=-1,b=0,c=763200,d=0,e=-40642560000

第一次估根~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减根代换得

− − --> 10000 y 4 − − --> 80000 y 3 + 1284500 y 2 + 577800 y − − --> 324506.25 = 0 {\displaystyle -10000y^{4}-80000y^{3}+1284500y^{2}+577800y-324506.25=0}

再次作扩根变换令z=10y 得:

− − --> z 4 − − --> 80 z 3 + 12845 x 2 + 57780 z − − --> 324506.25 = 0 {\displaystyle -z^{4}-80z^{3}+12845x^{2}+57780z-324506.25=0}

筹算程序:

置6262506.25为实

置15245为上廉

置1为益隅

上廉超二位,益隅超三位。

置商20步

以商乘益隅入下廉

以下廉乘商生负廉

以负廉与正廉相消得正上廉

以商乘上廉为方

以方乘商除实

又以商乘益隅入下廉

以下廉乘商生负廉

负廉与正廉相消

商与上廉生方

商隅相乘入下廉

商与下廉生负廉

负廉与正廉相消

商又与隅生下廉

下廉 三退 ,隅四退

无商(商第二位为0),以上廉并入方,并益隅入下廉

益隅并负廉与正方廉相消,命为母

约分

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

三上义夫特别指出(1)秦九韶在处理 − − --> x 4 + 15245 x 2 − − --> 6262506.25 = 0 {\displaystyle -x^{4}+15245x^{2}-6262506.25=0} 这一类四次方程式时,绝非作为 x 2 {\displaystyle x^{2}} 的二次方程式来求解(所谓双二次方程),而是按四次方程来求解的。(2)秦九韶算法同样可以求出小数点后的数值,后来的中国数学家和日本数学正是这么做的。

原理

设有 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}} 即为所求

应用示例

求当 x = 3 {\displaystyle x=3} 时 f ( x ) = 2 x 3 − − --> 6 x 2 + 2 x − − --> 1 {\displaystyle f(x)=2x^{3}-6x^{2}+2x-1\,} 的值。 反复提取公因子 x {\displaystyle x} 后,原函数可以写成 f 1 ( x ) = x ( x ( 2 x − − --> 6 ) + 2 ) − − --> 1 {\displaystyle f_{1}(x)=x(x(2x-6)+2)-1} 。建立下列 系速度 可以用来加快演算速度:

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

效率

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

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

意义

该算法看似简单,其最大的意义在于将求n次多项式的值转化为求n个一次多项式的值。在人工计算时,利用秦九韶算法和其中的系数表可以大幅简化运算;对于计算机程序算法而言,加法比乘法的计算效率要高很多,因此该算法仍有极大的意义,用于减少CPU运算时间。

参考文献

来源

李庆扬、王能超、易大义 (编). 《数值分析》 第四版. 清华大学出版社、Springer出版社. ISBN 7-302-04561-5.

参见

秦九韶

多项式方程求解


免责声明:以上内容版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。感谢每一位辛勤著写的作者,感谢每一位的分享。

——— 没有了 ———
编辑:阿族小谱

相关资料

展开

更多文章

更多精彩文章
打赏
私信

推荐阅读

· 秦九韶
秦九韶,字道古。普州安岳(今四川安岳)人,祖籍鲁郡(今河南范县)。中国古代数学家。南宋嘉定元年(1208年)生;约景定二年(1261年)被贬至梅州;咸淳四年(1268)二月,在梅州辞世,时年61岁。秦九韶其父秦季栖,进士出身,官至上部郎中、秘书少监。秦九韶聪敏勤学。宋绍定四年(1231),秦九韶考中进士,先后担任县尉、通判、参议官、州守、同农、寺丞等职。先后在湖北、安徽、江苏、浙江等地做官,1261年左右被贬至梅州,不久死于任所。他在政务之余,对数学进行潜心钻研,并广泛搜集历学、数学、星象、音律、营造等资料,进行分析、研究。宋淳祜四至七年(1244至1247),他在为母亲守孝时,把长期积累的数学知识和研究所得加以编辑,写成了闻名的巨著《数学九章》,并创造了"大衍求一术"。被称为"中国剩余定理"。他所论的"正负开方术",被称为"秦九韶程序"。世界各国从小学、中学到大学的数学课程,几乎都接触到...
· 秦九韶
生平秦九韶的籍贯是鲁郡(今山东省济宁市兖州区、曲阜一带),祖上世代为官。父亲秦季槱(yǒu/ㄧㄡˇ)字宏父,是四川普州(现安岳县)人,曾知潼州府、任职秘阁。1208年,秦九韶生于普州,(今四川安岳)是家里的第二个儿子。嘉定五年(1212年),秦季槱任巴州知州。嘉定十二年(1219年),兴元军士权兴等叛乱,秦季槱守巴州失陷,秦九韶随父亲回到临安(今杭州)。嘉定十五年后,秦季槱擢升工部郎中、秘书少监兼国史院编修官、实录检讨官。由于父亲是掌管各项工程、屯田、水利、交通的工部郎中,又任国史院官职,掌管各类经籍图书,少年的秦九韶得以接触学习各类知识。他生性聪颖,对当时的种种学问,如星象、音乐、算术以及建筑学等无一不学,并专研甚深。他还曾经向当时的隐士求教,学习数学。十八岁时在乡里为义兵首领。绍定二年(1229年)十月,秦九韶擢郪县县尉。绍定五年(1232)八月乙丑进士。端平三年(1236年)一月,秦...
· 九章详注比类算法大全
内容乘除开方起例,194问方田卷第一粟米卷第二212问衰分卷第三少广卷第四商功卷第五均输卷第六盈不足卷第七方程卷第八勾股卷第九开方卷第十各卷中的”古问“部分题目,取自刘徽《海岛算经》、王孝通《缉古算经》、杨辉《详解九章算法》,朱世杰《四元玉鉴》等古算术;”比类“是应用题。版本根据中算史家李俨考证,《九章详注比类算法大全》有如下版本天一阁明刊本吴敬编《算法大全》十卷明赵琦美《脉望馆数目》载吴敬《九章算法比类大全》八本,《算法大全》四本清初《清来堂书目》载明吴敬《比类算法大全》上海东方图书馆旧藏明弘治元年(1488年)刻本八册,现藏中国国家图书馆。北京大学图书馆有李盛铎旧藏十二册。日本静嘉堂有一部。评价明代数学家程大位对此书评价不高,认为此书章类繁乱,错误很多。清代数学家梅文鼎认为吴敬的数学水平高于程大位,现代数学史家钱宝琮认为明代在西洋数学传入中国之前,数学上可以称道的成就仅有珠算一门,景泰...
· 四川省-资阳市-安岳县秦九韶
秦九韶(1208—1268),字道古,四川普州(今安岳)人,嘉定元年(1208)春诞生在普州,绍定二年(1229)十月,秦九韶擢郪县县尉,绍定四年(1231)八月,秦九韶参与魏了翁平抑泸州蛮夷,葺其城楼橹雉堞,绍定五年(1232)八月乙丑进士,绍定六年,秦九韶在魏了翁带领吴潜等督视潼川府路、成都府路时认识吴潜,魏了翁和吴潜同秦九韶去拜望病中的许奕。端平三年(1236)一月,秦九韶擢升湖北蕲州(今湖北蕲春县)通判,嘉熙元年(1237)年秋,秦九韶知和州(今安徽和县)。嘉熙二年(1238),秦九韶回临安丁父忧,秦九韶在杭州丁父忧期中,发现西溪两岸的群众过河很不方便,在西溪上设计修建一座桥,名“西溪桥”,数学家朱世杰为纪念秦九韶,将桥命名为“道古桥”。嘉熙三年(1239),秦九韶在杭州处理完父亲的后事之后,便和母亲、妻子回到湖州西门外父亲早年备置的宅第,继续丁父忧。秦九韶在湖州丁父忧期中,与知庆...
· 算法
历史算法在中国古代文献中称为“术”,最早出现在《周髀算经》、《九章算术》。特别是《九章算术》,给出四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃拉托斯特尼筛法,线性方程组求解的算法。三国时代的刘徽给出求圆周率的算法:刘徽割圆术。自唐代以来,历代更有许多专门论述“算法”的专著:唐代:《一位算法》一卷,《算法》一卷;宋代:《算法绪论》一卷、《算法秘诀》一卷;最著名的是杨辉的《杨辉算法》;元代:《丁巨算法》;明代:程大位《算法统宗》清代:《开平算法》、《算法一得》、《算法全书》。而英文名称“Algorithm”来自于9世纪波斯数学家花拉子米(比阿勒·霍瓦里松,波斯语:خوارزمی‎,拉丁转写:al-Khwarizmi),因为比阿勒·霍瓦里松在数学上提出了算法这个概念。“算法”原为“algorism”,即“al-Khwarizmi”的音转,意思是“花拉子米”的运算法则,在18世...

关于我们

关注族谱网 微信公众号,每日及时查看相关推荐,订阅互动等。

APP下载

下载族谱APP 微信公众号,每日及时查看
扫一扫添加客服微信