r+n上正半定型差分代换

r+n上正半定型差分代换

最近，差分代换（sd）引起了相关科学家的注意。杨路对此做了较为系统的研究,引入逐次差分代换方法(SDS),克服了传统差分代换一次不成难以继续的困难。刘保乾也对差分代换做了一些探讨。对于什么样的多项式类,其逐次差分代换施行有限步后所产生的多项式集合中每个多项式的所有系数都是非负的?杨路等和姚勇研究认为:凡在R+n上严格正定的多项式,其逐次差分代换施行有限步后所产生的多项式集合中每个多项式的所有系数必然都变成非负,即在R+n上严格正定的多项式必是差分代换有限步到位的。然而,这些结果对于正半定型却是半可判定的。其后,徐嘉等用杨路等提出的逐次结式方法,给出差分代换完备化算法。另有一些学者将差分代换方法应用于非正半定型。Hou等利用型的系数、次数、变元个数及其在标准单形上的最小值给出了一个上界M,证明了非正定型的M次差分代换集中必有多项式,其系数全为负数。实际上,欲使差分代换集序列负向终止,只需差分代换集中存在多项式负定即可。因此可能会得到比M更小的上界m。本文发展差分代换方法,估计出这样的上界m,将这一上界与柱形代数分解算法结合,得到R+n上正半定型判定的一个完备化。本文还将探讨差分代换与柱形代数分解相结合的方法,同时提出一种新的差分代换矩阵以减少差分代换的次数。最后举例说明算法的正确性与有效性,并与其他差分代换算法做比较。1组成的集合和型f的m次差分代换集原始的差分代换方法选取矩阵An作为基本代换矩阵。然而,当m→∞时不收敛,这使得判定逐次差分代换方法的终止性变得困难。姚勇考虑将随机矩阵Tn作为其基本代换矩阵,因此可以更顺利地讨论终止性问题。定义1型(即齐次多项式)…叫做在R+n上是正半定的(PSD),如果满足其中……}。如果f还满足蕴涵关系则称f在R+n上是正定的(简称PD)。设Sn是n个文字的对称群是由σ对应的n×n置换矩阵。定义2n×n方阵Bσ由下式定义(即由Tn经行置换得到):并记所有Bσ组成的集合为PTn(共n!个元)。R+n中的标准单形Δn定义为点集:记如果则明显。定义3记定义线性映射如下:ψσ:,X。更一般的映射ψσ的复合是这里。标准单形Δn是由……,0)T,…所张成,即…,en]。明显映射的象是单形。记单形S的直径为d(S),我们有如下引理。引理1对于标准单形有设则也即引理2点…是线性独立的它们张成的单形记为。则有引理3定义4f∈R[x1,…,xn],X=(x1,x2,…,xn)T,Sn是n个文字的对称群。定义集合集合就称为型f的m次差分代换集。定义5型定义f的差分代换集序列(也称SDS集序列)如下:一个d次型f可写为其中…。记定义6如果型f的每一单项前的系数Cα都是非负实数,则称f是正平凡的。如果f(1,1,…,1)<0,则称f是负平凡的。明显地,型f是正平凡的,则f∈PSD;型f是负平凡的,则f∉PSD。定义7对给定的型f,若存在某个正整数k,使集合中每一个元都是正平凡的,这时称集合序列正向终止。定义8对给定的型f,若存在某个正整数k和型g,满足且g是负平凡的,这时称是负向终止的。定义9对给定的型f,集序列既不正向终止,也不负向终止,则称集序列为不终止。定义10对于一个n元多项式…,将h分解为中的不可约多项式乘积:定义sqrfree(h)如下:定义11对环中的一组无平方因子且两两互素的多项式集Brown投影算子为其中,lc(Pi,xn)是多项式Pi关于变元xn的首项系数(或称导系数),disc(Pi,xn)是多项式Pi关于变元xn的判别式,res(Pi,Pj,xn)是多项式Pi与Pj关于变元xn的结式。2主要结果2.1算法项的检验我们首先证明如下引理。引理4对于一个形如式(1)的d次型f,及标准单形上两点X′和X″,若|X′-X″|≤h,则证明记则由n元函数中值定理有其中0<θ<1,从而定理1给定一个形如式(1)的d次型…在标准单形上有解,则f的次差分代换集中必有负平凡元素。证明经过m次差分代换后,由引理3知,必存在使得且注意到标准单形的直径为故由引理4知,当或时,对于有从而定理得证。注这一上界要优于文献的定理2.1所给出的上界。事实上,算法1Projectk:给定一个n元d次齐次多项式算法Projectk返回非负实数k。中的多项式有正根,隔离最小的正根T0引理5对于d次型f,算法Projectk求得的k有如下性质:1)若k=0,则f是PSD的;2)若k>0,且f不是PSD的,则也不是PSD的。证明引进变量T,求出在标准单形上使下式非负的最小正数T的一个下界:f在标准单形上最小值的绝对值即为最小的正数T。我们用算法Projectk来求T的下界。记号同算法Projectk,将中非常数的多项式相乘记为P,则P为关于T的一元多项式。由Brown投影算子的性质知,若P无正根,则f为PSD,因此f≥0,否则最小的正根T0∈[a1,b1],其中a1>0。由条件及柱形代数分解(CAD)算法知,T∈[0,T0]时,F(T,x1,x2,…,xn)在Rn上必有实根。事实上,我们所欲求的T,必为P1的正根之一。从而当时,在标准单形上存在点X′,使得。因此不是PSD的,引理得证。由定理1、算法Projectk和引理5可知,对于型f,我们可以求得k>0,若f的次差分代换集中无负平凡元素,则f∈PSD。综上,差分代换对于正半定型是可判定的。在求满足f(X′)+k<0的k时,我们用到了柱形代数分解算法的投影部分。下面给出在求得这样的k后,通过检验样本点来判断型f正半定的方法。我们知道,对于非齐次的不等式,可以对其齐次化。证明令个点所构成的点集为S,对于标准单形上点X且f(X)=-k<0,必存在且则由引理4知:我们提供了一种用检验有限个点来证明n元不等式的方法,这只需要很少的数学知识。当然,当维数增多时,其需检验的点(样本点)也会大大增加。以Tn类差分代换为例,每做一次差分代换,实质是将单形分为n!个小单形。而我们已证明m步后,若型f非正半定则其必终止。所以我们也可以从(n!)m个单形中(此时每一个单形即为一个胞腔)各取出一个样本点(比如其重心),检验型f在这一点处的值,若全为非负,则型f为正半定。还有一种方法是采用差分代换与检验样本点相结合的方法,当差分代换集序列中元素始终增加时,就直接检验样本点。2.2h3类差分代换的推广差分代换矩阵Tn是姚勇在杨路提出的An差分代换矩阵的基础上建立的,优点是,作为列平均随机矩阵,迭代多次后矩阵能收敛。然而从定理1的证明中不难发现,每做一次迭代,直径仅变为原来的不利于对于次数m的估计。究其原因是差n-1n分代换这个名称使其局限于上三角矩阵。针对三元的情形,我们提出一种新的代换矩阵:H3类差分代换在几何上可以看做将二维的单形分成4个彼此全等并与原单形相似的单形。当n=4时,利用Dehn不变量,可证明不存在这样的矩阵与H3有同样的性质。因此能否将H3类差分代换推广至n≥5元的情形,也有待进一步研究。对于n=4,我们考虑如下代换矩阵:此时每做一次这样的差分代换,会产生8个新的型当时,是否存在这样的代换矩阵,使得每做一次差分代换,产生2n-1个新的型:这有待我们进一步研究。我们考虑如下矩阵:这样每做一次这样的差分代换,会产生n个新的型容易验证Zn类差分代换对于正定型的判定是完备的。徐嘉等据Tn类差分代换编写的TSDS5,需调用Maple宏包combinat中的命令permute。当n≥10时,屏幕会显示objecttoolarge,也即此时,TSDS5无效。尽管可以通过一些修改,使它逐个验证产生的n!个多项式,但这也需要消耗大量的资源,故Zn类差分代换能弥补Tn的不足。具体编程时,对于n=3的情形,我们选用H3类差分代换,9≥n≥4时,选用Tn类差分代换,n≥10时,选用Zn类差分代换。3输出型f是正半定型T1:依据算法Projectk,求出相应的k:=Projectk(f)T2:由k求出差分代换次数的上界m(见定理1)T4:对集F中每一个元素,计算集记不是正平凡的}T41:如果Temp是空集,则输出型f是正半定型,并停机T42:如果Temp中有负平凡的多项式,则输出型f不是正半定型,并停机T43:否则,令F=Temp,继续步骤T4T44:若m步之后程序仍未停机,则输出型f是正半定型,并停机根据上面的算法,我们在姚勇编写的程序tsds5基础之上重写了子程序restsds,并对newtsds等子程序略做修改,得到程序resnsds,此程序理论上对于判定型f的正半定性是完备的。4输出正则函数我们首先来比较类差分代换与类差分代换的应用范围(不加入完备化)。选用对比的程序为tsds5与resnsds。测试在InterCore22.10GHz的笔记本电脑,Maple15环境下进行。例1x,y,z∈R+,n∈Z,且n≥1,则f是严格正定的。n=1时,姚勇指出An类差分代换失效,事实上对于所有满足题目要求的n,An类差分代换均失效。n=6时,Tn类差分代换需16次,用时521.093秒;而H3类差分代换则需13次,用时只需9.078秒。n=7时,Tn类差分代换进行至第13次时已耗时超过1800秒,差分代换集中的多项式多达73801个,并无终止迹象。H3类差分代换需15次,耗时69.203秒。例2ai∈R+,i=1,2,...,10,判断或否定上述不等式显然不成立,例如a1=1,a2=1,ai=0,i=3,4,...,10。但若调用tsds5中的tsds(An类差分代换)或newtsds(Tn类差分代换),均显示“Error,(incombinat:-permute)objecttoolarge”。而基于Zn类差分代换的程序resnsds在差分代换一次后即输出不等式不成立。例3x1,x2,…则本例即为著名的均值不等式,无论An类差分代换或Tn类差分代换都是一次终止的。但对于H3类差分代换、J4类差分代换和Zn类差分代换,却是不终止的。通过以上几例可以发现各类差分代换都有在某些特定问题时的优势。我们提出新的差分代换矩阵,主要目的是用于降低差分代换次数的上界以及减少差分代换集中多项式的数目,提高完备化时证明的效率。例4a,b,c∈R+,则f无论用An还是用作为差分代换矩阵,都是不终止的。用反证法,假设f是不定的,根据引理5,由柱形代数分解算法,我们可求得1即1仍然是不定的。若选用H3类差分代换,此时差分代换10次后,差分代换集中无负平凡元素。因此导致矛盾,故不等式成立。整个过程若调用resnsds不足0.3秒。若选用Tn类差分代换,此时类似地,可由矛盾导致不等式成立。Hou等进一步得到仅与多项式的系数、次数、变元个数有关的非正半定型差分代换,终止次数的上界为这样不需要使用柱形代数分解即可实现差分代换的完备化。然而他们所得的上界过于巨大,因此在实际证明不等式中往往是不可行的。例如在本例中,运用他们的上界知,若4749次差分代换集中无负平凡元素,则不等式成立。然而第50次差分代换集中的多项式数目已多达46455个,总耗时超过4000秒,从第25次差分代换开始,差分代换集中的多项式数目都严格单调递增,以目前的计算机配置,几乎不可能算至4749次代换。由于完备化过程中引入了新的变元,作结式也增加了额外的计算,因此对于变元较多或次数较高的问题,我们提出的完备化方法会因计算量过大而变得不可行。例5x1,x2,x3,x4,x5∈R+,则有调用差分代换完备化程序resnsds,耗时超过4000秒仍未有结果。因此,给出效率较高的完备化方法,有待我们今后进一步研究。致谢感谢北京大学夏壁灿教授在论文修改中提供的帮助。直径。也等价于a1≥a2≥…≥an≥0,b