（计算数学专业论文）辐射度方程的快速配置求解.pdf

鹕- 荽 摘要 本文从快速、层次性、自适应性几个方面出发，利用多尺度配置小波基底的特性，来 构造基于辐射度方程的快速配置求解框架，并给出相应的理论分析，包括：场景的剖分 策略，基底、配置点的构造格式和插值误差分析，辐射度方程中奇异积分的快速算法和 误差分析，辐射度问题中线性系统方程求解部分的多层扩充求解算法和误差分析。较为 全面地给出了一。个辐射度问题的快速算法。本文所探讨的场景仅限于无遮挡的多面体表 面。全文共分三章。 第一章首先简要介绍计算机真实感图形中光照明模型的产生和发展，以及所取得的重 要成就：然后介绍辐射度方程的数学物理背景，给出方程的详细推导过程；最后介绍在 计算机图形学中，求解辐射度方程常用的方法：分片常数g a l e r k i n 方法和有限元辐射度方 法。 第二章首先给出利用快速配置法求解第二类积分方程的一般框架，包括：构造多尺度 基底需要满足的条件，系数矩阵的截断策略和配置法求解的误差分析；最后给出多片形 式的多尺度基底和线性范函的构造格式，并给出满足相应条件的证明。 第三章首先给出辐射度场景的剖分策略，构造满足辐射度方程的相应的多片形式的 多尺度基底和线性范函，并给出误差分析：其次给出利用快速小波配置法求解辐射度方 程的一般框架和理论分析；再次给出辐射度方程中奇异积分的数值计算方法以及相应的 误差分析：然后给出辐射度问题中线性系统方程求解部分的多层扩充求解算法和误差分 析；最后给出一个利用快速小波配置法求解辐射度方程的数值算例。 关键词：辐射度方程，多尺度，小波，配置法。 a d w a x d y j 1 6 3 n e t 第i 页，共5 4 页 a b s t r a c t i nt h i sp a p e r ，w em a i n l yd i s c u s st h ew a v e l e tc o l l o c a t i o nm e t h o df o rt h er a d i o s i t ye q u a - t i o nw h i c hc a nb et r e a t e da sas e c o n dk i n di n t e g r a le q u a t i o n f i r s tw ed e v e l o pat r i a n g u l a - t i o ns t r a t e g yf o rt h et a d i o s i t ys c e n e s s e c o n dw ec h o o s ea p p r o p r i a t em n l t i l e v e lw a v e l e tb a s i s a n dc o l l o c a t i o nf u n c t i o n a sh a v i n gt h ep r o p e r t yo fv a n i s h i n gm o m e n t s ，t h i r dw ed e v e l o p a na r i t h m e t i cf o rs i n g u l a ri n t e g r a t i o no ft h er a d i o s i t yp r o b l e m s a tl a s tw ei n t r o d u c et h e a u g m e n t a t i o n m e t h o df o rs o l v i n gl i n e a rs y s t e mo ft h er a d i o s i t ye q u a t i o n t h es t a b i l i t ya n d c o n v e r g e n c eo ft h ew a v e l e tc o l l o c a t i o nm e t h o dw e r ep r o v e di nt h ep a p e r i nt h ee n d ，w e p r o v i d ean u m e r i c a le x a r n p l e k e y w o r d ：r a d i o s i t y e q u a t i 。nm u l t i l e v e l ，w a v e l e t ，c o l l o c a t i o n a d w a r d y j 1 6 3 n e t 第i i 页，共5 4 页 ：! 。 尊嚣谜 2 = = = = = = = = = 2 = = ! ! = ! = = = ! ! = = = ! = ! = = = = = = ! ：= ： 1 1 光照明模型 第一章综述 计算机真实感图形是一种光栅图形。光栅图形显示器的屏幕由一系列显示单元组成，每一个 显不单元称为一个像素。生成一幅真实感图形时，我们必须逐个像素地计算画面上相应景物表面 区域的亮度。显然，在计算可见景物表面区域的亮度时不但要考虑光源对该区域入射光及光亮 度和光谱组成，而且还要考虑该表面区域对光源的朝向，表而的材料和反射性质等。简言之，这 种计算必须基于一定的光学物理模型，我们将其称之为光照明模型。 第一个光照明模型是由b l l i t u o n g p h o n g 在1 9 7 5 年提出的 p h o n 9 1 9 7 5 1 。p h o n g 模型主要是基 于考虑场景中的光源属性：入射光强度( 1 0 和环境光强度佤) ，景物表面属性：漫反射系数( 幻) 、镜 而反射系数( k ) 和对环境光的漫反射系数( ) ，给出如下方程： j = 厶十石_ i 南( 妇五( 7 育) + k 五( 7 才) “) ( 11 ) v 袖 围1 - 1 局部光照明模型 2 轴 如图卜1 所示：育是景物表面各可见点处的单位法向量，z 是单位入射光线方向向量，节是 单位镜而反射向量，可是单位视线向量，d 是景物表面到光源的距离。对于一个给定的景物表 曲，当用p h o n g 模型来计算景物上每一个可见点处的光亮度时，需分别对红、绿、蓝三色分 别使用式f l1 ) 来计算。这样，用户就可方便地控制物体表面的环境反射、漫反射光的颜色。 柱此基础上，b l i n n 在1 9 7 7 年提出t b l i n n 模型 b l i n n l 9 7 7 】，c o o k 和t o r r a n c e 在1 9 8 1 年提出了c o o k - t o r r a n c e 模型 c t l 9 8 1 1 ，进步完善t p h o n g 模型的不足。由于这类模型仅考虑光源直接照射在 景物表而所产生的光照效果，所以被称为局部光照明模型。局部光照明模型能表现由光源直接照 射在漫射表面上形成的连续明暗色调、镜面上的高光以及由于景物的相互遮挡而形成的阴影等， 具有定的真实感效果，而且实现简单，因此在这种模型的基础上，由w h i r r e d 在1 9 8 0 年提出的 光线跟踪算法f w h i t 铀a 1 9 8 0 1 成为了早期真实感图形研究和绘制的重要方法。 美m e o r n e l l 人学和日本的广岛大学的学者在1 9 8 4 年提出了真实感图形的另一种模型方法一 一辐射度方法。他们将热辐射工程中的辐射度方程( t h er a d i o s i t ye q u a t i o n ) b 1 入到计算机图形学 m w a r d y j 1 6 3 n e t 第1 页，共5 4 页 = ：= = = ! = = ：= ：! ；! 塑墅星壅堡竺鍪兰塑堡童塞 中【g t g b l 9 8 4 1 。辐射度方程的一般形式是： n r 、r b ( v ) 一半g 晒，q ) v ( p ，q ) b ( q ) d a ( q ) = e ) ，p s( 12 ) “j q e s 辐射度方法基于热辐射工程中的能量传递和守恒理论，即一封闭环境中的能量经多重反射以后， 最终会达到一种平衡状态。当假设这个封闭环境中的景物表面均为理想漫反射表面时，这种平衡 状态可以用辐射度方程( 12 ) 来定量表达。从数学上看，方程( 1 2 ) 是一个第二类的f r e d h o l m 积分方 程，我们可以通过数值方法来得到方程的近似解b ( p ) 。然后利用b ( p ) ，就可以确定景物表面s 上 像素点p 的亮度。这类模型由于考虑了场景中所有表面的多重反射，所以被也被称为整体光照明 模型。本文将在下一节r l t 给出辐射度方程( 12 ) 的物理背景和详细推导过程。 同常生活中，当两个表面，。一个红色的，另一个白色的，相当靠近时，会在白色的表面上发 现淡淡的红晕这种现象称为色彩辉映。光线跟踪算法由于它的采样性和局部光照明模型的不完 善性，很难实现这种效果，而辐射度方法却相当成功地模拟了这种现象。其次- 辐射度方法是一 个视点独立的算法，也就是说，在完成辐射度方程的计算之后，即使观察者改变在场景中的相对 位置，也不需要重复计算场景中备像素点的亮度值。正是由于这一特性使得辐射度方法被广泛应 用十虚拟环境的漫游系统中。 1 2 辐射度方程的数学物理背景 上一节中提到辐射度方程的一般形式为： b ) 一氅竽。g ( p ，q ) v ( p ，q ) b ( q ) d a ( q ) = e ( p ) ，p e s “ o 口t o 其中，s r 3 是理想漫射环境下的景物表面，p ) 【0 ，l 】是p 点处的漫反射率，y ( p ，q ) 是p 点 与g 点问的遮挡函数 一，、f 1 ，当p 和q 之间无遮挡物， v 憎，q ) - 10 ，当p 和q 之间有遮挡物。 g ( p l q ) c o s f 而0 vc o r s o q = 坠驾掣； 其中，嘶和分别为p 点和g 点处的单位法向量，和如分别为唧和嘞与连接p 、q 问向量商的夹 角。如图1 - 2 所示。 斟辅 a d w a r d y j 1 6 3n e t 图1 - 2 两表面间的能量交换 第2 页，共5 4 页 i 暑_ 善练述 ! = = = = = 1 2 = ! ! = = = ! = = = = = 2 = = = = = = ： = ：= ：2 。套衰羔妻：。姿堡袭塑跫度的物理概念给出辐射度方程的推导过程。首先，我们需要给出光通 量、立体角和光亮度的定义。 一 ，。窑些璧竺! ，誓孳荤壁# 塑着光线流动的光能流，并遵守儿何光学上的能量守恒定律，即在 单位时间内通过一个光线管中任一截面的能量是恒定的。 。一 。一 定义l t l 我们把单位时间以内通过某一面元栅的光能量称为通过该面积的光通量记 越d j 。 ，n e 甜2 面两 定义1 2 面元d s 在以某一点( 称为锥顶) 为巾心的单位球面上的投影画积称为该面元关于 该点所张的立体角，记为d 。 m = d s _ = c r o s 0 其中r 为锥顶到d s 中心的距离，o y g d s 心处的法向量与锥顶与d s 中心所形成向量之间的夹角( 如 图1 - 3 ) 。 圉1 - 3 立体角以， 对于表面发光面元d 岛来说，我们关心的是该面元单位面积上朝某方向辐射的光能。注意到 发光而元朝空间定方向辐射光能的有效面积只是面元d & 在该方向上的投影面积，且光能流的 传播是在立体角内进行的，因此， 定义1 3 发光面元d & 单位而积朝某方向辐射的光能可以表为( 如图l 一4 ) ，= 历五d 砸f 石 其中巩为d 鼠法向方向和辐射方向的夹角。物理量厢# 为面元d 瓯朝该方向上的光亮度，它决定了人 眼沿该方向从面元d 岛所接收的光能大小和色彩组成。 由光亮度的定义知，我们需要建立的是一个能够准确刻画景物袭面各点光亮度的数学模型。 假设图1 - 2 为封闭环境，其中的景物表面均为理想漫反射表面，即景物表面上每一一点向躅围环境 各个方向辐射的光亮度是相同的，表面各点处的光亮度，只与其位置有关，与辐射的方向无关。 假设d p 为表面某点处单位面积上朝某辐射方向发出的光通量，则由光亮度的定义1 3 知，d p 与 该点处沿同一方向的光亮度珀关系为 d p = i c 0 8 0 d wf l3 1 a d w a r d y j 1 6 3n e t第3 页，共5 4 页 图1 4 光亮度i 其中目为该点处的法向与辐射方向的夹角，扎为辐射方向对应的立体角。则该点处单位面积面元 向其四周半空间辐射的总能量亦即该点总辐射度为 b = d p = i c o s o d u ( 1 4 ) 其中n 为该点处表面朝法线方向的半球面空间( 如图1 5 ) 。由于i 与立体角山无关，故式( 1 4 ) 可表达 为 口= ，c o s 0 山= - f 0 2 ”z ；c 。s s t n 一。a 妒= ，” c s ， 图1 - 5 辐射度与光亮度的关系 由此可知，理想漫射表面每点处的辐射度值与光亮度值之比为一常数因子。因而，表面各点 的光亮度计算可以转化为计算表面各点的辐射度。假若周围环境为一封闭系统，则表面上每一 点x 处微面元d s ( z ) 向周围环境辐射的能量由它自身所具有的辐射光能和它接收来自环境中其它景 物表面向该点辐射的光能后所产生的反射光能组成。假设周围环境入射到微面元d s ( x ) 上- 的光能 为h ( x 1 ，p ( z ) 为该表面在x 处的漫反射率，则微面元d s ( z ) 对环境入射光能的反射而产生的那部分 辐射光能为p 扫) 日扛) 。因此，根据能量传递和守恒定律，x 点处的辐射度b ( z ) 满足 b ( x ) d a ( x ) = e ( x ) d a ( x ) + p ( x ) h ( x ) ( 1 6 ) a d w a r d y j 1 6 3 n e t 第4 页洪5 4 页 萼叠稼避 其中d a ( z ) 为微面元d s ( z ) 的面积。e ( z ) 为该表面在z 点处的自身辐射度，若该表面为漫射光源， 则e 向) 0 ，否则，e 血) = 0 。 现在我们来考虑如何计算矗( z ) 。由日扛) 的定义知，抒( z ) 是周围环境表面各点辐射度口( 。0 的 酌数。其中。z 。一般来说，z 处的微面元d s ( z ) 向四周辐射的能量中只有一部分到达。点处。 若我们用f ( x 7 ，z ) 来表示从微面元d s ( x ) 辐射并到达微面元d s ( z ) 的光能占它向四周辐剁的总光 能的比例，则d s ( 。) 对z 的入射光能为b 0 7 ) f ( z ，x ) d a ( x ，) 其中d a ( 。7 ) 为徽面元d s ( x 7 ) 的而积。 由日f 0 1 的定义知 目( z ) = 7b ( x ) f ( 。7 ，x ) d a ( x )( 1 ，7 ) j s 其中s 为环境中的所有表面。通常称f ( ，。) 为微面元d s ( x ) 列d 取z ) 的形状因子，或称为 点。，对z 的形状因子。由于理想漫剁表面接受到来自空间任一方向的光能后均朝叫面八方均匀 地反射出去，故形状因子f ( x ，。) 只与微面元d s ( z ) 和d s ( x 7 ) 的相对位置、几何大小有关，是一个 纯儿何量。根据立体角的定义( 12 ) ，当从z 7 处观梨d s ( z ) 时，即能量从z 7 辐射向d s ( z ) 时，a s ( z ) 所 张的立体角为： d w = c o s 积如丌d a ( z ) r - i z ，z j 其中，( z ，z ，) 为z 与。，之问的距离，如为d s 扛) 在$ 处的法向量虬与连接点z 与一的向量之问的夹 角( 如图1 - 6 ) 。 图1 - 6 点z 7 对z 的形状因子的几何说明 由方程( 13 ) 和( ) 知，由d s ( z 7 ) 发出的能量到达d s ( z ) 的能量为： d p ( 一) d a ( ) = j ( 一) c o so z d w d a ( x ) ：塑c o s 口d w d a ( x ，) 7 r 其中。d p ( x 1 为。，处单位面积朝立体角扎发出的光通量，j ( 。7 ) 为7 处沿方向( z z ) 的光亮 菇，。目。，为d s ( ：，) 在z ，处的法向量 o ，与连接点z 与一的向量之问豹夹角。由于微面元d s ( z ) 向四 j 封发出的总能量为b ( z ，) d a ( x ) t 故面元d s ( z 7 ) 到面元d s ( z ) 的形状因子为： a d w a r d y j 1 6 3n e t f ( 2 ，) =翌幽塑鲨2 ：c o s o , d u b ( z 7 ) d a ( x ) 口 = 籍州。)。i 而i 孑r ”译 第5 页，共5 4 页 上述推导显然隐含一个假设，即假设微面元d s ( z ) 和d s ( z ，) 之间是完全可见的。 若d s ( z ) 与d s ( x ) 之间存在遮挡物，则由光学原理知，d s ( x ) 入射到d s ( 。) 上的能量为零。由此， 我们可将形状因子表达为如f 的一般形式 f ( z 7 ，z ) = y ( 拶( 巩删( 。，) ) 篝；等；筹扰( 。) = v ( d s ( 乩舾( 奶) g ( z ，。) 姐( 。) ( 1 8 ) 其中矿( ，- ) 为遮挡函数，若d s ( x ) 与d s ( x ) 之间存在遮挡物，其值为0 ，否则为1 。 将方程( 】7 ) 和( 18 ) 代入方程( 】g ) 得 b ( x ) d a ( x ) = e ( x ) d a ( x ) + p ( x ) d a ( x ) b ( 。7 ) 矿( d s 知) ，d s ( x ) ) g 扛，z 7 ) d a ( x 7 ) j s 化简整理就得到如方程( 12 ) 所示的般形式： b ( z ) 一p ( z ) b ( x 7 ) y ( d s ( 。) ，d s ( z ) ) g ( z ，) d a ( x ) = e ( z ) ， 。s j 一s 该山程系统地描述了封闭环境中各景物表面在能量平衡状态时的光能分布。 1 3 辐射度方程的一般求解 1 3 1 分片常数g a l e r k i n 方法 在计算机图形学中，求解辐射度方程最常用的方法是分片常数g a l e r k i n 方法。算法假设场景 中的各景物表面被剖分成一系列互不重叠的小平面片且各面片上的辐射度值和漫反射率均为常 数。对方程( 12 ) 应用分片常数g m 目k i n 方法，可以离散得到如下的线性系统 b 一肼马= 岛，i = 1 ，2 ， ( 1 9 ) 爿巾 一” r ，= 圭j ( 。j ( ，学y ( p ，o ) d a ( p ) d ( q ) ( 1l 。) 在此，b ；是要求的面片s l 的辐射度，a i ：t 壬面片鼠的面积，是面片到岛的形状因子。由 式( 11 ( ) ) 容易知道，形状因子j _ 玎有以下良好的性质： 羁，和玛，服从交换关系a i 只j = 山玛t ： 对一封闭环境，我们有磐1r j = 1 ： 若面片函为一平面或凸曲面片，则有心= 0 。 ( 1 ( ) 1 可以写成矩阵的形式： 仃+ m ) b = e 其巾i 为n n 的单位阵， a d w a r d y j 1 6 3 n e t m = - p lf l l - p 2 f 2 1 - p l f l 2 一p 2 f 2 2 - p xf 1 n p 2 如 - - p n f n l 一p n f n 2 一p n f n n 口= ( b 1 ，岛，巩) r e = ( e 1 ，如，e n ) 7 第6 页，共5 4 页 蒂警，卷j 童 = = = ! = 自= = ! ! = = = ! = = ! = = = ! 1 2 = = = = = = ! = = = = = 2 = ：! ! = ：! ：= = - ! - ! 一= 故有 ，n 耳，1 一p i 蜀i 聋1 ，j f 因而，矩阵( j + m ) 是对角占优矩阵，显然存在唯一解。在数值计算中，有许多方法可以求 解上述辐射度系统方程，常用的算法有：c a u s s - s i e d e l 迭代法、s o u t h w e l l 迭代法和逐步求精 迭代法。特别值得一提的是，由美国c o r r n e l l 大学的c o h e n 等人在1 9 8 8 年提出的逐步求精迭代 法 c c w g l 9 8 8 1 ，它对s o u t h w e l i 算法进行了改进，使得在每一迭代过程中，可立即显示基于当前 近似解的场景面面，且计算复杂度由原来的d ( 2 ) 降为d ) ，很好地解决了由于辐射度求解过程 耗时大而产生的交互设计困难的问题。 整个分片常数c a l e r k i n 方法可以简单地归结为如图1 7 的流程图。 圈1 7 分片常数g a l e r k i n 辐射度方法流程圈 由9 ) 不难发现，辐射度方法的难点在于景物面片问形状因子的计算，其计算复杂度 为o ( n 2 】。实践也表明形状冈子的计算占辐射度方法总计算量的9 0 以上，因而提高形状冈子的 计算效率和精度是辐射度算法的关键所在。在辐射度方法的发震过程中，曾经提出了多种多样的 形状因r 计算方法，包括：线积分技术，n u s s e l t 方法，半立方体算法，半球面分割技术，m o n t , e c m l o 秋分方法。关于这些算法的详细介绍请参阅书籍i p b j l 9 9 9 a 其中由c o r r n e l l 大学的c o h e n 等人于1 9 8 5 年提出的半立方体算法 c 0 1 9 8 5 得到了最广泛的研 究和应用。它的基本思想是在每个微面元d & 处沿其正法向量方向放置一个虚拟的半立方休( 如 a d w a r d y j 0 1 6 3 n e t 第7 页，共5 4 页 = rp 氘。似 p 及质 性的子因状形由 1 3 辐射度方程的一般求解 i n l 8 所示) ，该半立方体的5 个表而被剖分成均匀正方形网格( 通常为5 0 5 0 或1 0 0 1 0 0 ) ，每一 网格均剥应d & 朝向半球面空间的一微立体角，从而形成一个半空间立体角查找表。算法预先计 算、存储好半立方体中心微面元对各表面网格的微形状因子。这样中心微面元到任一而片的形状 吲子就可阻用这些微形状因子的和来逼近。 图1 - 8 半立方体表面网格剖分 对有遮挡的情形，半立方体算法将场景中所有面片投影在半立方体的五个表面上，若某立方 体表面网格( 简称表面像素) 被两个以上面片的投影区域所覆盖，则通过比较这些面片离半立方 体中心微面元的距离来决定在该像素处可见的景物面片。每个像素均记录了各自的可见粤尊爸 专。这二过程实际上是取半立方体中心微面元为观察点以立方体的五个表面为视平面婴场景中蜩 各景物砸片做消隐处理。消隐算法一般采用硬件的z 缓存器或扫描线算法。这样，微_ 曲元d & 对 而片岛的形状因子可用下式来表达： 魄一s = 日 q 0 其中q 为半立方体表面像素缓存器中可见面编号为j 的像素组成的集合，岛为微面元d 岛对像 素口的微形状因子( 如图1 一o n e ) 。微面元d s 到顶面像素q 的微形状因子为 a d w a r d y j 1 6 3 n e t 图1 - 9 微面元d & 到面片毋的形状因子计算 岛= 丽r 南a t m 第8 页，共5 4 页 棼 萼镌皋 = = = = = = = = ! = = = = = = = ! = = = ! ! = = = = ! = = ：= = ：= = = ：- 摹烹全a 。婴为专享枣体项面像素的面积，它与顶面像素的分辨率有关。类似地，若像素g 位于半立 方体的x 轴方向的侧面，则有 1 凸g2 丽再刁聊a a s d e 其中4 m 如为半克方体侧面像素的面积，它亦与侧面像素的分辨率有关。显然，这样简单的表达 式大大提高了辐射度问题求解的效率，使得辐射度方法应用予复杂场景的真实感图形生成成为可 能。 另外，在1 9 9 3 年，p e t e rs c h r s d e r 借助微积分中的s t r o k e 定理推导出了一个关于两个般多边 彤间形状凶子羁j 的计算公式，也到达了一定的简化计算的效果，但是应用并不广泛，关丁这个公 式的详细情况请参阅【s h l 9 9 3 1 。 分片常数g a l e r l d n 方法由于其实现相对简单，理论性不太强，所以深受工程界的喜爱；但计 算量大、数据存储量大、无法提供精确的误差估计、自适应性差以及很大程度上依赖于初始场景 的剖分算法仍是其难以逾越的缺陷。 13 2 有限元辐射度方法 钊列分片常数g a l e r k i n 方法存在的问题，学界在九十年代中期将有限元技术引入辐射度方 法，提出了解决辐射度问题的另外种算法有限元辐射度方法。通过第二节对辐射度方程的介绍 我们知道，辐射度方法的核一山实质上就是个求解空间曲面第二类f r e d h o m 积分方程的问题。 如果我们把积分方程( 1 2 ) 写成算子的形式，有 f j k ) b = e 其i l - ，k 是一个定义在b a a a c h 空间x x 上的积分算子。 n 日( p ) = 生笋y ( p ，q ) g ( p q ) b ( q ) d a ( q ) ，p s ( 11 2 ) 通常，x = 工。( s ) 或铲( s ) 。 为了近似求解方程( 】1 1 ) ，我们需要首先选取一个有限维的子空间序列j 乇cx 且d j m ( ) = d 。 h ，我 们使用记号& 。：= h 1 7 从而 。的支集包含在s n 。中。需要注意的是，同在第n 层的各基函 数的支集并非互不相交的，但任给一基函数”一，n h ，在第n 层中最多另有p 1 个基函数的支 集和”。的支集有重叠部分。 为了定义配置法，我们需要v + 中的一组多尺度线性泛函 l n ：= 卫n m ：r n z 叫f n l ) ， n n o 其r f i 每个如。是有限个点值泛函的线性组合 一= ：c 。以， ( 2 8 ) s 鼠一 其l h 。都是常数，岛i 为岛t 中有限个点构成的集台，且j k 中点的个数对n n ，i z 。( 。) 致有 界。类似地我们记岛。：= 赢一 一并将看作泛函靠。的“支集”。 我们要求l 面的多尺度基底和线性泛函之间具有以下关系： f i i ) 对任意的扎，n 7 n o ，有： ( 1 州m ，叫帅) = 矗。，6 。m ，( n ，r n ) ，( n ，r n ) u ，礼sn ， ( 29 ) 其中如，为k r o n e c k e r 记号。此外。存在正常数1 使得 - _i ( 。，m 一，w n m ) i 7 ，( n ，竹t ) ，( ，r ) u ，札 n ( 2 1 0 ) m z f n l 在条件( i i ) 中，我们没有要求线性泛函与多尺度基双正交，而只是要求它们具有“半双正交 性”，如式阻9 ) 所示；另一方面，我们要求这种“半双正交性”近似于双正交性，两者之间的差 异不会太大。式( 2 1 0 ) 体现了这一要求特别地，式( 29 ) 表明处于较高层次的线性泛函作用在较低 层次的多尺度基上取值为0 。定义半无穷矩阵e ，其元素为： e m _ m ：= ( 。，m ，钟。m ) ，( 似，r n ) ，( n ，m ) eu 根据式皿 ) ) ，矩阵e 是一个分块上三角矩阵，且对角块都是单位阵。因此，其逆矩阵e _ 1 存在， 且具有相同的形式，即 ( e - 1 ) m ，。m = “。，d m m ，n n ，m z 叫( 。) ，r z ( 州) 利j = f i | 以上定义的线性泛函和多尺度基，我们可以建立求解第二类积分方程的快速配置法。首 先假设k 是一个弱奇性核，对任意的s e ，有( s ，) l 1 ( e ) 。从而由 a d w a r d y j 1 6 3 n e t ( 丘u ) ( s ) ：= fk ( s ，t ) “( ) 出，s e 第1 4 页共5 4 页 j 务 嚣弼鼍二譬_ 苛力。强的j 要配嬖法 = = ! = = ! = = g = ! = ! = = ! = = = = = = = = ! = = = ! = = = = 。= ：= ： 定义的积分算子咒：x v 是x 上的紧算子。考虑第二类n e d h o l m 积分方程 尼u = ，1f 2 1 1 1 其中，x 为一给定的函数，u x 为要求解的未知函数。假设1 不是蚓约特征值，则( 2 、1 1 ) 在嚣中葙 唯一解。求解( 2 _ ) 的快速配置法是求向量u 。：= i u i j ：( i ，j ) u 。严，使得r 中函数 吣= w 订 “j ) u 。 满足方程 ( 1 r j ，“。, c u 。) = ( 岛，】，f ) ，( i ，j 7 ) u 。 以t 求解过程等价于求解线性方程组 ( e 。一k 。) u 。= f n ， 其中 k n = 【( 如t ，瓦弛，) ，( 哟，唧) ， ：= f ( 如，蚴) 】，加) m ) ， 如= 【( t u ，) ( i ，j ) u r 由定义知，对“，j 气( i ，j ) u 。，有( r ) 。，玎= 马，巧：又由( 2 9 ) ，有 ( e 二1 ) ；一，玎= ( e - 1 ) ，j ，“，( t ，j ) ，( i ，j ) u 。 ( 2 1 2 ) f 2 1 3 1 f 2 1 4 需爱指m 的是，上面定义的配置法格式具有多尺度的特性，与传统的配置法格式有所不同。( 旦 是，它可以看作对传统配置法在逼近空间和配置泛函上作适当的基底变换后得到的格式。重要的 是通过研究发现，由于多尺度基和线性泛函的消失矩的作用，k 。的大部分元素值都非常小。对此 文章c m x 2 0 0 2 1 提出了一个有效的矩阵截断策略，使整个计算量( 包括系数矩阵的构造和线性方 程组的求解) 都大大减少，从而实现了快速配置求解的要求。当然。文章除了条件( i ) 、( i i ) ，f ， 对仫函数f ，) 的正则性，w 。的基函数的支集大小l 三l 及多尺度基和线性泛函的消失矩还徽了如下 的假设： f i i i ) 存在正整数女使得对任意p 巩，有 ( 。，p ) = 0 ，( w 。，p ) = 0 ，( n ，m ) u ，n 2 1 ， 其中( ) 表示三2 ( 凹) 中的内积。 条件( i i l l 对矩阵截断策略非常重要。由于多尺度基和线性泛函的消失矩的作用，k t 的大部分 元素值都非常小而线性泛函的消失矩使它们成为某种意义下的差商泛函 f i v ) 存在正常数使得对任意的( n ，m ) u ，有 l j 厶。| i + 8 咄m t 0 。s 如， 条件( i v l 实际上要求多尺度基底和线性泛函都一致有界。 ( v ) 对s ，t e ，s t ，核函数耳有连续偏导数d ；d f ( 8 ，) ，l o t i k ，i 口i k 。同时，存在正 常数口 1 及正常数c 一和c - ，使得当n 一。时 c 一“d i m f n 。+ p ”， a d w a r d y j 1 6 3 n e t第1 5 页 戋南4 页 c p “d i m w n o 十p ”， c 一卢一“d 兰d i m d n 。+ p 一“4 条件( v i ) 要求r s h w 。的维数随n 的增大呈指数增长，而d n 呈指数衰减 ( v i i ) 条件( i i ) 中涉及的常数，y 满足以下不等式 ( 1 + 7 ) 肛一k 。( 1 ( v i i i ) 存在正常数目2 和如使得刘所有n n o 和形如 ：= ( t j ) u 叼”玎的函数 ，有 o ：1 1 v 1 1 0 。1 i v l l 。0 3 ( n + 1 ) i i e v i i ( 2 1 6 ) ( i x ) 务o o ( e ) 中算子及逐点收敛到单位算子z 。即任绘尸怛) ，自 。l 。i m 。0 z 一$ l i 一5 o f x ) 存在正常数c 使得对任意的u ew ，”( e ) ， d i s t ( u ，r ) sc p h 4 i i “l l k 。 下面我们给出关于矩阵截断部分的结果。为此，首先将磁写成分块矩阵 k n = 【k m k z ， k “= i k , ，j ，甜b z “，) j z ) 我们对每个k m 进行截断，截断后的矩阵记为 k ( e ) “= 【( e ) t ，j 一，玎 j 一z 1 ，) j z 】， 其中e 为依赖丁 i i ，n 的截断参数， 獬7 却= 傺7 膏絮蒿黧坯毛 通过调节的值，可以得到相应的收敛阶和复杂度。下面的引理估计截断前后的矩阵块的误差。 引理2 1 ( c m x 2 0 0 2 ) 若条件( i ) ，( i i i ) - ( v ) 成立，则任给常数r 1 和o 口 “1 “ 2 ，d 一 口 ，存在正常数c ，使e r ( 巩+ d ；- ) 时，有 i i k 一k ( e ) e 1 1 i o 。“一”( d i 也，) ， i 7 ，i z n + l ， 其i ”：= 2 k d 。 令只。为从x 到f n 上的投影算子，定义为 ( ”，p h z ) = ( 玎，石) ， 0 ，j ) u n - 由( 29 ) 知只。的定义有意义。定义算子j o ：f n f n 为 _ i c 。：= e l f ， 易知坛。在基底 删巧：( t ，j ) u 。) 下的表示矩阵为e 二1 k 。对i o 的每个块k “，z ， z n + 1 ，我们都 确定列应的截断参数嘞，截断后的矩阵记为 良。= k ( 6 n 。；) 州k t z 。 记庀。：r 。h 为在基底 。玎：( i ，j ) u 。) 下以e ：1 良。为表示矩阵的线性算予。下面的引理给出 了截断参数选取的方法。 a d w a r d y j 1 6 3 n e t 第1 6 页，共5 4 页 第：筝蠡建积兮刀程的快篷酷髓法 引理2 2 ( c m x 2 0 0 2 )假设条件( i ) - ( v i i i ) 成立，o l ，b ，6 ，为实常数。则存在与n 无关的正常数c ，对任意 w k ，”( e ) ， f l ( _ i c 。一庀。) p 。口1 1 。o q 【2 七一b 叩，七一b ，叶；n 】( n + 1 ) p 一( + 。) “，d 1 1 1 t ，。，( 21 7 ) 且对任意口l 。( e ) ， ( 。一乏。) p 。u | i 。c 肛啤一6 叼，一町；礼】( 礼+ i b - a n d l l u l k o 。 ( 2 1 8 ) 定理2 1 ( c m x 2 0 0 2 ) 假设条件( i ) - ( x ) 成立，0 1 ，= 生，b + b = ( i i i ) b = l ，b i = ：；或6 = 警1 b = 争 则存在正常数c 和正整数m 使对任意n m ， 1 | 一o 。1 i 。c ，( n ) 一。4 ( 1 0 9 ，( n ) 厂| f f | k ，。 其中在情形f i ) 下r = 0 ，e l 青形( i i ) t v = 1 ，在情形( i i i ) 下r = 2 。 由定理21 我们可以看到，在 述截断策略下的快速配置法所求得的近似解矗佗的收敛阶是相当可观 的。 有关矩阵截断策略更详细的介绍和条件( i ) 一( x ) 的推导过程请参阅 c m x 2 0 0 2 1 a 2 2 多尺度基底和线性泛函的构造 在快速配置法一般框架中，构造满足条件( i ) 一( ) 、( ) 一( x ) 的多尺度基底w ：三j w l j ： 阮j ) 珏j 和配置泛函三：= f ：瓴j ) u 显然是关键。本小节将介绍如何构造出符合要求 的基底。 设积分区域ec 础具有紧集分解 e = u e 7 ， 其中 m e a s ( e n 庐) = 0 ， ，j z ，i j ， 且对任意，z 。，存在一族压缩映射族垂，：= 醒：e 孙，) ，使矿是垂下的不变集，即有 e 7 = 垂，( e 7 ) ：= u 蚝( e ) e z 。， 为r 适应计算，我们还要求压缩映射族垂，满足以下性质 对任意的r z 。，e ，映射在e 7 上有连续逆。 每个e 7 都有非空的内部，且 m e a s ( 框( e 7 ) n 蚝，( 上r ) ) = 0 ，e ，一z e e 7 a d w a x dy 1 6 3 n e t 第1 7 页，共5 4 页 ( 2 1 9 ) 矿生口 卜+ l 1 扩 ” 嚣下 | | b b + ! ：! 兰垦堡垄堕翌丝竺垦里竺塑! 圭 当垂，满足性质2 时，我们就可以利用町生成e 7 的一族多尺度分划t 磊：n n o ) 。即，任给e ：= ( c o ，e 1 ，e n - 1 ) z 2 ，：= z p ，xz “，x z ( 礼次) ，定义映射 7 e ：= 毛。咖矗o - - 。e l 一。， 并记 f z r ( e ) = 库一1 e 0 + - + 附e n 一2 + 一1 任维巧z ? ，存存：某个e z ：，使得j = 蜥( e ) 。由( 21 9 ) 及性质1 ，2 得： 霹= 联，。：霹。= 蛭( e 7 ) ，e z n f ) 构成e r 的第n 层分划。我们还要求此分划具有以下性质： 存在正常数c 一，。+ 使得对任意nen o ， c p 一”8 m a x d ( 霹。) ：e z 置， c + p 一”7 4 ( 22 0 ) 显然，e r 是一些简单的区域( 立方体、单纯形等) 时，满足以上要求的压缩映射是很容易构造 的。 舍配菩我们- 考虑如何- - 构e ，i ：跫氅嘤竺塌箍裟褰轰稳辫兰蕊骣装薷 喜巍勰丕商。曲薪，鬣磊赫磐雾夥镒j 苫荔猢有函数构成的空间。对每个r z ，定义吒为定义在集合e7 上，开且征早兀瑞，e 8 。i r _ 日_ 刊 束都是次数小于等于一1 的多项式的函数构成的空间a 于是 如= o 贬， m m c f s ，= m ：= ( 。+ ：一1 ) r e z v ， 因此， d i m ( f