《非线性方程迭代资料》由会员分享,可在线阅读,更多相关《非线性方程迭代资料(8页珍藏版)》请在金锄头文库上搜索。
1、线性代数及其应用一个有理矩阵方程的一个新的逆向方法概念:采用古典牛顿舒尔茨法找到一个非奇异的可逆矩阵,我们开发了一个新的 逆向方法获得有理矩阵方程X+ A?X- 1A = I的最小 hermitian 正定解,这里 I 是单 位矩阵,A 是一个给定的非奇异矩阵。 我们目前的收敛性结果和讨论该方法的稳 定性能时,从可用矩阵 AA?开始,我们也提出数值结果比较我们与一些以前开发 的逆向技术建议,以解决同与其相适应的矩阵方程。1.绪论 下面的矩阵方程的最小hermitian 正定解我们是很有兴趣的 X+ A?X- 1A = I, (1) 这里 A 是一个 n n的实或复的非奇异矩阵, I 是 n 阶
2、的单位矩阵。 它成立于 3, 如果( 1)有 hermitian 正定解,那么它有一个最大的hermitian 解记为 X+,和一 个最小的 hermitian 记为X-。这个最大解 X+能通过 X+= I - Y-,获得,这里Y-是偶 矩阵方程 Y+ AY- 1A?= I的最小解。参见 4有关于( 1)的解的存在性进一步理 论结果。 方程(1)出现在互惠平稳高斯过程的分析在有限的时间间隔(见5),在最优控 制理论的领域,它关系到一个代数Riccati 的卡尔曼滤波理论中所产生型方程7 使用知名的 hermitian 矩阵的 Lowner 有序( A ? (A B)表示 A - B是一个正定(
3、半正定)矩阵),认为: 0 X- 1,因此 X 00 0 0,那么 2Y- YWY W- 1, (6) 细节见文献 9,引理 3.2.因为A(I - Xj)- 1A? 0,对于 j=0,1,k,由(3)至(6),得Xj+1= 2Xj- XjA-?(I - Xj)A- 1XjA-?(I - Xj)A- 1- 1= A(I - Xj)- 1A?. (7) 结合( 5)与( 7),有Xj+1X-,令j = k时,得到 Xk+1X-. 现在,我们将证明 Xk是单调增的。使用( 3)和X0= AA?,我们有 X1= 2AA?- A(I - AA?)A?= AA?+ A(AA?)A?= X0+ A(AA?
4、)A?. 因此, X1- X0= A AA?A?0 . 我们需要证明 Xk+1- Xk0,由( 3)我们有 Xk+1- Xk= Xk- XkA-?(I - Xk)A- 1Xk= XkXk- 1- A-?(I - Xk)A- 1Xk. (8) 由(8)可以充分得到 Xk- 1A-?(I - Xk)A- 1. 现在我们假设归纳: XkXk- 1.使 用的是一个类似获得( 5)的过程,我们有A(I - Xk)- 1A?A(I - Xk - 1)- 1A?.(9)使用( 7)和j = k - 1,得A(I - Xk - 1)- 1A?Xk. (10)最后由( 9)和( 10)得 A(I - Xk)-
5、1A?XkXk- 1A-?(I - Xk)A- 1, 要求。 到目前为止,我们已经建立的序列Xk 的上界是 X-,且是单调增的。因此,它 是一个收敛序列。这里 Xk的极限是 X,显然满足 0 1,X-+ A?是可逆的。由于 X-+ A?= (X-A-?+ I)A?. 那么P = X-A-? 的所有特征值必须在封闭的单位圆盘,以保证对所有的 | | 1, X-A-?+ I都是非 奇异。因此 (P) 1,其中 (P) 表示P的谱半径。整个本节的其余部分,我们将 假设一分乘法矩阵规范正在使用,对于任何给定矩阵C,有C =C? .两个同 时满足的重要的规范,是光谱范数和Frobenius范数。定理 2
6、.4,如果 X-A-? 1,那么迭代( 3)表示一个稳态的方案。证明:让我们考虑迭代 (3),作为Xk+1= G(Xk)的固定点, 其中 G 是定义在(4) 中; 设?k是(3)中的 k 次迭代的数值扰动,并且令 Xk= Xk+ ?k. 对 G 绕Xk利用泰勒展开得到 Xk+1= G(Xk) = G(Xk+ ?k) = G(Xk) + G(Xk)?k+ R ?k.(11) 这R ?k满足, lim?k 0 R ?k / ?k = 0. 由XkX-, 利用引理 2.2 和 (11) ,有?k+1= GX-?k+ R(?k ) = X-A-?kA- 1X-+ R(?k) = P?kP?+ R(?k
7、 ) . (12)由(12),得到 ?k+1P 2?k + R(?k) , (13) 能再次得到 ?k+1P 2(k+1)?0+P 2(k - j) R(?j) k j=0. (14)因 P 1, 有 ?k+1 是一个有界值,这表明迭代(3)代表一个稳定的方案。 我们现在讨论( 3)的收敛速度。命题 2.5.(3)中产生的序列 Xk,由X0= AA?,满足 Xk+1- X- Xk- X- X- 1 + XkA-?2 Xk- X- . 证明:由定理 2.3,我们知道 limk Xk= X-.由(3)得 Xk+1= 2Xk- XkA-? I - X- (Xk- X-)A- 1X k.由X-解答问题
8、( 2),则 I - X-= A?X- 1A,并且有Xk+1= 2Xk- XkA-?A?X- 1A - (Xk- X-)A- 1Xk = 2Xk- XkX- 1Xk+ XkA-?(Xk- X-)A- 1Xk. (15) 从(15)的两边减去 X-,得到 Xk+1- X-= -X- 2Xk+ XkX- 1Xk+ XkA-?(Xk- X-)A- 1Xk = -Xk- X-X- 1Xk- X-+ XkA-?(Xk- X-)A- 1X k(16) 根据( 16)和Xk= Xk?,我们有 Xk+1- X- Xk- X-2 X- 1 + XkA-?2 Xk- X- (17)= Xk-X- X- 1 + X
9、kA-?2 Xk- X- (18)现在由limk Xk- X- X- 1 + XkA-?2 = X -A-?2,则收敛结果能得到。定理 2.6. 设 A 是一个非奇异的矩阵,设 Xkk 0是由迭代( 3)生成的序列 ,且X0= AA?。对 于任意的 ? 0,我们有 Xk+1- X- (X-A-?2+ ?) Xk- X- , 对所有足够大的 k 成立。 注意,对于迭代( 3),作为定理 2.6 的一个结果,对于任何的 X-A-? 1, 都有 q 线性收敛。3.数值试验。 所有实验均运行在奔腾IV,3.4 GHZ,利用 Matlab7. 我们报告所要求的迭代的 数量,程序停止时的规范和矩阵乘数的数
10、量要求。在我们的执行中, 我们立刻停 止所有的算法时,剩余的 Frobenius范数小于 10- 15。 我们与迭代(3) 比较(NS) , 和用逆向法求解( 2),在所有情况下,我们还应说明初步的推测,以确保其收 敛性。 在2,EL-Sayed和 AL-Dbiban 提出以下迭代M1:Yk+1=I - XkYk+ I , Xk+1= I - A?Yk+1A,初始值有 y0=x0=I。在6,Guo 和 Lancaster提出以下迭代M2: Yk+1= Yk2I - XkYk , Xk+1= I - A?Y k+1A,初始值有 y0=x0=I。在9,Zhan 提出以下迭代M3:Xk+1= I -
11、 A?YkA , Yk+1= Yk2I - XkYk,初始值有 y0=x0=I。重要的是要注意到, M2 和 M3 生成一个 hermitian 序列,且要求每次迭代产生4 个矩阵乘数,而 M1 需每次迭代产生 3 个矩阵乘数,但不会产生 hermitian 序列。 另一方面,因为 NS,产生一个 hermitian 序列Xk, 我们有 NS 迭代有每次迭代产生3 个矩阵乘数,且可逆矩阵A 只在开头。算法 1,迭代 NS 1:给定A Cnn和X0= AA? 2:令Ai = A- 1 3:k=0,1直到其收敛 4:令Tk= AiXk5:令Xk+1= 2Xk- Tk?(I - X k)Tk6:结束
12、由于 NS 收敛于 X-,而所有其他方案收敛于X+,我们利用 NS找到( 2)的最小 解,且用其他三个方案找到偶方程G X = X+ AX- 1A?- I的最大解。因此,“ Res” 的值在我们的报表 F(Xk) F里为 NS,这 G(Xk) F为这一进程停止时的其他方 法。因此,为了衡量我们的近似精度,我们还检查每个实验= Xk- (I - Xk) F是一个 “ 小数“ , 其中Xk是通过竞争得到 G 的最大近似解 ,这Xk是(2)的最大解的近似值。对所有的10- 16, 是希腊的第五字 母。以下实验均取自关于这一主题的文献。实验 1.在第一个实验中,考虑方程( 1),A 是1中例 3.1
13、给出时 . A =0.1- 0.15- 0.2598076 0.150.2125- 0.0649519 0.2598076- 0.06495190.137. 在表 1 的报告结果中,表明NS 需要每迭代次数的矩阵乘数最少,而M3 需要最 大。实验 2.在这试验中,我们求解方程( 1),这里 A 是定义在 9中的例 2 中。结 果见报表 2. 表 1. NS 的性能, M1,M2,M3 为实验 1 中求解( 1). 方案迭代剩余MM NS 18 2.4466e-16 54 M1 233.4606e-16 69 M2 18 4.235e-17 72 M3 33 5.467e-16 132表 2.
14、NS 的性能, M1,M2,M3 为实验 2 中求解( 1). 方案迭代剩余MM NS 27 9.384e-16 81 M1 48 5.7084e-16 144 M2 27 8.1694e-16 108 M3 52 5.707e-16 208 表 3. NS 的性能, M1,M2,M3 为实验 3 中求解( 1). 方案迭代剩余MM NS 17 9.4001e-16 51 M1 6 4.7227e-16 18 M2 6 3.4158e-17 24 M3 10 3.4356e-17 40 表 4. NS 的性能, M1,M2,M3 为实验 4 中求解( 1). 方案迭代剩余MM NS 123 7
15、.1803e-16 369 M1 263 8.8503e-16 789 M2 122 6.4394e-16 488 M3 240 7.8908e-16 960 表 5. NS 的性能, M1,M2,M3 为实验 5 中求解( 1). 方案迭代剩余MM NS 4 9.5158e-16 12 M1 5 4.1763e-17 15 M2 4 3.7695e-16 16 M3 6 3.7693e-16 24 A =1402- 1 7634 - 59 48 - 35106 28. 我们可以看到,在表 2, M3 需要比其他三种方法更多的迭代和更多的矩阵乘数, 以满足停止准则。 还可以看到, NS 需要与 M2 相同数量的迭代,以满足其收敛,但是它的矩阵乘 数要比其他所有方法少。实验 3.在这个测试中,矩阵A 为2的例 3.1 A =1 320.2- 0.1 - 0.10.6- 0.50.1 - 0.50.7 - 0.5- 0.5 0.10.70.10.8 0.80.5. 在表 3.我们看到NS 需要比其他方法更多的迭代,以满足其收敛, 然而,值得一 提的是, NS 产生一个很好的逼近方程( 1)的解的近似值,其迭代次数为6,的 确, F(X