第6章 线性方程组的迭代法_第1页
第6章 线性方程组的迭代法_第2页
第6章 线性方程组的迭代法_第3页
第6章 线性方程组的迭代法_第4页
第6章 线性方程组的迭代法_第5页
已阅读5页,还剩94页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第六章解线性方程组的迭代法1.雅可比(Jacobi)迭代法2.高斯-塞德尔(Gauss-Seidel)迭代法3.超松弛迭代法(SOR方法)4.迭代法的收敛性2023/2/41

迭代法就是用某种极限过程去逐步逼近方程精确解的方法。

迭代法程序设计简单,适于自动计算,且较直接法更少的计算量,但迭代法都要考虑是否收敛和收敛速度问题。迭代法是求解线性方程组,尤其是求解大型稀疏矩阵对应方程组的重要方法之一。解线性方程组的迭代法2023/2/42

迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组,对任选一组初始值

按某种计算规则,不断地对所得到的值进行修正,最终获得满足精度要求的方程组的近似解。

收敛向量序列解向量§6.1迭代法的基本思想2023/2/43设非奇异,,将线性方程组变换为一个等价同解方程组即将上式改写成迭代式如果(2)式求极限得即是(1)式的解2023/2/44这种方法称为迭代法。迭代格式选定初始向量代入迭代格式,反复不断地使用,逐步逼近方程组的精确解,直到满足精度要求为止接下来的问题就是迭代矩阵G

的构造法。2023/2/45§6.2雅可比(Jacobi)迭代法考察一般的n元线性方程组2023/2/46§6.2雅可比(Jacobi)迭代法2023/2/47雅可比迭代法公式的分量形式为:2023/2/48求出对角线上的2023/2/49据此建立迭代公式称为解方程组的Jacobi迭代公式。或2023/2/410例1用雅可比迭代法求解方程组

解:从方程组中分离出x1,x2和

x32023/2/411建立迭代公式取初始向量进行迭代,可以逐步得出一个近似解的序列:2023/2/412计算表计算结果表明,此迭代过程收敛于方程组的精确解x*=(1.1,1.2,1.3)T。直到求得的近似解能达到预先要求的精度则迭代过程终止,2023/2/413例2用迭代法求解线性方程组

或构造方程组的等价方程组据此建立迭代公式对于给定的方程组可以构造各种迭代公式。并非全部收敛,例如:

Jacobi迭代公式。2023/2/414例2用迭代法求解线性方程组

建立迭代公式取迭代解离精确解越来越远

迭代不收敛计算得

2023/2/415§6.2.2

雅可比迭代法的矩阵表示

上面介绍的雅可比迭代公式是实际计算中经常使用的用分量形式表示的公式。设方程组

的系数矩阵A非奇异,且主对角元素

,则可将A分裂成为了讨论雅可比迭代法的收敛性,需介绍的雅可比迭代法的矩阵形式。2023/2/416§6.2.2

雅可比迭代法的矩阵表示记作A=D-L-U2023/2/417则等价于即这样便得到一个迭代公式令则有称为雅可比迭代公式,B

称为雅可比迭代矩阵2023/2/418则有2023/2/4192023/2/4206.2.1雅可比迭代法的算法实现2023/2/421§6.3高斯-塞德尔(Gauss-Seidel)迭代法§6.3.1

高斯-塞德尔迭代法的基本思想

在Jacobi迭代法中,每次迭代只用到前一次的迭代值,若每次迭代充分利用当前最新的迭代值,即在求时用已经求出的新分量代替旧分量,就得到高斯-赛德尔迭代法。2023/2/422高斯-塞德尔迭代法公式的分量形式。即(k=0,1,2,…)2023/2/423高斯-赛德尔迭代法迭代法格式简写为:

(i=1,2,…,n,k=0,1,2,…)2023/2/424例3用GaussSeidel迭代格式解方程组

精度要求为ε=0.005

解Jacobi

迭代格式为取初始迭代向量,迭代结果为:

GaussSeidel

迭代格式为2023/2/4252023/2/426§

6.3.2Gauss—Seidel

迭代法的矩阵表示将A分裂成A=D-L-U,则Ax=b

等价于

(D-L-U)x=b

则高斯-塞德尔迭代形式为:

令因为

,所以

于是,则高斯—塞德尔迭代过程2023/2/427§

6.3.2Gauss—Seidel

迭代法的矩阵表示

则高斯-塞德尔迭代形式为:

2023/2/428§

6.3.3高斯—塞德尔迭代算法实现高斯-塞德尔迭代算法的计算步骤与流程图与雅可比迭代法大致相同,只是一旦求出变元的某个新值后,就改用新值替代老值,进行这一步剩下的计算。

2023/2/429§6.4超松弛迭代法(SOR方法)

使用迭代法的困难在于难以估计其计算量。有时迭代过程虽然收敛,但由于收敛速度缓慢,使计算量变得很大而失去使用价值。因此,迭代过程的加速具有重要意义。逐次超松弛迭代法(SuccessiveOverRelaxaticMethod,简称SOR方法),可以看作是带参数的高斯—塞德尔迭代法,实质上是高斯-塞德尔迭代的一种加速方法。

2023/2/430

超松弛迭代法目的是为了提高迭代法的收敛速度,在高斯—塞德尔迭代公式的基础上作一些修改。这种方法是将前一步的结果与高斯-塞德尔迭代方法的迭代值

适当加权平均,期望获得更好的近似值

。是解大型稀疏矩阵方程组的有效方法之一,有着广泛的应用。§6.4.1超松弛迭代法的基本思想2023/2/431合并表示为:SOR方法具体计算公式如下:⑴用高斯—塞德尔迭代法计算⑵把

取为

的加权平均,即

前后两次迭代结果加权平均2023/2/432式中系数ω称为松弛因子,当ω=1时,便为高斯-塞德尔迭代法。为了保证迭代过程收敛,要求0<ω<2。当0<ω<1时,低松弛法;当1<ω<2时称为超松弛法。但通常统称为超松弛法(SOR)。2023/2/433§

6.4.2超松弛迭代法的矩阵表示设线性方程组

Ax=b的系数矩阵A非奇异,且主对角元素

,

则将A分裂成A=d-L-U,则超松弛迭代公式用矩阵表示为或故

2023/2/434§

6.4.2超松弛迭代法的矩阵表示显然对任何一个ω值,(D-ωL)非奇异,(因为假设

)

于是超松弛迭代公式为令则超松弛迭代公式可写成2023/2/435例4用SOR法求解线性方程组

取ω=1.46,要求

解:SOR迭代公式

k=0,1,2,…,

初值2023/2/436该方程组的精确解只需迭代20次便可达到精度要求.如果取ω=1(即高斯—塞德尔迭代法)和同一初值,要达到同样精度,需要迭代110次.2023/2/437§

6.5迭代法的收敛性我们知道,对于给定的方程组可以构造成简单迭代、雅可比迭代、高斯-塞德尔迭代和超松弛迭代公式,但并非一定收敛。现在分析它们的收敛性。在什么条件下迭代序列收敛?经过等价变换构造出的等价方程组

对于方程组得到迭代序列2023/2/438§5.7向量和矩阵的范数

向量范数是用来度量向量长度的,它可以看作是解析几何中二、三维向量长度概念的推广。用Rn表示n维实向量空间。为了研究线性方程组近似解的误差和迭代法的收敛性,有必要对向量及矩阵的“大小”引进某种度量----范数的概念。2023/2/439记笔记定义5.2

对任一向量XRn,按照一定规则确定一个实数与它对应,该实数记为||X||,若||X||满足下面三个性质:则称该实数||X||为向量X的范数(1)||X||0;||X||=0当且仅当X=0;(2)对任意实数,||X||=||||X||;(3)对任意向量YRn,||X+Y||||X||+||Y||2023/2/440在Rn中,常用的几种向量范数有:记笔记其中x1,x2,…,xn分别是X的第n个分量,以上定义的范数分别称为

-范数,1-范数和2-范数.可以验证它们都是满足范数性质的,其中是由内积导出的向量范数。2023/2/441定理5.1对于任意向量x,有即

当p→∞,

证:其中2023/2/442当不需要指明使用哪一种向量范数时,就用记号||.||泛指任何一种向量范数。有了向量的范数就可以用它来衡量向量的大小和表示向量的误差。设x*为Ax=b的精确解,x为其近似解,则其绝对误差可表示成||x-x*||,其相对误差可表示成记笔记或2023/2/4432023/2/444例5.11设,计算

解:2023/2/445定义5.4(向量序列的极限)设为中的一向量序列,,记。如果(i=1,2,…,n),则称收敛于向量,记为

定理5.2(向量范数的等价性)设

上任意两种向量范数,则存在常数

C1,,C2>0,

使得对任意

恒有(证:略)

2023/2/446定理5.3

其中为向量中的任一种范数。证由于对于上的任一种范数,由定理5.2知存在常数C1,C2,使于是可得从而定理得证。2023/2/447定义5.5(矩阵的范数)如果矩阵的某个

非负的实值函数,满足则称是上的一个矩阵范数(或模)(相容性)2023/2/448矩阵范数通常要求满足与向量范数相容即:于是矩阵范数可由向量范数定义这样定义的矩阵范数称为由向量范数导出的矩阵范数2023/2/449矩阵范数的计算公式定理8对n

阶方阵(矩阵A的行范数)(矩阵A的列范数)(矩阵A的2-范数)2023/2/450(矩阵A的行范数)(每行绝对值相加化为列向量的范数)2023/2/451证明:2023/2/452例5.12计算方阵

的三种范数

解2023/2/453例5.12计算方阵

的三种范数

解先计算

所以从而

2023/2/454定义5.7(矩阵的谱半径)设的特征值为,称为A的谱半径。定理5.8设A为n阶方阵,则对任意矩阵范数都有2023/2/455定理5.8设A为n阶方阵,则对任意矩阵范数都有由于x≠0,故,所以证:设为A的特征值,x是对应于的特征向量,则两端取范数并依据其性质得因此讨论A的特征值与范数的关系2023/2/456矩阵范数是矩阵谱半径的上界对称矩阵的谱半径恰好等于矩阵的2范数2023/2/457定理1其中为矩阵的任一范数。定理22023/2/458证:必要性由于可以是任意向量,故收敛于0当且仅当收敛于零矩阵,即当时,

基本定理5

迭代公式收敛的充要条件是迭代矩阵G

的谱半径则在迭代公式两端同时取极限得设迭代公式收敛,当k→∞时,2023/2/459充分性:设,则必存在正数ε,使则存在某种范数

,使,由此定理可知,不论是雅可比迭代法、高斯—塞德尔迭代法还是超松弛迭代法,它们收敛的充要条件都是其迭代矩阵的谱半径2023/2/460前例2用迭代法求解线性方程组

构造的等价方程组据此建立迭代公式

并非所有迭代公式都收敛,例如:

迭代矩阵G=,其特征多项式为特征值为-2,-3,所以迭代发散2023/2/461前例2用迭代法求解线性方程组

构造的等价方程组雅可比迭代据此建立迭代公式迭代矩阵,所以迭代收敛其特征多项式为2023/2/462若迭代矩阵G的一种范数,则迭代公式收敛,且有误差估计式及

计算十分麻烦,因此将定理5改为定理6(迭代法收敛的充分条件)初值选择巡环结束①②2023/2/463若,则迭代公式收敛,且有误差估计式

及证:矩阵的谱半径不超过矩阵的任一种范数,即根据定理5可知迭代公式收敛。定理6(迭代法收敛的充分条件)2023/2/464因为,故x=Gx+d

有惟一解,即两边取范数与迭代过程相比较,有:①2023/2/465由迭代格式,有

两边取范数,得证毕②2023/2/466由定理知,当时迭代收敛,值越小,迭代收敛越快,在程序设计中通常用相邻两次迭代(ε为给定的精度要求)作为控制迭代结束的条件,只要迭代收敛与初值无关。2023/2/467例5已知线性方程组考察用Jacobi迭代和Gauss-Seidel迭代求解时的收敛性解:⑴雅可比迭代矩阵

2023/2/468例5已知线性方程组,考察Jacobi

迭代的收敛性故Jacobi

迭代收敛

解:雅可比迭代矩阵

2023/2/469⑵高斯-塞德尔迭代,系数矩阵

高斯-塞德尔迭代矩阵

2023/2/470高斯-塞德尔迭代矩阵

故高斯—塞德尔迭代收敛。

2023/2/471定理7

设n阶方阵为严格对角占优阵,则

A为非奇异阵。证:因A为对角占优阵,其主对角元素的绝对值大于同行其它元素绝对值之和,且主对角元素全不为0,故对角阵为非奇异。作矩阵2023/2/472利用对角占优知由定理知非奇异,从而A非奇异,证毕系数矩阵为严格对角占优矩阵的线性方程组称为对角占优方程组。结论:严格对角占优线性方程组的雅可比迭代公式和高斯-赛德尔迭代公式均收敛。2023/2/473例6

设证明,方程组

的Jacobi迭代与G-S迭代同时收敛或发散证:雅可比迭代矩阵其谱半径2023/2/474例6

设证明,方程组

的Jacobi迭代与G-S迭代同时收敛或发散G-S迭代矩阵2023/2/475G-S迭代矩阵其谱半径显然,和同时小于、等于或大于1,因而Jacobi

迭代法与G-S迭代法具有相同的收敛性。2023/2/476例7

考察用雅可比迭代法和高斯-塞德尔迭代法解线性方程组Ax=b

的收敛性,其中解:先计算迭代矩阵说明什么问题?2023/2/477求特征值雅可比矩阵

∴用雅可比迭代法求解时,迭代过程收敛(B)=0<12023/2/4781=0,2=2,3=2(G1)=2>1

∴用高斯-塞德尔迭代法求解时,迭代过程发散高斯-塞德尔迭代矩阵求特征值2023/2/479∴

Ax=b的系数矩阵按行严格对角占优,故高斯-塞德尔迭代收敛例8

设有迭代格式X(k+1)=B

X(k)+g

(k=0,1,2……)

其中B=I-A,如果A和B的特征值全为正数,试证:该迭代格式收敛。分析:根据A,B和单位矩阵I之间的特征值的关系导出(B)<1,从而说明迭代格式收敛。证:2023/2/480例9

设方程组写出解方程组的Jacobi迭代公式和迭代矩阵并讨论迭代收敛的条件。写出解方程组的Gauss-Seidel迭代矩阵,并讨论迭代收敛的条件。2023/2/481例9

设方程组写出解方程组的Jacobi迭代公式和迭代矩阵并讨论迭代收敛的条件。解①Jacobi迭代公式和Jacobi矩阵分别为

2023/2/482例9设方程组写出解方程组的Gauss-Seidel迭代矩阵,并讨论迭代收敛的条件。Gauss-Seidel格式,对任意初值x(0)均收敛。解②Gauss-Seidel矩阵为2023/2/483解:先计算迭代矩阵例10

讨论用雅可比迭代法和高斯-塞德尔迭代法解线性方程组Ax=b的收敛性。2023/2/484求特征值雅可比矩阵

(B)=1∴用雅可比迭代法求解时,迭代过程不收敛1=-1,2,3=1/22023/2/485求特征值高斯-塞德尔迭代矩阵

∴用高斯-塞德尔迭代法求解时,迭代过程收敛1=0,(G1)=0.3536<12023/2/486解:所给迭代公式的迭代矩阵为2023/2/487取0<<1/2迭代收敛2023/2/488例12

设求解线性方程组Ax=b的简单迭代法

x(k+1)=Bx(k)+g(k=0,1,2,……)

收敛,求证:对0<<1,迭代法

x(k+1)=[(1-)I+B]x(k)+g(k=0,1,2,…)

收敛。证:设C=(1-)I+B,(C)和(B)分别为C和B

的特征值,则显然(C)=(1-)+(B)

因为0<<1,(C)是1和(B)的加权平均,

且由迭代法

x(k+1)=Bx(k)+g(k=0,1,2,……)收敛知|(B)|<1,故|(C)|<1,从而(C)<1,即x(k+1)=[(1-)I+B]x

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论