（计算数学专业论文）离散tikhonov正则化解的条件数以及加权moorepenrose逆的二阶条件数问题.pdf

中文摘要 摘要 本文主要分两部分。第一部分讨论离散t i k h o n o v 正则化解的条件数问题。 我们给出的相对范数型条件数的显式表达式推广了m a l y s h e v 【s i a mj m a t r i x a n a l a p p l ，2 0 0 3 ，2 4 ，1 1 8 6 1 1 9 6 】的结果，给出了更一般意义下的相对范数型条 件数的可计算的精确表达式，并通过数值例子将由此得到的线性向前误差界 与n a n s e n 等人的结果比较，说明新的上界的优越性。此外，我们还利用增广 方程对离散t d c i l o n o v 正则化问题进行分量扰动分析。进一步，我们研究了离散 t t k h o n o v 正则解的混合型以及分量型条件数，给出它们的显式表达式。我们的 结果填补了之前文献在这一理论分析方面的空缺，并且在实际计算过程中我们 的结果还可以用于比较各种正则化参数选取策略。本文第二部分主要研究加权 m o o r e - p e n r o s e 逆的条件数问题，关于最一般意义下定义的加权m o o r e p e n r o s e 逆的范数条件数，目前为止还无法给出它的显式表达式，在本文中我们推导出 它的一个最优上界并给出一些特殊矩阵的加权m o o r e p e n r o s e 逆条件数的显式表 达式。进一步，我们研究了计算加权m o o r e p e n r o s e 逆的条件数的敏感性问题， 讨论了“条件数的条件数”，也就是二阶条件数的一些性质。 关键词；条件数，向前误差分析，向后误差分析，分量扰动，t i k h o n o v 正则化，加权 m o o r e - p e n r o s e 逆。二阶条件数 中图法分类号：0 1 5 1 2 1 一一 英文摘要 a b s t r a c t i nt h i sp a p e r , w ec o n s i d e rt h en o r m w i s e m i x e da n dc o m p o n e n t w i s ec o n d i t i o n n u m b e r sf o rt h ed i s c r e t et i l d a o n o vr e g u l a r i z a t i o n w eg i v e 出ec o m p u t a b l ee x p l i c i tf o r - m u l af o rt h e s ec o n d i d o nn u m b e r s a i s ow eg i v et h en u m e r i c a lt e s t st oi l l u s t r a t eo u rt h e - o r e d c a lr e s u l t sa n dv e r i f yt h a to u rn e wf o r w a r de r r o rb o u n di ss h a r p e rt h a nt h ee x i s t i n g r e s u l t s t h es e c o n dp a r to ft h i sp a p e ri so nt h el e v e l - 2c o n d i t i o nn u m b e rf o rw e i g h t e d m o o r e p e n r o s ei n v e r s e w ea l s oc o n s i d e rt h ep e r t u r b a t i o np r o p e r t yo ft h ec o n d i t i o n n u m b e rf o rw e i 吐t e dm o o r e p e n r o s ei n v e r s e ，i e ，t h el e v e l 一2c o n d i t i o nn u m b e r k e yw o r d s ： c o n d i t i o nn u m b e r , f o r w a r de r r o ra n a l y s i s ，b a c k w a r de r r o ra n a l y s i s ， c o m p o n e n t w i s cp e r t u r b a t i o n ，t t k h o n o vr e g u l a r i z a t i o n ，w e i g h t e dm o o r e - p e n r o s ei n - v e r s e ，l e v e l - 2c o n d i t i o nn u m b e r c h i n e s el i b r a r yc l a s s i f i c a t i o nn u m b e r ：0 1 5 1 2 1 一一 - t l - - 月i j 昌 条件数刻画了一个问题的解对于输入数据扰动的敏感程度。1 9 6 6 年，r i c e 建立了条件数的一般理论。令毋：彤一r 是两个有限维欧式空间上的映射。 若咖在a o r 。的邻域上连续且f r c h e t 可微，那么，根据r i c e 的理论，妒在0 0 的相对范数条件数可以按如下给出 c 删计哟峪s u 刮p 虫( 烛铲，榭) = 塔觜 其中( n o ) 是妒在n 0 的f r 6 c h e t 导数。 相对范数条件数的定义可能存在一些缺陷。一方面，这种意义下的条件数 没有考虑输入输出数据的稀疏性结构( 比如是否含有很多零元素) ；另一方面， 由于输入输出数据的各个分量大小可能不在一个数量级上甚至差别很大，这使 得小元素上的相对误差与大元素上相对误差大小差别可能会很大，因而，用范 数( 比如用2 一范数) 来衡量误差可能导致不准确。 克服这个问题的一个方法就是考虑分量误差分析。准确地说可以考虑另外 两种条件数，即混合条件数和分量条件数。所谓混合条件数，就是用范数来衡 量输出数据的误差而用分量来衡量输入数据的误差；而分量型条件数则是输出 数据和输入数据都用分量来衡量。 本文主要分两部分。第一部分讨论离散t t k h o n o v 正则化解条件数问题。我 们在第一章里以求解非奇异线性方程组为例，介绍了范数型扰动分析和分量型 扰动分析的发展和一些经典结果，并引入了g o h b e r g 关于范数型、混合型和分 量型条件数的一般性结论。在第二章里，我们给出离散t t k h o n o v 正则化问题相 对范数条件数、混合条件数以及分量条件数的显式表达式。本文第二部分主要 研究加权m o o r e p e n r o s e 逆的条件数问题，关于在最弱的限制条件下定义的加权 m o o r e p e n r o s e 逆的范数条件数，目前为止的研究较少，也还无法给出它的显式 表达式，在本文中我们给出了它的一个最优上界，并给出一些特殊矩阵的条件 数的显式表达式。进一步，我们研究了加权m o o r e p e n r o s e 逆的条件数的扰动问 题，讨论了“条件数的条件数”，也就是二阶条件数的一些性质。 i v 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名： 论文使用授权声明 日期：护- 6 j 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：盈导师签名：象主毛 日期： 0 7 6 ，6 第一章扰动分析与条件数理论 第一章扰动分析与条件数理论 在一个问题的输入输出数据有一定误差或者问题求解过程中存在不精确的 算术运算时，计算的解与问题的精确解之间会存在误差。误差分析理论往往考 虑下面三个方面的问题。以线性系统a x = b 为例，其中a p n ： ( 1 ) 计算得到的方程的近似解y 如果精确地满足一个扰动方程( a + a a ) y = b + a b ，这个扰动方程与原方程相差多少? 也就是，近似解y 的向后误差 有多大? ( 2 ) 对于一个给定的近似解，能否估计出它与精确解之间的误差? 也就是，如 何对问题进行向前误差分析? ( 3 ) 输入数据a 和b 的扰动，对解z 的影响有多大? 也就是，解对于输入数据 的扰动有多敏感? 1 9 4 7 年，y o nn e u m a n n 和g o l d s t i n e 在发表的 n u m e r i c a li n v e r t i n go fm a t r i c e s o fh i g ho r d e r 一文中，考虑了基本定点算术运算舍入误差满足的不等式，并 给出了用消去法进行矩阵求逆运算的严格的舍入误差分析。他们的工作奠定 了现代误差分析的基础，是自1 9 4 7 年发表以来被引用最广的一篇数值分析方 面的文献 7 5 ，w i l l k i n s o n ，1 9 7 1 】。n e u m a n n 和g o l d s t i n e 的误差分析是典型的 向前误差分析( f o r w a r de r r o ra n a l y s i s ) ，虽然其中也隐藏了一些向后误差分析 ( b a c k w a r da z t o ra n a l y s i s ) 的思想。而g i v e n s 则被认为是向后误差分析方面的先 驱，他在【2 3 ，1 9 5 4 中第一次明确提出并强调了向后误差分析，这是在现代误差 分析史上具有划时代意义的事件【7 5 】。与向前、向后误差分析密切相关的一个 概念就是条件数( c o n d i t i o nn u m b c r ) 。一个问题的解的条件数，描述了这个问题 的解对于数据的扰动的敏感程度。关于条件数的般性理论，最早则是由r i c e 5 5 ，1 9 6 6 建立的。 对于本章开始提出的关于扰动理论的三个基本问题，实际上我们都可以 从范数型扰动分析和分量型扰动分析这两方面加以考虑。 1 。1 范数型扰动分析与相对范数条件数 我们曹先给出一些经典的范数型扰动分析结果。在这一节里，我们用| f “ 表示任何向量范数以及相应的诱导矩阵范数。下文出现的矩阵e 和向量f 是任 意给定的。 1 9 6 7 年，r i g a l 和g a c h e s1 5 6 考虑范数衡量的向后误差 ，阳，( y ) ：= m i n e ：( a + a a ) y = 6 + a b ，i i a a l l i i e i l0 i 6 i ise l l ，| | ) ，( 1 1 ) 第一章扰动分析与条件数理论 并推导出 嘶= 热， ( 1 2 ) 兵中r = b a 。 对于线性方程组解的向前误差分析，我们有如下的经典结果| 4 4 】：假设 f , a a l 【e u e | | ，f i , x b l i l i ，0 ，并且e i l a 1 e | j 1 ，则有 百liz-yll南(皆坩1iiilli i i i e ie i ) ， ( 1 3 ) l l z 0 二 一e i l a 一1i i l 。| i 1 “几 u “ 一7 这个上界中关于e 的一阶扰动项是可以达到的。 根据r i c e 5 5 条件数理论，可以定义如下相对范数条件数 训舢) ；弛s u p 觜：删( z + a z ) = 6 + 6 ， i i z x a i i e l i e mi i a b l l e | | 刑) 并且- 7 以得到【删 仡e ，( 4 ，z ) = 且墨 碧 韭+ i i a 一1 1 1 1 1 e m 我们借用h i g h a m 【4 4 】的一个侧子来看看范数型扰动分析可能存在的几点 缺陷。令a 是8 8 的v a n d e r m o n d e 矩阵，a 的( i ，j ) 位置上的元素是j 2 “o ) ， b = e l 为单位矩阵的第一列。那么线性方程组a x = b 的精确解为a “的第一 列。用m a t l a b ( 机器精度为= 1 1 1 0 - 1 6 ) 执行部分主元高斯消去法得到 线性方程组a z = b 的一个近似解y 。取e = a ，= b ，对于o o - 范数，有 弧6 ( ) = 2 2 1 1 0 - 1 0 。这样小的向后误差估计值还是令人满意的，但是它也存 在着一些问题。首先，在这个闯题中，矩阵a 的最小元素( 1 ) 与最大元素( 8 “) 之间相差了大约1 2 个数量级，所以，当向后误差相对于大的矩阵元素比较小 的时候，可能相对于小元素，这个误差就会比较大。这个例子恰恰就是这种情 况。其次，用范数衡量的向量b 的误差，允许b 中零元素有非零扰动。这有时 是不可取的，比如我们正是要求近似解封是扰动后的矩阵a + a 的逆的第一 列向量时，就要求扰动后的右端项仍平行于e 。 考虑向前误差分析，我们将上例中右端项b 取作b = a e ，r 其中e = 【1 ，1 ，1 严。取a = 8 u l a l ，a b = s u l b l ，令2 是扰动后方程( a + a a ) z = 一2 一 第一章扰动分析与条件数理论 b + a b 的解，那么很容易得到 错卅铷枷- 1 2 而另一方面，在( 1 r 3 ) 中，取e = 8 u ，e = a ，f = b ，那么利用( 1 3 ) 计算得的 上界是3 0 3 t o 。可见，对于扰动矩阵及扰动右端项这种特殊取法，( 1 3 ) 中 的上界并不是一个很好的估计。这就要求我们采用分量型的扰动分析。 1 2 分量型扰动分析与混合条件数、分量条件数 1 9 6 4 年，o e t t l i 和p r a g e r 5 2 】给出了求解线性方程组a x = b 的分量型向后 误差( c o m p o n e n t w i s eb a c k w a r de r r o r ) ： u f ，0 ) = r a i n f ：( a + a a ) y = b + a b ，i aj c e ，i a b is ， = m a x 爿， 这里e ，均为非负的，r = b a y 。取e = f a 卜，= b ，这就得到了相对 分量向后误差( c o m p o n e n t w i s er e l a t i v e b a c k w a r d e r r o r ) 。注意到考虑分量扰动时， a 或b 的零元素相应的扰动必为零。相对分量向后误差的另一个重要性质是误 差分析结果不依赖于如何对线性方程组进行尺度变换( s c a l i n g ) ，也就是说，如 果选择对角阵两和岛将线性方程组a z = b 变换为( 毋4 岛) ( s i l z ) = 最6 ，那 么将变换为s 彳1 y ，而相对分量向后误差u 保持不变。 最早将分量扰动分析应用于推导向前误差界的是b a u e l 【3 ，1 9 6 6 】，但是 b a u e r 没有明确给出结果。s k e e l 在这一方面做了研究 5 9 ，1 9 7 9 ，他的结果 可以推广到如下更一般的结论【4 4 】：令a z = b ，( a + a a ) y = b + a b ，假设 l a a l 墨c e ，i a b lse ，并且e i i i a - 1 l e n 1 ，这里，l | 1 i 是一个绝对范数+ ，那 么 ! j z s ， ， e j ! l a 一1j e 陋j + 1 0 酬i 一1 一e i i a 一1 ii l f 0i l z 0 ( i 4 ) 并且，对于o 。范数来说，这个上界中关于e 的一阶扰动项是可以达到的。 利用上述向前误差界，可以定义并给出如下的“混合型条件数”， c o n d e j ( 舢) ：= 翱s u p 特：( a + 叫( z + 5 x ) = 6 + 6 ， i a i e e ，i a b l e ，l( 1 5 ) 称一个向量范数”6 为绝对托数是指t 对任意z c ”，有忙| | = i 0 。 一3 一 第一章扰动分析与条件数理论 一 ! ! ! 生二：! 星! 苎! ! 垒二：! ! j 一 恻f 取e = i a i ，= i b i ，就得到s k e e l 在【5 9 】中定义的条件数 础绀= 警 此外，【5 9 】中还引进了矩阵的如下条件数 c o n d ( a ) ：= c o n d ( a ，e ) = i a 一1 i i a | | i o 。sk o 。( a ) = a i i o 。i i a 一1 | f 。 ( i 6 ) 我们也把c o n d ( a ) 称为矩阵a 的“s k e e l - 条- 件数”。 1 9 8 9 年，r o l m 【5 7 】用区问分析的思想引入并推导出如下的“分量型条件数” c ( 郇) ：= 峄脚s u p 丽l m x d ：( a + 酬( z + a z ) = 6 + 6 i a i e l a l ，i 6 l - e l b l ) ( 1 7 ) = m a x ! ! 垒：! ! ! 墨! ! 竺! ! 垒：i ! ! 1 2 1 川， g o h b e r g 等人在重要的文献【2 4 _ 2 6 】中对范数型、混合型和分量型条件数给 出了一般性的结论。值得注意的是，h i g h a m 在【4 4 】中是把( 1 5 ) 的c o n d e , f ，。) 称作分量型条件数，为区别起见，我们仍沿用h i g h a m 的记号c o n d f ，( a ，g ) ， 而与g o h b e r g 的文中名称保持一致，称其为混合条件数，把( 1 7 ) 的c ( a ，b ) 称作 分量型条件数。 还是利用上一节的两个例子，我们来比较一下分量型扰动分析的结果。当 b = e 1 时，设y 是扰动后的线性方程组的解，也就是扰动后的系数矩阵逆的第 一列，取e = i a i ，= i b i ，我们有u e ，i ( y ) = 5 7 6 1 0 - 1 3 。这意味着如果我们 从分量意义上衡量扰动，那么在有舍入误差情况下进行计算得到的近似解，相 当于对原方程进行一定程度扰动以后的方程的精确解，这个扰动大约比机器精 度大4 个数量级。对于上一节第二个例子，用分量型扰动分析得到的向前误差 界( 1 4 ) 为 蜂二善坠 0 ，问题( 2 1 ) 有唯一 llj 解。注意到，问题( 2 1 ) 等价于如下最d , - - 乘问题 幽。一。 ( 2 2 ) 问题( 2 2 ) 的法方程是 ( a t 4 + a 2 l 丁l ) z = a r b ，( 2 3 由此，可以直接得到正则化解的如下显式表达式： z = ( a r a + a 2 l r l ) 一1 a t b 容易看出，与( 2 1 ) 相对应的扰动问题以及它的正则方程分别为， r a i n i f ( a + a a ) z 一( 6 + a b ) lj ；+ a 2 i i l x l l ； ，( 2 ，4 ) 9 第一二章离散t f i 蛐o n o v 正则化 和 ( ( a + a ) r ( a + a ) + a 2 l 丁l ) ( z a + 正) = ( a + a ) t ( 6 + 6 ) ， ( 2 5 ) 其中a a 和a b 分别是a 和b 的扰动，这里我们进一步假设这个扰动满足 叫a 列 对于t f l c h o n o v 正则化问题，m a l 3 ，s h e v 5 0 ，2 0 0 3 研究了下述相对范数条件 数【5 5 1 ： 么= 姆怕s 创u p 心( 糕锵) ，= 黜s u p 垒( 糕糌) 并且证明 屯= “刮。( a t a + a i ) - 1 卯驯 7 了r r t 母比固 。：烂坠掣；绌业， ( 2 7 ) 。2 j 司一 其中r = b a z 。但是，正如我们第一章里提及的，( 2 6 ) 和( 2 7 ) 中定义的相 对范数条件数并没有考虑a 和b 中元素的相对大小或者稀疏性结构。当a 和域 6 元素大小范围跨度很大时，或者存在很多零元素时，用范数衡量的扰动不能反 映出零元素或小元素的相对扰动大小。正是由于这个原因，人们开始考虑分量 型扰动分析，包括第一章提到的混合条件数( 1 1 1 ) 以及分量条件数( 1 1 3 ) 。具 体说来，所谓混合条件数，就是用范数来衡量输出数据的误差而用分量来衡量 输入数据的误差；而分量型条件数则是输出数据和输入数据都用分量来衡量。 据我们所知，目前为止的文献中尚未出现过t i k h o n o v 正则化问题的混合条 件和分量条件数。这一章我们将推导出t l k h o n o v 正则化问题范数型、混合型和 分量型条件数以及分量型向前误差上界。这些结果都大大改进了前人的工作。 2 2 范数型、混合型和分量型条件数 这一节我们先推导出t i k h o n o v 正则化解的范数型、混合型和分量型条件 数，然后给出残量的条件数的定义以及它们的显式表达式。 2 2 1 t i k h o n o v 正则化解的条件数 首先给出t i k h o n o v 正则解的范数型、混合型和分量型条件数的定义。 一l o 第一二章离散t 址, h o n o v 正则化 定义2 1 ：令z a 和。 + 正分别是问题( 2 1 ) 和( 2 4 ) 的唯一解。那么t i k h o n o v 正 则化解的范数型、混合型和分量型条件数定义为 c o n d f g # l i r a l i 【 ，删s 峪u p 帅! e l a x f l l 2 i m 脚一l i m 雠s u p 蝌铣，i 6 i s e 陋l 锄- 叫l i r a 粼s u p 剖孰6 l s c 一 其中i b 是按元素除法，即，：= ( 叁) ，用m a t l a b 记号为6 口，这里约定 钠= 三是。 在上面定义中，我们考虑了系数矩阵a 和右端项b 同时存在扰动的情况， 这比m a l y s h c v 的只考虑a 或者b 的扰动所定义的条件数( 2 6 ) 和( 2 7 ) 更具有一 般性。事实上，只考虑部分数据扰动定义的条件数通常被称作偏条件数。 定理2 2 ：令珑。为对角阵d 。= d i a g ( x , ) 的m o o r e - p e n r o s e 逆【4 ，6 8 ，并且定 义 r = b a x x ，m = ( a t a + a l t l ) a t ， 日= 一瑶。( ( a + a l 丁l ) 一1 a t ) + ( a + a l t l ) 一1 。r r ( i ) 假设f | 【aa b 川，e ab 圳，。如果e 足够小，那么 雠等a 6 s l f + o 洲6 】幅) ( 2 8 ) ( i i ) c o n d = 日m 】| 【a 1 = 丽- m 脚= 趔产， c 砌= i l 珑、li h i v e c ( i a i ) + i d ：。li m ii b li l 。 ( 2 1 0 ) ( 2 1 1 ) 第_ 二章离散t d h o n o v 正则化 证明：由于a 6 】i i f o ( ) ，根据法方程( 2 3 ) 和( 2 ，5 ) ，我们有 。= ( 4 丁a + a 2 l r l ) 一1a t a b + ( a a ) r ( 6 一a z ) 一a t a z 1 + o ( 2 ) ( 2 1 2 ) 我们先证明( 2 8 ) 和( 2 9 ) 成立考虑a z 的表达式( 2 1 2 ) ，去掉高阶项o ( e 2 ) 我们有 z = ( a r a + a 2 l t l ) 一1a r 6 + ( a ) t ( b - a z ) - a r a z 1 ( 2 1 3 ) 对上式两端作用v e c 算子，有 a o = 一z ；固( ( a r a + a l ? l ) 一1 a r ) + ( | 4 r a + a l ? l ) 一i r r ( a r a + a l r l ) 一1 a t 根据范数的相容性，我们有 l l x l l 2 ，h mm i i = 1 1 2 一| j z ij 2 胃m | 1 2 罂i i 【a6 】i i f 慨j 1 2 h 1 叫 所以( i ) 的结论成立。进一步，根据2 一范数的性质，这个上界是可以取得的，所 以( 2 9 ) 成立。 下面我们证明( 2 1 0 ) 成立。根据l a a l e i a i ，我们知道，如果= 0 ， 那么= 0 ，也就是a 中的零元素没有发生扰动。因此， v e c ( a a ) = d a d t a v e c ( a a ) ，( 2 1 5 ) 其中d = d i a g ( v e c ( a ) ) ，d j 是d a 的m o o r e p e n r o s e 逆。 一1 2 一 ( 2 1 4 ) 、啦舳 舢 坩 牝郜订u 似 m 篙批 v 第二章离散t 瑚h o n o v 正则化 式子( 2 1 4 ) 可以等价地写为 一旧蚴p 嚣刖 ， 亿坳 其中d o = d i a g ( b ) 。根据m 脚的定义，上式两边取o 。- 范数，我们有 ( 2 1 7 ) ( 2 1 8 ) 上面不等式中的等号是可以成立的。事实上，根据”。的定义，存在向量y o 满足1 1 9 0 l l 。= 1 ，使得 h d am d b 】l i 。= 。珊8 x ，i l h d am d b 9 1 | 。= l i h d m d 6 】蜘l i 。 l i 圳= j 令 心脚 ：c 矶小 那么，不考虑高阶项的情况下，( 2 1 7 ) 和( 2 1 8 ) 中等号成立。从而我们有 容易得到 m 脚：坐耸掣( 2 a 9 ) m 脚2 币瓜_ 叭h d am d 6 川。= = j h d a il m d b i 】e i h d aje + l m d b fe l l o o = 川h iv e c ( i a i ) + i m ii b 川。 其中e = 【1 ，1 ，1 】t 。 最后我们证明( 2 1 1 ) 。根据c r 目的定义，若( z k = 0 但是a z ，0 ，那么 有。腑= o o ；否则，把式子( 2 1 4 ) 改写为 d z t x a x = d ! 观蚴”嚣脚 z 一1 3 一 第二章离散t t l c h o n o v 正则化 那么我们有 c 脚= 叭d t 。h d ad t 。m d 。 = 珑。h d i1 m d 。t 。 = f ff 或，h d a e + f 珑。m d b le = i | 珑。f h iv e c ( a i ) + i 珑。i i 肘 口 条件数能够刻画问题在初始数据有微小扰动时解的最坏误差e 4 4 】。若e 是 初始数据误差的数量级，条件数和e 的乘积就可以作为问题的解的误差的一个 线性的局部界，这里我们把高阶项o ( e 2 ) 略去不计，因而这个线性界只对e 足够 小的时候成立 下面我们研究t d c h o n o v 正则化问题非限制的扰动界，也就是这里并没有限 制初始数据误差要足够小。结论由下述定理给出 定理2 3 ：令4 r ”“，a b r m 分别为a 和6 的扰动。令。 和弧：= z + z 分别为法方程( 2 3 ) 和( 2 5 ) 的解。如果存在某个非负矩阵e r m n 和 非负向量，p 使得i a aj e e ，i a b i e ，那么 其中 半se 世铲 q= 一互圆( ( a ? a + a 2 l r l ) 一1 a r ) + ( a r a + a 2 l t l ) 一l 固5 r s = ( a t a + a 2 l r l ) 一1 a 丁，占= b + a b 一( a + a a ) y 证明：将式子( 2 3 ) 代入( 2 5 ) ，我们有 ( a 了a + a 2 l 丁l ) ( z 一g ) = 一( a ) r ( ( b + a b ) - ( a + a a ) y a l 一a 丁( a b a a y ) = 一( a ) t s a 了a b + a t a a y a 因此 鲰一以 = ( a t a + a 2 了l ) 一1 ( - a t a a y x + ( a ) t 5 + a r a b ) 一1 4 一 第二章离散t d c h o n o v 正则化 = 一互。( ( a r a + a 2 l r l ) 一1 a t ) + ( a t a + a 2 l t l ) 一1 。s r ( a r a + a 2 l t l ) 一1 a 丁 m 棚 。 令d g = d i a g ( v e c ( 功) ，d = d j a g ( f ) 。我们有 从而 纵咄；【qs 】fd f l d 羔v e c ( a a ) 1 d ，儿d ；6j i l 纵一$ - f l * se jj cqs ， 。f 功 。= c “i q i v e c c e ，+ i s ，“。 于是，我们得到了不等式( 2 2 1 ) 。口 正如在定理2 2 的证明中看到的，误差上界( 2 2 1 ) 是可以达到的。从这种意 义上说，误差上界( 2 2 1 ) 是最优的。 2 2 2t i k h o n o v 正则化解的残量的条件数 在下面的讨论中，我们假设b 聋i n l ( a ) ，这里i n l ( a ) 指矩阵a 的值域。也 就是说，t 1 _ k h o n o v 正则化问题解的残向量满足r = b a 。 0 ，其中z 是正 则化问题( 2 1 ) 的解。下面我们对残向量r 引进混合型、分量型条件数的定义。 定义2 ，4 ：t t k h o n o v 正则化问题解的残向量的混合型、分量型条件数定义为 ：2 1 觋l 撼糕，i 州蔓e i 州 c r “：= 。l i 。r ai 篱s u 篷p ：矧；j | 竽l f 。 i 圳s e 川 一 下面的定理给出残向量r 的混合型、分量型条件数竹k 。和c r 。的显式表达 式。 定理2 5 ： 研。= 坳半，| | r l i c r 。= 0i 叫fi u l v e c ( 1 a ) + l d j v j b | | f 。 ( 2 2 3 ) ( 2 2 4 ) 笙三童曼墼! 堡! ! ! ! ! 重型些 一一 其中 r = b a z ， 【，= 一z ：。( ，一a ( a r a + a 2 l r l ) 一1 a r ) 一( a ( a t a + 2 l 丁l ) 一1 ) 。r t y = ，一a ( a 丁a + a 2 l r l ) 一1 a r ， 这里聊是d ，；d i a g ( r ) 的m o o r c - p c n r o s c 逆。 i 正日f l ：令s = b + 6 一( a + a a ) y ，其中玑是扰动后的法方程( 2 5 ) 的解略 去高阶项，残向量r 的扰动满足： r ：= s r = b + a b 一【月+ a a ) y a 一旧一a x a ) = 一( i - a ( a r a + a 2 l r l ) 一1 j 4 t 1 a z 一a ( a t a + a 2 l 丁l ) 一1 ( a ) r r + ( ，一a ( a 丁a + a 2 l t l ) 一1 a r ) 6 = z 互。( ，一a ( a t a + a 2 l r l ) 一1 a r ) 一( a ( a t a + a 2 l t l ) 一1 ) 。r r ( a t a + a 2 l v l ) _ l a t 垤掣l = 】i 怡掣l 川风，p 嚣御 从而我们得到 d t a v o c ( a a ) 川 叫6 川。 ( 2 2 5 ) f 2 2 6 ) 再回顾定理2 2 的证明，可以看出误差界( 2 2 6 ) 是可以达到的。因此，我们有 0 【u d av d b 】l i * 1 1i u l v e c ( t a f ) + i y 1 6 ij i 。7 豫”2 币面一5 丽f 一。 对于分量条件数c r 。，若r i = 0 但a r i 0 ，那么白。= 。a 否则，我们 一1 6 一 第二章离散t i l ( h o n o v 正则化 有 c 。= 小d i c ，d 一研y d a 】l l 。= i ii o , * lt u l v e c ( f a d + i d ，t li v li b l i i * 2 3 利用增广方程对t i k h o n o v 正则化进行分量扰动分析 口 这一节，我们利用增广方程对t t k h o n o v 正则化进行分量扰动分析。a r i o l i 等人【l 】以及b j 6 r c k 【5 】对于线性最4 , - 乘问题做过类似的扰动分析。回顾对于 非奇异的线性方程组a x = b ，b a u e r 【3 】和s k e e l 【5 9 曾给出如下扰动分析的 基本结论。根据等式 可以推出 所以有 a x = ( ，+ a 一1 a a ) 一1 a ( a b a a x ) 刮i ( ，+ a 一1 a a ) 一1li a 一1 l ( 1 6 i + i a a | | z i ) z is ( ，一i a - 1 a 1 ) - 1 i a - 1 1 ( 1 6 + j a a ii z l ) = ( ，+ o ( a - 1 i a a d ) i a 1 l ( 1 6 i + l a | | z i ) 其中i a 1 l 的谱半径必须满足p ( i a - 1i a a i ) 1 。下面我们把b a u e r - s k e e l 的分 析推广到t i k h o n o v 正则化。令 g ( a ) = q ，0a 0 a ， a l a ta l t0 g = 0 o ( a a ) r 0 a o0 00 其中a 0 是尺度变换参数。容易得到，g - 1 ( a ) 可以由下列块3 3 矩阵给出 g - 1 ( n ) 口一1