线性方程组的迭代法

线性方程组的迭代法第一页，共二十八页，2022年，8月28日

快速、高效地求解线性方程组是数值线性代数研究中的核心问题，也是目前科学计算中的重大研究课题之一。各种各样的科学和工程问题，往往最终都要归结为求解一个线性方程组。线性方程组的数值解法有：直接法和迭代法。直接法：在假定没有舍入误差的情况下，经过有限次运算可以求得方程组的精确解；迭代法：从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列。第二页，共二十八页，2022年，8月28日引例：Cramer法则不可行Cramer法则n>20时，计算量太大，现实上不可行Cramer法则数学上很重要，计算上无价值第三页，共二十八页，2022年，8月28日线性方程组的迭代法迭代法：从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列。迭代解法是目前求解大规模线性方程组的主要方法。只需存储系数矩阵中的非零元素运算量不超过O(kn2)，其中k为迭代步数

(1)迭代格式的建立(3)误差估计和收敛速度研究内容：(2)收敛性判断第四页，共二十八页，2022年，8月28日解线性方程组迭代法的基本思想

迭代格式的建立Ax=bA=M-NMx=Nx

+

bk=0,1,2,…给定一个初始向量x(0)，可得迭代格式：若产生的迭代序列{x(k)}

收敛到一个确定的向量x*，则x*

就是原方程组的解。

其中

G称为迭代矩阵。第五页，共二十八页，2022年，8月28日Jacobi迭代k=0,1,2,…则可得雅可比(Jacobi)迭代格式:令A=D+L+

U，

其中称为雅可比(Jacobi)迭代矩阵第六页，共二十八页，2022年，8月28日Jacobi迭代在计算时，如果用代替，则可能会得到更好的收敛效果。此时的迭代公式为Jacobi迭代的分量形式：第七页，共二十八页，2022年，8月28日Gauss-Seidel迭代写成矩阵形式:称为GS迭代矩阵此迭代格式称为高斯-塞德尔(Gauss-Seidel)迭代k=0,1,2,…解得第八页，共二十八页，2022年，8月28日SOR迭代称为SOR迭代矩阵在GS迭代中解得低松弛法0<<1；

=1

Gauss-Seidel迭代；超松弛法1<<2为了得到更好的收敛效果，可选参数w作与上面右式的加权平均,于是就得到逐次超松弛迭代法,简称SOR迭代,其中w

称为松弛因子。收敛的必要条件0<<2。

此时第九页，共二十八页，2022年，8月28日Jacobi、GS和SOR算法

Jacobi算法

GS算法

SOR算法第十页，共二十八页，2022年，8月28日举例解：例：解线性方程组取初始向量

x(0)=(0,0,0)，迭代过程中小数点后保留4位。Jacobi迭代格式令则迭代得：x(1)=(0.5000,2.6667,-2.5000)Tx(21)=(2.0000,3.0000,-1.0000)T第十一页，共二十八页，2022年，8月28日举例（续）GS迭代格式得x(1)=(0.5000,2.8333,-1.0833)Tx(9)=(2.0000,3.0000,-1.0000)T第十二页，共二十八页，2022年，8月28日举例（续）SOR迭代格式取w=1.1，得x(1)=(0.5500,3.1350,-1.0257)Tx(7)=(2.0000,3.0000,-1.0000)T如何确定SOR迭代中的最优松弛因子是一件很困难的事。

第十三页，共二十八页，2022年，8月28日矩阵分裂法

Jacobi迭代

GS迭代

SOR迭代A=M-

NM=

D,N=M–A=-(L+U)M=

L+D,N=-U第十四页，共二十八页，2022年，8月28日5.2向量和矩阵的范数问题：如何判断向量序列是否收敛？迭代格式产生的迭代序列是否收敛？收敛与否和迭代矩阵G或向量f有没有联系？迭代序列如果收敛，是否收敛于Ax=b的解向量？定义设向量序列和向量，若则称收敛到，记作。第十五页，共二十八页，2022年，8月28日向量范数定义1)||x||0，且等号当且仅当x=0

时成立；(正定性)2)对任意实数，有

||x||＝||·||x||

；(齐次性)3)对任意

x和

y，有

||x+y||||x||+

||y||

；(三角不等式)则称||x||为向量x的范数。常见向量范数：对xRn，若存在对应的非负实数||x||，满足5.2向量和矩阵的范数第十六页，共二十八页，2022年，8月28日例子：设求它的三种常用的向量范数。向量范数第十七页，共二十八页，2022年，8月28日矩阵范数定义对ARmn，若存在对应的非负实数||A||，满足1)||A||0，且等号当且仅当A=0

时成立；(正定性)2)对任意实数，有

||A||＝||·||A||

；(齐次性)3)对任意

A和

B，有

||A+B||||A||+

||B||

；(三角不等式)则称||A||为矩阵A的范数。4)对任意

A和

B，有

||AB||||A||||B||

；(相容性)定义设A是n

阶方阵，则称为A的谱半径，其中i

为A

的特征值。第十八页，共二十八页，2022年，8月28日常见的矩阵范数

矩阵范数：（诱导范数）由向量范数||·||p

导出关于矩阵A

Rnn

的p范数:典型代表：(1-范数，列范数)(-范数，行范数)(2-范数，谱范数)第十九页，共二十八页，2022年，8月28日例子：设求它的行范数、列范数。矩阵范数第二十页，共二十八页，2022年，8月28日相容范数一般地，如果有则称这三个范数是相容

的。我们只考虑：(1)A

为方阵；(2)

具有相容性的范数。算子范数总是相容的：

相容性：对任意

A和

B，有

||AB||||A||||B||

第二十一页，共二十八页，2022年，8月28日向量序列的收敛定理其中||·||

为任一向量范数。定义对任意xRn都成立，则称||·||

和

||·||

是等价的。若存在常数C1,C2

>0使得Rn上的所有向量范数都是等价的。第二十二页，共二十八页，2022年，8月28日迭代收敛的判断条件预备定理：若方阵G的某种范数则矩阵I-G为非奇异矩阵。定理4(充分条件)：若方阵G的某种范数则迭代法对于任意初值x(0)都收敛于方程组的唯一解x*.第二十三页，共二十八页，2022年，8月28日5.3迭代法过程的收敛性定理(全局收敛性)设迭代矩阵G的某种范数||G||<1，则x=Gx+f存在唯一解，且对任意初值,迭代序列x(k)=Gx(k-1)+f

收敛于x*，进一步有误差估计式证明略后验估计先验估计第二十四页，共二十八页，2022年，8月28日直接从Ax=b判断定理若A按行严格对角占优(),则解Ax=b的Jacobi迭代和Gauss-Seidel迭代均收敛。证明：由A严格对角占优，则无穷大范数||G||<1Jacobi迭代(直接证||G||1<1)Gauss-Seidel迭代,令y=Gx，则y=-D-1(Ly+Ux)先证对任意||x||1=1,||y||1<1再证存在某||x||1=1,使||G||1=||y||1第二十五页，共二十八页，2022年，8月28日定理

若A按行严格对角占优(),则解

的Jacobi迭代和Gauss-Seidel迭代均收敛。由A按行严格对角占优,再由定理3.4知迭代收敛。令，则有即写出分量形式有证:令雅可比迭代公式的迭代矩阵为再考察高斯-赛德尔迭代公式的迭代矩阵第二十六页，共二十八页，2022年，8月28日设