（计算数学专业论文）特殊矩阵类的结构及其快速算法.pdf

l ，q 儿l ：、l k 人学硕士学位论文 特殊矩阵类的结构及其快速算法 摘要 本文针对工程中常遇到的一些特殊矩阵进行研究，提出了h a n k e l 型矩阵、 对称h a n k e l 型矩阵的定义，得到了t o e p l i t z 型矩阵、l o e w n e r 型矩阵、h a n k e l 型矩阵、对称h a n k e l 型矩阵的显式表蒜给出了求解线性方程组、三角分解、 逆矩阵等的快速算法，主要内容如”卜： 在2 中，先后给 ：_ 了t o e p l i t z 型矩阵的显式表示、l o e w n e r 型矩阵的显式表 示、h a n k e l 矩阵的充要条件、h a n k e l 型矩阵的定义及慰式表示、对称h a n k e l 型 矩阵的定义及显式表示 在3 中，导出了求解对称h a n k e l 型方程组的快速算法，给出了数值算例 在4 中，导出了求解系数矩阵为对称l o e w n e r 型矩阵之和的线性方程组的 快速算法，给出了数值算例 在5 中，推导了h a n k e l 矩阵的新的快速三角分解算法，给出了数值算例 在6 中，给出了h a n k e l 阵的逆矩阵仍是h a n k e l 阵的充要条件 在7 中，给出了广义v a n d e r m o n d e 矩阵的逆矩阵。 在g 中，给出了mx , l o e w n e r 型矩阵和v a n d e r m o n d e r 型矩阵的左逆和乍i 逆、 表达式及快速算法 在9 中，介绍了非奇m 矩阵的定义，给出一一些关丁非奇m 矩阵的结论 关键词：t o e p l i t z 型蚌i 阵，h a n k e l 型矩阵，l o e w n e r ，艘矩阵 v a n d e r m o n d e r 型矩阵，快速算法 肚l | 、l k 人_ 硕士学位论文 t h ef a s ta i g o ri t h m so fs p e o i a i n a t ric e sa n dt h eirs t r u c t u r e a b s t r a c t t h ep a p e ri sc o n c e r n e dw i t hs o m em a t r i c e st h a ta r i s e i ne n g i n e e r i n g w eg i v e t h ed e f i n a t i o n so fh a n k e l t y p em a t r i xa n ds y m m e t r i c a lh a z e l t y p em a t r i x e x p l i c i t e x p r e s s i o n so ft o e p l i t z - t y p em a t r i x ，l o e w n e r - t y p em a t r i x ，h a n k e l - t y p em a t r i x ， s y m m e t r i c a lh a n k e l t y p e m a t r i xa r eo b t a i n e d w ea l s og i v ef a s ta l g o r i t h m sf o r s o l v i n gl i n e a re q u a t i o n s ，t r i a n g u l a rf a c t o r i z a t i o n ，i n v e r s em a t r i c e sa n ds oo n t h e p a p e ri sc o m p o s e do f t h ef o l l o w i n gm a i np a r t s ： i n 2 f i r s t l y ，w eg i v ee x p l i c i te x p r e s s i o n so f t o e p l i t z t y p em a t r i x ，l o e w n e r t y p e m a t r i x ，h a n k e l - t y p em a t r i xa n ds y m m e t r i c a lh a n k e l t y p em a t r i x ，t h e nw eg i v ea n 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 nf o rh a n k e lm a t r i x i n 3 ，af a s ta l g o r i t h mf o rs o l v i n gs y m m e t r i c a lh a n k e l t y p es y s t e m s i s o b t a i n e d ，a ls os o m en u m e r i c a te x a m p l e sa r eg i v e n i n 4 ，w eo b t a i naf a s ta l g o r i t h mf o rs o l v i n gl i n e a re q u a t i o n st h a tc o e f f i c i e n t m a t r i xi s l o e w n e r t y p e m a t r i x p l u s a n o t h e r l o e w n e r t y p em a t r i x ，w eg i v e a n u m e r i c a le x a m p l e i n 5 ，w er e s e a r c han e wl h s tt r i a n g u l a rf a c t o r i z a t i o na l g o r i t h mo fh a n k e lm a t r i x t h e nw eg i v ean u m e r i c a le x a m p l e i n 6 ，n 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 nf o rh a n k e lm a t r i xw i t hh a n k e li n v e r s e s r e v i s i t e da r eg i v e n i n 7 ，w eg i v ei n v e r s i o no fg e n e r a l i z e dv a n d e r m o n d em a t r i x i n 8 ，w eg i v et h ee x i s tc 【m d i t i o n s ，e x p l i c i te x p r e s s i o n sa n df a s ta l g o r i t h m so f l e f t i n v e r s ea n dr i g h ti n v e r s eofm h v a n d e r m o n d e - t y p em a t r i xa n dl o e w n e r - t y p e m a tr j x 曲北i 业大。、颁 “学位论文 i n 9 ，w ei n t r o d u c ed e f i n i t i o no fm - m a t r i x ，t h e nw eg i v es o m ec o n c l u s i o n s a b o u tm m a l ，r i x k e y w o r d s ：t o e p l i t z t y p em a t r i x ，h a n k e l t y p em a t r i x l o e w n e r - t y p e m a t r i x v a n d e r m o n d e - t y p em a t r i x ，l a s ta l g o r i t h m s | 1 曲北r 业人学硕士学位论文 1引言 一、研究特殊矩阵计算的意义 计算机科学的迅速发展，使得科学计算作为研究的有效手段，上升为与科学 理论和科学实验相并重的三大科学方法之。 近几十年，科学技术突飞猛进的发展，国防科技和国民经济建设c j 不断提出 许多大型和超大型的计算问题。这些问题要求计算机系统有更高的速度和更大的 信息存储量，从而促使计算机体系结构向巨型化和并行化方向发展。然而巨型机 和并行机的发展受限二j 。一个阎家的综合离力，作为一个发展中国家，我国的计算 机发展水平与先进国家比较还有相当的差距，并且不能指望人家把最先进的技术 和最好的计算机卖给我们。因此，如何利用现有的汁算机处理尽可能大型的问题 是。个很实际的课题。 科学技术和工程应用中需要进行人量的矩阵运算，而这些矩阵自身往往具备 一些特殊的结构及特殊的性质，这即是所谓的特殊矩阵。众所周知，对, 阶方阵 进行求逆、三角分解等，所需计算量为o ( n 3 ) 。而对一些特殊矩阵，我们_ u j 以根 据其特殊结构进行技巧性的处理，使矩阵的计算量降低个数量级，即由一般的 o ( n 3 ) 降低到o ( n 2 ) 或更低，当m 较大时，这大大的减少了运算量，所以这问题 拍研究具有理论意义和现实意义。 由于特殊矩阵在数值分析、优化理论、自动控制、数字信号处理、系统辨谚 、 谱分析、线性预测、最小：二乘估计、误差控制码及自回归滤波器设汁、1 ：程汁算 等领域中有重要的应用。为r 提岛矩阵汁算的效率，研究如何利用矩阵本身的结 构特征，得出计算特殊矩阵的快速算法，具有重要意义，所以对特殊矩阵的研究 直是被关注的热，7 i 。奖嘲的l i n e a ra l g e b r aa n di t sa p p l i c a t i o n s ) ) 、( s i a mm a t r i x a a a l y s i s a n di t s a p p l i c a t i o n s ) 、c m a t b e m a t i c c o m p u t a t i o a ) ) 期刊、德圜的c n n m e r m a t h 期刊和国内的汁算数学、数值词算和训算机应用、高等学校计t 算 数学学报等划刊上，发表了为数众多的相关论文、t o e p l i t z 矩阵、v a n d e r m o n d e 铜! 阵、非负矩阵、 i e r m i t e 短阵、作负矩阵、t o e p l i t z 型矩阵及与之密切斗f 1 天的 h a n k e l 矩阵中心与反t t ，心对称矩阵、h i l b e r t 矩阵、c a u c h y 型矩阵和l o e w n e r 型 矩阵等等，更是近年柬研究的热点。 二、有关求解特殊矩阵线性方程组的历史和研究现状 对于n 阶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 e v i n s i o n 在1 9 4 7 年对以t o e p l i t z 矩阵为系数的线性方程组的研究。 1 9 4 9 年，n l e v i n s i o n 首先给出了求解对称t o e p l i t z 方程组的快速算法；1 9 6 0 年，j d u r b i n 2 1 给出了有关h e r m i m 型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 年e h b a r e i s s 川通过构造一组同解的方程组推出了求解t o e p l i t z 方程 缉的另外一种快速算法。 1 9 7 3 年，h a k a i k e ”给出r 求解分块t o e p l i t z 方程组的快速算法。 1 9 8 6 年，o o h b e r g 、k a i l a t h 、k o l t r a c h t 6 1 等人给出了求t o e p l i t z 型方程组的 快速算法。 以上各算法都是求月阶t o e p l i t z 方阵的线性方程组的算法运算量均为 o ( n ! ) 。 l o e w n e r 矩阵是由k l o e w n e r i7 1 首先于1 9 3 4 年提出的。但是，在以后的研究 中有关l o e w n e r 矩阵的文献直很少。 1 9 8 4 年，z v a v r i n f s l 给出了l o e w n e r 矩阵求逆的快速算法，依此 叮得解 l o e w n e r 方程组的快迷算法。 1 9 9 5 一1 9 9 6 年，kr o s t 和| zv a v r i n 4 川给出了求l o e w n e r v a n d e r m o n d e 矩阵 为系数阵的方程组的快速算法。， 但是求解m n l o e w n e r 矩阵为系数阵的线性方程组的研究未见。 天于v a n d e n n o n d e 矩阵的研究，从二十世纪5 0 年代术至今，直受到人们 的理视。人们把v a n d e r m o n d e 矩阵从不刚角度推广，得到渚如v m 3 d e r m o n d ej r d j ；i ! p q 北工业大学硕十学位论文 阵、v a n d e r m o n d e 类矩阵、合流v a n d e r m o n d e 矩阵等等一系列重要结果。 1 9 6 6 年，j nl y n e s s 和c b m o l e r i l i ；1 9 7 0 年，a b j o r c k 和v p e r e y r a d 旧等 人分别给出了求解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 a r d 1 3 1 ；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 类方程 组的快速求解算法。 但是，以上算法都是针对n 阶v a n d e r m o n d e 方阵的，未见m nv a n d e r m o n d e 长方阵的。 有关h a n k e l 方程组阶快速算法的研究：1 9 8 6 年，g o h b e r g 、k a i l a t h 、k o l t r a c h t 等人分别给出了求解h a n k e l 方程组的快速算法。 1 9 6 5 年t r e n c h 、1 9 6 8 年b e r l e k a m p ，1 9 7 4 年r i s s a n e n 、1 9 8 3 年g r a g g 和 l i n d q u i s t 、1 9 8 4 年h e i n i n g 和r o s t 分别给出了h a n k e l 矩阵的逆矩阵的o ( n ! ) 阶 快速三角分解算法，依此町得t i m l k e l 方程组的快速算法。 三、本文的研究内容及安排 综上所述，对于特殊矩阵的的研究，目前主要是对t o e p l i t z 型矩阵、l o e w n e r 型矩阵、v a n d e r m o n d e ，魁矩阵、h a n k e l 矩阵进行快速三角分解以及解以卜述女l 嘴j 为系数阵的线性方程组的快速算法。 本文在2 中，给出一些特殊类型矩阵的显式表示。在3 中，给出了求解对 称h a n k e l 型方程组的快速算浊。在4t j ，给出了求解系数矩阵为对称l o e w n e r ，弘矩阵之和的线性方程组的快速算法。在5 中，给出了h a n k e i 矩阵的快速i 三角 分解。在6 中，给m 了h a n k e l 阵的逆矩阵仍是h a n k e l 阵的充要条件。在7t h 给出了广义v a n d e r m o n d e 矩阼的逆矩阵。在8 中，给出了肌 l o e w n e r 型矩阵 和v a n d e r m o n d e r 型矩阵的与：逆和右逆。在9 中，给出了非奇m 矩阵的结沦。 些坚! ：些望堡堂焦堡兰 2 一些特殊类型矩阵的显式表示 有关专著卜一般只给出了备“型”矩阵的定义，但是未给出其显示表达式为 了便于计算和应用，本节给出了一些特殊类型矩阵的显示表达式 一、t o e p li t z 型矩阵的显式表示 通常的t o e p l i t z 矩阵t = ( 善，) ? 。具有如下的位移结构 t z t z 7 = = o 。，f l ，f 一。+ 1 ) 7 p j - b e l ( o ，l ，f 。一) 其f “。表示第f 个分量为1 其余分量为0 的”维列向量，z = ( p ：，。3 一，p 。，0 ) 表 示以阶移位矩阵利用位移结构，进一步定义更广的一- 一类矩阵 定义2 1 若”阶方阵r 满足 l z z t z 7 = p “q 删1( 2 ，1 ) i = l 其叶i ，是正整数，而 p ”2 ( p ( 1 ) ，p 。( 2 ) ，p ( ) ) 7 ，q 1 = ( q n ( 1 ) ，可( ( 2 ) ，q ( j ( 月) ) 1 ( f ：1 ，2 ，) 则称t 为t o e p l i t z 型矩阵 t o e p l i t z 型矩阵丁有如i 、的显式表达式 定理2 。1 由式( 2 1 ) 定义的f o e p l i t z 型矩阵丁可以显示地表示为 ， r = 忙l p “1 ( 1 ) g ( 1 ) g ，( 2 ) g ( ( 门) p “( 2 )p “( 1 ) i 矿7 ，( 1 ) g ( ，( 月一1 ) p “1 ( n ) p ( n 1 ) p ”( i ) q ( 1 ) ( 2 2 ) 即t o e p l i t z 型矩阵丁 可以表示为若f 二个f 三角t o e p l i t z 矩阵和上三角1 b e p i i l z 矩 阵的乘积之和 证明 给式( 2 1 ) 分5 j i j 左乘矩阵z ，z2 ，z 一和右乘矩阵 z r , ( z ) ! ，( z 。) ”i ， 注意到移位矩阵z 满足z ”：0 ，得 n 北工业大硕士学位论文 z t z 。一z ! t ( z 2 、。 动( z g ) t z ! r ( z ：) 。一z j t ( z ，) t ：圭z ：p ( z ! q m ) t 。r 留”) t z ”r ( z ”) 1 = 窆z ”1 p 留”1 9 ) t i - t 将式( 2 1 ) 和上述诸式相加，得 r ：壹矿勿c n + 矿一，( z “矿，) t 】 1 q ( 1 ) 1 ：杰k ，印，z “矿，1 ( 御? ) t p 4 ( 1 ) 一亡ip 。( 2 ) 一厶l p 1 ( 1 ) f z “q p “( h ) p 气h 一1 ) p ) t m q 1 ( 1 ) ( 2 ) 矿( 1 ) 二、l o e l l n e r 型矩阵的显式表示 通常的l o e w n e r 矩阵有如下定义 q ( n ) q 2 ( h 一1 ) ( 1 ) 定义2 2 给定四组数o f ，3 ，孝，叩，( ，= 】川2 一，n ) ，且要求 口，卢，( f ，= 1 , 2 ， ) 称矩阵 五= l 为l o e w n e r 矩阵 容易验证，l o e w n e r 矩阵满足 d i a g ( a l 一) 三一l d i a g ( # 一，。) = g 一，己r ( i ，1 ) 一( 1 ，i ) 。0 一，口。) 帆i 匕 、i k 、学硕十学位论文 进一步有如卜- 定义 定义2 3 若月阶方阵l = ( f 。) 麓，满足 ， d i a g ( c f i ，口，口。江一l d i a g ( f l , ，腹，肛，) = p q “丌 ( 23 ) v = i 其中f 是正整数，而 p 5 1 = ( p 5 ( 1 ) ，一，p 。( n ) ) 。，q ”= ( g 5 ( 1 ) ，口。1 ( h ) ) ( j = 1 , 2 ，一，) 则称l 为l o e w n e r 型矩阵 定理2 2 满足式( 2 3 ) 的l o e w n e r 型矩阵l 可表示为 纠，j 。= | = 妻( 絮铲f ：。 眨。， 证明由式( 2 3 ) ，得 整理即得式( 2 4 ) ，。= p 。( 耐。1 ( ) 三、h a n k el 矩阵的充要条件 通常的h a n k e l 矩阵有如下定义 定义2 4 形如 h = 叩l7 7 2 玎2玑 仉叩。+ 的对称矩阵称为h a n k e l 矩阵 定理2 3 矩阵日是h a n k e l 矩阵的充要条件是 z h h z l = p p j p 】p 其中p = ( p i ，p ! ，一，p 。) 1 。足n 维步l j f 甸量 巩 叩肿1 ： 町2 n 一 证毕 ( 2 ，5 ) r 2 6 1 证明先汪必要1 阽设h 是如式( 2 5 ) 的h a n k e l 矩阵，则易验证口满足 z h h z l = ( o ，7 l ，一，7 7 。1 ) 1p j e l ( o ，叩i ，- ，叩。一。) 1 i 叫r ：业大学硕士学位论文 只要取p = ( o ，7 ，r l 。) 即可 再证充分性设 h = ( h ，。l = h 1 ih 1 2 一h l ， h ! lh 2 2 - h 2 h 。ih 。2 一。 把z ，z 1 ，日和p = ( n ，p 2 ，j ! ，。) 7 代入式( 2 6 ) ，得 0 一h l lh i2 h | | h 12 一h 2 1h i 3 一h 2 2 h 2 1h 2 2 一h 3 lh 2 3 一h 3 2 l h 。uh 一，z 一九，h 一，一吃z 比较上边矩阵的元素，得 一向1 。一1 h 1 。一h 2 。 h 2 ，h 。一 h i 女= p h ( k = 1 ，2 ，n 一1 ) 0 一p 2 一p 3 p，0 0 p 3 00 p 。0 0 h l ，= h 2 ，h 一一h h ，2 = h j l ( j = 1 , 2 ，h ) p ， 0 0 ： 0 曩。= h 。1 = = h 。( f = 1 , 2 ， ) 敞日是h a n k e l 矩阵证毕 定理2 4 矩阵h 是h a n k e l 矩阵的充要条件是 z 7 h 一脚= q e t e q ( 2 7 ) - t t ：c t q = ( g l ，9 1 ，q j l l 是跑维列向量 证明类似于定理2 3 从定理2 3 的证明过程可以看出，满足式( 2 6 ) 的h a n k e t 矩阵口的次对角线 以上的元素由，2 ，p - ，p 。1 1 侄一确定；同样的满足式( 2 7 ) 的h a n k e l 矩阵h 的次对 角线以卜的冗素由q l ，q 二，q 。唯一确定 四、h a n k e l 型矩阵的显式表示 根据定义2 1 的j 出发，我例t l j 以定义如下的h a n k e l 型矩阵 定义2 5 若n 阶方阵h 满足 h z h z = p m q 其中，是正整数，而 p 。= ( p 2 1 ( 1 ) ，一，p 。( 门) ) 1 ， 叮“= ( g n ( 1 ) ，- ，叮( 托) ) ( f = l ，2 ，一，) 则称口为h a n k e l 型矩阵 h a n k e l 型矩阵日有如i ：的湿式表达式 定理2 5 满足式( 2 - 8 ) 的h a n k e l 型矩阵日可以表示为 h = p ( n ( 1 ) q o ) ( 1 ) g ( 2 ) q u ) ( n ) ：( 2 ) ：。卜：矿” 矗。) ( n - ”o m 舢谝 f 28 1 ( 2 9 ) 即h a n k e l 型矩阵日可以表示为若干个下三角t o e p l i t z 矩阵和次上三角h a n k e l 矩 阵的乘积之和 证明给式( 2 8 ) 分别左乘及右乘矩阵z ，z 2 ，一，z ”。，并注意到矩阵z 满足 z “= d ，得 z h z z2 h z 2 = 勿“孽“汀z i = 1 ， z2 h z ! 一z 3 h z 3 = z 2 p o ) z 2 j = l ， z ”1 h z ”1 一z ”脚k z ”1 p z ” f _ 】 将式( 2 8 ) 和上述诸式相加，得 h = 窆k 留十勿q 7 z + + z ”。p “】叮“1 t z “。 忙i 譬“7 ：圭涮“，州一“_ ”。 舶北工业人学硕士学位论文 p 7 1 ( 1 ) ：圭 p e ：( 2 ) p q 1 ) p 1 ( ) p ( 一1 ) q ( 2 ) 忪_ _ ；j ( 2 ) 一 矿协) ， p ( 1 ) 眇1 ( n ) 五、对称h a n k ei 型矩阵的显式表示 根据定理2 3 和2 4 我们i i - 以定义不同于h a n k e l 型矩阵的另一类矩阵 定义2 6 若 阶对称矩阵h 满足 证毕 ， z h h z l = ( q “1 - q ”p “1 ) ( 2 1 0 ) i = j 其中，为正整数，而 p “= ( p ( 1 ) ，p 气月) ) 7 q 。= ( ( 1 ) ，t ，q ( 月) ) 7 ( i = 1 , 2 ，f ) 则称日为对称h a n k e l 型矩阵 对称h a n k e l 型矩阵的显示表示如下 定理2 6 满足式( 2 1 0 ) 的对称h a n k e l 型矩阵h = ( 。) 0 可以表示为 h = + 囊：l h 。ih 。! h ，f 1 ： ： h 。 q o l ( 1 ) q ”( 2 ) q 气1 ) 证明式( 2l o ) 片：乘z ，并利用z 7 z = j 。一e n p ! ，得 j 二是 q ( a ( n ) q 一1 ) qc o ( 1 ) ( ，。一p 。p j ) h zr h z 7 = ( z 1 p q “。一z q p 7 ) = l h = 8 - ( 自， ，t 。) + z 7 h z + ( z i p q 1 一z 7 qe p 邮) f = i ( 21 1 ) o ) 胛 (p) ) 2 月 吖吖o p p 鹕北i 一业大学硕t 学位论文 e 式分别左乘和右乘( z 1 ) 2 ( i = 1 , 2 ，h 一1 ) ，得 z t h z l = ( z 1 ) ! h i z l ) 2 + 窆l z l ) ! p g 7 2 1 。一( z 1 1 ) 2 口p 7 z 】 + e 。 ( 0 h 。，九h ) ( z 7 ) ”2 h ( z 7 ) ”2 = ( z 7 ) ”“n ( z 7 ) ” + ( z ，) 川p 窜r ( z 一) 一一( z t ) 川鼋j p 1r ( z - ) 一z + p ( o ，o ，矗) ( z 1 ) ”1 h ( z 尸= ( r h ( z 7 ) “ + 圭 ( z - ) ”p g t ( z - ) 一一( zr ) 一q ，r ( z t ) 一】 注意到( z 1 ) “= 0 ，则有 h = ( z 7 p “，( z 。) p + i ，：l + h h 。2 囊，i ； h h 。2 一h 。 矿1 ( 2 ) p ( ”) o ( z 1 ) “p ，o 妇，勿，z “g ) ” 矿1 ( ”) o l v q 2 1 ( 1 ) q ( o ( 2 ) - f |g ( 。( 1 ) 且 向 哆，： h 。1 ! h 。lh nh 。， g ( n ) 矿( ”一1 ) 证毕 显然，取，= l ，p 。1 = p ，矿= p 1 ，或者取f _ 1 ，g 1 = q ，p ”= e 。，则满 足式( 2 1 0 ) 的矩阵口为h a n k e l 矩阵可见对称h a n k e l 型矩阵是更广的类矩l 砖： f ) 曲，i kt 业大学硕士学位论文 3求解对称h a n k el 型方程组的快速算法 在2 中我们定义了一类新的矩阵，即对称h a n k e l 型矩阵本节我们推导 求解对称h a n k e l 型线性方程组的快速算法在推导过程中，要用到如卜- 的g i 理 引理3 i “”给定线性方，| ：7 2 f t a x = f ，a 7 y = g ，其中 x = g ( 1 ) ，x q l ，x o ) ) 7 ，f = ( 厂( 1 l ( 2 l ，。厂如) ) 7 ，g = ( g ( 1 ) ，g ( 2 ) ，g ) ) 1 设 ：0 c ( 1 ) ，( 七) ) 1 ，g 。= ( g ( 1 ) ，一，g ( ) ) 1 ，又设x 。= g 。( 1 ) ，“忙) ) 1 ， y 。= ( ) ，。( 1 ) ，y 。( 女) ) 1 ，比。= ( “。( 1 ) ，“。( 女) ) 。，叱= ( p 。( 1 ) ，- ，v 。( t ) ) 7 分别是线 性方程组4 = 以，州t n = g 。，a 。l f 。= p ，a z v 。= p 的解向量，这里p 是第k 个分量为1 其余分景为0 的k 维列向量若4 = ( “。 。的各阶顺序主予阵 a 。( k = 1 , 2 ，n ) 均可逆，则 x 。= x 。k - 1 + 盯。“。，。= ，了k + r 。r 。 其中吼= l 厂( 尼) 一甜。h 一，( f ) ，f 。= g ( 女) 一口。y 。( f ) 一、快速算法的理论推导 考虑求解线性方程组 崩k = s ( 3 1 、 其中h 是如2 中式( 2lo ) 所定义的九阶对称h a n k e l 型矩阵， x = 0 ( 1 l x ( 2 l ，x ( ”) ) r ，f = ( r 0 ) , s 。( 2 卜，o ) ) t 殴对称h a n k e l 型矩阵h = ( 。) k 的t 阶顺序 子阵日。均怍奇异， x 。= ( k ( 1 l h ( 2 ) ，n ) ) ”是线性方程组 雌毗l 业尺学硕十学位论文 日t 屯= ( k = 1 , 2 ，, )( 3 2 ) 的解向量，其中 = ( 厂( 1 ) ，厂( 2 ) ，厂( t ) ) 1 又设n = ( d ( 1 ) ，口( 1 ( 2 ) ，d ( f ( 丘) ) 7 雕”= ( b “( 1 ) ，b “( 2 ) ，b l , i ( 女) ) 。分别是线性方程组 h 。n ：7 i = p ：“，h 。6 ；”= 口：( 33 ) 的解向量，其中p = ( p 。1 ( 1 ) ，一p ( t ) ) 1 ，g ? = ( g ( 1 ) ，g ( ( 七) ) 1 山式( 2 1 0 ) 得 ， 五h 。一吼z ? = ( 7 辟i 其中z t 是七阶移位矩阵【一式两边分别左乘及右乘日i ，得 ， 嘶l 乙一z z h k l = ( 跏一 )( 34 ) 忙l 式( 3 4 ) 右乘p r ，并注意到z 。e p = 0 ，得 ， 一刃= ( 掣( ) 一日执t ) )( 35 ) 对方程组( 3 3 ) 分别应用引理3 1 ，得 其l f i n = 亭1 + ：。，影卜k b s ， 一i k - i = ( 七) 一口冰) ，v 净g ( 七) 一蝎( 力 ( 3 7 ) ，= l t = i 比较式( 3 7 ) 的最后一个分量，得 “：”0 ) = 踟。( ) ，6 l n 坼) = v 踟。( )( 3 8 ) 将式( 3 6 ) ，( 38 ) 代入式( 35 ) ，得 z 。t h * = 薹；“tc t ，( 卢；” 6 孑 一v ：“ “乎 c ，。，。h 。= “。( 女) l 卢；”i 。：1l v ：“j “：ll( 3 9 ) j i 、j uu j 比较式( 3 ，9 ) 的第，个分量，得 曲，i l 业k 学硕士学位沦文 “。( j + 1 ) = “。( t ) ( 硝础( ) 一v o 。0 ) ( 朋( ，= 1 “2 ，k 一1 ) ( 3 1 0 ) 扛l 尚需计算( 1 ) 和“。( 七) ，由口。“。= f ，得 由式( 3 1 1 ) 解得 h k i “( 1 ) + h k 2 u i ( 2 ) + + 矗船“k ( k ) = 1 将式( 3 1 3 ) 4 弋x 式( 3 1 2 ) 解得 = 一百1 酚k 州) 私一缸如= - 再将式( 3 1 0 ) 代入式( 3 1 4 ) 解得 法 ( k ) 剁瓦h i ：p 糍蛳 ( 3 1 1 ) ( 31 2 ) f 3 1 3 1 ( 3 1 4 ) ( 3 1 5 ) 结台式( 3 7 ) ，( 3 9 ) ，( 3 1 1 ) ，( 3 1 3 ) ，( 3 i 5 ) 得求对称h a n k e l 型方程组的如下快速算 算法：( 求解对称h a n k ei 型方程组) 日f 气1 ) ：掣，6 j 1 1 ) ：学叫( 1 ) ：( 1 ) ：掣( f = 1 z 力 n 1 1向l |力1 】力1 1 t i 一l = ( ) 一h z 烈mv k “= 一( ) 一a “j is ) ( ，) ( 扛u ，) 卜j 户f r ；”( ) = ；”6 ；0 ( j ) 一v ：”“：! 。( ) ( f = 1 , 2 ，f ；j = 1 , 2 ，- - ，k 1 ) 。( 女) ：士 ，l “ 州川渺) “) ( h ，2 ，) 州【1 ) = 一百1 矾k ，) ( 一 一 。一 ， j j z j q 此i 业大学硕t 学位论文 盯：“= 4 兰0 1 + ，z ：。“m ，6 ：“= 6 ：0 三 + v ：“t 盯。= 厂c t ，一：k 薯- in 。x 。，c ，x 。= 工占1 + a 。h 。 盯。= 厂( 女) 一 “x 。，( ，) ， x 。= “# 1l + a 。h 。 该算法所需要乘除法运算次数为丁5 1 + 3 疗2 + 翌笋n 一( 4 1 + 2 ) ，加减法运算次 数为5 1 2 + 3 2 + 莩州4 ) 二、数值算例 我们找了一些对称h a n k e l 型矩阵口= ( ，戌，= l 在微机( c p u2 6 0 g ，内存5 1 2 m b ) 上用m a t l a b 语言编程计算对称h a n k e t 型方程组h x = f ，其中向量 ，= ( i 厂( 1 ) ，( 2 ) ，( h ) ) 1 的元素取为f ( o = h 。( 待1 ，2 ，n ) ，此时对称 = 1 h a n k e l 型方程组h x = f 的解为x 。= ( 1 ，i ，1 ) 7 分别采用本文的快速算法及 g a u s s 消元法求解对称h a n k e l 型方程组h x = f ，时间为秒、误差用l i h r 一州：来 度最部分算例如下： 厂11、r 例3 1 取f 1 ，p = ( ) ，1 专，、 ，口= ( 1 ，o ，- ，o ) 7 此时日为h i l b e r t lz月一i ， 矩阵计算误差及所需时l 旬见表3 1 表3 1 快速算法g a u s s 消元法 【阶数误差时悯误差时间 53 1 4 0 e 1 6 0 9 5 4 3 e 一130 1 026 7 3 e 一1 4 o 6 9 7 2 e 0 5o 0 1 2 1 5l5 13 c 1 l02 ，9 1 6 e 一0 l0 1 3 8 2 03 0 2 2 e 1 003 7 8 60 7 8 1 2 56 9 1 8 e ，0 9 o 8 9 6 1o 9 8 1 3 045 15 e 0 6 o 3 1 2 51 3 6 8 曲北e 业大学硕i 学位论文 3 51 2 0 9 e 0 6o5 9 0 5 1 9 1 2 4 025 5 2 e 0 5o7 4 9 62 8 6 3 侈一。2 取，= - ，p = ( t + 旱，+ 罢，- ，- + 吾 7 ，碍= c t ，。，一，。，1 止c h ? h 为通 常的h a n k e l 矩阵计算误差及所需时间见表3 2 袁3 ，2 快速算法g a u s s 消元法 阶数 误差州。间误差时间 542 0 9 e 一1 4o7 6 7 5 e 一13o 1 08 3 9 3 e 一1 2o9 15 3 e - l lo 0 l l 1 551 1 2 e 0 8o6 5 9 6 e 0 7o 1 4 8 2 08 5 2 0 e 0 7o5 2 3 4 e 一0 40 7 9 5 2 52 4 3 0 e 0 4o3 5 9 6 e 0 110 0 l 3 053 6 9 e 0 4 o 1 2 2 01 4 6 7 3 5 2 。3 0 4 e 0 3o8 6 1 4 2 0 6 4 4 0 l1 4 7 e 0 20 1 5 9 62 9 5 2 4 52 0 3 1 e 0 2o 4 3 2 5 30 1 2 5 03 3l l e 0 209 6 4 54 3 1 6 例3 3 取，= 1 ，p = ( 1 ，圭，一，去) 1 ，q = ( 1 ，o ，一1 ) 此时h 为对称h 犁k e l 型矩阵计算误差及所需时间见表3 3 表3 3 快速赞：法g a u s s 消冗法 阶数 误差时问误差时问 51 1 5 5 e 1 405 1 6 1 e 13o 1 097 8 2 e - 1 1o9 6 1 6 e 1 lo 0 1 9 15 1 5 8 1e 一11 0 73 8 6 e 一0 7o 1 5 6 2 02 】9 3 e 1 0o6 9 4 6 e 0 40 6 0 2 2 5 3 9 8 6 e 一0 9o 4 ，1 9 6 e 0 11 1 0 1 i ) l i ，i tr 业大学硕十学位论文 3 09 5 0 3 e 0 6o2 1 2 l1 9 6 l 3 52 7 l l e 0 6o6 2 9 42 9 4 9 4 05 5 8 8 e 0 403 6 7 53 0 2 8 | 4 555 8 8 e 0 4o8 9 4 83 | 8 1 3 5 02 1 0 7 e 一0 3o1 0 0 i e 0 34 9 4 2 倒s 4 取，= z ，p = ( + ；，+ 吾，一，+ 吾) 1 1 ，p ：= ( ；，圭，一，去 7 口l = ( 1 ，l ，1 ) 7 ，q 2 = ( 1 + o 1 2 + 0 1 ，”+ o 1 ) 7 此时h 为对称h a n k e l 型矩阵计 算误差及所需时间见表3 4 表3 4 快速算法g a u s s 消元法 阶数 误差时间误差时问 59 5 9 l e 0 2o4 5 9 6 e 一1 3o 1 01 2 9 2 e 一0 107 9 1 6 e 1 1o 1 2 3 1 51 3 2 7 c 一0 lo8 1 2 9 e 一0 7o 2 0 1 2 0l2 9 7 e 一0 1o1 2 7 3 e 0 3 0 4 7 3 2 51 2 5 3 e 0 lo9 3 7