吳消去法

吳消去法，又稱吳特徵列方法，是中國科學院院士吳文俊創立的將多元多項式方程組簡化然後求解的機械化算法。吳消去法可用計算機實現，是數學機械化的基礎。

歷史

多項式的指標

多項式：

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]

參考文獻