（计算数学专业论文）加权toeplitz最小二乘问题的预处理算法.pdf

t h e s i so f m a s t e r2 0 1 0 u n i v e r s i t yc o d e ： 10 2 6 9 r e g i s t e rn u m b e r ：5 10 7 0 6 010 35 p r e c o n d i t i o n e dm e t h o d sf o r w e i g h t e d e p l i t zl e a s ts q u a r e sp r o b l e m s d e p a t m e n t -q 曼卫坌丛坠曼匹q ! 丛丛h 曼盟丛i 曼墨 m a j o r ： q 坐卫巫丛i q 堕垒! 丛丛垒星盟丛i 鱼墨 d i r e c t i o n ： 丛坠m 曼! i 堡垒! ! g 星坠! 垒 s u p e r v i s o r ：i 堑迎里垦塾 n a m e ：x i a o l i a nr e n c o m p l e t e di nm a y ，2 0 1 0 华东师范大学学位论文原创性声明 l i i ii i iiii i ii i ii ii ii il y 17 4 2 3 6 8 郑重声明：本人呈交的学位论文畛吩l 下牛b 协昂d 、番瑚虹小参妣帮艺甲， 是在华东师范大学攻读弼生博士( 请勾选) 学位期间，在导师的指导下进行的研究- i - 作 作者签名： 醐f o 郫月彳同 华东师范大学学位论文著作权使用声明 多。夺一叩帆善心、相畦而争她柱珥缓系本人在华东师范大学攻读学 位期间在导师指导下完成的砚壬博士( 请勾选) 学位论文，本论文的研究成果归华东师 范大学所有。本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部 门和相关机构如国家图书馆、中信所和“知网 送交学位论文的印刷版和电子版；允许 学位论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入全 国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版， 采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) () 1 经华东师范大学相关部门审查核定的“内部 或“涉密”学位论文宰， 于 年月日解密，解密后适用上述授权。 ( ) 2 不保密，适用上述授权。 导师签名 本人签名 y l o 年s 月y 日 f “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位 论文( 需附获批的华东师范人学研究生申请学位论文“涉密”审批表方为有效) ，未经上述 部门审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用上 述授权) 。 焦堕莲硕士学位论文答辩委员会成员名单 姓名职称单位备注 转哥 承程 缃唧认础蝴 、主席 羔如咀 弧仡 唧懈数的1 鹰参牝 农兹 务哆钐多旋弼- 摘要 由t o e p l i t z 矩阵作为系数的线性方程组出现在许多不同的应用中f 1 前已 经有许多有效的计算方法用于求解这类含有t o e p l i t z 结构的问题巾，但这些方 法对于含有t o e p l i t z 矩阵结构的加权最小二乘问题并不适川本文丰要考虑加 权t o e p l i t z 最小二乘问题的预处理迭代算法在图像还原和非线性图像恢复- l i 都会遇到这类最小二乘i 、曰j 题在实际l 日j 题，i i ，矩阵的规模通常会很大，由于加权 t o e p l i t z 最小二乘问题本身的特点，其正规方程的系数矩阵的置换秩会很大，在求 解这类问题时，现有的预处理子的效果并不是理想，所以需要寻找新的预处理子， 改变原系数矩阵的条件数和谱分布，从而提高迭代算法的收敛速度如何构造有 效的预处理子是目前数值代数领域的热门研究课题 本文首先将加权t o e p l i t z 最小二乘问题转化成一个等价的鞍点问题，然后研 究基于对称与反对称分裂的预处理子的构造和性质通过引入不同的参数使得算 法具有更多的灵活性，并且通过选取最优参数使得算法具有更快的收敛速度同 时本文还对预处理后的矩阵进行了理论分析最后我们对新提出的预处理子进行 了数值试验数值结果表明，这类预处理子具有较好的数值效果 关键词：t o e p l i t z 矩阵，最小二乘，预处理子，对称与反对称分裂，谱性质 a b s t r a c t l n e a rs y s t e m sw i t ht o e p l i t za n dt o e p l i t z - r e l a t e dc o e f f i c i e n tm a t r i c e sa r i s ei nm a n y d i f f e r e n ta p p l i c a t i o n s w h i l em a n ye f f i c i e n ta l g o r i t h m sh a v eb e e nd e v e l o p e df o rs o l v i n g p r o b l e m sw i t ht o e p l i t zs t r u c t u r e ，af e we m e r g i n ga p p l i c a t i o n sf o rw h i c ht h ea v a i l a b l e a l g o r i t h m sa r en o td i r e c t l ya p p l i c a b l e w ec o n s i d e rt h ep r e c o n d i t i o n e r sf o rw e i g h t e d t o e p l i t zl e a s ts q u a r e sp r o b l e m s a p p l i c a t i o n sl e a d i n gt os u c hl e a s ts q u a r e sp r o b l e m s i n c l u d ei m a g er e c o n s t r u c t i o na n dn o n l i n e a ri m a g er e s t o r a t i o n i nm a n yp r o b l e m st h e s i z eo ft h em a t r i c e sc a l lb ev e r yl a r g e b e c a u s eo ft h el o c a ln a t u r ea n ds p a t i a l l yv a r i a n tp r o p e r t yo fw e i g h t e dt o e p l i t zm a t r i c e s ，t h ed i s p l a c e m e n tr a n kc a nb ev e r yl a r g e e f f i c i e n ta n de f f e c t i v ep r e c o n d i t i o n e r sn e e dt ob ei n v e s t i g a t e dt od e v e l o pf a s ti t e r a t i v e m e t h o d sf o rs o l v i n gs u c hw e i g h t e dt o e p l i t zl e a s ts q u a r e sp r o b l e m s i n t h i sp a p e r ，w ef i r s tr e w r i t et h el e a s ts q u a r ep r o b l e mt oa ne q u i v a l e n ts a d d i ep o i n tp r o b l e ma n dt h e ns t u d yt h ep r e c o n d i t i o n e r sb a s e do nt h eh e r m i t i a na n d s k e w - h e r m i t i a n ( h s ) s p l i t t i n g w ei n t r o d u c es o m ep a r a m e t e r st oc o n s t r u c tt h ep r e - c o n d i t i o n e r t h es p e c t r u mp r o p e r t i e so ft h ep r e c o n d i t i o n e ds y s t e ma r ei n v e s t i g a t e di n d e t a i l f i n a l l y , af e wn u m e r i c a le x p e r i m e n t sa r eu s e dt oi l l u s t r a t et h ee r i e c t i v e n e s so f t h en e wd r e c o n d i t i o n e r s k e y w o r d s ：t o p l i t zm a t r i x ，l e a s ts q u a r e ，p r e c o n d i t i o n e r ，h ss p l i t t i n g ，s p e c t r u m p r o p e r t y 1 1 摘要 a b s t r a c t 目录 第一章引言 1 1 1 研究背景和意义 1 1 2 本文的研究内容和论文框架 2 第二章t o e p l i t z 矩阵和循环矩阵 3 第三章基于h s 分裂的预处理子的构造和性质 5 3 1 基于h s 分裂的一般预处理子的构造 5 3 2 第一类预处理子及其性质 7 3 2 1 预处理子的构造 7 3 2 2 预处理后系数矩阵的谱性质8 3 3 第二类预处理子及其性质1 1 3 3 1 预处理子的构造1 1 3 3 2 预处理后系数矩阵的谱性质1 2 3 4 第三类预处理子及其性质1 7 3 4 1 预处理子的构造1 7 3 4 2 预处理后系数矩阵的谱性质1 8 第四章数值例子 2 0 参考文献 致谢 2 3 2 5 1 1 研究背景和意义 第一章引言 在本论文巾，我们丰要考虑对加权t o e p l i t z 矩阵最d - 乘i 、口j 题的预处理迭代 算法考虑下面的最小二乘问题 m 工i n i i a z _ 6 眩 其t l 矩阵a 和右端项b 分别为 a = 阱6 = 阱 ( 1 1 ) ( 1 2 ) 这里d 是m r n 阶对角矩阵，对角线上的元素都是正数，j 是佗礼阶单位矩阵 k 是个m 礼阶t o e p l i t z 矩阵且是列满秩的，是。个给定的右端项，p 0 是 一个正则化参数【25 】这类问题通常出现在图像还原【1 5 】和j e 线性图像恢复 2 】i i 在这些应川中，问题的规模会很大，很容易上百万但很多时候我们必须在有限 的时问里解决这些问题，冈此必须寻求有效的快速算法米求解这类i 口j 题 对于一般的t o e p l i t z 线性方程组 k x = b ( 1 3 ) 其中k 舭加是对称正定的t o e p l i t z 矩阵l e v i n s o n 1 9 在1 9 7 4 年研究w i e n e r 滤波时，提出了求解方程组( 1 3 ) 的快速直接算法随后，k a i l a t h ，k u n g 和m o r f 【1 6 】利用t o e p l i t z 矩阵的置换结构和它的s c h u r 补，于1 9 7 9 年提出了求解方程组 ( 1 3 ) 的快速c h o l e s k y 分解法，也称s c h u r 方法以上两种直接算法的时问复杂 度都是o ( n 2 ) 1 9 8 0 年，a m m a r 和g r a g g 【1 】提出了超快速直接，其时问复杂度是 o ( n l 0 9 2 几) 这些算法都利用了t o e p l i t z 矩阵的特殊结构( 较小的置换秩) 和特殊 性质( 对称正定) 【1 8 1 1 2 1 ，但对于置换秩较大的t o e p l i t z 方程，或不定的t o e p l i t z 矩阵，这些算法均不适用因为加权t o e p l i t z 矩阵本身的性质和空间的特性，使得 a 的置换秩会很大f l7 1 所以在求解这类加权t o e p l i t z 最小二乘问题时，无法使 用快速直接算法，这时我们可以使用迭代算法，如k r y l o v 子空间迭代算法 我们知道，线性最d 、- - - 乘问题可以化为等价的正规方程，然后用共轭梯度法 来求解5 1 共轭梯度法在理论上是直接法若方程阶数是n ，则共轭梯度法的第 n 步迭代解z 。必定是精确解但实际上，由于舍入误差的影响，z n 往往不能满足 原方程另外，对于一般的迭代法( 包括共轭梯度法) ，当方程组的系数矩阵的条件 2 数较大或者谱分布较差时迭代算法的收敛速度通常很慢为了改进这一个问题， 人们提出了预处理技术，即在方程两边同时乘以一个非奇异矩阵的逆，然后再用 迭代法米求解近年来，人们不断提出各利，新的预处理技术预处理技术已经成 为解大型系数方程组的一个重要手段但是由于预处理子与问题本身密切相关， 针对不同的l 日j 题，预处理子也各不相同冈此如何构造有效的预处理子是f 1 前数 值计算领域- i 的热门研究课题之一 由于t o e p l i t z 矩阵与向量的乘秋可以通过快速f o u r i e r 变换( f f t s ) 实现，其 运算量为o ( n l o g n ) 冈此在对t o e p l i t z 线性方程组( 1 3 ) 做预处理时，对预处理 子有着特殊的要求，即求解预处理系统时的运算量不能超过o ( n l o g n ) f 1 前常川 的一类预处理子为循环矩阵因为循环矩阵可以通过f o u r i e r 矩阵对角化【1 4 】，所 以求解一个以循环矩阵为系数矩阵的线性方程组时，运算量为0 ( 几l o g 礼) 对于 t o e p l i t z 线性方程组( 1 3 ) ，f 1 前已有一些较好预处理子，如s t r a n g 循环预处理子 和t c h a n 循环预处理子等有学者将这监预处理子推广到了求解t o e p l i t z 矩阵 最小二乘| 、日j 题，对于置换秩较小的情形，取得了较好的效果f 8 ，9 ，x 0 1 但对于置换 秩较大的加权t o e p l i t z 矩阵最t b - - 乘问题，几前研究结果并不多【7 】 1 2 本文的研究内容和论文框架 本论文首先将加权t o e p l i t z 最小_ 乘f 日j 题( 1 1 ) 转化为等价的鞍点问题然 后研究基于对称与反对称分裂( h s ) 的预处理子的构造及其性质，并通过数值算 例来说明这些预处理子的有效性 本论文主要做了以下工作： ( 1 ) 通过引入三个参数矩阵，构造出了基于h s 分裂的预处理子的一般形式 ( 2 ) 通过对这三个参数矩阵的不同选取，构造出了三类有效的预处理子，并对这 些预处理子的性质进行了理论分析，给出了预处理后的系数矩阵的特征值分 布情况 ( 3 ) 对提出的预处理子进行了数值算例，验证了新的预处理子的有效性 本文主要结构如下：在第二章，我们对t o e p l i t z 矩阵和循环矩阵作了介绍在 第三章，我们给出了基于h s 分裂的预处理子，并进行了理论分析最后，在第四 章，我们给出了数值试验的结果 第二章t o e p l i t z 矩阵和循环矩阵 设a n r n 肌，如果a n 可写成下面的形式 则称其为t o e p l i t z 矩阵 设g r n 煳，如果c k 可写成下面的形式 ( 2 1 ) ( 2 2 ) 其中 c 一膏= c n 一， 1sksn 一1 ， 则我们称矩阵g 为循环矩阵【1 1 】循环矩阵可以被傅坐叶矩阵晶对角化即 g = e a n r ， ( 2 3 ) 其中k 是由g 的特征值组成的对角矩阵【1 4 】，r 为傅里叶矩阵，即 【f n 】j ，七= e 2 丌玎七n ，0 歹，k n 一1 v 。 我们知道矩阵k 可通过快速傅里叶变化( f f t s ) 得到，即用r 乘以g 的第一 n a p k i n 的所有特征值对于f f t s 我们可以参看c o o l e y 和t u k e y 1 3 j 。事 实上，k 的对角元k 可由： k = c j e 2 丌i f l 。加，k = 0 棚一1 j = 0 给出当我们得到了之后，对于任意的向量y r n ，乘积c y 和簖1 剪都可由 f f t s 得到，时间复杂度是o ( n l o g n ) 3 n n 一 一 一 吣 呲 0 。 ，吼 1 i 知 q 知 吼 知虮； 肛 卜 一一一 = k 哪 哪 o 砸 q 印 呻 d 1 ，q 1 q 印 q 印 q 轴 印q ； 卜 p ， 一 忡 = 4 对于t o e p l i t z 矩阵与任意向量的乘积，我们可以通过将其嵌入到循环矩阵 q - ，然后利j t jf f t s 来计算所以n 维t o e p l i t z 矩阵与向量的乘积的运算量为 o ( n l o g n l 在对t o e p l i t z 线性方程组作预处理时，循环矩阵是目前最成功的一类预处理 子我们这坐列出其l i l 的两利t 构造方法【1 1 j ： s t r a n g s 循环预处卿子这是最早的循环矩阵预处理子，由s t r a n g 【2 a 在1 9 8 6 年提出来的对给定的t o e p l i t z 矩阵a n ( 2 1 ) ，该预处理子矩阵是选取了如 。i l 的。部分元素，冉按照循环矩阵的要求填满矩阵的其余位置预处理子& 的每一条对角线上的元素s j = 【s 七一_ f 0 5 k ，l n ，由下列式子确定： f 叼， j 勺2 i a j n i ls n ， 0 j is 【n 2 j ， i n 2 j j n ， ( 2 4 ) 0 - j 0 ，我们有 p ( t 、 1 由上面的引理，我们立即可以得出如f 定理 定理3 2 设a 是矩阵p f l a 的特征值，则 i 入一1 i 1 ， 即p f l 4 的特征值在以( 1 ，o ) 为圆心，1 为半径的圆盘内 3 2 2 预处理后系数矩阵的谱性质 下面我们讨论磊的特征值分布令= p ，+ 三k t k ，可得 c 跗旷1 = h 嚣一嚣。1 又 ( d 1 + h ，- l ( o l - h ) = 瞄瑚， 其中 e = ( o c i - - ) ( q w ) ，u = 而f l - - z 2 互 所以 叫子瑚a i ，- 珊kj 1 - 1 一警。1 在实际应用中，我们选取p = 矿此时可得u = 0 于是有 矗= r 巾p t 蝴一全瞄。2 e ， 其中 f ：i 一三k 一1 k t ，、 通过上面的分析，我们可以得到下面的结论 定理3 3 设p = p 2 ，则只- 1 4 的特征值为入= 1 代数重数为n ) 或九= 1 一， i = 1 ，2 ，m ，其中魄为矩阵e f r m 仇的特征值 h 1 一! 下面我们对耳1 4 的特征值进行更深入的讨论 定理3 4 设= p 2 ，关于矩阵耳1 4 的特征值分布，我4 f 3 有如下的结论 当0 o t i n 时 “ 如果o q 瓦r m r i n ，则p f l 4 的特征值在区间( o ，1 ) 中 俐如果警锄 争删只- 1 4 的特征值在区间( i 乏，2 ) 中 俐当w m i 竹o t t ，懈时 n ，) 如果0 a 鲁刚耳1 4 的特征值在区间( 最，2 ) 中 俐如果雩笋 q w m 们时 f ，砂如果o q i o m r i n ，则p f l 4 的特征值在区间( 1 ，2 ) 中 例如果警 n - 唬- 7 衄，则p f l 4 的特征值在区间( i 鼍= ，2 ) 中 证明( a ) 当0 o t ，m 钿时，因为 e = ( o e i 一妙) ( o j + 形) ， 所以e 是负定的因为有 凡( j 一吾k 一l k 丁) = ，一2 ) q ( k e - 1 k t ) = 五c 。蕊# 2 - o 2 ， 所以 2 = m a x j 期f 1 当o a 笋时，f 是半负定矩阵，则e f 是半正定矩阵( 不一定对 称) 一由于e 是负定的，f 是对称的，所以e f 的特征值都为实数又 i i e f i l 2 i i e i l 2 i i f i j 2 1 ， 1 0 因为在一些实际问题中，有f f m a z 1 ，i n 0 ，不能满足0 l 刈圳22 急， 所以p f l 4 的特征值的范围在f ? 竺一，2 、之问 a + 叫m + ( b ) 当w m i n q 伽一时，e 是不定的 如果0 q 笠磐，即f 是负定时，e f 的特征值都是实数，且在区问 “ ( - 1 ，1 ) 内同样的，我们可以估计耳1 么的特征值的下界我们有 入( 只- 1 4 ) 1 一| j f j j 2 = 1 一骊0 2 z _ q p 2 = 戒2 0 q z 2 ， 则可1 4 的特征值的范围在区问( 瓦万2 瓦o e # 2，2 ) 之间 如果有笪字 a t t 钿n 时，即e 是正定矩阵 如果0 q a m 矿i n ，有f 是负定的，则e f 是负定矩阵，它的特征值在 ( 一1 ，0 ) 之间，所以斤1 4 的特征值在( 1 ，2 ) 之间 当f 不定时，e f 的特征值是实数，且在( - 1 ，1 ) 之问，估计耳1 4 的特 征值的下界有 a ( 耳1 4 ) 1 一i i e i l 2 = 瓦2 0 ， 则p f l 4 的特征值的范围在r 当，2 、) 之问 q + “) m a x 口 3 3 第二类预处理子及其性质 3 3 1 预处理子的构造 令 d 0 = 而1 j ，d 1 = q j ，d 2 = p j ， 则可得基于h s 分裂的第二类预处理子 恳= 南r 。帅2 ，从量玢 慨8 ， i 卜第一类预处理子的分析类似，我们有 巧1 4 = ，一噩， 其中 乃= 巧1 ( 岛一4 ) = ( 卢，+ s ) 一1 ( q ，+ 日) 一1 ( q ，一s ) ( 卢，一日) 因此，我们要得到巧1 4 的特征值分布，只需讨论死的特征值分布即可易知冠 与矩阵 磊= ( 卢，一日) ( q ，+ i - o 一1 ( q ，一s ) ( 卢，+ s ) 一1 相似，所以它们具有相同的特征值我们首先讨论磊的谱半径的范围 p ( 磊) = l l ( p ，一日) ( q j + 日) 一1 ( a ，一s ) ( 卢，一s ) 1 1 2 1 1 ( 3 z h ) ( c d + 日) 一1 1 1 2 1 1 ( , 1 x s ) ( p j s ) 1 1 2 = 。辫lq 了+ - 妣w , m a x n a f t 。- + + o 2 v ， 1 i mq + 伽i1 n 。+ 1 2 因为 对于 增m a 圳xa p + - 毗w i f = m a x 薏篇，万- w 磊m i n ，1 ， 我们分情况讨论 ( 1 ) 当q p 时，最大值为 器藤 ( 2 ) 当q p 时，最大值为i o l 2 - - 盯2 m a x 所以 ( 1 ) 当q p 躯札划= m a x 筹，塑 _ w 删m i n n ) 压- 萨2 扣蠹2 c 2 ，当a 卢时p c 磊，倪，其中倪= m a x 薏差宅，鲁 篆) 蔷 老 3 3 2 预处理后系数矩阵的谱性质 下面我们讨论磊的特征值分布令= f l i + 吉k t k ，可得 悯- t 一 吉i 1 - - 1 一嚣- 1 磊= 瞄爿瞄一a 胛ij 嚣1 驴中e - - i1 其中 e = ( f l i - 刚“盯1 ，u = 群 在实际使用中，我们选取p = 1 ；2 ，此时可得u = 0 于是有 雹2号e一参+刍ek一1舻一号一1)eke-1全ef(一茜一1)ekeh0 000 ， lii 其中 f = 虽，一( 景+ k z m k 1 3 定理3 5 设卢= 肛2 关于矩阵巧1 a 的特征值分布，我们有如下的结论 砂当n p 2 时 以，如果。 p 2 伽，则当。 口罨笋时，巧1 4 的特征值在 ( - 一甍等，) 之间，当鲁 q 笋时巧1 4 的特征值在 ( - 一m a x 瓮等，鲁老) 1 + 饥) 之间 例如果加m 饥p 2 伽m 则当。 q 罨笋时，巧1 4 的特征值在 ( ，一m a x 等等，1 。t 2 + - - 叫t o m r a 饥i n ，1 + 7 - )l 叫m + q 。o + 叫m 饥j 。一 之间，当警 q 加一，则当。 及s 笋时，巧1 4 的特征值在( 1 ，2 ) 之间，当 芬2 堡 q 笋时，巧1 4 的特征值在 之间 ( 一m a x 甍等，鲁老) ，1 + 7 - ) ( b ) - 3d p 时 俐如果0 i t 2 w r n i n , 则当。 q 罨笋时，巧1 4 的特征值在 (，一器22 ，) 1 4 之间，当鲁 q 笋时巧1 4 的特征值在“p 。 ( - 一m a x 琵希，鲁老) 1 + 1 。) 之间 ( 2 j 如果”m i n p 2 ，则当。 a 笋时，巧1 4 的特征值在 1 5 当o q 笋时，f 是半负定矩阵，e f 是半正定矩阵，并且e f 的特 征值都为实数因为 i i f i l 2 = m a xf 筹f _ 鱼0 2 m a x 型+ 2 4 ， 所以 一一 i i e f i l 2 剑e i l 2 i i f i l 2 嚣2 n u 2 则矩阵磊的特征值在( o ，错) 之问，所以预处理后的矩阵巧z 4 的特征值在( 1 _ - 盯盯2 象a n z 霉- - + o p l 2 4 卢，1 ) 之间 当譬笋 o l - m a x 毫等一22 因此，巧1 4 的特征值在区间 ( 1 一m 觚 瓮希，鲁老) ，1 + 饥) 之间 ( 2 ) 如果有 t tm 讯卢2 叫，则e 是不定的所以我们有 2 = m a x l 鲁f = m a x _ 薏岳，等等) 当o q 譬学时，f 是负定矩阵，且有 “ i i f i l 22 并 l - m a x 薏岳，等羔) 冈此，巧1 a 的特征值在区问 ( 一m a x 些w m a x 岳，等等) 1 + 7 )l+ o 。q + 饥j 一 之汛 。 当l r z f i n 口 l + qq 十 jl 盯嘉m z + 旷p 4盯二抽j 所以巧1 4 的特征值在以( 1 ，0 ) 为圆心， m a x 髻w m a x ，案) 一 l 十qq + 伽m t nj l 仃彘+ 肛4p + 仃二i nj 为半径的圆盘内 ( 3 ) 如果有p 2 t l m 则e 是正定矩阵，且有 2 = m a x l 篇i = 百肛2 _ 五w m a x 1 当0 q s 譬笋时，f 是负定的，并且有i l f 0 2 1 ，又因为e f 是负定矩 “ 阵，它的特征值都为是实数，所以杰的特征值在( 一1 ，0 ) 之间，则豸1 4 的特征值在( 1 ，2 ) 之间当口r a 矿i n a o m 下a x 时，f 是不定的，我们有 2 = m a x 甍等，鲁老) 1 7 i 列样的n j 以徒4 ：t - u 岍1 州= i - a c 靴l 堋1 2 = l - m a x 笔等，鲁老) 所以巧1 a 的特征值在 ( ，一m a x 瓮等，鲁老) 1 + ，) 之问 ( b 1 在这利- 情况下的证明可类似的由上面的情况推出 3 4 第三类预处理子及其性质 口 3 4 1 预处理子的构造 令 。= ( 2 q ，。q + 卢，j ) 一1 ，。t = ( q ja j ) ，。z = ( q ，p j ) ， 则可得基于h s 分裂的第三类预处理子 岛= r 。q 一- 1rw 。帅2 ，从二纱 q 9 ， 与前面的分析类似，我们有 p 3 - 1 4 = j 一死，一f 其中 乃= 巧1 ( 恳一4 ) = ( d 2 + s ) 一1 ( q ，+ 日) 一1 ( a j s ) ( d 2 一日) 因此，我们要得到p 3 - 1 a 的特征值分布，只需讨论t 3 的特征值分布即可易知t 3 与矩阵 磊= ( 卢j h ) ( o d + 日) 一1 ( d 2 一s ) ( d 2 + s ) 一1 相似，所以它们具有相同的特征值 1 8 3 4 2 预处理后系数矩阵的诸性质 下面我们讨论磊的特征值分布令e = p ，+ 丢k t k ，, - - 1 得 ( d 1 + s ) - l = h 蓦1 - 1 丢e 砸- i 。1 所以 磊= 言! ! l k a i t - q k j 丢jl 手1 ：二- t 1 k ? 一丢z k - i 一1 ， 其i - e 却卜酬q 盯1 ，u = 群 在实际使用巾，我们选取卢= 肛2 此时可得u = 0 ，所以有 磊= r 毛e _ 2 e 一全瞄e 一， 其，l ， f ：j 一呈k 一1 k t 定理3 6 设p = p 2 时，关于矩阵巧1 a 的特征值分布，我们有如下的结论 俐当。 n t 讥时，如果有。 t l h d z 时，如果有0 q 卢0 - 2 n ( k ) ，则百1 a 的特征值在( 1 ，2 ) 之间 证明( a ) 当0 o t 讥时，即e 是负定的并且有 i i e i i 。一a xi 麓i - 赢w m a x 币- - o 。 1 鼬( j 一兰k e - t k t ) k e - k t 一( k - i k r ) ：籁，( j 一三一) = 糍， 当0 q p 磅伽( k ) 时，f 是半负定矩阵，所以 o f i l 2 = m a x l 三盖 i 蔷l = 孑a 夏2 m , 丽“- a # 2 由于e f 是半正定矩阵，且 l i e f i l 2 0 e f i l 2 t t 7 m 即e 是正定矩阵，并且有 i i e i i z = m a x i 蒿i - 万o t - - 磊w r n i n 1 如果0 q 卢靠 n ( k ) 则f 是半负定的，故e f 是半负定矩阵同样地，有 i i e f i l 2 i i e i l 2 i i f i l 2 1 0 0 0 h s s ( a = p 2 ) 1 1 50 1 0 92 0 1 0 2 8 1 3 5 4 1 0 3 14 4 02 2 1 96 6 87 2 6 6 h s s ( a + ) 9 50 0 9 41 4 90 2 0 32 0 50 6 1 82 2 60 9 1 22 4 41 5 3 1 p 1 ( q + ) 6 00 0 7 87 60 0 9 48 50 1 8 89 90 3 1 21 1 6 0 6 2 5 p 2 ( a 4 ) 7 70 0 8 3 1 2 00 1 8 7 1 7 5 0 3 7 51 8 30 6 0 31 9 21 1 2 1 恳( a 4 ) 6 10 0 7 87 60 1 0 98 80 1 8 91 0 20 3 2 8 1 1 90 6 7 2 由农l - 的结果可以看出，当k 是病态的，我们提出的预处理子仍具有很好的 加速效果 参考文献 【1 】g a m m a ra n dw b g r a g g ? s u p e r f a s ts o l u t i o no fr e a lp o s i t i v ed e f i n i t et o e p l i t zs y s t e m s ， s i a mj m a t r i xa n a l a p p l 9 ( 1 9 8 8 ) 6 1 6 7 【2 】h a n d r e w sa n db h u n t “d i g i t a li m a g er e s t o r a t i o n ，”p r e n t i c e - h a l l ，e n m g l e w o o dc l i f f s n j ，1 9 7 7 【3 】z zb a i ，g h g o l u ba n dc kl i ，c o n v e r g e n c ep r o p e r t i e so fp r e c o n d i t i o n e dh e r m i t i a n a n ds k e w - h e r m i t i a ns p l i t t i n gm e t h o d sy o rn o n 1 l e r m i t i a np o s i t i v es e m i t i c f i n i t em a t r i c e s ， m a t h e m a t i c so fc o m p u t a t i o n7 6 ( 2 0 0 7 ) ，2 8 7 - 2 9 8 【4 】z - zb a i ，g h g o l u ba n dm k n g ，h e r r n i t i a na n ds k e w - h e r m i t i a ns p l i c i n gm e t h o d s ，d rn o n l l e r m i t i a np o s i t i v ed e f i n i t el i n e a rs y s t e m s ，s i a mm a t r i xa n a l a p p l ，2 4 ( 2 0 0 3 ) ， 6 0 3 _ _ 6 2 6 【5 】a b j o r c k ，“n u m e r c i a lm e t h o d sf o rl e a s ts q u a r e sp r o b l e m s ，”s i a b l ，p h i l a d e l p h i a ，1 9 9 6 【6 】6m b e n z i ，g h g o l u ba n dj l i e s e n ，n u m e r i c a ls o l u t i o no fs a d d l ep o i n tp r o b l e m s ，a c t a n u m e r i c a ，( 2 0 0 5 ) ，1 - 1 3 7 【7 】m b e r m ia n dm k n g ，p r e c o n d i t i o n e di t e r a t i v em e t h o d sf o rw e i g h t e dt o e p l i t zl e a s t s q u a r e sp r o b l e m s ，s i m aj m a t r i xa p p l ，2 7 ( 2 0 0 6 ) ，1 1 0 6 - 1 1 2 4 【8 】r h c h a n ，j g n a g ya n dr jp l e m m o n s ，f f t - b a s e dp r e c o n d i t i o n e r sf o t t o e p l i t z - b l o c k l e a s ts q u a r e sp r o b l e m s ，s i a mj n u m e r a n a l ，3 0 ( 1 9 9 3 ) 1 7 4 0 - 1 7 6 8 【9 】9r h c h a n ，j g n a g ya n dr jp l e m m o n s ，c i r c u l a n tp r e c o n d i t i o n e dt o e p l i t zl e a s t s q u a r e si t e r a t i o n s ，s i a mj m a t r i xa n a l a p p l ，1 5 ( 1 9 9 4 ) ，8 0 - 9 7 【1 0 1r h c h a n ，j g n a g ya n dr jp l e m m o n s ，d i s p l a c e m e n tp r e c o n d i t i o n e rf o rt o e p l i t z l e a s ts q u a r e si t e r a t i o n s ，e l e c t r o n t r a n s n u m e r a n a l ，2 ( 1 9 9 4 ) ，鲥广5 6 【1 1 】r h c h a na n dm k n g ，c o n j u g a t eg r a d i e n tm e t h o d sy o rt o e p l i t zs y s t e m s ，s i a m r e v i e w ，3 8 ( 1 9 9 6 ) ，4 2 7 - 4 8 2 【1 2 】r c h a na n dg s t r a n g ，t o e p l i t ze q u a t i o n sb yc o n j u g a t eg r a d i e n t sw i t hc i r c u l a n tp r e c o n - d i t i o n e r , s i a mj s c i s t a t c o m p u t ，1 0 ( 1 9 8 9 ) ，1 0 4 - 1 1 9 【