_解线性方程组的迭代法

《_解线性方程组的迭代法》由会员分享，可在线阅读，更多相关《_解线性方程组的迭代法（77页珍藏版）》请在金锄头文库上搜索。

1、第6章 解线性方程组的迭代方法,6.1 引言 6.2 基本迭代法 6.3 迭代法的收敛性 6.4* 分块迭代法,其中A为非奇异矩阵, 当A为低阶稠密矩阵时, 第5章讨论的选主元消去法是有效的. 但对于大型稀疏矩阵方程组(A的阶数n很大，但零元素较多), 利用迭代法求解是合适的.,本章将介绍迭代法的一些基本理论及雅可比迭代法，高斯-赛德尔迭代法，超松弛迭代法，而超松弛迭代法应用很广泛。,下面举简例，以便了解迭代法的思想.,对线性方程组,Ax=b， (1.1),6.1 引 言,例1 求解方程组,记为Ax=b，其中,方程组的精确解是x*=(3,2,1)T. 现将改写为,或写为x=B0x+f，其中,我

2、们任取初始值，例如取x(0)=(0, 0, 0)T. 将这些值代入(1.3)式右边(若(1.3)式为等式即求得方程组的解，但一般不满足)，得到新的值 x(1)=(x1(1), x2(1), x3(1)T =(3.5, 3, 3)T ，再将x(1)分量代入(1.3)式右边得到 x(2)，反复利用这个计算程序，得到一向量序列和一般的计算公式(迭代公式),简写为 x(k+1)=B0x(k) +f，,其中k表示迭代次数(k=0,1,2,).,迭代到第10次有,从此例看出，由迭代法产生的向量序列x(k)逐步逼近方程组的精确解是x*=(3,2,1)T. 即有,对于任何一个方程组x=Bx+f(由Ax=b变形

3、得到的等价方程组)，由迭代法产生的向量序列x(k)是否一定逐步逼近方程组的解x*呢？回答是不一定. 请同学们考虑用迭代法解下述方程组,但 x(k)并不是所有的都收敛到解x*！,对于给定方程组x=Bx+f，设有唯一解x*，则,x*=Bx*+f . (1.5),又设x(0)为任取的初始向量, 按下述公式构造向量序列,x(k+1)=Bx(k)+f , k=0,1,2,. (1.6),其中k表示迭代次数.,定义1 (1)对于给定的方程组x=Bx+f , 用公式(1.6)逐步代入求近似解的方法称为迭代法(或称为一阶定常迭代法，这里B与k无关). B称为迭代矩阵.,(2) 如果limx(k) (k)存在(

4、记为x*), 称此迭代法收敛, 显然x*就是方程组的解, 否则称此迭代法发散.,由上述讨论，需要研究x(k)的收敛性. 引进误差向量,由(1.6)减去(1.5)式，得(k+1)=B(k)(k=0,1,2,)，递推得,要考察x(k)的收敛性，就要研究B在什么条件下有lim(k)=0 (k)，亦即要研究B满足什么条件时有Bk0(零向量) (k) .,6.2 基本迭代法,其中，A=(aij)Rnn为非奇异矩阵，下面研究任何建立Ax=b的各种迭代法.,设线性方程组,Ax=b， (2.1),其中，M为可选择的非奇异矩阵，且使Mx=d容易求解，一般选择A的某种近似，称M为分裂矩阵.,将A分裂为,A=M-N

5、. (2.2),于是，求解Ax=b转化为求解Mx=Nx+b ，即求解,可构造一阶定常迭代法,其中 B=M-1N=M-1(M-A)=I-M-1A ， f=M-1b. 称 B=I-M-1A为迭代法的迭代矩阵，选取M矩阵，就得到解Ax=b的各种迭代法.,设aii0 (i=1,2,n)，并将A写成三部分,即 A=D-L-U,6.2.1 雅可比(Jacobi)迭代法,设aii0 (i=1,2,n)，选取M为A的对角元素部分,即选取M=D(对角阵)，A=D-N，由(2.3)式得到解方程组Ax=b的雅可比(Jacobi)迭代法. 又称简单迭代法.,其中B=I-D-1A=D-1(L+U)=J, f=D-1b.

6、 称J为解Ax=b的雅可比迭代法的迭代矩阵.,于是雅可比迭代法可写为矩阵形式,其Jacobi迭代矩阵为,下面给出雅可比迭代法(2.5)的分量计算公式, 记,由雅可比迭代法(2.5)有,每一个分量写出来为,即当aii0时，有,等 价 方 程 组,其中 aii(i)0 (i=1,2,n),即由方程组Ax=b得到的,建立的雅可比迭代格式为,于是，解Ax=b的雅可比迭代法的计算公式为,由(2.6)式可知，雅可比迭代法计算公式简单，每迭代一次只需计算一次矩阵和向量的乘法且计算过程中原始矩阵A始终不变.,6.2.2 高斯赛德尔迭代法,在 Jacobi 迭代中，计算 xi(k+1)(2 i n)时，使用xj

7、(k+1)代替xj(k) (1 j i-1)，即有,建 立 迭 代 格 式,或缩写为,称为高斯塞德尔(Gauss Seidel)迭代法.,其Gauss Seidel迭代矩阵为,BG = (D-L)-1U,于是高斯塞德尔迭代法可写为矩阵形式,这就是说，选取分裂矩阵M为A的下三角部分, 即选取M= D-L(下三角阵)，A=M-N，由(2.3)式得到解Ax=b的高斯塞德尔(Gauss Seidel)迭代法.,其中B=I-(D-L)-1A= (D-L)-1U=G, f=(D-L)-1b. 称矩阵G=(D-L)-1U为解Ax=b的高斯塞德尔迭代法的迭代矩阵.,由高斯塞德尔迭代法(2.7)有,每一个分量写

8、出来为,即当aii0时，有(与前面一样的式子),或,于是，解Ax=b的高斯塞德尔迭代法的计算公式为,或,雅可比迭代法不使用变量的最新信息计算xi(k+1)，而由高斯塞德尔迭代公式(2.8)可知，计算x(k+1)的第 i个分量xi(k+1)时，利用了已经计算出的最新分量xj(k+1) (j=1,2,i-1). 可看作雅可比迭代法的一种改进. 由(2.8)可知，高斯塞德尔迭代公式每迭代一次只需计算一次矩阵与向量的乘法.,算法1(高斯塞德尔迭代法) 见书p239.,例2 用高斯塞德尔迭代法解例1的方程组(1.2).,解 用高斯塞德尔迭代公式：取x(0)=(0, 0, 0)T.,迭代到第7次有,由此例

9、可知，用高斯塞德尔迭代法，雅可比迭代法解线性方程组(1.2)(且取x(0)=0)均收敛，而高斯塞德尔迭代法比雅可比迭代法收敛较快(即取相同的x(0)，达到同样精度所需迭代次数较少)，但这结论只当A满足一定条件时才是对的.,例1 用雅可比迭代法解方程组,解： Jacobi 迭代格式为,取 x(0)=(0,0,0)T 计算结果如下：,解：Gauss-Seidel 迭代格式为,例2 用GaussSeidel 迭代法解上题.,取 x(0)=(0,0,0)T 计算结果如下：,6.2.3 解大型稀疏线性方程组的逐次超松弛法(SOR方法),我们取0为松弛因子，建立迭代格式如下,即,或改写为,其逐次超松弛迭代

10、矩阵为,逐次超松弛法可写为矩阵形式,称为逐次超松弛迭代法，简称SOR方法.,显然，=1就是GaussSeidel 迭代法.,下面用矩阵方法推导，选取分裂矩阵M为带参数的下三角矩阵,从而得到解Ax=b的逐次超松弛迭代法 (Successive Over Relaxation Method，简称SOR方法).,其中0为可选择的松弛因子.,于是，由(2.3)可构造一个迭代法，其迭代矩阵为,解Ax=b的SOR方法为.,其中,下面给出解Ax=b的SOR方法的分量计算公式. 记,由(2.10)式可得,由此，得到解Ax=b的SOR方法的计算公式,或,(1) 显然，当=1时即为GaussSeidel 迭代法.

11、,(2) SOR方法每迭代一次主要运算量是计算一次矩阵与向量的乘法.,(3) 当1时，称为超松弛法；当1时，称为低松弛法.,(4) 在计算机实现时可用,控制迭代终止，或用,控制迭代终止.,SOR迭代法是GaussSeidel 迭代法的一种修正，可由下述思想得到.,设已知x(k)及已计算x(k+1)的分量xj(k+1) (j=1,2,i-1).,(1) 首先用GaussSeidel 迭代法定义辅助量 ,(2) 再由 与 加权平均定义 ，即,将(2.13)代入(2.14)得到解Ax=b的SOR迭代(2.11)式.,例3 用SOR迭代法解方程组. 见书p242.,6.3 迭代法的收敛性,6.3.1

12、一阶定常迭代法的基本定理,其中，A=(aij)Rnn为非奇异矩阵，记x*为(3.1)精确解，且设有等价的方程组,设线性方程组,Ax=b， (3.1),于是,设有解Ax=b的一阶定常迭代法,有意义的问题是：迭代矩阵B满足什么条件时，由迭代法产生的向量序列x(k)收敛到x*.,引进误差向量,由(3.3)式减(3.2)得到误差向量的递推公式,由6.1节可知，研究迭代法(3.3)收敛性问题就是要研究迭代矩阵B满足什么条件时，有.,定义2 设有矩阵序列 Ak=(aij(k)Rnn 及A=(aij)Rnn，如果n2个数列极限存在且有,则Ak称收敛于A，记为lim (k).,例4 设有矩阵序列Ak, 其中A

13、k=Bk,而,且设|1，考查矩阵序列极限.,解 显然, 当|1时, 则有,矩阵序列极限概念可以用矩阵算子范数来描述.,定理1 其中|为矩阵的任意一种算子范数.,证明 显然有,再由矩阵范数的等价性, 则定理对其它算子范数亦对.,定理2,证明作为练习.,定理3 设B=(bij)Rnn，则limBk=0 (k)(零矩阵)的充分必要条件是矩阵B的谱半径(B)1.,证明 由矩阵B的若当标准形,存在非奇异矩阵P使,其中若当(Jordan)块,且 ，显然有,其中,显然有, Et,0=I, Et,k=0(当kt)，(Et,1)k= Et,k. 由于Ji=I+Et,1 ，因此,下面考查Jik的情况. 引进记号,

14、其中,定理4(迭代法基本定理) 设有方程组,x=Bx+f. (3.4),及一阶定常迭代法,x(k+1)=Bx(k)+f. (3.5),对任意选择初始向量x(0)，迭代法(3.5)收敛的充要条件是矩阵B的谱半径(B)1.,证明 充分性. 设(B)1，易知Ax=f(其中A=I-B)有唯一解，记为x*，则,x*=Bx*+f.,误差向量,由设(B)1，应用定理3，有 . 于是对任意x(0)有 ，即 .,其中x(k+1)=Bx(k)+f . 显然，极限x*是方程组(3.4)的解，且对任意x(0)有,必要性. 设对任何x(0)有,由定理2知,再由定理3，即得(B)1.,定理4是一阶定常迭代法的基本理论.,

15、定理3和定理4的结论和起来即为,(1) 迭代法x(k+1)=Bx(k)+f 收敛limBk=O；,(2) 迭代法x(k+1)=Bx(k)+f 收敛(B)1.,推论 设Ax=b，其中A=D-L-U为非奇异矩阵且D非奇异矩阵，则有,(1) Jacobi迭代法收敛(J)1, 其中J=D-1(L+U).,(2) G-S迭代法收敛(G)1, 其中G=(D-L)-1U.,(3) SOR迭代法收敛(L)1, 其中 L=(D-L)-1(1-)D+U.,例5 考察用Jacobi方法解方程组(1.2)的收敛性.,解 因为方程组(1.2)的矩阵A及迭代矩阵J为,解得,即(J)1. 所以用Jacobi方法解方程组(1.2)是收敛的.,得迭代矩阵J的特征方程为,例6 考察用迭代法解方程组的收敛性. 其中,解 方程组的迭代矩阵B的特征方程为,