Hankel矩阵和Vandermonde矩阵之逆的新矩阵表示式及快速算法

Hankel矩阵和Vandermonde矩阵之逆的新矩阵 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示式及快速算法 Han kel 矩阵和 Van dermon de 矩阵之逆的新矩阵 表示式及快速算法 陆 全 , 徐 仲 , 叶正麟 ()西北工业大学 理学院 , 陕西 西安 710072 摘 要 :利用线性方程组是否有解给出 Hankel 矩阵 、Vander mo nde 矩阵可逆的条件及求逆的递推 公式 ,并给出了逆矩阵新的表示式. 表明 Hankel 矩阵 、Vander mo nde 矩阵的逆矩阵可以表示为一些 2 ( ) 特殊矩阵的乘积之和 ,并以 Hankel 矩阵为例 ,得到了求逆的快速算法 ,所需计算量为 O n ,一般 3 ) ( n 阶矩阵求逆的计算量为 O n. 关键词 : Hankel 矩阵 ; Vander mo nde 矩阵 ; 对称循环矩阵 ; 逆矩阵 ; 快速算法 中图分类号 : O151 . 21 ; O241 . 6 文献标识码 : A Ne w expressions an d fa st al gorithms f or inverse of Han kel matrix an d Van dermon de matrix L U Q uan , XU Zho ng , YE Zheng2lin ( ) College of Science , No rt hwester n Polytechnical U niversit y , Xi′an 710072 , Shaanxi , ChinaAbstract : ( ) ( ) The Hankel Vander mo nde mat rix is invertible if systems of Hankel Vander mo nde equatio ns ( ) are solvable . Also , t he inversio n of a Hankel Vander mo ndemat rix can be denoted as a sum of p ro duct s of particular mat rices. Especially , a f ast algo rit hm fo r t he inversio n of a Hankel mat rix 2 3 ( ) ( ( ) ) wit h O n operatio ns rat her t han O n , as required by standard mat rix inversio n met ho dsis derived. Key words : Hankel mat rix ; Vander mo nde mat rix ; symmet ric circulate mat rix ; inversio n mat rix ; f ast algo rit hm M R Subject cla ssif icat ion : 15A09 n(ξ) Hankel 矩阵 、Vander mo nde 矩阵在数字信号处 密切相关. 著名的 Hilbert 矩阵 H=j - i i , j = 1 1 1 n 理 、数值 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 、自动控制等领域中经常用到. 例 1就是特殊的 Hankel 矩阵. 常见的对 i + j - 1 i , j = 1 如 ,利用最小二乘法求数据的多项式拟合曲线问题 称循环矩阵也是特殊的 Hankel 矩阵. 文献 [ 2 , 5 ] 可转化为求解以 Hankel 矩阵为系数矩阵的线性方 介绍了 Hankel 矩阵 、Vander mo nde 矩阵求逆 、三角分 ( ) d x t 程组. 再如 : 线性系统的状态空间方程 =d t解及 Hankel 方程组的求解等一些快速算法 ; 文献 T ( ) ( ) ( ) ( ) A x t + u t b , y t = c x t 简化为能控规范型 6 给出了基于 Loew ner 矩阵求逆公式的 Hankel 线 2 或能观规范型方程所做的线性变换涉及 Hankel 矩 ( ) 性系统的快速解法 , 计算复杂性为 O n ; 文献[ 7 ] 阵. 在系统辨识中 , 规范型描述有利于减少辨识系数 介绍了 Hankel 和 Toeplitz 算子的广义逆. 本文利用 2 [ 1 ] Hankel 矩阵 、Vander mo nde 矩阵的新关系式得到了 ( ) 的数量 由 n+ 2 n 减少到 2 n . Hankel 矩阵 n 如下结果 :通过线性方程组是否有解给出 Hankel 矩η) (H = 与 重 要 的 Toeplitz 矩 阵 T = i + j - 1 j = i , 1 收稿日期 :2004204228 () ()基金项目 :国家自然科学基金资助项目 10071060;陕西省自然科学基金资助项目 2004CS110002 () 作者简介 :陆全 1957 —,女 ,浙江吴兴人 ,西北工业大学副教授. yy y 阵 、Vander mo nde 矩阵可逆的条件及求逆的递推公0 - x - x 1 2 n1 n - 1 式 ,并给出逆矩阵新的表示式 , 表明 Hankel 矩阵的 yΨ Ψ y ω ω 2 1( ). 6 逆矩阵可以表示为对称循环矩阵与上三角 Toeplitz ω - x Ψ Ψ 1 矩阵的乘积之和 ,而 Vander mo nde 矩阵之逆可以表y y y n 1 n - 1 0示为 对 角 阵 、Vander mo nde 矩 阵 的 转 置 与 上 三 角 ( ) ( ) 证明 ?由 2式及 Hx = e, Hy = f , 得1 Toeplitz 矩阵的乘积. 得到 Hankel 矩阵之逆的快速 T T T T T KH = H K + ef - f e= H [ K + xf - ye. 1 1 1 2 ( ) 算法 , 所需计算量为 O n , 而一般 n 阶矩阵求逆 于是 3 ( ) 的计算量为 O n .Tj Tj - 1 T T ( ) ( ) KH = KH [ K + xf - ye] = 1 T j T 1 基本引理与主要结论 = H [ K + xf - ye] , 1 j = 0 , 1 , , n - 1 . n 阶 Hankel 矩阵 H , n 阶 Vander mo nde 矩阵 V 上式两边右乘 x , 得 分别是形如 TjT j T ( ) ( )Ke= H [ K + xf - ye] x , 7 n i - 1 n1 1 (η) α) (H = , V = ( )j + j - 1 j = 1 1i , j i , j = 1 TTj - ye] x , 并注意到 令 z = K + xf 1 j 的方阵. TK e= e, j = 1 , , n - 1 . j j +1 引理 1 n 阶 Hankel 矩阵 H 满足关系式( ) 由 7式 , 得 T T T ()KH - H K = ef - f e , 2 1 1 TjTj - 1 ( ) ) ( Hz= Ke= Ke= j 1 2 其中 = e, j = 0 , 1 , , n - 1 . j +1 00 1 0 ( ) 令 X = z, z, , z , 则 0 1 n - 1 ηη- n +1 1 0 ω ω( ) ( ) HX = Hz, Hz, , Hz= e, e, , e= I,0 1 n - 11 2 nn ηη - , f = K =,n +2 2 故 H 可逆. ω ω 1 - 1 ( ) ( ) ?对 2式左乘及右乘 H , 并利用 Hx =1 0 0 ηη- 2 n - 1 n - 1 e, Hy = f , 得1 T ( ) ( )e= 1 , 0 , , 0. 3 1 - 1 T - 1- 1 - 1 TH K- KH = H H -ef 1 引理 2 n 阶 Vander mo ude 矩阵 V 满足关系式- 1- 1 T T T H f e H = xy - yx .1T VD - ZV = ef ,1 1 - 1 ( ) 记 H = v, v, , v, 上式右乘 e, 并注意到 1 2 n j 其中 T ( ) K e= ej = 1 , , n - 1, 得j +1 j 0 α1/ 1 v- Kv= y x - x y. j +1 j j j ω 1 ω, D =, Z =- 1 = x , e又 v= H 1 1 ω ω α1/ n 于是1 0 T v= x , αα1 ( )1/ , , 1/ 4 f = . 1 n 1 v= Kv+ y x - x y , j = 1 , 2 , , n - 1 . j +1 j j j 定理 1 设 H 是 n 阶 Hankel 矩阵 , 线性方程组 T ( ) 即 5式成立. ( ) Hx = e, Hy = f 有解 x = x , x , , x , y = 1 1 2 n T ( ) ( ) ?由 5式得( ) ( ) y, y, , y , 其中 e, f 由 3式确定 , 则 1 2 n 1 v= x , v= Kx + yx - x y , 1 2 1 1 ( ) ?H 可逆 ;2 - 1 v= Kx + yKx - x Ky + y x - x y , 3 1 1 2 2 ( ) ( ?H 的逆矩阵 H 的列向量 vj = 1 , 2 , , j ) n 满足递推公式 n - 1 n - 2 n - 2 v= Kx + y Kx - x Ky + ( )v= x , 5 n 1 1 1 + y x - x y , n - 1 n - 1 v= Kv+ y x - x y , j = 1 , 2 , , n - 1 ; j +1 j j j - 1 于是( ) ?逆矩阵 H 有显式矩阵表示式 x x x y 1 y 12n11 y y n - 1 1 n - 1 Ψ Ψ x x ω ω 21ω ω- 1 n - 1 + ( )H = x , Kx , , Kx + ω y Ψ Ψ 1ω y 1 x x x 1 n1n - 1 1 ( ) 0 - x - x ?先求 Hankel 线性方程组 Hx = e, Hy = f 1 n - 11 的解向量 x , y. ω ωn - 1 ( )y , Ky , , Ky =设 H 的所有顺序主子阵均非奇异 , 则可采用 ω - x 1[ 1 ] Go hberg2Kailat h2Kolt racht 算法求解 Hankel 方程 0 组 Hx = e和 Hy = f . 1 x x x 1 yy 1 2 n( k) 1 n - 1 ( ) 设 H x = e , H y = f , 8k k 1 k k k ( ) kx Ψ Ψ x ω ω2 1其中 H 为 H 的 k 阶顺序主子阵 , e 和 f 分别为 e +k 1 k 1 ω yΨ Ψ 和 f 的前 k 个坐标组成的列向量. 1 x x x ( ) 1 n 1 n - 1 第一步求 8式的解向量 x, y:1 1 y y y 0 - x - x 1 2 n1 n - 1 1yΨ Ψ y 2 1ω ω μη( ) νη( ) ( ) ,= - u1,= - u1, u1= 1 2 1 1 3 1 1 η ,1 ω - x Ψ Ψ 1 1( ) ( ) x 1= , y1= 0 ; 1 1 y y y 0ηn 1 n - 1 1 ( ) 即 6式成立. ( ) 第二步求 8式的 2 维解向量 : 类似定理 1 的证明可得如下定理 :η - 2 1 ,= u2 2( ) 定理 2 ?设 V 是 n 阶 Vander mo nde 矩阵 , ηηη- η 2 13 1 则 V 可逆的充要条件是线性方程组 V u = e有解 ; 1 η 31 ( ) ( ) 其中 V , e由 1、3式确定 ; ,x= 1 2 2ηηη- η- 2 13 2 (ηη) y= - u; 2 n +1 1 2 ( ) ( ?V u = e有解 u = u, u,设线性方程组 1 1 2 T T ( ) 第 k + 1 步求 8式的 k + 1 维解向量 x, k +1 ) ( ) , u , 又设 x = x , x , , x 是线性方程组 n 1 2 n T ( ) yk = 2 , , n - 1: () ( V x = f 的解向量 , 其中 f 由4式确定 ,记 vj = k +1 1 1 j 对 k = 2 , , n - 1 , - 1 ) 1 ,2 , , n为 V 的第 j 个列向量 ,则有递推公式k k v= u , 1 μη( νη( ) ) = - u j ,= - u j , k k + j k k k + j +1 k ??j = 1 j = 1 v= Dv- x u , j = 2 , 3 , , n ;j j - 1 j - 1 1 u= ?k +1 ( ) ?设线性方程组 V u = e有解 u , 则 n 阶 1 νν (μμ ) μ -- + k - 1 k - 1 kk k Vander mo nde 矩阵 V 的逆矩阵表示式为 u k - 1 0- 1 u k V =(μμ ) - - - ,0k - 1 k {} u k 0n - 1αα0 1 1/ 1/ u 1 1 1 k n - 1u αα1 1/ 1/ 2 2 2 η( ) σ= - x j ,k k + j k ? - ?j = 1 ω k n - 1u τη( ) n ααηηj , 1 1/ 1/ = - - y n k n + k kn k + j k ?1 j = - 1 x x x 1 2 n - 1 y kx kω ω ω τx=+ u. k +1 k k +1 σ+ u, y= k k +1 k +1 0 ω ω x .2 0 最后得到 Hankel 线性方程组 Hx = e, Hy = f 的1 ω x 12 解向量 x = x, y = y. 以上过程共需 4 n- 5 次乘除 n n - 1 2 运算 , 4 n- 5 n - 4 次加减运算. - 1 2 求 Han kel 矩阵之逆矩阵的 ( ) ( ) ?再利用 5式求 Hankel 矩阵的逆阵 H 的 - 1 ( 列向量 v, , v由于 H 对称 , H 也对称 , 故只需 1 n 快速算法及计算复杂性 - 1 ) 求 H 的下三角元素.以 Hankel 矩阵为例 , 给出求逆的快速算法及计 T ( ) 算量. 由定理 1 可知 , 只要求得 Hankel 线性方程组 第一步求 v= v , , v :1 11 n1 ( ) Hx = e, Hy = f 的解 x , y , 即可由 5式递推求出 1 v = x , i = 1 , , n ; i1 i - 1 T H 的诸列. ) ( 第二步求 v= v , , v : 2 12 n2 n - 1 v = v + yx - x y ,i2 i +1 , 1 1 i 1 i 2 2 2 k = n- n 次乘除运算 , n- n 次加减运算. ?k = 1 i = 2 , , n ,- 1 22 可见求 H共需 5 n - n - 5 次乘除运算 , 5 n ; 2 T ( ) - 6 n - 4 次加减运算 , 计算复杂性为 O n, 一般 n) ( 第 n - 1 步求 v= v , , v : n - 1 1 , n - 1 n , n - 1 3 ( ) 阶矩阵求逆的计算复杂性为 O n.v = v + y x - x y , n - 2 i , n - 1 i +1 , n - 2 n - 2 i i 3 数值算例 i = n , n - 1 ; T ( ) 第 n 步求 v= v , , v : n 1 n n n 采用 Matlab 编程计算 ,数值实验的结果表明本 v = v + y x - x y .n n 1 , n - 1 n - 1 n n - 1 n 文所给的算法是有效的. 部分算例及计算误差如表 - 1 ( ) 因此 , 由 5式可递推求出 H 的诸列元素需 1 —3 . 3 表 1 计算结果 1 Ta b. 1 Result of computation 1 n 3 4 5 6 7 8 9 10 11 - 1 - 13 - 12 - 10 - 8 - 7 - 5 - 3 - 2 ‖H H - I ‖2. 772. 19 ×10 7. 12 ×10 8. 34 ×10 1. 37 ×10 7. 43 ×10 1. 96 ×10 1. 19 ×10 3. 89 ×10 F 时间 / s 0 0 0 0 0 0 0 . 01 0 . 01 0 . 01 ) η( 3 = 1/ i i = 1 , , 2 n - 1, Hilbert 矩阵 i 3表 2 计算结果 2 Ta b. 2 Result of computation 2 n 4 6 8 10 12 14 16 18 20 22 - 1 - 15 - 14 - 13 - 12 - 10 - 8 - 7 - 5 - 4 - 3‖H H - I ‖2. 54 ×10 4. 89 ×10 6. 90 ×10 9. 85 ×10 2. 81 ×10 1. 04 ×10 1. 27 ×10 2. 56 ×10 3. 04 ×10 6. 02 ×10 F 时间 / s 0 0 . 01 0 . 01 0 . 01 0 . 02 0 . 01 0 . 02 0 . 02 0 . 02 0 . 03 η)η( ) ( 3 = 1/ i n = 1 , , i,= - 1/ i i = n + 1 , , 2 n - 1 i i 3表 3 计算结果 3 Ta b. 3 Result of computation 3 n 4 6 8 10 12 14 16 18 20 22 - 1 - 16 - 14 - 13 - 12 - 10 - 9 - 7 - 6 - 4 - 3‖H H - I ‖8. 96 ×10 4. 51 ×10 3. 49 ×10 8. 02 ×10 2. 07 ×10 2. 14 ×10 4. 99 ×10 2. 82 ×10 7. 41 ×10 7. 01 ×10 F 时间 / s 0 0 0 . 01 0 . 01 0 . 02 0 . 02 0 . 02 0 . 02 0 . 03 0 . 03 η( )η( ) 3 = 1/ i i = 1 , , n,= 0 i = n + 1 , , 2 n - 1 i i Toeplitz mat ricesJ . Numerical Mat hematics , 1974 , 22 : 参考文献 :,366 . 3611 徐仲 , 张凯院 , 陆全. Toeplize 矩阵类的快速算法 M . 5 徐仲. 范德蒙矩阵类的快速算法M . 西安 :西北工业大 西安 :西北工业大学出版社 ,1999 . 学出版社 ,1997 . 2 Philli p s J L . The t riangular deco mpositio n of Hankel 6 Peter Kravan ja , Marc Van Barel . A fast Hankel solver mat rices J . Mat hematics of Co m p utatio n , 1971 , based o n an inversio n formula for Loewner mat rices J . () 25 115:599,602 . Linear Algebra and it s Applicatio ns , 1998 ,282 :275,295 . 3 Rissanen J . Al gorit hm for t riangular deco mpositio n of block 7 Victor M Adukov. Generalized inversio n of finite rank Hankel and Toeplitz mat rices wit h applicatio n to factoring Hankel and Toeplitz operators wit h ratio nal mat rix J . positive mat rix polyno mials J . Mat hematics of Linear Algebra and it s Applicatio ns , 1999 ,290 :119,134 . () Co mp utatio n , 1973 , 27 121:147,154 . 〔责任编辑 张惠民〕4 Rissanen J . Solutio n of linear e quatio ns wit h Hankel and