论文部分内容阅读
[摘要] 对于非对称线性方程组Ax = b, 当A 是正定可对称化矩阵时,本文结合預对称化技术和Gauss-Seidel 迭代算法, 同时在Gauss-Seidel 迭代算法中加入一个松弛因子而导出了预对称Gauss-Seidel 松弛迭代算法,并且证明了当松弛因子满足一定条件时,该算法总是收敛的.数值例子表明该算法优于Gauss-Seidel迭代算法.
[关键词] 正定可对称化矩阵 Gauss-Seidel 迭代 松弛因子
中图分类号：O122.2文献标识码：A文章编号：1009-9646(2008)07-0000-00
1 引言
考虑大型稀疏线性代数方程组Ax =b,的求解，求解方法可分为两大类:直接法和迭代法。由于直接解法在进行矩阵分解时常引入大量填充元，导致存储量与计算量很大，而且当系数矩阵条件数很大时，直接法稳定性差。为利用系数矩阵的稀疏结构以尽可能减少存储空间和计算开销，迭代法成为求解(1)的主要方法。常见的迭代算法有Jacobi 和Gauss-Seidel迭代算法。然而Gauss-Seidel迭代算法并不能保证对所有的矩阵A 都收敛。当系数矩阵是大型稀疏的正定可对称化矩阵时，文[1,2] 讨论了一类预对称化技术。文[3]通过向Gauss-Seidel 迭代算法中加入松弛因子而导出一种松弛迭代算法，证明了对所有的对称正定矩阵A都具有收敛性，本文基于文[1,2]的预对称化技术及文[3]的松弛迭代算法，提出对一类非对称线性方程组的预对称Gauss-Seidel 松弛迭代算法。
2 预对称化技术
定义2.1. 矩阵A 称为正定可对称化矩阵,是指满足以下二个条件:
1. A 正定: (Au; u)> 0，
2. A 相似于对称正定矩阵，即存在非奇异矩阵W 与对称正定矩阵使得A =。
性质2.1. A 为p.d.s (正定可对称化矩阵) 为p.d.s 为p.d.s 为p.d.s。
性质2.2. 定义p.d.s 阵的条件数(A) = 。 设为p.d.s 阵，且W 为块对角矩阵,则Schur补C =也为p.d.s 阵，且满足(C)(A)。
定义2.2. 矩阵B 称为p.d.s 矩阵A 的预条件子,是指满足以下四个性质:
1. B 为 的某些近似。
2. 矩阵乘向量运算Bu简单易行。
3. BA 正定: (BAu, u)>0;
4. (BA) <(A).
引理2.1. 若A = tridiag(); > 0。令D = diag(1,… , ()),则DAD =tridiag() 为对称矩阵,且A 的特征值全为实数.
结合引理(2.1),我们来讨论下面的微分方程模型。
常微分方程的二点边值问题:
+ 2a + bu = f， u(0) = u(1) = 0,采用中心差分格式,离散微分方程为Au = ,对于等距情况(h = 1/(n + 1)),A =tridiag(-(1 + ah),(2 + bh),-(1- ah))。
定理2.1.当 1 时,令D = diag(1,…)， 则DAD= tridiag(-, (2 + bh),-).
3 Gauss-seidel 松弛迭代算法
下面给出Gauss-seidel 松弛迭代算法思想: 设A =将其分解为A = D -L -U, 其中D 为A 的对角阵, -L 和-U 分别为A 的严格下三角和严格上三角矩阵.
Gauss-seidel 算法的迭代过程为:(D -L)x=Ux + b; k = 0, 1, …(2)
由文[3]可知该方法收敛的充要条件为<1.文[3]通Gauss-seidel 算法加入松弛因子而导出一种Gauss-seidel松弛迭代算法.设为松弛因子,将矩阵A 分解为A = (D- L) -(U + (- 1)D) = D1- U1 其中D1 = D- L, U1 = U + (- 1)D. 迭代过程为:D1 x = U1 x + b, k = 0, 1, 2, …(3)
该方法收敛的充要条件为< 1.
4 预对称Gauss-Seidel 松弛迭代算法及收敛性
基于定理(2.1)构造而得非对称线性方程组的LR-预对称因子.令M = D. 则方程组(1) 变为MAMx = Mb. 这样我们结合预对称化技术,即可得新算法的思想:设线性方程组(1) 的系数矩阵A 为正定可对称化矩阵,则(1) 等价为
;A = MAM;= M;= Mb(4)
将矩阵分解为=(-)-(+(- 1)) = -其中= -,=+(- 1),为 的对角阵, - 为 的严格下三角矩阵.迭代过程为: (5)
引理4.1. Gauss-seidel松弛迭代算法对任意初始向量x收敛的充要条件是.
定理4.1. 设为正定可对称化矩阵,上述算法收敛的充要条件是.
证: 因为(6)
设为的特征值,y为对应于的特征向量,则(7)
所以的每一个特征值,当 1时,有 .反之,若02,有 1 , 即 1,由引理(4.1)可得结论成立.
定理4.2. 设线性方程组(1) 的系数矩阵A 为正定可对称化矩阵,则预对称Gauss-Seidel松弛迭代算法对任意初始向量x(0) 收敛的充要条件是
证: 必要性:设为迭代矩阵的全部特征值.
T=tridiag(-0.4,4,-1.6), I, T b =,易知方程组Ax = b 的精确解为x =.令M = diag(1,1/2, 1/4, 1/2, 1/4,1/8, 1/4, 1/8, 1/16), = tridiag(-0.8I,T,-0.8I), T =tridiag(-0.8, 4,-0.8),I, T; =用预对称Gauss-Seidel 松弛迭代算法,取精度为0.000001, 初始向量,取,只需要迭代8 次就可得满足要求的解，直接用Gauss-Seidel 松弛迭代算法需要9 次迭代, 直接用Gauss-Seidel 迭代算法需要14 次迭代,预对称化后用Gauss-Seidel 迭代算法需要13 次迭代得到满足精度要求的解. 它们证明了预对称Gauss-Seidel 松弛迭代算法的优势.更为重要的是，只要选取松弛因子大于1/2 ,该算法总是收敛的. 这拓宽了Gauss-
Seidel 迭代算法的应用范围.
参考文献
[1] 孙家昶. 正定可对称化矩阵与预对称迭代算法.计算数学, 2000, 22: 379-384.
[2] 李文军. 关于非对称线性方程组的新迭代算法.数值计算与计算机应用, 2001, 22: 71-80.
[3] 朱绍文,武继刚. 求解线性方程组的一种松弛迭代算法及其收敛性.华中师范大学学报（自然科学版）,1995, 29: 159-162.
[4] Saad Y. Iterative methods for sparse linear systems [ M ] . Boston PWS Publication Corporation ,1996.
[5] 白中治,仇寿霞.关于具优势对称部分的不定线性代数方程组的分裂极小残量算法.计算数学,2002,24:113-128.
[6] 李维国,陈金海.关于正定可对称化线性代数方程组的预对称正则化算法.高等学校计算数学学报,2006,28:151-161.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
[关键词] 正定可对称化矩阵 Gauss-Seidel 迭代 松弛因子
中图分类号：O122.2文献标识码：A文章编号：1009-9646(2008)07-0000-00
1 引言
考虑大型稀疏线性代数方程组Ax =b,的求解，求解方法可分为两大类:直接法和迭代法。由于直接解法在进行矩阵分解时常引入大量填充元，导致存储量与计算量很大，而且当系数矩阵条件数很大时，直接法稳定性差。为利用系数矩阵的稀疏结构以尽可能减少存储空间和计算开销，迭代法成为求解(1)的主要方法。常见的迭代算法有Jacobi 和Gauss-Seidel迭代算法。然而Gauss-Seidel迭代算法并不能保证对所有的矩阵A 都收敛。当系数矩阵是大型稀疏的正定可对称化矩阵时，文[1,2] 讨论了一类预对称化技术。文[3]通过向Gauss-Seidel 迭代算法中加入松弛因子而导出一种松弛迭代算法，证明了对所有的对称正定矩阵A都具有收敛性，本文基于文[1,2]的预对称化技术及文[3]的松弛迭代算法，提出对一类非对称线性方程组的预对称Gauss-Seidel 松弛迭代算法。
2 预对称化技术
定义2.1. 矩阵A 称为正定可对称化矩阵,是指满足以下二个条件:
1. A 正定: (Au; u)> 0，
2. A 相似于对称正定矩阵，即存在非奇异矩阵W 与对称正定矩阵使得A =。
性质2.1. A 为p.d.s (正定可对称化矩阵) 为p.d.s 为p.d.s 为p.d.s。
性质2.2. 定义p.d.s 阵的条件数(A) = 。 设为p.d.s 阵，且W 为块对角矩阵,则Schur补C =也为p.d.s 阵，且满足(C)(A)。
定义2.2. 矩阵B 称为p.d.s 矩阵A 的预条件子,是指满足以下四个性质:
1. B 为 的某些近似。
2. 矩阵乘向量运算Bu简单易行。
3. BA 正定: (BAu, u)>0;
4. (BA) <(A).
引理2.1. 若A = tridiag(); > 0。令D = diag(1,… , ()),则DAD =tridiag() 为对称矩阵,且A 的特征值全为实数.
结合引理(2.1),我们来讨论下面的微分方程模型。
常微分方程的二点边值问题:
+ 2a + bu = f， u(0) = u(1) = 0,采用中心差分格式,离散微分方程为Au = ,对于等距情况(h = 1/(n + 1)),A =tridiag(-(1 + ah),(2 + bh),-(1- ah))。
定理2.1.当 1 时,令D = diag(1,…)， 则DAD= tridiag(-, (2 + bh),-).
3 Gauss-seidel 松弛迭代算法
下面给出Gauss-seidel 松弛迭代算法思想: 设A =将其分解为A = D -L -U, 其中D 为A 的对角阵, -L 和-U 分别为A 的严格下三角和严格上三角矩阵.
Gauss-seidel 算法的迭代过程为:(D -L)x=Ux + b; k = 0, 1, …(2)
由文[3]可知该方法收敛的充要条件为<1.文[3]通Gauss-seidel 算法加入松弛因子而导出一种Gauss-seidel松弛迭代算法.设为松弛因子,将矩阵A 分解为A = (D- L) -(U + (- 1)D) = D1- U1 其中D1 = D- L, U1 = U + (- 1)D. 迭代过程为:D1 x = U1 x + b, k = 0, 1, 2, …(3)
该方法收敛的充要条件为< 1.
4 预对称Gauss-Seidel 松弛迭代算法及收敛性
基于定理(2.1)构造而得非对称线性方程组的LR-预对称因子.令M = D. 则方程组(1) 变为MAMx = Mb. 这样我们结合预对称化技术,即可得新算法的思想:设线性方程组(1) 的系数矩阵A 为正定可对称化矩阵,则(1) 等价为
;A = MAM;= M;= Mb(4)
将矩阵分解为=(-)-(+(- 1)) = -其中= -,=+(- 1),为 的对角阵, - 为 的严格下三角矩阵.迭代过程为: (5)
引理4.1. Gauss-seidel松弛迭代算法对任意初始向量x收敛的充要条件是.
定理4.1. 设为正定可对称化矩阵,上述算法收敛的充要条件是.
证: 因为(6)
设为的特征值,y为对应于的特征向量,则(7)
所以的每一个特征值,当 1时,有 .反之,若02,有 1 , 即 1,由引理(4.1)可得结论成立.
定理4.2. 设线性方程组(1) 的系数矩阵A 为正定可对称化矩阵,则预对称Gauss-Seidel松弛迭代算法对任意初始向量x(0) 收敛的充要条件是
证: 必要性:设为迭代矩阵的全部特征值.
T=tridiag(-0.4,4,-1.6), I, T b =,易知方程组Ax = b 的精确解为x =.令M = diag(1,1/2, 1/4, 1/2, 1/4,1/8, 1/4, 1/8, 1/16), = tridiag(-0.8I,T,-0.8I), T =tridiag(-0.8, 4,-0.8),I, T; =用预对称Gauss-Seidel 松弛迭代算法,取精度为0.000001, 初始向量,取,只需要迭代8 次就可得满足要求的解，直接用Gauss-Seidel 松弛迭代算法需要9 次迭代, 直接用Gauss-Seidel 迭代算法需要14 次迭代,预对称化后用Gauss-Seidel 迭代算法需要13 次迭代得到满足精度要求的解. 它们证明了预对称Gauss-Seidel 松弛迭代算法的优势.更为重要的是，只要选取松弛因子大于1/2 ,该算法总是收敛的. 这拓宽了Gauss-
Seidel 迭代算法的应用范围.
参考文献
[1] 孙家昶. 正定可对称化矩阵与预对称迭代算法.计算数学, 2000, 22: 379-384.
[2] 李文军. 关于非对称线性方程组的新迭代算法.数值计算与计算机应用, 2001, 22: 71-80.
[3] 朱绍文,武继刚. 求解线性方程组的一种松弛迭代算法及其收敛性.华中师范大学学报（自然科学版）,1995, 29: 159-162.
[4] Saad Y. Iterative methods for sparse linear systems [ M ] . Boston PWS Publication Corporation ,1996.
[5] 白中治,仇寿霞.关于具优势对称部分的不定线性代数方程组的分裂极小残量算法.计算数学,2002,24:113-128.
[6] 李维国,陈金海.关于正定可对称化线性代数方程组的预对称正则化算法.高等学校计算数学学报,2006,28:151-161.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”