（计算数学专业论文）toeplitz系统的最优求解算法与实现.pdf

罔防“学披术火学4 i j l 巍q i 皖学位论义摘要t o e p 】t z 系统在数值计算和工程计算中应用非常广泛。信号处理中反馈数字滤波器的滤波系数、时间序列分析中固定自返模式未知参数的求解都涉及到t o e p l i t z 系统求解；在整个域内，若采用离散时间、空间抽样，并用诸如正弦函数s i n ( nx ) ( nx ) 及其它核函数作基函数逼近初始数据，则逆热问题的数值解可通过解一t o e p lit z 系统获得。r 另外，t o e p l i t z 系统还应用于偏微分方程组求解，卷积型积分方程组的p a d e逼近求解以及控制论中的最小实现问题等。对t o e p | i t z 系统的求解，最广泛应用的是预条件共轭梯度法，而预条件共轭梯度法的关键是选择适当的预条件子。) 本文将在对已有预条件子小结的基础上，提出了预条件子的统一构造及性能分析，进而又给出了在离散w 变换情况下，最优预条件子的构造。另外，本文又提出了一种新思想，即基于证弦变换类交叉对角化t o e p l i t z 预条件子的构造，这工作具有很大的研究潜力。最后，文章还将小波变换与多重网格算法相结合，提出了解决病态t o e p l i t z系统的一种有效方法，这在信号处理中有十分重要的价值。关键词：t o e p l i t z 系统、预条件共轭梯度法、预条件子篇i 页l ! 坠塑兰丝查叁兰业蔓：! ：堕：! 丝堡竺一a b s t r a c tt o e p l i t zs y s t e m sa r i s ei nav a r i e t yo fa p p l i c a t i o n si nm a t h e m a t i c sa n de n g i n e e r i n g i ns i g n a lp r o c e s s i n g s o l u t i o n so ft h et o 印l i t zs y s t e m sa r er e q u i r e ds oa st oo b t a i nt h ef i l t e rc o e f f i c i e n t si nt h ed e s i g no fr e c u r s i v ed i g i t a lf i l t e r s t i m es e r i e sa n a l y s i si n v o l v e ss o l u t i o n so ft h et o e p l i t zs y s t e m sf o rt h eu n k n o w np a r a m e t e r so fs t a t i o n a r ya u t o r e g r e s s i v e sm o d e l s b yu s i n gd i s c r e t et i m ea n ds p a t i a ls a m p l i n go ft h ed o m a i na n dt h es i n ef u n c t i o ns i n ( 丌x ) ( 7 x ) a sab a s ef u n c t i o nf o ra p p r o x i m a t i n gt h ei n i t i a ld a t a t h en u m e r i c a ls o l u t i o n so fi n v e r s eh e a tp r o b l e m sc a r lb eo b t a i n e db ，s o l v i n gat o e p l i t zs y s t e m s o t h e ra p p l i c a t i o n si n v o l v es o l u t i o n so fp a r t i a ld i f f e r e n t i a le q u a t i o n ss o l u t i o n so fc o n v o l u t i o n ，t y p ei n t e g r a le q u a t i o n s p a d ea p p r o x i m a t i o n s a n dm i n i m u mr e a l i z a t i o np r o b l e m si nc o n t r o lt h e o r y r e c e n tr e s e a r c ho nu s i n gt h ep r e c o n d i t i o n e dc o n j u g m eg r a d i e n ta l g o r i t h ma sa l li t e r a t i v em e t h o df o rs o l v i n gt h et o e p l i t zs y s t e m sh a sg a i n e dm u c ha t t e n t i o nt h es u c c e s s f u la p p l i c a t i o no ft h ep c g ar e l i e so nt h ee x i s t e n c eo fag o o dp r e c o n d i t i o n e rl nt h i sp a p e r w e 1 1f i r s tg i v eau n i f i e da p p r o a c ht oc o n s t r u c tt h et o e p l i t zd r e c o n d i t i o n e r sm a di t sp r o p e r t i e sa n a l y s i st h e nn e wp r e c o n d i t i o n e r st h a tc a nb ed i a g o n a l i z e db yt h ed i s c r e t ewt r a n s f o r r nm a t r i xa r et h e np u tf o r w a r d a n o t h e ri m p o r t a n tc o n t e n to ft l l ep a d e ri san e wt h o u g h ta n di t se x p e r i m e n t t h et h o u g h ti st oc o n s t r u c tp r e c o n d i t i o n e r sb a s e do na c r o s s d i a g o n a l i z i n gt h et o e p l i t zs y s t e m sb yu s i n gs i n et r a n s f o r ma l s oi tw i l lb eo u re m p h a s e si nf u t u r es t u d y a tl a s t t h i sp a p e rc o n n e c tm u l t i g r i d d i n ga l g o r i t h mw i t hw a v e l e ta n a l y s i s a d v a n c i n ga no p t i m a lm e t h o dt os o l v i n gb a d - c o n d i t i o n e dt h et o e p l i t zs y s t e m s w h i c hi sv e r yv a l u a b l ei ns i g n a lp r o c e s s i n gk e yw o r d ：t h et o e p l i t zs y s t e m 、p r e c o n d i t i o n e dc o n j u g a t eg r a d i e n ta l g o r i t h m( p c g a ) 、p r e c o n d i t i o n e r 第l i 页! ! 型兰坐叁型! 型堕型丝生一第一章预备知识1 1t o e p l i t z 系统概述一个n 阶方阵r ，被称为t o e p li t z 矩阵，如果它满足r ，=- 2，n _ i1 1 i - 2，2 f ，2 一n即沿每条对角线的取值均为常数。t o e p i t z 矩阵的集合称为本文中，我们考虑以t o e p l i t z 矩阵为系数矩阵的线性方程组f ，x = b的求解。t o e p l i t z 系统。( 112 )1 2 求解线性方程组的预条件共轭梯度法描述求解线性方程组( 1 1 2 ) 的预条件共轭梯度法可描述如下：设x 。= o ，= 6 ，= 1 ，重复做下列运算直到满足精度要求，1 如果一，= 0 ，则z = x n ，结束；否则2 ( 1 ) 求解预条件系统p z 。= r k 一( 尸为预条件矩阵)( 2 ) 设卤：o ，计算瓯：挚：气2 0 2( 3 ) 设pj = z o ，计算p = 毛一】+ 以p ；( 4 ) 博嘶2 瓣，第l 贰型堕型主! ! 查叁兰型生：i ! ! ；| ；： = 垃堕! 一工 = 一i + 口， t h = 一1 一a r ，p tk ：2k + 1 转】。用预条件共轭梯度法求解t o e p l i t z 系统已广泛被采用，因为这种算法有两个优点：一是如果选择合适的预条件子，则求解n 阶t o e p i l z 系统算法的复杂性可由通常的0 ( n 2 ) 级降为0 ( n l o g n ) 。二是该算法可用来求解许多病态问题。嗣预条件共轭梯度法( p c g a ) 求解方程组，最关键的任务是构造出高效的预条件子。好的预条件子p 满足如下条件：( 1 ) 卢7 1 的特征值以1 为聚点。( 2 ) p 。x 的计算比t “x 的计算要简单。( 3 ) a 的计算比t x 的计算要简单。1 3 几种常见信号我们知道，在实际问题中，通过计算，可将具体信号转化为t o e p l i t z 系统求解。为数值实验的方便，下面介绍三种常见信号：方波，单边指数衰减波及双边指数衰减波。、( 1 ) 方波( 又称占波) ，函数形式为：r 】l f f 0 )( 口 0 )鼽科学技术人学圳究牛院学位论文第二章已有t o e piit z 预条件子及其性质综述8 0 年代中期，一些关于t o e p l i t z 系统的快速直接求解法的提出，如l e v i n s o n算法( 参见 6 ) ，使算法的运算量由o ( n2 ) 级降为o ( n l o g2n ) ，但由于这些算法的不稳定性，此处不再提及。在8 0 年代末至9 0 年代初中、期，基于快速变换与快速算法的思想，已出现了许多种有效的预条件子。如s t r a n g ( 参见 7 ) 和t c h a n ( 参见 8 ) 的循环预条件子、h u c k e ( 参见 9 ) 的循环和斜循环预条件子、以及基于实变换的正弦变换基预条件子、h a r t l e y 变换基预条件子( b i n ia n df a v a t ( 参见 1 0 ) ) 等。下面就对这些预条件子及其性质、收敛性做简单总结。2 1s t r a n g 的循环预条件子第一个循环预条件子由s t r a n g 于1 9 8 6 年提出。定义如下：对给定的n n对称正定( s p d ) t o e p l i t z 矩阵t = t ( “，r l ，。) ，表示如下则s t r a n g 的循环预条件子c ，的元素定义为c 。= c 。 。m 。? 一it i0 | j 1 ，q ，的谱满足 2 c o s ( 等半脱；。玎十l羹5 页h钆z，弘心。产盯巨b 。u a n 和k o h l ，a c h ( 参见 】1 ) 提出的n i 弦变换基预条件丁二为：s = ，。q ；( 2 18 )而在f 最优范数逼近意义下，r c h a r t 和m k n g ( 参见 1 2 ) 提出另一类f 弦变换基预条件子s 。，s 。的构造如下：设”= 2 n d t = 乏的奇数，= ，= 。一+ 二n + l 口一，! ，对于k 0 的偶数，吼= l + i ) ，2 川，对于足13i = 1 , 2 一m 然后取乩= z ，q( 如果 = 2 m + 1 ，则s 。的构造是一样的)2 5h a r t l e y 变换基预条件予设( 月) 是n 阶离散h a r t l e y 变换矩阵，第( j ，k ) 元素为( 2 1 ，9 )7 1c o s ( 型) + c o s ( 型) 0s ，ksn 一1n胛任意n 维向量的离散h a r t e y 变换可通过0 ( n l o g n ) 次实数运算计算。b i n ja n df a v a t i 首次提出了可被离散h a r t l e y 变换对角化的矩阵集合，并指出这些矩阵可表为循环阵和一个h a n k e l 阵的特殊和。见下定理，定理1 ( 参见c i 0 ) 任一可被h ( n ) 对角化的矩阵q 可分解为q ：+ x y ，其中，彤为一循环阵，y 为第一列元素为0 的斜循环阵，z 为x =l00001oo1o由上述定理，b i n ia n df a v a t j 构造出矩阵h ( r ) 。满足在可被h ( n ) 离散对角化的矩阵集合中， ( r ) 使得怆一r 1 1 最小。且构造矩阵 ( r ) 需o ( n ) 阶运算量利用快速h a r t l e y 变换，_ i l ( 丁) 的特征值可通过o ( n l o g n ) 阶运算量获得。下面繁页周酗科学投术人学州究生院学位论史给出构造定理。定理2 ( 参见 1 0 ) 设r 为n 阶对称正定t o e p l i t z 矩阵，令w 和y 分别为h ( t ) 的分解和y 的第一列，则有w 。：堕塑盥女：o ，1 ，n 一1门胪 华置一。第颂闽防科学投术人学研究生脘学位论史第三章t o e pl it z 预条件子的统一构造及性能分析本章我们将首先研究己知预条件子的特征值与生成函数f ( x ) 的f o u r i e r 级数部分和或c e s a r o 和之间的关系，证明上章提到的预条件子均为或近似为f ( x ) 的f o u r ie r 级数部分和或c e s a r o 和在某一致网格点上的值。第二节中，我们提出了四种新的循环，斜循环以及正弦变换基预条件子。通过引入校正矩阵，我佰得到，新的预条件子构成在某种范数意义下对原矩阵更好的逼近。第三节中，我们讨论了新的预条件子的谱性质。而新的正弦变换基预条件予对非负生成函数( 不恒为零) 总保持正定。第四节中的数值实验说明了校正预条件子方法的高效性( 本章的矩阵汜号同于上章) 。3 1各类预条件子的特征值对于给定的实值函数厂( x ) ，( x ) 的f o u r i e r 系数为f 。，即厂( x ) = y t 。e x p i 口 ，x 【0 ，2 石f o u r i e r 级数部分和与c e s a r o 和分别定义为 ( x 卜。t te x p 触 ，( 工) 5 高萎厶( 地工 o , 2 x 】定理3c ，和c ，的特征值可表为c 扣州争w ，) - 州净删= 0 , 1 2 胛一1证明略( 见参考文献 1 3 ) 。定理4 ( 1 ) 预条件予s 。的特征值可表为五，( s 。) ：仃。，( 羔型业)，：0 ，l ，2 ，”一1门出特征值集e 页，= 0 1 2 ，一7 1 1耻即。，等，警，逊p+l，。，：垃型p + l 逝，i - p q + ，t 三，g 叫等，如喾逝，。，。，池等进，可p t l + t p ，证明：( 1 ) 由循环矩阵性质得：认刚砜+ ( n - r e ) t j , - r m , _ me x p 挲+ 2 n - 1 ，t ( n - - m ) l mc o s f 警等)另- y f n 州半) = i 1g “- , , - i f ( 、( 2 l + 。1 ) z 。)；圭东m i - , t ，e x p t 等竽)= ：魏+ z 2 t jc o s 等擎】砥= ：= ! 。岛c o s 警竽一r o + ：掣华c o s 譬竽眦椭印。( 半)蕾9 页里坠型堂垫窭叁堂型壅生堕堂些堡兰一一一现在我们计算 7 阶矩阵s 。和s 。的特征值，首先我们构造函数引曲2 焘 焘酣砌小o s 妇n + 1”+ j 百类似定理3 的证明可得：定理5 矩阵s 。和s - 。的特征值可分别表示为姒趴，细。( 熹) + g “箸)九( s 舢) = “兰)= 1 2 一，接着，我们将讨论h a r t l e y 变换基预条件子的特征值如果我们置h ：c + s ，c ：下1 ( c o s 2 j z ) ，s ：下1 ( s i n 2 j _ _ k k ) 则有nnnn引理4 ( 参见 1 0 】) ( 1 ) 设a 是循环矩阵，r e d 。，i m d 。分别表示矩阵a 的实部与虚部，则h a h = r e d j + j i m d ( 2 ) x s s xs ，x c = c x = c ，从而h x = x h( h ，爿定义见上蕈)构造函数 。( x ) = ：，s i n & ，利用定理l ，定理3 与引理4 ，我们可以算出矩阵h ( t 1 的特征值。定理6 最优h a r t l e y 变换基预条件子h ( t ) 的特征值满足- ( ( 丁) ) ：叮。( 丝) + 。( 丝) ，：0 ，l ，1 ，n l3 2新的预条件子的设计上节中，我们研究了生成函数f ( x ) 的f o u r i e r 级数部分和或c e s a r o 和与几类典型的循环、斜循环以及两类变换基预条件子的特征值之间的关系，下面我们将第一节中和式项数n 1 或【兰】变为一般的数p ，则可以建立起具有一般性质2的新的预条件子。3 2 1新的循环类预条件子对于o p n ，定义循环预条件子s p 的特征值为雏l o 页堕些坐兰垫查尘兰型壅生堕：；i 三丝丝兰以( c ：厶( 三丝) ，t ：o 1 ，2 ，”一l玎则c y l 的显式表达式为c y =7 1 ( r 。，f ，一，o ，o ，一，o ，f ，t ，一，一)o p ；t ( t o ，f l ，r h 一，一i ，l h 一，+ ，p ，”一p + 1 + ，p 一1 ，( 3 2 1 )，+ k 川，w m ，f 1 )白 p sn 一1容易知道c ? ：”：c 。，c 。i , “】- c ，j 22新的斜循环类预条件子对于o p n ，斜循环预条件子s 。”的特征值定义为丸( 掣) ；l ( 业) ，：o 姚月一1则s 妒1 可显式表示为s =r ( ，。，f l ，一，r ，o ，o ，- 一，o ，一，p ，一，p l ，- ，f 1 )o p s 【；r ( f 。，f l ，f 。一p ，f ，。一，+ 1 f p ，l ，( 3 2 2 )一，o t _ p ，- - 一，一1 ，。)【昙 p s 打一132 3新的正弦变换基预条件子现在我们讨论f 弦变换基预条件子的设计方法。对于o p 0 l i r a p 。+ 哆( z ) c 2 。，则预条件子跚对充分大的n 是正定的，而预条件子c ，s 和s 玩恒为正定的，且点1 是，o c c , n 、 。瓦( c 妒) “l ，( s ) “t 和( s 恐) “疋的特征值的聚点。( 注：对预条件子锹，条件厂( x ) c 2 。可用厂( x ) 上2 代替。)证明：+ l i m p = + o 。，f ( x ) c 2 ，存在充分大的n ，当p n 时，总有厶( x ) 詈 o 乏e o ，2 万) 2 z 一致成立。利用( 3 2 1 ) ，( 3 2 2 ) 及( 3 2 3 ) 式以及定理7 和定理8 ，知c ；”，s 和s 鼢均为正定而且，对于矩阵s 揪，满足( 母0 ) = 仃。( 堡) ，；0 , 1 ，2 ，月一l疗第1 3 页我们得到口。( x ) 脚 0 ，从而 ( s 职) m 0 ，s 豫是正定矩阵。为了证明矩阵( c ) 。t 的特征值以1 为聚点，我们考虑两种情形( 1 ) o p 白，则c ；= t ( t 。，f 一，f p ，0 州0 ，0 ，u ，0p ，c y l 一r ，= 7 1 ( o ，0 ，一，0 ，一，。p ，f l l n - i ) ，一啦= 2 ：? k ( ”r 。) 24 ：? 女( 露+ r o= 4 ( ：? 灯：+ ：( n 一七) f ：)由于厂( 工) ：，则伸o ，； o 存在n ，使得当p n 时4 擎 ；而且存在n 使得三酗n - n ，则：一2 - 。k m - ip + ：( 一叫r ：) 昙：灯：+ 4 ：+ 4 ： o 在 o 2 x ) 上对所有n n2 - - 致成立，因而推出尊1 4 页一丝r拈一一一：一一汕：一m：塑f p 竺咖一咄瓣丽一冈防利学技术人学研究生院学位论义以( 掣) 要，k = 0 , i 一2 一，月一1对所有p n2 成立，因此煨1 一u ：云( 3 4 2 )由( 3 4 1 ) 式，( 3 4 2 ) 式我们有炉一1 l 一，m = 炉“( l 一掣呱i f c m ) “| | 2 f | l c 圳：扣刮虻m “”7= o ( n )( 2 ) 已】 p 0 ，可得又由可将s 嬲重新表为黔捌)踟：杰( 1 一i - 1 ) t , , q踟2 善1 。pqs ：! ：= t l s 。( z ) 一z 。( c r ( z ) )其中：= ( “，p - 1 l ，一，土t p _ 1 , 0 ，o ) ，设pp纂1 5 贰( 3 4 - 3 )i 鲥防学投术人学训究生航学位沦殳l ：( o 1 i , - 7 _ 1 2 ，型，川”，。i ) 7l = ( o 2 ，- ，：二，r i ，p ，一i ) 。ppp经整理得到，p - 1 ，。j ，0 ，p拇曩圳2 _ i s p - , ( 枞丁k2 ”2 ：一t ) ，：十：( k22 + 1由于三，；c + 。，! i m p = + o 。对任意占，o 成立，故我们总能找到正整数使得o t 2 三1 6成立。对给定的n ，存在n 。，只要p n 。，就有；叫了k2os j 2 ：一n , ，2 1 。2 n ，我们有；跏一，) 等- 2t k2 ；【踟一尹k22 + 跏堋2 + 。p - i ( k22 + ：r 。2 】s ；拇t ) 笋十z 赫“：_ 2 + 言叫k 22 + ：= o 搿2 s即愀曩一堋= o ( n 由( 3 4 2 ) 式，得f l ( 蹦) 。l 一，m = 煅( s t m ，) 。( l 一& i n ) j i ，2岩) 。1 2 l l l s 圳：扣一删：- - o ( n )第1 页，3 一p2 一p(1 l工一璺坠丛望些查叁兰婴塾生堕堂垡堡墨因此定理成立。做类似分析我们可以证明矩阵( s ) 。f ，和( s ) 。l 的特征值以1 为聚点。推论设对称t o e p l i t z 矩阵t 。= t ( ，o ，i ，t h ) 是近似带宽的，即，= o ，k f 0m 。是满足下述条件的对称矩阵0 m 。忆= o ( 行)k 。与m 。是同类的，则霞。= k 。+ m 。满足恽一艇= o ( 一)定理9 表明，有效预条件子添加一种无穷小量矩阵( 指特征值趋于零) ，仍为有效预条件子，这为我们下面找到更有效的预条件子提供了依据。3 5 数值例子这一节，我们将通过数值例子说明，对一些以前的许多预条件子失效的t o e p l i t z 矩阵，本文的预条件子校正技术对其进行校正后将变的有效。例。考察t o e p l i t z 系统的生成函数m ，= 兀斗p f z 妒：c o s 斋e 刚舡 + ，b 胁) - 2 c o s 熹e x p f 即，x 【0 , 2 ，r 】，由于，( x ) 0 可推得生成的t o c p l i t z 矩阵恒正定。但是另一方面当”2 s 6，循环预条件子c 。，正弦变换基预条件子s 。均为半正定，此时求解t o e p l i t 方程组的预条件共轭梯度法都将无效，作校正矩阵：己= g + f d i a g 2 0 ，茏一，) ，。第1 7 页闺防l 学拽术凡学_ | l j 究生院学位沦义其中7f 1 当 ( g ) = 0九2 1 0其它同理可构造出校难矩阵文。，则从表1 ( 见下页) 看出用校正矩阵作预条件予，则预条件共轭梯度法都收敛。其中迭代过程停止条件为：相对误差限小于l o 。表1 各类p c g a 方法迭代次数i 6 41 2 82 5 65 1 21 0 2 4c |2 93 8c _1 41 62 03 03 7s r ，|3 04 0j瓦、。】31 72 】2 22 8( 注：表i 中，表示方法无效。)第1 8 页周防科学技术人学研究生院学位论义第四章基于离散w 变换的t o e p ii t z 预条件子的构造4 1 离散w 交换矩阵a ；被称为斜循环矩阵，如果a 一。= ( c 。戌j k ，c 。= c 。且c 。，= 一。i = 1 , 2 ，”一l 。并表示为a l = c i r c 一】( c o ，。，c n - i ) 。下面给出离散w 变换( d w t ) 的定义。实序列 a 一( ，= 0 , 1 ，h 一1 ) 的离散w 变换定义为互= 属叩眦和训”仞争其中口，卢是实数，当( a ，声) = ( ；，o ) ，( o ，；) 或( ；，；) 时，存在快速zzzw 变换算法，将上述不同形式的d w t 分别表为d w t i i ，d w t i i ，d w t i v ，而变换矩阵则分别记为w i 】，w m ，w 。容易证得矽i 】7 = w i ”矿l 7 ( w 1 1 ) = ，。引理6 ( 参见 1 5 ) 设斜循环矩阵a 一。= c i r c 一，( c 。，。1 ) 一，c n - i ) 的特征值a ( o sk sn 一1 ) 满足a = r e 丑+ j i m a , j = 一1 ，r e d l 2 d i a g r e k o ，r e ，r e 丸一1 i m d b = d i a g i m k o ，h n ，h n 以一l 置换矩阵j ，= ( l ，) ：l l o 满足 * = 拈”1 訾 “。时，则矽a 一1 矽t i = r e d 一，+ ，li m d a _ 推论1 ( 1 ) 如果a l 是实对称斜循环矩阵，则i i7 彳一l i j 2 r e d 簟1 9 夔璺堕型堂丝查盔堂型壅生堕兰篁堡兰( 2 ) 如果a ，是实反对称斜循环矩阵，则渺7 。a 一wi i = j 。i m d “交叉对角阵b = ( ( 6 。) 。n - 。i 。) 定义为6 “= o ，如果i 盘且j + 盘 一1 , 0 s f ，七s 玎一1引理7 可逆交叉对角矩阵关于矩阵乘法构成群，其线性方程组能用0 ( n ) 次算术运算求解。4 2 与离散w 变换有关的一类矩阵代数构造矩阵，2 = ( j h ) _ n - ：i 。f1f = 七= oj = 一1i + k = ”10其它c j 与s m 为w n l 的余弦与f 弦部分即w i i i ：c i i i + s i ”容易证得，；= ，c l n j 22 c m ，s m j 2 一s i n( 4 2 1 )由( 4 2 1 ) 并直接计算可得j l w i l l = w m d ，因此以w i i l a 一1 w n = w i n j ，a lw l i( 4 2 2 )如果我们取a 一，为反对称斜循环矩阵，由推论1 ( 1 ) 和( 4 2 2 ) 可得到w m j 2 一一i w i l 2 i m d 一，设c m 。，s m 。分别是所有实对称反对称斜循环矩阵的集合，即c 峨_ c 咖c o ”以。，c j 咄川，。，一1 娜引)s m 。= 弧o , c i , c 2 ， , c n _ 1 ) ，c ，咄l 娜川一= 。，1 娜刨)其中r 为实数域，定义下列胆n 阶矩阵矿= a + j 2 b ，a c m 。，b s m 。)以及为所有满足w i e w i i = d i a g ，兄2 ，a 。 矩阵e 的集合，则d i m = n 第加页型些型兰垫查叁兰! ! ! ! 垒竺堕堂丝垒兰一任取v 痧，腿0 v = a + j 2 b ，a c m 。，b s m ，且w m v w i i = w i i i a w l l + w i n d ，bw i f= w i i i a w 】i + ，i w m bw l l2 r e d + i m d = d i a g 五o ，a - 一五， )推得矿w i ，另方面，c m 。ns m 。= 0 且d i m c m =d i m s m ，=罢n 是偶数2尘生。是奇数兰 是偶数2芝兰。是奇数1d i m w = d i m c m ，+ d i m s m 。= n ，从而妒= 。进一步地，我们可得下面的定理。定理1 1 所有能同时被d w t i i 变换矩阵对角化的矩阵类为矿。4 3w 变换基预条件子的构造及谱性质本节我们提出类新的预条件子是下列问题的极小解：m 酬胛旷l 忆胛i ，矿定理12 矩阵彬( l ) = a 。+ 以e 矿定义为( n i ) t ，一i t 。一a o2t o ，口。：l 。门6 ，：生丝j ：1 ，2 ，一，肝一1打使得任意w e 矿，满足i 吵一瓦忆最小证明：结论可对表达式i 吵一忆关于，口，b ，i = 1 , 2 ，n 1 求犏导数得到。!第2 i 页型坠型堂垫查叁堂型! ! 兰堕羔丝堕苎一一假设所有斜循环对称矩阵构成集合阳。，则犯。形，d i m s c 。= l ；j ，d i m 痧= n且s ，= ( s ( 爿) ：m i n t s ( a ) 一l 忆，对任意的s ( _ ) s c 。)彤( 7 ：，) = ：m i n r l w t i i ，对任意矽矿这表明彬( f 】) 和s ，分别为n 维矩阵空间矿及其l 兰j 维子空间s c 上按f r 。b e n i u s范数对瓦的最优逼近，从而彬( l ) 。瓦的范数可能小于s ，。的范数并导致更好的收敛性下面我们就来考虑新的预条件系统的谱性质仍采用第三章中的记号，称以2 n 为周期的l e b e s g u e 可积函数厂( x ) 缓慢趋于0 的，如果磐织q m ) 陋= 0其中r 10 y o妒r ( 工) = 1 0工 设函数岛( x ) = f 兰y z , d k “1 s i n h ，则我们有引理8 矩阵( l ) 的特征值可表示为以( 彬( l ) ) ：盯。( 堡生三竖) + g 。( 堡垒旦姿) ，k ：0 , 1 ，2 ，m 一1 ( 4 3 1 )证明：利用斜循环矩阵的性质以及，。= f 一。知纵驴知x p 等半)一r o + ：= ：半e 印 等半)+ ：堕警唧 等半) + - 堕半e 冲 等攀= i lk n - i 。t - - , , t , e x p 等半：吒( 螋)，i 褥页型坠型兰! ! 尘叁兰型! ! 生堕兰些堡! “1 于b 。是反列称斜循环矩阵，由定理1 2 我们有r e d 。= o ，又由( 4 1 1 ) 得【i7b 。wi 1 2 j id i a g i m 2 0 ，i m l - ，l m l j - j ll m d n 其中i m 丑：笋止血s i n ( 2 k + 1 ) h rx ，( 业) ，t ：o ，1 ，2 c - - 1 “乞f刀胛以由( 4 22 ) 则j iw i i7b 。w 】1 = w 17j ：b 。w 1 1因而a 。，j ：b 。可以同时被彤变换矩阵对角化，等式( 4 31 ) 成立。定理13 若，( 工) 2 ，( x ) 朋 0 ，则对充分大的n ，w 变换基矩阵暇( r ，) 是对称正定的，且矩阵k ( r ，) “f ，的特征值以1 为聚点。证明：由于l 厂( x ) m o 以及引理8 可得以( ( 瓦) ) 肌+ g 。( 堡生 丝) ，而) 甜圣奎娶兰竺门颦：墼胛、，行因此l i r ag 。( x ) = 0 对x 【o ，2 石) 一致成立，从而存在n 。使得以( 彬( l ) ) i f f l 对n n 。成立，彬( r ，) 为对称正定矩阵，且l 暇( l ) 一i i ：豪成立，利用定理1 2 则0 l 一彬( l ) 忆s 专4 阢一彳。忆+ l l j ：b 。忆、，门、n忆b m =击万s 訾。( n + )；1 1 7 - a 嵯薯盟掣第2 3 页罔防罩= | 学投术人学州究生院学位论义p a r s e v a l 等式保证了对任意 0 ，存在，使得对所有 n击l l r , , - a , , i i ，s 嘉跏2 ( 胆叫”2 女2 ( ”叫。2t 成立。对充分大的n= 4 乞。n - i ( ”一懈砉磊坳一姐t 2 半磊r t 2 0 ，构造校正最优w 变换基矩阵彬i l ) 为其中彬i l ) = 1 ir d i a g , j ：o ，五，无一。 w1 17f ( 彤( l ) ) ， 。16当 ( 彬( l ) ) 0其它定理1 4 设厂( x ) 是工：中非负缓慢趋于0 的函数，则校正w 变换基矩阵彬i l ) 是对称正定的，且矩阵i l ) - 1 l 的特征值以1 为聚点。推论设厂( x ) 是非负分段连续函数且有可数个零点，则矩阵彬i 瓦) 一1l繁m 页m 耽科学技术人学训究9 ：院学位论史的特征值以1 为聚点。4 4 数值例子本节中，我们对几种不同预条件子的谱性质和聚点性质进行检验。例1，= 去，i = o ，1 ，2 ，一，1 9 ，图1 分别显示了，彬( t ) _ 1 丁，s t ，c i l t 的特征f + l值。从图中，我1 f 3 7 6 难发现，( l ) 的聚态性质明显优于s 和c 。图1例2 = 百南，f = o i l ，2 ，1 9 ，图2 分别显示了丁，彬( 。) - i t s s t c i 7 的特征值。图2实际_ 匕，此时生成函数厂( x ) = 2 万l s i n 引是连续的且在点x = 2 七石，k 一一2 , - l ，0 ，1 ，2 ，为0 ，而f ( x ) 是不光滑的甚至一阶导函数也不连第2 5 页闽防科学技术人学圳究生院学位论义续。另一方面，我们知道，暇( f ，) 的特征值近似为生成函数f ( x ) 的c e s a r o 和在某些点的值，瓦和c 。的特征值是f ( x ) 的f o u r i e r 级数部分和在某些点的值，利用f o u r i e r 级数的性质可得c e s a r o 和一致收敛到某个函数而不依赖于函数的光滑性，而f o u r i e r 级数部分和的收敛性本质上取决于函数的光滑性，这也许可以解释m ( l ) 优于s 。和c 。的原因。第拍爽鬯堕型兰些查叁堂型堑兰堕兰堡堡兰一第五章基于正弦变换类交叉对角化t o e pljt z 预条件子的构造空间本章中，我们将提出一种新的预条件子，虽然它也是基于正弦变换的，但和已有的预条件子不同的是：新的预条件子不是被正弦变换对角化，而是被其交叉对角化。构造过程中，我们可以发现，已有的币弦变换基预条件予只是新的预条件子的一种特殊情况。5 1 特殊对角化正弦变换基预条件子的空间出引理3 可知，当五。= o 时，有( 一1 ) 砀= of - l从而可得：引理4 对奇数阶矩阵，特殊对角化正弦变换基矩阵，即将其中心对角元变换为0 的矩阵空间为h it = v ，( z ) 一z 。( 盯( z ) ) lz = ( z 。，杰( 一1 ) 7 2 2 ，一25 2 交叉对角化正弦变换基预条件子的空间设l 是所有能被矩阵s 。斜对角化的矩阵构成的向量空间，即l = s 。s 。i 。为n x n 斜对角矩阵)j ，d 均为n xn 矩阵，j 的第( i ，j ) 元素为阳= ：蒜+ 1d 的第( i ，j ) 元素为f1i = ，= 2 k + 1d ( i ，j ) = 一li = j = 2 kk = 10其它第”页竹一l2型些壁兰塾查叁堂型壅生堕兰丝笙墨一一我们注意到即一方面为斜对角阵另一方面，s j s = dj s = s d0_0所以，d q 。= m 。构成l 。空间的一组基( 为非零实数)引理5l ： d ( v 。( z ) 一z 。盯( z ) ) 5z = ( z 】，z2 ，z 。) 7 r ”)证明：由上文可知d q 。构成l 。空间的一组基，故对任意l el ，唯一存在一组系数z ，z2 ，z 。，使得( 其中z = z 。g 。)月月l = z 。d q 。2 o d ( k ( e 。) - z 。( 盯( e 。) ) = d w ( z 。气) 一d z 。( 仃( z 。g 。) )：d ( 1 l ，。( z ) 一z 。仃( z ) )因此，l = d ( v 。( z ) 一z 。盯( z ) ) iz = ( z l ，z z 。) 7 r ”定理15 设p 为可被正弦变换矩阵交叉对角化的矩阵空间，则p 。= h ( x ) 一z 。( 盯( x ) ) + d ( 瑚。( y ) + z ( 盯( y ) ) )2x 2 ( x l ，( 一1 ) 7 x 2 ，x 。) 7 r “y 2 【y i ，y2 ，y 。) 7e r ”)1 - 2鬃丛页里堕型兰丝查盔兰型丛生堕兰些垒兰一证明：由引理4 ，引理5 可知，p 。，= t 。+ l 对任意p p ，存在x = ( x ，( 一1 ) j ：，t 25 3 数值实验下面我们通过实例说明新构造的预条件子的优越性，仍引用文献常见的例子。例1f ，= c o s ( 一1 ) i ；f = 1 , 2 ，5 2 1图一1图1 中，分别对应瓦( o 5 ) ，c s ( 1 o ) ，s s ( 1 5 ) ，p ( 2 o ) ，c s 。t ( 2 5 ) ，s s 。t ( 3 o )p1 t ( 3 。5 ) 的特征值。侈0 2r = 4 ( 1 4 i 2 ) ，i = 1 , 2 ，一，5 2 1 ；图一2 中，分别对应l ( 0 5 ) ，c s ( 1 0 ) ，s s ( 1 ，5 ) ，p ( 2 ，o ) ，c s 。t ( 2 5 ) s s 。t ( 3 o )、第i 9 疑y仃zb啦d+。扭酿口r()nhzy，一一仅”。yv，l lpf 蝌璺堕型兰垫查叁鲎型壅生堕兰竺堡兰p1 t ( 3 5 ) 的特征值。纂如翼闯酗科学挫术人学研究生院学位论义第六章利用小波变换与多重网格算法求解病态t o e p ii t z 系统在卫星摇测、摇感、医学、实验物理等领域经常要对信号进行高清晰度的恢复，通常情况下，我们观测到的信号，经过数学上的离散化后可表示为h a + r = g其中h =h oh lh oih lh 口h 口h oh j：h 是一个n i 3 带宽列循环矩阵，n 与n 分别为输出与输入信号的长度，口1 3 1 ，= ( ，。一x ，1 ) 。，g = ( g o ，g 一，g ) 7本章利用正弦变换类预条件共轭梯度法、多重网格算法并结合小波变换技术求解下述在实际应用中广为采用的最小二乘模型m 。i 。n 0 h x 一柏或者等价的h lh x = h tg在实际问题中，利用前提条件通过直接计算可将上式化为下列形式l = b其中，b = ( 6 0 ，乜，b 。) 7 ，t = ( t k - j ) o s ，。一，为对称t o e p l i t z 矩阵，并且满足铲1 一x - , 乙- k h 。：菇嚣戮川b = h m gf ，k = 0 , 1 ，2 ，n - 1 “一一纂，l 页下面我们将指出当信号重构模型为病态时t 利用本文的新方法构造禹散小波变换，并将多重网格法以及小波变换技术相结合，可以给出一种有效的信号重构方法。数值实验表明此方法对各种不同信号的重构可达到高效。6 1 多重网格算法对方程组r , x ，= b ，z ，r “，1 7 p的求解( 其中p 为总水平数，而l = l 为最小水平数) ，利用j a c o b i 迭代，可将其转化为乃v ，= d 其中v 是一个光滑的网格函数，将粗网格运算定义为从而可利用粳网格方程正= _ ：1 正+ l ，“1 ，1 ，s pi 一1 v ，1 = d h来逼近精确解。我们希望v 。是v ，的一个精确逼近，但v 。仅在粗网格上有定义因此我们利用瓦= p v 。对此粗网格函数进行插值( 如分片线性插值) 。这一过程称为粗网格校正，尽管粗网格校正似乎是有效的，但由于其本身是非收敛的迭代，故不能做为一种收敛。光滑迭代和粗网格校正的组合产生了快速收敛，但各自收敛缓慢，甚至不收敛，这样的组合称为二重网格迭代，因为它包含了，和，一l 层，我们小结其算法如下，( 其中，线性插值算子与限制算子分别为_ j 】：r “一只1 以及_ 卜1 ：r 1 一r 嘶“)p r o c e d u r et g m ( i ，x ，b ) ；i n t e g e rl ；a r r a yx , b ；i f1 = 0t i l e nx ：；玎。be l s eb e g i na r r a yv ，d ；x ：= 妒j ( z ，b ) ；( k 次前光滑迭代)d ：_ r + ( 正x b ) ；( 亏量限止)、v ：= _ ：t d ；( 粗网格方程求解)x ：= ) ( - p + v；( 对x 的校正)e n dt g m ；繁3 2 甄国防科学技术人学州究生院学位论文j 二述算法依赖于v 是先进行光滑迭代后粗网格校译；更一般地，可以先进行v 步光滑迭代，然后在粗网格校f 之后再进行v ，步迭代，结果导出算法：p r o c e d u r et o m ( 1 ，x ，b ) ；i n t e g e rj ；a r r a yx , b ；i f1 = 0t h e nx ：= t o - + be l s eb e g i na r r a yv d ；x ：2 钟( x ，b ) ；( 前光滑迭代)d ：2 p ( r , x b ) ；( 亏量限止)v ：。r , - ：+ d ；( 粗网格方程求解)x ：2 x p + v；( 对x 的校正)x ：2 妒? 2 ( x ，b ) ；( 后光滑迭代)e n dt o m ；当粗网格方程组的求解存在较大困难时，采用多重网格算法对粗网格方程组的求解过程进一步近似，从而得到p r o c