（计算数学专业论文）二次有限元多网格的cg迭代算法.pdf

摘要 对高维问题利用一次元求解，只有2 阶精度，当网格加密时计算 规模浩大而不可接受本文提出，在多网格上利用2 次有限元的超 收敛性，采用c g 迭代求解，是一种可行的办法本文研究一维二次 元的多网格c g 迭代求解，是为解决高维问题的准备性工作主要 讨论如下： ( 1 ) 在两层网格上，设已知粗网格上二次有限元解，在每个单 元上利用两节点值及中点值，二次插值可得两个四分点的值，以这5 个值作为密网格上2 次元的初值，再作c g 迭代，得到更准确的解 本文发现了，二次插值的一个奇特性质，误差在两个四分点只有三 阶精度，形成高频振荡，但被2 - 3 次c g 迭代消除，效果相当好 ( 2 ) 若已知两层网格磊，磊2 上的有限元解u ，u 2 ，我们构造一 组新外推公式，可以得到第三层网格上z h 4 上2 次有限元很准确的 节点值，用二次插值获中点值，几次c g 迭代可达到很高的精度 关键词：椭圆型方程，共轭梯度法，超收敛，二次有限元，外推 a b s t r a c t t oh i g h - d i m e n s i o n a lp r o b l e m s ，m u l t i - g r i dc gi t e r a t i v et o g e t h e rw i t hs u - p e r c o v e r g e n c eo fq u a d r a t i cf i n i t ee l e m e n ti saf e a s i b l es o l u t i o n ，i n s t e a do f l i n e a r e l e m e n tw i t h2 - o r d e ra c c u r a c yw h i c hw o u l db ei n s u f f i c i e n tf o rt h ev a s ts c a l eo f c o m p u t i n gw h e ng r i d sa r er e f i n e d t h i sp a p e rs t u d i e sh o wm u l t i - g r i dc gi t e r - a t i v eo fo n e - d i m e n s i o n a lq u a d r a t i ce l e m e n ts o l v e sh i g h - d i m e n s i o n a lp r o b l e m s s e c t i o no n e ：g i v e nt h eq u a d r a t i cf i n i t ee l e m e n ts o l u t i o ni nc o a r s eg r i d s o ft h et w o - l a y e rg r i d s ，am o r ea c c u r a t es o l u t i o nw o u l db eo b t a i n e di ft h ef i v e v a l u e s ，i e t w o - n o d ev a l u ei ne a c ho ft h em o d u l e s ，m i d p o i n tv a l u e ，a n dv a l u e o ft w oq u a r t i l e sf r o mq u a d r a t i ci n t e r p o l a t i o n ，a r et a k e na st h ei n i t i a lv a l u eo f q u a d r a t i ce l e m e n ti nr e f i n e d 酊d ，f o l l o w e db yc gi t e r a t i v e ap e c u l i a rn a t u r e o fq u a d r a t i ci n t e r p o l a t i o ni sd i s c o v e r e dt h a te r r o r 葛i nt h et w oq u a r t i l e sw i t h o n l yt h r e e - o r d e ra c c u r a c yf o r m i n gh i g h - f r e q u e n c yo s c i l l a t i o n sa r ee l i m i n a t e d b y2 - 3t i m e so fc gi t e r a t i o nw i t he x c e l l e n te f f e c t s e c t i o nt w o ：g i v e nt h ef i n i t ee l e m e n ts o l u t i o nu h ，u h 2i nt h et w o - l a y e r g r i d s 磊，z h 2 ，m g ha c c u r a c yc a nb ea c h i e v e db ys e v e r a lt i m e so fc gi t e r a t i v e ， s i n c ea c c u r a t en o d ev a l u eo fq u a d r a t i cf i n i t ee l e m e n tc a nb eo b t a i n e di nt h e t h i r dl a y e rz h 4w h e nan e w e x t r a p o l a t i o nf o r m u l ai sc o n s t r u c t e d ，a n dm i d p o i n t v a l u ec a nb eg o tw i t hq u a d r a t i ci n t e r p o l a t i o n k e yw o r d s ：e l l i p t i ce q u a t i o n s ，m o n o t o n i cd e c r e a s e ，e x t r a p o l a t i o nc gi t - e r a t i v em e t h o d ，s u p e r c o n v e r g e n c e i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明 本人完全意识到本声明的法律结果由本人承担 学位论文作者签名：鸯霜兰 i o 年5 月； 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密眇 ( 请在以上相应方框内打”) 劫l o 年多 列。年f 月引日 月弓日 二次有限元多网格的c g 迭代算法 1 引言 有限元是大规模科学与工程计算中最主要的方法之一，但要精 细的解高维问题，例如垂6 维问题，却是困难重重若我们采用1 次 元，每个方向取1 0 0 个节点，h = 1 0 一，精度为h = 1 0 一，对d = 6 维问 题，总未知数高达n = 1 0 1 2 ( 1 万亿) 目前不可接受若采用二次元取 h = 1 0 ，超收敛精度仍有h 4 = 1 0 ，总未知数n = 1 0 6 ( 1 百万) p c 机 都可计算因此在多网格上采用2 次元及c g 迭代可能是解决高维 问题的可行办法之一而共轭梯度法( c g 法) 是求解有限元方程最 常用的迭代方法之一，因为c g 迭代具有存储量小、结构简单、易于 实现、收敛速度快等优点 我们知道迭代误差是由初始误差小和压缩比小两个因素决定如 何为密网格提供好的初值，是本文重点考虑的内容针对缩小初始 误差，本文提出了两种方法 第一种方法是：利用二次元的超收敛性先考虑两层网格问题 设在粗网格磊上已知二次有限元解“ 我们知道，二次元节点和中 点有4 阶超收敛，它们可作为密网格魂2 上的节点初值但是如何 提供密网格上中点的初值呢? 自然的办法是取二次元在这些点的值， 它一般只有3 阶精度。我们发现它们与密网格上准确有限元u h 2 的 误差曲线，形成了以单元为周期的高频振荡，中心线接近e = o ( h 4 ) ， 振幅为o ( h 3 ) ，并且发现2 - 3 次c g 迭代即将这些“峰”消除了，达到 了整体误差为o ( h a ) ，效果相当好这是一种很奇特的性质但是几 次c g 迭代后，误差已较光顺( 低频分量) ，继续c g 迭代，就只有 c g 迭代的经典收敛速度p = 1 一c h 了不过对高维问题而言这是 一个福音，因为对高维问题选取的步数h 不是很小，而这个收敛率 p = 1 一c 危与维数无关，因此c g 迭代的压缩效果很好 第二种方法是：利用二次有限元超收敛性和外推的特点我们知 道二次元的节点误差有渐进展开 e = 乱一缸= 勺，毋+ d ( ? ) 而中点的误差有渐进展开e = u u = 白磅+ 吻蟛+ d ( 增) 我们提出 湖南师范大学硕士学位论文 了一种新外推公式，利用第一、第二层网格上有限元解，可以构造第 三层网格上节点的值，利用它们作2 次插值，得到第三层网格上的 中点值，这样就为第三层网格提供了初始值这种方法提供的初始 值，由于中点只有3 节精度，误差又形成了高频振荡，可用几次c g 迭代消除，效果很好 最后考虑c g 迭代的收敛率问题我们知道d 维2 阶椭圆问题上 n 次有限元方程组，其条件数为c o n d ( a ) = o ( h - 2 ) ，只与步长h 有关， 与维数d 以及有限元次数佗无关一般迭代法的迭代矩阵s 的谱半 径为p = l c 危2 ，经m 次迭代后，初始误差被压缩为 i e o0 p m | i e 0 0 e - 1 4 收敛扔慢而共轭梯度法的谱半径为p = 1 一c h ，例如对五点差分格 式此常数c 1 ，因此， p m = ( 1 一九) m e - 础 1 0 6 只要m = 1 4 h 即可，与维数d 无关，这对求解高维问题是有利的 2 二次有限元多网格的c g 迭代算法 2 2 次有限元及多网格算法 2 1 二次元的超收敛性及渐进展开 考虑最简单的一维两点边值问题 - ( a ( x ) u ，) ，4 - b ( x ) u = ，( z ) ，牡( o ) = 乱，( 1 ) = 0( 2 - 1 ) 定义子空间 s o = u h 7 ( ，) ，u ( o ) = 0 ( 2 - 1 ) 的解满足 a ( 札， ) = 0 1 ( a u t v 74 - u v ) 如= ( ，口) ( 2 - 2 ) 对区间j = ( 0 ，1 ) 作均匀剖分，记节点集磊：巧= j h ，j = 0 ，1 ，2 ， 单元e l = ( 巧_ 1 ，巧) 和步长h = 1 n 记函数的节点值哟= “( 巧) 作分 片t t 次有限元空间 s h = u c ( n 叱，r 分片多项式，u ( o ) = o ) ( 2 1 ) 的有限元解u s 满足变分方程 觚。) = 0 1 ( 。矾，+ 6 u v ) d x = z 1 触郇m ，v es h ( 2 - 3 ) ( 2 - 1 ) 与( 2 - 2 ) 相减，可知误差e = u - u 满足重要的( 按能量内积) 正交 关系 a ( u 一阢幻) = 0 ，秽s 已经证明：n 次有限元有最佳的误差估计 u u i i = o ( h n + 1 ) ，l i ( 乱一u ) ，i i = o ( h n ) ( 2 4 ) 但有限元u 及其导数u 在某些点可能有更高阶精度，称为超收 敛性 3 湖南师范大学硕士学位论文 对一般的变系数情形，在任何边界条件下，在逐点的意义下已有 如下的3 类超收敛结果： ( 1 ) 在单元节点巧上，对几2 次元有最佳超收敛 ( i t 一乱 ) ( 巧) = o ( h 加) l l i t l l n + l ； ( 2 ) 在每个单元的n + l 阶内部l o b b a t t o 点上有超收敛( 佗2 ) ( u u h ) ( + h t j ) = o ( h n + 2 ) l l i t l l n + 2 ， ( 3 ) 在每个单元的1 1 阶g a u s s 点上导数有超收敛m 1 ) 见( 铭一) ( 乃+ 九芬) = o ( h n + 1 ) l l u j i 竹十2 ， 以后进一步证明，当剖分均匀时，n 次有限元在节点巧上有超 收敛性的渐进展开式： ( i t u ) ( 巧) = c ( 巧) 2 n + o ( h 2 m + 2 ) ， 1 1 , 1 若剖分非均匀时，余项为o ( h 2 1 ) ，( 见参考文献【1 1 1 9 8 1 ) 特别地，对二次有限元有两个具体结果： ( 1 ) 在节点巧和单元中点奶上，位移都有高精度( 4 阶超收敛 性) ( 让一c ，) ( 毛) = o ( h 4 ) ，( 2 - 5 ) ( 2 ) 在节点和中点上还有渐进展开 一u ) ( ) = c ( x j ) h 4 + 0 ( 胪) ，( t 正一u ) ( 毛) = c ( ) 胪+ 七( ) 酽+ d ( 危6 ) ，( 2 - 6 ) 这里的c ( x j ) 与尼( 巧) 是俨函数 数例：考虑两点边值问题， 一心+ 牡= 1 ， 乱( 0 ) = u ( 1 ) = 0 其准确解为u = 1 一c o s h ( 1 一x ) c o s h l 4 二次有限元多网格的c g 迭代算法 我们计算2 次有限元函数节点的值和真解的误差，分析它们在 节点和中点的精度 对于仃= 2 ，4 ，8 部分列出二次元节点和中点的误差e n ，于表2 1 表2 - 1 ，不同剖分下节点和中点上的误差及其前后的比值 节点e 4 1 0 5e 8 1 0 5e 1 6 1 0 8e , e 8e 8 e 1 6 1 1 6 o 1 1 0 1 ( 中)一0 0 7 4 2 ( 节) 1 4 8 3 8 2 7 1 8o 1 5 3 1 ( 中)0 0 2 2 6 ( 节)一o 1 4 0 9 ( 节) 一6 7 7 4 3 41 6 0 0 4 3 3 1 60 0 7 9 6 ( 中)一0 2 0 0 5 ( 节) 3 9 7 0 0 7 1 4o 0 6 5 1 ( 节)0 0 4 0 6 ( 节)0 2 5 3 6 ( 节) 1 6 0 3 0 51 6 0 1 3 4 5 1 60 0 5 5 0 ( 中)0 3 0 0 8 ( 节) 1 8 2 8 4 6 3 1 8 0 0 7 3 6 ( 中)o 0 5 4 8 ( 节)一0 3 4 2 5 ( 节) 一1 3 4 3 0 71 6 0 1 1 7 7 1 6 0 0 3 5 6 ( 中)0 3 7 9 1 ( 节) 一9 3 9 0 7 1 2o 1 0 5 5 ( 节)一0 0 6 5 8 ( 节)0 4 1 0 9 ( 节) 1 6 0 3 8 3 1 6 0 0 8 8 9 1 60 0 2 0 7 ( 中)一0 4 3 8 3 ( 节) 一4 7 2 2 8 5 80 0 2 5 5 ( 中)o 0 7 3 9 ( 节)一0 4 6 1 4 ( 节) 一3 4 5 0 61 6 0 1 2 1 1 1 1 60 0 0 9 9 ( 中)一0 4 8 0 7 ( 节) 一2 0 5 9 5 3 4o 1 2 7 4 ( 节)一0 0 7 9 4 ( 节)0 4 9 6 2 ( 节) 1 6 0 3 9 31 6 0 0 7 7 1 3 1 60 0 0 2 9 ( 中)0 5 0 8 0 ( 节) 一0 5 7 0 9 7 8o 0 0 2 9 ( 中)0 0 8 2 7 ( 节)一o 5 1 6 4 ( 节) 0 3 5 0 71 6 0 1 0 8 1 5 1 60 0 0 0 5 ( 中)0 5 2 1 4 ( 节) 0 0 9 5 9 1 一o 1 3 4 3 ( 节)一0 0 8 3 7 ( 节)一0 5 2 3 1 ( 节) 1 6 0 3 5 81 6 0 1 0 3 从该表可以看出，在粗网格与细网格相对应的节点上误差比e 几e 2 n 的值接近1 6 0 ，这表明有渐进展式( 2 5 ) ，因此可以利用外推的方法， 用粗网格上的节点值，来提供细网格上的节点值 5 湖南师范大学硕士学位论文 为了分析有限元的误差在每个单元上的变化特性我们绘出5 单 元上2 次插值函数的误差e = ( 珏一u ) ( z ) 曲线图( 图1 ) 图1 ；在5 个单元上二次插值函数误差曲线e ( z ) = t | 一u ，l ，纵坐标标尺为1 0 5 由于二次有限元在节点及中点上有超收敛性o ( h 4 ) ，在每个单元( 一h ，h ) 上可将有限元误差表示为 ( 缸一( z ) = c x ( x 2 一h 2 ) + o ( h 4 ) ，h 0 在迭代中，高频部分很快衰减，而低频部分很难压缩，按一般估 计迭代误差有以下估计 i l e + 1 l l l i s l l 七1 1 e 0 1 i p 七| i 扩一c ，i i ， k = 0 ，1 ，2 ， 即迭代误差由压缩比小和初始误差小两个因素决定 一般迭代格式的谱半径p = 1 一c h 2 1 ，接近1 因此迭代的收敛 速度很慢 例如对于一维问题p 1 7 h 2 则迭代k = 4 h 一2 次，误差压缩为 p 七：( 1 - 等) 知e “l o _ 6 7 湖南师范大学硕士学位论文 当h = 0 0 1 时，迭代n = 6 4x1 0 4 次才能压缩到1 0 一，收敛速度慢对 一般迭代法，迭代次数大致都是这个量级这是迭代法最本质的困 难 与一般的迭代法相比，c g 迭代法具有明显的优势对于一维问 题，一般的迭代法，s 的谱半径为p = 1 一h 2 4 而c g 的收敛速率为 p = 1 一h ，m 次迭代压缩为 ( 1 一九) m = 【( 1 一 ) 一壹】一 m e 一1 ( 2 - 7 ) 即只需要迭代m = h - 1 次，也可使误差缩小到e 。 例如h = 0 0 1 ，对于普通的迭代算法，需要m = 萨4 次迭代误差可 以缩小到e _ 而对于c g 迭代仅需要m = h - 1 = 1 0 0 次迭代就可以使 误差缩小到e - 1 因此我选择了c g 迭代法作为研究对象 对于高维问题：若每个方向的步长为h ，则未知数的总数为n = o ( h “) ，d 代表维数例如当维数d = 3 时，步长h = 1 0 ，则未知数 的个数n = 1 0 6 ( 百万) ，当网格加密一倍时，未知数的个数增加2 3 倍 而c g 迭代法的收敛率仍为p = 1 一c h ，与维数无关所以c g 迭代 对高维问题非常有利，而对于低维问题没有优势本文的研究一维 问题目的是为研究高维问题作铺垫 例：考察一+ u = 1 ，在区间【0 ，1 】上，u ( o ) = 让”) = 0 用二次元求解该线性方程组，取节点 1 磊：x j = j h ，j = 0 ，1 ，2 ，2 n ；h = 云 单元乃= ( x 2 j - 2 , z 巧) 的中点是x 2 j - 1 ，节点值 将单元矩阵陬| 6 e 】组集成总矩阵，处理本质边界条件, 4 0 ) = 0 后， 得到线性方程组 a u = 6 ；u = ( 让1 ，u 2 ，u n ) f ，u o2 0 本文讨论c g 迭代的收敛问题，为了比较我们还用直接法求出 线性方程组的有限元解u 我们的目标是在多层网格迭代收敛速度 磊，z h 2 ，上用二次有限元求解魄，u h 2 ，首先考虑两层网格，设 8 二次有限元多网格的c g 迭代算法 已知在粗网格磊上的解巩，如何利用，为密网格磊。提供初值 硼2 下面讨论提供初值：的方法 设在粗网格磊的每个单元( z 巧2 z 笱) 上，三个点( x 2 j - 2 ，z 巧“x 巧) 上的函数值( u 2 j - 2 ，u 2 1 - 1 , u 2 j ) ，已知定义二次插值函数 2 j 让= l i ( x ) u t i = 2 j - 2 取此单元三个节点值( u 。伸，u 。，u 2 j ) ，仍作为密网格磊2 上的节点 值计算上述2 次插值函数在2 个4 分点上的值u 2 ，一昙，让2 ，+ 昙，取它们 作为密网磊2 上新增的两个中点上的值，这5 个值组成了密网磊2 上两个单元上的初值嘲2 ，我们在z h 2 上用c g 迭代可得到近似解 u h 2 z h z 利用这种方法构造的初值，在节点和中点的精度为o ( h a ) ， 但在四分点上只有精度o ( h 3 ) 设粗网格为4 个单元，在4 单元上的节点和中点值( 一共9 个 点) ，以及其每个单元上进行二次插值所得到的2 个四分点的值( 一 共8 个点) ，总共1 7 个点的值，这些值为8 单元网格提供了初值( 4 单元网格上的节点和中点成了8 单元网格上的节点，而4 单元上的 四分点是8 单元上的中点) 下表2 1 给出4 单元网格上除去端点u ( 0 ) = 0 外，其余的1 6 个 节点、中点和4 分点的值与8 网格上准确有限元解的误差，标尺是 ( e j = e j 1 0 4 ) 表2 1 ，不同剖分的节点上的误差( 乘1 0 4 ) 及其前后的比值 分点中点分点节点分点中点分点节点 e le 2 e 3e 4e 5e 6e 7e 8 0 7 9 0 90 0 1 5 50 7 7 5 60 0 0 6 10 5 3 8 80 0 0 7 90 5 1 4 90 0 0 9 9 分点中点分点节点分点中点分点节点 e 9e l oe l le 1 2 e 1 3 e 1 4e 1 5e 1 6 0 3 1 7 90 0 0 3 30 。2 8 9 10 0 1 1 9一o 1 1 4 60 0 0 1 10 0 8 3 60 0 1 2 6 从该表可以看出，4 单元节点和中点上的误差很小，四分点的精度较 差，而且4 分点上的正负值，两两交替出现这种方法提供的初值应 该是一条高频振荡折线 9 湖南师范大学硕士学位论文 图( 2 1 ) 给出了1 6 网格c g 迭代的初始值与有限元解的误差图 ( 包括端点缸( o ) = 0 ，一共是1 7 + 1 6 = 3 3 个点的误差图) ，即有8 网格 所给的1 7 个节点和中点的值和以及经过二次插值得到的1 6 个四分 点的值，共1 7 + 1 6 = 3 3 个值，它们是1 6 网格的c g 迭代的初始值 图( 2 2 ) 给出了3 2 网格初始值与有限元解的误差图( 包括端点 u ( o ) = 0 ，一共是3 3 + 3 2 = 6 5 个点的误差图) ，即有1 6 网格所个的3 3 个节点的值和经过二次插值得到的3 2 四分点的值，这样的3 3 + 3 2 = 6 5 个点的值，它们是3 2 网格的c g 迭代的初始值 图2 1 ：8 网格上的节点和中点值 及单元四分点上的二次插值与1 6 网格有限元解的误差图，纵坐标 的标尺是( 1 0 一6 ) 图2 2 ：1 6 网格的节点与中点值及 单元四分点上的值与3 2 网格有限 元解得误差图，纵坐标的尺标是 ( 1 0 7 ) 由上面的误差图形中可以清晰的看出：由粗网格上的节点值及 中点值( 具有高精度o ( h 4 ) ) ，以及由每个单元上的节点和中点值进 行二次插值所求出的四分点的值( 精度较低o ( 3 ) ) ，这样得到的密 网格上的初始值是一条以单元为周期的含有高频振荡折线( 振幅为 o ( h 3 ) ) 这就为密网格提供了一个精度较高的初始值在这个基础上 进行c g 迭代，就可以很快使总体误差达到o ( h 4 ) 用这种方法提供的初始值，初始值的误差有较高的精度，下面将 用这种提供好初值，对c g 迭代求解有限元方程箜。 一 1 0 二次有限元多网格的c g 迭代算法 3c g 迭代的收敛性 3 1c g 迭代法及其按日1 及z 2 模的收敛性 在n 维欧式空间r n 中定义内积，l z 模和a 模 ( x ，y ) = 巧协， 对于线性方程组 a x = b 这里x = ( x l , z 2 ，) ；a = ( a 0 ) n n 对称正定定义二次多项式： f ( z ) = 互1 x r 似一b x 其梯度是f ( x ) 在x 点处增长最快的方向 v f ( x ) = a x b 负梯度 一vr ( x ) = b a x 是f ( x ) 下降最快的方向 我们引用参考文献【2 】，列出共轭梯度法( c o n j u g a t eg r a d i e n t ，c g ) 的计算格式如下： ( 1 ) 任意给初值x o ，计算最快下降方向铂及共轭方向p 1 卜坷裂舢； 湖南师范大学硕士学位论文 ( 2 ) 对k = 1 ，2 ，3 ，采用以下公式计算 f 口七= ( r k l ，r k 1 ) ( r ，a r ) ； l x k = x k 一1 + 口p k ； ( r k = r 七一1 一a k a p 七； l 凤= ( n ，r k ) ( r k - l r k 一1 ) ； i最+ 1 = r k + d k p k ； 对给定的精度e ，当i r k l 时终止迭代 由c g 迭代的算法中，得到两个向量组 n ) ， p a l ，即两个正交 系：2 2 正交系 吩) 和a 正交系 p a 它们有如下正交的性质： ( 孤，最) = 0 ，k = 1 ，2 ，3 ， ( r k ，r f ) = 0 ，( p k ，a b ) = 0 ，k z 从该算法中可以看出，共轭梯度法具有以下优点： ( 1 ) 不需要任何参数估计 ( 2 ) 在全部算法中仅包含矩阵a 和某个向量的乘积，或则一些 向量之间的点积，a 矩阵本身在计算中不改变，因而不产生非零填 充，所以c g 算法适合于解大型稀疏矩阵 ( 3 ) 在计算中，若遇到= 0 或( 最，a 最) = 0 时，计算中止 因为如果遇到剩余向量r k = b a x 是= 0 ，即有a x 奄= a x 。= b ，由 矩阵a 对称正定，则z 七= 甄已是方程组的解 如果( r ，a r ) = 0 ，因为a 对称正定，所以p k + l = 0 = r k + d k p k ， 由c g 迭代的性质，有( ，r k ) = h ，p k ) = 0 ，亦有强= 0 若r k 0 ，k = 1 ，2 ，正交列一定是线性无关的，则机 组 成线性无关向量组，方程组a x = b 的解一定可由这组向量线性表示， 因此c g 迭代法最多经过n 次迭代，一定可以得到精确解 c g 有两个基本收敛性估计； ( 1 ) 迭代算子s 按谱范数是单减的，即： i s 七e 0 | i a i l e o l l a ， 】2 二次有限元多网格的c g 迭代算法 这里的e o 是初始误差。 ( 2 ) c g 作为一种迭代方法，其收敛性一般比几种经典的迭代方 法好，已经证明c g 在a 一范数意义下的收敛性： i i s k e o i l a 2 ( 糕c o n g 纠l e 0 忆( ) va + l 这里的c o n d ( a ) 是矩阵a 的条件数或谱范数 对有限元，条件数c o n d ( a ) = o ( h - 2 ) ，设为( o h ) ，一般有c ；， 因此 ：型墅二!：12ch1一hp= ：= = = = = 工一z l 一 x c o n d c a ) + 1 而一般迭代法的压缩因子只有p = 1 一c h 2 ，因此c g 迭代远比一 般的迭代法好这些c g 迭代法的基本估计，在理论分析中起着关 键的作用在研究瀑布型网格法，特别是外推瀑布型网格法时，当h 适当小时， p m = ( 丽1 - c 万h ) m e 一撇 即在m = 矗次迭代后，误差缩小为e - 1 因此c g 迭代法不仅仅是磨光作用，也还有压缩作用 最近陈传淼，胡宏伶还研究了c g 法离散z 。模的性质我们引用 其结果如下： 定理1 ( 1 2 模单降性) ：若a 是对称正定矩阵，则共轭梯度法在 1 2 范数下为单调下降的，即 0 s 七e oj i l l e o i i ，k 0( 3 - 2 ) 定理2 ( 1 2 模收敛性) 对口，c g 迭代算子s 按1 2 模收敛性 估计 0 s m e o l l 2 p m l i e o i i( 3 - 3 ) 这里压缩比 p = 需而1 - c h 引q 傩 湖南师范大学硕士学位论文 因此，c g 迭代按1 2 模的收敛性质与按a 模类似但按1 2 模可度 量节点误差的精度，它一般比按a 模误差高1 阶精度。 3 2 二次插值的奇特特性 用二次有限元解1 维椭圆问题 一( 口( z ) 牡7 ) 7 + 6 ( z ) u = ，( z ) ，u ( o ) = ( 1 ) = 0( 3 - 4 ) 其弱形式 a ( u ，”) = ( 缸7 u 7 + u v ) d x = ( ，口) ，口s j 0 因为二次有限元解u 也满足 ，1 a ( u h ，u ) = ( 乱：t ，7 + u v ) d x = ( ，口) ，0 所以 a ( u 一也，l ，口) = 0 ，可s ， 在陈传淼教授的工作中( 见参考文献【1 1 1 9 8 1 ) 已证明二次元误差在 单元k = ( 一h ，h ) 上有表示式 e ( s ) = r ( s ) + h a w ( s ) + o ( h 5 ) ，z = h s ，一h z h ，一1 8 1 这里w ( x ) 是z 的俨函数，r 为u ( x ) 的m 型展开的余项 r ( 8 ) = a a m 3 ( s ) + a 4 m 4 ( s ) - 4 - a a m s ( s ) a - o ( h 6 ) ；= 0 ( ) ，坞( 士1 ) = 0 ，j 2 在节点( s = 士1 ) 和中点( s = o ) 分别有4 阶超收敛精度的渐近 展开 e ( x z ) = c ：h 4 ( 奶) + o ( h 5 ) ；z = 歹，j + 2 e i + l = - - e ( 易) = c h 4 + c 2 h 4 + o ( h 5 ) ； 因此两者的公式结构不同，中点误差一般可能大些 1 4 二次有限元多网格的c g 迭代算法 当利用钍 在两节点巧，即+ 2 及中点+ ，上的有限元u l 作2 次插 值时，产生的误差有两部分组成：让的二次插值误差 r ( s ) - a - - j 1 2 乱= 百h 3 s ( s 2 - 1 ) d a u + o ( h 4 ) ，一1 s 1 及节点误差勺，钳1 ，勺+ 2 的二次插值 j 1 2 乱= 勺+ 1 + 差( 勺+ 2 一勺) + 丢( 白+ 2 2 勺+ 1 + 勺) o ( 4 ) 而r ( s ) 在两个4 分点s = 4 - ；上有 r ( 丢) = 士岛危3 + c 2 h 4 + c a h 5 + d ( 舻) 因此在两个4 分点上s = 士 ， e ( 土主) = 士岛护+ ( g + g ) 酽士a 危5 + o ( 尼6 ) 它有两大特点； ( 1 ) 主部为三阶项i c o h 4 ，数值相等符号相反，形成了一个反对 称结构，从整个区间上看，它是以单元为周期的高频震荡折线，几 次c g 迭代即可消除 ( 2 ) 剩下一些较平滑的低频4 阶项，少数几次c g 迭代很难消 除 因此上式误差在一个单元( 勺，巧+ 2 ) 上5 点( x j ，巧+ ，x j + l ，x j + 1 + ，x j + 2 ) 的误差分布为 c 2 h 4 ，一c h 3 4 - c 3 h 4 ，( q + a ) h 4 ，c h 3 + c 3 h 4 ，c 2 h 4 ， 用2 3 步c g 迭代，高频振荡项：e ：c 3 h 3 消失，误差磨光为 c 2 h 4 ，c 3 h 4 ，( c 1 + c 2 ) h 4 ，c a b 4 ，c 2 h 4 ， 以后进一步被磨光，误差进一步减小，并趋于平稳 仍考虑前面的例子：一+ 乱l ，在区间【0 ，1 】上，u ( o ) = ( 1 ) = 0 1 5 湖南师范大学硕士学位论文 首先在单元上计算二次元得到2 n + 1 个节点的值( 包括x = 0 上u o = o ) 在每个单元除去端点和中点外，还计算2 个4 分点上的 值，总共得到4 + 1 个点上的值，并将它作为2 n 单元上2 次有限元 的初始值用j 次c g 迭代求得扩，为了与2 n 单元上的准确有限 元u 比较，考察迭代误差 e = 驴一u 当迭代步数增加时，趋向0 ，此种方法可考察c g 迭代的收敛性 利用前面提到的提供初值的方法，用二次元求解该有限元方程， 考察8 个单元上c g 迭代解与准确有限元解的误差图 下面绘制误差图形，图3 1 是4 网格上的节点及中点值( 5 个节 点与4 个中点) 以及8 个4 分点的值( 由4 网格上的节点值经过插 值得到的) ，共1 7 个点误差图该图在9 个节点和中点上有超收敛 o ( h 4 ) ，而在8 个4 分点上精度只有o ( h 3 ) 4 网格上这9 + 8 = 1 7 个点 的值，为8 网格提供了初值，8 个4 分点成了8 网格的中点，精度为 o ( h 3 ) ，节点与中点的精度为o ( h 4 ) 对8 网格进行c g 迭代，每次c g 迭代后，我们绘出误差( 1 7 个点) 的变化情况 这里绘出了前1 6 步迭代误差图( 误差萨= u 8 一w k ，u 8 是准确 有限元解，七是c g 迭代k 次的近似解) 图3 3 ：k = 0 ，标尺( 1 0 一5 ) ，8 个 尖峰在4 分点上 1 6 图3 4 ：k = 1 ，标尺( 1 0 一6 ) ，误差 缩小近1 0 倍 二次有限元多网格的c g 迭代算法 图3 5 ：k = 2 ，标尺( 1 0 一6 ) 图3 7 ：k = 4 ，标尺( 1 0 一6 ) 图3 6 ：k = 3 ，标尺( 1 0 一6 ) 图3 8 ：k = 5 ，标尺( 1 0 6 ) 图3 9 ：k = 6 ，标尺( 1 0 6 ) 图3 1 0 ：k = 7 ，标尺( 1 0 6 ) 湖南师范大学硕士学位论文 图3 1 1 ：k = 8 ，标尺( 1 0 6 ) 图3 1 2 ：k = 9 ，标尺( 1 0 一6 ) 图3 1 3 ：k = 1 0 ，标尺( 1 0 一6 ) 图3 1 4 ：七= 1 1 ，标尺( 1 0 一6 ) 图3 1 5 ：七= 1 2 ，标尺( 1 0 一6 ) 图3 1 6 ：k = 1 3 ，标尺( 1 0 一6 ) 二次有限元多网格的c g 迭代算法 图3 1 7 ：后= 1 4 ，标尺( 1 0 一6 ) 图3 1 8 ：k = 1 5 ，标尺( 1 0 6 ) 图3 1 9 ：七= 1 6 ，标尺( 1 0 1 5 ) ，机 器误差 1 9 湖南师范大学硕士学位论文 从图3 2 3 4 可以看到这8 个尖峰被2 3 次c g 迭代消除、磨平 了，误差峰值缩小了1 0 一3 0 倍，效果相当好。以后折线变得较为光 顺，误差曲线主要在正侧，压缩比也趋于平稳 对于n 元的线性方程组，并且用c g 迭代法，仅需不超过n 次的 迭代就可得到精确解上述方法得到的n 阶线性方程组a x = b ( a 是对称正定矩阵) 采用c g 迭代求解，高频振荡的尖峰经过几次迭 代就被消除、磨平了，使误差曲线变的较光顺，以后多次迭代具有 平稳压缩的特点 原因分析： ( 1 ) 由前面的图1 可以知道c g 迭代中我们选择的初始误差是一 个高频振荡的折线，误差e j 主要有节点和中点上的低频误差o ( h 4 ) ， 而误差的高频振荡是二次插值在四分点上只有3 阶精确度造成的 ( 2 ) 这些高频用2 3 次迭代即被消除、磨光，以后趋于稳定，以 低频为主，但基本误差曲线还在同侧，即使用c g 迭代也不容易压 缩 ( 3 ) 因为c g 迭代的压缩比 + 1 p = 斜= 1 一c h( 3 - 5 ) 当取c = 1 ，h = 百1 时，压缩比p ；，所以当高频被消除以后，c g 的的压缩比趋于稳定，从图3 4 - 3 1 6 可以看出c g 迭代后误差峰值由 3 1 0 6 降为1 5x1 0 ，每次迭代压缩较少 对于前面的一维问题，剖分成8 个单元的网格，先计算出其压缩 比，然后观察其特点 设z 是准确有限元解，祝是第i 次的迭代解采用a 模( 能量模) 及工z 模度量误差，记前后两次c g 迭代的误差比为 鼽= 锗 麓= 糍崭 2 0 二次有限元多网格的c g 迭代算法 下表3 1 ，歹i 出犰关于i 的变化情况 可1y 2y 3y 4y 5y 6y 7 y 6 0 4 3 2 90 2 4 3 30 6 1 0 6 0 9 1 0 30 8 6 5 6o 9 0 7 3 0 7 7 3 70 9 2 9 2 y 9可1 0y l ly 1 2y t 3y 1 4y 1 5 0 8 7 9 10 9 0 7 10 8 6 1 0 0 9 2 6 60 9 2 5 70 9 2 5 62 3 5 8 5 1 0 9 由上表3 1 可以看出误差的能量模i i x 一z 0 是单调下降的 z 1z 2 z 3z 4 z 5 铂z 7z s 0 6 2 0 70 6 9 8 80 9 6 8 9 0 9 7 5 40 9 4 2 40 9 5 1 9 0 8 9 6 50 9 6 9 6 z 9z 1 0z l lz 1 2z 1 3z 1 4z 1 5 0 9 4 4 60 9 5 9 70 9 4 2 9 0 9 2 6 60 9 5 0 30 8 7 8 92 4 4 5 1 1 0 9 误差的l z 模也是单调下降的 由以上两表看到，无论是按a 模或是l 2 模度量，其误差都是单 调下降的除前2 - 3 次迭代外，其它迭代的压缩比都接近0 9 ，由此我 们就产生了外推加速的想法，多次c g 迭代以后，误差e i 变的光顺， 即成为低频，使c g 迭代压缩效果降低，因此，光顺不是好事，是 否可用什么方法改变这种不利的结构? 下章提出用c g 外推加速的 思想 2 1 二次有限元多网格的c g 迭代算法 4 c g 迭代的外推算法 4 1c g 迭代的外推计算 对代数方程的线性迭代形式： x = s x 七f 。x j q = s x j + f 1 其误差 p = x x j ；e i j 七1 = s 0 = s 3 e 0 设初始误差 e o ( z ) = o t 仇( z ) ， i = l 于是经j 次迭代，误差有 伊e o = c f 吼( z ) = 啦店俄( z ) ，p t 1 一c f 舻 1 ， i = l 由于在本文采用粗网上的2 次有限元，为密网提供2 次元初值 的模式下，则初始误差主要由低频和高频两大类组成，经多次迭代 后主要剩下最低频 印一x = = a l p g l ( z ) + o ( 1 ) ，i l e j f i = c 彳+ o ( 1 )( 4 - 1 ) 前后两次迭代误差比趋于稳定 l l + m i i l l d l l = p m + d ( 1 ) ，m 1 我们又可写出 + 1 一x = 一十1 = 口l 彳+ 1 9 1 ( z ) + o ( 1 ) ，l i + 1 i i = c 彳+ 1 + 0( 4 - 2 ) 前面( 4 - 1 ) ( 4 - 2 ) 两式相减，得到前后两个迭代计算值之差( 可计算 量) 一+ 1 一= 口1 p ( p 1 1 ) g l ( z ) + o ( 1 ) ； 2 3 湖南师范大学硕士学位论文 l i + 1 一x i i = c , ( p l 一1 ) + d ( 1 ) ； + 2 一妒+ 1 = a l p l + 1 ( p l 一1 ) 9 l ( z ) + o ( 1 ) ； l i + 2 一+ 1 0 = c 彳+ 1 ( 1 1 9 l 一1 ) + d ( 1 ) ； 它们之比( p 为可计算量) p = 两i i x j 瓦+ 2 - 巧x j 嘲+ s l l = p l + d ( 1 ) 1 ， ，) = 一= ，) 1 + l ，i - i i 尸 ij x j +