（计算数学专业论文）不适定问题的求解及其在图像恢复中的应用.pdf

原创性声明 l i i i i i i i i i i i i i 1 1 1 1 1 t i 1 1 1i i p i l l l l l l l l l l l l y 17 4 13 6 9 本人声明：所呈交的论文是本人在导师指导下进行的研究工作除 了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或 撰写过的研究成果参与同一工作的其他同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示了谢意 签名之彳嗍w 以够 本论文使用授权说明 本人完全了解上海大学有关保留，使用学位论文的规定，即：学校 有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容 ( 保密的论文在解密后应遵守此规定) 始云奄新签砩 期：伪o 6 6 够 上海大学理学硕士学位论文 不适定问题的求解及其在 图像恢复中的应用 作者：王芹 导师：张建军 专业：计算数学 上海大学理学院 二零一零年四月 ad i s s e r t a t i o ns u b m i t t e dt os h a n g h a iu n i v e r s i w f o rt h ed e g r e eo fm a s t e ri ns c i e n c e t h es o l u t i o n st oi l l - - p o s e dp r o b l e m sw i t h a p p l i c a t i o n si ni m a g er e s t o r a t i o n m d c a n d i d a t e ：w a n gq i n s u p e r v i s o r ：p r o f e s s o rz h a n gj i a n ju n m a j o r ：c o m p u t a t i o n a lm a t h e m a t i c s s c i e n c ec o l l e g e ，s h a n g h a iu n i v e r s i t y a p r i l2 0 1 0 摘要 本文研究不适定问题的求解及其在图像恢复中的应用不适定问题的求解在 许多科学领域都有重要应用，如地球物理学、生物医学和天体力学等学科领域 该问题求解的主要困难在于近似解的不稳定性，即初始数据的微小扰动就会引起 近似解与真解的较大偏差正则化方法是解决此问题的必经途径 本文首先基于经典的t i k h o n o v 正则化和截断的奇异值分解正则化，提出了一 种求解不适定问题的混合m s v d 正则化方法，并通过四个典型的数值例子，说明 了该算法的有效性 其次，结合双网格分裂和极小残量算法，提出了一个求解不适定问题的s c m r e s 算 法，给出了四个不适定问题的数值实验结果，并将该算法与c g l s 算法s u s c c g 算法 就相对误差进行了比较 最后，将求解一维不适定问题的s c m r e s 算法推广到二维层面上来进行图 像恢复我们对六幅图像进行了数值实验，并将该算法与l s q r 算法、c g l s 算法 和s c c g 算法在相对误差、峰值信噪比等方面进行了比较数值结果表明，此方法 能够有效地恢复模糊图像 关键词：不适定问题t i k h o n o v 正则化双网格分裂m i n r e s 算法s c c g 算 法图像恢复 a b s t r a c t t h i sp a p e rs t u d i e st h es o l u t i o n st oi l l - p o s e dp r o b l e m sa n da p p l i c a t i o n si n i m a g er e s t o r a t i o n t h es o l u t i o n so fi l n p o s e dp r o b l e m sh a v em a n yi m p o r t a n t a p p l i c a t i o n si ns c i e n t i f i ca r e a 8 ，s u c h8 8t h eg e o p h y s i c s ，b i o m e d i c a ls c i e n c e ，c e l e s t i a l m e c h a n i c sa n do t h e rd i s c i p l i n e s t h em a i nd i f f i c u l t yo ft h es o l u t i o n so fi l l - p o s e d p r o b l e m si st h ei n s t a b i l i t yo fa p p r o x i m a t es o l u t i o n i e t h es m a l lp e r t u r b a t i o n o fi n i t i a ld a t aw i l lc a u s el a r g ed e v i a t i o nb e t w e e ne x a c ts o l u t i o na n da p p r o x i m a t e s o l u t i o n r e g u l a r i z a t i o ni st h ee s s e n t i a lm e t h o dt od e a lw i t ht h i sp r o b l e m i nt h i st h e s i s 。w ef i r s ti n v e s t i g a t eam s v db a s e dh y b r i dm e t h o df o ri l l - p o s e d p r o b l e m sb yc o m b i n i n gt i k h o n o vr e g u l a r i z a t i o nw i t ht s v dr e g u l a r i z a t i o n f o u r n u m e r i c a le x a m p l e sa l ep r e s e n t e dt oi l l u s t r a t et h ee f f e c t i v e n e s so ft h ep r o p o s e d a l g o r i t h m w bt h e nd e v e l o pas c m r e sa l g o r i t h mb yc o m b i n i n gt w o - g r i ds p l i t t i n gw i t h m i n r e sa l g o r i t h m f o u rn u m e r i c a le x a m p l e sa r eg i v e n f o rc o m p a r i s o n ，w e a l s og i v et h er e s u l t so ft h es c c ga l g o r i t h ma n dc g l sa l g o r i t h mi nt e r m so ft h e r e l a t i v ee r r o r f i n a l l y , t h es c m r e sa l g o r i t h mo fs o l v i n go n e - d i m e n s i o n a li l l p o s e dp r o b - l e m si se x t e n d e dt ot w o - d i m e n s i o nc a s ei no r d e rt os o l v et h ei m a g er e s t o r a t i o n p r o b l e m s w bp r e s e n ts i xn u m e r i c a le x a m p l e s ，a n dg i v et h er e s u l t so fs c m r e s a l g o r i t h m ，l s q ra l g o r i t h m ，c g l sa l g o r i t h ma n ds c c ga l g o r i t h mi nt e r m so f t h er e l a t i v ee r r o ra n dp e a ks i g n a lt on o i s er a t i o ( p s n r ) n u m e r i c a lr e s u l t ss h o w t h a tt h ep r o p o s e dm e t h o dc a nr e s t o r et h eb l u r r e di m a g ee f f i c i e n t l y k e y w o r d s ：i l l p o s e dp r o b l e m s t i k h o n o vr e g u l a r i z a t i o n t w o - g r i ds p l i t t i n g m i n r e sa l g o r i t h ms c c ga l g o r i t h mi m a g er e s t o r a t i o n i i 摘要 a b s t r a c t 第 第 目录 绪论 研究背景与意义 国内外研究现状 论文内容与结构安排 预备知识 c g l s 算法和l s q r 算法 不适定问题的正则化 正则化参数的选取 第三章混合m s v d 正则化及其在不适定问题中的应用 1 0 3 1 混合m s v d 正则化 1 0 3 2 混合m s v d 正则化在不适定问题中的应用 1 1 第 第 s c m r e s 算法及其在不适定问题中的应用 双网格分裂 s c m r e s 算法 s c m r e s 算法在不适定问题中的应用 s c m r e s 算法在图像恢复中的应用 图像恢复的问题模型。 实验结果与讨论 图像质量评价 参考文献 作者攻读硕士学位期间发表的论文 致谢 i i i i 1 l 2 3 5 5 7 8 立旱n 地墙 章粗沈粥 一 -一 5 5 6 1 5 5 6 6 2 7 8 l 1 2 2 2 2 2 & 3 & 立覃钳讹镪 立耳弛粥 四 五 上海大学硕士学位论文 第一章绪论 本章首先介绍了不适定问题和图像恢复的研究背景和研究意义，然后介绍了 不适定问题和图像恢复的研究内容和研究现状，最后给出了整篇论文的研究内容 和结构安排想进一步了解这两个领域的研究工作，可以阅读以下这几本较为优 秀的著作【2 ，4 7 ，4 9 1 1 研究背景与意义 1 不适定问题的研究背景与意义 不适定问题广泛应用于生物医学工程、地球物理学、计算机图形学、图像重建 与恢复、控制理论和信号处理等学科领域f 1 5 ，3 4 ，3 7 ，4 2 1 ，之所以如此，很大程度上 是由工程技术领域中大量出现的待以解决的反问题造成的许多学者女1 h a n s e n 教 授、n a g y 教授以及我国的王彦飞教授、程晋教授、汪元美教授、贺国强教授等 都在这个领域做了大量的工作，并取得了许多有价值的研究成果f 1 2 ，1 5 ，3 4 3 6 ， 3 9 - 4 1 ，5 6 囚此，研究不适定问题的求解具有极其重要的理论意义及应用价值 【1 3 ，1 7 ，2 2 ，2 3 ，4 0 】 1 9 2 3 年h a d a m a r d 提出了适定问题的概念如果一个问题的解满足下列三个条 件：该问题的解是存在的、是唯一确定的、足稳定的，则称该问题足适定的反 之，这三个条件中，如果有一个不满足，我q n 称之为不适定问题一般地说不适 定问题，常常是指稳定性条件不满足，即较小的噪声扰动将会导致近似解与真解 严重偏离，为了减小这种不适定性，常常需要采用正则化技术将病态问题良化 2 0 世纪6 0 年代以来，出现了许多经典的正则化方法包括t i k h o n o v 正则化f 1 3 ， 1 7 ，2 2 、全变差j 下则化f 4 ，6 ，7 ，3 8 1 、截断奇异值分解正则化( t s v d ) f 1 3 ，2 2 ，2 7 】和 一些混合j 下则化算法f 3 1 1 ，其中最具普适性且行之有效的方法是t i k h o n o v 正则化 和t s v d 正则化t i k h o n o v 正则化的主要思想是将原不适定问题的求解转化为极 小化问题，这种方法本质上是通过乘以一个滤波因子来达到阻尼高频分量中的噪 声的效果，可以较好的平滑噪声，但是常常会产生边缘模糊现象t s v d 正则化足 通过确定截断次数k ，直接将岛频分量去除，但是选择正则化参数k 又是一个比较 团难的问题若选取的正则化参数偏大，则平滑噪声的效果较好，但是会造成图像 边缘细节的模糊，若选的偏小，恢复效果常常不理想f 1 6 ，3 2 ，4 8 因此，许多学者开 始研究诉则化参数的选取技术若已经知道噪声水平时，常常采用偏差原理方法 或者a r c a n g e l i 准则，若不知道噪声水平时，常常采用广义交叉验证法 1 3 ，3 1 、l 一曲 线方法f 2 6 ，5 0 1 或者其它一些改进算法 2 图像恢复的研究背景与意义 随着科学技术的日益发展，图像已经成为人们获取信息的必不可少的手段之 一但是由于各种原因造成的图像模糊给人们带来了不便造成图像模糊的原因 l 上海大学硕士学位论文 有很多，例如恶劣天气下传播光线的散射、物体与照相机的相对运动、摄像机聚 焦不准确、信道传输和传感器噪声等f 1 ，3 ，1 8 ，3 0 为了解决这些问题，许多学者研究了图像恢复问题图像恢复是一个典型的不 适定问题，它首先利用图像模糊的先验知识，建立数学模型，然后以此模型为基础， 采用各种图像恢复技术来估计原始图像图像恢复和图像增强都可以达到提高图 像质量的目的，f f l 是二者是有区别的图像恢复是利用图像模糊的先验知识，采 用某些方法试图恢复图像的本来面目，而图像增强则不考虑图像模糊的原因，通 过有选择的突出图像中感兴趣的特征，衰减不需要的特征和提高模糊图像的对比 度，来达到增强人类视觉特性、改善图像视觉效果的目的 但是，造成图像模糊的原因很多，这对科研工作者们是一个很大的挑战为了 恢复模糊图像的本来面日，国内外大批科研工作者一直在为寻找较为有效的图像 恢复技术而不懈努力着迄今为止，科研工作者们在图像恢复领域已经取得了很 可观的研究成果，但是在解决实际问题时，鉴于造成图像模糊原因的多样化，许 多理论和研究方法还有很大的发展空间 早期图像恢复技术的研究始于2 0 世纪中期n a s a 实验室对空间飞行器上摄像 机拍摄的模糊卫星图片的处理后来在1 9 7 8 年发生了震惊世人的美国第三十五任 总统肯尼迪遇刺事件，由于事发突然，现场拍摄到许多由运动造成的模糊图片，为 了了解、调查这个事件的真实原因，也曾经采用了图像恢复技术进行辅助调查取 证工作f 3 3 1 现在这项技术已广泛应用于生物医学、刑事侦查、地球物理和气象 预报等领域【1 5 ，3 4 ，4 2 】因此，研究图像恢复问题具有重要的理论价值和实际意 义【l ，3 ，2 0 ，2 1 】 1 2 国内外研究现状 1 不适定问题的研究现状 2 0 世纪7 0 8 0 年代，确定正则化参数的选取方法得到了飞速的发展f 1 3 ，2 6 ，3 1 ，5 4 ， 5 6 1 ，其中最具代表性的是g o l u b 提出的广义交叉验证( g c v ) 方 澌h 1 9 9 2 年h a n s e n 提 出的l 一曲线( l c u r v e ) 准则2 0 0 8 年，n a g y 等人基于传统的正则化参数选取技术，提 出了一种基于加权g c v 算法的正则化参数选取方法 1 3 】，该算法切实有效，大大 促进了不适定问题的研究进展 近年来，求解不适定问题的算法层出不穷，但是较为常用的是迭代正则化方法 我们知道，虽然迭代j 下则化方法具有较少的计算复杂性，可以求解大规模的不适 定问题，但是其收敛速度有时会很慢，为了解决这个问题，一些学者提出了多尺 度算法，提高了求解不适定问题算法的收敛速度f 2 5 ，5 8 ，6 0 h a n k e 牙h v o g e l 通过 引入预条件，将其与正则化、双网格分裂等相结合提出了一些新的较为行之有效 的算法 2 0 1 ，不仅如此，他们还为不适定问题的理论发展做出了很多贡献 2 0 ，2 1 2 0 0 4 年，n a g y 等人公开了一系列基于m a t l a b 的图像恢复迭代算法代码【3 9 ，4 0 ， 为我们有效快速解决不适定问题提供了另一种新思路2 0 0 8 年，n a g y 等人提出了 基于加权g c v 算法的混合l a n c z o s i f 则化方法1 3 1 ，为求解不适定问题的研究工 2 上海大学硕士学位论文 作做出了很大贡献 2 图像恢复的研究现状 图像恢复技术已经取得了很多研究成果早期的图像恢复经常使用的方法是 频率域法，主要是采用低通滤波去除噪声，高通滤波增强边缘，从而实现图像恢 复的目的尽管早期图像恢复算法有很多，但状得人们认可的算法大致上有逆滤 波方法和伪逆方法这两种逆滤波方法以经典逆滤波、维纳滤波和卡尔曼滤波 较为出名经典逆滤波不考虑噪声的影响，直接对造成图像模糊的点扩散函数求 逆来实现图像恢复的目的，因而当图像受到噪声的干扰时，会受到不适定性的困 扰维纳滤波方法是通过将图像恢复问题转化为能量极小化问题来实现图像恢复 的，该方法的优点足考虑了噪声的影响，具有较小的计算复杂度，缺点是需要预 先知道原始图像和噪声的功率谱卡尔曼滤波及一些改进算法也具有较好的恢复 能力【1 4 ，5 1 ，5 5 】伪逆方法是基于点扩散函数离散矩阵奇异值分解的算法，但足 当有噪卢时也会碰到不适定性这个困难 1 9 9 9 年，h a n k e 和v o g e l 提出了基于正则化方法的双网格分裂法，并给出了一套 较为完美的理论支持和相应的算法及数值结果f 2 0 ，2 1 1 2 0 0 0 年，j a c o b s e n 等人将 双网格分裂迭代算法与c g 算法相结合，提出了s c h u rc o m p l e m e n tc g 算法，为求 解不适定问题提供了一个更为可行的工具2 s 2 0 0 7 年，h a n s e n 矛l l j e n s e n 将k r y l o v 子 空问方法与正则化相结合，提出了一系列图像恢复的有效算法，但是恢复效果紧 紧依赖于迭代步数，故选择合适的正则化参数较为关键f 2 4 2 0 0 8 年，n a g y 等人 提出了种较为有效的正则化参数选取方法f 1 3 1 著名学者t f c h a n 也在不适 定问题求解和图像恢复领域取得了相当大的研究成果f 4 ，6 1 0 1 贺国强将广义 极小残量方法同正则化技术相结合，提出了一种较为有效的图像恢复的正则化 混合g m r e s 方法3 5 此外，将s c h u r 方法与- k r y l o v 子空间方法和j 下则化相结合 也可以扶得较好的恢复效果2 0 0 8 年，s t e w a r t s h k i m i t e i 提出了一种超线性最& - - 乘s c h u r 方法进行图像恢复这些研究成果不仅为我们进行图像恢复提供了有效 的研究工具，还为我们进一步开展研究工作打下了良好的基础 虽然各种图像恢复算法层出不穷，但足图像恢复领域还具有较大的发展空间 神经网络方法 4 3 ，5 2 1 、遗传算法【5 3 ，5 9 1 、小波技术f 2 5 ，5 2 】和图像分割技术【4 2 等方法都为图像恢复注入了新活力此外，彩色图像恢复与增强也取得了很多 成果，如著名学者t f c h a n 和h y s h u m 都在彩色图像恢复与增强领域做出了很 大贡献2 9 ，5 7 q s h a n 和j y j i a 也提出了具有较好恢复能力的彩色图像恢复算 法 4 5 】 1 3 论文内容与结构安排 本文基于经典的求解不适定问题的正则化方法，首先提出了一种求解不适定 问题的混合m s v d 币则化方法接着，结合双网格分裂和极小残量法，我们推导 了系数矩阵为对称正定矩阵的线性方程组a x = b 的迭代算法最后，我们探讨 了图像恢复的相关算法 全文共分为血章： 3 上海大学硕士学位论文 第一章主要介绍了不适定问题和图像恢复的研究背景、研究意义、研究现状、 论文的主要内容和结构安排 第二章回顾了论文所涉及的一些预备知识首先简要描述了c g l s 算法和l s q r 算法接下来介绍了两种经典的正则化方法t i k h o n o v 正则化和截断的奇异值分解 正则化( t s v d ) 最后讨论了正则化参数的选取方法 第三章我们描提出了求解不适定问题的混合m s v d 正则化方法我们对四个典 型的数值例子，进行了数值实验，数值结果表明，我们提出的算法是有效的 第四章首先回顾了双网格分裂思想，然后提出了基于双网格分裂和极小残量 法的s c m r e s 迭代法最后，我们对四个典型的数值例子，进行了数值实验数 值结果表明，我们提出的算法是可行的 第五章将求解一维不适定问题的s c m r e s 算法推广n - 维层面上来进行图像 恢复我们选取了人幅图像进行了数值实验，并与l s q r 算法、c g l s 算法和s c c g 算 法在相对误差、峰值信噪比和主观视觉效果等方面进行了比较数值结果表明， 此方法是可行的，能够有效地恢复模糊图像 4 上海大学硕士学位论文 第二章预备知识 本章首先介绍了我们所研究的问题模型，然后回顾t c g l s 算法、l s q r 算法、 正则化方法和正则化参数的选取技术等相关知识 对于线性不适定问题 k x = y ，( 2 0 1 ) 其中，k 胛煳，y j f p 对其进行t i l ( 1 l o n o v 正则化可得 z = m i n l i k x 一剪1 1 2 + a l i l x i l 2 ) = m i n l l k x y l l 2 + a l i l x i 2 ) 蚓m 侧| 2 它等价于解法方程组 ( k t k + a l t l ) x = k 丁y ， 其中，? 表示转置，”l f 表示2 范数，口 0 ，a 控制正则化程度，称为正则化参数， k 胛黼是一个条件数很大的矩阵，y 胛为一给定的向量矩阵l 一般可取为 单位矩阵厶 记 m = l t l r n 黼，b = k t y ， a ：k t k + a m ，( 2 0 2 ) 则可以将正则化后的原问题转化为求解方程组 a x = b ，( 2 0 3 ) a 肝黼是一个对称正定( s p d ) 矩阵，b 舻为一给定的向量 2 1c g l s 算法$ f l l s q r 算法 c g 算法是1 9 5 2 年由h e s t e n e s 和s t i e f e l 提出的，这种方法在求解大型稀疏线性方 程组时效果较好，但足对于大型稠密线性方程组和不适定问题，其收敛特性则因 具体的情况而异将c g 算法应用于求解线性最小二乘问题m i ni l y k x l l ，可以得 茹 至i j c g l s 算法，具体算法如下【3 4 ，4 4 】 算法2 1 1 c g l s 算法 1 初始化：y o = 0 ，r o = y k x o = y ，z o = k t r o = k t y ，p o = z o ； 2 迭代：对k = 0 ，1 ，2 ，n ，计算 5 上海大学硕士学位论文 w k = k p k 钒= i i z 1 1 2 l l 叫k l l 2 x k + l = z 七+ q 七尹 他+ 15 仇一o l k w k z k + l2k t 强+ 1 风= l i + 1 1 2 l l z k l l 2 m + l = z k + l + 反p k 。 l s q r 迭代方法是p a i g e 和s a u n d e r s 于1 9 8 2 年提出的基于l a n c z o s 过程的一种方 法，其基本思想足将原问题转化为用双对角化方法求解最小二乘问题m i n 恼一 z k x l l 由于求解过程用到了q r 因子分解法，因此被称为l s q r 方法具体算法如下 【3 4 】 算法2 1 2 l s q r - 算法 1 初始化：z l u l = y ，q l 钉1 = k t u l ，w 1 = 钉1 ，z o = o ，石1 = 屈，万l = o t l ，i = 0 2 迭代：对i = i + 1 ，进行双对角化 3 t + l u i + 12k u t c q u i o l i + 1 v i + 12k t u i + l 一屈+ l y i 3 确定正交变换，进行q r 分解 p i = ( 孝+ 风1 ) m q = 磊胁 8 i = 8 t u | 队 巩+ l 。s i d i + 1 见+ l2 一q c 0 1 + 1 如= 龟也 如+ l = 8 i 识 4 确定正交变换，进行q r 分解 戤= x i 一1 十( 如风) 叫 w i + l = + 1 一( 也+ 1 p i ) w i 若满足则终止迭代，否则转2 6 上海大学硕士学位论文 各种仿真数值结果表明，在求解大型稀疏线性方程组和最小二乘问题时，l s q r 算 法和c g l s 算法具有相似的数值特性当系数矩阵病态时，l s q r 算法在求解大型 稀疏线性方程组时只有收敛速度快、计算精度高、数值稳定性好的特点，因此备 受大家的青睐。 2 2 不适定问题的正则化 目前已经有许多科研工作者根据不同的不适定问题提出了许多正则化方法，下 面我们简要的介绍一下t i k h o n o v 正则化和截断的奇异值分解正则化 t i k h o n o v 正则化是t i k h o n o v 于2 0 世纪6 0 年代提出的，其基本思想是在原问题 的残量和解的范数之i m j g i 进了一个权重，既保证了近似解的拟合效果，又限制了 系数矩阵较小奇异值对近似解的扰动，从而保证了解的存在性和唯一性条件得到 满足 一般形式的t i k h o n o v 正则化形式如下 m i ni i k z 一l i + a l l l x l 2 ( 2 2 1 ) z 其中，a 0 ，a 称为正则化参数，通常可以由偏差原理方法、广义交叉验证( g c v ) 方 法或l 一曲线方法求得矩阵l 可取为单位矩阵问题( 2 2 1 ) 等价于求解法方程 ( k t + a 1 ) z = k t y ( 2 2 2 ) 设k 的奇异值分解为= 仉1 吁，其中仉= 【札t ，u 2 ， 。】，= 【 0 1 ，v 2 ， 中 的向量分别称为k 的左、右奇异向量，e 1 = d i a g ( a 1 ，0 2 ，如) ，o n a n 一1 s y l ，吼称为k 的奇异值可以求得问题( 2 0 1 ) 的解 利用k 的奇异值分解，可得( 2 2 2 ) 的解 ( 2 2 3 ) 杀亟o i 饥 ( 2 2 4 ) 因为不适定问题近似解与真解的偏差是由线性方程组系数矩阵较小的奇异值 引起的，因此，我们将较小的奇异值进行截断，就会使近似解逼近真解了但是究 竟保留多少个奇异值，这就足j 下则化参数的选取问题了囚此，选取的j 下则化参 数越准确，近似解的误差就越小由t s v d 正则化求得的不适定问题的解的一般形 式为 kt z ：f 业饥 ( 2 2 5 ) 葛口 其中，k 为正则化参数 7 亟吼 n：l i l z n 僦 i | q z 上海大学硕士学位论文 2 3 正则化参数的选取 下面简单介绍一下正则化参数的三种选取办法：偏差原理方法( m o r o z o v 偏差 原理) 、广义交叉验证( g c v ) 方法和【广曲线方法【5 ，2 6 ，3 1 ，5 0 】 偏差原理方法足指在已知噪卢的功率谱1 1 n 1 1 的大小时，使正则化解满足 i i 可一k x 。f i = 6 l l n l l ，6 1 进而转化为关于正则化参数q 的非线性方程 ，( q ) = i l y k x 。0 6 l l n l l 的求解问题这种方法的优点是当噪声趋于零时，j 下则化解逼近真解效果较好缺 点是近似解的精确度依赖于噪卢大小估计的准确程度有关用偏差原理方法选取 正则化参数的研究成果请参考【1 5 1 g c v 方法是由g o l u b 提出的，它的原理是选择正则化参数q 使g c v 函数达到最 小值， g ( 班搿， 其中， 磁= ( k t k + q j ) 1 矿 在已知系数矩阵奇异值的情况下， 打( 卜k k ) 5 南 g c v 方法的缺点是，g c v 曲线在极小点附近往往过于平坦，很难准确确定哪一点 是最小点 2 0 0 8 年，n a g y 等人提出- f w - c c v 算法【1 3 】，该算法可以精确地选取正则化参 数w - g c v 算法的基本思想足选择正则化参数o t 使得w - g c v 函数达到最小值， 其中w - g c v 函数为 g c 邺，= 器筹器， 记o t k , 硎为在第k 步迭代中最优的参数，满足 0 o t k ，o v t 6 r m i n ( b ) ， 其中，- c 7 r n i n ( 鼠) 是矩阵最小的奇异值对于较少的迭代步数尼，假设在第k 步迭代已 经知道了o z k o p t ，那么可以通过下面的式子求出权重u 一 i 羞( g ( 邺) ) l 如讲。o 事实上，我们足不知道a 七，o p t 的，所以我们根据o l k ，叩t = 0 m t n ( 鼠) 来求出玩当迭代 步数尼变得很大时，。( 鼠) 变得非常接近于零，这种选取方法效果就不好了，此 时，令u 七取丽，蕊，瓦的均值，进而，就可以求出。詹，卿了 8 上海大学硕士学位论文 i 广曲线方法是h a n s e n 于1 9 9 2 年提出的，基本思想是：使l 曲线的曲率达到最大 的参数a 即为正则化参数l - 曲线是在直角坐标系中以( 1 0 9 l l k x 。- y l l ，l o g l l x 。| | ) 为 坐标构成的曲线当采用t i k h o n o v 正则化并且已知系数矩阵k 的奇异值分解时该 方法非常有效但在拟合l 曲线时，参数点数目的选取很重要，如果选取的参数点 过多，则计算量较大，参数点较少，则求出的正则化参数不够准确 9 上海大学硕士学位论文 第三章混合m s v d 正则化及其在不适定问题中的应用 这一章我们首先回顾t l a n c z o s 双对角化过程【1 3 】接着基于经典的t i k h o n o v e 则化和t s v d 正则化，提m 了一种新的f 则化方法一混合m s v d 正则化然后对四个 典型的不适定问题进行了数值实验数值结果表明，我们的算法是可行的和有效 的 3 1 混合m s v d , 1 ：贝, 1 1 化 对原不适定线性方程组系数矩阵k 进行k ( k = 1 ，2 ，n ) 步l a n c z o s 双对角化后 得到矩阵 帆 m ( 知+ 1 ) ， 圪) 。知， y k + 1 ) 。1 和 鼠) ( 七十1 ) 七满足如下关系 k t 帆= k 酲+ 口知+ 1 y 七+ 1 e 玉1 k k = 帆风 原问题( 2 0 1 ) 转化成最小二乘问题进行求解 呶r a i n 。l i z 一可l i 。呼懒，一例| ( 3 1 1 ) 其中，e 南+ 1 表示k + 1 维单位阵的最后一列，o l k + 1 表示矩阵风+ 1 的第k + 1 个对角线 元素和圪具有正交的列向量，肌的第一列取为y l l y l l ，p = 叭经过第k 步迭 代以后，得到原问题的近似解为 z 知= 氓， 传统的求解投影问题( 3 1 1 ) 的方法是混合l a n c z o s i e f l , l j 化方法，它是通过迭代正则 化方法求解投影问题的，即在每步迭代中对投影问题进行t i k h o n o v 正则化，然后 采用直接求系数矩阵逆矩阵的方式求解正则化后的投影问题，每步迭代中的正则 化参数是通过g c v 技术求得的 我们知道，不适定问题的近似解严重偏离真解是囚为线性方程组系数矩阵具 有部分较小的奇异值，数据y 较小的扰动会被这些较小的奇异值放大因此，如果 我们保留较大的奇异值，而对稍微小的奇异值进行平滑处理，对非常接近于零 的奇异值进行截断以避免较小的扰动被放大，就能得到较为稳定的近似解，这就 是m s v d 正则化的基本思想 对于不适定问题( 2 0 1 ) ，可以将它的解( 2 2 3 ) 写成如下形式 ( 3 1 2 ) 其中，o n a n 一1 o k + r + l 口o k + r o k + 1 、石+ 盯o k 0 2 o 1 ( 0 克礼，0 r 他一免) ，口r 1 0 眈 亟吼 h馆m扛 十 仇 亟吼 枷斟 + 眈 亟以 。甜 = z 上海大学硕士学位论文 我们保留近似解( 3 1 2 ) 中较大的奇异值o 1 ，o k 对应的第一部分，平滑稍微小 的奇异值o k + l ，吼+ r 对应的第二部分，截断非常接近于零的奇异值盯七+ 件1 ，对 应的第三部分，就可以避免较小的扰动被放大，得到不适定问题的较为稳定的解 该算法具体形式如下 算法3 1 1 m s v d 正则化算法 1 初始化：z = 0 i f 2 计算k 的奇异值分解：k = u i e l 吁 3 通过g c v 方法求正则化参数q ，选取m s v d 参数口 4 对i = l ，2 ，n ，计算 ( i ) 如果毋v z + 口，则 z = z + 亩u t b 仇 ( i i ) 如果仃吼 、伍+ 口，贝4 z = z + 熹等仇 混合m s v d 正则化方法的构造思想是：通过l a n c z o s 双对角化把大型不适定问 题的系数矩阵投影到低维空问风，然后对维数较小的方程组( 3 1 1 ) 运用m s v d i i 二 则化方法来求解具体算法如下 算法3 1 2 混合m s v d 正则化算法 1 初始化：f = 0 舻 2 对k 进行l a n c z o s 双对角化k = w b y t ，将原问题转化成投影问题( 3 1 1 ) 3 对k = 1 ，2 ，。，计算 对鼠进行奇异值分解：b k = 巩2 谬， 通过g c v 方法求出正则化参数q ，选取圪， 运用m s v d 正则化算法求出投影问题( 3 1 1 ) 的解f ， 求出原问题的第k 个近似解：z 七= y k f 3 2 混合m s v d t t ：贝, 1 化在不适定问题中的应用 本节，我们对四个典型的数值例子“d e r i v 2 ”、“s h a w ”、“h e a t ”和“b a a r t ”进行 试验，这四个例子取自文献 2 3 】我们同时与加权的g c v 方法( w g c v ) 【1 3 、混 合l a n c z o s 正则化方法【1 3 $ u l s q r 算法进行了比较在数值实验时，我们产生的 矩阵阶数足2 5 6x2 5 6 对于“d e r i v 2 ”，我们取仃= 1 0 ，而对于“b a a r t ”、“s h a w ”和“h e a t ”， 我们取仃= 1 0 一，迭代步数为8 0 正则化参数由g c v 方法产生，真解为z t ，雠无噪 1 1 上海大学硕士学位论文 声扰动的右端常数项y t ，鸺= k x t ，雠，受噪声干扰的可由可= y t ，懈+ 5 n 产生，其中， 是均值为零方差为1 的高斯白噪声，且6 满足 魍：0 0 1 i l y t ，批0 例3 2 1 d e r i v 2 ，是通过离散第一类积分方程可( s ) = 詹k ( s ，) z ( ) 出获得系 忌( s ，z ) = s ( t - 1 ) , s t 邢，= 嚣： 小，= 茎掣，篓： 例3 2 2 s h a w ”是一个一维图像重建问题k 和z 打。是在s ，t 【一吾，詈】上通 ) = ( c 。s ( s ) - j rc o s ( 似s i n f ( u ) ) 2 邢) = 嘉e 卅知 上海大学硕士学位论文 例3 2 4 b a a r t ”是在s 【0 ，专1 上通过离散第一类积分方程秽( s ) = 石k ( s ，t ) x ( t ) d t 来 构造系数矩阵耐口右端常数项孙雠其中， k ( 8 ，t ) = e x p ( sc o s ( t ) ) ， x ( t ) = s i n ( t ) ， 秒( s ) ：2 s i n _ = ( 一h s ) 图( 3 2 1 ) 足混合l a n c z o s 正则化算法、混合m s v d 正则化算法、l s q r 算法和w g c v 算法求解四个不适定问题时产生的相对误差图由这四个图可以看出，对 于”h e a t “、”s h a w “和”b a a r t “，混合m s v d 正则化算法可以达到与w - g c v 算法类 似的效果，对于”d e r i v 2 “，效果稍差些图( 3 2 2 ) 是混合m s v d 正则化算法产生的 近似解与真解的逼近程度对比图，实线代表真解，虚线代表混合m s v d 正则化算 法产生的近似解数值结果表明，我们的算法是有效的 ( a ) h e a t( b ) d e r i v 2 ( c ) s h a w( d ) b a a r t 图3 2 1 四种算法求解四个不适定问题产生的相对误差对比图 1 3 上海大学硕士学位论文 ( a ) h e a t ( c ) s h a w ( b ) d e r i v 2 ( d ) b a a r t 图3 2 2 混合m s v d 正则化算法产生的近似解和真解的比较 1 4 上海大学硕士学位论文 第四章s c m r e s 算法及其在不适定问题中的应用 1 9 9 9 年h a n k e 和v o g e l i t 正明t s c h u r 丰b 解法 ：匕k r y l o v 子空间方法具有更好的收敛 效果【2 1 2 0 0 0 年，j a c o b s e n 提m 了一种求解大型不适定问题的有效解法一s d m r c g ( s c c g ) 算法，这种算法是结合s c h u r b 思想和c g 算法提出的，它对于求解不 适定问题十分有效本文在上述思想的启发下，针对不适定问题提出了s c m r e s 算 法。我们通过四个数值例子说明了该算法的有效性 4 1 双网格分裂 我们将尼。胁空间分裂成两个子空间：七维子空间k 和佗一k 维子空间w k ，其中 和么是m 正交的令礼后级列满秩矩阵的列构成k 的一组基，礼x 一七) 级列 满秩矩阵矽的列构成w ；的一组基，且砂和砂满足 矿m e = 0 h 一七，矽t m e = 厶一七 对于对称正定线性方程组( 2 0 3 ) ，满秩矩阵眵叫r n 黼将其转化成 眵妒】ta 【砂妒】妒】一1z = 【妒妒】t b 我t f 弓l 入记号 a 1 1 = 矿a ，a 1 2 = 丁a 妒，a 2 l = 妒t a 咖，a 2 2 = 妒t a 妒， 定义 r1 让：l 也1l ：妒1 一z 铮z ：币让。+ 妒u 。， lu 2i 那么( 2 0 3 ) 可化为如f 形式 匕北甜 通过高斯消去法，我们得到 a 。l la 船一a a 。1 。2 a 叠a 。： ： = 妒t 6 一a d p 。t 。b a 寻护6 。 其中，右下角的块矩阵 s = a 2 2 一a 2 1 a - a i a l 2 ， 是矩阵a l l 的s c h u r 补，由( 4 1 1 ) 可以推出 u l = a - f f 妒t b a -