查看“︁吴消元法”︁的源代码

{{NoteTA
|G1 = Math
}}
'''吴消元法'''，又称'''吴特征列方法'''，是[[中國科學院]]院士[[吴文俊]]创立的将多元多项式方程组简化然后求解的机械化算法。吴消元法可用[[计算机实现]]，是[[数学机械化]]的基础。

==历史==
{{Empty section}}

==多项式的指标==

多项式：

:::P=P(<math>x_{1}</math>,<math>x_{2}</math>,……<math>x_{n}</math>)中 
;主变元
:变元(<math>x_{1}</math>,<math>x_{2}</math>,……<math>x_{n}</math>)中下标最大下标
称为多项式P的主变元，记为 Ivar(P)<ref name="吴文俊“">吴文俊，第三章 74页</ref>
:例如 P=<math>-2*x_{2}^2-x_{1}*x_{2}^2+2*x_{1}*x_{2}+2*x_{1}^2*x_{1}+x_{1}^3</math>
:变元为<math>x_{1}</math>,<math>x_{2}</math>,主变元为 Ivar(P)<math>=x_{2}</math>。
;多项式的类
:多项式P的'''类'''定义为 主变元 Ivar(P)的下标，记作 cls(P).
:上例多项式P的'''类''' 为 cls(P)=2。
;多项式的次数
:多项式关于变元<math>x_{i}</math>的次数 记为 deg(P,<math>x_{i}</math>)<ref name="Wenjun">Wen-tsün,p9</ref>
:多项式关于主变元的''次数''，记为deg(P)=deg(P,Ivar(P))
:多项式的长度，定义为多项式的项数，记为 t(P).
:多项式的指标集[t(P),cls(P),deg(P)]。

==多项式的初式和正则形式==
;初式
多项式的'''初式'''，是多项式主变元 Ivar(P) 最高幂项的系数，记为 init(P)<ref name="w">吴文俊 75页</ref>
:例如 P=<math>-2*x_{2}^2-x_{1}*x_{2}^2+2*x_{1}*x_{2}+2*x_{1}^2*x_{1}+x_{1}^3</math>
<math>=(-2-x_{1})*x_{2}^2+2*x_{1}*x_{2}+2*x_{1}^2*x_{1}+x_{1}^3</math>

init(P)=<math>(-x_{1}-2)</math>;

初式 init(P)是一个除主变元之外的多项式I

：I=I(<math>x_{1}</math>,<math>x_{2}</math>,……<math>x_{c-1}</math>)
:其中  c=cls(P) 是多项式 P的类。

;正则形式
将多项式表示为 

:::P=<math>I*x_{c}^d+</math>关于<math>x_{c}</math>的低次幂项，称为多项式P的'''正则形式'''。<ref name="吴”">吴文俊 75页</ref>

==多项式的偏序和约化==
P，Q为非零多项式，如果 cls(P)<cls(Q)，或cls(P)=cls(Q)，但deg(P)<deg(Q),则称P的序低于Q的序。记为 P<Q。

:如果P<Q，或Q< P 都不成立，则P，Q同序，记为  P~Q.<ref name="wu wenjun">吴文俊 75页</ref><ref name="关“">关霭雯 15页</ref>
===约化===

多项式 P，Q，如果 

:cls(P) =c>0；  deg(Q,<math>x_{c}</math>)<deg(P).

则称P对于Q是约化的<ref name="wu w">Wen-tsün, p9</ref>

如果多项式P的初式 init(P) 是常数，则对于任何低类多项式Q，（cls(Q)<cls(P))都是约化的。<ref name="guan 2">关霭雯 16页</ref>
:例子：<ref name="guan 3">关霭雯 16页</ref>


:P=<math>(x_{1}+3)*(x_{1}+8)*x_{2}^5+S(x_{1},x_{2}) </math> 
:Q=<math>(x_{1}+1)*(x_{1}+2)*(x_{1}+3)*x_{2}^2</math>

其中 ivar(P)=<math>x_{2}</math>
: cls(P)=c=2
: deg(P)=5
: deg(S)<5
: deg(Q,<math>x_{c}</math>)=2;

P 对于 Q 是约化的。

==升列与三角列==
;升列
多项式集  AS: <math>A_{1}</math>,<math>A_{2}</math>....<math>A_{r}</math>是一个'''升列'''

如果满足以下两个条件：<ref name=W3>吴文俊 76页</ref>
#cls(<math>A_{1}</math>） < cls(<math>A_{2}</math>) <....<  cls(<math>A_{r}</math>)
#init(<math>A_{j}</math>) 关于  <math>A_{i}</math>  对于任意的 i<j  是约化的。

;三角列 
:如果非零多项式集  AS: <math>A_{1}</math>,<math>A_{2}</math>....<math>A_{r}</math>
:只满足：
:cls(<math>A_{1}</math>） < cls(<math>A_{2}</math>) <....<  cls(<math>A_{r}</math>)
:则非零多项式集  AS 是一个'''三角列'''，又称为'''弱升列。'''<ref name=W4>吴文俊 76页</ref>

==多项式求余与零点集==
两个多项式:F,G, 其中 cls(F)=c,init(F)=I,通过多项式除法可得：

:::      <math>I^s*G=Q*F+R </math>
如取s尽量小，R称为 G关于F的Ritt余式，记为   R=Remdr(G/F)<ref name="W5">吴文俊 79页</ref>

;零点集
:多项式方程组 PS =0 的全部解，称为PS 的零点集，记为 Zero(PS)<ref name="guan 6">关霭雯 13页</ref>
:两个多项式方程组  <math>P_{1}</math>,<math>P_{2}</math>
:如果  R=Remdr(<math>P_{2}</math>/<math>P_{1}</math>)
:则  Zero(PS)=Zero(<math>P_{2}</math>,<math>P_{1}</math>)=Zero((<math>P_{2}</math>,<math>P_{1}</math>,R)
:加入余式，零点集不变。<ref name="g5">关霭雯  13</ref>
;多项式对升列的余式

给出一个多项式P=P(<math>x_{1}</math>,<math>x_{2}</math>……<math>x_{k}</math>}和一个升列      AS={<math>A_{1}</math>,<math>A_{2}</math>……<math>A_{k}</math>}

按反向次序连环计算下列余式：

:<math>r_{k}</math>=Remdr(P / <math>A_{k}</math>)
:<math>r_{k-1}</math>=Remdr(<math>r_{k}</math> / <math>A_{k-1}</math>)
:<math>\ldots</math>

:<math>r_{1}</math>=Remdr(<math>r_{2}</math> / <math>A_{1}</math>)

最后得到的余式  <math>r_{1}</math>≡R≡Remdr(P/AS) 称为 P 对于 AS 的余式。<ref name="g7">关霭雯 21页</ref>
:R 是唯一确定的多项式。
:R 对于 AS 是约化的。<ref name="Wu 80">吴文俊 80页</ref>
==软件包==
* 王东明 以 [[Maple]] 编写的 CharSets 软件包，自1991年就成为Maple Shared Library 的软件包，也是他2003年  Epsilon Maple软件包的组成单元之一<ref>Domgming Wang, p26 CharSets Package - Version 2.2 (C) 2003 by Dongming Wang [cfactor, charser, charset, csolve, ecs, eics, ics, iniset, ivd,   mcharset, mcs, mecs, pid, qics, remset]</ref>
*[[数学机械化自动推理平台]] MMP 3.0 有 charser 软件，但MMP 3.0 平台为半成品，用户寥寥无几，远不如 王东明 CharSets 软件包成功。

== 应用 ==

* [[计算机视觉]]、[[自動化定理證明]]、[[机器人]]、[[生物]]<ref>{{Cite journal|title=Automated production of traditional proofs in solid geometry|url=http://dx.doi.org/10.1007/bf00881858|last=Chou|first=Shang-Ching|last2=Gao|first2=Xiao-Shan|date=1995|journal=Journal of Automated Reasoning|issue=2|doi=10.1007/bf00881858|volume=14|pages=257–291|issn=0168-7433|last3=Zhang|first3=Jing-Zhong}}</ref>

== 参考文献 ==
=== 引用 ===
{{Reflist|2}}

=== 书籍 ===
* [[吴文俊]] 著 《数学机械化》 科学出版社 2006  ISBN 7-03-010764-0
* Wen-tsün Wu, The Characteristic Set Method and Its Applications, p4-41 Mathematics Mechanization and Applications, Ed, Xiao-Shan Gao, Dongming Wang, Academic Press 2000 ISBN  0-12-734760-7
* [[王东明 (数学家)|王东明]] 著 《消去法及其应用》 科学出版社 2002 ISBN 7-03-010560-5
* Dongming Wang（王东明）. ''Elimination Practice'' London: Imperial College Press, 2004, ISBN 1-86094-438-8
* 高小山、王定康、裘宗燕、杨宏 著 《方程求解与机器证明》 科学出版社 2008  ISBN 978-03-017862-6
* 关霭雯 编 《吴消元法讲义》  北京理工大学  1994

{{中国数学史}}
{{Authority control}}
[[Category:数学术语]]
[[Category:数学机械化]]
[[Category:多项式]]