（电磁场与微波技术专业论文）基于mdasvd的快速直接解法——cbd.pdf

硕叶：论文旗子m d a s v d 的快速直接解法c b d 摘要 多层矩阵分解算法( m u l t i l e v e lm a t r i xd e c o m p o s i t i o na l g o r i t h m ，m l m d a ) 最初由 m i c h i e l s e n 和b o a g 提出用来解决二维散射问题，之后r i u se ta l 等人在三维问题中得以 应用。本文将介绍矩阵分解算法( m d a ) 的基本原理，如等效基函数的引入及( m a t r i x d e c o m p o s i t i o na l g o r i t h m s i n g u l a rv a l u ed e c o m p o s i t i o n ，m d a s v d ) 。m d a s v d 算法 是在m d a 基础上进行奇异值分解( s i n g u l a rv a l u ed e c o m p o s i t i o n ，s v d ) 。m d a s v d 算法通常在使用格林函数的现有矩量法( m o m ) 编码基础上实现，这种方法具有两个优 点：一个是对于分段光滑平板物体效果比快速多极子( f m m ) 好，另外就是克服了多 层快速多极子算法( m l f m m ) 的缺点，可以用来分析多层媒质问题。 在上述m d a s v d 的基础上，本文使用一种新的快速直接解法压缩块儿分解算 法( c o m p r e s s e db l o c kd e c o m p o s i t i o n ，c b d ) 来求解矩量法( m o m ) 中电磁辐射和散射 问题。近场自作用是直接计算的，填充的是满秩矩阵。远场和近场互作用不是满秩填充 的，而是稀疏形式。这种方法具有两个优点：一个是克服了迭代法性态不好的缺点，另 外就是计算单站雷达散射截面( r c s ) 时间很短。c b d 对于自由空间的电磁辐射和散射 问题，它的计算复杂度是o ( n 2 ) ，存储量是o ( y 3 佗) 。 继c b d 之后，我们又进一步分析了多层压缩块儿分解算法( m u l t i l e v e lc o m p r e s s e d b l o c kd e c o m p o s i t i o n ，m l c b d ) 的基本原理及其操作步骤，对于电大尺寸目标的散射， 其未知量数目较大，此时应用m l c b d 将获得比c b d 更高的效率。 为了更好地应用c b d ，我们使用一种迭代提高解精度的方法。由于c b d 的阻抗矩 阵经过s v d 压缩，当截断精度提高时，时间和内存减少了很多，但同时却会带来解不 精确的问题，这时使用线性迭代法，可以提高解的精确度。最后把c b d 做成与预条件， 来改善收敛性态。 关键词：矩量法，压缩块儿分解，多层矩阵分解 a b s t r a c t硕i ：论文 a b s t r a c t t h em u l t i l e v e lm a t r i xd e c o m p o s i t i o na l g o r i t h m ( m l m d a ) w a so r i g i n a l l yd e v e l o p e d b ym i c h i e l s e na n db o a gf o r2 - dt m zs c a t t e r i n gp r o b l e m sa n dl a t e ri m p l e m e n t e di n3 - db y r i u se ta 1 t h i sp a p e rw i l li n t r o d u c em a t r i xd e c o m p o s i t i o na l g o r i t h m ( m d a ) ，s u c ha st h e b a s i cp r i n c i p l eo fe q u i v a l e n ta n dm d a - s v d m d a - s v di sb a s e do nm d aa l g o r i t h m s i n g u l a rv a l u ed e c o m p o s i t i o n ( s v d ) 。m d a s v da l g o r i t h mu s i n gg r e e nf u n c t i o nb a s e do nt h e e x i s t i n gt h em e t h o do fm o m e n t ( m o m ) c o d i n gu s u a l l y , t h i sm e t h o dh a st w oa d v a n t a g e s ：o nt h e o n eh a n d ，ap i e c e w i s ss m o o t hf l a to b j e c ti sb e t t e rt h a nf a s tm u l t i p o l ee f f e c t ，o nt h eo t h e rh a n d i tc a no v e r c o m et h ed i s a d v a n t a g e so fm u l t i l e v e lf a s tm u l t i p o l em e t h o d ( m l f m m ) ，a l s oc a nb e u s e dt oa n a l y s i se l e c t r o m a g n e t i cp r o b l e mo fm u l t i l a y e r e dm e d i u m o nt h eb a s i so fm d a s v d ，t h i sp a p e ru s e san e wf a s td i r e c ts o l u t i o n - - c o m p r e s s e d b l o c k d e c o m p o s i t i o na l g o r i t h m ( c b d ) t o s o l v et h em o m e n tm e t h o d ( m o m ) o f e l e c t r o m a g n e t i c r a d i a t i o na n ds c a t t e r i n gp r o b l e m t h en e a rf i e l di sd i r e c t l yc o m p u t e d ， w h i c hi sf i l l e dw i t hf u nr a n km a t r i x t h ei n t e r a c t i o nb e t w e e nf a rf i e l da n dn e a rf i e l di sn o t f i l l e dw i t hf u l lr a n kb u ts p a r s em a t r i x t h i sm e t h o dh a st w oa d v a n t a g e s ：o n ei st h a ti t o v e r c o m et h ed i s a d v a n t a g e so fi t e r a t i v em e t h o d t h eo t h e ri st h a tw h e ni tc a l c u l a t em o n o s t a t i c r c s ，i tc o s tv e r ys h o r tt i m e f o rr a d i a t i o na n ds c a t t e r i n gp r o b l e m s i nf r e e s p a c e e l e c t r o m a g n e t i c ，t h en u m e r i c a lc o m p l e x i t yo fc b d i ss h o w nt ob eo ( n 2 ) a n dt h es t o r a g e r e q u i r m e n t s i so ( n 3 7 2 ) a f t e rt h ec b d ，w ea n a l y z e dt h eb a s i cp r i n c i p l ea n dt h eo p e r a t i o ns t e p so fm u l t i l e v e l c o m p r e s s e db l o c kd e c o m p o s i t i o na l g o r i t h m ( m l c b d ) f o re l e c t r i c a l l yl a r g et a r g e t s ，t h e n u m b e ro fu n k n o w ni sv e r yl a r g e ，t h ea p p l i c a t i o no fm l c b dw i l lg e th i g h e re f f i c i e n c yt h a n c b d i no r d e rt ou s ec b db e t t e r , w eu s ea ni t e r a t i v em e t h o dt oi m p r o v et h ea c c u r a c yo f r e s u l t a f t e rt h ec o m p r e s s e do fc b di m p e d a n c em a t r i x ，w h e nt h ep r e c i s i o no ft r u n c a t i o ni s i m p r o v e d ，i tw i l lr e d u c et h et i m ea n dm e m o r y , b u ti tw i l lm a k et h er e s u l ti m p r e c i s e ，a tt h i s m o m e n tu s i n gl i n e a ri t e r a t i v em e t h o dw i l li m p r o v et h ea c c u r a c yo ft h er e s u l t f i n a l l yt h e c b di su s e df o rt h ep r e c o n d i t i o n ，w h i c hc a ni m p r o v et h ec o n v e r g e n c ec o n d i t i o n k e y w o r d s ：t h em e t h o d o fm o m e n t ( m o m ) ，c o m p r e s s i o nb l o c kd e c o m p o s i t i o n ( c b d ) ， m u l t i l a y e ri m p e d a n c em a t r i xd e c o m p o s i t i o n ( m l m d a ) 1 1 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除- r j 口以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 纠9 年否月7 7 日 硕士论文 基于m d a s v d 的快速直接解法c b d 1 绪论 1 , 1 本文的研究背景 如何快速、准确地分析三维复杂目标的电磁特性，长期以来一直是计算电磁学领域 的研究重点。对导体目标和介质目标的精确电磁散射计算问题，可通过以下两种途径进 行研究：求解麦克斯韦偏微分方程和求解电磁场积分方程。前者的典型方法包括时域有 限差分法( f d t d ) 和有限元法( f e m ) ；后者的典型方法有矩量法( m o m ) 脚3 等。 虽然基于偏微分方程类的方法算法简单，易于计算机编程，且所涉及的矩阵为一稀 疏矩阵，可以方便的进行计算机存储。但通常这类方法的未知量分布在整个自由空间， 故涉及的未知量非常庞大。同时，由于偏微分方程的局域性，电磁场在数值网格的传播 过程中会形成色散误差。所研究的区域越大，色散误差的积累也越大。因此，对于电大 尺寸和复杂结构的目标来说，为保证计算结果的精确性，人们不得不采用更精确的网格 来剖分，这就使未知量更加庞大了。 由于庞大的未知量和数值色散误差是微分方程类方法用于分析复杂电磁目标的两 个瓶颈，因此在分析复杂电磁目标时需要使用基于电磁积分方程的数值方法。这类方法 的优势在于未知量仅定义在源分布的区域上，这就使积分方程类方法的未知数数目要比 微分方程类方法少得多；另一方面，由于格林函数的引入；场在网格中的传播过程可由 格林函数精确描述以减少了数值色散误差。数值方法中最常用的就是矩量法，它是一种 采用基函数和测试函数离散化积分方程的方法。矩量法作为一种严格的数值方法，计算 结果精度高，但计算效率很低且需要占用大量的内存，所以很难在现有的设备条件下用 矩量法完成电大尺寸复杂目标的计算。 近年来，随着多层快速多极子( m l f m m ) 和多层矩阵分解算法( m l m d a ) 等快速方 法的出现，上述问题得到了有效的解决，从而使得应用积分方程方法求解超大型的电磁 散射问题成为可能。 最近，矩阵低秩分解类方法得到了国际的广泛重视。利用压缩方法可以减少矩阵在 计算机中的存储量和计算复杂度，这样减少了矩阵矢量乘的时间，有利于快速分析电磁 散射问题。 这些矩阵矢量乘算法是被用在迭代解法里面，比如双共轭梯度( b i c g ) 、广义最小 余量法( g m r e s ) ，尽管迭代解法在很多的工程问题上得到了非常成功的应用，但是就 求解矩阵方程的“鲁棒性”来说，它仍然不能与直接解法相比拟。迭代解法依赖于矩阵的 性态。如果性态不好，则收敛率是不可预测的。进而对直接解法的需求则非常迫切。 1 绪论硕一l 论文 1 2 研究历史和现状 电磁场数值分析是根据m a x w e l l 方程，利用适当的边界条件确定所关心区域或物体 内的电磁场或电流分布，进而求出所需要的物理参量。回顾计算电磁学发展的历史， 早在1 8 6 4 年，m a x w e l l 已用偏微分方程的形式给出了电磁波现象中电场和磁场的统一 表达式，他的研究成果被称誉为1 9 世纪最显著的科学成就之一。而求解电磁场问题的 方法，归纳起来可分为三大类，其中每一类又包含若干种方法，第一类是解析法；第二 类是数值法；第三类是半解析数值法。经典的数学分析方法是近百年来电磁学学科发展 中一个极为重要的手段。解析法包括建立和求解偏微分方程或积分方程。严格求解偏微 分方程的经典方法是分离变量法；严格求解积分方程的方法主要是变换数学法。 大多数快速方法基于多层子域分解，多层快速多极子算法( m l f m a ) 就是方法之 一，它是由快速多极子方法不断发展而得到的。该算法对划分的单元在多个层级进行分 组，按照层间嵌套、逐层递推的原则实现快速多极子算法。类似于传统的快速多极子算 法，在最细层级上，邻近组单元间的相互作用仍然用矩量法计算，只对非邻近组单元采 用快速多极子算法，从最细层级开始逐层向上聚合，直到第二层( 区分邻近组和非邻近 组的最粗层级) ，然后逐层向下配置，并在此过程中计算转移因子。m l f m a 的计算量 相比传统矩量法由o ( n j ) 减少到o ( n l o g n ) 。由于m l f m a 卓越的计算效率，近年来它 被广泛用于电大目标。目标尺寸越大，未知量的数目越多，越容易显现计算的高效率。 矩量法( m o m ) 作为一种积分类方法，已经广泛的用于各种天线辐射、复杂散射体 散射以及微带贴片结构分析等领域。然而，在分析表面积分方程时，得到的阻抗矩阵z 是一个稠密的满矩阵，如果采用矩量法直接求解，则需要的存储、填充和矩阵矢量乘的 操作的计算复杂度为o ( n ) ，其中n 为未知量的个数。这极大程度地阻碍了求解电大 尺寸三维散射问题。 一些成功的技术方法能够有效地降低表面积分方程在迭代过程中的存储量和计算 量。这些方法包括快速多极子方法( f m m ) 鹪】、自适应积分方法( a i m ) 、修正的快速 傅罩叶变换方法( p f f t ) 等。多层快速多极子方法( m l f m m ) 能够有效的降低存储和 c p u 计算复杂度到o 州) 和o ( n l o g n ) 。然而，在m l f m m 中，公式的推导、执行、以及 运算往往需要预先己知格林函数。基于快速傅里叶变换( f f t ) 的方法，如灿m 和p f f t ， 用规则网格上的等价源取代了基函数，它能够在一些指定位置再生出原始电流源所产生 的场。对于计算近场的相互作用，利用f f t 也可以进行加速，然而f f t 不能完全正确 的对近场的相互作用进行计算，还需要对其进行修正。基于f f t 的方法对于大量积分方 程( v i e s ) 和平面结构具有较好的效果。对于v i e s ，基于f f t 的方法能够达到的复杂 度为o ( n l o g n ) ，然而对于s i e s ，存储和c p u 计算时间的复杂度会分别降低到o ( n 1 5 ) 和o ( n 1 。5l o g n ) 。 2 硕i ：论文基于m d a s v d 的快速直接解法c b d 自适应交叉近似法( a d a p t i v ec r o s sa p p r o x i m a t i o n ，a c a ) 阳h 2 1 方法利用一对具有低 秩特性的矩阵块来代表矩量法中的远场相互作用。这个方法最初由b e b e n d o r f 提出。自 适应交叉近似法( a d a p t i v ec r o s sa p p r o x i m a t i o n ，a c a ) 方法的优点在于它的完全的数学 特性。也就是通过对阻抗矩阵进行线性代数操作来提高计算速度。它类似于q r 分解、 奇异值分解( s v d ) 、l u 分解。因此，自适应交叉近似法( a d a p t i v ec r o s sa p p r o x i m a t i o n ， a c a j 的研究并不完全依赖于对积分方程、基函数本身的知识，他还依赖于其数学特性。 因此，a c a 能够很容易的整合到矩量法的代码中去。总的来说，a c a 方法是一种多级 矩阵分割方法，他能够通过对代表远场作用的低秩子矩阵进行l u 分解，从而降低计算 量。 这种方法已经成功用于静态和低频问题的求解中，在这些应用中，积分核函数是渐 进平滑的，其复杂度为o f n l o g n ) 。当离散尺寸h - - w a v e l e n g t h 7 ，未知量个数为5 0 0 0 0 0 时，自适应交叉近似法( a d a p t i v ec r o s sa p p r o x i m a t i o n ，a c a ) 对内存和c p u 计算时间 的需求量大概为人r 乃l o gn 量级。这种方法只需要传统矩量法- d , 部分的内存和c p u 时 间便可得到非常精确的结果。 为克服迭代解法收敛耗时的缺点，主要有两种解决途径。( 1 ) 迭代解法的每一步迭代 中，矩阵矢量乘是主要的运算，其计算量j 下比于o ( n z ) ，因此，降低迭代方法的矩阵矢 量乘的计算复杂度，减少每一步的迭代时间必将节省大量的计算时间；( 2 ) 减少迭代收敛 所需的步数，同样能够节省许多计算时间。 第一种方法主要有两种实现途径：一是基于快速傅里叶变换( f f t ) h 0 1 ，二是基于 快速多极子方法( f m m l 4 1 - - 4 7 第二种方法的实现主要是采用预条件技术。 无论m l f m m 还是c g f f t 方法，虽然它们每次迭代的计算复杂度都是 o ( n l o g ) ，但对于微波集成电路电大尺寸结构存在收敛速度较慢，迭代次数较多，计 算量巨大的问题。因此可以采用合适的预条件技术以减少迭代步数。所谓的预条件技术， 简而言之就是将原始的线性系统转换为另一个等价的线性系统，从而使转换后的线性系 统与原始的线性系统拥有相同的解，并且对于迭代法更加易于求解。众所周知，稠密矩 阵的特征值主要决定于积分算子，迭代解法收敛所需的迭代次数将极大的依赖于积分算 子或离散线性系统矩阵的谱特性h 剐。积分方程的预条件技术大部分以代数处理为基础， 它们主要分为以下两类：( 1 ) 设计一个易转换或易处理的预条件器；( 2 ) 设计一个稀疏 系数矩阵预条件器。各种预条件技术已被用来减少迭代步数刖。一种广泛使用的预条件 技术是系数矩阵的不完全三角( i l u ) 分解州3 。另一种预条件技术是以矩阵近似逆为基 础的方法。然而，形成这些预条件器需要额外的计算时间，预条件策略不同所需时间也 不同。因此，选用的预条件器必须使算法的收敛性有较大的改善。最简便的方法是用系 数矩阵的对角线矩阵作为预条件器。尽管这种简单的预条件器在许多情况下能减少一些 l 绪论 硕t 论文 迭代步数，但它们不能使迭代步数有明显的减少。近似分块对角阵明预条件器依靠对角 带矩阵的l u 分解使得该预条件器的复杂度为o ( n ) 。可是，该预条件技术仅在离散一 维混合位势积分方程时很有效，如果应用于二维混合位势积分方程则效果不是很好。像 对角阵或分块对角阵预条件器一样，对称逐次超松弛( s s o r ) 预条件器也能直接从系数矩 阵中得到，并使稀疏线性系统的收敛性得到比较明显的改善一3 。然而，这就无法应用 快速傅立叶变换技术加速矩阵矢量乘，导致每步迭代的计算量大幅增加。 在所有的迭代方法中，共轭梯度方法( c o n j u g a t eg r a d i e n t ，c g ) 畸7 1 应用最为广泛，与 预条件技术结合的也最为紧密，这是因为在理论上，对于对称正定矩阵， 当c g 方法迭代步数与方程数或未知数个数相同时，必将得到精确解。除此以外， 基于k r y l o v 子空间投影理论的各种算法近年来也是层出不穷，如双共轭梯度方法、广 义最小余量法( g m r e s ) ，准最小余量法( q u s i m i n i m a lr e s i d u a l ，q m r ) 等m 侧。 如何减少电场积分方程迭代求解的计算量，提高迭代过程中的收敛速度，一直是 众多研究学者所关注的问题。基于这方面的研究大致集中于如下的三个方面：基函数的 选择、优良性态电场积分方程的重新构造以及基于近区稀疏矩阵信息的预处理技术。 对于基函数选取方面，主要是采用高阶的基函数呻1 ，包括高阶的插值基函数和等 级基函数。高阶基函数的使用，可以提高解的精度，尤其是能够减少所生成阻抗矩阵的 未知量，使得对于同样的问题可以利用较少的未知量就可以获得同一般常用的低阶基函 数( 如r w g 基函数) 相同的求解精度。正是由于这个原因，高阶基函数的使用才可以节 约求解积分方程的计算量。然而，高阶基函数的使用，在减少了阻抗矩阵未知量的同时， 也使得阻抗矩阵的性态变差( 相对于低阶而言) ，不利于迭代算法的求解。 除了发展快速算法和各种预条件方法之外，通过寻求新的基函数来减少所研究问题 的未知量数目是提高计算效率的另一种有效途径。基于压缩方法的快速直接解法和预条 件方法是本文的主要研究内容，在后面的章节中将详细叙述。 1 3 本文的内容安排 本论文正文分为六章，具体安排如下： 第二章主要介绍了矩量法的基本原理，并对快速算法、矩阵低秩分解类方法做了基 本介绍，比较了迭代法和直接解法的优缺点，从而引出了m l c b d 算法。 第三章主要介绍了m d a 算法的基本原理，并阐述了m d a 中所涉及到的分层思想 和等效源的选取，由对m d a 中压缩矩阵的分析引出对矩阵的进一步s v d 压缩，从而 阐述m d a s v d 算法的基本原理，并把m d a s v d 与m d a 相比较。 第四章主要介绍了c b d 算法的基本原理及具体的操作步骤，并测出一系列的算 例来验证其j 下确性，由对c b d 的原理分析引出了m l c b d ，从而来解决大未知量的问 题。 4 硕f ：论文 基于m d a s v d 的快速直接解法c b d 第五章主要提出了一种c b d 的改进方法结合线性迭代法，提高解精度。由于 对阻抗矩阵进行c b d 求逆时阻抗矩阵经过s v d 截断，当截断精度提高时，求解的时间 和内存减少了很多，但同时却会带来解不精确的问题，这时使用线性迭代法，可以提高 解的精确度。最后通过算例验证了这种方法的的高效性。 第六章中把c b d 做成预条件，用到迭代法里面，来改善收敛性态。并与稀疏近似 逆( s a i ) 预条件进行了比较，通过算例验证了c b d 预条件的效果。 第七章中总结和回顾了本文的工作，指出了值得进一步研究的内容，提出了下一步 努力的方向。 2 矩量法方法简介硕 ：论文 2 矩量法方法简介 2 1 概述 本文中积分方程的求解即计算机算法实现是基于矩量、法l 刊( m o m ) 的，矩量法是一种 将连续方程离散化为代数方程组的方法。它既适用于求解微分方程，又适应于求解积分 方程。由于已有有效的数值计算方法求解微分方程，故目前矩量法大都用来求解积分方 程。对于不同的问题应选取不同的基函数与测试函数，采用不同形式的矩量法才能奏效。 矩量法作为求解积分方程的主要方法之一，由于所用的格林函数直接满足辐射边界 条件，无需像微分方程的解法，如时域有限差分法( f d t d ) 、有限元( f e m ) ，必须设 置吸收边界条件( 女i i p m l ) 。而且矩量法数值精度比较高，能够得出比较精确的数值解， 该方法在求解复杂结构目标的电磁散射、微带天线电流分布及辐射和微带电路的传输特 性等许多方面，有着广泛的应用。由于计算机存储量和计算时间的限制，传统矩量法仅 限于求解低频区和谐振区目标的散射问题。对于有些数值方法所要求的特殊剖分或者电 大尺寸结构等其他原因，造成计算未知量很大，这时因为需要极大的存储量而难以实现。 近十几年来，随着各种快速方法的提出和计算机性能的飞速提高，以矩量法为基础的一 些高效方法，如快速多极子方法，它可用于电大尺寸目标散射的求解。如多层矩阵分解 算法，它能弥补快速多极子的缺点，可以应用到其他的非自由空间的电磁问题。 本章将具体介绍矩量法( m o m ) 和快速算法的基本原理和相关内容，并把迭代法和直 接解法进行了比较，作为本文后续章节的基础和铺垫，为后续研究打下基础。 2 2 矩量法的基本原理 根据线性空间的理论，个线性方程的联立方程组，微分方程、差分方程、积分方 程等均属于希尔伯特空间中的算子方程，这类算子方程可化为矩阵方程求解。由于在求 解过程当中，需要计算广义矩量，故此种方法又称为矩量法。事实上，矩量法是将方程 化为矩阵方程，然后求解矩阵方程的方法，进一步分析还会看到，它实质上是内域基加 权余量法p 引。 矩量法的原理是将整个连续区域离散成许多子域，在子域中，未知函数用带有未知 系数的基函数来表示，其未知系数通常为我们要求解的未知量。因此，无限自由度的问 题就被转化成了有限自由度的问题，用冲击函数匹配法、线匹配法或伽略金测试方法得 到矩阵方程，最后通过求解这一矩阵方程获得最终解。用矩量法求解积分方程包括下列 步骤： ( 1 ) 求解区域的网格离散或目标的剖分； 6 硕卜论文基于m d a s v d 的快速直接解法c b d ( 2 ) 基函数和测试函数的选择； ( 3 ) 阻抗元素的生成，即矩阵方程的建立； ( 4 ) 方程组的求解。 在上述四个步骤中，基函数与测试函数的选取至关重要，因为求解过程中权函数和 基函数的选择的好坏与求解出来的结果的精度有很大的关系。 一般来说，在选取基函数时，要求基函数自动满足所表示的量的边界条件，并且使 涉及到的运算有相应的物理含义，并尽量减少运算的复杂性【1 8 】。文献【1 9 】还要求在电流 展开成基函数时，要求基函数要能模拟电荷量的特性。基函数可以分为全域基和分域基， 权函数可分为全域权和分域权以及点匹配，它们之间的不同组合便形成不同的方法。如 果取= 帆，即权函数等于基函数，则称为迦辽金法。本文中即采取迦辽金( g a l e r k i n ) 法。 下面我们逐步了解矩量法的相关原理及公式推导。设有算子方程 ( 门= g( 2 2 1 ) 式中g 是已知函数( 如激励函数) ，l 为算子，算子方程可以是微分方程、差分方程或 积分方程，为未知量函数( 如电流系数) 。假定算子方程的解存在，且具有唯一性， 可知矩阵方程为可逆的，于是有逆算子f 1 存在，则有厂= l - 1 ( g ) 成立。算子l 的定义域 为算子作用于其上的自变量函数，的集合，算子三的值域为算子在其定义域上运算而得 的函数g 的集合。 假定两个函数变量彳和五以及两个任意常数a 1 和口：有如下关系： 三( q 石+ 呸石) = a , l ( a ) + a 2 l ( f 2 ) ( 2 2 2 ) 则称三为线性算子。 在应用矩量法处理问题的过程中，需要求内积( 厂，g ) 的运算。内积定义为 ( 厂，g ) - i 。厂( x 培( x ) d x ( 2 2 3 ) 式中g ( x ) 是g ( x ) 的复共轭。下标d 为求解区域。 在希尔伯特空问h 中两个元素厂和g 的内积是个标量( 实数或复数) ，记为( ，g ) 。 内积满足下列关系： ( 1 ) ( 厂，g ) = ( g ，厂) ( 2 2 4 ) ( 2 ) ( a l f + a 2 9 ，h ) = 口1 ( 厂，办 + 口2 ( g ，厅( 2 2 5 ) 慨甾箩篇 亿2 q 式中q ，a 2 为标量，厂为厂的共轭量。 下面用上述算子的概念结合线性空间来解释矩量法的含义。假设有一算子方程为第 一类f r e d h o l m 积分方程 2 矩量法方法简介 硕1 j 论文 ig ( z ，z ) 厂( z ) 出= g ( z ) ( 2 2 7 ) 口 式中g ( z ，z ) 为积分内核，g 【z ) 为已知函数，f ( z 7 ) 为未知函数。首先用线性不相关的 函数z ( z ) ( n = l ，n ) 来近似表示未知函数，即： _ f ( z ) z ( z ) ( 2 2 8 ) n = 1 为待定系数，l ( z 7 ) 为子域内的基函数。为正整数，其大小根据要求的精度确 定。根据相关文献可以知道，n 取值越大，计算精度越高，但相应的计算量也越大。将 f ( z 7 ) 的近似表达式代入算子方程的左端，可以得到 吼z ( z ) 】g ( z ) ( 2 2 9 ) h = l 由于f ( z ) 用近似式表示，因此算子方程的左端近似值与右端精确值g ( z ) 之间存在 如下的关系： ( z ) = a o q l ( z ) 】一g ( z ) ( 2 2 1 0 ) n = l e ( z ) 称为余量或残数，表示计算精度。如果算子方程的加权平均值为零，即： = 0 ，( 所= 1 ，2 ，)( 2 2 1 1 ) 式中既是权函数序列，就是我们所选取的测试函数，这种方法就是加权余量法。 将上式展开便可得到典型的矩阵方程。其中基函数z 必须在算子l 的定义域内选择并且 满足边界条件。 矩量法是使数值求解问题矩阵化的处理方法，对于算子方程l ( f ) = g 的矩量法解， 可以归纳成统一的求解步骤，它包括三个基本的求解过程。 ( 1 ) 离散化过程 这一过程的主要的目的在于将算子方程化为代数方程，其具体步骤如下： 1 在算子上的定义域内适当地选择一组基函数( 或称为展开函数) 石，石，z ，它们需 要是线性无关的。 2 将未知函数f ( x ) 表示为该组基函数的线性组合，并且取有限项进行逼近，即： o ) = z 厶 ) = z ( 2 。2 1 2 ) n = ln = l 3 将式( 2 2 1 2 ) 代入式( 2 2 1 ) ，利用算子的线性，将算子方程化为代数方程，即： ( z ) = g ( 2 2 1 3 ) n = l 于是，求解f ( x ) 的问题转化为求解正的系数吼的问题。 ( 2 ) 取样检验过程 为了使f ( x ) 的近似函数 ( z ) 与f ( x ) 之间的误差相对较小，在我们可以接受的范围 内，必须进行抽样检测，为了确定未知系数口。，需要在抽样点上使加权平均误差为零， 硕士论文基于m d a s v d 的快速直接解法c b d 这一过程的基本步骤为： 1 在算子三的值域内适当地选择一组权函数( 又称检验函数) ，它们也应该彼此线 性无关。当形与厂相同的时候即为迦辽合法。 2 将既与式( 2 2 1 3 ) 取内积进行抽样检验，因为要确定个未知数，需要个方程， 因而需要进行次抽样检验，则 ( 三( 五) ，既) = ( g ，) ( m = 1 ，2 ，)( 2 2 1 4 ) 3 利用算子的线性和内积的性质，将式( 2 2 1 3 ) 化为矩阵方程，即 ( 三( ) ， = ( g ，呢) n = l 将它写成矩阵形式，即为： 】 吼】- 【g 。】 式中 【a 。】- 【k 】- 口l 口2 ： a n ( ( z ) ，彬) ( ( 石) ，) 【g 。】_ 沏= 1 ，2 ，)( 2 2 1 5 ) ( m = 1 ，2 ，)( 2 2 1 6 ) ( g ，彬) ( g ，) ( g ，) ( ( z ) ，彤) ( ( 灰) ，) ( l ( ) ，彬) ( ( 厶) ，) ( 上( 石) ，) ( 上( 以) ，k ) ( l ( f n ) ，w n ) ( 2 2 17 ) ( 2 2 18 ) 于是，求解代数方程的问题转化为求解矩阵方程的问题。 ( 3 ) 矩阵的求逆过程 一旦得到了矩阵方程，通过常规的矩阵求逆来求解线性方程组，就可以得到矩阵方 程的解 【a n 】_ 】_ l 【g 。】 ( 2 2 1 9 ) 式中【乙】- 1 是矩阵【k 】的逆矩阵。将求得的展开系数代入到式( 2 2 1 2 ) 6 0 ，便得到 原来算子方程式( 2 2 1 ) 的解 厂( x ) z ( x ) ( 2 2 2 0 ) n = l 以上所述是矩量法求解算子方程的基本过程，在矩量法的所有应用中，通常都要遵 循这个统一的过程。 9 2 矩量泫方法简介硕十论文 2 2 快速算法的基本介绍 快速算法的发展加速了由矩量法离散的电磁积分方程的求解。本节主要分析比较了 快速多极子算法( m l f m m ) ，多层快速多极子算法( m l m d a ) ，多层自适应交叉近似法 ( m l a c a ) 6 1 咱2 1 作为积分方程稀疏化的一种高效方法，快速多极子方法( m l f m m ) 不但大大加速了 矩矢乘计算，同时也大大降低了存储量。快速多极子算法的数学基础是矢量加法定理， 即利用加法定理对积分方程中的格林函数进行处理；基本物理依据为减少源对远区作用 的信息量不会明显影响计算精度，却可以使由矩量法所形成的满阵成为稀疏矩阵，从而 适用于迭代求解。其基本原理为：将所有离散单元分为若干组，组内单元之间均为近区 作用，再将所有组分为近区组集合和远区组集合，对近区组集合中单元之间的相互作用 仍采用传统矩量法进行计算，而对远区组集合则采用特殊算法。快速多极子方法对远区 组集合的处理分为三个过程：首先统一求出各源点单元到所在组中心的作用；然后求出 源点所在组中心到观察点单元所在组中心的作用；最后统一求出观察点单元所在组的中 心到个观察点单元的作用。借助这种特殊的技术，可使计算量由原来的o ( n - ) 减少到 o ( n 川z ) ，故其已广泛用于复杂目标散射、辐射等分析。 随后，m i c h i e l s e n 和b o a g 提出了多层矩阵分解算法( m l m d a ) ，是类似于f f t 的 多层m d a 算法。该算法是将阻抗矩阵的物理数学性质应用于得到有效矩阵向量积。在 m l m d a 中，矩矢乘表现为：1 ) 将整体m o m 矩阵细分为许多子矩阵；2 ) 对每个子矩 阵分别进行所需的乘法计算；3 ) 将子向量结果整理成所需要的向量。多层矩阵分解算 法( m l m d a ) 算法简单、易于实现且其关键优势是它可以在任何用m o m 离散的比波 长小很多的子域基函数和常用格林函数基础上编程。m l m d a 最初是用于解决二维问 题，但将其应用到三维问题时发现它对分段光滑平板物体非常有效和准确。然而， m l m d a 也存在以下问题：1 ) 对于一般性三维问题，m l m d a 相比m l f m a 需要更长 的计算时间和更大的存储空间，因此它不如m l f m a 有效；2 ) m l m d a 的压缩矩阵误 差较大，且当压缩矩阵维数增加时压缩误差并不趋于零。 之后的自适应交叉近似法( a d a p t i v ec r o s sa p p r o x i m a t i o n ，a c a ) 也是快速算法的一 种，其广泛用于解决大型电磁问题。该算法应用远场空间子域可减少自由度数目这一事 实，从而提高了计算速度并节约了存储空间。自适应交叉近似法( a c a ) 算法的优点在于 它是纯代数的，因此在使用时不需依赖格林函数或积分方程。即计算速度可通过一些线 性代数操作得到提高，如q r 分解q rf a c t o r i z a t i o n ) 、奇异值分解( s i n g u l a rv a l u e d e c o m p o s i t i o n ，s v d ) 、l u 分解( l uf a c t o r i z a t i o n ) 等。同时自适应交叉近似法( a c a ) 很容易与m o m 编码整合。通过数值计算，还可以发现自适应交叉近似法( a c a ) 算法很 稳定，同时它只用了m o m 算法所需存储空间和总c p u 时间的- d , 部分，就可以得到非 1 0 碗士论空 筚于m d a s v d 的恍速直接解 圭一b d 常精确的结果。a c a 算注现已成功运用到了静态低频问题中，最近，a c a 也被用于天 线辐射和r c s 计算。 本节的目的是在对各个快速算法进行分析后，介绍一种新的改进的多层快速多极于 算法( m l m d a ) 算法，即m d a - s v d 算法。该算法引入了等效源并对矩阵进行奇异值分 解( s i n g u l a rv a l u ed e c o m p o s i t i o n ，s v d ) 进步压缩。该算法使得随着压缩矩阵维数增 加时，由压缩矩阵引起的误差趋于零；同时，其在处理一般性性三维问题时能解决效率 和准确性问题。m d a s v d 算法的计算时州和内存需求近似多层快速多极子算法 ( m i 。m d a ) ，多层自适应交叉近似法( m l a c a ) ，且该算法在较短时问内可获得比a c a 和m l f m a 少一个数量层的矩阵压缩误差。与多层自适应交叉近似洼( m l a c a ) 、多层 快速多极子算法( m l m d a ) 一样m d a s v d 算法可在通常格林函数的现有m o m 编码基 础上实现，但m d a - s v d 算法对于分析平板或分段光滑平板物体如印刷天线要有效得 多。 2 3 迭代法与直接求解方法比较 对于积分方程，最终都可以转化为形如 ax=b ( 3 1 ) 矩阵方程的形式来求解。求解矩阵方程一般分为直接解法和迭代解法两种。直接解法是 指基于待求矩阵直接分解的一种代数矩阵方程组的求解方法。直接解法的优点非常多， 首先，只要分解过程稳定，直接解法就能提供高可靠性以及高精度的解。 其次，尽管选代解法在很多的工程问题上得到了非常成功的应用，但是就求解矩阵 方程盼“鲁捧性”来说，它仍然不能与直接解法相比拟。迭代解法依赖于矩阵的性态。如 果性态不好，则收敛率是不可预测的，而直接解法则避免了这个问题。 第三，对于多个右边激励项的问题，由于直接解法只要求对系数矩阵进行一次分解， 并且这种矩阵的分解信息可以重复利用，使得对于多个激励项的求觯问题变得更简单。 例如在散射体单站r c s 的计算中，对于不同的入射角度，会形成成百上千个代数矩阵 方程。而这些矩阵方程的系数矩阵具有相同的形式，只是右边的激励向量因入射角度的 不同而不同。 然而，在现代电磁特性如散射及辐射分析中，在对线性方程组求解时未知量较大， 即使目前的高性能计算机仍无法直接快速计算。最近，矩阵低秩分解类方法得到了国际 的广泛重视。近年来，随着多层矩阵分解算法( m l m d a ) 等压缩方法的出现，大未知 量问题得到了有效的解决，从而使得应用积分方程方法求解超大型的电磁散射问题成为 可能，利用压缩方法可咀减少矩阵在计算机中的存储量和计算复杂度，这些新算法有极 大地扩大了直接解法在m o m 的应用。 3 多层矩阵分解算法( m d a ) 的基奉原理硕j ：论文 3 多层矩阵分解算法( m d a ) 的基本原理 3 1m d