全标单纯形的刻画

全标单纯形的刻画

1.同伦算法对于连续映射f：内侧的rcn，验证方程f（x）=0。1.1实现yj0c3y0的有机结合,确定必要性取J3顶点集和中心顶点集分别如下:定义W:y∈J0c30c3→(ω0(y),ωl(y),…,ωn(y))T∈{-1,1}n+1,其中按yiy0yiy0是1mod4或3mod4分别取ωi=-1或1。定义设y∈J0c3‚y0≤12y∈J0c3‚y0≤12;π=(π(0)π(1)…π(n))是0,1,…,n的一个排列,j使π(j)=0;S=(s1,s2,…,sn)T∈{-1,1}n;W=W(y),则j3(y,π,s)是具有如下顶点的单纯形:J3是所有这些j3(y,π,S)的集合。1.2同标单纯形采用整数标号法。将Rn分成如下n+1个集:Q0={x=(x1‚x2‚⋯‚xn)Τ∈Rn|xi≤0(1≤i≤n)}(2)Qk={x=(x1‚x2‚⋯‚xn)Τ∈Rn|max[j∶xi≥0‚i＜j]=k‚(1≤k≤n)}(3)∀映射,G:Ω⊂Rm→Rn,定义Ω的点基于G的标号法为:lG(x)=k,若G(x)∈Qk,其中x∈Ω,k=0,1,…,n(4)若Ω中某单纯形具有全部n+1个标号,则称之为全标单纯形。1.3f16定义投影算子P如下:P:x=(x1,x2,…,xn)T∈×Rn→(x1,x2,…,xn)=P(x)∈Rn(5)选取适当的F0:Rn→Rn,作一个新的映射˜F:J0→Rn如下:˜F(x)={F0(Ρ(x))‚x0=1F(Ρ(x))‚x0＜1(6)其中x=(x1,x2,…,xn)T∈J0。取标号法l=l∼F。设F0使得J3中有且只有一个单纯形σ0,使其中一个n维面τ0⊂{1}×Rn且τ0是全标,则运算按下列步骤进行:步0:设σ0∈J3如上,y+是σ0的不属于¯τ0的顶点,置m:=0,确定一个充分小数ε>0步1:必有σm的另一个顶点y-使l(y-)=l(y+),τm+1是σm的不以y-为顶点的面,若∃k使τm+1⊂{2-k}×Rn,且diam(τm+1)≤ε,则xε∈ˉτm+1‚Ρ(xε)是F的近似零点,否则转步2。步2:利用轮移规则寻找与σm共有单纯形面τm+1的唯一τm+1∈J3,取其顶点y+∈ˉσm+1\ˉσm,置m:=m+1,转步1。2.．2.2本nn构造模型2,2,10,11.设Qi,i=0,1,…,n,如(2),(3),Rn中欧氏模记为|ue0b6|引理1:设G={σ={x0,x1,…,xn}⊂Rn|xi∈Q,i=0,1,…,n}(7)则有infσ∈G{max0≤i‚j≤n∧(xi‚xj)}≥arcsin1√n(8)(∧a‚b)其中为Rn中向量a,b的夹角。证明:记xi={xi1,xi2,…,xin}T设xnj=max1≤i≤j{xni},必有xnj|xn|≥1√n(否则推出|xn|xn||＜1,矛盾),设Si为坐标平面{x∈Rn|xi=0}‚(ˆa‚S)是向量a∈Rm与Si的夹角,利用“位于平面两侧的两向量夹角不小于它们与这平面的夹角之和”这一事实,有maxl≤i‚j≤n(∧xi‚xj)≥(∧xn‚xj)≥(∧xn‚Sj)+(∧xj‚Sj)≥(∧xn‚Sj)=arcsin|xnj||xn|≥arcsin1√n引理2:设G如(7),则∀ε>0,当diam(σ)≤ε时有supσ∈G{maxl≤i≤n[|xi|xi∈σ]}≤(√n+1)ε(9)证明:∀x,y∈Rn,记α=(∧x‚y),成立如下的余弦公式:ρ2=|x-y|2=|x|2+|y|2-2|x||y|cosα(10)任意固定ρ,若α≥π2,则由cosα≤0知:max{|x|,|y|}≤ρ(11);若α＜π2,将(10)改写成|x|为未知量的一元二次方程|x|2+(-2|y|cosα)|x|+(|y|2-ρ2)=0由一元二次方程实根存在性条件有|y|≤ρsinα,同理亦有|x|＜ρsinα,于是max{|x|‚|у|}≤ρsinα‚0＜α≤π2(12)由引理1,∀σ={x0,x1,…,xn}∈G,∃i,j使(∧xi‚xj)≥arcsin1√n=αn,故|xi|≤max{|xi|‚|yj|}≤|xi-xj|sinαn≤√n|xi-xj|而当diam(σ)≤ε时,∀k‚|xk|≤|xi|+|xk-xi|≤(√n+1)ε定理1设(6)中F及F0满足:∃μ,当|△x|≤μ时,lim|x|→∞|F(x)-F(x0)||F0(x)|=0‚lim|x|→∞|F(x+△x)||F0(x)|=1(13)其中x∈Rn且F和F0连续,则∃r>0,使区域Ωr={(x0,xT)T∈×Rn,|x|≤r}(14)之外不存在σ∈J3为全标单纯形。证明:记αn=arcsin1√n,不妨设∀σ∈J3,diam(σ)≤μ(否则作坐标变换即可)。∀x,y∈J03,设P(x1)=x,P(x2)=x+△x,|△x|≤μ,于是cos∧(F%(x1)‚F%(x2))=˜F(x1)Τ˜F(x2)|˜F(x1)||˜F(x2)|=|˜F(x2)|˜F(x2)|-˜F(x2)-˜F(x1)˜F(x2)|+(˜F(x1)|˜F(x1)|)Τ(˜F(x2)-˜F(x1)|˜F(x2)|)不难验证‚(13)等价于(记F1=F)lim|p(x1)|→∞|Fi(p(x2))-Fj(p(x1))||Fi(p(x1))|=0‚i=0‚1；j=0‚1即lim|x|→∞|˜F(x2)-˜F(x1)||˜F(x2)|=0。这样lim|x|→∞cos∧(˜F(x1)‚˜F(x2))=1,于是∃r>0,当x1,x2∈Ωr时^(˜F(x1)‚˜F(x2))＜αn(由(13)易知当|x|充分大时(F(x1),F(x2))接近π是不可能的)由此知,若∀σ∈J3且σ∩Ωr=∅,则任给σ的两个顶点x′和x″,有∧(˜F(x′)‚˜F(x″))＜αn,由引理1,σ不是全标单纯形。定理2设F在Rn连续,则∀ε>0,在Rn的某个有界闭区域上,∃δ>0,使当n维全标单纯形τ满足diam(τ)≤δ时,∀x∈τ,|F(x)|≤ε证明:由F在有界闭区域上的一致连续性及引理2即得证。3.为k,1为,2,1.2定理3设F和F0满足定理2的条件,又存在唯一的σ0∈J3使其中一个面τ0是{1}×Rn上的全标单纯形,则:(i)∀ε>0,算法总可在步1达到全标单纯形τm+1使diam(τm+1)≤ε,因此可得到近似解xε。(ii)∀εm→0,则F(p(xεm))→0,(m→∞)(iii)若F在Rn只有有限个零点,则∀εm→0,P(xεm)收敛到其中之一(m→∞)。证明:(i)因为算法经过的单纯形构成一条不重复的路径Γ,且∃r>0使由(14)定义的Ωr之外没有全标单纯形,因此Г含有Ωr之内,又∀k<0,区域Ek,r=Ωr∩[2-k,1]×Rn中只有J3的有限多个单纯形,因此只需有限步Г必须穿过Ek,r的边界。由σ0的唯一性,Г的不重复性及Γ含于Ωr内的性质,Г只能穿越Ωr∩[2-k,1]×Rn这时只要k充分大,由J2的渐细性质必然达到所需要的τm+1。(ii)这是定理2的直接推论。(iii)设x1,x2,…,xn是F在Rn的全部互异的零点。(a)取δ>0,记Oi是Rn中以xi为心半径为δ的球,使Oi∩Oj=∅,(i≠j),则∃μ>0,使当全标单纯形σ∈J3满足diam(σ)≤μ时,有σ∈Μ∪p=1[0‚1]×Οi。事实上,设不然,取μk→0,存在σk:diam(σk)≤μk且σk⊆Μ∪i=1[0‚1]×Ο。因为Ρ(ˉΩr)是Rn中的紧集,又由定理1‚p(σk)⊂p(ˉΩr),故若记ˆxk为σk的重心,则ˆxk必有聚点x*,由定理2可证P(x*)∉{x1,x2,L,xn}P(x*)是F的零点,但显然P(x*)∉{x1,x2,…,xn},矛盾。(b)在J3中,∃k>0使[0,2-k]×Rn内的单纯形直径都小于μ,而Ek,r中只有有限个单纯形,故∃N′,使当m>N′时,算法中的σm⊂[0,2-k]×Rn,又由(a