Gröbner基理论是一种在国外被普遍认同的用于求解多变元高次方程系统的有效算法,其概念最早由Buchberger提出.其本质是从多项式环中任意理想的生成元出发,刻画和计算出一组具有“好的”性质的生成元,进而研究理想的结构并进行某些理想运算;由于数学、科学和工程学中的许多问题都可以用多元多项式方程组表示(例如,理想,模块和矩阵),Gröbner基的代数算法在理论物理学、应用科学和工程学中具有广泛的应用;
让我们先来了解如何用Gröbner基来计算多项式理想;
判定任给多项式是否属于一个给定生成元的理想，
♡ \heartsuit ♡ 定理3.1 :P \mathbb{P} P K [ x ] \mathcal{K}[\boldsymbol{x}] K [ x ] G \mathbb{G} G P \mathbb{P} P P ∈ K [ x ] P \in \mathcal{K}[\boldsymbol{x}] P ∈ K [ x ]
P ∈ ⟨ P ⟩ ⟺ nform ( P , G ) = 0 P \in\langle\mathbb{P}\rangle \Longleftrightarrow \operatorname{nform}(P, \mathbb{G})=0 P ∈ ⟨ P ⟩ ⟺ n f o r m ( P , G ) = 0
♡ \heartsuit ♡ 定理3.2 :P \mathbb{P} P Q \mathbb{Q} Q K [ x ] \mathcal{K}[\boldsymbol{x}] K [ x ] G \mathbb{G} G P \mathbb{P} P
⟨ Q ⟩ ⊂ ⟨ P ⟩ ⟺ nform ( Q , G ) = { 0 } \langle\mathbb{Q}\rangle \subset\langle\mathbb{P}\rangle \Longleftrightarrow \operatorname{nform}(\mathbb{Q}, \mathbb{G})=\{0\} ⟨ Q ⟩ ⊂ ⟨ P ⟩ ⟺ n f o r m ( Q , G ) = { 0 }
⋆ \star ⋆ 例3.3(判定理想I I I :I = ⟨ f 1 , f 2 ⟩ = ⟨ x z − y 2 , x 3 − z 2 ⟩ ∈ C [ x , y , z ] I=\left\langle f_{1}, f_{2}\right\rangle=\left\langle x z-y^{2}, x^{3}-z^{2}\right\rangle \in \mathbb{C}[x, y, z] I = ⟨ f 1 , f 2 ⟩ = ⟨ x z − y 2 , x 3 − z 2 ⟩ ∈ C [ x , y , z ] f = − 4 x 2 y 2 z 2 + y 6 + 3 z 5 f=-4 x^{2} y^{2} z^{2}+y^{6}+3 z^{5} f = − 4 x 2 y 2 z 2 + y 6 + 3 z 5 f ∈ I f \in I f ∈ I
计算其Gröbner基:G = ( f 1 , f 2 , f 3 , f 4 , f 5 ) = ( x z − y 2 , x 3 − z 2 , x 2 y 2 − z 3 , x y 4 − z 4 , y 6 − z 5 ) G=\left(f_{1}, f_{2}, f_{3}, f_{4}, f_{5}\right)=\left(x z-y^{2}, x^{3}-z^{2}, x^{2} y^{2}-z^{3}, x y^{4}-z^{4}, y^{6}-z^{5}\right) G = ( f 1 , f 2 , f 3 , f 4 , f 5 ) = ( x z − y 2 , x 3 − z 2 , x 2 y 2 − z 3 , x y 4 − z 4 , y 6 − z 5 )
现在可以判定I I I G G G f f f
f = ( − 4 x y 2 z − 4 y 4 ) ⋅ f 1 + 0 ⋅ f 2 + 0 ⋅ f 3 + 0 ⋅ f 4 + ( − 3 ) ⋅ f 5 + 0 f=\left(-4 x y^{2} z-4 y^{4}\right) \cdot f_{1}+0 \cdot f_{2}+0 \cdot f_{3}+0 \cdot f_{4}+(-3) \cdot f_{5}+0 f = ( − 4 x y 2 z − 4 y 4 ) ⋅ f 1 + 0 ⋅ f 2 + 0 ⋅ f 3 + 0 ⋅ f 4 + ( − 3 ) ⋅ f 5 + 0
因为其余数为0 0 0 f ∈ I f \in I f ∈ I
在数学和应用科学的许多不同领域中,有许多问题都可以使用Grobner基础解决.在这里,我们仅列出一些应用问题:
多项式方程组的求解系统,例如相交的曲面和曲线,找到曲线上或曲面上最接近给定点的点,Lagrange乘子问题(尤其是那些具有多个乘子的问题)等.这些问题的解决方案基于所谓的扩展理论.参见文献[1]
为等距曲线和曲面找到到由多项式方程定义的曲线和曲面的方程,例如圆锥截面,Bezier三次方程;在各种多项式集合之间找到syzygy关系,例如对称多项式,有限组不变式,插值函数等.这些问题的解决方案基于所谓的消除理论.参见文献[1]
找到等距的曲线和曲面作为相应曲线和曲面族的包络.参见文献[2,1]
隐式化问题,即消除参数并找到曲线和曲面的隐式形式.
机器人技术中的正向运动学和逆向运动学问题.参见文献[3,1]
自动几何定理证明.参见文献[3,4,1]
根据生成不变式表达有限组的不变式.参见文献[1]
查找多项式函数之间的关系,例如插值函数(Syzygy关系).
有关大地测量学的最新应用.参见文献[5]
另请参见约翰·拉顿计算与应用数学研究所(RICAM)的Grobner基地书目.参见文献[6]
⋆ \star ⋆ 例3.4 :S 1 S_{1} S 1 S 2 S_{2} S 2 f 1 f_{1} f 1 f 2 f_{2} f 2
f 1 = 4 ( x 1 − 1 ) 2 + 4 x 2 2 + 4 x 3 2 − 9 , f 2 = ( x 1 + 1 ) 2 + x 2 2 + x 3 2 − 4 f_{1}=4\left(x_{1}-1\right)^{2}+4 x_{2}^{2}+4 x_{3}^{2}-9, f_{2}=\left(x_{1}+1\right)^{2}+x_{2}^{2}+x_{3}^{2}-4 f 1 = 4 ( x 1 − 1 ) 2 + 4 x 2 2 + 4 x 3 2 − 9 , f 2 = ( x 1 + 1 ) 2 + x 2 2 + x 3 2 − 4
也就是说 S 1 = V ( f 1 ) S_{1}=\mathbf{V}\left(f_{1}\right) S 1 = V ( f 1 ) S 2 = V ( f 2 ) S_{2}=\mathbf{V}\left(f_{2}\right) S 2 = V ( f 2 ) J J J x > y > z x>y>z x > y > z
G = { 256 x 2 2 + 256 x 3 2 − 495 , 16 x 1 − 7 } G=\left\{256 x_{2}^{2}+256 x_{3}^{2}-495,16 x_{1}-7\right\} G = { 2 5 6 x 2 2 + 2 5 6 x 3 2 − 4 9 5 , 1 6 x 1 − 7 }
此处第一个多项式c c c V ( c ) \mathbf{V}(c) V ( c ) V ( π ) \mathbf{V}(\pi) V ( π ) C = S 1 ∩ S 2 = V ( c ) ∩ V ( π ) C=S_{1} \cap S_{2}=\mathbf{V}(c) \cap \mathbf{V}(\pi) C = S 1 ∩ S 2 = V ( c ) ∩ V ( π )
i) 两个球面相交的方式(图左);ii) 圆柱面和平面相交的方式(图右);
⋆ \star ⋆ 例3.5(机械手臂动作规划) :V V V { e 1 , e 2 , e 3 , e 4 , e 5 } \left\{\mathbf{e}_{1}, \mathbf{e}_{2}, \mathbf{e}_{3}, \mathbf{e}_{4}, \mathbf{e}_{5}\right\} { e 1 , e 2 , e 3 , e 4 , e 5 } V V V
e i 2 = 1 , e i ⋅ e j = e j ⋅ e i = 0 , e i ⋅ e 4 = e i ⋅ e 5 = 0 , e 4 2 = e 5 2 = 0 , e 4 ⋅ e 5 = − 1 \mathbf{e}_{i}^{2}=1, \quad \mathbf{e}_{i} \cdot \mathbf{e}_{j}=\mathbf{e}_{j} \cdot \mathbf{e}_{i}=0, \quad \mathbf{e}_{i} \cdot \mathbf{e}_{4}=\mathbf{e}_{i} \cdot \mathbf{e}_{5}=0, \quad \mathbf{e}_{4}^{2}=\mathbf{e}_{5}^{2}=0, \quad \mathbf{e}_{4} \cdot \mathbf{e}_{5}=-1 e i 2 = 1 , e i ⋅ e j = e j ⋅ e i = 0 , e i ⋅ e 4 = e i ⋅ e 5 = 0 , e 4 2 = e 5 2 = 0 , e 4 ⋅ e 5 = − 1
进一步的方式表示以上约束有:
P = p + 1 2 p 2 e ∞ + e 0 , S = s + 1 2 ( s 2 − r 2 ) e ∞ + e 0 , π = n + d e ∞ P=\mathbf{p}+\frac{1}{2} \mathbf{p}^{2} e_{\infty}+e_{0}, \quad S=\mathbf{s}+\frac{1}{2}\left(\mathbf{s}^{2}-r^{2}\right) e_{\infty}+e_{0}, \quad \pi=\mathbf{n}+d e_{\infty} P = p + 2 1 p 2 e ∞ + e 0 , S = s + 2 1 ( s 2 − r 2 ) e ∞ + e 0 , π = n + d e ∞
这儿p \mathbf{p} p s \mathbf{s} s r \mathbf{r} r n \mathbf{n} n d d d
值得注意的是,以上是约束方程 ,也就是机械手臂无论怎么动都必须满足的方程,我们还会引入目标方程,也就是希望机械手臂终端去触碰的轨迹,这时结合约束方程,就会得到一个非线性多项式方程组,其解即为操纵段的运动轨迹;比如需要求解:
C = S 1 ∧ S 2 = − 17 8 e 1 ∧ e ∞ + 2 e 1 ∧ e 0 − 7 8 e 0 ∧ e ∞ C=S_{1} \wedge S_{2}=-\frac{17}{8} \mathbf{e}_{1} \wedge e_{\infty}+2 \mathbf{e}_{1} \wedge e_{0}-\frac{7}{8} e_{0} \wedge e_{\infty} C = S 1 ∧ S 2 = − 8 1 7 e 1 ∧ e ∞ + 2 e 1 ∧ e 0 − 8 7 e 0 ∧ e ∞
写出其多项式方程组形式,再求这个方程组生成的理想I I I
{ − 495 + 256 r 2 , c 3 , c 2 , − 7 + 16 c 1 , n 3 , n 2 , n 1 + 2 } \left\{-495+256 r^{2}, c_{3}, c_{2},-7+16 c_{1}, n_{3}, n_{2}, n_{1}+2\right\} { − 4 9 5 + 2 5 6 r 2 , c 3 , c 2 , − 7 + 1 6 c 1 , n 3 , n 2 , n 1 + 2 }
最终我们解出得到n c = ( − 2 , 0 , 0 ) , c = ( 0 , 0 , 0 ) , \mathbf{n}_{\mathbf{c}}=(-2,0,0), \mathbf{c}=(0,0,0), n c = ( − 2 , 0 , 0 ) , c = ( 0 , 0 , 0 ) , r = 5 2 r=\frac{\sqrt{5}}{2} r = 2 5
⋆ \star ⋆ 例3.6 :
x m + j ( e ) + x j ( e − 1 ) + ∑ l = 1 m d j , l ⋅ f ( x m + l ( e − 1 ) + k l ( e − 1 ) ) = 0 x_{m+j}^{(e)}+x_{j}^{(e-1)}+\sum_{l=1}^{m} d_{j, l} \cdot f\left(x_{m+l}^{(e-1)}+k_{l}^{(e-1)}\right)=0 x m + j ( e ) + x j ( e − 1 ) + l = 1 ∑ m d j , l ⋅ f ( x m + l ( e − 1 ) + k l ( e − 1 ) ) = 0
那么很明显我们就是想解出某个约束方程组(先将上面这个方程组记为P = { p i = 0 } \mathcal{P}=\left\{p_{i}=0\right\} P = { p i = 0 } ( ( P 1 , … P t ) , ( C 1 , … , C t ) ) \left(\left(P_{1}, \ldots P_{t}\right),\left(C_{1}, \ldots, C_{t}\right)\right) ( ( P 1 , … P t ) , ( C 1 , … , C t ) ) G = { g i = 0 } \mathcal{G}=\left\{g_{i}=0\right\} G = { g i = 0 }
x 1 ( 0 ) + P 1 = 0 x 1 ( r ) + C 1 = 0 ⋮ ⋮ x t ( 0 ) + P t = 0 x t ( r ) + C t = 0 \begin{array}{ll}
x_{1}^{(0)}+P_{1}=0 & x_{1}^{(r)}+C_{1}=0 \\
\vdots & \vdots \\
x_{t}^{(0)}+P_{t}=0 & x_{t}^{(r)}+C_{t}=0
\end{array} x 1 ( 0 ) + P 1 = 0 ⋮ x t ( 0 ) + P t = 0 x 1 ( r ) + C 1 = 0 ⋮ x t ( r ) + C t = 0
现在令I \mathfrak{I} I L = ( ⋃ i { p i } ) ∪ ( ⋃ i { g i } ) \mathcal{L}=\left(\bigcup_{i}\left\{p_{i}\right\}\right) \cup\left(\bigcup_{i}\left\{g_{i}\right\}\right) L = ( ⋃ i { p i } ) ∪ ( ⋃ i { g i } ) **恢复理想 .
聪明的读者到此处应该已经知道了,我们就是要求I \mathfrak{I} I G D R L G_{DRL} G D R L G = { g i = 0 } \mathcal{G}=\left\{g_{i}=0\right\} G = { g i = 0 }
Gröbner基方法属于代数几何和交换代数偏应用的、计算机算法色彩比较浓厚的一个方向,由于其可用性、理论深度兼具,因此非常值得学习,特别是针对有志于用代数工具和思维解决工程实际问题的研究人员来说,更应该掌握;
(完结)
[1] D. Cox, J. Little, D. O’Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. (Springer, New York, 2008)
