柯西矩阵的三角分解及应用.pdf

2 0 1 1 年 3月 高等 学校计 算数学 学报 第 3 3卷第 1期 柯西矩阵的三角分解及应用 李琳 袁修久 赵学军 ( 空军工程大学应用数学物理系， 西安 7 1 0 0 5 1 ) TRI ANG ULAR F ACToRI ZAT1 0N oF CA UCH Y M ATRI X AND I TS APPLI CATI oN L i L i n Y u a n Xi u j i u Z h a o Xu e j u n ( D e p a r t me n t o f A p p l i e d Ma t h e ma t i c s a n d P h y s i c s ， A i r F o r c e E n g i n e e r i n g U n i v e r s it y , X i ’a n 7 1 0 0 5 1 ) A bs t r ac t I n t h i s pa p e r ，a ne w me t ho d f o r t r i a ng u l a r f a c t o r i z a t i o n o f Ca uc h y ma t r i x i s pr o po s e d b y d e c o mpo s i t i ng t h e Ca u e h y ma t r i x a n d i t s i n v e r s e i n t o t he p r o du c t of s o me s pa r s e l o we r a n d u p pe r t r i a n g ul a r ma t r i c e s ． Thi s pr o vi de s a t he o r e t i c foun da t i on f o r f u r t h e r s t u dy i n g t he f a s t a l g or i t hm of t h e n ume r i c a l s o l u t i o n s o f l i n e a r e qu a t i o n s wi t h t he Ca uc h y ma t r i x as i t s c o e ffic i e n t mat r i x． Th e m e t h od do e s n o t d e pe n d o n t h e s e l e c t i o n o f t he p i v o t a nd i t s a r i t he m a t i c o pe r a t i o n s i s o( n 。

) wh i c h i s f e w e r t h a n t h e e x i s t i n g a l g o r i t h ms ． K e y wor ds Ca u c h y ma t r i x，s p a r s e up pe r t r i a n gu l a r ma t r i x， s pa r s e l o we r t r i a n— g u l a r m a t r i x， t r i a n gu l a r f a c t o r i z a t i on． AMS ( 2 0 0 0 )s u b 3 e c t c l a s s i fi c a t i o n s 1 5 A2 3 ， 6 5 F 0 5 中图法分类号O 2 4 1 ． 6 1 引 言 陕西省 自然科学基金 ( 2 0 0 6 A0 5 ) 资助； 陕西省电子信息系统综合集成重点实验基金资助 收稿 日期：2 0 0 8 — 0 2 0 9 高 等 学 校 计 算 数 学 学 报 矩阵分解具有非常重要的应用 ．例如 ，可以利用矩 阵的 L U 分解 回代求解线性方程 组 Ax=b ． 对于在有理函数的计算中经常遇到的以柯西矩阵为系数的线性方程组的求解 问题 ， 需要做柯西矩阵的三角分解． 在 [ 1 ] 中给出了求柯西矩阵逆矩阵的算法，[2 ] 是在 ⋯ 的基础上对求逆方程进一步修正， 得到一种精度更高的方法． [ 3 】 给出了具有位移结构的矩 阵部分旋转的高斯消元法．[ 4 】 【 5 ] 给出了有关柯西矩阵的分解 ， 但是数值解 的稳定性依赖 r主元 的选取．本文所给出的方法是通过左乘和右乘一些稀疏的下三角形矩阵和上三角 形矩阵，从而把柯西矩 阵分解为稀疏 的下三角和上三角矩阵之积，而求解 以这些稀疏矩 阵为系数 的线性方程组编程容易， 并且所需计算量为 o( n 。

) ，降低了运算量 ． 定义 1 给定数组 ， Y j ( J=1 ， 2 ⋯ ， n ) ， 且 X i ≠y j ( i ， J= 1 ， 2 ， ⋯ ， 礼 ) ， 称矩阵 c =( ) ㈩ 为柯 西 ( C a u c h y ) 矩 阵． 当 =J ， Y j=1 一J ( J=1 ， 2 ⋯ ， 礼 ) 时， C 就是通常的 H i l b e r t 矩阵． 2柯西矩阵 的三角分解 对于柯西矩阵有如下的三角分解定理 ． 定理 1 设式 ( 1 ) 的柯西矩阵 C满足 X i ≠x j ， Y i ≠Y j ， X i ≠y j ( i ， J=1 ， 2 ， ⋯ ， 他 ) ， 则 c 及 c 均可分解为一系列稀疏下三角矩阵和上三角矩 阵的乘积 C ： L1⋯Ln -1 D U n 一1¨ ． U 1 ， C ～= V l ⋯u 1 D 一 L 1⋯L 其中D d i a g ( ( x 1 一 Y 1 ) ， ( 2 一 y 2 ) ， ． 一 ( 一Y ) 一 ) ， L k=Di Mk ~ ) k ， Uk=D— k M—k D k 一 ( ： ， ． ． ．： 一 ， 压 =( I 一 1 ．．． ) ． 阶矩 阵 2 3 2 一 z 1 ) ( 咒 ／ ＼ 2 0 1 1 年 3月 高 等 学 校 计 算 数 学 学 报 9 3． 从而可得 l zn— Y 第二步对 Du 进行一系列初等列变换 记 ／ l一 1 u =f l D U U 1 一般地 ， 记 、1 f， 1 一 n／ ＼ ( 1 一Y 1 ) 0 0 0 0 。

V 22-一V i3 0 0 0 0 0 0 I k 一1 t ．1 1 1 ／ n -- Xk) 1 1一 2 0 ．x；~ --y 2 ． 2 一 i 型 量 = 生 2 i 二 曼 2( Y 2 -Y n J _I 3 --Y 3 j ( X 2 一Y 4 ) ( X 3 一Y 4 ) ( X 2 一 ! ， n ) ( 3 一 n ) n ( 一 4 ) 3 兀 ( X i -- y 4 ) 0 ／ I 一 1 f 一 ui l ． ＼ —Y n ／ I k — — 1 f 1 L＼ Y 一 知+1 1 Y 一 忆 1 Y1一 n 兀 ( 一Y ) ( X 4 - Y 4 ) I k — — 1 1 3 兀 ( t -y 4 ) 兀 ( 一 ) = 2 兀 ( X l --y ) t= 2 } ⋯一1 1 ．． J 1 ／ ( 3 ) 2— 4 0 二 一 2— 2 一 2— 3 0 二 一 2 —2 一 、lJ＼l●，●●J／ 9 4． 李琳等： 柯西矩阵的三角分解及应用 第 1期 依次右乘 Du ，最后得 DUU~ - U 可得 u =u1 u ⋯ u ， 其中 卜 C=L 1 ⋯ L n - 1 DUn 一 1 ⋯ U1 ( 6 ) ( 5 ) 其中 L ， u ( =1 ， 2 ， ⋯ ， n一1 )由式 ( 3 ) 和 ( 5 ) 给出，均为稀疏的下、上三角矩阵． 从式 ( 6 ) 可得 C 一 ： u ⋯u 1 D 一 L 1⋯L 其中 L ，u ( =1 , 2 ， ⋯ ， n一1 )由式 ( 2 ) 和 ( 4 ) 给出 3 柯西矩阵的三角分解的应用 给定柯西矩阵线性方程组 Cx=b ( 8 ) 其中 x, b E Rn , C=( ) ： ∈R．n ~ n为柯西矩阵． 显然， 线性方程组 ( 8 ) 同解于 L1⋯Ln一1 D U n --1- · · U 1 x = b 、 一 _ ． ／ ， ● ● ● ● ● ● ● ● 、 ＼ 、 、 ● ● ● ● ／ ● ● 一 一 ． ． l1 一 ■ ／ ，● ●，●、＼ ／ ＼ } l U 2 0 1 1 年 3月 高 等 学 校 计 算 数 学 学 报 方程组 ( 9 )的解可通过依次求解下面 2 n一2个方程组 Ll yl= b L2 y2： Yl Ln --2 Yn -2 = Yn--3 Ln --l Yn 一1= Yn --2 U n—l Zl= D 一 Yn 一1 U n--2 Z 2 Zl U 2 z n --2 Z n --3 U 1 X = Z n --2 ( 1 0 ) 于是得到求解 以柯西矩阵为系数矩 阵的线性方程组的解 ． 本文算法需要 3 n 。

次乘 除运算 ， 4 n 一几次加减运算．而直接求解，如高斯消去法和 L u 分 解 法 所 需 乘 除 运 算 约 为 礼 3 ． [9 ] 中 的 递 推 算 法 所 需 n 2 一 耋 佗 乘 除 运 算 ， 佗 2 + 三 n 加减运算 ． 显然本文算法所需计算量小． 4 数值算例 我 们 针对一 些 柯西矩阵c：( _ _ 兰 ) ： 1 在微 机 ( C P U 2 ．6 0 G ， 内 存5 1 2 M B ) 上 用 Ma t l a b语言编程计算以柯西矩 阵为系数的线性方程组， 其中向量 b=( 6 ( 1 ) ， 6 ( 2 ) ， ⋯ ， 6 ( 札 ) ) 丁 的元素取为b ( i )= ∑ 1 ／ ( c ( ) 一d ( 歹 ) ) ，( i= 1 ， 2 ， ⋯ ， 佗 )，此时柯 西矩 阵 c 的方程组 J= 1 Cx：b的解为 X o： ( 1 ， 1 ， ⋯ ， 1 ) T ．采用本文的算法求解 Cx=b ，时间为秒 ，误差 用 J i x—X 0 l l 2来度量． 部分算例如下： 例1 取柯西矩阵c=( 去) J = 1 ， 其中c j =‘7 ， =1 一 歹 =1 ， 2 ， ⋯ ， n ) ， 此时c 为 Hi l b e r t矩阵， 求线性方程组 Cx=b的解． 计算误差和时间见下表 本文算法 全主元高斯 一 约当消去法 阶数 误差 时间 误差 时间 5 3． 5 39 e 一 1 2 0 6． 3 4 2 e ． 1 3 0． 01 6 7 3． 0 8 5 e 一 0 8 0 3． 3 3 3 e — O 8 0． 01 5 f 8 5 ．3 7 0 e 一 0 7 0 7 ．9 3 4 e 一 0 7 0 ． 0 1 5 ， 1 0 1 ． 1 2 8 e 一 0 4 0 7 ． 6 5 8 e 一 0 4 0 ． 0 1 6 例2 取柯西矩阵 C一( ) ： l， 其中 C i =i 2 , d j =1 一j 2 ( i ， J=1 ， 2 ， ⋯ ， 礼 ) ． 求线 性方程组 Cx=b的解． 计算误差和时间见下表． ．9 6 。