向量标号转轴算法基本定理

《向量标号转轴算法基本定理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、维普资讯http://www.cqvip.com第3卷第2期应用教学与计算数学学报Vo1．3No．21989年1o月COMM．ONAPPL．MATH．ANDCOMPUTOctober，l98s向量标号转轴算法基本定理王则柯(中山大学计算机科学幕广州)TheFundamentalTheoremofVectorLabellingComplementaryPivotingAlgorithmsWangZeb(D~pgrtmentofComputerScience，ZhomashonUnive，sity，Guangzhou

2、)AbstractThispaperprovesgeometricallythefundamentaltheoremofvectorlabell；ngcomplementarypivotingalgorithms．ItJsshownthatthefeasibilityofthealgo—rithmsisabsoluteone，11omatterwhetherethereisanunderlyingsimplicialtrian—gulationornot．Relateddiscussionsaredevelope

3、d．本文通过几何讨论，建立向量标号转轴算法的基本定理，从而每个从人为完备单形出发的计算序列，都由依次联接的完备单形组成．这一情况并不依赖于空间的单纯剖分．§1．弓I言整数标号和向量标号的单纯同伦算法，是非线性问题数值解的有效方法．其代表是计算R“连续自映射零点或不动点的采用to．1]×R的双屠铷分的Merrill重复开始算法和采用(o，1]×R的渐细剖分的Eaves-Salgal同俭算法．向量标号的算法，还是计算欧氏空间上半连续集值自映射不动点或零点的基本方法(参看[1]或[3])．在本文中，若一点与一给定单形的

4、顶点集的任一真子集仍然组成空间的仿射无关点组．就说该点关于该单形具有正则位置．按照维数关系易知，一点关于一单形的这种位置正则性是一很宽的条件，特别当一点与一单形的所有顶点张成一个高一维的单形时，这种位置正剐性当然成立．整数标号算法的基本做法是；现有n维全标单形的n+1个顶点分别带有0，⋯，垒部n十1种标号．若关于该单形具有正则位置的一点的标号为i，就用它取代原来标号为i的本文10年4月1日收到．’本支为中山学高等学术研究牢心基金会资助课题．维普资讯http://www.cqvip.com应用数学与计算数学学报3卷

5、顶点．得到一个新的维全标单形．向量标号算法的基本做法是：给定§3所说的维完备单形和关于该单形具有正则位置的任意一点，按照§5字典式取主转轴运算规则，该点唯一地取代原单形的一个顶点．得到一个新的n维完备单形．这个性质是字典式取主转轴算法本身所具有的，并不取决于空间是否进行了单纯剖分．本文从几何的方面完成这一讨论．得到若干结果，着重揭示所建立的命题在向量标号转轴算法中的基本重要性．§2．几何引理假定读者熟悉欧氏空间凸集的单纯剖分的概念，我们沿用[3，§1．2]的符号．维单形的m-1维面特称界面．设f=‘6。，⋯，6>

6、是维单形．b不在f所决定的超平面上．那末<6，6。，⋯，6>是+1维单形，简记作<6，r>设毒是置中一个单形．记‘=<，⋯，-。，Ⅱ卅．⋯，口>，则tY~-：-{or；=O，⋯，"}是的界面组．这时，若aCR，定义指数算子oind：口—}{0，1}如下：若d和d位于置的以o't所在的超平面为边界的同一个开半空间，则ind(a)=1：否则，ind(t)=0．从几何上看，当且仅当对所有，寺f，d和的凸包collv{Q，}和tyt之交都空时．有ind(t)=】．例如图1中．ty2被conv{G，o"1}

7、部分复盖，所以ind。(2)=o，而ind()一1和ind(1)=1则是因为和l并不被这样部分复盖．由指数算子的上述几何意义．立得：。引理2．1设盯=<0。．⋯，Ⅱ>是露“中一单形，d∈R．则维单形组G={<Ⅱ．t>：ind。()=1)田1是口和的凸包COHV{Ⅱ．}的一个单纯剖分，固2例如．图2中{<口，l>，<口，ty0>}是conv{tJ．}的单纯剖分，{<6．。>}是ccnv{6，的单纯剖分．{，}剖分COIIV(C，．{，，}剖分eonvld，

8、}，{}剖分COllV／e，}．在后三个例子中，维普资讯http://www.cqvip.com2期向量标号转轴算法基本定理conv{e．孑}=conv{d．}~COI)V{e，_盯}一吾，在最后的例子中还有{<日，>}={0-}．注意．单纯剖分G的元素数目不超过n+1．§3．完备单形在本节中，给定连续映射，：置一置“．对任何正数e，记J(e)一{(}，⋯．PJ