（计算数学专业论文）自适应无网格方法及路径规划的新算法.pdf

苏州大学学位论文使用授权声明 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属在年月解密后适用本规定。 非涉密论文口 论文作者签名： 芝罐 e l期： 竺2 1 ：兰! 笙 导师签名：要系 日 期：童! 丝! 壁：z 生 自适应无网格方法及路径规划的新算法 摘要 自适应无网格方法及路径规划的新算法 摘要 无网格方法( m e s h f r e em e t h o d s ) 是近年来出现的新兴的数值方法，得到众多学者 广泛的重视并取得了快速的发展。自适应无网格方法是无网格方法的一个重要的研究 方向。我们介绍了一种新的自适应无网格方法，并用该方法进行了悬臂梁和圆孔板问 题的数值模拟。全局路径规划是机器人控制技术研究中的一个重要问题。我们构造了 移动机器人全局路径规划的一种新算法，并进行了大量的数值实验，验证了方法的有 效性。本文的主要内容如下： 1 简述了现有的自适应无网格方法。基于两个不同支撑域大小的自适应无网格 误差估计及利用v o r o n o i 图进行新节点插入的技巧，构造了一种新的自适应 无网格方法。 2 将这种新的自适应无网格技巧分别与移动最小二乘法和径向点插值法结合， 形成了自适应m l s 无网格方法及自适应r p i m 无网格方法。并分别应用于悬臂 梁问题及圆孔板问题的数值模拟，均取得了很好的计算结果，验证了算法的 有效性。 3 分析了传统的全局路径规划方法，提出了移动机器人全局路径规划的一种全 新方法一盲人摸路算法。给出了该算法的详细描述过程并证明了算法的收 敛性。与传统的全局路径规划方法相比，该方法在进行路径规划之前，不需 要对障碍环境进行特殊的简化处理。算法理论浅显，计算简单，信息存储量 小，能够快速搜索出无碰路径。最后通过大量数值算例说明了算法的正确性 和有效性。 最后给出了结论及未来工作的展望。 关键词：无网格方法自适应无网格方法全局路径规划盲人摸路算法 作者：王永兴 指导老师：丁睿 m e t h o di so n eo fa r li m p o r t a n td i r e c t i o no fm e s h f r e em e t h o d an e w a d a p t i v em e s h f r e e m e t h o di si n t r o d u c e di nt h i sp a p e ra n da p p l i e dt os o l v et h ec l a s s i c a lp r o b l e m so fc a n t i l e v e r b e a ma n dp l a t ew i t hac i r c l eh o l e g l o b a lp a t hp l a n n i n gi sac r i t i c a lp r o b l e mi nt h ea r e ao f r o b o tc o n t r o lt e c h n i q u e w ec o n s t r u c taw h o l en e wa l g o r i t h mf o rg l o b a lp a t hp l a n n i n g p r o b l e m ，a n dr e a l i z e dal o to fn u m e r i c a le x p e r i m e n t s i tr e v e a l s t h ee f f i c i e n c yo ft h i s m e t h o d t h em a i nc o n t e n t si nt h i sp a p e ra r ea sb e l l o w ： 1 i tg i v e sas i m p l yd e s c r i p t i o no fp r e s e n ta d a p t i v em e s h f r e em e t h o d s b a s e do nt h e t e c h n i q u eo ft h ee r r o re s t i m a t ea td i f f e r e n ts u p p o r td o m a i n s ，a n dt h en e w n o d e si n s e r t b yt h ev o r o n o ig r a p h ，an e wa d a p t i v em e s h f r e em e t h o di si n t r o d u c e d 2 b yc o u p l i n gt h ea d a p t i v et e c h n i q u ew i t ht h em l sa n dr p i mm e s h f r e em e t h o d ，i t y i e l d st h ea d a p t i v em l sa n dr p i mm e s h f r e em e t h o d s a p p l y i n gt h e s et w om e t h o d s t os o l v et h ec l a s s i c a lp r o b l e m so fc a n t i l e v e rb e a ma n dp l a t ew i t hac i r c l eh o l e r e s p e c t i v e l y ，t h er e s u l t sh a v eag o o da g r e e m e n tw i t ht h ee x a c ts o l u t i o n ，a n dv a l i d a t e t h i sn e w a l g o r i t h m 3 i ta n a l y z e dt h ec l a s s i cg l o b a lp a t hp l a n n i n gm e t h o d si nt h ea r e ao fr o b o tc o n t r o l t e c h n i q u e i tp r e s e n t san e wa l g o r i t h m ，n a m e l yt h eb l i n dg r o p i n ga l g o r i t h m ，f o r m o b i l er o b o t sc o l l i s i o na v o i d a n c ep l a n n i n g ad e t a i l e da c c o u n to ft h ea l g o r i t h m p r o c e s si sg i v e na n dap r o o fh a sb e e np r e s e n t e df o rt h ec o n v e r g e n c e c o m p a r e d w i t l l t h ec l a s s i c a lg l o b a lp a t hp l a n n i n gm e t h o d s ，t h eo b s t a c l ee n v i r o n m e n td o e s n tn e e dt o b es i m p l i f i e db e f o r ep l a n n i n g t h et h e o r yo ft h i sa l g o r i t h mi ss i m p l e ，a n dt h e c a l c u l a t i o ni se a s y i ti so n l yn e e das m a l ls t o r a g eo fi n f o r m a t i o n af r e ep a t hc o u l d b ef o u n do u tq u i c k l y a tl a s t ，s o m en u m e r i c a le x p e r i m e n tr e s u l t sh a v ej u s t i f i e da n d v a l i d a t e dt h ea l g o r i t h m k e yw o r d s ：m e s h f r e em e t h o d ；a d a p t i v em e s h f r e em e t h o d ；g l o b a lp a t hp l a n n i n g ；t h eb l i n d g r o p i n ga l g o r i t h m w r i t t e n b y ：w a n gy o n g x i n g s u p e r v i s e db y ：d i n gr u i i i 目录 第一章绪论1 1 1 引言1 1 2 论文的主要研究内容3 第二章自适应无网格方法5 2 1 自适应无网格方法简介5 2 2v o r o n o i 图简介7 2 3 基于一种新的误差估计及节点插入的自适应无网格方法8 第三章悬臂梁问题的自适应无网格数值模拟1 0 3 1 引言1 0 3 2 悬臂梁问题的自适应最d , - 乘g a l e r k i n 无网格方法1 0 3 2 1 悬臂梁问题描述1 0 3 2 2 移动最小二乘( m o v i n gl e a s ts q u a r e ，m l s ) 1 1 3 2 3g a l e r k i n 方法1 5 3 2 4 自适应移动最小二乘g a l e r k i n 无网格方法1 7 3 3 数值算例1 8 3 4 结论2 2 第四章圆孔板问题的自适应无网格数值模拟2 3 4 1 引言2 3 4 2 圆孔板问题的自适应径向点插值g a l e r k i n 无网格方法2 3 4 2 1 圆孔板问题描述2 3 4 2 2 径向点插值方法( r a d i a lp o i n ti n t e r p o l a t i o nm e t h o d ，r p i m ) 2 4 4 2 3 自适应径向点插值g a l e r k i n 无网格方法2 7 4 3 数值算例2 9 4 4 结论3 6 第五章移动机器人全局路径规划的盲人摸路算法3 7 5 1 引言3 7 5 2 盲人摸路算法3 8 5 2 1 算法思路3 8 5 2 2 算法过程3 8 5 2 3 程序步骤4 0 5 3 收敛性证明4 1 5 4 数值算例4 2 5 5 算法改进及结论4 5 4 6 4 7 4 9 5 0 自适应无网格方法及路径规划的新算法 第一章绪论 第一章绪论 1 1 前言 物理、力学及工程等众多自然科学领域中存在大量的难以采用解析方法解决的问 题。这就驱使人们研究新的数值方法。上世纪中叶，出现了有限单元法( f i n i t e e l e m e n tm e t h o d ，f e m ) ，伴随计算机技术的快速发展，有限元法作为工程分析的有效 方法，在数学理论、方法研究、计算机程序开发以及应用领域的开拓等方面均取得了 很大的发展，目前有限元已经成为理论基础完善、应用最为广泛的数值方法之一。 尽管有限元取得了巨大的成功，但对一些重要问题还存在困难，比如在大变形分 析问题中，网格畸变即当单元被很大程度的扭曲或挤压时，使得有限元求解精度出现 大幅下降；在沿复杂及不确定路径增长的裂缝问题中，由于边界拓扑关系的变化使得 有限元法处理起来仍然相当困难。究其原因，这主要是由于有限元依赖于有序的单元 连接。这些困难的传统解决方法是在模拟过程中不断重新划分网格。为了有效解决这 些问题，出现了自适应有限元方法( a d a p t i v ef e m ，a f e m ) 。自适应技巧的实质就是按 照某种准则，对于原始网格下的计算结果进行筛选，对于结果不大满意的节点进行局 部加密。再重新计算，直到达到要求为止。该技巧中有两个关键点，即选择准则及如 何进行加密。得益于有限元方法成熟的理论分析及方便的网格加密方式，使得自适应 有限元方法能够在不极大的增加计算规模的前提下提高问题的计算精度。 从2 0 世纪7 0 年代开始，特别是最近十多年，无网格法( m e s h f r e em e t h o d s ) 受到了 广泛重视并且得到了快速发展，先后出现了各种类型的无网格法，它们的共同点就是 近似函数不依赖节点之间的有序拓扑连接而通过节点信息直接建立起来。对于用传统 有限元法求解较困难的问题，有着独到的优势，已成为一个非常活跃的研究方向h 吲。 无网格法又称为无单元法，其基本思想是用一系列的节点代替有限元法中的单元，采 用一种与权函数( 或核函数) 相关的近似，使整个区域上的节点可以影响研究对象上任 何一点的力学特性乜1 。它与有限元法的主要区别是：近似函数的构造不借助于网格， 它是基于函数逼近而非插值近似。目前已经提出多种无网格法：光滑粒子法( s m o o t h e d p a r t i c l eh y d r o d y n a m i c ，s p h ) 口1 、h p 无网格云团法( h p m e s h f r e ec l o u d sm e t h o d ) r 3 、 第一章绪论自适应无网格方法及路径规划的新算法 无网格伽辽金法( t h ee l e m e n t f r e eg a l e r k i nm e t h o d ，e f g ) 嵋3 、漫射元法( d i f f u s e e l e m e n tm e t h o d ，d e m ) 、有限点法( t h ef i n i t ep o i n tm e t h o d ，f p m ) 1 、局部伽辽金 无网格法( m e s h f r e el o c a lp e t r o v g a l e r k i n ，m l p g ) 、局部边界积分法( 1 0 c a l b o u n d a r yi n t e g r a le q u a t i o nm e t h o d ，l b i e ) 盯3 等。这些方法的主要区别在于所使用 的试探函数和微分方程等效形式不同。目前用来构造近似函数的方法主要有移动最小 二乘近似( m o v i n gl e a s ts q u a r e ，m l s ) 、重构核函数近似( r e p r o d u c i n gk e r n e l p a r t i c l em e t h o d ，r k p m ) 随3 、单位分解法( p a r t i c l eo fu n i t y ，p u m ) 、径向基函数 ( r a d i a lb a s i sf u n c t i o n s ，r b f ) 1 、点插值法( p o i n ti n t e r p o l a t i o nm e t h o d ，i p m ) 等。常用的等效积分形式有：g a l e r k i n 法、配点法、最& - - 乘法、p e t r o v g a l e r k i n 法等。文献 1 0 对这些无网格法及其特点进行了总结。通过与有限差分法、有限元法 和边界元法的比较，无网格法具有以下优点： ( 1 ) 无网格法的近似函数采用区域逼近，不依赖于网格，减少了因网格畸变而 引起的困难； ( 2 ) 无网格法基函数的选择较自由，针对不同问题可以选择与其适应的基函数， 因此能够用于分析各类具有高梯度、奇异性等特殊性质的应用问题； ( 3 ) 权函数采用紧支函数时，无网格法的系数矩阵也和有限元法一样具有带状 稀疏的特点，可以用于求解大型科学与工程问题； ( 4 ) 无网格法的前处理只要节点位置信息，不用网格信息，容易分析复杂三维 结构。 无网格方法虽然有自身的一些优点，比如像不依赖与网格剖分，对大变形问题的 有效解答等。但仍然存在着天然的缺点，即其计算量随着问题的规模增大而迅速增加。 这样就限制了无网格方法的使用，特别是对三维问题的解答。为了解决这一难题，无 网格也引入了自适应算法，形成了近些年的一个热门研究课题自适应无网格方 法。自适应方法是专门为了克服计算量过大的问题而提出来的，由于实际的大规模问 题往往是由局部的复杂性而引起的。所以类似于自适应有限元方法，局部细化的办法 是个很好的选择。这便形成了自适应无网格方法。然而自适应无网格方法也有两个 极大的困难，即：( 1 ) 方法的理论还远未成熟，因而大多数无网格方法都没有相应的 误差估计结果，所以很难给出一种适当的自适应局部加密的判断准则；( 2 ) 无网格节 2 自适应无网格方法及路径规划的新算法 第一章绪论 点的局部加密如何实现。不同于有限元中方便的网格加密方式，无网格节点的局部是 分布不规则的其它节点。如果需要加密，如何选择新的插入节点是一难题。 路径规划是机器人控制技术研究中的一个重要问题。路径规划是指给定环境障碍 条件，以及起始和目标的位置，要求选择一条从起始点到目标点的路径，使运动物体 ( 机器人) 能安全、无碰撞地通过所有的障碍。这种自主地躲避障碍并完成作业任务的 机器人是机器人研究的一个重要内容。移动机器人的路径规划方法可分为基于地图的 全局路径规划和基于传感器的局部路径规划。全局路径规划，作业环境的全部信息已 知，又称静态或离线路径规划；局部路径规划，作业环境信息全部未知或部分未知， 又称动态或在线路径规划。全局路径规划和局部路径规划并没有本质区别。局部路径 规划只是环境考虑的更复杂一些，即环境是动态的。很多适用于全局路径规划的方法 经过改进都可以用于局部路径规划；而适用于局部路径规划的方法都可以适用于全局 路径规划。全局路径规划方法主要包括栅格法n 1 1 ，可视图法n 2 。1 副，自由空间法n 1 j ，拓 扑法n 钔，神经网络法n 5 3 等。局部路径规划方法主要包括人工势场法n ，模糊逻辑算法 口，神经网络法n6 1 ，遗传算法n 6 3 等。以上算法各有其优缺点。栅格法中，栅格大小直 接影响环境信息存储量大小和规划时间长短。栅格划分大了，环境信息存储量小，规 划时间短，但分辨率下降，在密集环境下发现路径的能力减弱。栅格划分小了，环境 分辨率高，在密集环境下发现路径的能力强，但环境信息存储量大，规划时间长；可 视图法能够搜索出最短路径，但对障碍复杂的环境，建立可视图计算量比较大；自由 空间法的缺点也在于计算复杂度随环境复杂度的增加而急剧增大，且得不到最短路 径；拓扑法通常不需要机器人的准确位置，对于位置误差也就有了更好的鲁棒性，缺 点是建立拓扑网络的过程相当复杂，特别在增加障碍物时如何有效地修正已经存在的 拓扑网是有待解决的问题。 1 2 论文的主要研究内容 本文详细介绍了一种自适应无网格技巧，给出了误差判定准则及局部节点的加密 方法。并与最为常见的两种无网格方法结合，构造了自适应无网格方法。采用该方法 对悬臂梁问题和圆孔板问题进行了数值模拟。另外文中还研究了机器人控制技术中的 全局路径规划问题。给出了全局路径规划的一种新算法，实现了大量算例。全文结构 3 第一章绪论 自适应无网格方法及路径规划的新算法 如f ： 1 、第二章详细叙述了自适应无网格方法的发展。简单介绍v o r o n o i 图的概念。着 重描述了一种新的自适应无网格方法，即基于不同支撑域大小的误差估计以及利用 v o r o n o i 图插入局部节点的自适应无网格方法。 2 、第三章论述了悬臂梁问题的自适应移动最d - - 乘g a l e r k i n 无网格方法。介绍了 基函数形成的移动最d - 乘方法和控制方程离散的g a l e r k i n 方法。给出了自适应移动 最小二乘g a l e r k i n 无网格方法的实现步骤。最后实现了数值计算，并分析了计算结果。 3 、第四章论述了圆孔板问题的自适应径向点插值g a l e r k i n 无网格方法。介绍了基 函数形成的径向点插值方法。给出了自适应径向点插值g a l e r k i n 无网格方法的实现步 骤。最后给出了计算的可视化结果，并且分析了算法解答该问题的有效性。通过数值 模拟，分析了算法的效果，说明白适应技巧中的误差判定准则以及v o r o n o i 图方式的 局部节点生成规则是有效的。 4 、第五章介绍了移动机器人全局路径规划的一种新算法。分析了传统的全局路 径规划方法的缺点，提出了移动机器人全局路径规划的一种新方法盲人摸路算 法。给出了该算法的详细描述过程并证明了算法的收敛性。与传统的全局路径规划方 法相比，该方法在进行路径规划之前，不需要对障碍环境进行特殊的简化处理。算法 理论浅显，计算简单，信息存储量小，能够快速搜索出无碰路径。最后通过大量数值 算例说明了算法的正确性和有效性。 最后给出了结论及未来工作的展望。 本文内容得到了国家自然科学基金项目( n o 1 0 2 0 1 0 2 6 ，n o 1 0 6 7 2 1 1 1 ) 的资助， 作者在此表示衷心的感谢1 4 自适应无网格方法及路径规划的新算法 第二章自适应无网格方法 第二章自适应无网格方法 2 1 自适应无网格方法简介 用某种数值方法求解偏微分方程边值问题，得到相应问题的近似解。为满足科学 研究和工程设计的需要，对近似解还常有一定的要求。例如，分析计算对象的结构形 态、安全特征、位移与应力分布等要有一定的精度。对在某些临界点的位移、应力及 应力强度因子的计算度可能要求更高。于是，仅仅在初始网格上进行一次计算往往是 不够的。我们的计算过程还应包括： ( 1 ) 对计算结果进行估计，以便知道该结果是否满足需要； ( 2 ) 根据上述估计控制计算过程，以最小的代价得到满足要求的结果； ( 3 ) 通过后验过程，从计算结果获得所需要的高精度数据。 换句话说，计算不是一次完成。如果解不能达到要求，还需要在更精细的网格上 进行多次数值计算。自适应方法最早被应用到有限元方法中。b a b u s k a 教授先后提出 了h 型、p p d 及h _ p 型三种类型的自适应有限元方法口7 1 。所谓h 型方法是指有限元单元的 阶( 即作为单元上基函数的分片多项式的阶) p 是固定的，仅通过细分网格即减d , h 来达到提高精度的目的。所s ”h p 型方法则保持固定的网格，即h 不变，而提高作为基函 数的分片多项式的次数p 以改善计算结果。h p 型方法则是二者的结合。为了提高近似 解的精度，或着需要某个高精度的数据，通常并不需要把网格的所有单元一致的细分， 也不需要将所有单元的阶提高，而只需局部的细分单元或提高单元的阶。 那么应该细分哪些单元或提高哪些单元的阶呢? 自然，应该细分近似解误差太大 的那些单元，或者提高那些误差较大的单元上近似多项式的阶。于是我们需要作后验 误差估计。利用初始的或上一步的计算结果进行后验误差估计，再根据这些估计去细 分网格或改变逼近结构，使之按某种标准达到最优，这便是自适应算法。由于有限元 方法的数学理论很成熟，相关的后验误差估计比较完备。此外有限元网格细化实现容 易，因而自适应有限元方法得到了极大的发展。是大规模科学计算和高精度科学计算 中常用的数值方法。 正如绪论中论述的，无网格方法由于其排点灵活，且在计算中可根据需要插入结 5 第二章自适应无网格方法自适应无网格方法及路径规划的新算法 点的特点，促成了自适应无网格方法的发展。其基本思想是将初始节点排布得较为稀 疏，得出初步结果后根据位移或应变梯度、应变能密度的变化，确定需要做进一步分 析以提高精确度的区域，在这些区域插入较多的结点重新计算，以此类推，直到计算 结果满足要求。此方法既保证了计算的精确度，又减少了运算量，可看作有限元方法 中h 方法在无网格领域的推广。 然而新兴的无网格方法种类繁多，且相关的数学理论不完善，特别是误差估计很 少。此外由于无网格方法没有网格只有节点，因而在进行局部节点加密时如何选择新 的插入节点。这两个问题都是自适应无网格方法必需要解决的。目前关于自适应无网 格方法的研究有了一定的进展。d u a r t e 利用了h - p - 云h 3 自适应无网格方法，c h u n g 和 b e l y t s c h k o n 踟采用有限元影射技术分析e f g m 误差的自适应无网格方法，l i u n 町采用背 景网格内能量误差来进行误差估计的自适应无网格方法，c o m b e 等人心们提出了计算位 移的二阶导数和应变能密度( s t r a i ne n e r g yd e n s i t y ，s e d ) 的自适应无网格方法等。 误差估计的方法大致上可分为两大类，一类是基于局部区域上的误差估计，另一 类是基于节点的误差估计。基于区域的误差估计是指在初始剖分节点上进行计算完成 以后，考察某一区域上的误差，进而判断是否在该区域中插入新的节点。这里的“某 一区域”可以是支撑域，也可以是背景网格。例如文献 4 的h - p 云方法及文献 1 9 采用背景网格就分别是采用了这两种区域进行误差估计。图2 1 是用h _ p 云团进行误差 估计，而图2 2 5 1 j 用背景网格行误差估计。值得注意的是，基于区域上的误差估计的 后验误差计算量比较大，基于节点的误差估计后验误差计算量相对较小。在2 3 节我 们将详细介绍一种基于不同支撑域的节点型误差估计的自适应无网格方法。 另外，在选择插入新的节点时，哪些点要作为计算点来判别是否需要插入到域节 点当中呢? 关键就是将欲插入的这些点插入到原来的域节点中后，要保证节点局部的 均匀性，既不能使有些节点太近，又不能让有些节点太远。要使得密集的节点逐渐的 过渡到稀疏的节点。目前插入新节点的主要思想是利用有限元网格细化的思想，计算 时只用到节点，而插入节点时又用到网格剖分n 1 。舯1 来细化网格、选取节点。文献 2 2 利用以下节2 2 介绍的v o r o n o i 图来做插入新的节点是一种比较新颖的思路。 6 自适应无网格方法及路径规划的新算法 第二章自适应无网格方法 ：。 。+ 。一：。 f_， - j ：j 1 1 ! 一j - 。，：o - 0j ，- ： _ 1 一一0 i - ： - ：。 。：t ：?t ；。j 一： t ，_ 黼 - -0 。：r ：。彤蠢：善 磺爵 豢 蠢 鬻至 ：- ：+ 江势臣馘： 麟 j 。，：旁聋岁。 一i i? 搿：囊 j ，。i | 耪； !蕊：； i t ： 7 ：i j j ：i 曩 1 ：o 囊鬻鬈：0 - 。“ ，j ! ： ： 。，q ：1 i ! ：0 7 坨：撼! ：j ： ；= = 1 0 豫。 。： ：? 一：j ：o - ： ：o 0 ：。-。o ： - j _ 。： 。： 图2 1 利用h - p 云团进行误差估计图2 2 利用背景网格行误差估计 2 2v o r o n o i 图简介口1 1 v o r o n o i 图，又叫泰森多边形或d i r i c h l e t 图，它是一组由连接两邻点直线的垂直 平分线组成的多个连续多边形。 分布在平面上的不同的点，按照最邻近原则划分平面，每个点与它的最近邻区域 相关联，由此便形成j v o r o n o i 多边形。如图2 3 所示为某一组节点的v o r o n o i 图。其 中“+ ”表示平面上分布的节点，每个多边形区域中仅包含一个节点，且多边形中的 其它任意点到该节点的距离最小，这个多边形就是v o r o n o i 多边形。v o r o n o i 多边形的 顶点称为v o r o n o i 节点。 图2 3v o r o n o i 图 7 第二章自适应无网格方法 自适应无网格方法及路径规划的新算法 对于任意给定的一组无网格节点，我们可利用m a t l a b 函数库中的 v ，c = v o r o n o i n ( x ( ：) y ( ：) ) 函数方便的求出其v o r o n o i 节点。在该函数中，v o r o n o i 节点保存在返回值v 中。例如，随机取一组点。如图2 3 所示。 x = 0 6 1 5 4 3 ，0 7 9 1 9 4 ，0 9 2 1 8 1 ，0 7 3 8 2 1 ，0 1 7 6 2 7 ，0 4 0 5 7 1 ，0 9 3 5 4 7 0 9 1 6 9 ，0 4 1 0 2 7 ，0 8 9 3 6 5 ) ， y = 0 9 5 0 1 3 ，0 2 3 11 4 ，0 6 0 6 8 4 ，0 4 8 5 9 8 ，0 8 9 1 3 ，0 7 6 2 1 ，0 4 5 6 4 70 0 1 8 5 0 4 ， 0 8 2 1 4 1 ，0 4 4 4 7 ) 调用v o r o n o i 函数，可知其v o r o n o i 节点为： v x = 一1 2 0 7 3 ，- 0 1 1 1 7 ，0 2 3 2 7 4 ，1 1 1 3 4 ，0 7 7 8 5 ，0 8 0 1 8 3 ，0 2 5 2 8 6 0 7 2 7 11 ，0 7 0 8 9 7 ，0 2 8 1 0 2 ，0 3 6 3 5 9 ，0 5 2 8 3 9 ，0 5 3 8 3 5 ， v y = 一1 4 1 2 2 ，一0 2 3 7 4 4 ，1 0 3 8 1 ，0 3 7 0 0 4 ，0 5 8 0 1 5 ，0 2 7 6 9 8 ，0 2 6 3 7 2 0 7 11 0 6 ，0 6 4 2 4 9 ，0 9 6 2 2 6 ，0 7 8 8 9 1 ，0 8 9 2 6 7 ，0 8 3 5 3 2 其中，v x ，v y 分别表示所有v o r o n o i 节点的横坐标向量和列坐标向量。 在自适应无网格方法中，调用v o r o n o i 函数，形成当前节点的v o r o n o i 图。每个 v o r o n o i 多边形包含一个节点，且多边形中的所有点到它所包含的节点的距离最小。 除去v o r o n o i 多边形节点中落在计算区域以外的节点，剩余的节点作为计算点，考察 其误差，进而判断它是否作为新的节点插入到原来的无网格节点集当中。 2 3 基于一种新的误差估计及节点插入的自适应无网格方法陇1 首先在某一确定的支撑域半径，下，利用某种无网格方法计算出位移及应力，然 后再将支撑域半径扩大为2 ，重新计算2 ，时的位移及应力。如果计算工作量过大， 也可采用支撑域半径为，时的计算结果插值出2 ，时的位移及应力。对于已给定的计算 点牙，考察该点的某一相关量a ( 2 ) ( 比如应力矩阵的特征值或解函数) 在两种不同支 撑域半径下的误差虿( i ) 。 虿( i ) = 矽j ( i ) 嵋一? ( i ) 砰， ( 2 1 ) 其中虿( 冤) 为所估计的误差，彤与卯7 分别为第，个节点处，支撑域半径分别为，与2 ， 时所对应的基函数，k 为上一步所求的第，个节点所对应的解的一个相关量，衅是 8 自适应无网格方法及路径规划的新算法第二章自适应无网格方法 用支撑域半径为2 ，的基函数和上一步计算出各个物理量所求出的量。具体计算可参 照第三章或第四章的( 3 3 8 ) 式或( 4 2 9 ) 式。 基于两个不同支撑域大小的误差估计原理可由图2 4 简单解释。一般来说，支撑 域越大，基函数就越光滑，那么对于域函数变化较大的区域的逼近效果就越差。因此， 误差大的区域就可以由两个支撑域不同的基函数所逼近的解反映出来。这就是基于节 点的误差估计的基本原理。 图2 4 支撑域分别为，与2 ，两个基函数 对于某一计算点i ，一旦利用( 2 1 ) 式估计出误差，那么就可以在给定误差限e 的 情况下，确定该点是否作为新的节点插入到原节点当中。具体自适应无网格方法的计 算步骤可参照节3 2 4 或4 2 3 。 理论上讲，任何一种无网格方法都可以做自适应计算，具体哪一种方法做自适应 无网格计算较有优势，目前尚未见到相关讨论。但是目前发表的自适应无网格方法中， r k p m 、h - p 云团法较多见。本文选用移动最小二乘方法和径向点插值方法构造基函数， 选用g a l e r k i n 方法离散控制方程来做自适应计算，取得了很好的效果。 9 第三章悬臂梁问题的自适应无网格数值模拟 自适应无网格方法及路径规划的新算法 第三章悬臂梁问题的自适应无网格数值模拟 3 1 引言 悬臂梁是指一端为不产生轴向、垂直位移和转动的固定支座，另一端为自由端( 可 以产生平行于轴向和垂直于轴向的力) 的梁。在工程力学受力分析中，悬臂梁是一 种典型的简化模型，大部分实际工程受力部件都可以简化为悬臂梁。由于悬臂梁问题 存在精确解，所以它经常被用来验证各种数值方法。 本章我们主要介绍了形函数采用移动最小二乘的自适应无网格方法，并实现了悬 臂梁问题自适应无网格方法的数值模拟。 3 2 悬臂梁问题的自适应最, j 、- - 乘g a ie r kin 无网格方法 3 2 1 悬臂梁问题描述3 如图3 1 所示的悬臂梁问题，左端固定，右边的自由端受到均布力。其控制方程 为： l r d l k + 云= 0 ， ( 3 1 ) 其中厅= 鬈) 为位移，云= 乏) 为体力。 l = 旦。 缸 a 0 护抛嫦t 肚截 aai l u 砂反j 10 ，、 1 一y u 一 2 ，由材料的性质决定。e 为杨氏模量，y 为泊松比。 左端满足位移边界条件：“i 脚= 0 ，v i 删= 0 ；右端满足力的边晁条件： 仃秒l 。= 尸。 1 0 自适应无阏格方法及路径规划的新算法第三章悬臂梁问题的自适应无网格数值模拟 x 图3 1 悬臂梁 悬臂梁问题位移的精确解如下： 出川= 一球班艄删卜孚 ， 2 ， 吣川= 6 - 笔1 3 0 y 2 ( l - x ，+ ( 4 5 0d 4 2 x + ( 3 l - x ) x 2 3 ， 应力的精确解如下： 仃。( x ，y ) ：一p ( _ l - x ) y ， ( 3 4 ) 盯w = 0 ， ( 3 5 ) 吲训) 上2 i 匠l 4 y 2 ( 3 6 ) 下面我们讨论自适应无网格方法，其中基函数采用移动最小二乘方法，方程的离 散形式采用g a l e r k i n 方法。由此形成的自适应无网格方法称作自适应移动最小二乘 g a l e r k i n 无网格方法( a d a p t i v em o v i n gl e a s ts q u a r eg a l e r k i nm e s h f r e em e t h o d ) ， 现在分别介绍移动最小二乘方法和g e r l e r k i n 方法，然后结合第二章描述的自适应技 巧给出方法的实现步骤。 3 2 2 移动最小二乘( m o v i n gl e a s ts q u a r e ，m l s ) 嘞1 考虑个定义在域q cr 2 上的函数z f ( i ) ，在i 点i 拘m l s 逼近为： “6 ( i ) = p ，( i ) 口，( i ) = 芦7 ( i ) 历( 元) ， ( 3 7 ) 第三章悬臂梁问题的自适应无网格数值模拟自适应无网格方法及路径规划的新算法 其中多( i ) 为定义在笛卡尔坐标空间i r = 【x ，j ， 中的基函数，脚是基函数的个数。通常 j ( i ) 是由p a s c a l = 角构造的多项式基函数，由此保证它具有完备性。在一些特殊情 况下，可以加入一些特殊的基函数项来改进m l s 的性能。这里为了方便叙述我们只讨 论具有多项式基的情况。 在( 3 7 ) 中，注意到系数云( i ) 是计算点i 的函数。历( i ) 可以由以下加权泛函的极 小化得到： j = 旷 一训p r ( i 。) 五( i ) 一“，】2 ， ( 3 8 ) 其中，2n 乇t g ni 的支撑域中节点的个数，权函数矿( 贾一i ，) 0 ，甜，为节点i = i ，处的 节点参数。( 3 8 ) 是一个由未知的节点参数及逼近形式构造的加权误差平方和的残量 表达式。由于m l s 逼近形式中的节点数聆一般大于聊，所以逼近函数“( i ) 不通过节点， 如图3 2 所示： 0 雨 图3 2m l s 中的逼近函数“( i ) 和节点参数“， 令，对云( j ) 导数为零可得： 么( i ) 面( i ) = b ( i ) 痧， ( 3 9 ) 其中痧为支撑域中节点参数所组成的向量，即： ( 3 1 0 ) 自适应无网格方法及路径规划的新算法 第三章悬臂粱问题的自适应无网格数值模拟 彳( 元) = 旷( i i ，) 卢7 。( i 。场( i f ) ， ( 3 1 1 ) i = l 对于二维情形，如果取m = 3 ，则么( i ) 为一3 阶的对称矩阵，可以显式的写成： a 3 。3 ( i ) = 旷( i i ，) p7 1 ( i ，殄( i ，) i = l 矩阵b ( i ) 为： 解( 3 9 ) 得： = 矿c j i ， 妾曼。x 委 y y 。 + 旷c i i ：， = 矿( j i ) h x ? 。l + 旷( i i ：) l y lx l y li jl + + 旷c 贾一曼。， 妾耋。凄， 矿一矿y ，矿 j = lt = ll = l t 矿z ? 矿t y ，矿 i = l i = lt = l ” ”丹 z y ，矿x ，y ，彬y ? 矿 ，= lj = lf = l b。cj，=矿cii。，妾，旷cii：，i1 哌c i i 。，i 1 1 将上式带回( 3 7 ) 得： 1 呢l = ix 。x 2 1 1y 1 y 2 w e y 。既l 历( i ) = 彳( i ) 一1b ( i ) 痧 ( 3 1 2 ) ( 3 1 3 ) ( 3 1 4 ) u h ( i ) = 谚( i ) “，= 面7 ( i ) 衫， ( 3 1 5 ) ，= l 其中面( i ) 为计算点i 对应的m l s 形函数向量，支撑域内节点数为刀。面( 元) 可写成： 面7 ( i ) = 移，( i ) ，矽：( i ) 九( i ) ) ，。= 卢7 ( i ) 彳( 孑) 一1 b ( i ) ， ( 3 1 6 ) 1 3 第三章悬臂梁问题的自适应无网格数值模拟 自适应无网格方法及路径规划的新算法 第i 个节点的形函数的表达式为： 痧( i ) = p ，( i ) ( 4 ( 矿b ( i ) ) = 多7 ( i ) 彳( 矿b ( 砩 ( 3 1 7 ) j = l 根据m l s 形函数的定义可知，只要选择适当的权函数，m l s 形函数可以在整个定义 域内保持连续性。下边简要介绍一下权函数的选取要求以及几种常见的权函数。 ( 3 1 6 ) 式表明，m l s 形函数的光滑性依赖于多( i ) 及矩阵彳( 章) 和b ( i ) ，矩阵彳( i ) 和 b ( i ) 的光滑性直接依赖于权函数的选取，因此权函数对m l s 逼近的性能有重要的影响 作用。从目前的研究情况来看，旷( i i ，) 总是要求满x 2 n - f 性质： ( 1 ) 在支撑域内矿( i i ) 0 ； ( 2 ) 在支撑域外矿 一i ，) = 0 ； ( 3 ) 从计算点i 向外矿( 舅一置) 单调递减； ( 4 ) 矿( i i ，) 要求充分光滑，特别是在支撑域内。 最后一条保证了当节点进出支撑域时的光滑性，从而保证了m l s 形