_解线性方程组的迭代法.ppt

《_解线性方程组的迭代法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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=B0

2、x+f，其中我们任取初始值，例如取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.

3、即有对于任何一个方程组x=Bx+f(由Ax=b变形得到的等价方程组)，由迭代法产生的向量序列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)逐步代入求近似解的方法称为迭代法(或称为一阶定常

4、迭代法，这里B与k无关).B称为迭代矩阵.(2)如果limx(k)(k→∞)存在(记为x*),称此迭代法收敛,显然x*就是方程组的解,否则称此迭代法发散.由上述讨论，需要研究{x(k)}的收敛性.引进误差向量由(1.6)减去(1.5)式，得ε(k+1)=Bε(k)(k=0,1,2,)，递推得要考察{x(k)}的收敛性，就要研究B在什么条件下有limε(k)=0(k→∞)，亦即要研究B满足什么条件时有Bk→0(零向量)(k→∞).6.2基本迭代法其中，A=(aij)∈Rn×n为非奇异矩阵，下面研究任何建立Ax=b的各种迭代法

5、.设线性方程组Ax=b，(2.1)其中，M为可选择的非奇异矩阵，且使Mx=d容易求解，一般选择A的某种近似，称M为分裂矩阵.将A分裂为A=M-N.(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的各种迭代法.设aii0(i=1,2,,n)，并将A写成三部分即A=D-L-U6.2.1雅可比(Jacobi)迭代法设aii0(i=1,2,,n)，选取M为A的对角元

6、素部分,即选取M=D(对角阵)，A=D-N，由(2.3)式得到解方程组Ax=b的雅可比(Jacobi)迭代法.又称简单迭代法.其中B=I-D-1A=D-1(L+U)=J,f=D-1b.称J为解Ax=b的雅可比迭代法的迭代矩阵.于是雅可比迭代法可写为矩阵形式其Jacobi迭代矩阵为下面给出雅可比迭代法(2.5)的分量计算公式,记由雅可比迭代法(2.5)有每一个分量写出来为即当aii0时，有等价方程组其中aii(i)0(i=1,2,,n)即由方程组Ax=b得到的建立的雅可比迭代格式为于是，解Ax=b的雅可比迭代法的计算公式

7、为由(2.6)式可知，雅可比迭代法计算公式简单，每迭代一次只需计算一次矩阵和向量的乘法且计算过程中原始矩阵A始终不变.6.2.2高斯－赛德尔迭代法在Jacobi迭代中，计算xi(k+1)(2in)时，使用xj(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)式得到解

8、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)有每一个分量写出来为即当aii0时，有(与前面一样的式子