全標單純形的刻畫

全標單純形的刻畫

1.同倫算法對于連續(xù)映射f：內側的rcn，驗證方程f（x）=0。1.1實現(xiàn)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同標單純形采用整數(shù)標號法。將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)選取適當?shù)腇0: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,確定一個充分小數(shù)ε>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:利用輪移規(guī)則尋找與σ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連續(xù),則?r>0,使區(qū)域Ω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連續(xù),則?ε>0,在Rn的某個有界閉區(qū)域上,?δ>0,使當n維全標單純形τ滿足diam(τ)≤δ時,?x∈τ,|F(x)|≤ε證明:由F在有界閉區(qū)域上的一致連續(xù)性及引理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,區(qū)域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