（计算数学专业论文）toeplitz型矩阵类的快速算法及性质研究.pdf

t o e pi it z 型矩阵类的快速算法及性质研究 摘要 t o c p l i t z 型矩阵及与之密切相火的v a n d e r m o n d e 型矩阵、l o e w n e r 型矩阵、 循环分块矩阵利广义中心对称矩阵等，是应用最“泛的特殊矩阵类之。盯丁这 类矩阵在许多科技领域中有着广泛的应用，所以对该类矩阵的研究一直甚为活 跃。本文针对l b e p l i t z 型矩阵和v a n d c r m o n d e l o e w n e r 型矩阵，得到了求解线性 力程组、m o o r e p e n r o s e 逆、求逆等的新的快速算法。也对有关正稳定矩阵的问 题进行_ r 研究，给i u 了判定特殊对称循环分块矩阵和特殊广义中心对称矩阵为正 稳定矩阵的充要条件。本文的内容安排如一i c ： 第章给出了问题的应用背景及研究现状。 第章给出了相关矩阵的定义及基本关系式。 第三章通过构造特殊分块矩阵并研究其逆矩阵的快速三角分解，分别给j i 了 求以秩为m 的h m 阶t o e p l i t z 型矩阵和v a n d e r m o n d e l o e w n e r 型矩阵为系数阵 的线性方程组极小范数最小二乘解的快速算法，并通过算例将新算法与已有的法 方程组的方法和诈交化方法作了比较。 第四章通过构造特殊分块矩阵并推导其逆矩阵的快速算法，得到了求 t o e p l i t z 型矩阵m o o r e p e n r o s e 逆的快速算法，并给出了数值算例。 第五章利用t o e p l i t z 型矩阵的特殊结构，导出了求t o e p l i t z 型矩阵逆矩阵的 快速算法，给出了相应的数值算例。 第六章给出了判定特殊对称循环分块矩阵和特殊广义中心对称矩阵为正稳 定矩阵的充要条件。 关键词：t o e p l i t z 型矩阵，v a n d e r m o n d e l o e w n e r 型矩阵，m o o r e p e n r o s e 逆，正 稳定矩阵，列称循环分块矩阵，广义中心对称矩阵 阳北i 叫k 人学颂 学位论文 r e s e a r c ho nt h ef a s t aig o rit h m sa n dp r o p e r tie s o ft h ek i n do ft o e p ii t zt y p em a t r i c e s a b s t r a c t i b e p l i t zt y p em a t r i c e sa n dv a n d e r m o n d et y p em a t r i c e s ，l o e w n e rt y p em a t r i c e s ， c i r c u l a n tp a r t i t i o n e dm a t r i c e sa n dg e n e r a l i z e dc e n t r a ls y m m e t r i cm a t r i c e s ，w h i c ha r e n e a r l yc o r r e l a t i v ew i t ht o e p l i t zt y p em a t r i c e s ，b e l o n gt o o n eo fw i d e l y a p p l i e d s p e c i a lm a t r i c e sk i n d s t h er e s e a r c ho nt h ek i n do fm a t r i c e si sv e r ya c t i v eb e c a u s e t h ek i n do fm a t r i c e si sa p p l i e di nm a n ys c i e n c ea n dt e c h n o l o g yf i e l d s a i m i n ga t t o e p l i t zt y p em a t r i c e sa n d v a n d e r m o n d e l o e v ) n e rt y p em a t r i c e s t h cp a p e rg i v e s s e v e r a ln e wf a s ta l g o r i t h m so fs o l v i n gl i n e a rs y s t e m s ，c o m p u t i n gt h em o o r e p e n r o s e i n v e r s ea n dt h ei n v e r s e f i n a l l y , w cr e s e a r c ho nt h ep r o b l e m sa b o u tp o s i t i v es t a b l e m a t r i c e sa n dg i v et h en e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n sf o rs p e c i a ls y m m e t r i c c i r c u l a n tp a r t i t i o n e dm a t r i c e sa n ds p e c i a lg e n e r a l i z e dc e n t r a ls y m m e t r i cm a t r i c e s b e i n gp o s k i v es t a b l em a t r i c e s t h eo r g a n i z a t i o no ft h ep a p e ri sa sf o l l o w s ： i nc h a p t e ro n e ，w ei n t r o d u c et h eb a c k g r o u n da n dr e s e a r c ha c t u a l i t yo ft h e p r o b l e m s i nc h a p t e rt w o ，w eg i v et h ed e f i n i t i o n sa n db a s i cf o r m u l a i nc h a p t e rt h r e e ，b yc o n s t r u c t i n gas p e c i a lp a r t i t i o n e dm a t r i xa n ds t u d y i n gt h e f a s tt r i a n g u l a rf a c t o r i z a t i o no fi t si n v e r s em a t r i x ，w er e s p e c t i v e l yg i v ef a s ta l g o r i t h m s f o rt h em i n i m a ln o r ml e a s ts q u a r e ss o l u t i o n so fl i n e a re q u a t i o n sw h i c hc o e f f i c i e n t m a t r i c e sa r en mt o e p l i t zt y p em a t r i c e sa n dv a n d e r m o n d e l o e w n e rt y p em a t r i c e s w i t hf u l lc o l u m nr a n k f u r t h e rw ec o m p a r et h en e w a l g o r i t h m sw i t ht h em e t h o db y s t r u c t u r i n g n o r m a l e q u a t i o n sa n d t h e o n h o g o n a l i z a t i o nm e t h o db yn u m e r i c a l e x a m p l e s i nc h a p t e rf o u r , b yc o n s t r u c t i n gas p e c i a lp a r t i t i o n e dm a t r i xa n ds t u d y i n gt h ef a s t j q j l 州k 人学硕十学位论文 a l g o r i t h m so fc o m p u t i n gt h ei n v e r s e ，t h ea l g o r i t h m so fc o m p u t i n gt h em o o r e p e n r o s e i n v e r s eo ft o e p l i t zt y p em a t r i c e sa r e g i v e n a tt h es a m et i m ew eg i v en u m e r i c a l e x a m p l e s i nc h a p t e rf i v e ，u s i n gt h es p e c i a ls t r u c t u r eo f i o e p l i t zt y p em a t r i c e s ，w es t u d y t h ef a s ta l g o r i t h m so fc o m p u t i n gt h ei n v e r s eo f t o e p l i t zt y p em a t r i c e s l a s tw eg i v e n u m e r i c a le x a m p l e s i nc h a p t e rs i x ，s o m en e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n sf o rs p e c i a ls y m m e t r i c c i r c u l a n tp a r t i t i o n e dm a t r i c e sa n ds p e c mg e n e r n i z e dc e n t r a ls y m m e t r i cm a t r i c e s b e i n gp o s i t i v es t a b l em a t r i c e sa r eg i v e n k e y w o r d s ：f o e p l i t zt y p em a t r i x ，v a n d e r m o n d e l o e w n e rt y p em a t r i x ，m o o r e p e n r o s e i n v e r s e ，p o s i t i v es t a b l em a t r i x ，s y m m e t r i cc i r c u l a n tp a r t i t i o n e dm a t r i x ，g e n e r a l i z e d c e n t r a ls y m m e t r i cm a t r i x 第一章引言 1 。1 应用背景 t o e p l i t z 矩阵及与之密切相关的v a n d e m l o n d e 矩阵、l o e w n e r 矩阵、循环分块 矩阵和广义中心对称矩阵等，是应用最广泛的特殊矩阵类之一。从5 0 年代术至今， 该类矩阵的研究。直受到人们的重视，是甚为活跃的研究领域之。 t o e p l i t z 矩阵在数学和工程。 有着广泛的应用。例如，在信号处理中，有赖丁 通过求觯t o e p l i t z 矩阵方程组状得的参数包括：递推数字滤波器的系数“”1 、一维 和二维平稳自回归( a r ) 模型的a r 参数”1 ”1 等。又如，信号和图像的恢复也可归 结为t o e p l i t z 矩阵方程组的求解“。其他的应用例子有：偏微分方程和卷积型积分 方程的求解、p a d e 逼近和控制理论中的最小实现问题等1 。v a n d e r m o n d e 、l o e w n e r 矩阵及其组合矩阵在多项式插值与曲线拟合、控制沦与系统理论等领域c j 有着重 要的应用”。”1 9r “”。如：i b 实验测得函数y = - 厂b ) 在坍个点卜的值b ，y ，) ( f = 1 , 2 ，肌) ，其中_ x ，( j ) ，如果用p 0 ) = 9 0 ) + g )( 其中g g ) 是多项 式而 x ) 是有理多项式) 按最小平方逼近的思想拟合这组数据，问题可转化为求以 v a n d e r m o n d e - - l o e w n e r 矩阵为系数阵的矛盾方程组的最d , - - - 乘解。由于最, b - - 乘 问题在数理统计、数学规划、系统辨识、信号处理、控制论、经济与生物工程等 领域”1 。“”中有着广泛的应用，如在统计学中，常对所构建模型的未知参数进行 最小二乘估计“；在系统辨识领域中，常基于最小二乘原理建立辨识算法“；在 自适应信号处理中，研究自适应滤波器时很多问题都基于求解线性方程组的最小 二：乘解”“；在工程技术中，常常利用最4 , - 乘方法进行曲线拟合和最佳逼近“。 因此，研究求解线性方程组的最d , - - 乘解问题有着重要的实际意义。本文研究了 求解以t o e p l i t z 型矩阵和v m a d e r m o n d e l o e w n e r 型矩阵为系数矩阵的线性方程组极 小范数最小二乘解的快速算法问题。 广义逆矩阵是逆矩阵对奇异矩阵和长方矩阵的推。，它在数理统训、系统理 论、优化算平l i 控制论等许多领域”。- j 有雨要的应用。对广义逆矩阵的理论和应 用晌研究足矩阵论的一个重要分枝。m o o r e p e n r o s e 逆矩阵是最重要的f 一义逆矩 阵之一。本文从逆矩阵和广义逆矩阵两方面刈t o e p l i t z 型矩阵f 内有关算法进行研 究。 稳定性理论是俄国数学家l y a p u n o v 存j | 世纪术创立的。山于他的i ：作，使 得判别一个线性系统的稳定性i 、u j 题归结为研究一个矩阵的特征值问题。因此，人 们称+ 个矩阵是稳定的，即是指该矩阵对应的线性系统是稳定的。目前，人们 醍 重视从矩阵的角度来研究系统的稳定性，并把具有稳定性的矩阵作为一个特殊矩 阵类束研究。正稳定矩阵是最重要的稳定矩阵之一。对于特殊知! 阵稳定性判别工 作的研究一赢是有关稳定矩阵问题研究的主要方面，而对称循环分块矩阵和广义 中心对称矩阵在数字信号处理，石油、地震物探，线性系统，线性估计等领域”1 一 有着重要的应用。因此，判定对称循环分块矩阵和广义中心对称矩阵为正稳定 矩阵有着重要的理论意义与实际意义。 1 2 研究现状 1 9 4 9 年，n l e v i n s o n ”首先给出了求解对称t o e p l i t z 方程组的快速算法；1 9 6 0 年，j d u r b i n “”给出了有关h e r m i t e 型t o e p l i t z 方程组的快速解法； 1 9 7 4 年， s z o h a r ”给出了解t o e p l i t z 方程组的类似的方法。 1 9 6 9 年，eh b a r e i s s ”4 1 通过构造一组同解的方程组推出了求解t o e p l i t z 方程 组的另一快速解法。 1 9 7 3 年，h a k a i k e “”给出了求解分块t o e p l i t z 方程组的快速解法。 t 9 8 5 年，r k u m a r “将t o e p l i t z 矩阵镶嵌成一个大的循环矩阵，进而得到求 解t o e p l i t z 方程组的快速算法。 1 9 8 6 年和1 9 9 5 年，t g o h b e r g ，j i n j e nh s u e ，”3 等人相继给出了求t o e p l i t z 方程组的几种快速算法。 但求解以 x m 阶t o e p l i t z 型矩阵( t o e p l i t z 矩阵是其特殊情况) 为系数阵的线 性方程组的研究未见。 关于v a n d e r m o n d e 矩阵的的研究，从二十世纪5 0 年代末至今，一直受到人 两北一1 ：业人学硕1 + 学位论文 们的重视。人们把v a n d e r m o n d e 矩阵从不同角度推厂，得到诸如v a n d e r m o n d e 型矩阵，v m l d e r m o n d e 类矩阵，合流v a n d e r m o n d e 矩阵等等一系列重要结果。 1 9 6 6 年，j n l y n e s s 和c b m o l e r 1 ，1 9 7 0 年，a b j o r c k 和v , p e r e y r a d 3 等 人分别给出了求解v a n d e r m o n d e 方程组的快速算法。 1 9 7 1 年，g g a l i m b e r t i 和v p e r e y r a 。“，1 9 7 3 年，a b j o r c k 和t e l f v i n g ”等 人分别给出了求解合流v a n d e r m o n d e 方程组的快速算法。 1 9 9 6 年，h a ol u 。”给出了v a n d e r m o n d e 类方程组和合流v a n d e r m o n d e 类方 程组的快速求解算法。 2 0 0 4 年，徐仲，陆全。“1 给出了求v a n d e r m o n d e 型方程组极小范数最, - - 乘 解的快速算法。 l o e w n e r 矩阵是由k l o e w n e r 嘲首先于1 9 3 4 年提出的，但在以后的研究中有 关l o e w n e r 矩阵的文献一宜较少。 1 9 8 4 年，z v a v r i n ”给出了l o e w n e r 矩阵求逆的快速算法，依此可得解 l o e w n e r 方程组的快速算法。 有关组合矩阵，1 9 9 5 1 9 9 6 年，k r o s l 和z v a v r t n “_ 。”1 给出了求以 l o e w n e r v a n d e r m o n d e 矩阵为系数阵的方程组的快速算法。但未见对以 v a n d e r m o n d e l o e w n e r 型矩阵为系数阵的线性方程组的研究。 t 9 6 4 年，w f t r e n c h 。”1 对h e r m i t e 型t o e p l i t z 矩阵给出了求其逆矩阵的快速 算法。1 9 6 9 年，s z o h a r ”将其推广到强非奇( 即各阶顺序主子阵均非奇异) t o e p l i t z 矩阵。 1 9 7 3 年， l a k a i k e “”给出了求分块t o e p l i t z 矩阵逆矩阵的快速算法。 1 9 8 6 年，a b e n a r t z i ”给出求非奇异t o e p l i t z 矩阵逆的显示表达式。 2 0 0 4 年，徐猛等“”人给出了求t o e p l i t z 型矩阵的逆矩阵的快速三角分解算 法。 但求t o e p l i t z 型矩阵的逆矩阵的快速算法的研究未见。 1 9 9 2 年，徐仲”“指出t o e p l i t z 矩阵的m o o r e p e n r o s e 逆可以表示为下三角和 上三角t o e p l i t z 矩阵的乘积之和。 1 9 9 4 年，g e o r g h e i n i g “”等人给出了t o e p l i t z 方阵的m o o r e p e n r o s e 逆的快速 算法。 两北t j 业人学硕十学位论文 2 0 0 4 年，魏义民等“人给出t - ；- t 1 算t o e p l i t z 矩阵的m o o r e p e n r o s e 逆的种 迭代算法。 但未见对求n m 阶t o e p l i t z 型矩阵的m o o r e p e n r o s e 逆的快速算法的研究。 在对判别矩阵为正稳定矩阵的研究中，对矩阵阶数n 较低时3 1 已经有了 比较有效的判定方法”“1 。对非低阶情况的判定研究结果较少，其中对三对角矩阵 和循环矩阵已有了一些研究结果”。 1 3 本文的内容及安排 本文研究列满秩的”x m 阶t o e p l i t z 型矩阵和v a n d e r m o n d e l o e w n e r 型矩阵等 的有关计算问题，给出了求解相应线性方程组极小范数最小二乘解和 m o o r e p e n r o s e 逆的新的快速算法，所需计算量均为0 0 聊) + o ( m2 ) ；而利用构造 法方程组的方法和正交化方法求最小二乘解所需计算量为o ( n m 2 ) + o b3 ) ，通常 求m o o r e p e n r o s e 逆方法的计算量也为o ( n m 2 ) + o ( m3 ) 。又对n 阶t o e l j l i t z 型矩 阵导出了求逆的新的快速算法，所需计算量为d b 2 ) ，而用全选主元高斯一约当硝 去法求逆需计算量为o ( n 3 ) 。最后，研究了判定矩阵为难稳定矩阵问题。各章安 排如下： 第一章给出了问题的应用背景及研究现状；第二章介绍了相关矩阵的定义及 基本关系式；第三章通过构造特殊分块矩阵并研究其逆矩阵的快速三角分解，间 接得到了求解t o e p l i t z 型方程组和v a n d e r m o n d e l o e w n e r 型方程组极小范数最小 二乘解的快速算法；第四章给出求t o e p l i t z 型矩阵m o o r e p e n r o s e 逆的快速算法； 第五章利用t o e p l i t z 型矩阵的特殊结构给出了t o e p l i t z 型矩阵求逆的快速算法； 最后一章研究了判定特殊对称循环分块矩阵和特殊广义中心对称矩阵为正稳定 矩阵的充要条件。 第二章相关矩阵的定义及基本结论 2 1 一相关矩阵的定义 证本文。用p ”裘示第i 个分量为1 ，其余分母为0 的，? 维列向避 z 。= 0 “，e p ，p ，o ) 表示”阶移位矩1 斗：。 考虑”0 l 阶t o c p l i t z 矩阱： r * ，of l t j，o f w + ir 2 ，一l lm l ： f 月4 - 1 1 存易验“ ：，+ l b c p l i t z 矩阡1 1 满足 r z 。t z j = k t1 ，r 一。) e l ”) + e l 。( o ，f l ，。t ，) 进m 何蜘i 卜定义。 定义2 ，1 “1 若矩阵丁= ( ，“l ，满足 ，一z 。他：蜘( “( ( z 1 1 ) 1 】 ：儿q - ，是i 卜整数，而 掌( ，) ：b ( j ( 1 ) ，譬( ，( 2 ) ，一，g 【，( n ) ) 1 ， j 1 = ( 【，( 1 ) ， ( ，( 2 ) ，- - ，h ( a ( 删) ) 7 川称7 1 为t o c p ii t z 型矩阵。 t o e p l i t z 矩阵是i o e p l i t z 型矩阵的特殊情形n 设f h ，肛：，“。妊矾个史数或复数，称”x m 阶矩阵v = k j1 聪，为 v a n d c r m o n d e 矩阵。又给定p q 耋f ；i 数z 。专o = 1 ，2 ，。) 和v ，”，( ，= l ，2 ，_ ) ，n 枷，吲乩，也黼邛仙= ( 等一舳e 划啦 似设“0 ( k = 1 , 2 ，m ) 。容易验讧 ，h 州阶v a n d e r m o n d e 矩阵p 满足 【儿i 北i ) e 人学侦扣学位论文 矿池毒，土，ii-zv=e计(一l，i1(12al，l a ln 。，l“2 i s 阶l o e w n e r 矩阵工满足 ，爿 d i a g ( t 1 ，一，) 一l d i a g ( v 。，一，v 。) = ( 营，f ，) 1 ( 1 ，一，1 ) 一( 1 ，- 一，1 ) 1 ( 目，- 一，。) 进而有如下定义。 定义2 2 ”。“1 若矩阵y = ( v 。l 。，满足 v d _ ，y ：圭暑“w 1 其r i ，f 为取定的m 整数，而 d = d i a g ( d 一d 。) 且d ，0 ( i = l ，, i f ) 占“) ：k ( ，( 1 ) ，g ( ，0 ) ) t ， ( ，) = 0 “( 1 l ，h ，( m ) ) t 称y 为v a n d e r m 。n d e 型矩阵。若矩阵工= 也) 。满足 d l 一l d ：芝p “1 1 其c pd 和d 2 南对角阵，p ( - ) ：( p 【，( 1 ) ，p ( - o ) ) t ，q o ) = 0 ( ，( 1 ) ，q j o ) ) 1 ，l ： 为取定的i f j ：= 整数，则称三为l o e w n e r 型矩阵。 v a n d e n n o n d e 矩阵和l o e w n e r 矩阵分别是v a n d e r m o n d e 型矩阵和l o e w n e r 型矩阵的特殊情形。 定义2 3 设组合矩阵c ：缈1 工) ，其中矿= ( v ，圯：，上= ( f 。p 篙分别满足 p 。一z 矿= 窑擘：n ，p 和。工一工。：= 羔j = l p ) a 材1 ( z ，z ) 这里d ，d 1 ，d ：为对角矩阵，v i _ d 的对角元非零，g ：= g o ) ( 1 ) ，g j jm ，) ) t ， ! ，) ：g ( - ( 1 x ， ( ，o ) ) t ，p ，】_ ( p 一( 1 l ，1 n ) ) t ，q 留= 0 ( 1 ) ，q b ：) ) t 卅1 + 2 = 删。称此组合矩阵c 为v a n d e r m o n d e - l o e w n e r 型矩阵。 定义2 4 w 如果”阶矩阵爿的每个特征值 ( f = l ，2 ，”) 的实部均为正值，即 6 = f v r e n ) 0 ( i = 1 2 ， ) ，则称a 为正稳定矩阵。 定义2 5 ”1 具有如下形式的p 阶方阶c ! 7 、r ) 称为实循环甜! l 晦 c 驴)f p ) c 掣，c 1 其中c p ( f = 0 , 1 ，p 一1 ) 为实数。显然c ? 山其首行元素唯一决定，简记为 c ? = c i r c ，c ”一，c ) ( 2 1 + 3 ) 定义2 ，6 4 1 具有如下形式的卵阶方阵0 。称为循环分块矩阵 c ? c ? c ”c ? c j 1 ) c 盱 c ：c ? c ? 其中c ? 忙= o “1 一，g 一1 ) 为形如式( 2 1 3 ) 的实循环矩阵。简记为 o 。= c i r c ) ，c ，c ) ( 2 1 4 ) 若0 。为刈称矩阼，称已。为实对称循环分块矩阵。 定义2 7 。3 设一，b 是川阶方阵；p 是卅阶可逆矩阵。称分块矩阵 足：。= f p 三嚣p b ，p 4 p 为广义中心对称矩阵。 2 2 基本结论 本节给出后面章节要用到的一些结论。 引理2 1 8 】设”阶矩阵s = b ，l 。的顺序主子阵s ( f = 1 ，2 ， ) 均可逆。给 定线性方程组s x = 6 ，其中b = ( 6 l ，一，b 。) 7 ，记b ，= 0 l ，b ) t 。而 j = ( x ，一，x 。) t ，l = 0 ，捌。) 1 分别是线性方程组s ，一= b ，s ，q = p 的解向 擐，则 其。p 铲竹，“ 盯，= b ，一s 。h ， 引理2 2 ”1 设 阶对称矩阵s 的顺序主予阵s ，( i = 1 ，2 ， ) 均i u 逆，义设 s ，z = p j 的懈向量为= 0 。，“。) 1 ，则 其中 = f 器舯川 1 “ 证明 殴s = b 。l 。= g 。，睢) 。，由假设知 利刚分块求逆公式得 副= ( 爷牡1 q l n 踞 1 ) 其。p 点= s ，一c ，l s i r 】c h 0 。上式右乘p y 得 嵋= s 1 p p = 茧一c s q 。 代入式( 2 2 3 ) ，并整理即得式( 2 2 1 ) 。证毕 定义2 1 给出的t o e p l i t z 型矩阵还满足其它的关系式。 定理2 1t o e p l i t z 型矩阵t 满足如下关系式： ( 2 2 1 ) ( 2 2 2 ) ( 2 2 3 ) ( 2 2 4 ) z j 丁一弦：笠1 ( 2 2 5 ) j = 1 8 、1， 0 s 出，l = s i 些：i ! 1 ：! ! 叁堂里! ：堂生堕皇 其中 t z 。_ r ：兰川】t ：k + e 9 ) e 如( ，：k 一，f ) ，p t ) ：一。z ) ：一。，1 ( 2 2 6 ) = h 7 ( ，= l ，f ) 1 = ( 0 一，。，) 1 ，口( ”) ：，) 。 _ r 】= g 。u = 1 ，) tr “。1 = ( o 。t 一，f 椰，) 7 ，( ) = 。t ) 1 k + e ，) e 炒u ：l 一，) ，) ：一。”。z ) ：一。粤 证明由式( 2 1 1 ) 得 ，一( z 。+ e 心，7 b ：圭 ( j 】7 一。陆 r z 5 ，= j 注意到( z 。+ e f ”) e ) _ 1 ：z j + 。? t ) 。 7 ，上式两边左乘- 。+ 。，0 ，1 1 ) 1 ，有 协+ 。矿j r 一秘j 挫理得式( 2 2 5 ) 。同理 注意到 ：毕。t + 。妒 “) 7 丁一邑丁协+ e 州一) 一k 十。“。眇嘁 占 ( j ) t 一毛窘) p 。 k + 。鼽妒) _ 1 ：瓦+ 。陆妙 则上式两边右乘( z ：+ 。乎e f m ) 1 ) _ 1 ，有 z k 。+ 。 m ，。等，7 ) 一z t ：圭g c ，l “) t ( z 。+ 。寥，1 ) 一邑n 7 p k 。+ 。 。乎，1 ) 糕理得式( 2 2 6 ) 。证毕 9 第三章求线性方程组 极小范数最, j 、- - 乘解的快速算法 3 1 基本思想 不草趟趟午勾造钓：妹分块m 阵并研苑其惩矩阵的快速三角分解，问接得到了求 解儿类“型”矩阵方程组极小范数最小二乘解的快速算法，摹本思想如卜。 设矩阵a 是秩为m 的 m 阶矩阵，构造 十m 阶矩阵 m = 三 b tt ， 易证，m 满足 ( 爿i n ，比分( 艺“巾0 于是 = ( k h 。枷0 比 一f 爿( 4 1 4 ) 。1 a 。一j 。a ( a 1 a ) 。1 一l( _ _ ) 一4 ( 爿1 4 ) 一j 因此，若能求出m 1 的三角分解，记做 m 一= ( 一0 7 ”u u ： ( 一。”。 ( 一u ，u 是 c s z ， lz 人d 几，。ij 其中u ，是卜三角阵，d 为列角阵，则有 a ( a 1 爿) 。a 。一j 。= u 】d u j i 。 a ( a 1 4 ) 一= u 1 d ，j ( 4 _ ) 。a 1 = u 2 d ，j ( 4 1 爿) = u 2 d u ； o 州北t 业大学硕十学位论文 斟此，线性方祥组a x = b 的极小范数最小_ 二乘解为 x o = ( 爿1 4 ) 。a 7 6 = u 2 d u m b ( 3 1 3 ) 由以上分析可见，只要求得式( 3 1 1 ) 的分块矩阵m 之逆的蔓角分解，即可通 过式( 3 1 3 ) 求得线性方程组a x = 6 的极小范数最，、二乘解。 又由引理2 2 得： 镀1 = 悟：) + u n f i t , u ： o h 九， oj 2 馁，絮j + l 眇l ( m 加j ：f ( 3 ： - t - i n2 0jt”一，“j：(，0cn一：，x：1r时j，k一，-i。)。，z。，j i2 x f 呐 2 。2j 、。 = 隧，譬心n - 2 ) k 。r ) 竹 峰城 = ，= ( 冶 。1 ) + _ ，+ ( ”0 一) 。一t - j 、。) + 以 。h ： = r ：甜。f 黛。 慨， 解向量甜，即可通过式( 3 】4 ) 得到s 的逆矩阵s 。1 的三角分解。 下面分别讨论以n r n 阶t o e p l i t z 型矩阵v a n d e r m o n d e - l o e w n e r 型矩阵为系 数矩阵的线性方程组的极小范数最小二乘解。 3 2 求t o e p ii t z 型方程组 极小范数最小二乘解的快速算法 设矩阵f 是秩为m 的n 聊阶t o e p l i t z 型矩阵，构造h + m 阶对称矩阵 t 卜 “ k 群 t ， 0 以_ _ 叫 曲北川k 人学硕十学位论文 由式( 2 】1 ) 知，m 满足关系式 m rz 。 jz i i 。jiz ，! j m = j 习 = o 丁地m 篙t t z 。t z l ：f 邑z j 。卜z 。t z ：1 l t r - z 。，t 7 z 。t 0 j = 撇1 ”“h 渺胪。叫 。 丢e f ”i + e f “+ ) 1 。e f ， 丢e “+ 月t ) 7 些驯+ 1 ”t “) 7 ) 其中 ，) = 鼢一忆 ( 3 2 2 ) ( ，= 1 ，) p ( ，+ 1 ) = 一丢 ”+ m ) ，口( ，十1 ) = 已f ”+ n ) 下面推导求m 。的三角分解的快速算法。 设式( 3 2 1 ) 的矩阵m 的顺序主子阵m = 1 ，2 ，月+ 埘) 均可逆，又设是线 性方程组m 。= p 的解向量。 当k = h ，n + m 一1 时，由式( 3 2 2 ) 知 一严m 。r = 鼬1 + 1 吼0 ) t + q 洲) z 。， 如果= h ，由式( 3 2 3 ) 得 2 p q 北t 、1 k 人学项十吖妒沦文 即 睁：卜，扣。，一( 一： f0 m 。+ 1 - 10 0纠 芝c p 黝。黝7 + 。蚴p 托1 ) m 。一( ( ：j ! ：1 + ( 器： = 芝j = 1 - 黝a 姚7 + a 托p ：2 ) | 一式右乘( ，得 其中 m 。( 一e 黠”一h 。( ”) e 船”= 一骞b ，p 1 2 + y p g 姚) ( s 2 。) = - - u n 0 彬( 1 ) ，= 一n 酗- - 1 蹦，) ( f + 1 ) ( 3 2 5 ) 删= 鼢 注意到m 。= 一i 。，则有 又由引理2 1 得 其中 删= m ，) = 一9 0 ) ，z ? l0 。 印k ( 学 刊。 3 = ， + 1 ，h 十m ) ( 3 2 6 ) o = 1 ，2 - ，? ) ( 3 2 7 ) = ( 。“。 ( j = 1 ，l ；k = n + 1 ，v + m ) ( 3 2 8 ) 型些迹垃k ，。7 = 一羔，埘。印奠 o ) ，以，：础j ( 女一。) 芝止。 ， 。) 式( 3 2 4 ) 左乘螈? ，得 1 似w ，2 蚓+ 妒撇 ) 每 、，卜r ) 。，o 、， h ，= 一f j ( ：；2 1 2 ) 结合式( ：3 2 - 8 ) ，并整理式( 3 2 】( j ) ，得 “1 2 ， “蔷7 - g + p p 船) = 礤：”一薯( 以( 喀j + “，( 秀7 ) ) 今 、 7 ” 则 其叶 ，2 志j = l 。谢十缈抄托) ( 3 2 1 2 1 叫以k 。q ，p 一 巩】也+ 倒l t t l x ( k - n 4 穰麓絮引 贮甜o t t o 曰( k w ，j 7 2 蔷眩二 口f ：_ 7 + g 足 p f 窖1 ) ( 。，。) 4 一引 明 毋o 岬 得 小 一o z帆 ，一吐 州i 坍“私川 巢 o o ；o 卜 一 ，。l = 站 一 些! ! ! ：! ! 丛竺堡! 堂堡鎏塞 式( 3 2 1 4 ) z - i 乘fo ，得 l “j 其中 叫料h 洳i 南， 。一，小+ 阻一似。) 。托o j l 仁l j 一喜b ，) p ：。+ 妒p - s 2 = 一骞i 妒t ”( ! ：。 + y 。 墨+ i c 。z s ， j 2 1 = 1 l”女l 女n + l 一( f 弘( f + 1 式( 3 2 1 5 ) 左乘m 0 。，并结合式( 3 2 6 ) ，得 ( 黝 型“。( f ) g “( f 十1 ) 。飞嵋p 卜。，卜。 t + 山+ 帅跗， 一m 乏。圭协+ 少 黝 _ 一圭嘲，) 船+ y l 心她 ( 3 2 1 7 ) 2 = 1 j = l 设吼，d ( k = t + 1 ， + 2 ， + m ) 是如下线性方程组的解向量 则 m m c 。l = p 黯”，m 。+ l d = p 瓣1 ) 帆c 。= i 商，1 ，m 。d 。= p 端 ( k = n + 2 ，”- i - 州) ( 3 2 1 8 ) c 十l = l f ”“，d ”+ l = h n 十i 由引理2 1 ，并结合式( 3 2 1 8 ) 和( 3 2 1 9 ) 有 旷f 。：) + c e k u k ,小( d o 5 + 版 ( 3 2 1 9 ) ( k = 月+ 2 ，”+ m ) ( 3 2 2 0 ) pj 婀北刖k 人学颁k 学位论义 其r 口t = 一，。t 。一，一耋，m 。c * 一，o ) ，卢m = 一”l l ik - n d * 一，o ) ( 3 2 - 2 1 ) 将式( 3 2 1 8 ) 代入式( 3 2 1 7 ) ，得 e + 。一“t ( n ) c * + + 篓r 。，“t ( f + ”) d * - 2 一喜b f 力棚 2 + f ，z l ： 将式( 3 2 8 ) ，( 3 2 2 0 ) 代入上式得 ( 。0 。 一。+ 一“。c 一 ( 名 + 口。+ ，t “+ ， + 萋；，。“。o + ”) ( 名 + 反+ 。 犯理得 令 则 喜 妒：力( 喘 + ；2 “。 + y p ( 。p 0 + v ：。“。 一：鲁晒p ，卢 2 + v ，v 盘) + “。( ”k ? + i 一 薹t = ：lr 。“。( f + n ) j 屏。 “+【，= 1 l j ；l 。+ 圭j = l f l 妒p ( 鼍 + 妒；7 ( 。 ：1 一“。) ( 名 + 薯r 。，“e o + ”) ( 乩：1 一圭妇l ，) ，。黝+ y ，) v 船) + “。o k 。一i 笠。“。( f + ”) i 风+ ， ( 3 2 2 2 ，= 1 l f _ 】 j i = 去( + 骞 妒p ( 喈 + y p ( 。| ： 一“t , h i l l + 善，。，“t 。+ ”) ( 名 ( 3 2 2 3 ) 由式( 2 2 2 ) ，( 3 1 2 ) ，( 3 1 4 ) ，( 3 2 5 ) ，( 3 2 7 ) 一( 3 2 9 ) ，( 3 2 1 1 ) 一( 3 2 1 3 ) ，( 3 2 1 6 ) ，( 3 2 1 9 ) 一( 3 2 2 3 ) 可得求m 。1 的三角分解的如下快速算法 q ，= 一p ? 。) m j ，) = 一g “) ，z ，1 = 0 。(