（计算机软件与理论专业论文）离散的不适定问题的正则化方法与数值计算.pdf

离散的不适定问题的正则化方法与数值计算 吴国丽( 计算机软件与理论) 指导教师：李维国教授 摘要 本文主要研究利用双网格迭代方法求解离散的不适定问题 t i k h o n o v 正则化后的对称正定线性方程组。论文首先研究了求解对称 正定线性方程组的双网格迭代方法，其中主要介绍了两种预优因子和 一种共轭梯度法的变形，还考虑了二维卷积问题的求解。之后重点研 究了不适定问题的边界约束正则化，考虑用双网格迭代法求解转化后 的对称正定线性方程组，并考虑了更一般的边界约束条件，以及能更 好地刻画边界的s o b o l e v 范数，针对这些边界约束条件给出了相应的 正则化对称正定线性方程组及相关定理的证明，然后用双网格迭代法 进行求解，接着还考虑了正则化完全最小二乘问题的求解，由数值试 验结果可看出，用双网格迭代法求解转化后的不同的对称正定线性方 程组效果很好。最后研究了正则参数的选择问题，其中主要研究了对 l 曲线准则的一神改进方法，即通过l 曲线上点的边界图及曲率边界 图来确定正则参数，此方法相对于i 广曲线准则，计算量有很大的减少， 并考虑在双网格迭代法求解不适定问题的正则化方程组中，用此方法 确定正则参数。另外，论文还研究了在双网格迭代算法中用广义交叉 验证法确定正则参数。本文对这些方法都进行了数值试验。且数值试 验的效果良好。 关键词：不适定问题，正则化方法，正则化参数，预优因子，迭代 法 r e g u l a r i z a t i o nm e t h o d sa n dn u m e r i c a lc o m p u t a t i o no f d i s e r e t e1 1 1 p o s e dp r o b l e m s w u g u o - l i ( c o m p u t e rs o f t w a r ea n dt h e o r y ) d i r e c t e db yp r o f e s s o rl iw e i - g u o a b s t r a c t i nt h i s t h e s i s ，t w o g r i di t e r a t i v em e t h o d sa r e c o n s i d e r e dt os o l v e s y m m e t r i ca n dp o s i t i v ed e f i n i t el i n e a rs y s t e m sa r i s i n gf r o mt i k h o n o v r e g u l a r i z e dd i s c r e t ei l l - p o s e dp r o b l e m s f i r s t l y ，t w o - g r i di t e r a t i v em e t h o d s s o l v i n gi l l - p o s e dl i n e a rs y s t e m sa r et r e a t e di nd e t a i l t w op r e - c o n d i t i o n e r s a n dav a r i a t i o no ft h ec o n j u g a t eg r a d i e n t sa r ei n t r o d u c e d t w o d i m e n s i o n c o n v o l u t i o ni sa l s od i s c u s s e d t h e nt h eb o u n d a r yc o n s t r i c tr e g u l a r i z a t i o n o fi l l p o s e dp r o b l e m sa r e i n v e s t i g a t e d t w o g r i d i t e r a t i v em e t h o d sa r e c o n s i d e r e dt os o l v et h eo b t a i n e ds y m m e t r i ca n dp o s i t i v ed e f i n i t el i n e a r s y s t e m s m o r eg e n e r a lb o u n d a r yc o n d i t i o n sa n dt h es o b o l e vn o r ma r e c o n s i d e r e dw h i c hd e s c r i b et h eb o u n d a r yb e t t e r r e g u l a r i z e ds y m m e t r i c a n d p o s i t i v e d e f i n i t el i n e a r s y s t e m sa n dp r o o f so ft h et h e o r e m s c o r r e s p o n d i n gt od i f f e r e n tb o u n d a r yc o n d i t i o n sa r eg i v e n t h e nt w o g r i d i t e r a t i v em e t h o d sa r ec o n s i d e r e dt os o l v et h e s es y s t e m s r e g u l a r i z e dt o t a l l e a s t s q u a r e sa r ea l s oc o n s i d e r e d f r o mt h er e s u l to ft h en u m e r i c a l e x p e r i m e n t sw ec a l ls e et w o 一面di t e r a t i v em e t h o d ss o l v i n gt h es y m m e t r i c a n dp o s i t i v ed e f i n i t el i n e a rs y s t e m sa r ee f f e c t i v e f i n a l l y , t h e i m p r o v e d m e t h o d so ft h el - c u r v ea n dg e n e r a l i z e dc r o s s - v a l i d a t i o na r ea p p l i e dt o c h o o s et h er e g u l a r i z a t i o np a r a m e t e r o u rm e t h o d sa r eb e t c e rt h a nt h e l - c u r v e n u m e r i c a le x p e r i m e n t so f t h e s em e t h o d sa r eg i v e ni nt h i st h e s i s k e yw o r d s ：i l l - p o s e dp r o b l e m s ，r e g u l a r i z a t i o nm e t h o d s ，r e g u l a r i z i n g p a r a m e t e r , p r e - c o n d i t i o n e r , i t e r a t i v em e t h o d s l 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 中国石油大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 签名： 关于论文使用授权的说明 弓e l 本人完全了解中国石油大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件及电子版，允许论文被查阅和借阅； 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复 制手段保存论文。 ( 保密论文在解密后应遵守此规定) 学生签名： 导师签名： 铆趾舻j 月 弓 日 月 日 中国石油大学( 华东) 硕士论文第1 章前言 第1 章前言 1 1 课题提出背景及其研究意义 自2 0 世纪6 0 年代以来，在地球物理、生命科学、材料科学、遥 感技术、模式识别、信号( 图像) 处理、工业控制乃至经济决策等众 多的科学领域中，都提出了“由效果、表现( 输出) 反求原因、原象 ( 输入) ”的反问题，通称“数学物理反问题”。由于此类问题有着广 泛而重要的应用背景，其理论又具有鲜明的新颖性与挑战性，因而吸 引了国内外许多学者从事该项研究。至今，它已发展成为具有交叉性 的计算数学、应用数学和系统科学中的一个热门分支。 在求解数学物理反闯题时，面临的两个本质性的实际困难是：i 、 原始数据可能不属于所谓精确解所对应的数据集合，因而，在经典意 义下的近似解可能不存在；i i 、近似解的不稳定性，即：原始资料的 小的观测误差会导致近似解与真解的严重偏离。概言之，反问题常常 是不适定的。 关于“适定 ( w e l l - p o s e d ) 和“不适定 ( i l l - p o s e d ) 的概念是h a d a m a r d 为了描述数学物理问题与定解条件的合理搭配，于2 0 世纪初引入的。 设a ：f _ u 是映，到u 的线性或非线性算子，p ，和几分别是度量 空间f 和的度量， 定义1 1 ：称问题或方程a z = 口，z e f ，口u 为适定的，如果 它满足以下三个条件： v u e u ，都存在z f 满足方程a z = 口( 解的存在性) ； 设，u ，若z j 和z 2 分别是方程4 z = 材对应于u l 喾u 2 的 解，则z ，：( 解的唯一性) ： 中国石油大学( 华东) 硕士论文第1 章前言 v f o ，3 8 ( e ) 0 ，只要玑( u t ，u 2 ) 艿p ) ( “”口2 ，) ，就有 p f ( ：j ，乙) f ( a z i = u l ，a z 2 = 1 1 2 ) ( 解的稳定性) ； 反之，若上述三个条件中，至少有一个不能满足，则称其为不适 定的。 大量反问题都可写成如下的第一类算子方程的形式： a z = ，：e f ， u ( 1 1 ) 反问题为在已知舒和4 的情况下求z ，有时甚至在仅知砧的情况下求z 和4 。当4 为线性算子时，称其为线性反问题，否则称其为非线性反 问题。 本课题正是在这种背景下，针对离散的线性不适定问题提出的。 形如第一类算子方程( 1 1 ) 的不适定问题是大量而普遍存在的。例 如，由于微分算子的特征值是无界的，作为微分方程的离散近似，一 般用差分法或有限元法所导出的离散方程是病态的，而且随着离散尺 寸h 的缩小将更加严重。同样，由于第一类积分方程的求解是不适定 的，故由它直接导出的离散线性方程组，即使可解也是病态的。所有 这些不适定问题，都需要用特殊的方法( 如正则化方法) 来处理，才 能得到稳定的近似解。 1 2 国内外研究现状分析 近二十年来，数学物理反问题已成为应用数学中发展和成长最快 的领域之一，之所以如此，很大程度上是受其他学科与众多工程技术 领域的应用中的迫切需求所驱动。国内外有很多数学专家在研究不适 定闽题的正则化方法及其数值求解，并取得了丰硕的研究成果。数学 物理反问题的求解已发展了各种方法，例如脉冲谱技术( p s t ) 、广义 2 中国石油大学( 华东) 硕士论文第1 章前言 脉冲谱技术( g p s t ) 、最佳摄动量法、蒙特卡罗方法( m c m ) 、各种 优化方法和正则化方法等。 目前最具普适性、在理论上最完备且行之有效的方法。是由著名 学者t i k h o n o v 于2 0 世纪6 0 年代初提出、后来得到深入发展的正则化 方法。其基本思想是：用一族与原问题相邻近的适定问题的解去逼近 原问题的解。因而，如何构造“邻近问题”而获得所谓的正则算子和 正则解，如何控制与原问题“邻近程度”并求解与原始资料的误差水 平相匹配的正则参数以及上述工作的快速数值实现，成为正则化理论 和方法的三大核心问题。 然而应当强调的是，反问题的不适定性是问题的本身所固有的一 种特征，如果没有关于欲求解的附加信息( 例如，单调性、光滑性或 有界性，或原始数据的误差界限等) ，这一本质性的困难是无法克服的。 反问题的求解就是依据所能提供的关于解的附加信息，尽可能多的， 尽可能稳定地恢复原问题的部分信息。 1 3 主要研究内容和目标 本课题主要研究离散的线性不适定问题的正则化方法及数值实 现，这不但是由于大量的不适定问题本身就是线性的，还因为很多求 解线性不适定问题的方法可以推广到非线性领域。本文首先介绍双网 格迭代方法，其中包括两个预优因子和一个共轭梯度法的变形，另外 考虑二维卷积问题的求解。接着重点研究边界约束正则化下的双网格 迭代方法，考虑更一般的约束条件，以及能更好的刻画边界的s o b o l e v 范数，给出在各种约束条件下转化得到的正则化方程组及相关定理的 证明，并进行数值试验。最后研究确定正则参数的两种方法，一种是 通过画出l 曲线及曲率边界图来确定正则参数，一种是用广义交叉验 3 中国石油大学( 华东) 硕士论文第1 章前言 证法确定正则参数，考虑把这两种方法应用到求解正则化方程组的双 网格迭代算法里，并进行数值试验。 在研究过程中，首先要提到数值软件的使用。本课题将各种涉及 到的正则化策略和数值工具都应用于算法中，并使用大型数值软件 m a t l a b 结合大量的实例进行试算。 大规模的不适定问题离散化后形成如下的线性方程组： g = k + 刀( 1 2 ) 其中k 是大型病态矩阵，一是测量数据g 中的扰动( 如噪音) 向量， 要求的是未知向量的近似值要避免所求解不受噪音的干扰需考虑 对问题进行正则化。正则化有很多种形式，如t i k h o n o v 正则化方法n 截断迭代法【2 】和截断奇异值分解法【3 】等。若假定已知真解的范数的上 界，则正则化过程将转化为求解下面的约束最小值问题： m i n 寺厂7 k 7 矽一9 7 9 f ，s t i i ：1 1 2s ( 1 3 ) 可证f 1 8 1 ，是边界约束最小值问题( 1 3 ) 的解的充分必要条件是厂 是如下线性方程组的解： ( 足7 k m ) f = k 7 9( 1 4 ) 其中k 7 足一村是半正定的，五s o ，a ( 一8 卅：) - - o 。 我们对约束最小值问题( 1 3 ) 考虑更一般的约束条件，以及考虑能 更好地刻画边界的s o b o l e v 范数，则约束最小值问题分别变为： m i n 厂k 7 o f 9 7 k f ，s t 1 i 刎1 2s ( 1 5 ) r a i n i l ，7 k 7 9 f 9 7 x f ，s t s a ( 1 6 ) 4 中国石油大学( 华东) 硕士论文第1 章前言 m i n 去7 k 7 髟一9 7 k f ，s t 8 矽i s 墨 ( 1 7 ) m i n 去7 k 7 影一9 7 髟，s 1 i l f - d l 2 盯乙，则4 2 2 = 甲r k 7 胖+ 峨。吐i 。 这样就会形成带有如下系数的方程组， q o 毗r a o 慨, o r k 叱r o f _ 箍 可以把它分裂成三个部分( j = 工+ 西+ u ) ： 6 = 置 ，l = 三，： ，u = ：名1 c 2 t 。， 中国石油大学( 华东) 硕士论文第2 章不适定问题和共轭梯度法 2 2 2 雅可比预优 标准的j a c o b i 预优因子是由系数矩阵的对角线形成的。如果采用 ( 2 1 8 ) 作为方程组的系数，则可得到 6 】、【7 】中所描述的j a c o b i 1 i k e 预优 因子： m 痖一 可以直接把( 2 2 0 ) 式用于标准的预优共轭梯度法来求解( 2 9 ) 。但 是，残量和迭代向量要根据( 2 9 ) 做相应的变化。整个预优步骤采用以 下形式： 算_ 中，v 】n s , 1 【m ， e 1 7 ， ( 2 2 1 ) r 表示残量。下面将说明怎样避免直接应用甲，且如何来使用预 优因子的结构。当用( 2 2 0 ) 作为预优因子时，需求解以下类型的方程组： m “= 【o ，吲7 ， 上式等价于； a i l = o 7 ， ( 2 2 2 ) 倒2 = v 7 ， ( 2 2 3 ) 对于方程( 2 2 3 ) ，f l j ( 2 6 ) - ( 2 8 ) 可得： 甲“2 ：l q a e r ，：三w r 7 m m l ，：土鲫一i ， ：三( ，一o g 一一。7 m ) m l ，：l ( m 4 一。g 一1 7 p 口 最后可利用a 。的逆求解( 2 2 2 ) ，代入到( 2 1 0 ) 可得： x - - - - 中“i + 甲“2 ：o ( 爿矗由7 r ) + 三吖- l r _ 1 0 g 一1 7 ， 1 2 中国石油大学( 华东) 硕士论文第2 章不适定问题和共轭梯度法 ：母( 4 0 一土g ) 中r r + 土 彳一一，( 2 2 4 ) 这样，就避免了甲的直接应用。( 2 2 4 ) 式可直接用于预优共轭梯度算 法，但是，在每一步迭代里都要进行预优处理，因此可以先对a 。进行 因式分解。由于a 。l 是对称正定的，所以可以对a i ij 新c h o l e s k y 因式 分解。对m 的逆可做同样的考虑，但是在这种情况下，可先对上做q r 分解l = q r ，则m = 工= r 7 q q r = r 7 r 2 2 3 对称高斯一塞德尔预优 对称g a u s s s e i d e l 1 i k e 预优因子也包含删除后的对角块矩阵，预优 因子的矩阵分解形式为： n o s = ( b + l ) d 1 ( d + ( ，) ( 2 2 5 ) 和j a c o b i 双网格预优因子的情况一样，要对岱“= m ，、壬r 】7 ，的解 重新表示，v 可以用中表示，以避免对甲的直接应用。 首先对，进行分裂： 限咖嘲= ： 则有： ：，= ( 西+ 一1 西( 6 十) 。1 r = i ：! ：一- 4 a 1 2 2 1 j a 丢i l l r ，2 1 ) a 2 1 4 2 i 彳一，i ”| = ： c 2 z 6 ， 【匀( ，2j l 划 一 把a l l 、_ 等量代入到( 2 2 6 ) 中，可得到“。、“2 的如下表达式： “l 。a f t ( 中r r - 。7 k , v z 口( w t r - - 甲7 芷7 胍伽7 ，) ) 1 3 中国石油大学( 华东) 硕士论文第2 章不适定问题和共轭梯度法 ”2 = l 口( w r r _ 掣7 式7 删r ) ) 预优解为，= o u 。+ w u 2 。为简化表达式，由( 2 6 ) - ( 2 8 ) 可得： 、 ，“：；丢甲甲7 ( ，一足7 k o a i t 0 7 ，) ) ：占w 7 m m 一1 ( ，一k 7 k o a i t o r r ) ) a ：土( l p ) m 。1 ( ，一k 7 k 。a f i o r r ) ) a 。三( f 一一o g ，1 由7 ) ( ，一j i ：7 k o a n - o r r ) ) ( 2 2 7 ) 口 且有m 蚝；o a f i l ( o r r _ m 7 置k 甲吉( 甲t r - - 甲7 k 7 ：m 4 矗中。) ) = o 一0 0 7 ( ，- k 7 k f u 2 )( 2 2 8 ) 因此，可先计算( 2 2 7 ) 得到 f u ：，然后再代入( 2 2 8 ) ，求出o u ，。 2 2 4 舒尔补共轭梯度法 顾名思义，它不是一个预优因子，而是共轭梯度法的一种变形。 对( 2 1 7 ) 进行高斯消去，可得； 毒：l 二彳：，彳膏彳。： ： = 瞄：一爿：。，。 其中右下角的块为： s = a 2 2 - a 2 l a n t a l 2 = v ，j 4 ( ，一。一0 函r 一) 甲( 2 2 9 ) 它表示( 2 1 7 ) 系数矩阵中a i li 拘s c h u r * b 。 在第一个方程中，可分离出。： “l = 4 0 7 b 一4 矗4 t 2 “2( 2 3 0 ) 对第二个方程进行整理可得到： 1 4 中国石油大学( 华东) 硕士论文第2 章不适定问题和共轭梯度法 s u 2 = 掣7 b - a 2 l 利0 7 6 ， ( 2 3 1 ) 可见，如果从( 2 3 1 ) 中求出“：，那么利用( 2 3 0 ) 可以很容易的求出, l 。 因为4 是对称正定的，所以s 矗忡m ”也是对称正定的 1 0 ，定 8 3 9 】，而且又由于s 是大型矩阵( 考虑要对a 。和g 进行因式分解所以 选的七一般都很小) ，因此，自然考虑到用共轭梯度法来求( 2 3 1 ) ，在 算法中，因为 - f 和非对角矩阵块4 ：和4 ：规模很大，所以我们设法不 直接应用它们的值，另外，s c h u r b 空间里对迭代向量和残量可通过对 原方程组实施算法获得。显然此方法比j a c o b i 和对称g a u s s s e i d e l 预优 要复杂的多。 在共轭梯度法里，需要计算以下三个量： 芦= f 一厨，声= 阮万2 丽pd 6 口 其中上面有标记的向量表示“s c l a u r b 空间”里的向量，如譬= ”，。 首先应选取一个好的初值，由表达式x = o u l + - i u 2 可得： 石= m ( a f t l 西7 b - 4 a 1 2 甜2 ) + 掣“2 = o 爿0 巾7 6 + ( l 一中。爿0 7 4 ) 、壬，“2( 2 3 2 ) 从方程( 2 3 2 ) 中可看出，初值可取而= 州0 0 7 6 ，那么迭代向量的表 达式为x ( ，) = 鼻( 。) + ( 一删0 中7 彳) 甲“2 “。为方便起见，以后都把迭代 指标省略掉了。 接下来要找出残量的表达式， ，= b 一出= b - a e a 彳f i l 中7 b 一4 ( ，一( d ，i 中7 4 ) 甲2 1 s ! 鱼至鎏查兰! 兰奎! 堡主堡苎苎! 童至堡窒塑望塑苎塑塑堕鎏 = ( i - a o a f i 0 7 ) ( 6 一a w u 2 ) 在s c h u r - b 空间里的残量芦为： 芦= b 一勋2 = ( 甲7 b 一、王，a o a f i l 0 7 6 ) 一( 甲7 彳甲一、壬，7 a o a i m 7 a 。f ) u 2 = 甲7 ( ( i - a o a ( o ) ( 6 一a f u 2 ) ) = 甲， 由此可得到多： 声= 芦r 芦- - r 7 w r m m 一1 r = r r q m 一1 ，= ，r ( 肘一e o g 。中r ) ， 而由于： 母，= 西r ( ，一4 爿1 中r ) ( 6 一a w u 2 ) 毒( o r 一彳l l 爿一o r ) ( 6 4 甲) = 0 “ 因此有芦= ，m 。1 ，。由( 2 3 3 ) 可定义下降方向孑为： 孑= 甲7 d ，d 砖 由s c h u r 丰b 可得： s 孑= 甲r 爿( l c o a t i 。r 一) w r d = 甲r 彳( 一一1 1 0 r 一) 、壬n ，7 m m 一1 d = i 壬，爿( 厶一。爿0 中7 彳) ( 厶一中g + 1 0 7 甲、壬，7 m ) m t d = 甲r 爿( l 一( 套，4 0 0 r a ) m 一1 d 对任意孑r 一，定义w er 一如下： w = 爿( l o 爿_ m 7 a ) m d 1 6 ( 2 3 3 ) ( 2 3 4 ) 中国石油大学( 华东) 硕士论文第2 章不适定问题和共轭梯度法 由此可简化( 2 3 4 ) 式为：荫；、王，7 w 下面计算声：的分母： d 1 s d 孑s 2 ：d r t i “f r w ：d r w w r m m 。w = d 7 ( f 一中g “中7 ) w = d 7 m 一w 最后，解的迭代公式即为： x ( ，= 一，) + 肛) ( l 一4 0 m 7 4 ) 甲乏。) = t j ) + 局。) ( l o 爿0 中7 a ) w a 7 m m 。1 吐， = ，) 十屈) ( l q 埘矗m 7 a ) m 。吐。) 2 3 二维卷积问题的求解 在本节中，将研究如何求解二维卷积问题： fi ：k ( x , y ，未，力砬谚= g ( x ，_ ) ，) 其中核k 具有如下形式( k ，m 都表示函数) ： k ( x ，y ，j ，多) = r ( x - s c ) c o ( y 一多) 此问题可被离散成k r o n e e k e r 积的形式： ( 墨ok 2 ) v e c ( x ) = v e c ( b )( 2 3 5 ) 其中函数v e c ( ) 是把目标矩阵拉直成一个列向量。k r o n e c k e r 积有以下 几条重要的代数性质： ( a 圆b ) 7 = a o b 7 ( a o 占) 一= a 一o b 一1 1 7 中国石油大学( 华东) 硕士论文第2 章不适定问题和共轭梯度法 ( 4 固b ) v e c ( x ) = v e c ( b x a 7 ) ( 爿圆口) ( c 汐口) = ( a c ) 固( b d ) 则由l ( r o n e c k e r 积的性质，( 2 3 5 ) 可转化为： k ：x k ：= 8 由k l 、k 2 的奇异值分解k i = u l i k 7 ，k 2 = u 2 x 2 曙) 及k r o n e c k e r 积的性质，可得到如下关系式： k i 固k 2 = ( u io u 2 ) ( i 固2 ) ( 曙p 嘭) 因此二维卷积问题的子空间可通过两个适合于一维问题的予空间求 k r o n e c k e r 积形成。 另外，若令由；中。圆中2 ，则j ，= 印7 x 可写为： v e c ( r ) = ( 中l 固由2 ) 7 v e t ( x ) y = 中；釉i 其“逆算子”为：v e c ( x ) = ( 中l0 0 2 ) v e t ( r 3 铮x = 0 2 y o ： 那么a 。可写成如下形式： a j l ；( 中j k i k l 0 1 ) o ( m ；定；k 2 0 2 ) + o 力7 工r i 巾 为了方便计算，可把砷7 f 三由省略掉( 类似于2 2 1 节中把甲7 k 7 磊叩 从a 2 2 中删除) ，那么由k r o n e c k e r 积的性质可得； 彳0 v e t ( x ) 五0 v e c ( x ) = v e c ( ( 中；墨；足2 0 2 ) 一x ( r k r k l o i ) 一) 这样在初始化及每步迭代中都节省了计算量。 2 4 小结 大量的线性不适定问题都可离散化为不定线性方程组，t t k h o n o v 1 r 中国石油大学( 华东) 硕士论文第2 章不适定问题和共轭梯度法 正则化方法是求解不定线性方程组的常用且有效的方法，本章中，考 虑用双网格迭代法求解线性不适定问题t i k h o n o v 正则化后的对称正 定线性方程组。其中主要介绍了两种预优因子和一种共轭梯度法的变 形，另外还考虑了二维卷积问题的求解。 双网格迭代方法的优点在于它把大规模的问题影射到了一个较小 规模的粗子空间上来，由于子空问的维数相对较小，这样就可以很容 易在租子空间上求相应问题的精确解，然后再经过一个校正，影射回 原空间上。 1 9 中国石油大学( 华东) 硕士论文第3 章边界约束正则化 第3 章边界约束正则化 3 1 双网格迭代法求解边界约束正则化问题 大规模的不适定问题离散化后形成如下的线性方程组： g = k f + n( 3 1 ) 其中足是大型病态矩阵。厅是测量数据g 中的扰动( 如噪音) 向量， 要求的是未知向量，的近似值。要避免所求的解不受噪音的干扰，需 考虑对问题进行正则化处理。正则化有很多种形式，如t i k h o n o v 正则 化方法【”，截断迭代法【2 l 和截断奇异值分解澍3 1 等。在本文中，假定已 知真解范数的上界，那么正则化过程将转化为计算下面的有约束的 最小值问题： m i n 厂7 k 7 k f 9 7 i c ys t 1 i j q l ： ( 3 2 ) 在很多实际应用中很难找到一个好的上界，但是，如果已知一 个好的上界，则可利用这个信息进行研究。g a n d e r 已经描述y ( 3 2 1 的解的性质的理论结果t “1 。本文中，我们所关心的是计算( 3 2 ) 的解的 有效算法的实施。 对于小型矩阵，可利用奇异值分解求( 3 2 ) 的解。对于大规模的 问题，奇异值分解的方法花费很大。e l d e n t l 3 娩出了基于q r 分解的一 种更有效的方法，但是这种方法花费相对较大，而且，在算法中很难 利用系数矩阵的特殊结构。c h a r t 、o l k i n 和c o o l e y t h l 考虑利用牛顿法 和割线法来求解( 3 2 ) ，但他们是假定最小二乘问题的有效解存在。 g o l u b 、v o nm a t - t i t s l 提出了在( 3 2 ) 中的约束条件是等式的时候，基于 l a n c z o s 双对角化的数值方法。d e m e n t i e v 、n a g y 1 6 1 对s o r e n s e n 和r o j a s 提出的求解边界约束正则化问题的方法迸行了改进，得到了较好的结 2 0 中国石油大学( 华东) 硕士论文第3 章边界约束芷则化 果，r o j a s 和s o r e n s e n 提出的方法基于以下的引理。 引理3 1 1 1 6 i ：厂是边界约束最小值问题( 3 2 ) 的解的充分必要条件是 厂是如下线性方程组的解： ( k 7 k a j ) f = k 7 9( 3 3 ) 其中k 7 k 一村是正半定的，五o ，五( 一0 卅i ：) = 0 。 通常( 3 3 ) 被写为带非负正则参数口= 一a 的形式。这样，求解约束 最小值问题( 3 2 ) 就转化成了求解正则化问题( 3 3 ) 。 当a = 0 时，约束条件没有起作用，所以考虑五 0 的情况，则( 3 3 ) 即为对称正定的线性方程组，因此，我们考虑用第二章介绍的双网格 迭代法求解正则化的对称正定线性方程组( 3 3 ) 。 数值试验：考虑【1 7 】中的几个试验问题。疗为问题离散的维数，取 n = 3 0 0 ，方程组右边的量为； 一 ， 舻g + s 而 其中g = y 二。，是随机向量，其元素不均匀的分布在 o ，l 】之间，s 是误差水平取为4 厶。i ：。 试验l ：首先用双网格迭代法求解b a a r t 问题： j 屉( j ，t ) f ( t ) d t 。g ( s ) ，o j 万2 ( 3 4 ) 其中k ( s ，f ) = e x p ( s c o s ( t ) ) ，g ( s ) = 2s i n h ( s ) s ，解为厂( ，) = s i n ( t ) 。用 1 7 】 中的b a a r t m a t l a b 编码来离散( 3 4 ) ，得到矩阵k r 3 ”、右端向量 g r ”和真解_ ，二。，l l 厶地= 1 2 5 3 3 。k 的条件数为1 0 6 3 8 x 1 0 ”， 2 1 中国石油大学( 华东) 硕士论文第3 章边界约束正则化 此方程是非常病态的。 表3 1 显示的是用三种双网格迭代算法( 分别简记为j a c o b i c g 、g s c g 、 s c h u r c g ) 求出的正则近似解的相对误差和迭代步数。 表3 - ib a a r t ( = 1 2 5 3 3 占= o 0 1 ) j a c o b i c gg s c gs c h u r c g f 厂一乙8 ： 迭代步 0 厂一k l ： 迭代步 妙一厂涮配 迭代步 f l ，乙8 ：数l | f 2 数0 乙0 ：数 o ，1 1 4 6 5 9 4 0 o 1 0 8 1 9 39 0 0 6 1 1 9 9 1 0 图3 - 1 是用三种算法分别得到的正则近似解和真解的图形比较( 其 中我们增加了问题的离散维数n = 1 0 0 0 ) 。 a j a