多项式实根的分布及求所有实根的算法
第２２卷总第４１期２００１年９月
Ｊｏｕｒｎａｌｏｆ
西北民族学院学报（自然科学版）
ＮｏｒｔｈｗｅｓｔＭｉｎｏｒｉｔｉｅｓＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅ）
ＶｏＩ．２２．Ｎｏ．３
Ｓｅｐ．２００１
多项式实根的分布及求所有实根的算法
朱凤娟
（西北第二民族学院信息与计算科学系，宁夏银川７５００２１）
［摘要】利用多项式实根的分布及计算孤立区间的算法，可计算出多项式的所有实根
［关键词］多项式；根；孤立区间；算法；Ｓｔｒｕｍ定理［中图分类号］０１２２．２
［文献标识码】Ａ［文章编号］１００９—２１０２（２００１）０３—０００５—０４
护ｗ８扩泸扩ｑ庐ｗｏ驴驴驴矿矿矿＿Ｂｑ庐＿２驴驴驴扩ｑ／８ｑ８ｗｏ矿≈尹ｗｏｗｏ矿々口口￥８ｐ日口々口、∥镕、
许多实际问题。尤其是矩阵特征值、微分方程问题的求解、数值方法稳定性的派别往往都
归结为特征方程——一元，ｔ次方程根的求解问题．而现有的大部分方法特点是给出求一个实
（复）根的方法，逐步分解多项式，重复使用相应的方法来获得每一个根，如二分法、牛顿法…，
劈因子法【２Ｊ２，商一差法【３ｊ３，Ｇｒａｆｆｅ’ｓ法【４｜。但商一差法收敛速度慢，Ｇｒａｆｆｅ’ｓ法难以实现．在无重根时，现在又有厂一种新的数值迭代方法［５｜，其收敛速度是二阶的，但计算量大．本文主要研究多项式根的分布情况，随后给出求根的数值方法，利用此方法可以求出多项式的所有实
限．
１
多项式实根的分布
定义１【６】
设．，。（ｚ）ＥＲ［Ｔ］是一个非零多项式，入∈Ｒ是ｆ（Ｔ）的根．如果包含入的区
问［ａ，ｂ］满足：ＶＥ［Ⅱ，ｂ］＼｛入｝’厂（ａ）≠０，则称区间［ａ，ｂ］为包含根入ＥＲ的孤立区间．
ａ
对于任意一个非零多项式．ｆ（ｚ）ＥＲ［Ｔ］，记Ｔ为ｆ（ｚ）的孤立区间所形成的集合，则丁为一组互不相交的区间，每个区间都是ｆ（ｚ）的孤立区间，并且ｆ（３Ｌ＂）的每一个实根都在Ｔ中的某一个区间内．下面从多项式．厂（ｚ）出发，求出，‘（ｚ）的孤立区间集合Ｔ．首先，我们找到一个包含厂（ｚ）的所有实根的区间．
定理１
设ｆ（Ｔ）＝ｃ／．ｎ５Ｃ”＋ａ，ｌ工”＿１＋…＋ⅡｌＴ十“ｏ
ｎｎ，ｒ．１
Ｅ
Ｚ［ｚ］是整系数多项式，若ｒ＿ｒ是
它的有理根，其中ｒ，５互质，则必有ｓ
证明
定理２
ｎ”
利用本原多项式的性质。易证．
设非零多项式．厂（ｚ）ＥＲ［工］，令，’（ｚ）＝Ｏ－ｎＸ“＋ｎｎ－Ｉ５ｆ”＿１＋…＋“ｌＴ＋ｕｌＪ．假
设，ｔ＞０，Ｏ．ｎ≠０，记Ｍ（＿厂）＝ｍａｘ｛１，｝＿等＋｝磊＋…＋上ｆ芝ｊ』｝；Ｎ（．『）＝１＋
［收稿日期】２００１—０６—０４
［作者简介］朱凤娟（１９７２一），女，宁夏中宁人，西二ＩＥ笫二民族学院信计系助教．
万方数据
一５一
ｍａ“捌，爿，…，等细有：①Ｖ…＞Ｍ（，）＇Ｉ．ｆ（ｒ）Ｉ＞。；②Ｖ
ｆ（，４）Ｉ＞０．
Ｊｒ
ｌ＞ｗ），
证明
ｒ
１）对于Ｉ
ｒ
Ｉ＞Ｍ（ｆ），由于Ｍ≥１，我们有ｌ
ｌｌ
Ｉ”一１＋…＋Ｉ
ｒ
Ｉ＞１．如果ｒ是，’（Ｔ）的根，并且
Ｉ＞１，贝０有，’（ｒ）＝０ｊ．厂（ｒ）＝ａ。ｒ“＋ｎ。一ｌ
ａ。一１
ｒ
ｒ’。一１＋…＋ｎ１
ｒ＋ｎｏ＝０＝》｜ｎ。ｊＪ，‘Ｉ’２＝ｌ
ａｆＪ
ｎ川，一１＋…＋ｎ１ｒ＋ｎ１）ｆ≤Ｉ
ａｌ｜Ｉ
ｒ
Ｉ＋Ｉ
Ｉ．由此可见Ｉｒ｜¨｛≤
ｒ｜＜Ｍ（厂）’与假设
｛％导×｜ｒ｜”＿ｌ＋…＋｝等×ＩｒＩ＋｝等＜Ｍ（，）刈ｒ｜”－１≥Ｉ
产生矛盾，故ｒ不是．厂（ｚ）的根，即Ｉｆ（ｒ）Ｉ＞０．
２）对于Ｉ
ｒ
Ｉ＞Ｎ（ｆ），由于Ｎ（ｆ）≥１，我们有Ｉ
ｒ
Ｉ＞１．如果ｒ是．厂（３１２）的根，并且Ｉ
ａ，．一ｌ
ｒ
Ｉ＞
ｒ”一１
１，贝０有，（，一）＝０＝》．厂（ｒ．）＝ａｎｒ’１＋ｎ。一Ｌｒ”一１＋…＋ｎｌｒ＋ａｏ＝０＝＞Ｉｎ。｜ｌ，’Ｉ”＝Ｉ
＋…＋ａｌ
ｒ．＋Ⅱｏ
Ｉ≤Ｉ
ａ，ｔ
ＩＩ
ｒ
ｎ—ｌ＋…＋Ｉ
ｎｌ
ＩＩ
ｒ
Ｉ＋ｆ
ｎＩ）Ｉ．由此可见，Ｉ
ｒ
ｌ”≤一｝Ｐ｝×ｌ
Ｑ虹卑手掣≥Ｉ
的根，即１．厂（ｒ）Ｉ＞０．
定理３【７］，（ｚ）的根，则ｌ
定理４
ｒ
州。－ｌ＋．一十爿刈ｒ｜＋槲＜（Ｎ（，）．１）×（Ｊｒ｜¨‘１＋．一十｜ｒ｜＋１）＜
ｒ
Ｉ一１＜Ｎ（Ｊ’）一１ｊ
ｒ
Ｉ＜Ｎ（，），与假设产生矛盾，故ｒ不是，（Ｔ）
设非零多项式ｆ（工）∈Ｒ［工］，令．厂（工）＝（Ａ，，ｚ３Ｃ”＋“，ｌＴ’２—１＋…＋ｎｌ丁＋“”
ａｌ
假设７ｌ＞０，ｎ。≠０，记Ｌ（．厂）＝１＋ｍａｘ｛Ｉ
Ｉ，Ｉ
ａ２
Ｉ，…，Ｉ
ｎ。Ｉ｝／Ｉ“１）１．若ｒ为多项式
Ｉ≥南・
ａ。Ｉ，ｌ
ａｎ－１
设ｆ（ｚ）＝“，一’１＋ａ，。一ｌＴ”１＋…十“ｌｚ＋ｎ（）∈ｚ［ｚ］是整系数多项式，令ＩＩ．，¨ｉ１；ｌｉｆｌｌｏ。＝ｍａｘ｛ｌ
Ｉ，…，ｌ
ａｌ
＝∑ｌ
ｎｉ
ｌ，ｌ
ａｏ
ｌ｝，则多项式．ｆ‘（工）的所有根都
在区间（一ＩＩ．，’ｌＩ零根ｒ，满足
证明
Ｉ＋Ｉ
ｔｔｎ－１
ｒ
ｌ，｜｜Ｉ厂｜｜１），（一１一ＩＩ川ｏ。，１十Ｉ｜ｌ厂｜ｆ。。）中，而且对于多项式．厂（ｚ）的所有非
Ｉ＞ｉ
１）由于ｆ（ｚ）是整系数多项式，因为Ⅱｉ≠０，所以Ｉ“川≥１，于是有Ｉ｜，’忆＝ｌ“。
Ｉ＋…＋Ｉ
ｎｏ
Ｉ≥１＋Ｉ
ａｎ－１
Ｉ＋…＋ｌ
ｎ（）Ｉ≥１十（≥二ｌ“ｊＪ）／ｌ
“。ｌ≥’
ｍａｘ｛１，（∑ｆ“川／ｆ‰Ｉ｝＝Ｍ（，）．
，由定理２可知多项式，‘（ｚ）的所有根都在区间（一ＩＩ刘１，｜Ｉ川１）中．
２）由于．厂（Ｔ）是整系数多项式，因为ｕ；≠０，所以Ｉ
ｍａｘ｛Ｉ“。ｌ，Ｉ“。一ｌＩ，…，Ｉ
ａＯ
ａｉ
Ｉ≥１，于是有ｌＩ．刚ｏ。＋１＝
Ｉ，…，ｌ“ｌＪ１｝＋
１
ｌ｝＋
１
≥
ｍａｘ｛１，ｌ
ａ。一ｌ
≥
１
＋
ｎｌａｘ｛１，Ｉ
——
ａ‰ｔ！－１
ｌ，…，ｌ罢１）≥Ｎ（厂）．由定理２可知多项式ｆ（ｘ）的所有根都在区问（一１一
ＩＩ，｜｜ｏ。，１十｜Ｉ，ｌｌｏｏ）中．
３）设ｒ为．，’（ｚ）的非零实根，则有／’（ｒ）＝ｎ。ｒｎ＋Ｃｔ，ｌ，’１＋…＋ｎｌＩ＝０ｊｎ。＋ａｎ－ｌ×
６——
万方数据
专＋…＋ｎ。×（专）“＝ｏ，做ｇ（ｙ）＝ａｏＮｎ＋ａｌｙｎ－１＋…十口。，则又有ｇ（｛）＝ｏ．而ｆｊｆｌｌ。。
＝ＩＩ
ｇ
ＩＩ
ｏ。，由２）知Ｔ＿ｈ＜１＋ＩＩ１１１
ｏ。，因此有Ｉ
ｒ
ｌ＞ｒＦ寻了Ｉ＝．．
显然，定理２至定理４给出了多项式ｆ（ｚ）的所有实根的上下界，进而确定了一个包含多项式ｆ（ｚ）所有实根的区间．
２
Ｓｔｕｒｎｌ定理
由第二节知，我们确定了一个包含多项式ｆ（ｚ）所有实根的区间（一１一ＩＩ．刚。。，１＋
｜｜，ＩＩｏ。）和区问（一Ｉｌ，ＩＩｌ，｜｜，｜｜１）．下面利用这两个区间来求多项式ｆ（ｚ）的孤立区间，为研究方便，我们引入Ｓｔｕｒｍ序列的定义及Ｓｔｕｒｍ定理．
定义２［６３
设，（ｚ），ｇ（ｚ）ＥＲ［ｚ］，由ｆ，ｇ定义的多项式序列（ｒ０（ｚ），ｒｌ（ｚ），…ｒ。（ｚ））
称为Ｓｔｕｒｍ序列．若它们满足：
ｒｏ（ｚ）＝ｆ（工）ｒｌ（ｚ）＝ｇ（工）
ｒｏ（ｚ）＝ｑｌ（ｚ）ｒｌ（３２）一ｒ２（工），ａ（ｒ２（ｚ））＜ａ（ｒ１（ｚ））Ｖｉ－Ｉ（Ｔ）＝ｑｉ（ｚ）ｒｉ（ｚ）一ｒｉ＋ｌ（ｚ），ａ（ｔ＋ｌ（ｚ））＜ａ（一（ｚ））
＾一】（ｚ）＝吼（ｚ）以（丁）
用Ｓｔｒｕｍ（ｆ，ｇ）来表示由ｆ，ｇ产生的多项式序列（ｒｏ（ｚ），ｒ１（ｚ），ｏｏ・，＾（ｚ））．
定理３如果Ｃ＝＜ｃｌ，ｃ２，…，ｃ。）是实数域Ｒ上的非零有限序列，则称Ｖ（ｃ）＝Ｉ｛ｉ：１≤ｉ≤ｓ，ｃｉ×Ｃ州＜０｝Ｉ为序列ｃ的签曼变！￡鱼麴．
定义４
对于一个多项式序列Ｆ＝（ｆｌ（ｚ），ｆ２（ｚ），…，五（ｚ））和实数域Ｒ上的一个数ａ，
则称Ｖ。（Ｆ）＝Ｖ（（ｆｌ（口），，２（ｎ），…，＾（口）＞）为多项式序列Ｆ关于数倪的符号变化数．
Ｓｔｕｒｍ定理
设ｆ（ｚ）∈Ｒ［ｚ］，对于任意一区间［ａ，６］ｃＲ，记７．Ｉｕｒｎ为ｒ（工）在区间［ａ，
１１）］上不同根的个数，则有：Ｖｎ（Ｓｔｕｒｍ（ｆ，．厂））一Ｖ６（Ｓｔｕｒｍ（ｆ，ｆ７））＝，㈨玑
证明
见参考文献［６］．
定理５【２】
多项式方程ｆ（ｚ）＝０的正实根个数或者恰好为ｆ（ｚ）中系数列的变号数，或
者比ｆ（ｚ）中系数列的变号数少一个的正偶数，其中ｆ（ｚ）＝Ｏ．ｎ２ｃ”＋ａ。一ｌ工”。＋…＋ｃＬｌｚ＋“ｎ．
推论１多项式方程．ｆ（ｚ）＝０的负实根个数恰好为ｆ（一ｚ）中系数列的变号数或者比之少一个的正偶数，其中．，’（ｚ）＝ａ．ｎｊ２”＋ｎ，ｌｚ”一１＋…＋ｎｌｚ＋ｎｏ．推论２若厂（ｚ）没有负系数，则厂（工）＝０没有正根．
推论３
若ｆ（一ｚ）没有负系数，则ｆ（ｚ）＝０没有负根．
３
求孤立区间的ＲＯＯＴＩＳＯＬＡＴＥ算法ＲＯＯＴＩＳＯＬＡＴＥ算法虫玎一Ｆ：①Ｓｔｕｒｍ（ｆ，厂）净Ｆ；②ＩＩ，ｌｌ
１≥Ｉ，，一｛ｊ刘１≥口；③若Ｖｎ（Ｆ）＝Ｖ『Ｊ（Ｆ），则多项式ｆ（工）
无实根．若Ｖ。（Ｆ）一Ｖｂ（Ｆ）＝１，则多项式，’（３２）只有一个实根，且区间［～１１．川ｌ，ｌ｛．，‘｜ｌ门是
——
１——
万
方数据
所求的惟一的孤立区间；④若Ｕ（Ｆ）一Ｖ６（Ｆ）＞１，令掣≥ｃ，此时若有Ｖｎ（Ｆ）＞ｕ（Ｆ），
则令ｃ≥６，否则令ｃ≥口；⑤若Ｖｎ（Ｆ）一Ｖｂ（Ｆ）＝１，则区间［ｎ，ｂ］为所求的孤立区问，否则，
转到第４步，直到Ｕ（Ｆ）一ｖｂ（Ｆ）＝１时停止．⑥输出孤立区间［ａ，易］．
在利用Ｒ（）（）ＴＩＳＯＬＡＴＥ算法求孤立区间时，每次只能求出一个孤立区间，反复使用ＲＯＯＴＩＳＯＬＡＴＥ算法就可以求出ｆ（ｚ）的实根的所有孤立区间．在每个孤立区间上可采用二分法、迭代法很容易求出ｆ（ｚ）的所有实根．参考文献：
［１］颜庆津．数值分析［Ｍ］．北京：北京航天航空大学出版社，１９９２．［２］金一庆，陈越．数值方法［Ｍ］．北京：机械工业出版社，２０００．［３］蒋尔雄．数值逼近［Ｍ］．上海：复旦大学出版社，１９９６．［４］Ｃｕｒｔｉｓ，Ｆ．Ｇｅｅｒａｌｄ，Ｐａｔｒｉｃｋ０．Ｗｈｅａｔｌｙ［Ｊ］．Ａｐｐｌｉｅｄ
３８—４４．
ｍｕｍｅｒｃｉａｌａｎａｌｙｓｉｓ．１９８４。３１—３４．
［５］张志海，田伶改．求无重根时代数方程根的一种数值迭代方法［Ｊ］．高等学校计算数学学报，２０００，１（２３）：［６］何青．计算代数［Ｍ］．北京：北京师范大学出版社．１９９７．
ＤｉｓｔｒｉｂｕｌｉｏｎｏｆＰｏｌｙｎｏｍｉａｌＲｅａｌＲｏｏｔｓａｎｄＡｌｇｏｒｉｔｈｍ
ｏｎ
ＣａｌｃｕｌａｔｉｎｇＡＬＬＲｅａｌＲｏｏｔｓ
ＺＨＵ
７５００２１，Ｃｈｉｎａ）
Ｆｅｎｇ－ｊｕａｎ
ＮｏｒｔｈｗｅｓｔＩｎｓｔｉｔｕｅ
（ＤｅｐａｒｔｍｅｎｔｏｆＩｎｆｏｒｍａｔｉｏｎａｎｄｃａｌｃｕｌａｔｉｏｎＳｃｉｅｎｃｅｓ，’ｌ＇ｈｅＳｅｃｏｎｄ
Ｎｉｎｇｘｉａ
ｆ（）ｒＮａｔｉｏｎａｌｉｔｉｅｓ．Ｙｉｎｃｈｕａｎ
［Ａｂｓｔｒａｃｔ］Ｔｈｅａｕｔｈｏｒｇａｖｅｓｔｈｅｉｎｔｅｒｖａｌｉｎｃｌｕｄｉｎｇａｌｌｒｅａｌ
ｒｏｏｔｓ
ｏｆ
ａ
ｐｏｌｙｎｉｍｉａｌａｎｄ
ｇａｖｅｓ
ａｌｇｏｒｉｔｈｍｏｆｃａｌｃｕｌａｔｉｎｇａ１１ｒｅａｌｒｏｏｔｓ．
［Ｋｅｙｗｏｒｄｓ］ｐｏｌｙｎｏｍｉａｌ；ｒｏｏｔ；ｉｓｏｌａｔｅ（接第４页）
ｉｎｔｅｒｖａｌ；ａｌｇｏｒｉｔｈｍ；Ｓｔｒｕｍｔｈｅｏｒｙ
ＴｈｅＵｎｉｆｏｒｍｌｙ
Ｍｉｎｉｍｕｍ
ＶａｒｉａｎｃｅＵｎｂｉａｓｅｄＥｓｔｉｍａｔｏｒ
ｏｆｔｈｅＰａｒａｍｅｔｅｒｉｎＮｅｇａｔｉｖｅＢｉｎｏｍｉａｌＤｉｓｔｒｉｂｕｔｉｏｎ
ａｎｄＩｔｓＡｓｙｍｐｔｏｔｉｃＥｆｆｉｃｉｅｎｃｙ
ＴＩＡＮＪｕｎ－ｚｈｏｎｇ
（ＤｅｐａｒｔｍｅｎｔｏｆｉｎｆｏｒｍａｔｉｏｎａｎｄＣａｌｃｕｌａｔｉｏｎＳｃｉｅｎｃｅ，ＴｈｅＳｅｃｏｎｄＮｏｒｔｈｗｅｓｔ
Ｎｉｎｇｘｉａ７５００２１，ＣｈｉｎａＪ
Ｉｎｓｔｉｔｕｔｅｆｏｒ
Ｎａｔｉｏｎａｌｉｔｉｅｓ－Ｙｉｎｃｈｕａｎ
［Ａｂｓｔｒａｃｔ］Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｄｉｓｃｕｓｓｔｈｅｓｕｆｆｉｃｉｅｎｔａｎｄｃｏｍｐｌｅｔｅｓｔａｔｉｓｔｉｃｏｆｎｅｇａｔｉｖｅｂｉｎｏｍｉａｌｏｂｔａｉｎｔｈｅ
ｕｎｉｆｏｒｍｌｙｍｉｎｉｍｕｍｖａｒｉａｎｃｅｕｎｂｉａｓｅｄ
ｅｓｔｉｍａｔｏｒｗｉｔｈ
ｕｎｋｎｏｗｎ
ｄｉｓｔｒｉｂｕｔｉｏｎ，ａｎｄ
ｐａｒａｍｅｔｅｒ０ｔｈｒｏｕｇｈｄｉｓｃｕｓｓｉｏｎｏｆｃｒａｍｅｒ—Ｒａｏｉｎｅｑｕａｌｉｔｙａｎｄｔｈｅｂｅｌｏｗｂｏｕｎｄｏｆｔｈｅｕｎｂｉａｓｅｄｅｓｔｉｍａｔｅ，ｉｔｉｓｐｒｏｖｅｄｔｈａｔｕｎｉｑｕｅＵＭＶＵｅｓｔｉｎｏｔｅｏｆｔｈｅｐａｒａｍｅｔｅｒ０ｉｓａｓｙｍｐｔｏｔｉｃａｌｌｙｅｆｆｉｃｉｅｎｔｅｓｔｉｍａｔｅ．
［Ｋｅｙｗｏｒｄｓ］Ｕｎｉｆｏｒｍｌｙ
ｍｉｎｉｍｕｍｖａｒｉａｎｃｅｕｎｂｉａｓｅｄ
ｅｓｔｉｍａｔｏｒ；ｓｕｆｆｉｃｉｅｎｃｙ；ｃｏｍｐｌｅｔｅｎｅｓｓ；
ｅｆｆｉｃｉｅｎｃｙ；ＧＲｉｎｅｑｕａｌｉｔｙ；ａｓｙｍｐｔｏｔｉｃａｌｌｙｅｆｆｉｃｉｅｎｔｅｓｔｉｍａｔｅ
８
万方数据
多项式实根的分布及求所有实根的算法
作者：作者单位：刊名：英文刊名：年，卷(期)：
朱凤娟
西北第二民族学院,信息与计算科学系,宁夏,银川,750021
西北民族大学学报（自然科学版）
JOURNAL OF NORTHWEST MINORITIES UNIVERSITY (NATURAL SCIENCE）2001,22(3)
参考文献(6条)
1.颜庆津 数值分析 19922.金一庆.陈越 数值方法 20003.蒋尔雄 数值逼近 1996
4.Curtis, F. Geerald.Patrick O Wheatly 1984
5.张志海.田伶改 求无重根时代数方程根的一种数值迭代方法[期刊论文]-高等学校计算数学学报 2000(23)6.何青 计算代数 1997
本文链接：http://d.wanfangdata.com.cn/Periodical_xbmzxyxb-zrkxb200103002.aspx