（计算数学专业论文）蝴蝶分解的若干应用研究.pdfVIP

上海交通大学硕士学位论文 蝴蝶分解的若干应用研究 摘要 e v a n s 和h a t z o p o u l o s 于1 9 7 9 年 1 l 提出了矩阵乘积分解的一种新构想：w z 形式 分解。1 9 8 0 年，e v a n s 和h a d j i d i m o s l 2 1 针对对称矩阵给出了改进的w z 形式分解： 1 9 8 8 年，谢松茂p 1 建立了顺序w z 分解构想能兑现的一个充要条件，并在选2 一主元 的情况下，给出了舍入误差的浮点分析。围绕w z 方法进行扩展和应用研究的还 有：蔡大用【6 l 、e v a n s 和h a d j i d i m o s ”1 、e v a n s 和r s o j o o d ih a g i g h i l 4 1 以及文【4 l 一 4 3 。 在精细算法方面，钟万勰院士1 4 ”- 5 5j 于1 9 9 4 年提出了齐次线性定常系统的时程 积分法。钟万勰、沈为平和李红云i 4 9 67 j 等基于寻找有简单解析式的特解的原理提出 了非齐次线性定常系统的精细求解方法。王跃先对精细积分方法的机理进行了较为 细致的研究。目前，精细算法的研究和应用已成为计算力学领域的热点。考虑到精 细算法可以应用于大系统问题，而其中含有大量的矩阵运算；因此，结合矩阵的分解 与运算技巧，实现精细算法的快速与并行计算，无疑是十分重要、十分必要的。另 工作 ( 2 ) 最后 ( 3 ) ( 4 ) 应用蝴蝶分解，建立了求解复h e r m i t e 矩阵特征值问题的新方法一完全避 免复数运算的 指标对快速蝴蝶算法与超快速蝴蝶算法。所设计的 4 个算例证实了新算法的有效性。 应用蝴蝶分解，就一类复h e r m i t e 不定矩阵的方程组问题，建立了完全 避免复数运算的c 实域，蝴蝶松弛迭代解法，给出了具体算法，得到了收 敛性定理：分析了最佳松弛因子。所设计的3 个算例证实了新算法的有 效性。 结合蝴蝶分解、精细算法与矩阵运算技巧开展研究： 就一类特殊复系数线性周期时变系统，建立了相应的精细算法，开展了 相关的误差分析、稳定性和收敛性分析。 应用蝴蝶分解与矩阵运算技巧实现了( 3 ) 中精细算法的完全避免复数运 算的快速计算，称为 蝴蝶精细算法，应用于时变系统，( 4 1 i ) 的 计算，至少节省了8 0 以上的计算量。所设计的5 个算例表明：这一算 法在长时间计算过程中，还能保持较高的精度，与r k 算法的计算结果相 比较，优势十分明显。 关键词蝴蝶分解复h e r m i t e 矩阵复系数线性周期寸变系统 矩阵 ：j ) 相比：( d 、”1l 廿丑 猜想是：若能将( 复) a 。+ i 。b 计算问题转化为( 实) ( ：j 】的计算 问题，那么，就完全避免了复数运算。 难题是：两者不等价，即：a 十i b 的 性质与可行 算法一般 不能自然延伸为e ? 1 的c 实域 性质与可行c 实域 算法。 例如： a 若川b 对称，但( ：j 不保眦冁 b 若爿+ 膪可c h 0 1 e s k y 分解，但匕j 不保留此性质； c 若爿+ 旧h e m i t e 正定，但f ：j ) 只保留对称性质，不保留正定性 质。 【注】：蝴蝶分解应用于复矩阵的处理，在一定程度上，可以解决上述的难题。 所设计的c 实域，蝴蝶算法，不仅完全避免了复数运算，而且一般都可以 并行化。计算实验还显示：即使是串行计算，c 实域) 蝴蝶算法也会比已 知的一些需要复数运算的计算方法节省许多计算时间。本文的算例给出 了一些这样的时间统计。 咽爱匝目呵 砌：【x ) 【一 【 】 的矩阵称为蝴蝶矩阵。 匠圄圃 形如： 的矩阵称为蝴蝶三对角矩阵。 匠圜卿 把矩阵分解为若干个蝴蝶矩阵相加减的形式称为蝴蝶加法分解； 把矩阵分解为若干个蝴蝶矩阵与若干个正交矩阵的混合乘积形式称为蝴蝶乘法 分解。 上海交通大学硕士学位论正 1 3 本文主要工作 本文基于已有的研究成果，开展蝴蝶分解的应用研究，就3 个c 复域，矩阵计算 问题建立了它们的蝴蝶型整体 计算方法，这些方法克服了1 2 中所表述的2 个特征。 主要有下列四个方面的工作： ( 1 ) 用蝴蝶分解，建立了求解复h e r m i t e 矩阵特征值问题的新方法完全避免 复数运算的 实域，指标对快速蝴蝶算法与超快速蝴蝶算法。所设计的4 个算例证实了新算法的有效性。 ( 2 ) 应用蝴蝶分解，就一类复h e r m i t e 不定矩阵的方程组问题，建立了完全 避免复数运算的 蝴蝶松弛迭代解法，给出了具体算法，得到了收 敛性定理；分析了最佳松弛因子。所设计的3 个算例证实了新算法的有 效性。 最后，结合蝴蝶分解、精细算法与矩阵运算技巧开展研究： ( 3 ) 就一类特殊复系数线性周期时变系统，建立了相应的精细算法，开展了 相关的误差分析、稳定性和收敛性分析。 ( 4 ) 应用蝴蝶分解与矩阵运算技巧实现了( 3 ) 中精细算法的完全避免复数运 算的快速计算，称为 蝴蝶精细算法，应用于时变系统( 4 1 1 ) 的 计算，至少节省了8 0 以上的计算量。所设计的5 个算例表明：这一算 法在长时间计算过程中，还能保持较高的精度，与r k 算法的计算结果相 比较，优势十分明显。 【注】暇卿嘲圈哩囹噬豳 均指本文的工作。 上海交通大学硕上学位论文 第二章求解复h e r m i t e 矩阵特征值问题的 2 1 引言 指标对快速蝴蝶算法与超快速蝴蝶算法 考虑特征值问题： a o v = 2 v ( 2 1 ) 其中，a 。是n 阶复h e r m i t e 矩阵，v c ”，通过原点移动和酉变换，可化为 如下的三对角复h e r m i t e 正定矩阵的特征值问题： h o = = p z ( 2 2 ) 其中， h 。是三对角复h e r m i t e 正定矩阵。 记： h o = a + i b ，( a 、b r ) 有：4 = 并记 a 1 届 0 ta 20 2 z = x + i y ，( x ，y r ”) = l + 扯2 ，( l 、2 r ) 艮， “” 0 口l 0 _ 2 一仉，一1 0 协 一目+ 1 0 不妨设? + 口j 0 ，i = 1 , 2 ，n 一1 ，否则可以转化为低阶特征值问题。 求解( 2 2 ) ，已经构造了一些算法，但是这些算法都需要复数运算。本章针对 复矩阵的特点，建立了求解( 2 2 ) 的二个新算法一完全避免复数运算的 指标对快速蝴蝶算法与超快速蝴蝶算法。 【注】：本章下面的许多结论和算法可以推广到三对角复严格对角占优矩阵：由 于三对角复矩阵通过原点位移可以转化为三对角复严格对角占优矩阵， 因而本章下面的部分算法可以应用到三对角复矩阵。 上海交通大学硕士学位论文 2 2 指标对快速蝴蝶算法与超快速蝴蝶算法 【引理2 2 0 】h 。：= ：，( ：0 ) ，等价于直接 实域) 特征值问题 b a a b ( y 。了 = ( ；了 ( ：；! i2 c z ， 事实上，日。z = 肛展开后有 分实部、虚部，有： ( ：b ) ( k a = ( ；一x j ，j f 卢2 1 及( ：- 4 b 阱- yg 烈i 2 即： (爿一b；了=；了(：-,ub a 。2 l儿y x j【yx 儿“，“j c = ( 2 _ 2 称为复特征值= 。+ 扭：的 蝴蝶特征值问题( 2 4 ) 。 直接验i i e 目p 可得到。 因为h 。是三对角复h e r m i t e 正定矩阵，不难得到： 眶医量冒圆对s = o ，l ，2 ，始终有： 。：。掣，其中，h “= ? 、，是可逆下三角矩阵； ，始终是三对角的复h e r m i t e 正定矩阵。 记：皿： + j 矿，只= ( 篆- 脚b ( 训) j i ， 其中，爿( o ) = a ，b o = b ，a “，b 3 r ”( s = 0 , 1 ，2 ，) 。 反复应用定理2 2 6 和定理2 2 3 ，可以得到： 重嚣重冒脚 对于5 = 0 , 1 ，2 ，始终有： f 、= 畎w 7 其中，f + = 畎。形 w 的形状如同定理2 2 3 中的w 。 屈一 i l k 上海交通大学硕上学位论文 e 雷冒团设h 。满足： ( 1 ) h 。有n 个复特征值，( ，= 1 , 2 ，”) 并且川 川 川 0 ； ( 2 ) 记d 是对角元素为2 ，的对角矩阵，( j = 1 , 2 ，月) ， 如果有h 。= x d y ，= y ，并且存在初等矩阵鼻，p 2 使得： x 只，p 2 y 有l r 分解。 则： 当j 寸0 0 时，迭代序列只本质上收敛到z 型矩阵( 一，。) ：。一 并且z + z 2 。吐，是h o 的特征值，( ，= 1 ，2 ，月) 。 证明： 因为h 。是三对角复h e r m i t e 正定矩阵， 所以，风有c h o l e s k y 分解；由此，不难看出：一定有分解：h 。= x d y ， 并且，其中的x ，y 分别是对角元素非0 的下、上三角矩阵，x = y ， 当 j _ 时，h ，本质上收敛到上三角矩阵r ，并且对角元0 ，就是h 。的 复特征值，( j = 1 , 2 ，n ) i g ：r = r 1 + i r ”，( r ”，r 2 r ) ， 由定理2 2 5 7 ，不难得到： c 本质上收敛到( 盖? ：) - 锻r ，j j i ，。j m ，时。 并且( 量l l ：) - 腰r ( 2 ) ，j j i 为z 型矩阵c 气，b 。一 。 由于r ，就是h 。的复特征值，不难看出： 第j 个 指标对( ：。，一z 气2 n - ，j 。 诱导的z j , j 一 1 z 2 n _ ) + l , j ( = 1 , 2 ，h ) 是h 。的n 个复特征值。 证毕 一卜海交通大学硕一学位论文 匪蟊冒蛋嘲( 指标对快速蝴蝶算法) s t e p l 计算= 葛( 鼽肚拶) - b ) s t e p 2 ：调用算法2 2 1 ，分解c 得到：c = 峨昨， 计算只+ = 嘭岷 s t e p 3 ：记f 、+ l = ( ，了。) 2 吖l h l _ i n , l o 是预先设定的误差限) ， j + _ j + 1 ， 执行s t e p 2 ，否则执行s t e p 4 ； s t e p 4 ：岸，= 矗j 1 + 兆：川。( = 1 ，2 ，n ) 就是h o 的n 个复特征值。 【注1 ：考虑到定理2 2 4 ，可以看到：算法2 2 1 有并行性，所以，算法2 2 2 也 下面，建立求解( 2 2 ) 的既没有复数运算也没有丌方运算的 指标对超 ! 鳃5 所有都是形如： b 兰 日l b lc 1 2 0 b ，ld ，0 一 t ，l 0 d ，b ，l o 蝶三对角矩阵；简记：b 兰 6 川+ i 4 川，d ，。 口二6 l 口， 称为w 形状的蝴 上海交通大学硕士学位论文 1 9 证明 存在正交矩阵u 。，使得w 。r = u 。 由于只+ 。= 畈+ 。w 。r = 眈哌，且吼+ 可逆 所以，略。= ( 吲嘭) ，记u = 嘲町 有 u 。u j = 吲町( t + 。) = 喇e + 。( 吆。) = 吲+ 。吆，( 吆，) = ，：。 同理有： u j u = ，：。 这就证明了u 。为正交矩阵。 第新i 第2 n k + 1 行 第2 h 一+ 1 行 如下形状的矩阵称为 蝴蝶g i v e n s 矩阵 垒0 o s 2 l 0l0 0 卫0 ， 垒0 ， 0 o0 垒0 记为j ( j ，k ；c l + i c2 ，s l + i s 2 ) l0 0 c a l r 0 垒 ， 00 0 0 一垒 o 10 0l 垒0 0 00 00 一生0 c 1 0 r ol 0 量0 r 0 0 生 ， 0 一l 0 10 0 垒 ， o 其中厂= 、习- 下了了e 雨 ，r o ；q + 衍：和j + i s , 是两个复常数 一f ，s ，s ，r 。 0 上海交通大学硕士学位论文 眶量嘎雷圃 j ( j ，七；c 。+ 捃：，5 。+ i s2 ) 是正交矩阵 对于任意非零向量t y e ，向量l 喜j ( 1 j 0 是预先设定的误差限。 2 3 数值算例 计算 h o = 1 22 + 4 f 2 - 4 i1 43 + 3 f 3 3 f1 64 + 2 i 4 2 i1 85 + f 5 一f2 06 62 2 7 一f 7 + f2 48 2 f 8 + 2 f2 69 3 j 9 + 3 f2 81 0 一4 j 1 0 十钔3 0 的特征值 丝t 勺 半 g 墼巳 行 乃 执 ， 一 十 0 巳 = = 巳 ， 巳 1 | 对 k 把 上海交通大学硕士学位论文2 3 _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ - _ d _ _ _ _ _ _ _ - _ _ - - _ _ _ - _ _ _ _ _ _ _ - - _ _ _ _ _ _ _ _ - _ _ _ _ - 一一 验证可知：。是复h e r m i t e 正定矩阵 分别用 指标对快速蝴蝶算法( 算法2 2 2 ) 、 c h o l e s k y l u 算法、 q r 算法和无开方运算的 指标对超快速蝴蝶算法( 算法2 2 5 ) 计算。 结果如下： 特 迭代 指标对超快速蝴蝶 值 算法 5 0 4 31 9 5 3 5 9 5 7 7 4 1 8 4 84 31 9 5 3 5 9 5 7 7 4 1 8 5 l4 31 9 5 3 5 9 5 7 7 4 1 8 5 34 31 9 5 3 5 9 5 7 7 4 1 8 5 1 5 1 0 04 33 9 4 8 4 6 3 6 5 6 2 0 8 54 3 3 9 4 8 4 6 3 6 5 6 2 0 8 3 6 4 33 9 4 8 4 6 3 6 5 6 2 0 8 3 94 3 3 9 4 8 4 6 3 6 5 6 2 0 8 6 5 f l 2 0 04 33 9 4 8 4 8 2 6 3 6 6 51 9 64 33 9 4 8 4 8 2 6 3 6 6 5 1 9 4 3 3 9 4 8 4 8 2 6 3 6 6 5 2 1 44 33 9 4