（电磁场与微波技术专业论文）电磁散射中迭代加速算法研究.pdf

硕士论文 电磁 散射 中迭代加速算法研究 ab s t r 8 c t the el e c tr o m a g n eticsc a tt ering and口 d l ation of3 dcom p l ex targ ets ll a v e理 tt r a c t ed m uch morea tt e n t i on i n eng i n eering app l i c atio ns. r e cen tl y ， i ntensi ve in v e st i g at i ons h a v e 卜 哭 n donetofi ndn is t and accu ra t e n umeri喇 m e t h o d s tosolv e suchp r o b l e m s . the m ethod o f m omellt ( mo m) h asb e e n 初del y 理 把 d toana 】 y s i s th e s catt e ri n g and r a d 1 atio n pr o b l e m s . h o wever， the conve n t 1 0 n almo mr equl re s a d i s c r e t 说 at l ono f t y p l c al ly ten p e r wav e l engt 玩 w hi c hgen e ra t e s al ar g en umber ofl lj 止 n o wnsin】l a n d l i ng lar ge-s c al ep r o b l e ms for a des ir e d ac c urac y . there 眼 t hr e e w a y s toa ttac k s u c h a troubleinm 0 m . t 七 e fi istwayis to dev e l o psom efi 巧 tal g oril hl ns ， fo rex aj 爪 p l e ， 阮 m u l ti l e v e l五 比 tm u l t i pol emeth od ( ml f m m) ， toacc e l e r ate th e m a t ri x v ector m u lti p l y . 丁 b e se cond way i s to6 n d s 0 r n e n e w b a s i s 加 11 ctio ns， i n cl u d i nghi gho rd erb asis fu n ct i o ns. the l ast w a y i s tos tudy the e ffic i ent i t e n ” i ves peedin gal gori t hr nstor educe the conditi on n u m ber ofthe o pera t o r eq场 at i o ns. thi s di s s e 川 刁 t i o ni s fo c us o nthe l a t er幻 刀 oa p p ro ac h e s andth e i r com b i nati o n初ththe ml f mm. 刀， e ma i ncon t ri but i o ni s as fol l o ws : l d e ta 1 1 ed workb asbeen done fo r the n ume ri c ali m p 1 e m e n t at i0 no f m o m toso l v e p ra c 石 cal p ro bl elns . w。 抽v es tu d ied th ese lecti on of b 出 犯伪 刀 ctio ns ， the re sultof 加伴山 川 优m 田 五 x and s o u n 笼 .atthe s ame t 如e ， we 1 n tr edu c e th e i t e ra t 1 veso1 utio n o f l ar g e d e nse com p l e x l in e ars y stems and p r e c o n d i ti 0 n l n g tec腼q u es 2 .an e wki n do f hi ghero rder hi erarc hi c alb as i s fu n ctions i s p r o p 0 s e dto朋a 】y s i s the e l e c tr o m a gne t i c s c a 廿 e ri n g and radi atio n o f e l e c 币司一 l ar g e t ar g ets. the n ew m u l t i 一 幼d p r e c o n d i t i o ni ng t e c 肠 吐 q uei s p r o pos edtoa c c e 1 e r a t e th e it er a t i o n o f th e ml f m mw 1 t h the hi g h er o t d e rhi e r a r c h i 司 b as i sfu n ctio n s .a tt h e义 in l eti m e ，th etwo 一 鱿 叩 p r 创 为 n di t i o 苗 n g i s p r o pos edbyp r e condi t i o ni n g and m u l t i 一 ghd t e c hoi q ues 3 .thehi g h e ro r d er i n t e 耳 幻 1 atory v e c to rb as i sfi u 1 c t io ncom b i n ed with ml f mm i s 即 p l i ed toa n a 】 y s i s the e l e c t r o m a gnet i cs c a ti e ri ng andradi atio nofe l e c t ri cal一 i ar g e 恤g ets. the n e ar 一 fi e l d prec o n d i ti 画n g tec俪q u e and th e 幻 刀 0 一 s t e p p r e c o n di ti o ni n g are p r o pos ed to 毗e l e ratethe c o n v erge n ce o fthe m l f m m 硒th th ehi gh o rd er in te rl x ，l atoryv ecto r b as i s fij ll c t i o n . 4 .we a p p 1 y th e mrpr ee o n di ti o n ertoth e m l f m mfo r th e e l ec t r o m a gne t i c sc a tt e ri n g . 11 叩 沐 叮 s th atth e a p p l i c at io n o f th e m r厂 e con d i ti o n ers peed s upth e i terat i v e s o l ver c o n v e r g e n c e 硕士论文电磁 散射中迭代加速算法研究 k e 州o rds : e l e c tr o m a gnet i c s c a tt e ri n g ， m ethodo f m o m ent ， m u l ti l e v e l fa st m u l t i p o lem etho d ， ite r a t l ve sol vers ， p r e c o n d i ti o n i ng te c hni q u e s ， m u l t i ghd m etho d s ，1 w 。 - s t e p p re con di ti o ni ng，m u l ti re solu ti on( m 双 ) p r e c o n d iti o nging 声明 本学位论文是我在导师的指导下取得的研究成果， 尽我所知， 在 本学位论文中， 除了加以 标注和致谢的部分外， 不包含其他人已经发 表或公布过的研究成果， 也不包含我为获得任何教育机构的学位或学 历 而使用过的 材料。 与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确 的说明。 研究生签名:年月日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档， 可以借阅 或上网公布本学位论文的部分或全部内 容， 可以向有关部门 或机构送 交并授权其保存、 借阅或上网公布本学位论文的部分或全部内 容。 对 于保密论文，按保密的有关规定和程序处理。 研究生签名:年月日 硕 七 论文电磁散射中迭代加速算法研究 1 . 绪论 1 . 1 研究工作的背景 1 8 6 4 年麦克斯韦奠定了经典的电磁理论， 提出了电磁场普遍规律的数学描述: 电磁场基本方程组伽 ax舰n 方程组) 。 所有的电磁场问题都可以归结为m ax蛇n 方 程组在各种边界条件下的解.因此，如何获得 m axw ell方程组在各种边界条件下 的精确解就成了对电磁场理论与工程问题进行分析的基础。 随着近代科学技术的发展，电磁场有效控制和利用问题已经日益成为许多学 科、工程技术部门研究的课题.但是，由于实际电磁场问题的复杂性，相当长时 期以来，从解析方法着手进行的分析所取得的进展不大，难以获得满意的分析结 果.六十年代开始，计算机和计算技术的飞速发展对科学、生产、生活等各个领 域都产生了深刻的影响，为数值分析的广泛应用奠定了基础。自 从计算机引入微 波工程和电磁场领域之后，给工程电磁场问题的理论分析和工程设计带来了新的 变化，新的计算思想和方法不断涌现，特别是最近一段时期，电子计算机的计算 速度与容量不断增加，数值计算方法得到越来越广泛的应用。高速电子计算机的 问世，给电磁学的研究开辟了新的前景，改变了过去一些传统的研究方法， 使得 从前被人们认为完全超出解析范围的许多问题能进行求解。 数值方法包含着一个离散化的问题，因为无论在微分方程或积分方程中，微 分或积分所作用的函数都是连续函数，而电子计算机所能处理的函数则是离散函 数。数值方法所做的工作就是将微分方程化为差分方程，或将积分方程的积分化 为有限求和，从而建立代数方程组。在数值方法应用于电磁场领域的短短3 0 多年 里，工程电磁场问题的理论研究和分析方法取得了前所未有的进展，并获得了大 量 有实 用 价 值的 结果。 各 种数 值计 算 方 法 应 运而生， 例如: 有限 元 法 川 121 、 有限 差 分 法 131 、 矩量 法 i- i0l 、 格 林函 数 法、 边界 元 素 法、 谱 域法、 几何 绕 射 理 论、 奇 点 展 开法、 变分法等。 1 . 2 研究工作的现状和意义 电磁场数值分析是根据m axwen方程， 利用适当的边界条件确定所关心区域或 物体内的电磁场或电流分布，进而求出所需要的物理参量。回顾计算电磁学发展 的历史，早在1 8 64年，m axw e n 已用偏微分方程的形式给出了电磁波现象中电场 和磁场的统一表达式，他的研究成果被称誉为19世纪最显著的科学成就之一。而 求解电 磁场问题的方法， 归纳起来可分为三大类， 其中每一类又包含若干种方法， 第一类是 解析法:第二类是数值法;第三类是半解析数值法. 硕士论文电磁散射 中迭代加速算法研究 经典的数学分析方法是近百年来电磁学学科发展中一个极为重要的手段。解 析法包括建立和求解偏微分方程或积分方程。严格求解偏微分方程的经典方法是 分离变量法:严格求解积分方程的方法主要是变换数学法。解析法的优点是: ( 1)可将解表示为已知函数的显式，从而可计算出精确的数值结果: (2 ) 可以 作为近似解和数值解的检验标准; (3 ) 在解析过程中和在解的显式中可以 观察到问 题的内 在联系和各个参数对数值 结果所起的作用。 用解析法求解电磁场的边值问题，有时可以得到精确的数据结果，并能根据 参量的变化，推断出 解的变化趋势。但是这种方法所能够解决的问题不多，满足 不了不断增长的工程方面的需要。于是人们就致力于研究求解复杂边值问题的近 似方法和数值方法。 麦克斯韦早在1897年就尝试用积分方程的数值解来计算矩形 金属板间的电容量。在计算机出现以前，应用数值法求解更复杂的边值问题并非 易事， 但随着高速度大存储量计算机的发展，数值方法的应用日益广泛，过去看 来难解的问题，现在已能比较容易地求得足够精确的数值解了。 数值方法一般可分为两大类，一类为积分方程类方法，包括矩量法( m o m ) 、边 界元法( b 阴) 等;另一类为微分方程类方法，包括时域有限差分法( f dtd)、有限元 法( f e 团等。 在微分类数值方法中， 其未知数理论上讲应定义在整个自 由空间以 满 足电磁场在无限远处的辐射条件。由于计算机只有有限的存贮量，人们引入了吸 收边界条件来等效无限远处的辐射条件，从而使未知数定义在有限的空间内，如 理 想 匹 配 层( 附 l) 吸 收 边界 条 件 11 1 . 因 此， 微分 方 程 类方 法 所 涉 及 的 未 知 数 数目 是很庞大的。另外，由于偏微分方程的局限性，使得电磁场在数值网格的传播过 程中形成耗散误差。所研究的区域越大，耗散误差的积累越大。所以，对于大尺 寸目标，为了保证计算结果的精确性，人们不得不采用更精细的网格来剖分。数 目庞大的未知数和数值耗散问题使得微分类方法在分析大电磁目 标时遇到了困 难。 与微分类方法相反，积分方程类数值方法中的未知数仅定义在源上，而不是 整个空间。因此，积分类方法所产生的未知数数目比微分类方法少很多。另一方 面，由 于格林函数的引入，电磁场在无限远处的辐射条件己 解析地包含在积分方 程类方法之中，所以 其数值耗散误差可以 减至很小。 然而， 积分类方法 ( 如矩量法) 所产生的 矩阵为一稠密矩阵， 不可避免的要 面临矩阵方程求解的问 题。关于矩阵方程的求解， 分为直接解法和迭代解法。 直 接解法， 包括高斯消去法、 克劳 特( c rout) 分解法、 乔累斯基( c h olesk y ) 分解法等， 它 们的 计 算复 杂度为o(n ， ) 。 而 迭代 解法， 包 括高 斯一 赛 德尔( g auss 一 s eidel) 迭 代 法、 逐次 超松弛( s o r)迭代法， 共 辘梯度 法( c g)等， 它 们的计算复杂 度为口 ( n ， ) ， 硕士论文电磁散射中迭代加速算法研究 这里 “ n”是未知数的数目 匆 ， tzj。因此， 对于中 等规模的方程组及带型或 稀疏方 程组，由于直接法所具有的准确性和可靠性，因此经常选用此法求解.而对于较 高阶的方程组，特别是对应于当偏微分方程数值求解呈现大型稀疏方程组时，由 于直接法计算的代价较高，且因舍入误差影响的存在，使得迭代法更具有竞争力。 其优点不仅是程序编制较为简单，而且显著地节省存贮单元。因此，在求解大型 线性系统中，迭代解法应用更为广泛.但与直接解法相比，迭代解法最大的缺陷 就是缺乏 “ 鲁棒性” ， 容易出现不收敛和收敛慢的问题。因此在实际工程应用中受 到了诸多限制. 为克服迭代解法收敛耗时的缺点，主要有两种解决途径。( 1)迭代解法的每一 步迭代中， 矩阵矢量乘是主要的运算， 其计算量正比 于o(n 2 ) ，因此，降低迭代 方法的 矩阵矢量乘的计算复杂度，减少每一步的迭代时间必将节省大量的计 算时 间;( 2)减少迭代收敛所需的步数，同样能够节省许多计算时间。 第 一 种方 法主 要有 两种实 现途径: 一是基 于 快速 傅里叶变换 ( f 阿) 112， 二是 基于快速多极子方法( f m m ) 113 一201。本教研室在这方面己经做出了卓有成效的工作。 第二种方法的实现主要是采用预条件技术。 无论mlf 朋还是c g 一 f ft方法， 虽 然它们每次迭代的计算复杂度都是o(n l og构 ， 但对于 微波集成电 路电 大尺寸结构 存在收敛速度较慢， 迭代次数较多，计算量巨大的问 题。因此可以采用合适的预 条件技术以减少迭代步数. 所谓的预条件技术，简而言之就是将原始的线性系统 转换为另一个等价的线性系统，从而使转换后的线性系统与原始的线性系统拥有 相同的解，并且对于迭代法更加易于求解。众所周知，稠密矩阵的特征值主要决 定于积分算子， 迭代解法收敛所需的迭代次数将极大的依赖于积分算子或离散线 性系 统 矩阵 的 谱 特性 阳 姻。 积分 方 程的 预条 件 技 术 大 部 分以 代数 处 理为 基础， 它 们主要分为以下两类:( 1) 设计一个易转换或易处理的预条件器;( 2) 设计一个 稀疏系数矩阵预条件器。各种预条件技术已 被用来减少 迭代步数121 。 一种广泛使 用的 预条 件技术是系 数 矩阵的 不完全 三角 ( i lu) 分 解 122 一 】 。另 一种预条件技 术是 以矩阵近似逆为基础的方法. 然而，形成这些预条件器需要额外的计算时间，预 条件策略不同所需时间也不同。因此，选用的预条件器必须使算法的收敛性有较 大的改善。最简便的方法是用系数矩阵的对角线矩阵作为预条件器。尽管这种简 单的预条件器在许多情况下能减少 一 些迭代步数，但它们不能使迭代步数有明显 的减少251。 近似分块对角阵【zlj 预条件器依靠对角带矩阵的lu分解使得该预条件器 的复杂度为0 ( n ) . 可是， 该预条件技术仅在离散一维混合位势积分方程时 很有效， 如果应用于二维混合位势积分方程则效果不是很好. 像对角阵或分块对角阵预条 件器一样，对称逐次超松弛( ssor) 预条件器也能直接从系数矩阵中得到，并使稀 疏线性系统的收敛性得到比 较明显的改善125 11 29。 然而， 这就无法应用快速傅立叶 硕士论文电磁散射中迭代加速算法研究 变换技术加速矩阵矢量乘，导致每步迭代的计算量大幅增加。 在 所有的 迭 代方 法中， 共 扼 梯 度 方 法( c o n j u g a t e g r a d i e n t ， “) 13 0 应 用 最为 广泛，与预条件技术结合的也最为紧密，这是因为在理论上，对于对称正定矩阵， 当c g 方法迭代步数与方程数或未知数个数相同时，必将得到精确解。除此以外， 基于k rylov 子空间投影理论的各种算法近年来也是层出不穷， 如双共辘梯度方法 ( b i c o n j u g a t e g r a d i e n t ， bcg ) 、 广义最小余量法( g e n e r a l i z e d m i n i m a l r e s i d u a l ， 洲r e s ) ， 准最小 余量法( q u s i 一 m i n i m a l r e s i d u a l ， 朋r ) 等13 ， 1 132 。 这些成果中 较为 成熟的己 被融进商业软件mat 以b6. 5 ，直接为我们所用。 除了发展快速算法和各种预条件方法之外，通过寻求新的基函数来减少所研 究问 题的 未知量数目 是 提高 计算效率的另一种有效 途径。 通过高阶 基函数 13 3 刊的 使用，在保证精度的前提下大大减少未知量的数目。快速算法和各种预条件方法 的结合以 及对高阶基函数的研究是本文的主要研究内容，在后面的章节中将详细 叙述。 1 . 3 研究内容 在强烈的工程需求背景和当今计算电磁学发展的趋势下，本文开展了对高阶 基函 数加速算法，以 及多分辨预条件技术的 研究。 本文研究内 容主要包括: ( 1) 详细介绍了矩量法的基本原理以及具体实施，包括积分方程的选取、基 函数的选择、对积分方程的离散、以及右边项的生成、矩阵方程的求解和预条件 技术等。 (2 )提出了一种新的高阶叠层矢量基函数应用于矩量法中，并与 m l f 翩 结合 用于分析电大目 标的散射问题。 在此基础上， 发展了一种基于f g m r es方法的多重 网格迭代算法改善收敛效果。高阶结合叠层矢量基函数基础之上，结合预条件技 术以 及多重网格技术提出了基于特征谱的双步预条件技术。 ( 3) 将高阶插值型矢量基函数结合 m l f 翩 分析电大目 标的电磁特性，针对高 阶基函数形成的矩阵条件数变大，致使收敛变慢的问题，发展了稀疏化近场矩阵 预条件技术以 及双步预条件技术加快基于高阶插值型矢量基函数的 m lf朋 的收敛 速度。 (4 )对于物体表面比较平坦的结构采用多分辨预条件技术结合 m l f 朋 进行电 磁散射分析，加快了收敛速度. 硕士论文电磁散射中迭代加速算法研究 2 . 矩量法的基本原理和实现 自 r o g e r f . h arr i n g t o n于1 9 6 8年在其所著( f i e l d c o 叩u t a t i o n b y m o m e n t m e t h o d s ) 一书中系统叙述t矩量法 ( m e t h o do fm o m e n t ，简称m o m )在求解电磁场 问题中的应用以来，矩量法己 经广泛的用于各种夭线辐射、复杂散射体散射以 及 静态或准静态等领域。矩量法精度高、所用格林函数直接满足辐射条件，无须像 微分方程法那样必须设置吸收边界条件。但是由于矩量法产生满阵，其存储量为 . o( 矿) ， 矩 阵 求 逆 的 复 杂 度 更 达 到o( n ， ) ， 所以 对 于 高 频 区 电 大 尺 寸目 标 的 求 解， 往往因为需要极大的存储量和很长的计算时间而不能在现有的计算机资源条件下 实现。矩量法是我们以后研究共骊梯度快速傅立叶变换方法、快速多极子方法的 基础，因此，对矩量法进行深入系统地研究是本文研究工作至关重要的一步. 本章从矩量法的数学原理出发，按照矩量法数值求解的基本步骤来讲述矩量 法。在矩量法的实际运用过程中， 最关键的部分主要是基函数和测试函数的选取、 离散矩阵方程的快速求解技术。限于篇幅，我们仅对本文用到的基函数形式、离 散矩阵方程的求解过程做详细介绍，其余部分一带而过，感兴趣的读者可以参考 相关文献。 2 . 1 矩量法的基本原理 对于实际的电磁散射问 题， 积分方程都可以用下面的算子方程来描述 l . f= 9( 2. 1 . 1 ) 式中l 为 线 性 算子，9 是己 知函 数 如激励函 数，f 为 待定未知函 数如电 流。 算子乙 的定义域为 算子作用于其上的函数f 的集合， 算子l 的值域为算子在其定义域上运 算而 得的 函 数9 的 集 合。 一般要获得方程 ( 2 1 . 1) 的精确解是非常困难的， 除非l 为非常简单的线性算 子 为 了 获 得 方 程(2 . 1 . 1)的 数 值 解 ， 将f 在l 的 定 义 域内 展 开 成 不 ， 人 ， ， 几 的 线性组合表示成 ， 二 氛 ( 2 . 1 . 2 ) 其 中 ， 气是 待 定 的 标 量 系 数 ， 天为 基函 数 。 如 果n 一00 且 儿 是 完 备 集， 则 方 程 (2. 】 .2) 是精确的。由于计算机容量有限，n必须有限.此时方程 (2. 1 .2) 的 右 边 项 是 待 求函 数f 的 近似 解。 将 式 (2 . 1 .2) 代 入式(2 . 1 . 1)， 再由 算子l 的 线 性 性质，可以得到 艺气 l. 人 二 9 ( 2 . 1 . 3 ) 硕 十 论文电磁散射中迭代加速算法研究 为 了 求 解 方 程(2 . 1 .3)以 确 定 未 知 系 数气， 选 取 一 组 测 试 函 数 wl， 叭， ， 叭 ， 用每个测试函数跟方程 ( 2 . 1 . 3) 做内积，由算子l 的线性性质，可以得到 艺州嗽， l. 劲钊呱， 9 ) 上 述 方 程 可 以 写 成 矩 晖 雍式 ( m= 1 ， 2 ，. ， n) ( 21 . 4) 2 a = 9 ( 2 . 1 . 5 ) 其中， ( 9 ) = z 二 1 ( 2 . 1 . 6 ) ( 2 . 1 . 7 ) 如果矩阵 2 1 非奇异， 那么未知 量 a便可求出 毛 a 卜 2 丁 ， 毛 9 ( 2 . 1 .5 ) 这样未知函 数f 便可由 式 ( 2 . 1 . 2) 获得。上述便是矩量法完整的离散化过程。 2 . 2 积分方程的离散 在矩量法的描述中，对算子方程离散实际上就是对未知函数的离散。在实际 电 磁问 题中， 未知函 数就是散 射体 的电 流分布函 数入司。 对积分方程的 离散就是 把电流分布函数展开成基函数的形式，因此离散积分方程的第一步就是选取基函 数和权函数。基函数和权函数的选取具有相当的灵活性。于是在选取它们时便要 考虑方便与否，讲究精度的要求，比较效率高低，以及考虑阻杭矩阵的求解难易 等因素，下面就这些方面进行阐述。 2 . 2 . 1基函 数和权函数的 选择 为了使矩阵方程 (2， 1 . 5) 的解更接近原问题式 ( 2 . 1 . 1) 的解，理想的基函数 和权函数应满足以下要求:( 1) 可以获得高精度的解;( 2) 阻抗矩阵元素的求解 要容易实现:( 3) 未知量数目 要尽可能小;( 4) 生成的阻 抗矩阵要有好的条件数， 具有对角优势。但是，上述几条原则又是相互矛盾的，不能全部符合要求，必须 有计划的进行取舍。 一般权函数的选择就决定了测试的方式。对应于点匹配、线匹配、伽略金匹 配方法，相应的权函数可取为点脉冲、线性函数、与基函数相同的函数。从实施 过程的难易程度而 从计算效果上考虑， 言，点匹配最方便，线匹配其次，伽略金匹配最繁杂。但是， 伽 略 金 匹 配 方 法 最 稳 定 。 下 面 重 点 介 绍 基 函 数 的 选 取 硕士论文电磁散射中迭代加速算法研究 通常，基函数分为两类:一类为全域基函数，一类为局域基函数。所谓全域 基函数是指在算子l 定义域内的全域上存在的一组基函数， 这类基函数在解决某些 特殊问 题时比较有效， 但对于一般的问题，这类基函数很难构造，因而很少使用。 近期对全域基函数的研究有了一些新的进展和应用。 目前通常使用的是局域基函数。局域基函数一般是按照下列方式构造的:先 将整个求解域分成很多子区域，然后在每个子区域中选择若干位置上的函数值作 为参数，用多项式插值得到整个子区域的函数，最后整个区域待定函数的表达式 便由子区域函数叠加而成。不难看出，局域基函数的构造关键在两点:一是如何 选择子区域形状，二是如何选择插值函数。子区域形状多种多样。一般来说，如 果求解域是面，则三角形较为通用、方便:如果求解域是体，则四面体较为通用、 方便。这是因为，任何一个面都可用三角形来剖分，任何一个体都可用四面体来 剖分。针对不同的剖分形式，也有不同的基函数，例如基于矩形网格剖分或者基 于三角形剖分的基函数:在具体的剖分情况下又有不同的数学形式，例如定义在 曲面或参数曲面上的高阶基函数等。 2 . 2 . 2方程的离散形式 以分析理想导体散射问题为例，基函数确定以后，理想导体表面的未知的电 流函数就可以表示成一组基函数的线性叠加: 入 弓 = 艺 人 众朴 ( 2 . 2 . 1 ) 把式 ( 2 . 4 . 6 ) 代入式 ( 2 . 3 . 1 6 )的混合积分方程 ( c f i e ) ，我们得到 c f i e的离 散形式: 。 x ; 、 共 咔 万 .、一卜 一 罕。 二 ，v 蕊工 v ，4 艺 人 元 ( 万 ， 9 (声 ，产 ， 21刀es、 . 凡止 艺几 元 ( 产 ， )9 (万 ，声 专 ( 1 一 a ) 2 艺 几 又 ( 司( 2 2. 2 ) = 矛 【 a 厂 (劝 + ( 一 a ) 。 ” x 万 (司 ，声 e s 2. 2 )平面r wg基函数 对任意形状的理想导体表面， 使用三角形剖分可以 非常简单、有效地刻画出 物体的局部精细特征。 广泛使用的r wg基函数 对于三角形网格，r a o ，甲 i l t o n ，g l i s s o n 提出t至今仍被 r w g 基函数定义式为: 硕士论文电磁 散射 中迭代加 速算法研究 声 。 军 几( 朴=声 。 万 ( 2 . 2 . 3 ) f仁口 之 加” 风几 生城生试。 一十、 其中，几 十 ，瓦 为第m 个基函 数 所 对应的 两 个相 邻三角形，几 为公 共边的 长度. 凡十 ， 心一 分别 为 三角形几 ， 瓦 一 的 面积. 戒，八分 别为 三 角 形几 伞 的 顶点 指向 该 三角形上的场点、 三角形几一 上的场点 指向 该三角形顶点的矢量( 见图2 . 2 . 1 所示) . 图2 . 2 . ir w g 三角形对及其几何参数 由此我们可以得到 r wg 基函数的散度为 r 任 几寸 r 任 兀 ( 2 . 2 . 4 ) -礁。一式 r口 the rs 护!1.、，月.阵. 介 -几 早 由 式(2 . 2 . 3 ) ， 可 见， 在瓦 冲 ， 几 一 上电 荷 密 度 均 匀。 两 相 邻 三 角 形的总电 荷 为零，并无线电荷的堆积，保证了 相邻三角单元两边电流的连续性。 阻抗矩阵的生成 混合积分方程离散之后，接下来就是用所选的测试函数对离散的方程进行测 本文采用伽略金测试方法，即所选的测试函数和基函数相同。将测试函数 介jo 2.试一 几( 司对 式( 2. 2. 2)两 端 进 行 测 试 ， 我 们 可 以 得 到 混 合 积 分 方 程 的 矩 阵 形 式 【 2 【 1 1 = 【 v l ( 2 3. 1 ) 硕 士论文电磁散射中迭代加速算法研究 z 为阻 抗矩阵，i 为代求电流系数， v为右边激励向 量。 2的元素表达式为 、 = 、卜 ，卜 。但兰 上 里* 、 v 、 套 :.; ( 。9(万， ，心 元 (秘 、。 矛二 蕊工 大 ( ， 一 。元 ，ds ( 2 . 3 . 2 ) 叮 ( 1 一 “ ) 2 ; (声 ， 元 (万 ) r.esl，l .占 + 右边激励向 量【 v的 元素表达式为 嵘 = 工 f a 万 (朴 + (， 一 a )。 ” x 万 (万 ) 元 (f )“2 ， ， ， 实际上，传统阻抗元素计算方法是对应于每一个基函数、权函数而言的。对 于平面rwg 基，每个三角形( 边缘三角形除外) 均对应于三个基函数、三个权函数. 这意味着采用传统阻抗元素计算方法时， 对给定的一个场三角形和一个源三角形， 共有九个阻抗元素与之对应，所以在该源三角形上的面积分要计算九次。显然， 当三角形贴片数目很多时，阻抗元素的计算效率将很低。为高效计算阻抗元素， 我们采用平面三角对组合计算来代替传统的边对边阻抗元素计算方法。平面三角 对组合计算针对给定的一个场三角形、一个源三角形开展。对给定的场三角形、 源三角形，在源三角形上的面积分只计算三次，因此大大提高了阻抗元素的计算 效率。 至此，我们己从理论上得到了阻抗矩阵， 但是实际上要通过数值方法得到精 确的阻抗矩阵元素，还需要处理由于场点和源点重合而带来的积分奇异性，以及 当场点和源点非常接近时所引起的积分近奇异性问题。这里就不再详细展开了。 2 . 4 矩阵方程激励源的生成 对电磁散射问题外加源一般是平面波。为了方便定义极化方向，我们将入射 电 场分解为。 和护 方向 的 分量表示: e， ( 弓= ( 凡已+ 凡或 )e 片 了( 2 . 4 . 1 ) 其中传播方向定义为 不 = 成( 2 . 4 . 2 ) 坐标位置矢量为 r=工 龙 十 州十器( 2 . 4 一 3 ) 单位矢量定义为 硕士论文电磁散射中迭代加速算法研究 吞= x c o s 只 c o s 喊 + 夕 c os o， s in 碑 一 z s i n o， ( 2 . 4 . 4 ) 护 ， = 一 x s i n 碑 + y c o s 碑 ( 2 滩. 5 ) = x s in叹cos 喊 + y s in叹 s in或 + : cos 况 ( 2 4石) 2 . 5 阵方程的求解 2 . 5 . 1 广义最小余量法 ( 以 祝邓) 通过矩量法把表面积分方程离散化为阻抗矩阵方程后，面临的问题是如何求 解这一矩阵方程。对阻抗矩阵方程的数值求解有直接法和迭代法之分. 直接法主 要有高 斯消 元法、 lu分 解法、 奇异 值分 解法( s v d) ， 它们的 计算复杂度为0 ( n ， ) 。 由于直接法所具有的准确性和可靠性，因此对于较小规模的方程组经常选用直接 法求解。而迭代解法，包括雅可比迭代法 ( j acobi ) 、高斯一 塞德尔迭代法 ( g a u s s 一 s e i d e l ) 、超松弛迭代法 ( s o r ) ，共扼梯度法 ( c g ) ，广义最小余量法 ( g m r es) ， 双 共 辘梯 度 法等 等( bi 一 ) 州日 ， 它 们 的 计算 复 杂 度 为。 ( n ， ) ， 这 里 “ n” 是未知数的数目。对于较高阶的方程组，由 于直接法计算的代价较高，且因舍入 误差影响的存在，使得迭代法更具有竞争力。 其优点不仅是程序编制较为简单， 而且显著地节省存贮单元。因此，在求解大型线性系统中，迭代解法应用更为广 泛。本文的求解方法如没有特殊说明都是指g m r es算法.这里我详细介绍了g m r es 算法。 设a是一个n 阶矩阵，若采用广义最小余量法求解如下线性方程组 ax =b 其执行过程具体如下: 1 . 开 始: 选 择 k rylo v 子 空 间 的 初 始 值xo 和 维 数爪 。 使 所 有 的 气 ， 初 始 化 为 零 。 2 . arn o l d i 过程: ( a ) c o m p u t e 几 = b 一 axo， 刀 = 1ro llz ， vl = ro / 刀 ( b )forj = 1 ， ， m d o .c o m p u t ew 片a vj; ( 25 . 1 ) 定义一个( m+ 1 ) x m 矩阵万 。 硕士论文电磁散射 中迭代加 速算法研究 . f o ri = 1，二 ， j ，d 。 h， ， ” ( w， vj ) w := w 一 杠 .， vl e n d d o . c o m p u t e e n d d o ( c ) d e f i n e气:= 如.， = 0 叫 2 ， i vl ， ， 、 b 十 ， = ” / 气 ， l.j 3 . 求 得近似解 : comput 任凡二 xo+ 犷 ， 入 其 中 、 = arg min， ilne.一 瓦 川 ， ， 。 一 l ，。 ， ，0r 其 中、 = arg min， 内 一 而2 ， 。 = l ，0 ， ，0t 4 . 重复: 如果满 足精度要求则 停止; 否则， 使凡= 孔并 返回 到2 . 迭代方法中主要运算量集中在矩阵矢量乘部分，可以 通过共辘梯度快速傅立 叶变换方法和多层快速多极子方法加速矩阵矢量乘，使计算复杂度降为 0 ( nlo g 的 0 2 . 5 . 2 . 1 预条件技术的基本原理 与直接解法相比，迭代解法最大的缺陷就是缺乏“ 鲁棒性” ，容易出现收敛慢 甚至不收敛的问 题，因此在实际工程应用中受到了 诸多限 制。 对于电 大尺寸复杂 目 标的电 磁特性问题通常离散后得到的矩阵方程的阶数将达到上万以上，采用迭 代法往往需要迭代几千步以上才能达到收敛精度，虽然采用了快速傅立叶变换 ( f 盯) 和多层快速多极子技术可以降低计算复杂度， 但是达到收敛所需的迭代步 数并没有减少，因此收敛缓慢的缺陷并没有得到改善。然而通过 “ 预条件”技术 能够同时提高迭代解法的计算效率与鲁棒性。这也导致了各种预条件技术的研究 一直是计算电磁学的热点之一。 迭代算法的收敛速度与矩阵a的特征值的分布有关。 当a的特征值聚集在某个 值的附近时 ( 称才的谱是聚集的) ，迭代法的收敛速度就快;否则，迭代法的收敛 速度就慢， 且数值稳定性也较差【刘 。 为 提高 算法的收敛速度和改进它的数值性能， 硕士论文电磁散射中迭代加速算法研究 可以对原方程组进行预条件。 其实质是构造一个可逆矩阵m ， 在线性方程组(2:51) 两边同时乘以 矩阵m一， ，得到下式 m一 iax = m一 l b( 2 .5 .2 . 1 . 1 ) 则转为求解矩阵方程: 月 j=b( 2 . 5 . 2 . 1 . 2 ) 其中又 = m一 ， a ，石 = m一 lb。 这个可逆矩阵m就称为 预条件器或预处理器。 显然当 m= a时相当于采用直接求解算法求解原矩阵方程。从这里可以看出预条件后的 线性系统是否比原系统更易于求解，构造一个好的预条件器是关键。 构造预条件器一般要遵循以下的三条基本原则. (1 ) 构 造 可 逆 矩 阵 m的 计 算复 杂 度 不 超 过口 ( 。 1 09司; (2 ) 矩 阵 向 量 积m 一 lx 的 计 算 复 杂 度 不 超 过口 ( 。 logn); (3 )m一 a 的 谱 应当是 聚集的. 预 条 件 技 术 的 实 现 形 式 有 左 边 预 条 件 、 右 边 预 条 件 和 两 边 预 条 件 三 种 方 式 。 其中，右边预条件技术相比于其他两种方式有更大的灵活性，它允许在每步迭代 中使用不同的预处理器。下面我们给出左边预条件的g m r es算法。具体如下: 1 . 开 始 : 选 择 k ry l ov 子 空 间 的 初 始 值 xo 和 维 数 m 。 定 义 一 个 (m+1 ) 、 m 矩 阵 万 。 ， 使 所 有 的气 ./ 初 始 化 为 零 。 2 . arn o l d i过程: ( a )c o m p u t ero ( b )f o rj = 1 ， = 材一 ， ( b 一 八 ) ， 刀 =i lro 1， ， =w/ vl= ro / 刀 二 ， m d o c o 叩 u t e w := m 一 ，a vj f o ri =1 ， ， j ，d o 气 ， 片 ( w， 咋 ) w 井w 一 气 j 从 e n d d o .co 呻 “ t “ 如， = 叫 2 ， v+l e n d d o 忆 十 i.j 硕士论文电磁散射中迭代加速算法研究 ( c )d e f i n e 3 . 求得近似解 : 今= 【 vl ， ， 叼 c o m p u t e凡二 xo+ v . 入 其 中 、 = arg “ n ， 俩一 瓦 川 2 ， e : 一 11 ，0 ， ，0r 4 . 重复: 如果 满足精度要求则 停止; 否则， 使xo二 气并 返回到2 。 如果将预条件矩阵m用单位矩阵来代替，上述算法就是一个普通的g m r es算 法。简而言之，所谓的预条件技术就是将原始的线性系统转换为另一个等价的线 性系统，从而使转换后的线性系统与原始的线性系统拥有相同的解，并且对于迭 代法更加易于求解。 2 . 5 . 2 . 2 常用预条件技术简介 1 . j a c o b i 预条件 对角预条件又称为雅可比预条件，是一种最简单的预条件技术。它利用系数 矩阵的对角矩阵作为原矩阵的一个近似。其预条件矩阵被定义为: m =d( 2 . 5 2 .2 . 1 ) 这里，d 代表一个对角矩阵， 其元素由 稀疏化的近区作用矩阵入的对角线元素组 成。这种预条件突出的好处就是构造简单，便于施加，并且几乎不需要额外的存 储量。然而，由于其包含的稀疏矩阵的信息过少，一般情况下其预条件的效果并 不是很明显。 2 .s s o r 预条件 与对角预条件算子的构造相似，对称超松弛预条件算子也可以直接利用稀疏化的 近区 作用 矩阵入 直接表达。 其预 条 件矩阵 被定 义为: m =( d + 口 e ) d 一 ， ( d + 口 f )( 2 . 5 2 2 .2 ) 其中 ， d ， e ， f 分 别表 示入的 对 角 阵、 严 格 下 三 角 阵以 及 严 格上 三 角 矩阵 。 口 。 (0 ， 2. 0) 是一 个松弛因 子。由 于入的对称性， 有f=e。 从(2 .5.2. 2. 2) 式的定义可以 看出， s s o r预条件算子比diag包含了 更多的稀疏 矩阵信息，因而常常具有更好的预条件效果。 此外，由于 s s o r预条件算子具有 分解的 形式， 因此它又揽括了 基于分解的预条件算子的 特征. 例如， 同il u一样， s s o r预条件算子的施加同样包含了 三角阵的求逆过程. 同时，由于s s o r预条件 算子的分解因子 ( 如d 十 。 e) 是直接从系数矩阵中抽取的，避免了预条件算子构 造过程中不稳定的现象。 3 .不完全lu分解预条件技术( 工 lu) 基于l u分解的直接法求解矩阵方程时， 首先将矩阵分解成上、 下两个三角阵 硕士论文电磁散射中迭代加速算法研究 因子的乘积，然后利用这两个三角阵的求逆获得矩阵方程的解。很自然的，如果 对该矩阵进行不严格或不完全的lu 分解， 那么， 就可以利用得到的上、 下两个三 角阵因子的乘积作为原系数矩阵一个很好的近似。 即m= l 二 a。 这里l ， 分别 是矩阵a严格分解的因子l ， u的一个近似。这就是不完全 l u分解预条件的构造 思想。 4 .稀疏近似逆预条件( s p ai) 稀疏近似 逆预条 件s ai(s p ar se a ppro xim atelnve rs e) 是一种显式的 预条件 技术， 它通过对系数矩阵的逆矩阵作直接稀疏的近似来构造预条件算子。常用的稀疏近 似逆预