（计算数学专业论文）jacobi和拟jacobi梯度迭代法求解sylvester矩阵方程.pdf

上海大学硕士学位论文4 摘要 本文主要讨论的是j a c o b i 梯度迭代法和拟j a c o b i 梯度迭代法求解s y l v e s t e r 矩阵方程的问题 第一章通过回顾线性系统的基本知识及其模型简化问题而引出s y l v e s t e r 矩 阵方程求察问题 。 第二章在回顾大类迭代方法( 主要是梯度迭代法) 的基础上，将求解线性 方程组的j a c o b i 和g u a s s - s e i d e l 迭代法应用于已有的梯度迭代法中，得到本文 主要结果之一的j a c a o b i 梯度迭代法和g u a s s - s e i d e l 梯度迭代法，从而降低了运 算量此外。还对连续型，离散型和广义型的j a c o b i 梯度迭代法分别给出了收 敛性证明并附e 若干数值锣! l 子 通过第二章对j a c o b i 梯度选代法的进步思考，我们在第三章引出了拟j 扣 c o b i 梯度迭代法它是对j a c o b i 梯度迭代法做了一些技术上的改进，也同样给 出相关的收敛性定理和数值实例 关键词ts y l v e s t e r 矩阵方程，梯度迭代法，j a c o b i 捞度迭代法，拟j a c o b i 梯度迭代法。收敛因子 a b s t r a c t i nt h i sp a p e r ，j a c o b ia n dq u a s i - j a c o b ig r a d i e n ti t e r a t i v em e t h o d sa r es t u d - i e da n da r ea p p l i e dt os o l v es y l v e s 舰rm a t r i xe q u a t i o n s t h ep r o b l e mf o rs o l v i n gs y l v e s t e rm a t r i xe q u a t i o n sa r i s e sf r o ml i n e a rs y s - t e n t sa n di t sm o d e lr e d u c t i o np r o b l e m t h u s ，f i r s t l y , w er e v i e ws o m eb a s i ck n o w l - e d g eo fl i n e a rs y s t e mi nc h a p t e ro n e t h e n ，w ed e r i v ej a c o b ia n dq u a s i - j a c o b i g r a d i e n ti t e r a t i v em e t h o d sb yp r e s e n t i n gt h ek n o w ng r a d i e n ti t e r a t i v em e t h o d ， r e s p e c t i v e l yi nc h a p t e rt - 7 0 a n dt h r e e ，f o rs o l v i n gc o n t i n u o u s d i s c r e t ea n dg e n - e r f l l i z e ds y l v e s t e rm a t r i xe q u a t i o n s c o n v e r g e n c et h e o r e m sa n ds e v e r a le x a m p l e s f o rj a c o b ia n dq u a s i - j a c o b ii t e r a t i v em e t h o d sa r eg i v e nt os h o wt h e s et w om e t h - o d so r em o r ee f f i c i e n ta n du s e f u l 。 k e y w o r d s ：s y l v e s t e rm a t r i xe q l m t i o n s ，g r a d i e n ti t e r a t i v em e t h o d ，j a c o b i - g r a d i e n ti t e r a t i em e t h o d ，q u u s i - j a c o b ig r a d i e n ti t e r a t i v em e t h o d ，c o n v e r g e n c e f a c t o r 上海大学硕士学位论文 1 第一章绪论 1 1 引言 应用数学中的许多问题需要求助于解s y l v e s t e r 方程 a x + x b = 一g ( 1 1 1 ) 其中。a p ”，b c “。”，c c ”。”事实上，对于线性代数中的许多基本 问题，在确定了b 和c 之后，都可以归结为求解s y l v e s t e r 方程s y l v e s t e r 方 程另个主要应用来源是矩形域上可分椭圆形边界值问题的离散化，其中4 和 口分别代表了l 和霉方向上的差分算子f 8 ，1 9 】s y l v e s t e r 方程其他的应用还包 括块三角矩阵的块对角化【1 9 】，特征值扰动理论【3 0 】，降阶观测器的设计【8 】但 是所有应用中引起最多关注的就是大规模动力系统的降维简化问题 在一般情况下，动力系统简化问题中的s y l v e s t e r 方程具有低秩结构，即【2 8 l ： a x + x b = 一c d 。 ( 1 1 2 ) 其中，c c - ”，d c ”，p m i n ( r a ，n ) ， 表示个矩阵的共轭转置式 ( 1 1 2 ) 为连续型s y l v e s t e r 方程此外。也有离散型s y l v e s t e r 方程； x 一一c a x b ( 1 1 3 ) 连续型和离散型s y l v e s t e r 方程可以通过双线性变换互实现换 s y l v e s t e r 方程其实是二次r i c c a t i 方程t x d x + a x + x b = g 。 的个特例。其中a c ”“，b c ”。”，c c ”。”，d c ”【2 1 1 最优控制中 的许多问题常要求解r i c c a t i 方程，而求解r i c c a t i 方程的许多算法又要求求解 多个l y a w m o v 方程，如下【2 8 】： a x + x a = 一d ( 1 1 4 ) 在下述内容中，我们限定a 的特征值都在开的左半平面( 即：a 是稳定的) ，且c 是h e r m i t 矩阵在这些约束条件下，解x 就是唯一的且h e r m i t i a n 半正定的 此外，l y a p u n o v 方程也出现在动力系统稳定性分析当中 ：皇瀣盘堂亟堂焦堡塞 = ：至 1 2l y a p u n o v 方程在线性系统中的应用背景 许多物理过程可以建模为如下的动力系统。 眈( t ) = 血( ) + 凰( 。) ， ( 1 2 1 ) u ( t ) = c x ( t ) + o u ( t ) ， 其中，x ( t ) i p 称为系统的状态，“( t ) r ”称为系统的输入。暑，( t ) r p 称 为系统的输出；而e c “，4 c ，“，b c “。“，c c p ”，d c p 。”为常 量矩阵个具有单输入( 仇= 1 ) 和单输出国= 1 ) 的动态系统称为单输入单输 出( s i s o ) 系统否则，称之为多输入多输出( m i m o ) 系统动力系统通常出现 在诸如电路设计，流体力学，以及机械系统仿真等实际应用中矩阵a 和e 通 常都是h e r m i t 型的。e 常为正定的，且假设a 是稳定的这些矩阵通常是大 型稀疏阵般系统的输入和输出都是比较小的，也即m 一扎当e 为奇异 矩阵时，我们就将( 1 2 1 ) 视为个描述系统大多数情况下。都假设e 是可逆 的，也即( 1 2 1 ) 等价于个状态矩阵为e 1 a ，输入矩阵为e _ 1 b 的系统本文 以下内容中，都假设e 为可逆的。或将其简单视为单位矩阵， 我们定义系统从输入t ( t ) 到输出暑，( t ) 的传递函数矩阵t y ( s ) = g ( 8 ) u ( 8 ) ， 其中，t r ( 8 ) 和y ( 8 ) 分别为“( t ) 和y ( t ) 在零初始条件z ( o ) = 0 下的l a p l a c e 变 换因此，有 g ( s ) = c ( s l a ) 一1 b + d 为了简化传递函数矩阵计算。采用如下记号； ：= c ( s i a 1 1 b + d 在某些情况下，个动态系统最自然，最方便的描述是传递函数矩阵例如， 对于一些非常复杂的系统，它们的解析微分方程太难表示出或者太复杂因此， 必须对系统进行工程上的近似或辨识比如，通过由实验得到的输入输出频率 响应就能够获得近似描述系统动态特性的传递函数矩阵但因状态空间计算在计 算机上实现更为方便，所以又有必要用状态空间来表示传递函数矩阵 ：占鲞盘堂亟堂笪堡塞：墨 一般地，假设g i s ) 是个真实有理传递函数矩阵，若有 g ( s ) = 则称状态空间模型( a ，b ，ad ) 是g ( s ) 的个实现【2 j 定义1 1 1 2 l 若a 具有可能的最小维数，则称g 俐的状态空问实现( a ，b ，c ，d ) 是g 俐的最小实现 定理1 1 1 2 lg 例的状态空间实现( a ，口，c ，d ) 时最小实现，当且仅当( a ，b ) 为可控且( c a ) 为可观测 证明略可控与可观测的定义详见【2 】中的定义3 1 ，3 4 和定理3 1 ，3 3 因此，要得到个系统状态空间的最小实现。既可以采用k a l m 觚可控能测 性分解方法( 【2 】，第三章的3 3 节) 消去其中的不可控和不可观测的状态，也可以 采用一种在数值计算上可靠的消除不可控和( 或) 不可观测状态的方法，即平 衡实现法具体思想如下 假定g 一是稳定的，即a 是稳定的( 如果a 的所有特征值均位 于左半开平面，则称a 是稳定的) 设p 和q 分别表示可控性g r m n i t m 矩阵和 可观测性g r a m i a n 矩阵，满足下列l y a p u n o v 方程； a p + 蹦= - b b ，( 1 2 2 ) a q + q a = 一( 了g( 1 2 3 ) 并且p 0 和q 0 进而， 测，当且仅当q 0 引理1 1 嘲设 ( a b ) 为可控，当且仅当p o ；( c ，a ) 为可观 3 1 8 、 为传递函数矩阵g 纠体一定是稳定的，的一个 状态空间实现假定存在一个对称矩阵尸= p = ： ，其中，r 为非奇 异。使得 成立若将实现( a ，b ，q d ) 按矩阵p 相应分块如下 ，则 也是g 的一个实现并且，若a n 为稳定，则( a l l ，z h ) 为可控 引理1 2 n 设 为传递函数矩阵g 俐r 不一定是稳定的j 的一个 状态空间实现假定存在一个对称矩阵q = 固= 奇异，使得 q + q a + 口c = 0 q 。1 ，其中，q 。为非 00j 成立若将实现，口，a d ) 按矩阵q 相应分块如下，触 也是g 的一个实现并且。若a n 为稳定，则( c 1 ，a n ) 为可观测 由上面的两条引理可知，要从个稳定的非最小实现获得最小实现。只需去 掉可控性g r a m i a n 矩阵p 和可观测性g r a m i a n 矩阵q 中对角块为零部分所对 应的状态但是，单方面消去不可控或不可观测的子系统，并不能得到个系统 的最小实现( 详见【2 】，p p 8 9 - 9 0 ) 这就启发我们引入一种平衡实现，这种实现给 出了可控性和可观测性的平衡g r a m i a n 矩阵 假定通过个非奇异矩阵t ，系统的状态变换成量= t x ，则有实现 g =嘲= 离倒 因而g r a m i a n 矩阵就变换成p = t p p 和国一( t 一1 r q t 注意到，矗0 = t p q r ，因此，在状态变换下，两个g r a m i a n 矩阵乘积的特征值不变 考虑到相似变换t 可给出如下的特征向量分解 p q = t - 1 a ea = d i a g ( ) q ，k ) ， 则7 “1 的列就是p o , 对应于特征值 九) 的特征向量因为p 之0 且q 0 ，所 以p q 具有实对角的j o r d a n 型且a 0 虽然特征向量不是唯一的，但在最小 实现的情况下，它们总可被选择以使 户= t p p ；e 土查盘堂塑堂鱼堡塞 墨 q = ( t _ 1 ) q t _ 1 = e 成立其中，e = d i a g ( a 1 ，) 直e 2 = a 这种具有可控性g r a m i a n 矩阵 与可观测性g r a m i a n 矩阵相等，即p = q = 的实现称为平衡实现( 也称为内 部平衡实现) 依次递减排列的毋，砚0 称为系统的h a n k e l 奇异 值如果对某个r ，有西听+ 1 ，则平衡实现意味着。对于与奇异值0 r r + 1 ， 对应的那些状态，它们的可控性和可观测性与o 1 ，：- ，c r r 所对应的状态相上匕要弱 些因此，截去那些可控性和可观测性都较弱的状态将不会使系统损失太多的 信息这也就得出解决线性系统模型简化问题的平衡截断方法 综上，解决线性系统模型简化问题或求解个线性系统的最小实现问题就归 结为求解l y a p u n o v 方程( 1 2 2 ) 和( 1 2 3 ) 而由1 1 节引言知，l y a p u n o v 矩阵 方程其实是勖b 皓t e r 矩阵方程的一种特殊形式所以j 本文将主要围绕如何求 解s y l v e s t e r 方程来展开 1 3 本文所做的主要的工作 本文在第二章通过回忆大类迭代法引入了求解s y l v e s t e r 方程的梯度迭 代法。并对其进行改进得到了j a c o b i 梯度迭代法，并将其分别应用于连续型， 离散型和广义型s y l v e s t e r 方程的求解然后，对这三种方程分别给出了相关的 收敛性定理和数值实例 通过对梯度迭代法和j a c o b i 梯度迭代法的进步观察，在第三章中得到 一种改进的j a c o b i 梯度迭代法一拟j a c o b i 梯度迭代法同样的，将该方法应用 于连续型，离散型和广义塑的s y l v e s t e r 方程的求解，也同样给出了相关的收敛 性定理和数值椤! i 子 上海大学硕士学位论文 6 第二章j a c o b i 梯度迭代法 f e n gd i n g 和t o n g w e nc h e n 在文章【l o ，1 2 ，1 4 】中将一种新的迭代方法应用 于几类s y l v e s t e r 矩阵方程( 连续的，离散的，广义的) 的求解本章中，将把求 解线性方程组的j a c 西b i 迭代法的基本思想应用到f e n gd i n g 和t o n g w e nc h e n 的方法中，进而得到一种新的，更为简便的迭代方法同时还将研究其收敛性， 并给出具体数值倒子： 2 1 一类迭代方法简介 设有如下线性方程组， 知= b ( 2 1 1 ) 其中a = 】( ，= 1 ，2 ，n ) 是个行n 且对角元素均不为。的满秩矩阵。 b 黔是常向量，茁职p 是未知向量令d 为a 的对角部分，l 和u 分别 是a 的严格下三角和严格上三角部分。 d = d i a g a n ，a n ，】鼢“， l= u oo o o 2 l 0 o ； a 3 1 衄0 ； ； 0 口，1 1 玛口口r i m l0 0 口1 2 口1 3 口l n 00o 2 3 口轨 ： - 吗i 一1 “ 0 0 0 p 。” r 竹。竹 土鲞盔堂亟堂焦迨塞 ：! 满足l + d + u = a j a c o b i 和g u a s s - s e i d e l 迭代法可以被表示成如下的形式 f 1 4 】： m x ( k ) = l v x ( k 一1 ) + 玩凳= 1 ，2 ，3 ， 对j a c o b i 迭代法，m d 且n = - ( l + u ) ； 对g u a s s - s e i d e l 迭代法，m = l + d 且n = 一u 令g r - ”是个满秩待定矩阵，肛是步长或收敛因子我们可以将一大 类迭代方法归结为如下形式。 z ( 后) = ( 七一1 ) + p g b a z ( 七一1 ) 】，k = 1 ，2 ，3 ( 2 1 2 ) j a c o b i 和g u a s s - s e i d e l 迭代法都是其特殊情况， 取g = d - 1 和p = 1 ，即为j a c o b i 迭代法； 取g 一( l + d ) - 1 和p = 1 ，就为g u a s s - s e i d e l 迭代法： 定理2 1 1 1 4 1 假设对于迭代格式仁1 纠，系统似1 砂具有唯一解那么， 如果存在一个与k 无关的g 0 ，使得 p ( g a ) r ( g a ) + e l ( c a ) t + ( c a ) ， ( 2 1 - 3 ) 对所有的k 成立，则对于任意初始值z ( o ) ，逮代解z ( 七 都收敛于精确解易即 矗m m z ( 七) = z 证明【1 4 j 令误差向量 孟( 七) = x ( k ) 一z 将( 2 1 2 ) 代入上式并利用( 2 1 1 ) ，可得 孟( 后) = 童( 七一1 ) + 心 缸一血( 七一1 ) 】 = 奎( 七一1 ) 一p g 童( 膏1 ) 一【i u g a l 童( k 1 ) 定义个非负定的函数ts ( k ) 一矽( 七) 蠡( 后) 因此有 s ( k ) = 矿( 詹一1 ) 【j p g a r 【j 一心a 】圣 一1 ) = 矿( 七一1 ) 孟( 七一1 ) 一肛矿( 七一1 ) 【g a + ( g a ) t u ( g a ) t ( g a ) 忙( 七一1 ) = s ( k 1 ) 一 癌r ( 后一1 ) 【g a + ( g a ) t u ( g a ) t ( g a ) 】孟( 七一1 ) 。土鲞盘堂塑堂鱼盈塞 ：垒 再由( 2 1 3 ) 式，可得 a s ( k ) = s ( k ) 一s ( k 一1 ) = 一i 西r ( 七一1 ) 【g a + ( g a ) t 一p ( g a ) t ( g a ) 】i ( 七一1 ) 一心孟t ( 七一1 ) 童( _ j 一1 ) 0 所以，当k o 。时，s ( k ) 一o 我们知道，如果( ，一d _ 1 锄。的所有特征值都落在单位圆内。那么j a c o b i 迭 代法就收敛于精确解；类似的，如果p 一+ d ) - 1 a 】的所有特征值都落在单位 圆内，那么g u a s s - s e i d e l 迭代法也收敛于精确解在这里，我们引入了收敛因子 p ，它可以使得j a c o b i 和g u a s s - s e i d e l 方法的收敛条件放松这是因为，只要适 当选取p ，就可以使( ，一p d - 1 a ) 或【，一p ( l + d ) - 1 刎所有的特征值都落在单 位圆内由定理2 1 ，我们可以得到如下一些推论 推论2 1 1 1 4 取g 。d ，如果矩阵d 一1 + d 一1 a 正定且满足条件 。 p 0 且满足条件 。 p 弋) 。n t 习n a 矛t ( l 石+ 订d ) 矿- r 砸+ ( 了l + 丽d ) - i a ， 则对蒂收敛因子j i 的g u a s s - s e i d e l 迭代法 z ( 七) = x ( k 一1 ) + ，( l + d ) 一1 【6 一a 茁( 七一1 ) 】 有l 钿l k m 茹( = z 推论2 3 1 1 4 1 取g = a t ，则梯度迭代法( g r a d i e n ti t e r a t i v ea l g o r i t h m , 简记 为t o p o i z ( 七) = z ( 七一1 ) + p a r 【6 - a z ( 七：1 ) 】， ( 2 1 4 ) 10 p 焉：币2 砑d r0 肛 前 、7 鲞盔堂塑堂鱼迨塞望 其中i i x l l r = t r x 1 推论2 4 【1 4 1 如果a 是一个mx n 的列满秩矩阵，取g = ( a t a ) 一a t ，则 最小二乘迭代算法口o l z ( 七) = z ( 七一1 ) 4 - i j ( a t a ) 一1 a r 【6 一a z ( k 1 ) 】，0 p 2 有收敛性l i m k ：o o z ( k ) = z 在以下的篇幅中，将先对推论2 3 的梯度迭代法进行回顾，然后将着重介绍 由其推广得到的j a c o b i 梯度迭代法，并分另应用到解连续型，离散型和广义型 s y l v e s t e r 矩阵方程中 2 2 梯度迭代法 在这一节，我们将主要回顾求解s y l v e s t 玉矩阵方程 a x + x b = g ( 2 2 1 ) 的梯度迭代法( g i ) 1 2 ，其中a r m “，b r n 。n , c er m “是常量矩阵， x r m n 是未知矩阵 对于个方阵m ，m 表示其第i 个特征值厶表示个n ，l 的单位 阵m 0 表示m 与的k r o n e e k e r 乘积对个m n 矩阵 x = 扛l 勋】r m “ c d z i x 】就表示由x 的列组成的个撇维矩阵，也即，c o f x l = 陋 霹瑚t 引理2 1 1 1 锄方程阻幺砂有唯一的解当且仅当对任意的i 和j ，有凡川+ 【b 】o i 在这个条件下。方程的解可以表示为 删冈= 【固a ) + ( b r 固k ) 】_ 1 c o z c ，( 2 2 2 ) 且对应的齐次方程a x + x b = 0 只有唯一解x = 0 特别的，当b 一伊时。( 2 2 1 ) 就是连续时间状态下的l y s p t m o v 方程； 其存在唯解的充分必要条件为，对任意的i 和j ，州+ 【州0 土鲞盘堂塑堂垡监塞。 ! q 。 由【1 1 1 和【1 剐，井基于最小二乘法的思想，方程( 2 2 1 ) 可以被分解成两个子 方程由此，我们就可以得到个迭代算法。具体过程如下首先定义两个矩阵“ 6 l ：= c x b ，b 2 ：= c a x ( 2 2 3 ) 那么由( 2 2 1 ) ，我们可以得到两个如下形式的子系统 a x = b l ，x b = b 2 ( 2 2 4 ) 令x l ( 七) 和x 2 ( k ) 为x 在( 2 2 3 ) 中两个子系统分别迭代至于第k 步的近 似值由f 1 翻的引理1 就可以得到如下的迭代方程， x l ( 知) = 局( 七一1 ) + p 爿r 【6 l a x i 一1 ) 1 ， ( 2 2 5 ) x 2 ( k ) = 局( 七一1 ) + ，i 【6 2 一恐( 七一1 ) 捌b t ( 2 2 6 ) 这里“被看作是迭代步长或收敛因子为方便起见。可以取 p = a 。【a 们+ 入。旧且1 ) 。1 ( 2 2 7 ) 其中k 。表示最大特征值， 将( 2 2 3 ) 代入( 2 2 5 ) 和( 2 2 6 ) ，并用x 在第k 一1 步的迭代近似值代替 x ，有如下【1 2 】 墨( 七) = x l ( 七一1 ) + “【c a x l ( 七一1 ) 一磁( 七一1 ) 吲，( 2 2 8 ) 恐( 七) = 恐( 七一1 ) + p 【c a x 2 ( k 一1 ) 一恐( 七一1 ) b b t ( 2 2 9 ) 但事实上，我们只需要个迭代解x ( 七) ，而不是墨( 七) 和恐( 七) 这两个迭代解 所以，一种简单的处理方法就将对x 1 ( 七) 和恐( 詹) 取数值平均，便得到如下梯 度迭代算法( g r a d i e n ti t e r a t i v ea l g o f i t h m ) 1 2 1 x ( k ) = x x ( k ) + x 2 ( 后) 】2 ， x l ( 七) = x ( k 1 ) + p a ? 妙一a x ( k 一1 ) 一x ( k 一1 ) 明， ( 2 2 1 0 ) 恐( 七) = x ( k 一1 ) + p p a x ( k 一1 ) 一x ( k 一1 ) b 】口r 可以取初始迭代矩阵x ( 0 ) 一0 或各元素趋于0 的实矩阵，如x ( 0 ) = 1 0 - 6 1 。， 这里1 。表示矩阵元素全为1 的个m ，l 矩阵算法( 2 2 1 0 ) 的收敛性可 以由如下的定理保证，且证明中的范数均表示为i l x 咿= t r x 1 壅盘堂亟堂鱼逢塞 ： ! ! 定理2 2 【1 2 1 如果s g l , j e s t e r 方程俾幺砂有唯一解x f 见研中引理j ，那么 由算法阻2 1 0 ) 一偿彦j 剀得到的迭代解x ( k ) 收效于x ，也即 i m 。x ( 后) = x i 或是，对于任意初始值x ( o ) ，误差x ( 知) 一x 收敛于n 证明f l2 l 定义误差矩阵 裂三焉j ，枷：吲耵x 眨z m ， 而( 七) - 墨( 七) 一x ，恐( 七) ：= 恐( 七) 一x 和 。 毒( 七) ：= a 2 ( k 一1 ) 叩( 七) ：一贾( 奄一1 ) b ( 2 2 1 2 ) 由( 2 2 1 ) 和( z 忍1 0 ) 不难得到 贾1 ( 七) 一戈伪一1 ) + 舭t 【- 从 一1 ) 一2 ( k 1 ) b 】， ( 2 2 1 3 ) 岛( 七) = 戈( 詹一1 ) + “一a 2 ( k 一1 ) 一戈( 七一1 ) 明b t ( 2 2 1 4 ) 对( 2 2 1 3 ) 和( 2 2 1 4 ) 取范数，并用( 2 2 1 2 ) 得 1 1 2 - ) 1 1 2 = 1 1 2 ( k 一1 ) 1 1 2 + 2 p 打 贾t ( 七一1 ) a t 一( 的一卵( 七) 1 ) + p 2 i i a t 【一f ( 七) 一，7 ( 后) 】0 2 ( 2 2 1 5 ) 1 1 2 ( k 一1 ) 1 1 2 + 2 彬r p ( 七) 【一( 七) 一叼( 詹) 】 。 + 矿i i a i l 2 i i ( k ) + 町( 七) 肝 1 1 2 2 ( k ) 1 1 2s1 1 2 ( k 一1 ) 1 1 2 + 私r 胩( 七) 一删】矿( 七) ) ( 2 2 1 6 ) + p 2 i i b i l 2 i i ( k ) + 町( 七) 1 1 2 。 因此，由( 2 2 1 1 ) ，( 2 2 1 5 ) 和( 2 2 1 6 ) ，有 1 1 2 ( k ) 1 1 2 = 【1 1 2 1 ( 七) 十恐( k ) l l2 4 【1 1 2 1 ( k ) 1 1 2 + 1 1 4 ( k ) 1 1 2 2 i i x c k 1 ) 1 1 2 一肛0 ( 詹) 十卵( 后) 1 1 2 + 譬( i i a i l 2 + l i b i l 2 i k ( ) + 町( 七) 1 2 = i i x ( k 一1 ) 2 一学 2 一u ( i i a i l 2 + i i b i l 2 ) ) j i f ( 七) + 叩( 七) 1 1 2 1 1 2 ( o ) 1 1 2 一等 2 一， i i a i l 2 + i i b i l 2 】) j i f ( i ) + , 1 ( 0 1 1 2 ：土壹盘堂亟圭堂笪堡塞：! 呈 如果选择收敛因子使其满足 0 p 2 i i a i l 2 + i i b i l 2 ) ，( 2 2 1 7 ) 那么就有 o o i i , c k ) + 叩( 酬2 o o k = l 这表示当k 一时，专( 七) + 叩( 七) 一0 ，或a 宕 一1 ) + 贾陋二1 ) b 一0 所以， 根据引理2 1 ，当k o o 时，有2 ( k ) 一0 , i e ，x ( k ) 一x 口 算法( 2 2 8 ) 或( 2 2 9 ) ，也就是通常所说的单边迭代法。但它们并不能保证 五( 七) 收敛于x ；而( 2 2 1 0 ) 给出了一种平衡的迭代法。我们也可以将其简写成 【1 2 】 x ( k ) = x ( k 一1 ) + i l p a r 【c a x ( k 一1 ) 一x c k 1 ) b 】 + i ，i f c a x ( k 一1 ) 一x ( k 一1 ) 矧b t ， ( 2 2 1 8 ) p = 2 ( i i a i l 2 + i i b i l 2 一1 2 3j a c o b i 梯度迭代法 在这节中，我们将给出一种求解s y l v e s t e r 矩阵方程的改进方法，即tj a c o b i 梯度迭代法( j a c o b ig r a d i e n ti t e r s t i v ea l g o r i t h m ，简记为j g i ) ，并给出了该方法 的收敛性定理 我们都知道用于求解线性方程组a z = b 的j a c o b i 迭代法是先将系数矩阵 a 分解成a = d + l + u ( 见【l 】) ： a x = b 号( d + l + 叨z = b 每d z = 一( 三+ u ) z + b 净茹= 一d 一1 ( l + u ) $ + d 一1 b 其中d ，五和矿分别表示矩阵a 的对角阵，严格下三角阵和严格上三角阵那 么j a c 0 1 ) i 迭代法就可以写作 x ( k ) = - d 一1 ( l + 扩弦陋一1 ) + d 一1 b 。鲞盍堂亟堂垡堡塞 ! 墨 现在我们将j a c o b i 迭代法中分裂系数矩阵的思想应用到求解s y l v e s t e r 矩阵 方程( 2 2 1 ) 中首先将矩阵a 和b 进行如下分解t 。 a = d 1 + 三l + 以，b = d 2 + 历+ 巩 ( 2 3 1 ) 其中d l 和上) 2 分别是矩阵a 和b 的对角矩阵 d 1 = d i a g a n ，d 2 2 ，嘶。】r m 。”， d 2 = d i a g 眈l ，6 2 2 ，】舻 l 1 和如分别是a 和口的严格下三角阵：驴i 和沈分别是a 和口的严格上三 角阵 将( 2 3 1 ) 带入( 2 2 3 ) 得 ( d 1 + 工1 + 仉) x = 6 l ：= c x b ， x ( d 2 + 如+ 阮) = b 2 ：一c a x 净 d 1 x 。e x b 一( l 1 + 仉) x ， ( 2 3 2 ) x d 2 一c a x x ( 2 + 观) 我们有如下定义 a = d t ，b = d 2 ( 2 3 3 ) 6 l = c x b 一( l 1 + u 1 ) x ，b 2 c a x x ( 如+ 巩)( 2 3 4 ) 我们发现，( 2 3 3 ) 和( 2 3 4 ) 的定义使得( 2 3 2 ) 可以简化为与2 2 节中( 2 2 4 ) 相同的格式t a x = 6 l ，x b = b 2 通过和2 2 节相同的处理方法，我们可以得到迭代方程 剐x 2 ( 七k ；絮二：篮竖拦笔；尝 皿3 劫 ) = 配( 七一1 ) + p 【6 2 一恐( 七一1 ) b 】f t 将( 2 3 3 ) 和( 2 3 4 ) 带入( 2 3 5 ) 得 蜀( 七) = x l 佧一1 ) + p d l 眵一d l x l 一1 ) 一( l 1 + 仉) x j r 捌， ( 2 3 6 ) 磁( 奄) 一 一1 ) + p 【d a x x ( 岛+ c ，2 ) 一义j ( 七一1 ) d 2 】z ) 2 。 盘盍堂塑主鸶焦堡塞 ! 生7 在( 2 3 6 ) 中，用x 在第( 奄二1 ) 步的近似值代替x ，禧 x l ( 七) = x d k 一1 ) + p d l p d i x l ( k 一1 ) 一( l l + 仉) x l ( 七一1 ) 一x k k 一1 ) 例 = x 1 ( 七一1 ) + # d 1 p a x i ( k 一1 ) 一x l ( k 一1 ) 吲， 而( 七) = 恐 一1 ) + p 【c a x 2 一1 ) 一恐忙一1 ) + 踢) 一恐( 后一1 ) d 2 l 晚 = x 2 ( 七一1 ) + u c a x z ( k 一1 ) 一配( 七一1 ) b i d 2 。 取托( 后) 和恐( 七) 的平均值，我们得到j a c o b i 梯度迭代算法( j a c o b ig r a d i e n t i t e r a t i v ea l g o r i t h m ，简记为tj g i 算j 5 翳： x ( k ) = x i ( k ) + 】，2 ( 七) 】2 ， x a ( k ) = x ( k 一，1 ) + p d l i v a x ( k 一1 ) 一x ( k 一1 ) b 1 ， ( 2 3 7 ) 恐( 奄) 一x ( k 1 ) + 弘【c a x ( k 一1 ) 一x ( k 一1 ) 矧d 2 定理2 3 对于任意初始值x ( o ) ，当收敛因子p 满足 l i t 一2 # d l a l l 2 + ，一2 9 b d 2 1 1 2 + 2 肛d 蠢砷+ 2 妒p 2( 2 3 8 ) 时。由算法但是砂得到的速代解x ( k ) 收敛于x 倍詹一o o 其中 o t i l d l i l 2 = m a z l a i ，i = 1 ，m ， p = i i d 2 1 1 2 = m a x l b z i ，j = 1 ，弼 且一1 和口i 2 分别是矩阵a 和b 最大的奇异值 证明定义误差矩阵 贾( 七) = 冠：= x ( 七) 一x ， ， 蜀( 七) ：= 五( 詹) 一墨恐( 七) 垮x z ( k ) 一x 由( 2 2 1 ) 和( 2 3 7 ) 不难得到 置( 七) = 贾1 ( 七一1 ) + p d l 【一a 宕l 一1 ) 一矗( 七一1 ) 司， 兄( 七) 予危( 七一1 ) + “一a r 2 ( k 一1 ) 一盅( 七一1 ) 矧d 2 取r ( k ) 的2 - 范数，a - - i p a 得 0 噩l l 。= 1 1 2 , 一1 + p d l 【一a 冠一l 一冠一l 明+ p 卜月盈一- 一兄一l b 】d 2 1 1 2 = 0 【，一2 # d 1 a 】瓢一l + 兄一1 【，一2 p d 2 明 + d k l 一2 u d l 意一1 吲+ 1 2 , 一1 2 ，| 4 氟一l d 2 1 1 2 s l i t 一2 p d l a l l 2 0 兄一l i l 2 + 0 ，一2 u b d z l l 2 0 氟一1 h 2 + 0 吼一l 一2 # d l 兄一1 驯2 + 0 磊一1 一私厩一1 d 2 胁 土壹盘堂亟堂鱼逢塞： ，! 曼 由奇异值分解( s v i ) ) a = 仉1 h 和b = 巩e 2 v 2 ，其中仉，仉，k ，均为酉 矩阵( 以w = w 阢= i ，k w = k k = j r ，i = 1 ，2 ) ，并且 e 1 = d i a g ( a 1 ) ，仃i 1 嘏) ； 岛= 成叼( 蠢) ，铲世) 由【1 1 1 我们可知酉矩阵的2 范数始终为1 那么。 i l 冠一l 一2 # d 1 赢一1 b h 2 = 9 兄一1 叼k 一2 # d 1 最一l 沈砀k 2 _ 一 i i x , 一1 叼一和d 1 x h 一1 砀| 1 2 i | 1 1 2 = 0 盈一1 w 一2 # d l 盅一1 2 0 2 i l 盅一l “：+ 2 胆西2 0 冠一1 0 2 = 【1 + 2 p , a o - i 2 ) 川寇一l 2 类似的，有0 冠一l 一劫a 元一l 仍h 2 = 【l + 2 p 胁 1 ) 】| i 或一1 0 2 因此， 0 鬼1 1 2 射0 j r 一2 1 * d 1 a 2 + i i ，一2 # b d 2 1 1 2 。 + ( 1 + 2 脚p ) + ( 1 + 2 肛卢h 1 ) ) l l l 兄一1 1 1 2 令q ：一瓤0 j 一2 # d x a 2 + i f ，一2 * b d 2jj 2 + ( 1 + 2 胆盯 2 ) + ( 1 + 御妒仃i 1 ) j ， 有 0 最i i 。s 口i l 兄一- l l 。刑岛怯 因此，如果适当选择收敛因子p 使其满足q l ，也即 i l ，一2 # d 1 a l l 2 + i l ，一2 , e d 2 1 1 2 + 枷抒+ 2 “胁i 1 ) 2 ， 我们就可以得到 0 甄1 1 2 0 k 1 0 2s sf i x o i l 2 这也就表明七_ + 0 0 ，盈一o ，i e h _ x 口 注2 1 如果b = a t ，那么( 2 2 1 ) 就为连续型l y s p u n o v 矩阵方程， a x + x a t ：0 壹太堂亟堂笪堡塞! 鱼 其j a c o b i 梯度迭代算法和其收敛性窟理可以仿照f 2 3 7 ) 和定理2 3 类似得到 但此时。定理中的收敛条件( 2 3 8 ) 就化为 j r 一2 # d a i l 2 + i i ，一2 p a t d h 2 + 4 p n a l + 2 其中d l = d 2 = d ，n i l o l l 2a n d0 1 是矩阵a 最大的奇异值 在2 4 节中将给出个数值例子( 例2 3 ) 来说明j g i 方法对于l y a p u n o v 矩 阵方程求解的有效性 注2 2 其实，由上述推导j o b i 梯度迭代法的过程，不难类似得到g u 瓣 s e i d e l 梯度迭代法，如下t x ( k ) = l h ( 七) + 恐( 七) 】2 x l ( 功；x ( k 一1 ) + p ( d i + l l i t i e a x ( k 一，1 ) 一x ( k 一1 ) b 】， ( 2 3 9 ) 恐( 七) = x ( k 一1 ) + p 【c a x ( k 一1 ) 一x ( k 一1 ) b ( d 2 + 如) r 类似于定理2 2 ，对于g u a s s - s e i d e l 梯度迭代法也存在收敛性定理，如下 定理2 4 对于任意初诒值x ( o ) ，当收敛因子p 满足 i i i 一2 上( d 1 + l 1 ) t a l l 2 + 埘，- 2 j b ( d 2 + 如) r 2 + 2 ，q 卉+ 2 p p 蠢1 ) 2 ， 由算法偿只砂得到的速代解x ( k ) 收敛于x 俏七一o o 时，这里口和卢分别 是矩阵d 1 + l i 和d b + 如p 1 ，上) 2 ，二l ，如的定义同偿只j 的最大奇异值，一 和一动依然分别是矩阵a 和口最大的奇异值 证明略 但是，在后面的数值实验( 例2 4 ) 中，将会发现g u a s s - s e i d e l 梯度迭代法的 计算结果并不比j o b i 梯度迭代法好；而且，很显然。g u a s s - s e i d e l 梯度迭代 法的运算量显然比j a 0 0 _ b i 梯度迭代法的大所以。我们更倾向使用后者且在 下面的一系列推广中。也将着重于j a c o b i 梯度迭代法 2 4j a c o b i 梯度迭代法的数值例子 这部分将通过五个数值例子来验证我们给出的j a c o b i 梯度迭代算法的有 效性和实用性