数值分析第六章解线性方程组的迭代法_第1页
数值分析第六章解线性方程组的迭代法_第2页
数值分析第六章解线性方程组的迭代法_第3页
数值分析第六章解线性方程组的迭代法_第4页
数值分析第六章解线性方程组的迭代法_第5页
已阅读5页,还剩65页未读 继续免费阅读

下载本文档

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

文档简介

数值分析第六章解线性方程组的迭代法第一页,共七十页,编辑于2023年,星期六2/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis第六章解线性代数方程组的迭代法

§6.1引言§6.2几种常用的迭代格式§6.3迭代法的收敛性及误差估计§6.4判别收敛的几个常用条件§6.5迭代法收敛判定的应用举例第二页,共七十页,编辑于2023年,星期六3/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.1引言

线性方程组的数值解法有:直接法和迭代法。直接法:在假定没有舍入误差的情况下,经过有限次运算可以求得方程组的精确解;迭代法:从一个初始向量出发,按照一定的迭代格式,构造出一个趋向于真解的无穷序列。第三页,共七十页,编辑于2023年,星期六4/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.1引言当A为稀疏矩阵时,直接法将破坏矩阵A的稀疏性。系数矩阵的分类第一类:低阶稠密方程组,即系数矩阵的阶数不高,含零元素很少,在线性代数等课程学习中通常见到的,都属这类方程组;第二类:高阶稀疏方程组,系数矩阵的阶数很高,如几百阶、甚至成千上万阶,其中零元素成片分布,数量上绝对占优。第四页,共七十页,编辑于2023年,星期六5/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis迭代法适用于解大型稀疏方程组(万阶以上的方程组,系数矩阵中零元素占很大比例,而非零元按某种模式分布)问题:(1)如何构造迭代格式?

(2)迭代格式是否收敛?

(3)如何进行误差估计?§6.1引言第五页,共七十页,编辑于2023年,星期六6/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.1引言迭代法的基本思想迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组,对任选一组初始值,按某种计算规则,不断地对所得到的值进行修正,最终获得满足精度要求的方程组的近似解。

第六页,共七十页,编辑于2023年,星期六7/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis设非奇异,,则线性方程组

有惟一解,经过变换构造出一个等价同解方程组将上式改写成迭代式选定初始向量,反复不断地使用迭代式逐步逼近方程组的精确解,直到满足精度要求为止。这种方法称为迭代法第七页,共七十页,编辑于2023年,星期六8/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis

如果向量序列存在极限则称迭代法是收敛的,否则就是发散的。收敛时,在迭代公式中当时,,则故是方程组的解。对于给定的方程组可以构造各种迭代公式。并非全部收敛。第八页,共七十页,编辑于2023年,星期六9/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式雅可比(Jacobi)迭代格式例6.2.1

建立迭代格式求解方程组

方程组的精确解x*=(3,2,1)T。

第九页,共七十页,编辑于2023年,星期六10/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式建立迭代公式

第十页,共七十页,编辑于2023年,星期六11/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis取初始向量进行迭代,可以逐步得出一个近似解的序列:(k=1,2,…)直到求得的近似解能达到预先要求的精度,则迭代过程终止,以最后得到的近似解作为线性方程组的解。当迭代到第10次有计算结果表明,此迭代过程收敛于方程组的精确解x*=(3,2,1)T。

第十一页,共七十页,编辑于2023年,星期六12/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis考察一般的n元线性方程组

写成第十二页,共七十页,编辑于2023年,星期六13/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis若,分离出变量第十三页,共七十页,编辑于2023年,星期六14/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式(Jacobi迭代公式)(k=0,1,2,…)第十四页,共七十页,编辑于2023年,星期六15/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式(Jacobi迭代公式)据此建立迭代公式上式称为解方程组的Jacobi迭代公式。也称为简单迭代法。第十五页,共七十页,编辑于2023年,星期六16/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis雅可比迭代法的矩阵表示

设方程组的系数矩阵A非奇异,且主对角元素,则可将A分裂成

记作A=L+D+U第十六页,共七十页,编辑于2023年,星期六17/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis则等价于因为

,则这样便得到一个迭代公式§6.2几种常用的迭代格式(Jacobi迭代公式)第十七页,共七十页,编辑于2023年,星期六18/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis其中

令则有(k=0,1,2…)称为雅可比迭代公式,B称为雅可比迭代矩阵§6.2几种常用的迭代格式(Jacobi迭代公式)第十八页,共七十页,编辑于2023年,星期六19/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis

雅可比迭代法的算法实现

第十九页,共七十页,编辑于2023年,星期六20/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式(Jacobi迭代公式)functionX=jacobi(A,B,P,delta,max)%求解AX=B,A是非奇N阶方阵dleta是误差界,max是最大迭代次数N=length(B);fort=1:maxfork=1:NX(k)=(B(k)-A(k,[1:k-1,k+1:N])*P([1:k-1,k+1:N]))/A(k,k);enderr=abs(norm(X'-P));if(err<delta)break;endendX=X';第二十页,共七十页,编辑于2023年,星期六21/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式高斯-塞德尔(Gauss-Seidel)迭代法在Jacobi迭代法中,每次迭代只用到前一次的迭代值,若每次迭代充分利用当前最新的迭代值,即在求时用新分量代替旧分量第二十一页,共七十页,编辑于2023年,星期六22/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式Gauss-Seidel迭代法(i=1,2,…,n

k=0,1,2,…)高斯-赛德尔迭代法的迭代法格式为:第二十二页,共七十页,编辑于2023年,星期六23/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式Gauss—Seidel迭代法的矩阵表示将A分裂成A=L+D+U,则等价于

(L+D+U)x=b

于是,则高斯—塞德尔迭代过程

第二十三页,共七十页,编辑于2023年,星期六24/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式Gauss—Seidel迭代法的矩阵表示因为,所以

故则高斯-塞德尔迭代形式为:令第二十四页,共七十页,编辑于2023年,星期六25/68郑州大学研究生2011-2012学年课程数值分析

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

第二十五页,共七十页,编辑于2023年,星期六26/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式functionX=gseid(A,B,P,delta,max)%求解AX=B,A是非奇N阶方阵dleta是误差界,max是最大迭代次数N=length(B);fort=1:max

fork=1:Nifk==1X(1)=(B(1)-A(1,2:N)*P(2:N))/A(1,1);elseifk==NX(N)=(B(N)-A(N,1:N-1)*(X(1:N-1))')/A(N,N);elseX(k)=(B(k)-A(k,1:k-1)*X(1:k-1)'-A(k,k+1:N)*P(k+1:N))/A(k,k);endend

err=abs(norm(X'-P));if(err<delta)break;endendX=X';高斯-塞德尔迭代法第二十六页,共七十页,编辑于2023年,星期六27/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis例6.2.2,按高斯-塞德尔迭代公式迭代7次,得,

用高斯-塞德尔迭代法解下面线性方程组第二十七页,共七十页,编辑于2023年,星期六28/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis

由此例可知,用高斯-塞德尔迭代法,雅可比迭代法解线性方程组(且取)均收敛.

而高斯-塞德尔迭代法比雅可比迭代法收敛较快(即取相同,达到同样精度所需迭代次数较少).

但这结论只当满足一定条件时才是对的.且第二十八页,共七十页,编辑于2023年,星期六29/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式超松弛迭代法(SOR方法)

使用迭代法的困难在于难以估计其计算量。有时迭代过程虽然收敛,但由于收敛速度缓慢,使计算量变得很大而失去使用价值。因此,迭代过程的加速具有重要意义。

逐次超松弛迭代(SuccessiveOverrelaxaticMethod,简称SOR方法)法,可以看作是带参数的高斯—塞德尔迭代法,实质上是高斯-塞德尔迭代的一种加速方法。

第二十九页,共七十页,编辑于2023年,星期六30/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式超松弛迭代法的基本思想

超松弛迭代法目的是为了提高迭代法的收敛速度,在高斯—塞德尔迭代公式的基础上作一些修改。这种方法是将前一步的结果与高斯-塞德尔迭代方法的迭代值适当加权平均,期望获得更好的近似值。是解大型稀疏矩阵方程组的有效方法之一,有着广泛的应用。

第三十页,共七十页,编辑于2023年,星期六31/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式SOR方法⑴用高斯—塞德尔迭代法定义辅助量。⑵把取为与的加权平均,即

合并表示为:

第三十一页,共七十页,编辑于2023年,星期六32/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式SOR方法式中系数ω称为松弛因子,为了保证迭代过程收敛,要求0<ω<2。

当ω=1时,便为高斯-塞德尔迭代法。当0<ω<1时,低松弛法;当1<ω<2时称为超松弛法。但通常统称为超松弛法(SOR)。

第三十二页,共七十页,编辑于2023年,星期六33/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式故

令则超松弛迭代公式可写成SOR迭代法的矩阵表示第三十三页,共七十页,编辑于2023年,星期六34/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式显然对任何一个ω值,(D+ωL)非奇异,(因为假设

)于是超松弛迭代公式为(k=0,1,2,…)第三十四页,共七十页,编辑于2023年,星期六35/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis例6.2.3它的精确解为取,迭代公式为用SOR方法解方程组解第三十五页,共七十页,编辑于2023年,星期六36/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式取,取其他值,迭代次数如下表.第11次迭代结果为第三十六页,共七十页,编辑于2023年,星期六37/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis

从此例看到,松弛因子选择得好,会使SOR迭代法的收敛大大加速.本例中是最佳松弛因子.第三十七页,共七十页,编辑于2023年,星期六38/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis定义设有矩阵序列及,如果个数列极限存在且有则称收敛于,记为第三十八页,共七十页,编辑于2023年,星期六39/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis例且设,考查其极限.

解由于,当时,有设有矩阵序列所以第三十九页,共七十页,编辑于2023年,星期六40/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis定理设,则(零矩阵)的充分必要条件是矩阵的谱半径(证明参见:关治,陈景良.数值计算方法,清华大学出版社,P410~412)第四十页,共七十页,编辑于2023年,星期六41/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis矩阵的谱半径第四十一页,共七十页,编辑于2023年,星期六42/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis定理

对给定方阵G,若,则为非奇异矩阵,且

证:用反证法,若为奇异矩阵,则存在非零向量x,使,即有由相容性条件得

由于,两端消去,有,与已知条件矛盾,假设不成立,命题得证。又由于有即

将G分别取成G和-G,再取范数

又已知,有

第四十二页,共七十页,编辑于2023年,星期六43/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.3迭代法的收敛性及误差估计对于给定的方程组可以构造成雅可比迭代公式、高斯-塞德尔迭代公式和超松弛迭代公式,但并非一定收敛。现在分析它们的收敛性。对于方程组经过等价变换构造出的等价方程组

在什么条件下迭代序列收敛?第四十三页,共七十页,编辑于2023年,星期六44/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis定理6.3.1

迭代公式收敛的充分必要条件是迭代矩阵G的谱半径证:必要性设迭代公式收敛,当k→∞时,则在迭代公式两端同时取极限得记,则收敛于0(零向量),且有

于是由于可以是任意向量,故收敛于0当且仅当收敛于零矩阵,即当时所以必第四十四页,共七十页,编辑于2023年,星期六45/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis充分性:设,则必存在正数ε,使则存在某种范数

,使,,则,所以

,即。故收敛于0,

收敛于由此定理可知,不论是雅可比迭代法、高斯—塞德尔迭代法还是超松弛迭代法,它们收敛的充要条件是其迭代矩阵的谱半径。

§6.3迭代法的收敛性及误差估计第四十五页,共七十页,编辑于2023年,星期六46/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis定理6.3.2

(迭代法收敛的充分条件)若迭代矩阵G的一种范数,则迭代公式收敛,且有误差估计式,且有误差估计式及§6.3迭代法的收敛性及误差估计第四十六页,共七十页,编辑于2023年,星期六47/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.3迭代法的收敛性及误差估计证:矩阵的谱半径不超过矩阵的任一种范数,已知,因此,根据定理6.3.1可知迭代公式收敛又因为,则det(I-G)≠0,I-G为非奇异矩阵,故x=Gx+d有惟一解,即与迭代过程相比较,有第四十七页,共七十页,编辑于2023年,星期六48/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis∴

两边取范数§6.3迭代法的收敛性及误差估计第四十八页,共七十页,编辑于2023年,星期六49/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.3迭代法的收敛性及误差估计由迭代格式,有

两边取范数,代入上式,得证毕第四十九页,共七十页,编辑于2023年,星期六50/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.3迭代法的收敛性及误差估计

由定理知,当时,其值越小,迭代收敛越快,在程序设计中通常用相邻两次迭代

(ε为给定的精度要求)作为控制迭代结束的条件第五十页,共七十页,编辑于2023年,星期六51/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.4判别收敛的几个常用条件迭代法收敛的判别条件:1.Jacobi迭代法(简单迭代法)的收敛判定。2.Gauss-Seidel迭代法的收敛判定。3.SOR迭代法的收敛判定。第五十一页,共七十页,编辑于2023年,星期六52/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis定理6.4.1

设n阶方阵为对角占优阵,则它是非奇异的。证:因A为对角占优阵,其主对角元素的绝对值大于同行其它元素绝对值之和,且主对角元素全不为0,故对角阵为非奇异。作矩阵第五十二页,共七十页,编辑于2023年,星期六53/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.4判别收敛的几个常用条件利用对角占优知知非奇异,从而A非奇异,证毕

系数矩阵为对角占优阵的线性方程组称作对角占优方程组。

第五十三页,共七十页,编辑于2023年,星期六54/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.4判别收敛的几个常用条件定理6.4.2

对角占优线性方程组的雅可比迭代公式和高斯-赛德尔迭代公式均收敛。证:雅可比迭代公式的迭代矩阵为

由定理6.4.1知,这时,再由定理6.3.2知迭代收敛.再考察高斯-赛德尔迭代公式的迭代矩阵第五十四页,共七十页,编辑于2023年,星期六55/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.4判别收敛的几个常用条件令,则有即写出分量形式有设

而由上式得第五十五页,共七十页,编辑于2023年,星期六56/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.4判别收敛的几个常用条件由此整理得利用对角占优条件知上式右端小于1,(如果右端大于1,则得出与对角占优条件矛盾的结果)故有据定理6.3.2知G-S法收敛第五十六页,共七十页,编辑于2023年,星期六57/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis定理6.4.3

当系数矩阵A为正定矩阵,高斯-塞德尔迭代收敛。定理6.4.4

松弛迭代收敛的必要条件是0<ω<2§6.4判别收敛的几个常用条件第五十七页,共七十页,编辑于2023年,星期六58/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis

定理6.4.6

若A为对称正定矩阵时,则松弛迭代收敛的充要条件是.

定理6.4.5(松弛法收敛的充分条件)

如果系数矩阵A为严格对角占优,当松弛因子

时,松弛迭代法收敛。§6.4判别收敛的几个常用条件第五十八页,共七十页,编辑于2023年,星期六59/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.5迭代法收敛判定的应用举例例6.5.1

已知线性方程组考察用Jacobi迭代和G-S迭代求解时的收敛性解:⑴雅可比迭代矩阵第五十九页,共七十页,编辑于2023年,星期六60/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.5迭代法收敛判定的应用举例故Jacobi迭代收敛

第六十页,共七十页,编辑于2023年,星期六61/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.5迭代法收敛判定的应用举例故高斯—塞德尔迭代收敛。

第六十一页,共七十页,编辑于2023年,星期六62/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.5迭代法收敛判定的应用举例例6.5.2

设有迭代格式

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

第六十二页,共七十页,编辑于2023年,星期六63/68郑州大学研究生2011-2012学年课程数值分析

NumericalAnalysis§6.5迭代法收敛判定的应用举例证:因为B=I-A,故(B)=(I)-(A)=1-(A)(A)+(B)=1

由于已知(A)和(B)全为正数,

温馨提示

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

评论

0/150

提交评论