吴消元法

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

历史

多项式的指标

多项式：

P=P(${\displaystyle x_{1}}$,${\displaystyle x_{2}}$,……${\displaystyle x_{n}}$)中

主变元

变元(${\displaystyle x_{1}}$,${\displaystyle x_{2}}$,……${\displaystyle x_{n}}$)中下标最大下标

称为多项式P的主变元，记为 Ivar(P)^[1]

例如 P=${\displaystyle -2*x_{2}^{2}-x_{1}*x_{2}^{2}+2*x_{1}*x_{2}+2*x_{1}^{2}*x_{1}+x_{1}^{3}}$

变元为${\displaystyle x_{1}}$,${\displaystyle x_{2}}$,主变元为 Ivar(P)${\displaystyle =x_{2}}$。

多项式的类

多项式P的类定义为 主变元 Ivar(P)的下标，记作 cls(P).

上例多项式P的类 为 cls(P)=2。

多项式的次数

多项式关于变元${\displaystyle x_{i}}$的次数 记为 deg(P,${\displaystyle x_{i}}$)^[2]

多项式关于主变元的次数，记为deg(P)=deg(P,Ivar(P))

多项式的长度，定义为多项式的项数，记为 t(P).

多项式的指标集[t(P),cls(P),deg(P)]。

多项式的初式和正则形式

初式

多项式的初式，是多项式主变元 Ivar(P) 最高幂项的系数，记为 init(P)^[3]

例如 P=${\displaystyle -2*x_{2}^{2}-x_{1}*x_{2}^{2}+2*x_{1}*x_{2}+2*x_{1}^{2}*x_{1}+x_{1}^{3}}$

${\displaystyle =(-2-x_{1})*x_{2}^{2}+2*x_{1}*x_{2}+2*x_{1}^{2}*x_{1}+x_{1}^{3}}$

init(P)=${\displaystyle (-x_{1}-2)}$;

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

：I=I(${\displaystyle x_{1}}$,${\displaystyle x_{2}}$,……${\displaystyle x_{c-1}}$)

其中 c=cls(P) 是多项式 P的类。

正则形式

将多项式表示为

P=${\displaystyle I*x_{c}^{d}+}$关于${\displaystyle x_{c}}$的低次幂项，称为多项式P的正则形式。^[4]

多项式的偏序和约化

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.^[5][6]

约化

多项式 P，Q，如果

cls(P) =c>0； deg(Q,${\displaystyle x_{c}}$)<deg(P).

则称P对于Q是约化的^[7]

如果多项式P的初式 init(P) 是常数，则对于任何低类多项式Q，（cls(Q)<cls(P))都是约化的。^[8]

例子：^[9]

P=${\displaystyle (x_{1}+3)*(x_{1}+8)*x_{2}^{5}+S(x_{1},x_{2})}$

Q=${\displaystyle (x_{1}+1)*(x_{1}+2)*(x_{1}+3)*x_{2}^{2}}$

其中 ivar(P)=${\displaystyle x_{2}}$

cls(P)=c=2

deg(P)=5

deg(S)<5

deg(Q,${\displaystyle x_{c}}$)=2;

P 对于 Q 是约化的。

升列与三角列

升列

多项式集 AS: ${\displaystyle A_{1}}$,${\displaystyle A_{2}}$....${\displaystyle A_{r}}$是一个升列

如果满足以下两个条件：^[10]

1. cls(${\displaystyle A_{1}}$） < cls(${\displaystyle A_{2}}$) <....< cls(${\displaystyle A_{r}}$)
2. init(${\displaystyle A_{j}}$) 关于 ${\displaystyle A_{i}}$ 对于任意的 i<j 是约化的。

三角列

如果非零多项式集 AS: ${\displaystyle A_{1}}$,${\displaystyle A_{2}}$....${\displaystyle A_{r}}$

只满足：

cls(${\displaystyle A_{1}}$） < cls(${\displaystyle A_{2}}$) <....< cls(${\displaystyle A_{r}}$)

则非零多项式集 AS 是一个三角列，又称为弱升列。^[11]

多项式求余与零点集

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

${\displaystyle I^{s}*G=Q*F+R}$

如取s尽量小，R称为 G关于F的Ritt余式，记为 R=Remdr(G/F)^[12]

零点集

多项式方程组 PS =0 的全部解，称为PS 的零点集，记为 Zero(PS)^[13]

两个多项式方程组 ${\displaystyle P_{1}}$,${\displaystyle P_{2}}$

如果 R=Remdr(${\displaystyle P_{2}}$/${\displaystyle P_{1}}$)

则 Zero(PS)=Zero(${\displaystyle P_{2}}$,${\displaystyle P_{1}}$)=Zero((${\displaystyle P_{2}}$,${\displaystyle P_{1}}$,R)

加入余式，零点集不变。^[14]

多项式对升列的余式

给出一个多项式P=P(${\displaystyle x_{1}}$,${\displaystyle x_{2}}$……${\displaystyle x_{k}}$}和一个升列 AS={${\displaystyle A_{1}}$,${\displaystyle A_{2}}$……${\displaystyle A_{k}}$}

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

${\displaystyle r_{k}}$=Remdr(P / ${\displaystyle A_{k}}$)

${\displaystyle r_{k-1}}$=Remdr(${\displaystyle r_{k}}$ / ${\displaystyle A_{k-1}}$)

${\displaystyle \ldots }$

${\displaystyle r_{1}}$=Remdr(${\displaystyle r_{2}}$ / ${\displaystyle A_{1}}$)

最后得到的余式 ${\displaystyle r_{1}}$≡R≡Remdr(P/AS) 称为 P 对于 AS 的余式。^[15]

R 是唯一确定的多项式。

R 对于 AS 是约化的。^[16]

软件包

• 王东明 以 Maple 编写的 CharSets 软件包，自1991年就成为Maple Shared Library 的软件包，也是他2003年 Epsilon Maple软件包的组成单元之一^[17]
• 数学机械化自动推理平台 MMP 3.0 有 charser 软件，但MMP 3.0 平台为半成品，用户寥寥无几，远不如 王东明 CharSets 软件包成功。

应用

• 计算机视觉、自動化定理證明、机器人、生物^[18]

参考文献

引用

1. 吴文俊，第三章 74页
2. Wen-tsün,p9
3. 吴文俊 75页
4. 吴文俊 75页
5. 吴文俊 75页
6. 关霭雯 15页
7. Wen-tsün, p9
8. 关霭雯 16页
9. 关霭雯 16页
10. 吴文俊 76页
11. 吴文俊 76页
12. 吴文俊 79页
13. 关霭雯 13页
14. 关霭雯 13
15. 关霭雯 21页
16. 吴文俊 80页
17. 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]
18. Chou, Shang-Ching; Gao, Xiao-Shan; Zhang, Jing-Zhong. Automated production of traditional proofs in solid geometry. Journal of Automated Reasoning. 1995, 14 (2): 257–291. ISSN 0168-7433. doi:10.1007/bf00881858.

书籍

• 吴文俊 著 《数学机械化》 科学出版社 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